Using Laplacian Spectrum as Graph Feature Representation
arXiv:1912.00735
Abstract
Graphs possess exotic features like variable size and absence of natural ordering of the nodes that make them difficult to analyze and compare. To circumvent this problem and learn on graphs, graph feature representation is required. A good graph representation must satisfy the preservation of structural information, with two particular key attributes: consistency under deformation and invariance under isomorphism. While state-of-the-art methods seek such properties with powerful graph neural-networks, we propose to leverage a simple graph feature: the graph Laplacian spectrum (GLS). We first remind and show that GLS satisfies the aforementioned key attributes, using a graph perturbation approach. In particular, we derive bounds for the distance between two GLS that are related to the \textit{divergence to isomorphism}, a standard computationally expensive graph divergence. We finally experiment GLS as graph representation through consistency tests and classification tasks, and show that it is a strong graph feature representation baseline.
arXiv comment10 pages, 3 figures, 7 appendices
References in corpus (10)
- Scikit-learn: Machine Learning in Python
- Semi-Supervised Classification with Graph Convolutional Networks
- Spectral Networks and Locally Connected Networks on Graphs
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
- Spectral methods for network community detection and graph partitioning
- Graph Isomorphism in Quasipolynomial Time
- A Simple Baseline Algorithm for Graph Classification
- Feature-Based Classification of Networks
- Dynamics Based Features For Graph Classification
- Variational Recurrent Neural Networks for Graph Classification