NetLSD: Hearing the Shape of a Graph

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.

arXiv commentKDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19--23, 2018, London, United Kingdom

References in corpus (8)

• Stochastic blockmodels and community structure in networks
• struc2vec: Learning Node Representations from Structural Identity
• Consistency of spectral clustering
• VERSE: Versatile Graph Embeddings from Similarity Measures
• DELTACON: A Principled Massive-Graph Similarity Function
• The Multiscale Laplacian Graph Kernel
• Hitting and commute times in large graphs are often misleading
• Heat kernel based community detection

Cited by in corpus (31)

• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Identity Inference on Blockchain using Graph Neural Network
• GOT: An Optimal Transport framework for Graph comparison
• Network comparison and the within-ensemble graph distance
• netrd: A library for network reconstruction and graph distances
• M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification
• Data Augmentation for Graph Classification
• The Shape of Data: Intrinsic Distance for Data Distributions
• Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs
• Tree++: Truncated Tree Based Graph Kernels
• Graph embeddings for Abusive Language Detection
• A Large-Scale Database for Graph Representation Learning
• Generalized Spectral Clustering via Gromov-Wasserstein Learning
• Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs
• Simplicial Complex Representation Learning
• An embedding-based distance for temporal graphs
• Hyperparameter-free and Explainable Whole Graph Embedding
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• JITuNE: Just-In-Time Hyperparameter Tuning for Network Embedding Algorithms
• Hypergraph Dissimilarity Measures
• Spectral Graph Complexity
• DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data
• Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
• Unsupervised Joint $k$-node Graph Representations with Compositional Energy-Based Models
• Little Ball of Fur: A Python Library for Graph Sampling
• Graph-Level Embedding for Time-Evolving Graphs
• Density of States Graph Kernels
• Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization
• Graph Coarsening with Preserved Spectral Properties