Metrics for graph comparison: A practitioner’s guide
Open accessPublished version of a preprint
The DOI matches its Crossref record; 121 of the 121 references it cites were found in a registry or an index.
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
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
Semi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853
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 · cited 2×
“Comparison of graph structure is a ubiquitous task in data analysis and machine learning, with diverse applications in fields such as neuroscience [1], cyber security [2], social network analysis [3], and bioinformatics [4], among others.”
BackgroundA tutorial on spectral clustering
von Luxburg, U. (2007) · Statistics and Computing · doi:10.1007/s11222-007-9033-z · Cited by 10,349
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 · cited 1×
“, [54–57] and references therein).”
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
Graph 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. (2018) · arXiv · doi:10.48550/arxiv.1812.08434 · Cited by 6,880
Research works printed but not linked: 15
- 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 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
- 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
- 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
- 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.
- 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
- CH Papadimitriou, 2003, Encyclopedia of Computer Science, 260
- 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
- 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
- 2012, Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
- G Casella, 2002, Statistical inference
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. (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.”
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
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
- 121
- 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
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.