Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Cited by 196

The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.

Metrics for graph comparison: A practitioner’s guide

Open access
Wills, Peter, Meyer, François G. · 2020 · PLOS ONE

Published version of a preprint

Abstract

Comparison of graph structure is a ubiquitous task in data analysis and machine learning, with diverse applications in fields such as neuroscience, cyber security, social network analysis, and bioinformatics, among others. Discovery and comparison of structures such as modular communities, rich clubs, hubs, and trees yield insight into the generative mechanisms and functional properties of the graph. Often, two graphs are compared via a pairwise distance measure, with a small distance indicating structural similarity and vice versa. Common choices include spectral distances and distances based on node affinities. However, there has of yet been no comparative study of the efficacy of these distance measures in discerning between common graph topologies at different structural scales. In this work, we compare commonly used graph metrics and distance measures, and demonstrate their ability to discern between common topological features found in both random graph models and real world networks. We put forward a multi-scale picture of graph structure wherein we study the effect of global and local structures on changes in distance measures. We make recommendations on the applicability of different distance measures to the analysis of empirical graph data based on this multi-scale view. Finally, we introduce the Python library NetComp that implements the graph distances used in this work.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1371/journal.pone.0228728

Cites

23 of 23 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 23 references

Research works printed but not linked: 95

  1. D J Cook, 2006, Mining Graph Data, 10.1002/0470073047 · DOI · Paper page
  2. JM Haslbeck, 2018, How well do network models predict observations? On the importance of predictability in network models, Behavior research methods, 50, 853, 10.3758/s13428-017-0910-x · DOI · Paper page
  3. W Liu, 2019, Learning Graph Topological Features via GAN, IEEE Access, 7, 21834, 10.1109/ACCESS.2019.2898693 · DOI
  4. C Donnat, 2018, Tracking network dynamics: A survey using graph distances, The Annals of Applied Statistics, 12, 971, 10.1214/18-AOAS1176 · DOI
  5. AL Barabási, 1999, Emergence of scaling in random networks, Science, 286, 509, 10.1126/science.286.5439.509 · DOI · Paper page
  6. DJ Watts, 1998, Collective dynamics of ‘small-world’ networks, Nature, 393, 440, 10.1038/30918 · DOI · Paper page
  7. ND Monnig, 2018, The resistance perturbation distance: A metric for the analysis of dynamic networks, Discrete Applied Mathematics, 236, 347, 10.1016/j.dam.2017.10.007 · DOI
  8. RC Wilson, 2008, A study of graph spectra for comparing graphs and trees, Pattern Recognition, 41, 2833, 10.1016/j.patcog.2008.03.011 · DOI · Paper page
  9. T Biyikoglu, 2007, Laplacian eigenvectors of graphs: Perron-Frobenius and Faber-Krahn type theorems, 10.1007/978-3-540-73510-6 · DOI · Paper page
  10. Rudin W. Functional Analysis. International series in pure and applied mathematics. McGraw-Hill; 1991. Available from: https://books.google.com/books?id=Sh_vAAAAMAAJ.
  11. S de Lange, 2014, The Laplacian spectrum of neural networks, Frontiers in computational neuroscience, 7, 189, 10.3389/fncom.2013.00189 · DOI
  12. JR Lee, 2014, Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities, J ACM, 61, 37:1
  13. WH Haemers, 2004, Enumeration of cospectral graphs, European Journal of Combinatorics, 25, 199, 10.1016/S0195-6698(03)00100-8 · doi:10.1016/s0195-6698(03)00100-8
  14. AJ Schwenk, 1973, Almost all trees are cospectral, New directions in the theory of graphs, 275
  15. S Bhamidi, 2012, Spectra of Large Random Trees, Journal of Theoretical Probability, 25, 613, 10.1007/s10959-011-0360-9 · DOI
  16. IJ Farkas, 2001, Spectra of “real-world” graphs: Beyond the semicircle law, Physical Review E, 64, 10.1103/PhysRevE.64.026704 · DOI · Paper page
  17. EP Wigner, 1958, On the Distribution of the Roots of Certain Symmetric Matrices, The Annals of Mathematics, 67, 325, 10.2307/1970008 · DOI · Paper page
  18. S O’Rourke, 2010, Gaussian Fluctuations of Eigenvalues in Wigner Random Matrices, Journal of Statistical Physics, 138, 1045, 10.1007/s10955-009-9906-y · doi:10.1007/s10955-009-9906-y
  19. Chung FRK. Spectral Graph Theory. American Mathematical Society; 1997. · DOI · Paper page
  20. J Friedman, 2004, Wave equations for graphs and the edge-based Laplacian, Pacific Journal of Mathematics, 216, 229, 10.2140/pjm.2004.216.229 · doi:10.2140/pjm.2004.216.229
  21. C Maas, 1985, Computing and interpreting the adjacency spectrum of traffic networks, Journal of Computational and Applied Mathematics, 12-13, 459, 10.1016/0377-0427(85)90039-1 · doi:10.1016/0377-0427(85)90039-1
  22. Moore EF. The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching. 1959; p. 285–292.
  23. W Ellens, 2011, Effective graph resistance, Linear Algebra and its Applications, 435, 2491, 10.1016/j.laa.2011.02.024 · DOI
  24. TH Haveliwala, 2003, Topic-sensitive PageRank: a context-sensitive ranking algorithm for Web search, IEEE Transactions on Knowledge and Data Engineering, 15, 784, 10.1109/TKDE.2003.1208999 · DOI · Paper page
  25. W Goddard, 2011, Structural Analysis of Complex Networks, 49, 10.1007/978-0-8176-4789-6_3 · doi:10.1007/978-0-8176-4789-6_3
  26. P Wills, 2020, Complex Networks and Their Applications VIII, 211, 10.1007/978-3-030-36687-2_18 · DOI
  27. D Koutra, 2016, Delta Con: Principled Massive-Graph Similarity Function with Attribution, ACM Transactions on Knowledge Discovery from Data (TKDD), 10, 28, 10.1145/2824443 · DOI
  28. D Koutra, 2011, Machine Learning and Knowledge Discovery in Databases, 245, 10.1007/978-3-642-23783-6_16 · DOI
  29. M Berlingerio, 2012, NetSimile: A Scalable Approach to Size-Independent Network Similarity, CoRR
  30. DS Bassett, 2008, Hierarchical organization of human cortical networks in health and schizophrenia, Journal of Neuroscience, 28, 9239, 10.1523/JNEUROSCI.1929-08.2008 · DOI · Paper page
  31. M Kaiser, 2011, A tutorial in connectome analysis: topological and spatial features of brain networks, Neuroimage, 57, 892, 10.1016/j.neuroimage.2011.05.025 · DOI · Paper page
  32. MP van den Heuvel, 2013, Abnormal rich club organization and functional brain dynamics in schizophrenia, JAMA Psychiatry, 70, 783, 10.1001/jamapsychiatry.2013.1328 · DOI · Paper page
  33. Yanardag P, Vishwanathan S. Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2015. p. 1365–1374. · DOI · Paper page
  34. Li Y, Gu C, Dullien T, Vinyals O, Kohli P. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. arXiv preprint arXiv:190412787. 2019.
  35. Fout A, Byrd J, Shariat B, Ben-Hur A. Protein interface prediction using graph convolutional networks. In: Advances in Neural Information Processing Systems; 2017. p. 6530–6539.
  36. Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE. Neural message passing for quantum chemistry. In: Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org; 2017. p. 1263–1272.
  37. Ktena SI, Parisot S, Ferrante E, Rajchl M, Lee M, Glocker B, et al. Distance metric learning using graph convolutional networks: Application to functional brain networks. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer; 2017. p. 469–477. · DOI · Paper page
  38. K Preuer, 2018, Fréchet ChemNet distance: a metric for generative models for molecules in drug discovery, Journal of chemical information and modeling, 58, 1736, 10.1021/acs.jcim.8b00234 · DOI · Paper page
  39. Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:160902907. 2016.
  40. Li Y, Tarlow D, Brockschmidt M, Zemel R. Gated graph sequence neural networks. arXiv preprint arXiv:151105493. 2015.
  41. Monti F, Boscaini D, Masci J, Rodolà E, Svoboda J, Bronstein MM. Geometric deep learning on graphs and manifolds using mixture model CNNs. arXiv preprint arXiv:161108402. 2016. · DOI · Paper page
  42. F Scarselli, 2009, The graph neural network model, IEEE Transactions on Neural Networks, 20, 61, 10.1109/TNN.2008.2005605 · DOI · Paper page
  43. Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:13126203. 2013.
  44. Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in neural information processing systems; 2016. p. 3844–3852.
  45. Battaglia PW, Hamrick JB, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:180601261. 2018.
  46. Kriege NM, Johansson FD, Morris C. A Survey on Graph Kernels. arXiv preprint arXiv:190311835. 2019. · DOI · Paper page
  47. Xu K, Hu W, Leskovec J, Jegelka S. How powerful are graph neural networks? arXiv preprint arXiv:181000826. 2018.
  48. Morris C, Ritzert M, Fey M, Hamilton WL, Lenssen JE, Rattan G, et al. Weisfeiler and Leman go neural: Higher-order graph neural networks. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33; 2019. p. 4602–4609. · DOI · Paper page
  49. L Oneto, 2017, Measuring the expressivity of graph kernels through statistical learning theory, Neurocomputing, 268, 4, 10.1016/j.neucom.2017.02.088 · DOI
  50. M Gromov, 2007, Metric structures for Riemannian and non-Riemannian spaces
  51. M Berger, 2003, A Panoramic View of Riemannian Geometry, 10.1007/978-3-642-18245-7 · DOI · Paper page
  52. C Villani, 2008, Optimal transport: old and new
  53. F Mémoli, 2005, A theoretical and computational framework for isometry invariant recognition of point cloud data, Foundations of Computational Mathematics, 5, 313, 10.1007/s10208-004-0145-y · DOI · Paper page
  54. F Mémoli, 2011, Gromov–Wasserstein distances and the metric approach to object matching, Foundations of computational mathematics, 11, 417, 10.1007/s10208-011-9093-5 · DOI · Paper page
  55. VM Panaretos, 2019, Statistical aspects of Wasserstein distances, Annual review of statistics and its application, 6, 405, 10.1146/annurev-statistics-030718-104938 · DOI · Paper page
  56. G Peyré, 2019, Computational optimal transport, Foundations and Trends® in Machine Learning, 11, 355, 10.1561/2200000073 · DOI · Paper page
  57. Wu L, Yen IEH, Xu K, Zhao L, Xia Y, Witbrock M. From Node Embedding to Graph Embedding: Scalable Global Graph Kernel via Random Features; 2018. · doi:10.1145/3292500.3330918
  58. Xu H, Luo D, Zha H, Carin L. Gromov-wasserstein learning for graph matching and node embedding. arXiv preprint arXiv:190106003. 2019.
  59. Titouan V, Courty N, Tavenard R, Laetitia C, Flamary R. Optimal Transport for structured data with application on graphs. In: International Conference on Machine Learning; 2019. p. 6275–6284.
  60. R Bhatia, 2019, Matrix versions of the Hellinger distance, Letters in Mathematical Physics, 1
  61. R Bhatia, 2019, On the Bures–Wasserstein distance between positive definite matrices, Expositiones Mathematicae, 37, 165, 10.1016/j.exmath.2018.01.002 · DOI
  62. P Rezaeinia, 2020, Identifying Brain Network Topology Changes in Task Processes and Psychiatric Disorders, Network Neuroscience, 0, 1
  63. CH Papadimitriou, 2003, Encyclopedia of Computer Science, 260
  64. N Halko, 2011, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review, 53, 217, 10.1137/090771806 · DOI · Paper page
  65. JA Bondy, 2008, Graph Theory, 10.1007/978-1-84628-970-5 · DOI · Paper page
  66. Zhou D, Huang J, Schölkopf B. Learning from Labeled and Unlabeled Data on a Directed Graph. In: Proceedings of the 22nd International Conference on Machine Learning. New York, NY, USA: ACM; 2005. p. 1036–1043. · DOI · Paper page
  67. E Abbe, 2016, Exact recovery in the stochastic block model, IEEE Transactions on Information Theory, 62, 471, 10.1109/TIT.2015.2490670 · DOI
  68. GU Yule, 1925, A Mathematical Theory of Evolution, based on the Conclusion of Dr. J. C. Willis, F.R.S, Philisophical Transactions of the Royal Society B, 213, 402
  69. R Durrett, 2007, Random graph dynamics
  70. R Van Der Hofstad, 2016, Random graphs and complex networks, 10.1017/9781316779422 · DOI · Paper page
  71. Flaxman A, Frieze A, Fenner T. High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003. Proceedings. Springer Berlin Heidelberg; 2003. p. 264–274. Available from: https://doi.org/10.1007/978-3-540-45198-3_23. · DOI
  72. EA Bender, 1978, The asymptotic number of labeled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 296, 10.1016/0097-3165(78)90059-6 · DOI · Paper page
  73. X Zhang, 2014, Spectra of random graphs with community structure and arbitrary degrees, Phys Rev E, 89, 042816, 10.1103/PhysRevE.89.042816 · doi:10.1103/physreve.89.042816
  74. M Bayati, 2010, A Sequential Algorithm for Generating Random Graphs, Algorithmica, 58, 860, 10.1007/s00453-009-9340-1 · DOI
  75. J Blitzstein, 2011, A sequential importance sampling algorithm for generating random graphs with prescribed degrees, Internet mathematics, 6, 489, 10.1080/15427951.2010.557277 · DOI · Paper page
  76. 2012, Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
  77. Wolfe PJ, Olhede SC. Nonparametric graphon estimation. arXiv preprint arXiv:13095936. 2013.
  78. Li Y, Vinyals O, Dyer C, Pascanu R, Battaglia P. Learning deep generative models of graphs. arXiv preprint arXiv:180303324. 2018.
  79. You J, Ying R, Ren X, Hamilton WL, Leskovec J. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:180208773. 2018.
  80. Shine A, Kempe D. Generative Graph Models based on Laplacian Spectra? In: The World Wide Web Conference. ACM; 2019. p. 1691–1701. · DOI
  81. Dehmamy N, Barabási AL, Yu R. Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology. arXiv preprint arXiv:190705008. 2019.
  82. J Stehlé, 2011, High-resolution measurements of face-to-face contact patterns in a primary school, PloS one, 6, e23176, 10.1371/journal.pone.0023176 · DOI · Paper page
  83. J Leskovec, 2007, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), 1, 2, 10.1145/1217299.1217301 · DOI · Paper page
  84. A Fornito, 2016, Fundamentals of Brain Network Analysis
  85. V Subbaraju, 2017, Identifying differences in brain activities and an accurate detection of autism spectrum disorder using resting state functional-magnetic resonance imaging: A spatial filtering approach, Medical Image Analysis, 35, 375, 10.1016/j.media.2016.08.003 · DOI
  86. G Casella, 2002, Statistical inference
  87. Hajij M, Wang B, Scheidegger C, Rosen P. Visual detection of structural changes in time-varying graphs using persistent homology. In: 2018 IEEE Pacific Visualization Symposium (PacificVis). IEEE; 2018. p. 125–134. · DOI
  88. Gutfraind A, Safro I, Meyers LA. Multiscale network generation. In: 2015 18th International Conference on Information Fusion (Fusion). IEEE; 2015. p. 158–165.
  89. U Von Luxburg, 2007, A tutorial on spectral clustering, Statistics and computing, 17, 395, 10.1007/s11222-007-9033-z · DOI · Paper page
  90. FG Meyer, 2014, Perturbation of the eigenvectors of the graph Laplacian: Application to image denoising, Applied and Computational Harmonic Analysis, 36, 326, 10.1016/j.acha.2013.06.004 · DOI
  91. G Cheung, 2018, Graph spectral image processing, Proceedings of the IEEE, 106, 907, 10.1109/JPROC.2018.2799702 · DOI · Paper page
  92. C Geniesse, 2019, Generating dynamical neuroimaging spatiotemporal representations (DyNeuSR) using topological data analysis, Network Neuroscience, 3, 763, 10.1162/netn_a_00093 · DOI
  93. MK Chung, 2019, Exact topological inference of the resting-state brain networks in twins, Network Neuroscience, 0, 1
  94. J Rasero, 2018, Predicting functional networks from region connectivity profiles in task-based versus resting-state fMRI data, PloS one, 13, e0207385, 10.1371/journal.pone.0207385 · DOI
  95. Roli F, Giacinto G, Vernazza G. Methods for Designing Multiple Classifier Systems. In: Multiple Classifier Systems: Second International Workshop, MCS 2001 Cambridge, UK, July 2–4, 2001 Proceedings. Springer Berlin Heidelberg; 2001. p. 78–87. Available from: https://doi.org/10.1007/3-540-48219-9_8. · DOI

Cited by

See all 196

Metadata

Authors
Wills, P., & Meyer, F. G.
Venue
PLOS ONE
Published
2020-02-12
Volume
15
Issue
2
Pages
e0228728
ISSN
1932-6203 (ISSN-L)
OpenAlex
W2939135441
Cited by
196
References
23
FWCI
10.57
Type
journal article
Language
en
Open access
gold
Funders
National Science Foundation (CCF/CIF 1815971)

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Metrics for graph comparison: A practitioner’s guide. https://app.cochat.ai/papers/10.1371/journal.pone.0228728
The paper
Wills, P., & Meyer, F. G. (2020). Metrics for graph comparison: A practitioner’s guide. PLOS ONE. https://doi.org/10.1371/journal.pone.0228728

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.