CoChat

Metrics for graph comparison: A practitioner’s guide

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

Published version of a preprint

Cited by 196

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.

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

Integrity signals

Registry

Crossref · 10.1371/journal.pone.0228728

Cites

121 of 121 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 121 references

Research works printed but not linked: 15

  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
  2. AJ Schwenk, 1973, Almost all trees are cospectral, New directions in the theory of graphs, 275
  3. 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
  4. 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
  5. 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
  6. 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
  7. F Scarselli, 2009, The graph neural network model, IEEE Transactions on Neural Networks, 20, 61, 10.1109/TNN.2008.2005605 · DOI · Paper page
  8. Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:13126203. 2013.
  9. 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.
  10. 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
  11. CH Papadimitriou, 2003, Encyclopedia of Computer Science, 260
  12. 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
  13. 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
  14. 2012, Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
  15. G Casella, 2002, Statistical inference

Cited by

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
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.