PaperlayerView exact revision on arXiv

Source-linked AI summary

Metrics for Graph Comparison: A Practitioner's Guide

Peter Wills, Francois G. Meyer

arXiv:1904.07414v2stat.APcs.SIphysics.data-anq-bio.NC

TL;DR

Graph comparison lacks a comparative assessment of how common distances distinguish topology across structural scales. The paper evaluates distances on random graph ensembles and empirical networks through a multi-scale framework, finding scale-dependent behavior and recommending combined exploratory and multi-distance analysis.

  • Problem

    No comparative study had established how graph distances discern common topologies and structural scales, despite graph comparison's role in analyzing network structure.

  • Method

    The paper compares distances on samples from distinct random graph ensembles and empirical networks, organizing them by local, mesoscale, and global structure.

  • Results

    Distances differ in the scales they detect: some are tuned to global structure, while others observe multiple scales across numerical and empirical experiments.

  • Takeaways & Limitations

    Practitioners should combine exploratory structural analysis with multiple distance measures and aggregate their information rather than applying adjacency spectral distance naively.

  • Takeaways & Limitations

    The Wasserstein distance remains prohibitively expensive for large graphs, with cost mn^2 + m^2n.

Abstract

from arXiv · show

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 in data in these fields yields 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 (also known as $λ$ 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 and 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 empirical datasets. We put forward a multi-scale picture of graph structure, in which the effect of global and local structure upon the distance measures is considered. We make recommendations on the applicability of different distance measures to empirical graph data problem based on this multi-scale view. Finally, we introduce the Python library NetComp which implements the graph distances used in this work.

Introduction

The paper studies practical pairwise graph comparison across global and local structural scales. It evaluates graph distances on random graph ensembles and empirical networks to guide their use in applications such as two-sample testing and change-point detection.

  • Graph comparison supports tasks including two-sample testing and change-point detection, but useful methods depend on whether users seek global or local structure.Global examples include communities and hubs; local examples include vertex degree and triangle prevalence.
  • Existing surveys rely mainly on observational datasets, making their findings difficult to generalize across network types.
  • The paper compares distances using random graph ensembles as prototypical structural building blocks and studies their sensitivity to ensemble-specific features.The approach compares samples drawn from distinct ensembles rather than restricting evaluation to a small set of deterministic or simple random graphs.
  • Practical scalability restricts attention to methods whose runtime is linear or near-linear in vertices for sparse graphs, because quadratic methods become infeasible on large networks.The paper notes that graph data may contain 10^4 to 10^8 vertices.
  • The analysis organizes graph distances through a multi-scale lens distinguishing local connectivity, mesoscale structure, and large-scale communities.The paper examines how global and local structure affect distance performance in numerical and empirical experiments.

2.1 Notation

This section establishes graph notation, matrix representations, spectral conventions, isomorphism, and the meaning of node correspondence. These definitions provide the vocabulary for describing graph distances and their invariances.

  • A weighted graph is represented as G = (V, E, W), with n vertices, m edges, and positive edge weights assigned by W.
  • The adjacency matrix records edge weights, while the degree matrix is diagonal with vertex degrees on its diagonal.
  • The combinatorial and normalized Laplacian matrices are standard matrix representations used alongside the adjacency matrix.
  • Adjacency eigenvalues are ordered descending, whereas Laplacian and normalized-Laplacian eigenvalues are ordered ascending from zero.The corresponding eigenvector is denoted φ_k.
  • The eigenvalue index k encodes the oscillation frequency of its corresponding eigenvector, with approximately k oscillations and k + 1 nodal domains.
  • Two graphs are isomorphic when a vertex mapping preserves edges, equivalently when their adjacency matrices differ by a permutation similarity.
  • A distance requires node correspondence when isomorphic relabelings can change its distance to a third graph, so meaningful vertex mappings are needed.

2.2 Graph distance measures

The paper surveys graph distance measures selected for near-linear scalability and interprets their sensitivity through global and local graph structure. It emphasizes spectral distances’ scale flexibility while noting metric and computational limitations.

  • Selection criteria: The studied distances are selected for computation in reasonable time on large, sparse graphs, requiring linear or near-linear scaling.The paper distinguishes standard and newer distances while imposing this practical constraint.
  • Caveats: Several studied distances are not mathematical metrics, and spectral distances can assign zero distance to non-isomorphic cospectral graphs.The paper notes that small graphs and trees have documented cospectrality, while its numerical experiments do not encounter it at their graph sizes.
  • Taxonomy: The taxonomy divides the studied distance measures into two non-exhaustive categories, while some methods do not fit either category.The authors note that this taxonomy refines a feature-based group from prior work.
  • Spectral distances: Spectral distances compare eigenvalue sequences from graph matrix representations, including adjacency, Laplacian, and normalized Laplacian forms.The adjacency distance is an ℓ2 distance between spectra; the Laplacian variants are defined analogously, and node correspondence is unnecessary.
  • Spectral distances: Truncated spectral distances compare only k ≪ n eigenvalues, with adjacency distances using the largest k and Laplacian distances using the smallest k.Small-k comparisons can focus on community structure while ignoring local structure.
  • Structural scale: Spectral distances can target local or global structure, whereas the paper’s broader results show that some distances are tuned to global structure and others observe multiple scales.The authors frame this flexibility as a significant advantage of spectral distances.

2.3 Computational Efficiency

The paper emphasizes linear or near-linear algorithms for graph comparison because real graphs can contain millions to billions of vertices. It compares theoretical complexity with small-graph runtimes from NetComp implementations, while noting that implementation quality affects observed efficiency.

  • Scalability: Graphs with millions or billions of vertices make quadratic-time algorithms impractical, motivating linear or near-linear complexity for sparse graphs.The paper defines linear as O(n) and near-linear as O(n log an), with an asymptotically polynomially bounded.
  • Algorithmic complexity: Spectral distances have equivalent complexity because each requires eigendecomposition of a symmetric real matrix.The spectral complexity analysis is based on Krylov subspace methods involving kTmult and (m + n)k^2.
  • Algorithmic complexity: DeltaCon and resistance distance provide exact and approximate algorithms, with approximate versions likely preferable for large graphs.The paper uses exact forms experimentally and in NetComp, while approximate forms have O(m) complexity.
  • Empirical runtimes: Runtime experiments use graphs of n = 100, 300, and 1,000, primarily because larger-distance computations are difficult on a personal computer.The reported runtimes use non-optimized NetComp implementations and sparse data structures when available.
  • Empirical runtimes: The edit distance is the most efficient tested measure, whereas NetSimile is notably slow because much of its computation uses NetworkX.The authors caution that optimized implementations could produce substantially different runtime comparisons.

2.4 Random graph models

The study uses random graph ensembles as controlled examples of global, local, degree-based, and regular structures. These models support comparisons of which graph distances detect particular structural features, while also exposing modeling and analytical limitations.

  • Uncorrelated random graphs: Erdős-Rényi graphs provide a structureless null model, but their uniform topology does not reproduce many properties of empirical networks.Each edge exists independently with probability p, and the model has identical statistical properties across edges and vertices.
  • Small-world structure: The Watts-Strogatz model begins with a ring lattice and introduces shortcuts by randomly rewiring edges.Its generative mechanism is used to model clustering-related structure in networks.
  • Scope and limitations: The study restricts graphs to unlabelled, undirected graphs without self-loops and reports limitations in modeling and spectral analysis.At n = 100, theoretical preferential-attachment results from a slightly different model did not provide a particularly good approximation for the experiments.
  • Community structure: The stochastic blockmodel represents global community structure while remaining locally similar to an uncorrelated random graph.Balanced communities use within-community edge probability p and between-community probability q.
  • Degree structure: Preferential attachment models scale-free degree distributions through degree-proportional attachment, producing high-degree vertices characteristic of some real networks.The model grows from a star and attaches each new vertex to l existing vertices with probability proportional to their degree.
  • Degree-matched null models: Configuration models preserve a prescribed degree sequence and can serve as degree-matched null models for comparisons.They can share features such as preferential attachment’s power-law degree distribution while controlling for degree sequence.

2.5 Real world networks

The empirical evaluation covers dynamic social-contact and email networks plus functional brain-connectivity networks. These datasets provide real examples of changing community structure, temporal interactions, and population-level connectivity differences.

  • Dynamic networks: The empirical study evaluates change-point detection on a primary-school contact network and an 803-day email time series.The email network contains 986 members of a large European research institution.
  • Brain connectivity: The neuroscience experiment compares functional connectivity networks from subjects with autism spectrum disorder against controls.The two-sample test evaluates whether the ASD and control populations could share the same generating distribution.
  • Primary-school contacts: The school contact data contain 232 students represented across N = 150 intervals of approximately 200 seconds.An edge records face-to-face contact during the corresponding interval.
  • Primary-school contacts: School classes act as weakly connected communities, while lunch and recess increase inter-community links and disrupt that structure.The cited snapshots identify these changes at specific times during the school day.
  • Brain connectivity: Brain connectomes are constructed from fMRI-derived regional time series using thresholded absolute Pearson correlations.Both weighted and unweighted graphs are generated across multiple thresholds to reduce dependence on one parameter choice.

2.6 Evaluation protocol: the distance contrast

The evaluation contrasts within-population distance variability with between-population distances, then applies analogous normalization to temporal graph changes. This protocol tests whether distances separate graph populations or detect meaningful transitions.

  • Population comparison: The protocol compares a null population’s within-distribution distances D0 with between-population distances D1 for each measure.D0 captures natural variability, while D1 measures separation between null and alternative populations.
  • Population comparison: A distance is effective when the D0 and D1 distributions are well separated.The paper interprets separation as evidence that the measure differentiates the null population from the alternative.
  • Normalized contrast: The normalized contrast uses the sample means and standard deviations of D0 and D1 to compare between-population separation against within-population variability.The statistic is studentized and related to the Wald test statistic.
  • Random-graph comparisons: Random-graph experiments compare each model with an Erdős-Rényi or degree-matched configuration-model null and record the structural feature under evaluation.Spectral distances are also evaluated for different numbers k of principal eigenvalues when appropriate.
  • Temporal comparison: Temporal experiments normalize adjacent-graph distance changes by the sample mean temporal distance.This produces a normalized temporal difference for dynamic networks.
  • Brain-connectivity comparison: For functional brain connectivity, G1 contains ASD connectomes and G0 contains control connectomes, evaluated with the same distance-contrast statistic.The protocol therefore treats the clinical comparison as a null-versus-alternative population test.

Results

Across synthetic and empirical experiments, graph-distance performance depends on the structural scale and topology being compared. Distances variously emphasize global communities, fine-scale connectivity, temporal community changes, or are overwhelmed by local variability.

  • Experimental setup: 50 connected graph pairs of size n = 1,000 were generated per experiment, using exact algorithms and matched expected graph volume.The experiments condition random-graph samples on connectivity; larger graphs would make the slower exact algorithms prohibitively expensive.
  • Stochastic blockmodel: For stochastic blockmodels, DeltaCon separated models most reliably, while edit, resistance perturbation, and non-normalized Laplacian distances failed.Adjacency and normalized Laplacian distances also performed well when graph volumes were matched.
  • Stochastic blockmodel: The stochastic-blockmodel adjacency distance was driven mainly by the second eigenvalue λA_2, whereas adding normalized-Laplacian eigenvalues reduced performance.The normalized Laplacian obtained most of its benefit from λL_2; further eigenvalues added no benefit for adjacency.
  • Preferential attachment vs uncorrelated: For preferential attachment versus an uncorrelated random graph, combinatorial Laplacian distance performed best, while normalized Laplacian failed to separate the models.Fine-scale, large-index combinatorial-Laplacian eigenvalues were needed, whereas the smallest adjacency eigenvalue captured much of the contrast.
  • Preferential attachment vs configuration: No distance differentiated preferential attachment from a randomized graph with the same degree distribution, suggesting significant structure was prescribed by degree distribution.The combinatorial-Laplacian spectral distance, strongest against the uncorrelated model, was unavailing here.
  • Watts-Strogatz: In the Watts-Strogatz comparison, adjacency and normalized-Laplacian spectral distances were strongest, while DeltaCon outperformed resistance distance.Unlike the earlier preferential-attachment comparison, normalized Laplacian outperformed combinatorial Laplacian; resistance distance was affected by disconnected null-model components.
  • Lattice and configuration: Lattice-versus-configuration discrimination required all eigenvalue scales, highlighting the importance of local topology; resistance distance had the highest performance in this regular-graph case.Spectral distances performed equally well, and scaled distances were about an order of magnitude higher for some measures.
  • Empirical networks: Matrix distances detected school-day transitions into and out of a strong ten-community structure, whereas NetSimile and all-eigenvalue spectral distances were more affected by fine-scale fluctuations.NetSimile responded significantly to random edge fluctuations, while spectral temporal differences became noisy because high-frequency eigenvalues were influenced by stochastic connectivity.

Discussion

The discussion frames graph comparison as multi-scale: different distances respond to global, mesoscale, and local structure, while their usefulness depends on the task and noise. Spectral distances work well for several random-graph comparisons, but dynamic change detection favors resistance-based analysis under some conditions.

  • Mesoscale structure: Preferential attachment’s multi-scale connectivity suggests mesoscale-adapted distances should detect it effectively.Its power-law degree distribution spans fine through coarse scales; the Watts-Strogatz model is likewise expected to require mesoscale connectivity analysis.
  • Global structure: The second eigenvalue λ2 is the primary spectral feature separating the two-partition stochastic blockmodel.The bulk spectra overlap substantially, so adding eigenvalues can introduce noise and reduce contrast.
  • Global structure: Adjacency spectral distance and DeltaCon perform well for global structure, while community detection need not use the full spectrum.The discussion specifically identifies λ2 as sufficient for the two-community stochastic blockmodel.
  • Fine-scale structure: Combinatorial Laplacian spectral distance is effective for polynomially decaying degree distributions because its degree matrix captures high-degree vertices.The Laplacian spectrum’s tail can exhibit polynomial decay resembling the degree-distribution tail.
  • Fine-scale structure: Adjacency spectral distance detects Watts-Strogatz graphs through triangle-related high-frequency structure, requiring much of the spectrum.The model’s local degree structure resembles the uncorrelated random graph, so lower-scale information alone is insufficient.
  • Impact of local structure: Locally targeted distances can amplify uninformative fluctuations, whereas ignoring local structure can discard essential graph signatures.Resistance distance is disproportionately affected by local fluctuations in the stochastic blockmodel, while DeltaCon is less affected.
  • Empirical networks: In functional brain networks, real-world noise causes many distances to miss subtle structural differences.The study therefore examines more targeted analysis techniques for noisy empirical data.
  • Dynamic networks: Spectral distances perform poorly for dynamic change-point detection, while resistance distance detects subtle topology changes and ignores random local changes.This contrasts with their efficiency and stability when comparing random graphs sampled from distinct probability models.

Conclusion

The paper develops a multiscale framework for evaluating graph distances using random graph ensembles and real-world networks. It finds adjacency spectral distance broadly useful, but recommends choosing methods according to graph structure, dynamics, and volume changes rather than applying one distance naively.

  • Contribution: The study addresses the lack of an equivalent basis for rigorously analyzing graph ensembles by evaluating graph distances on prototypical random-graph structures.The ensembles represent structural building blocks of real-world networks.
  • Multiscale framework: Distances are organized through a multiscale lens spanning local connectivity, mesoscale structure, and large-scale communities.The study relates ensemble families and characteristic structures to distance sensitivity.
  • Empirical evaluation: Experiments cover two-sample testing on functional brain-connectivity networks and change-point detection in a dynamic face-to-face contact network.These experiments extend the analysis from random graph ensembles to empirical networks.
  • Recommendations: Adjacency spectral distance performs well across varied scenarios and can compare graphs of different sizes without known vertex correspondence.Spectral distances also offer practical advantages over matrix distances.
  • Recommendations: Adjacency spectral distance is not general enough for naive use in every two-sample or anomaly-detection problem.The authors recommend exploratory structural analysis and combining multiple distances into a consensus.
  • Scope boundary: Graph-volume variation changes distance selection: matrix distances are most effective for detecting latent changes in dynamic networks.The random-graph analysis primarily compared graphs with equal expected volume.

Notation

The notation section points readers to a consolidated table of symbols used throughout the paper.

  • Notation: Table 7 provides the notation used throughout the paper.

NetComp: network comparison in python

NetComp is a Python library for applying the graph distances studied in this work, including methods absent from NetworkX.

  • NetComp: NetComp implements the graph distances studied in the paper for practical network comparison.It complements NetworkX by providing advanced spectral-comparison and DeltaCon algorithms.

H.1 Design consideration

NetComp is designed for fast, flexible, and extensible graph comparison. Its current alpha release implements exact but quadratic-time forms for DeltaCon and resistance distance, while approximate forms are not yet included.

  • Speed: NetComp implements graph-comparison algorithms that run in linear or near-linear time for large graph data problems.
  • Flexibility: The library uses adjacency matrices in dense NumPy or sparse SciPy formats, enabling graph data from varied sources.
  • Extensibility: NetComp is written for extension, with the included distances intended as the beginning of a broader library of efficient graph-comparison tools.
  • NetComp is distributed through the Python Package Index and can be installed locally using pip.
  • The alpha release omits approximate DeltaCon and resistance distance, providing only their quadratic-time exact forms.
Loading 1904.07414v2…