# NetLSD: Hearing the Shape of a Graph

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2018.

## Built on by (most cited first, 30 of 52)

- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Simplicial Complex Representation Learning](https://mlsanity.com/paper/2103.04046/) (2021)
- [DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data](https://mlsanity.com/paper/2107.02168/) (2021)
- [AutoGL: A Library for Automated Graph Learning](https://mlsanity.com/paper/2104.04987/) (2021)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [A Survey of Graph Unlearning](https://mlsanity.com/paper/2310.02164/) (2023)
- [Identity Inference on Blockchain using Graph Neural Network](https://mlsanity.com/paper/2104.06559/) (2021)
- [Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization](https://mlsanity.com/paper/2109.07016/) (2021)
- [Motif Graph Neural Network](https://mlsanity.com/paper/2112.14900/) (2021)
- [Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding](https://mlsanity.com/paper/2102.13582/) (2021)
- [Automated Graph Machine Learning: Approaches, Libraries, Benchmarks and Directions](https://mlsanity.com/paper/2201.01288/) (2022)
- [Feature Learning for Nonlinear Dimensionality Reduction toward Maximal Extraction of Hidden Patterns](https://mlsanity.com/paper/2206.13891/) (2022)
- [FGOT: Graph Distances based on Filters and Optimal Transport](https://mlsanity.com/paper/2109.04442/) (2021)
- [MOOMIN: Deep Molecular Omics Network for Anti-Cancer Drug Combination Therapy](https://mlsanity.com/paper/2110.15087/) (2021)
- [Challenges of Generating Structurally Diverse Graphs](https://mlsanity.com/paper/2409.18859/) (2024)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Log-Euclidean Signatures for Intrinsic Distances Between Unaligned Datasets](https://mlsanity.com/paper/2202.01671/) (2022)
- [Survey of Malware Analysis through Control Flow Graph using Machine Learning](https://mlsanity.com/paper/2305.08993/) (2023)
- [JITuNE: Just-In-Time Hyperparameter Tuning for Network Embedding Algorithms](https://mlsanity.com/paper/2101.06427/) (2021)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Fast Attributed Graph Embedding via Density of States](https://mlsanity.com/paper/2110.05228/) (2021)
- [A Comprehensive Survey on Graph Summarization with Graph Neural Networks](https://mlsanity.com/paper/2302.06114/) (2023)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [Visual Concept Networks: A Graph-Based Approach to Detecting Anomalous Data in Deep Neural Networks](https://mlsanity.com/paper/2409.18235/) (2024)
- [A Comparison of Graph Neural Networks for Malware Classification](https://mlsanity.com/paper/2303.12812/) (2023)
- [Enhanced Graph Neural Networks with Ego-Centric Spectral Subgraph Embeddings Augmentation](https://mlsanity.com/paper/2310.12169/) (2023)
- [LLMs Prompted for Graphs: Hallucinations and Generative Capabilities](https://mlsanity.com/paper/2409.00159/) (2024)

## Abstract (arXiv)

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.