NetLSD: Hearing the Shape of a Graph
Authors:
- Anton TsitsulinATAnton Tsitsulin
- Davide MottinDMDavide Mottin
- Panagiotis KarrasPKPanagiotis Karras
- Alex BronsteinABAlex Bronstein
- Emmanuel MüllerEMEmmanuel Müller
Preprint
Abstract
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.Keywords
All Related Versions
- Version 1, 2018-05-28, ArXiv
- Version 2, 2018-05-29, ArXiv
- Published version: , 2347.
This publication has 30 references indexed in Scilit:
- Approximation of graph edit distance based on Hausdorff matchingPattern Recognition, 2015
- Graph similarity search on large uncertain graph databasesThe VLDB Journal, 2014
- A spectral notion of Gromov–Wasserstein distance and related methodsApplied and Computational Harmonic Analysis, 2011
- Web graph similarity for anomaly detectionJournal of Internet Services and Applications, 2010
- oddball: Spotting Anomalies in Weighted Graphs2010
- Approximate graph edit distance computation by means of bipartite graph matchingImage and Vision Computing, 2009
- A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud DataFoundations of Computational Mathematics, 2005
- Which graphs are determined by their spectrum?Linear Algebra and its Applications, 2003
- A Panoramic View of Riemannian Geometry2003
- Hardness of approximating graph transformation problem1994