Metrics for Graph Comparison: A Practitioner's Guide

Introduction

• The analysis focuses on pairwise graph comparisons relevant to two-sample testing and change-point detection, where users may seek either large-scale organization or local connectivity.Examples include communities and hubs at larger scales, and vertex degree or triangle prevalence locally.Source: Introduction · pp. 1–2
• The study compares samples from distinct random-graph ensembles to test how distances detect their characteristic structures, addressing the limits of generalizing surveys based on observational datasets.The authors use numerical sampling because rigorous probabilistic analysis of many generative graph models is difficult.Source: Introduction · p. 2
• To suit large sparse graphs, the study limits attention to distance methods whose calculation time scales linearly or near-linearly with vertex count.The paper notes that quadratic-time algorithms quickly become infeasible for graph datasets with 10^4 to 10^8 vertices.Source: Introduction · p. 2
• Distances differ in their sensitivity to graph structure: some emphasize global features, while others capture multiple scales, as shown in numerical and empirical experiments.The global features include communities and hubs; local features include median degree and triangle density.Source: Introduction · p. 2

2.1 Notation

• A graph G = (V, E, W) has vertex set V = {1, . . . , n}, edge set E, positive edge weights, size n = |V|, and m = |E| edges.The notation also uses i ∼ j when (i, j) ∈ E.Source: §2.1 · p. 3
• The adjacency matrix stores edge weights and uses 0 for nonedges; the degree matrix is diagonal, and the normalized Laplacian is D−1/2LD−1/2.A, L, and the normalized Laplacian are common matrix representations of a graph; a broader catalog is cited as.Source: §2.1 · p. 3
• The spectrum is the sorted eigenvalue sequence; adjacency eigenvalues are ordered descending, while Laplacian and normalized-Laplacian eigenvalues are ordered ascending from 0.The kth eigenvalue is denoted λA_k, λL_k, or λL_k for the respective matrices.Source: §2.1 · p. 3
• The index k encodes eigenvector frequency: the eigenvector associated with λk has about k oscillations on the graph and k + 1 nodal domains.The corresponding eigenvector is denoted φk.Source: §2.1 · p. 3
• Graphs are isomorphic when a vertex-set map makes their edge sets equal, equivalently when their adjacency matrices are related by a permutation matrix; a distance requires node correspondence if isomorphic inputs can yield different distances to the same graph.Node correspondence means knowing a meaningful mapping between the vertex sets being compared.Source: §2.1 · pp. 3–4

2.2.1 Spectral distances

• Truncated spectral distances can target structural scale: small-k leading eigenvalues emphasize communities, while including higher-index eigenvalues captures local as well as global features.Spectral distances do not require node correspondence, and normalized Laplacian spectral distance can compare graphs of different sizes.Source: §2.2.1 · p. 5
• Spectral distances can assign zero distance to non-isomorphic cospectral graphs, and a small distance may still conceal important topological differences.The authors report that cospectrality is not encountered in their numerical experiments, but identify small-distance topological mismatches as a more troubling failure mode.Source: §2.2.1 · p. 5

2.2.2 Matrix distances

• Matrix distances compare pairwise-affinity matrices and require node correspondence; edit distance targets edge changes, resistance distance connectivity changes, and DeltaeCon weights influence across path lengths.Shortest-path distance uses a single path, whereas effective resistance incorporates all paths and thus reflects communication robustness.Source: §2.2.2 · pp. 6–8

2.2.3 Feature-based distances

• Feature-based distances compare graph properties such as degree distributions or triangle counts; NetSimile summarizes local and egonet features, though some features are not scalable to large graphs.NetSimile aggregates feature values using the mean, median, standard deviation, skewness, and kurtosis; scalable variants need features computable in linear or near-linear time.Source: §2.2.3 · pp. 8–9

2.2.4 Learning Graph Kernels

• Learned graph embeddings map networks into Euclidean space and can tailor similarity to applications, but graph kernels may be non-injective and fail the triangle inequality.The section also describes graph neural network expressivity in relation to the Weisfeiler-Lehman graph isomorphism test.Source: §2.2.4 · p. 9

2.2.5 Comparing Graphs of Different Sizes

• For different-sized graphs, metric-space distances include Gromov-Hausdorff and Wasserstein/Kantorovich-Rubinstein, but the optimal-alignment search makes Gromov-Hausdorff impractical.Wasserstein distance treats comparison as the cost of transporting a measure between metric spaces.Source: §2.2.5 · pp. 9–10
• Wasserstein estimation costs mn2 + m2n, but Gaussian measures yield a Bures distance between covariance matrices, reducing to Hellinger distance when they are diagonal,.The cost is expressed in terms of m edges and n nodes.Source: §2.2.5 · p. 10
• Connections among metric spaces, optimal transport, and metrics on positive semidefinite matrices are beyond this study’s scope and remain avenues for future work.Source: §2.2.5 · p. 10
• Distributions of structural features can define a probability measure for a graph, as in using hitting-time distributions to characterize functional brain connectivity.The study examines how graph-ensemble features relate to distance sensitivity.Source: §2.2.5 · p. 10

2.3.1 Algorithmic Complexity

• Near-linear complexity is needed for graphs with millions or billions of vertices; the authors define linear as O(n), near-linear as O(n log^a n), and assume sparse graphs have m linear in n up to a logarithmic factor.Here a is asymptotically bounded by a polynomial.Source: §2.3.1 · p. 10
• Spectral distances share eigendecomposition complexity, while DeltaCon and resistance distance have exact and approximate algorithms; randomized spectral methods could improve efficiency on large matrices.The experiments use exact DeltaCon and resistance distance implementations.Source: §2.3.1 · pp. 10–11

2.3.2 Comparison of Runtimes on Graphs on Small Graphs

• Runtime comparisons use NetComp implementations that are not highly optimized, with spectral calculations relying on standard SciPy solvers and sparse data structures when available.The reported means and standard deviations are calculated for graphs of sizes n = 100, 300, and 1,000.Source: §2.3.2 · p. 11
• The edit distance is by far the most efficient, while NetSimile is notably slow because its metric calculations rely heavily on NetworkX, which is not designed for maximal efficiency or scalability.The reported comparison uses NetComp implementations.Source: §2.3.2 · p. 12, Table 2 · p. 12
• A thorough equitable comparison of optimized implementations is beyond the scope of this work, since each distance would need careful use-case-specific optimization.The authors note that more efficient implementations are possible for each distance.Source: §2.3.2 · p. 12

2.4.1 The Uncorrelated random graph

• The uncorrelated Erdős-Rényi model assigns each edge an independent probability p, serving as a structureless null model that fails to reproduce many empirical network properties.It is used as a null model in many experiments.Source: §2.4 · p. 12, §2.4.1 · p. 13

2.4.2 The Stochastic blockmodel

• The stochastic blockmodel’s balanced communities create global partition structure but little local structure, making it useful for testing whether distances detect community structure.Edges occur independently with probability p within a community and q between communities.Source: §2.4.2 · p. 13

2.4.3 Preferential attachment models

• Preferential attachment produces scale-free degree distributions and hubs that shorten paths globally while creating tree-like local structure.Each new vertex attaches to l existing vertices with probability proportional to their degrees; the model is less analytically understood than the uncorrelated random graph or stochastic blockmodel.Source: §2.4.3 · p. 14

2.4.4 The Watts-Strogatz model

• The Watts-Strogatz model [16] uses rewiring of a ring lattice to produce high local clustering and short paths, with primarily local structure and no communities or high-degree vertices at large scales.The model must remain connected, restarting the procedure if rewiring disconnects it; neither it nor preferential attachment reproduces all observed network properties.Source: §2.4.4 · p. 15

2.4.5 The Configuration model

• The configuration model prescribes a degree sequence and serves as a null model that controls for degree while retaining structure such as preferential attachment’s power-law distribution.Because the basic model can generate self-edges or multiple edges, the study uses Bayati et al.’s approximately uniform sampler of simple graphs despite its lack of finite-size uniformity guarantees.Source: §2.4.5 · p. 15

2.4.6 Lattice graphs

• A two-dimensional lattice provides a highly regular, low-noise example whose discrete spectrum supports probing graph distances on strongly structured graphs.Its planar structure makes the eigenvalues interpretable as approximations to surface vibrational frequencies.Source: §2.4.6 · p. 16

2.4.7 Exponential random graph models

• Although ERGMs are flexible and interpretable, the authors exclude them because attempts to tune graph properties individually were unsatisfactory.Increasing triangles also increased graph volume, while counteracting volume produced samples resembling an uncorrelated random graph.Source: §2.4.7 · pp. 16–17

2.4.8 Graph Neural Networks

• Learned graph-generating neural networks offer implicit representations of graph sets, but their structural properties remain poorly understood and distance-sensitivity experiments are beyond this paper’s scope.The authors describe such experiments as a needed complement to theoretical work on graph-model expressivity.Source: §2.4.8 · p. 17

2.5.3 Functional brain connectivity

• The brain-connectivity comparison tests whether ASD and control populations share the same distribution of functional networks.The data come from fMRI measurements aggregated into 116 AAL-region time series; 871 of 1,114 subjects passed quality assurance.Source: §2.5 · p. 17, §2.5.3 · p. 19

2.5.1 Primary school face to face contact

• The school contact network tracks 232 students in 10 classes across 150 intervals of approximately 200 seconds, with edges marking RFID-recorded contact.Classes are treated as communities; lunchtime and recess increase links between communities and disrupt their structure.Source: §2.5.1 · pp. 18–19

2.5.2 European Union Emails

• The email time series comprises weekly graphs of 986 people, linking a pair only when each person emailed the other at least once that week.Graph distances were computed between weekly graphs; the timeline begins October 1, 2003.Source: §2.5.2 · p. 19

2.5.3 Functional brain connectivity

• Brain graphs use thresholded absolute Pearson correlations between regional time series, with both weighted and unweighted connectomes tested across multiple thresholds.Low correlations are excluded as potentially spurious; testing multiple thresholds checks that results are not artifacts of parameter choice.Source: §2.5.3 · pp. 19–20

2.6.1 The Distance contrast

• The distance contrast normalizes between-population distances by null-population variability; a contrast distribution well separated from zero indicates effective separation.D0 captures natural variation within the null population, while D1 measures distances between null and alternative graphs.Source: §2.6.1 · p. 20

2.6.2 Comparisons of the random graph ensembles

• Random-ensemble experiments compare each model with an Erdős-Rényi or degree-matched configuration null, using the distance contrast and, where appropriate, spectral distances across k.Table 4 lists the comparisons and the structural feature evaluated in each experiment.Source: §2.6.2 · p. 20, Table 4 · p. 21

2.6.3 Comparisons of the real world networks

• For real-world networks, the protocol quantifies temporal topology changes with normalized distance differences and evaluates ASD connectomes against control connectomes using the distance contrast.The temporal differences are normalized by their sample mean.Source: §2.6.3 · p. 21

3.1.1 Stochastic blockmodel

• Against an uncorrelated random graph, DeltaCon separates the stochastic blockmodel most reliably, while adjacency and normalized Laplacian perform well; edit, resistance, and combinatorial Laplacian fail.Adjacency’s performance is driven mainly by its second eigenvalue, with no benefit from more; normalized Laplacian gains most from its second eigenvalue, but adding eigenvalues reduces performance.Source: Figure 3 · p. 22, §3.1.1 · p. 22, Figure 4 · p. 23

3.1.2 Preferential attachment vs uncorrelated

• For preferential attachment versus an uncorrelated random graph, combinatorial Laplacian distance outperforms all others; adjacency’s first eigenvalue captures much of the contrast, while fine-scale Laplacian eigenvalues are needed.The edit distance fails when edge counts match; resistance is mediocre, and DeltaCon has high variability despite the highest median among matrix distances. The normalized Laplacian does not separate the models.Source: §3.1.2 · p. 24, Figure 6 · p. 24

3.1.3 Preferential attachment vs configuration model

• For preferential attachment versus a degree-matched configuration model, no distance differentiates the graphs, suggesting significant structural features are prescribed by the degree distribution.The combinatorial Laplacian, which gave the strongest contrast against an uncorrelated random graph, is unavailing against this degree-matched null.Source: §3.1.3 · pp. 24–25, Figure 7 · p. 25

3.1.4 Watts-Strogatz

• In Watts–Strogatz versus degree-matched configuration graphs, adjacency and normalized Laplacian are strongest; DeltaCon outperforms resistance, and normalized Laplacian surpasses combinatorial Laplacian.The resistance distance’s negative median likely reflects disconnected components in the null model inflating renormalized resistance distances; optimal spectral contrast requires coarse and fine scales.Source: §3.1.4 · pp. 25–26, Figure 8 · p. 26, Figure 9 · p. 26

3.1.5 Lattice graph

• For lattice versus degree-matched configuration graphs, resistance performs best and spectral distances perform equally well, with spectral discrimination requiring all eigenvalue scales.The lattice’s extreme regularity makes many distances effective; the importance of all spectral scales points to local structure.Source: Figure 10 · p. 27, §3.1.5 · p. 27, Figure 11 · p. 28

3.2.1 Primary school face to face contact,

• In school contact networks, resistance, edit, and DeltaCon detect schedule-related transitions into and out of a strong ten-community structure; NetSimile is affected by random fine-scale edge fluctuations.Spectral distances using all eigenvalues are noisy because stochastic connectivity changes affect high-frequency eigenvalues, obscuring significant topology changes.Source: §3.2.1 · p. 28, Figure 12 · p. 29, Figure 13 · p. 29

3.2.2 European Union Emails

• In EU email networks, spectral distances correlate with parliamentary activity, while matrix distances detect Barroso’s election and the 2004–2009 Commission hearings and entry into office.Detected events include hearings in October 2004 and the Commission’s entry into office at the end of November 2004.Source: §3.2.2 · p. 30, Figure 17 · p. 32, Figure 18 · p. 32

3.2.3 Functional brain connectivity

• No distance effectively separates ASD and control connectome ensembles; greater variability within controls and localized differences make global graph comparisons ineffective.The negative median contrast indicates that average between-population distances are lower than within-control distances; refined analysis attributes this to localized changes comparable in magnitude to random local variation.Source: §3.2.3 · p. 35

Discussion

• The discussion frames comparison across local, mesoscale, and community scales, with stochastic local changes potentially contrasting with large-scale connectivity changes.It argues that preferential attachment and small-world graphs require mesoscale analysis because their connectivity spans multiple scales.Source: Discussion · p. 35

4.1.1 Detecting large scale changes

• For global structure, adjacency spectral distance and DeltaCon perform well; for two-community blockmodels, λ2 separates the models, while adding bulk eigenvalues reduces contrast.The empirical spectral densities are separated around the second-largest adjacency eigenvalue, while the bulk spectra overlap.Source: §4.1.1 · pp. 36–37, Figure 24 · p. 37

4.1.2 Detecting mesoscale changes

• For preferential-attachment graphs with polynomial degree decay, combinatorial Laplacian spectral distance is most effective, and its final eigenvalues capture high-degree tail differences.The degree matrix in L = D − A makes Laplacian comparisons sensitive to degree distributions; the spectrum’s tail also exhibits polynomial decay similar to the degree tail.Source: §4.1.2 · pp. 37–38
• Adjacency spectral distance best detects short-average-distance Watts–Strogatz graphs; high-frequency modes capture their spectral skew, though they can dilute contrast when degree distributions match random graphs.The third spectral-density moment reflects triangle counts, and experiments found large-k eigenvalues essential for distinguishing these models, while fine-scale degree similarity can make high modes uninformative.Source: §4.1.2 · pp. 38–39, Figure 26 · p. 39

4.1.3 Impact of local structure

• In preferential attachment, high-frequency Laplacian eigenvalues expose degree-distribution signatures; a degree-matched null model makes the graphs indistinguishable.The degree distribution acts as a fine-scale signature of connectivity.Source: §4.1.3 · p. 39
• For lattice graphs, increasing the number of eigenvalues improves all spectral distances because cycles of every size, starting at length four, characterize local connectivity.Source: §4.1.3 · p. 39
• For stochastic blockmodels, the Laplacian spectrum fails to distinguish the model from an uncorrelated random graph, but the normalized Laplacian succeeds by removing uninformative degree information.Source: §4.1.3 · pp. 39–40
• Local structure can be noise or signal: resistance distance can miss global block structure amid local fluctuations, DeltaCon is less affected, and ignoring local features can also omit essential information.Whether to use locally targeted distances depends on whether local topological features matter for the comparison.Source: §4.1.3 · p. 40

4.2 Real world networks

• With real-world brain-network noise, many distances miss subtle population differences; spectral distances perform consistently in two-sample tests but prove unreliable for change-point detection with volume fluctuations.The paper examines targeted analysis techniques for noisy real-world data.Source: §4.2 · p. 40

4.2.1 Primary school face to face contact

• In the school contact network, resistance-perturbation detects inter-community topology changes while suppressing within-class random fluctuations, whereas edit distance tracks volume but misses key events.Because classrooms are densely connected and weakly connected to each other, the same edge change has a larger resistance-perturbation effect across classrooms than within one classroom.Source: §4.2.1 · pp. 41–42

4.2.2 European Union Emails

• In institute email graphs, spectral distances rise at Parliament session changes and all distances at the Commission transition, while resistance and DeltaCon alone detect Barroso’s election.The results support resistance-perturbation as a sensitive statistic for detecting changes in dynamic networks.Source: §4.2.2 · p. 43

4.2.3 Functional brain connectivity

• ASD-control structural connectome differences are smaller than one standard deviation of control correlations, and their low-amplitude, sparse pattern contributes to graph distances’ inability to detect significant changes between the populations.ASD subjects are underconnected in regions 73 through 77 and overconnected in regions 79 and 84 through 89.Source: §4.2.3 · pp. 44–45

Conclusion

• The study uses random graph ensembles as prototypical structures to evaluate graph distances for two-sample testing, relating ensemble features to distance sensitivity across local, mesoscale, and community scales.The local scale is represented by ego-nets; the mesoscale bridges local and global structure.Source: Conclusion · p. 45
• Real-world experiments examined two-sample testing on functional brain-connectivity networks and change-point detection in a dynamic face-to-face contact network.Source: Conclusion · p. 45

5.1 Recommendations

• The adjacency spectral distance performed well across varied scenarios and can compare graphs of different sizes without known vertex correspondence; its spectrum is well studied.Fast, stable eigensolvers also support rapid deployment.Source: §5.1 · p. 45
• Because adjacency spectral distance is not suitable for every two-sample or anomaly-detection problem, practitioners should explore graph structure and combine multiple distances into a consensus.The paper compares this approach to voting classifiers.Source: §5.1 · p. 45
• For consecutive-time-step change-point detection, matrix distances—especially resistance perturbation distance or DeltaCon—performed best; spectral distances were unusably noisy and raw volume fluctuations uninformative.The paper notes this differs from two-sample testing because consecutive graphs share many more edges.Source: §5.1 · p. 46
• For population-membership comparisons, the adjacency spectral distance was the most reliable; the decision process first screens volume or size, then selects a method suited to the setting.If these approaches are inadequate, the paper recommends domain-specific analysis, such as edge-wise statistical comparison of weights.Source: §5.1 · p. 46

• Table 7 provides notation used throughout the paper.Source: Notation · p. 46

NetComp: network comparison in python

• NetComp bridges gaps in NetworkX by implementing advanced spectral comparisons and DeltaCon.NetworkX offers tools for network construction and analysis, but does not include these advanced algorithms.Source: NetComp: network comparison in python · p. 46

• The library implements linear- or near-linear-time algorithms intended for large graph data problems.Source: §H.1 · p. 46
• NetComp uses adjacency matrices in dense NumPy or sparse SciPy formats, allowing input from a wide variety of sources.Source: §H.1 · p. 46
• NetComp is written to be extended, with its included graph distances intended as a starting point for a broader library of efficient graph-comparison tools.Source: §H.1 · p. 48
• NetComp is available through the Python Package Index, commonly accessed with pip.Source: §H.1 · p. 48
• As of writing, NetComp was in alpha: exact quadratic-time DeltaCon and resistance-distance forms were implemented, but their approximate near-linear forms were not included.Source: §H.1 · p. 48