LanczosNet: Multi-Scale Deep Graph Convolutional Networks

By Renjie Liao, Zhizhen Zhao, Raquel Urtasun, Richard S. Zemel. 2019

249 citations recorded by the source corpus.

We propose the Lanczos network (LanczosNet), which uses the Lanczos algorithm to construct low rank approximations of the graph Laplacian for graph convolution. Relying on the tridiagonal decomposition of the Lanczos algorithm, we not only efficiently exploit multi-scale information via fast approximated computation of matrix power but also design learnable spectral filters. Being fully differentiable, LanczosNet facilitates both graph kernel learning as well as learning node embeddings. We show the connection between our LanczosNet and graph based manifold learning methods, especially the diffusion maps. We benchmark our model against several recent deep graph networks on citation networks and QM8 quantum chemistry dataset. Experimental results show that our model achieves the state-of-the-art performance in most tasks. Code is released at: \url{this https URL}.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Neurology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Neurology

Citations in the corpus

Masked Label Prediction: Unified Massage Passing Model for Semi-Supervised Classification (2020, methodology): “…of methods to implement message passing model, Graph Neural Networks (GNNs) [ Kipf and Welling, 2016; Hamilton et al. , 2017; Xu et al. , 2018b; Liao et al. , 2019; Xu et al. , 2018a ] and Label Propagation Algorithms (LPAs) [ Zhu et al. , 2003; Zhang and Lee, 2007; Wang and Zhang, 2007;…”
Simplifying Graph Convolutional Networks (2019, methodology): “Similarly, on QM8 quantum chemistry dataset (Ramakrishnan et al., 2015), more advanced AdaLNet and LNet (Liao et al., 2019) get 0.01 MAE on QM8, outperforming SGC’s 0.03 MAE by a large margin.”
Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, methodology): “…instead focus on selecting a speciﬁc node ordering based on heuristics: GraphRNN (You et al., 2018b) uses random breadth-ﬁrst search (BFS) to determine an ordering, and GRAN (Liao et al., 2019) adaptively chooses an ordering depending on the input graph from a family of pre-deﬁned node orderings.”
Graph Neural Networks With Convolutional ARMA Filters (2019, methodology): “…(FIR) and realize a weighted moving average ﬁltering of graph signals on local node neighbourhoods (Tremblay et al., 2018), thus allowing for fast distributed implementations based on Chebyshev polynomials and Lanczos iterations (Susnjara et al., 2015; Defferrard et al., 2016; Liao et al., 2019).”
Do Large Scale Molecular Language Representations Capture Important Structural Information? (2021, methodology): “…and Welling (2017); Li et al. (2015); Veli ˇ ckovi ´ c et al. (2018); Hamilton et al. (2018); Gilmer et al. (2017); Schlichtkrull et al. (2017); Liao et al. (2019); Chen et al. (2019) have been extensively used and shown impressive performance for learning molecular representations on QM…”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “Graph convolutions have spatial (see, e.g., Hamilton et al. (2017a,b); Schlichtkrull et al. (2018); Gilmer et al. (2017)) and spectral constructions (see, e.g., Liao et al. (2019); Kipf and Welling (2017); Defferrard et al. (2016); Levie et al. (2017)).”
GRAND: Graph Neural Diffusion (2021, methodology): “…Networks (CGNN) (Xhonneux et al., 2020), Graph Neural Ordinary Differential Equations (GDE) (Poli et al., 2019), and Ordinary Differential Equations on Graphs (GODE) (Zhuang et al., 2020) and two versions of LanczosNet (Liao et al., 2019) which approximate solutions to a linear diffusion PDE.”
Disentangling and Unifying Graph Convolutions for Skeleton-Based Action Recognition (2020, methodology): “LanczosNet [24] deploys a low-rank approximation of the adjacency matrix to speed up the exponentiation on large graphs.”
Graph convolutional networks: a comprehensive review (2019, methodology): “Based on this, the proposed spectral filter in LanczosNet is formulated as: where R̂(k) = fk([R0, . . . ,RK−1]) is a diagonal matrix and fk is a multi-layer perceptron (MLP).”
Graph Representation Learning (2020, methodology): “Existing works have used this strategy with graph statistics such as degree distributions, graphlet counts, and spectral features, with distributional distances computed using variants of the total variation score and the first Wasserstein distance [Liao et al., 2019b, You et al., 2018].”
What graph neural networks cannot learn: depth vs width (2019, background): “Networks using a global state (Battaglia et al., 2018) or looking at multiple hops per layer (Morris et al., 2019; Liao et al., 2019; Isuﬁ et al., 2020) are not directly GNN mp , but they can often be re-expressed as such.”
Unifying Graph Convolutional Neural Networks and Label Propagation (2020, background): “…the node side V , node features are propagated along edges and transformed through neural network layers, which is known as Graph Convolutional Neural Networks (GCN) (Kipf & Welling, 2017; Hamilton et al., 2017; Li et al., 2018; Xu et al., 2018; Liao et al., 2019; Xu et al., 2019; Qu et al., 2019).”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “Graph convolutions have spatial (see, e.g., [87, 88, 199, 80]) and spectral constructions (see, e.g., [145, 123, 59, 138]).”
Learning Lane Graph Representations for Motion Forecasting (2020, background): “Graph Convolutional Networks: Graph Convolutional Networks (GCNs) [36,19,15,26,13,30] have been shown to be eﬀective for graph representation learning.”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “The power graph adjacency matrices leverage multi-scale information in the graph, but note that they differ from simply taking the powers of the adjacency matrix, which is exploited in [24] for example.”