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 accessPublished 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.
Integrity signals
Registry
Cites
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.
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
Tzourio-Mazoyer, N., Landeau, B., Papathanassiou, D., Crivello, F., Etard, O., Delcroix, N., Mazoyer, B., & Joliot, M. (2002) · NeuroImage · doi:10.1006/nimg.2001.0978 · Cited by 16,319
Complex brain networks: graph theoretical analysis of structural and functional systems
Bullmore, E., & Sporns, O. (2009) · Nature Reviews Neuroscience · doi:10.1038/nrn2575 · Cited by 11,820
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582
Exploring Network Structure, Dynamics, and Function Using NetworkX
Hagberg, A. A., Schult, D. A., & Swart, P. J. (2008) · Proceedings of the Python in Science Conference · doi:10.25080/tcwv9851 · Cited by 7,477 · cited 2×
“Most of the models in this work are sampled via the Python package NetworkX [84]; details of implementation can be found in the source code of the same.”
MethodGraph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Di Martino, A., Yan, C.-G., Li, Q., Denio, E., Castellanos, F. X., Alaerts, K., Anderson, J. S., Assaf, M., Bookheimer, S. Y., Dapretto, M., et al. (2014) · Molecular Psychiatry · doi:10.1038/mp.2013.78 · Cited by 2,780
Holme, P., & Saramäki, J. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.03.001 · Cited by 2,736
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639
Organization, development and function of complex brain networks
SPORNS, O., CHIALVO, D., KAISER, M., & HILGETAG, C. (2004) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2004.07.008 · Cited by 2,055
Research works printed but not linked: 95
- D J Cook, 2006, Mining Graph Data, 10.1002/0470073047 · DOI · Paper page
- 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
- W Liu, 2019, Learning Graph Topological Features via GAN, IEEE Access, 7, 21834, 10.1109/ACCESS.2019.2898693 · DOI
- C Donnat, 2018, Tracking network dynamics: A survey using graph distances, The Annals of Applied Statistics, 12, 971, 10.1214/18-AOAS1176 · DOI
- AL Barabási, 1999, Emergence of scaling in random networks, Science, 286, 509, 10.1126/science.286.5439.509 · DOI · Paper page
- DJ Watts, 1998, Collective dynamics of ‘small-world’ networks, Nature, 393, 440, 10.1038/30918 · DOI · Paper page
- 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
- 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
- T Biyikoglu, 2007, Laplacian eigenvectors of graphs: Perron-Frobenius and Faber-Krahn type theorems, 10.1007/978-3-540-73510-6 · DOI · Paper page
- Rudin W. Functional Analysis. International series in pure and applied mathematics. McGraw-Hill; 1991. Available from: https://books.google.com/books?id=Sh_vAAAAMAAJ.
- S de Lange, 2014, The Laplacian spectrum of neural networks, Frontiers in computational neuroscience, 7, 189, 10.3389/fncom.2013.00189 · DOI
- JR Lee, 2014, Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities, J ACM, 61, 37:1
- 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
- AJ Schwenk, 1973, Almost all trees are cospectral, New directions in the theory of graphs, 275
- S Bhamidi, 2012, Spectra of Large Random Trees, Journal of Theoretical Probability, 25, 613, 10.1007/s10959-011-0360-9 · DOI
- IJ Farkas, 2001, Spectra of “real-world” graphs: Beyond the semicircle law, Physical Review E, 64, 10.1103/PhysRevE.64.026704 · DOI · Paper page
- 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
- 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
- Chung FRK. Spectral Graph Theory. American Mathematical Society; 1997. · DOI · Paper page
- 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
- 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
- Moore EF. The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching. 1959; p. 285–292.
- W Ellens, 2011, Effective graph resistance, Linear Algebra and its Applications, 435, 2491, 10.1016/j.laa.2011.02.024 · DOI
- 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
- 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
- P Wills, 2020, Complex Networks and Their Applications VIII, 211, 10.1007/978-3-030-36687-2_18 · DOI
- 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
- D Koutra, 2011, Machine Learning and Knowledge Discovery in Databases, 245, 10.1007/978-3-642-23783-6_16 · DOI
- M Berlingerio, 2012, NetSimile: A Scalable Approach to Size-Independent Network Similarity, CoRR
- 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
- 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
- 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
- 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
- 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.
- 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.
- 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.
- 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
- 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
- Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:160902907. 2016.
- Li Y, Tarlow D, Brockschmidt M, Zemel R. Gated graph sequence neural networks. arXiv preprint arXiv:151105493. 2015.
- 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
- F Scarselli, 2009, The graph neural network model, IEEE Transactions on Neural Networks, 20, 61, 10.1109/TNN.2008.2005605 · DOI · Paper page
- Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:13126203. 2013.
- 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.
- 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.
- Kriege NM, Johansson FD, Morris C. A Survey on Graph Kernels. arXiv preprint arXiv:190311835. 2019. · DOI · Paper page
- Xu K, Hu W, Leskovec J, Jegelka S. How powerful are graph neural networks? arXiv preprint arXiv:181000826. 2018.
- 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
- L Oneto, 2017, Measuring the expressivity of graph kernels through statistical learning theory, Neurocomputing, 268, 4, 10.1016/j.neucom.2017.02.088 · DOI
- M Gromov, 2007, Metric structures for Riemannian and non-Riemannian spaces
- M Berger, 2003, A Panoramic View of Riemannian Geometry, 10.1007/978-3-642-18245-7 · DOI · Paper page
- C Villani, 2008, Optimal transport: old and new
- 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
- 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
- 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
- G Peyré, 2019, Computational optimal transport, Foundations and Trends® in Machine Learning, 11, 355, 10.1561/2200000073 · DOI · Paper page
- 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
- Xu H, Luo D, Zha H, Carin L. Gromov-wasserstein learning for graph matching and node embedding. arXiv preprint arXiv:190106003. 2019.
- 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.
- R Bhatia, 2019, Matrix versions of the Hellinger distance, Letters in Mathematical Physics, 1
- R Bhatia, 2019, On the Bures–Wasserstein distance between positive definite matrices, Expositiones Mathematicae, 37, 165, 10.1016/j.exmath.2018.01.002 · DOI
- P Rezaeinia, 2020, Identifying Brain Network Topology Changes in Task Processes and Psychiatric Disorders, Network Neuroscience, 0, 1
- CH Papadimitriou, 2003, Encyclopedia of Computer Science, 260
- N Halko, 2011, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review, 53, 217, 10.1137/090771806 · DOI · Paper page
- JA Bondy, 2008, Graph Theory, 10.1007/978-1-84628-970-5 · DOI · Paper page
- 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
- E Abbe, 2016, Exact recovery in the stochastic block model, IEEE Transactions on Information Theory, 62, 471, 10.1109/TIT.2015.2490670 · DOI
- 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
- R Durrett, 2007, Random graph dynamics
- R Van Der Hofstad, 2016, Random graphs and complex networks, 10.1017/9781316779422 · DOI · Paper page
- 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
- 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
- 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
- M Bayati, 2010, A Sequential Algorithm for Generating Random Graphs, Algorithmica, 58, 860, 10.1007/s00453-009-9340-1 · DOI
- 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
- 2012, Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
- Wolfe PJ, Olhede SC. Nonparametric graphon estimation. arXiv preprint arXiv:13095936. 2013.
- Li Y, Vinyals O, Dyer C, Pascanu R, Battaglia P. Learning deep generative models of graphs. arXiv preprint arXiv:180303324. 2018.
- You J, Ying R, Ren X, Hamilton WL, Leskovec J. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:180208773. 2018.
- Shine A, Kempe D. Generative Graph Models based on Laplacian Spectra? In: The World Wide Web Conference. ACM; 2019. p. 1691–1701. · DOI
- Dehmamy N, Barabási AL, Yu R. Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology. arXiv preprint arXiv:190705008. 2019.
- 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
- 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
- A Fornito, 2016, Fundamentals of Brain Network Analysis
- 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
- G Casella, 2002, Statistical inference
- 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
- Gutfraind A, Safro I, Meyers LA. Multiscale network generation. In: 2015 18th International Conference on Information Fusion (Fusion). IEEE; 2015. p. 158–165.
- U Von Luxburg, 2007, A tutorial on spectral clustering, Statistics and computing, 17, 395, 10.1007/s11222-007-9033-z · DOI · Paper page
- 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
- G Cheung, 2018, Graph spectral image processing, Proceedings of the IEEE, 106, 907, 10.1109/JPROC.2018.2799702 · DOI · Paper page
- C Geniesse, 2019, Generating dynamical neuroimaging spatiotemporal representations (DyNeuSR) using topological data analysis, Network Neuroscience, 3, 763, 10.1162/netn_a_00093 · DOI
- MK Chung, 2019, Exact topological inference of the resting-state brain networks in twins, Network Neuroscience, 0, 1
- 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
- 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
Pham, D., Tan, X., Balderson, B., Xu, J., Grice, L. F., Yoon, S., Willis, E. F., Tran, M., Lam, P. Y., Raghubar, A., et al. (2023) · Nature Communications · doi:10.1038/s41467-023-43120-6 · Cited by 730
Network Statistics of the Whole-Brain Connectome of Drosophila
Lin, A., Yang, R., Dorkenwald, S., Matsliah, A., Sterling, A. R., Schlegel, P., Yu, S.-C., McKellar, C. E., Costa, M., Eichler, K., et al. (2023) · doi:10.1101/2023.07.29.551086 · Cited by 147
Network statistics of the whole-brain connectome of Drosophila
Lin, A., Yang, R., Dorkenwald, S., Matsliah, A., Sterling, A. R., Schlegel, P., Yu, S.-C., McKellar, C. E., Costa, M., Eichler, K., et al. (2024) · Nature · doi:10.1038/s41586-024-07968-y · Cited by 147
“We com-1005 puted the average 3D position of all of the neuron’s incoming synapses to approximate the position of the neuron’s dendritic arbor, and did the same to approximate the position of the neu-1008 ron’s axonal arbor.”
Metadata
- Authors
- Wills, P., & Meyer, F. G.
- Venue
- PLOS ONE
- Publisher
- Public Library of Science (PLoS)
- 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.