Spectral graph theory
By A. Hinge. 2019
2,822 citations recorded by the source corpus.
Spectral graph theory is a vast and expanding area of combinatorics. We start these notes by introducing and motivating classical matrices associated with a graph, and then show how to derive combinatorial properties of a graph from the eigenvalues of these matrices. We then examine more modern results such as polynomial interlacing and high dimensional expanders
Subfields: Geometry and Topology
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
- Michael M. Bronstein
- Michaël Defferrard
- Xavier Bresson
- Jiaoyang Huang
- Pierre Vandergheynst
- Vladimir Braverman
- Renjie Liao
- Raquel Urtasun
Citations in the corpus
- Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning (2018, background): “The graph Laplacian (Chung 1997) is defined as L := D − A, and the two versions of normalized graph Laplacians are defined as Lsym := D − (1)2LD− 1 2 and Lrw := D−1L respectively.”
- Generating 3D faces using Convolutional Mesh Autoencoders (2018, methodology): “The graph Fourier transform [15] of the mesh vertices x ∈ R is then defined as xω = U x, and the inverse Fourier transform as x = Uxω.”
- Discovering Options for Exploration by Minimizing Cover Time (2019, methodology): “On the other hand, while the eigenoption also uses the graph Laplacian for option discovery, their method is repurposed from a feature construction method.”
- Proximity Without Consensus in Online Multiagent Optimization (2016, result): “obtain the first one which has the a comparable Fiedler number (second-smallest eigenvalue of the graph Laplacian matrix) as the grid network, which is a standard measure of network connectivity – see [36], Ch. 1 for details. We display the results of this localization experiment in Figure 4. In Figu”
- Spectral Clustering for Speech Separation (2009, background): “Finally, in the next section, we also consider the normalized Laplacian matrix defined as L̃ = I − D−1/2WD−1/2.”
- Graph Sparsification by Effective Resistances (neutral): “Many properties of graphs and random walks are known to be revealed by their spectra (see any text on spectral graph theory, e.g. [7] or [18] for details).”
- Label Informed Attributed Network Embedding (2017, methodology): “Based on the definition of normalized graph Laplacian [8], we can reformulate Eq.”
- Network Topology Inference from Spectral Templates (2016, positive): “well, including for instance the combinatorial Laplacian Lc and the random walk Laplacian [34].”
- The Laplacian in RL: Learning Representations with Efficient Approximations (2018, methodology): “The d smallest eigenvectors of the Laplacian provide an embedding of each vertex in Rd which has been found to be especially useful in a variety of applications, such as graph visualization (Koren, 2003), clustering (Ng et al., 2002), and more (Chung & Graham, 1997).”
- Online Factorization and Partition of Complex Networks From Random Walks (2017, positive): “The matrix M gives a set of approximate “principal components" of the Markov chain, which has a similar spirit as spectral clustering [6].”
- Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “For instance, supposing G is a finite regular graph and the communication matrix is the random walk matrix, then the inverse of the spectral gap (1− σ2) scales as Θ(1) for a complete graph, Θ(n) for a grid, and Θ(n(2)) for a cycle [14, 24, 18].”
- Learning to Propagate Labels: Transductive Propagation Network for Few-Shot Learning (2018, methodology): “2 GRAPH CONSTRUCTION Manifold learning (Chung and Graham, 1997; Zhou et al., 2004; Yang et al., 2016) discovers the embedded low-dimensional subspace in the data, where it is critical to choose an appropriate neighborhood graph.”
- Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (2019, background): “It is known that the largest eigenvalue of ∆ is 2 if and only if the graph has a non-trivial bipartite connected component (see, e.g., Chung & Graham (1997)).”
- Multi-View Clustering and Semi-Supervised Classification with Adaptive Neighbours (2017, background): “There is an important property of Laplacian matrix (Mohar 1991), (Chung 1997) Theorem 1.”
- Propagation Model Search for Graph Neural Networks (2020, methodology): “We consider two normalized versions of the adjacency matrix A , which have been well analyzed in spectral graph theory (Chung and Graham 1997) and have been shown to be important for learning graph moments in the context of GNN (Dehmamy, Barab´asi, and Yu 2019), as our propagation matrices: where…”