# Multiscale Graph Comparison via the Embedded Laplacian Discrepancy

arXiv: https://arxiv.org/abs/2201.12064 · HTML: https://mlsanity.com/paper/2201.12064/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 73 references that are in the map.
- First posted on arXiv 28 Jan 2022.

## Builds on (most cited first, 20 of 20)

- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Wasserstein Embedding for Graph Learning](https://mlsanity.com/paper/2006.09430/) (2020)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Vertex-Frequency Analysis on Graphs](https://mlsanity.com/paper/1307.5708/) (2013)
- [DELTACON: A Principled Massive-Graph Similarity Function](https://mlsanity.com/paper/1304.4657/) (2013)
- [Modeling Network Populations via Graph Distances](https://mlsanity.com/paper/1904.07367/) (2019)
- [Nonparametric Bayes Modeling of Populations of Networks](https://mlsanity.com/paper/1406.7851/) (2014)
- [An information-theoretic, all-scales approach to comparing networks](https://mlsanity.com/paper/1804.03665/) (2018)
- [Graph Matching via Optimal Transport](https://mlsanity.com/paper/2111.05366/) (2021)
- [A Community-Developed Open-Source Computational Ecosystem for Big Neuro Data](https://mlsanity.com/paper/1804.02835/) (2018)
- [Efficient estimation of the modified Gromov-Hausdorff distance between unweighted graphs](https://mlsanity.com/paper/1909.09772/) (2019)

## Built on by (most cited first, 5 of 5)

- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding](https://mlsanity.com/paper/2310.18716/) (2023)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Scalable Sobolev IPM for Probability Measures on a Graph](https://mlsanity.com/paper/2502.00737/) (2025)
- [A Spectral Framework for Evaluating Geodesic Distances Between Graphs](https://mlsanity.com/paper/2406.10500/) (2024)

## Abstract (arXiv)

Laplacian eigenvectors capture natural community structures on graphs and are widely used in spectral clustering and manifold learning. The use of Laplacian eigenvectors as embeddings for the purpose of multiscale graph comparison has however been limited. Here we propose the Embedded Laplacian Discrepancy (ELD) as a simple and fast approach to compare graphs (of potentially different sizes) based on the similarity of the graphs' community structures. The ELD operates by representing graphs as point clouds in a common, low-dimensional space, on which a natural Wasserstein-based distance can be efficiently computed. A main challenge in comparing graphs through any eigenvector-based approaches is the potential ambiguity that could arise due to sign-flips and basis symmetries. The ELD leverages a simple symmetrization trick to bypass any sign ambiguities. For comparing graphs that do not have any ambiguities due to basis symmetries (i.e. the spectrums are simple), we show that the ELD becomes a natural pseudo-metric that enjoys nice properties such as invariance under graph isomorphism. For comparing graphs with non-simple spectrums, we propose a procedure to approximate the ELD via a simple perturbation technique to resolve any ambiguity from basis symmetries. We show that such perturbations are stable using matrix perturbation theory under mild assumptions that are straightforward to verify in practice. We demonstrate the excellent applicability of the ELD approach on both simulated and real datasets.