Source-linked AI summary
NetLSD: Hearing the Shape of a Graph
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alex Bronstein, Emmanuel Müller
TL;DR
Graph comparison requires invariance to node ordering and graph size, adaptation across structural scales, and efficient computation, yet existing methods do not provide these properties together. NetLSD addresses this gap with a normalized, multi-scale Laplacian heat-trace signature and approximations for large graphs. Experiments report that it outperforms NetSimile and FGSD while processing graphs with millions of nodes.
Problem
Graph comparison lacks a method that jointly provides permutation-invariance, size-invariance, scale-adaptivity, and efficient computation for large graph collections.
Method
NetLSD represents each graph with a normalized multi-scale heat-trace signature derived from the Laplacian spectrum and approximates heat traces for large graphs.
Results
NetLSD outperforms NetSimile and FGSD and computes similarity for one-million-node graphs in 16 minutes, whereas previous methods did not finish within one day.
Takeaways & Limitations
NetLSD enables multi-scale comparisons of large graphs without graph alignment, expensive kernel computations, or supervised representation learning.
Takeaways & Limitations
The initial low-order Taylor and truncated-spectrum approximations miss medium scales and cannot directly compare graphs with different numbers of computed eigenvalues.
Abstract
from arXiv · showhide
Comparison among graphs is ubiquitous in graph analytics. However, it is a hard task in terms of the expressiveness of the employed similarity measure and the efficiency of its computation. Ideally, graph comparison should be invariant to the order of nodes and the sizes of compared graphs, adaptive to the scale of graph patterns, and scalable. Unfortunately, these properties have not been addressed together. Graph comparisons still rely on direct approaches, graph kernels, or representation-based methods, which are all inefficient and impractical for large graph collections. In this paper, we propose the Network Laplacian Spectral Descriptor (NetLSD): the first, to our knowledge, permutation- and size-invariant, scale-adaptive, and efficiently computable graph representation method that allows for straightforward comparisons of large graphs. NetLSD extracts a compact signature that inherits the formal properties of the Laplacian spectrum, specifically its heat or wave kernel; thus, it hears the shape of a graph. Our evaluation on a variety of real-world graphs demonstrates that it outperforms previous works in both expressiveness and efficiency.
1 INTRODUCTION
Graph comparison needs to be permutation-invariant, scale-adaptive, size-invariant, and efficiently computable, but existing approaches do not satisfy these requirements together. NetLSD addresses this gap with compact, multi-scale spectral signatures enabling constant-time similarity computations after preprocessing.
- Graph comparison supports applications involving biological networks, chemical compounds, social interactions, and knowledge bases.
- An ideal comparison measure is invariant to node ordering, adaptive across local and global scales, and invariant to graph size.
- Existing methods fail to satisfy all three comparison requirements while also remaining efficiently computable for large graph collections.
- NetLSD provides permutation- and size-invariant, scale-adaptive graph comparison through compact Laplacian heat- or wave-kernel signatures.
- At small scales, rings and wheels are similar; at large scales they both appear as rings, while intermediate scales distinguish their local structures.
2 RELATED WORK
Prior graph-comparison methods include direct approaches, kernels, and statistical representations, but each has important limitations in scalability, invariance, alignment, or expressiveness. Spectral graph theory provides the foundation for comparing graph structure across scales.
- Graph-comparison methods are commonly categorized as direct methods, graph kernels, and statistical representations.
- Direct Methods: GED is NP-hard and APX-hard, requires node correspondence, and treats all edit operations as equally consequential for topology.
- Direct Methods: Flexible distances reduce sensitivity to local changes but usually require node alignment, limiting them to specific applications.
- Graph Kernels: Graph kernels lack both scale-adaptive and size-invariant comparison while requiring expensive computations at comparison time.
- Graph Kernels: MLG achieves scale-adaptivity through propagation but incurs computational overhead cubic in the number of Laplacian eigenvalues.
- Statistical Representations: Statistical representations are easy to compute but early methods emphasize local properties and overlook global features, while FGSD uses a high-dimensional sparse representation.
- Spectral Foundations: Spectral graph theory motivates graph comparison because some graphs are determined by their spectrum and isospectral graphs tend to be isometric.
3 PROBLEM STATEMENT
The problem statement formalizes graph-comparison distances as pseudometrics that should be permutation-invariant, scale-adaptive, and size-invariant. These properties require preserving structural identity, representing local and global features, and recognizing similar phenomena at different magnitudes.
- Distance requirements: A representation-based graph distance should support clustering, nearest-neighbor classification, and distance-based anomaly detection while satisfying symmetry and triangle inequality.These requirements motivate treating the distance as a pseudometric.
- Expressiveness properties: Permutation-invariance requires isomorphic graphs to have zero representation distance, regardless of node ordering.Isomorphism is defined through a bijection preserving edges between the two graphs.
- Expressiveness properties: Scale-adaptivity requires both local features derived from subgraphs and global features that cannot be derived from any such local subgraph information.Local features capture node- and edge-level structure, whereas global features capture broader properties such as communities.
- Expressiveness properties: Size-invariance requires graphs sampled from the same domain to receive zero distance, even when they represent the phenomenon at different magnitudes.The motivating example is two similarly structured criminal circles with different sizes.
- Expressiveness properties: The stated goal is an expressive representation that satisfies these properties and enables easy graph comparison.NetLSD is introduced as the representation intended to meet this goal.
4 NETLSD: NETWORK LAPLACIAN SPECTRAL DESCRIPTOR
NetLSD transfers graph comparison to the spectral domain, using heat or wave diffusion to create compact signatures across scales. Heat traces support permutation-invariant comparison, tunable local-to-global structure, and efficient approximations for large graphs.
- Spectral representations: NetLSD represents a graph with heat or wave diffusion derived from its Laplacian spectrum.The spectral perspective treats graph nodes as masses and edges as springs, with propagation observed through heat or mechanical waves.
- Heat trace signature: The heat trace summarizes heat-kernel behavior into a graph-level quantity because the heat kernel itself involves pairs of nodes.The resulting signature samples heat traces across multiple time scales, h(G) = {h_t}_t>0.
- Scalable computation: Full Laplacian eigendecomposition costs O(n^3) time and Θ(n^2) memory, motivating Taylor and truncated-spectrum approximations.Taylor terms are useful at small time scales and can compare graphs locally in O(m), while spectral interpolation handles manageable graph sizes and medium scales.
- Scalable computation: The combined approximation strategy uses low-order Taylor expansion for small t and truncated spectral information for larger t, but misses the medium scale.The approximation error of the Taylor expansion stays low until time scale 1 and is independent of graph size in the reported random-graph experiment.
- Representation properties: The heat trace is permutation-invariant because isomorphic graphs are isospectral and therefore have equal heat trace signatures.This property follows directly from the corresponding invariance of the Laplacian spectrum.
- Scale-adaptivity: At small scales, the heat kernel captures local connectivity, while at large scales it reflects global connectivity and central structure.The scale parameter controls kernel localization, allowing the representation to produce both local and global features.
- Graph comparison: Heat trace signatures can be sampled at finite scales to form vector representations whose distances support efficient pruning of dissimilar graphs.The resulting signatures are indexable, allowing the lower-bounding scheme to prune candidates using the index alone.
5 EXPERIMENTAL EVALUATION
The evaluation tests NetLSD’s approximation quality, graph-classification effectiveness, community expressiveness, discovery potential, and scalability across diverse graph collections. NetLSD generally matches or outperforms comparison methods while remaining applicable to graphs with millions of nodes.
- Approximation quality: Using eigenvalues from both spectrum ends achieves almost an order of magnitude higher approximation accuracy than using only one side.The two-sided strategy performs consistently better, although approximation is harder at medium t values.
- Community structure: NetLSD outperforms competitors when detecting community structure across graphs with increasing or randomly varying sizes.For fully size-agnostic comparisons, normalization must be chosen carefully: complete-graph normalization performs best for the wave kernel, while empty-graph normalization performs best for the heat kernel in the uniform-size regime.
- Discovery potential: A furthest-pair query using normalized heat signatures identifies a protein interaction network and an enzyme structure as the least similar graphs among the visualized collections.The comparison excludes REDDIT-L because its graphs are harder to visualize readably.
- Scalability: 16 minutes is sufficient for NetLSD to compute similarity on graphs with 10^6 nodes, whereas previous methods do not finish within one day.The scalability test computes 300 eigenvalues for the heat-trace approximation on graphs of increasing size.
6 CONCLUSIONS
The paper concludes that NetLSD provides a compact, multi-scale spectral representation for graph comparison without alignment, expensive kernels, or supervised representation learning. Its approximation and normalization schemes support efficient, size-invariant comparisons, and experiments show advantages over NetSimile and FGSD across several tasks.
- Conclusion: NetLSD combines multi-scale heat-trace signatures, efficient heat-trace approximation, and normalization for size-invariant graph comparison.The representation is based on the graph Laplacian spectrum and lower-bounds the Gromov-Wasserstein distance.
- Conclusion: NetLSD outperforms NetSimile and FGSD across graph collections on community detection and graph classification.The conclusion reports this outcome as evidence from the paper’s experiments.