2019

LanczosNet: Multi-Scale Deep Graph Convolutional Networks

Liao, Renjie, Zhao, Zhizhen, Urtasun, Raquel et al.

Understand

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.

Built on

An iteration method for the solution of the eigenvalue problem of linear differential and integral operators
Cornelius Lanczos · 1950
Earlier work this paper cites.
The Symmetric Eigenvalue Problem
Beresford N Parlett · 1980
Earlier work this paper cites.
Scale-space filtering
Andrew P Witkin · 1983
Earlier work this paper cites.
Recursive distributed representations
Jordan B Pollack · 1990
Earlier work this paper cites.
Spectral graph theory
Fan RK Chung · 1997
Earlier work this paper cites.
Low-rank matrix approximation using the lanczos bidiagonalization process with applications
Horst D Simon and Hongyuan Zha · 2000
Earlier work this paper cites.
Nonlinear dimensionality reduction by locally linear embedding
Sam T Roweis and Lawrence K Saul · 2000
Earlier work this paper cites.
A global geometric framework for nonlinear dimensionality reduction
Joshua B Tenenbaum, Vin De Silva, and John C Langford · 2000
Earlier work this paper cites.
Laplacian eigenmaps and spectral techniques for embedding and clustering
Mikhail Belkin and Partha Niyogi · 2002
Earlier work this paper cites.
Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
David L Donoho and Carrie Grimes · 2003
Earlier work this paper cites.
Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods
Ronald R Coifman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker · 2005
Earlier work this paper cites.
Self-tuning spectral clustering
Lihi Zelnik-Manor and Pietro Perona · 2005
Earlier work this paper cites.
Diffusion kernels on statistical manifolds
John Lafferty and Guy Lebanon · 2005
Earlier work this paper cites.
Diffusion maps
Ronald R Coifman and Stéphane Lafon · 2006
Earlier work this paper cites.
From graph to manifold laplacian: The convergence rate
Amit Singer · 2006
Earlier work this paper cites.
Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators
Boaz Nadler, Stephane Lafon, Ioannis Kevrekidis, and Ronald R Coifman · 2006
Earlier work this paper cites.
Semi-supervised learning literature survey
Xiaojin Zhu · 2006
Earlier work this paper cites.
Manifold regularization: A geometric framework for learning from labeled and unlabeled examples
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani · 2006
Earlier work this paper cites.
Metric learning for kernel regression
Kilian Q Weinberger and Gerald Tesauro · 2007
Earlier work this paper cites.
A tutorial on spectral clustering
Ulrike Von Luxburg · 2007
Earlier work this paper cites.
Methods of information geometry
Shun-ichi Amari and Hiroshi Nagaoka · 2007
Earlier work this paper cites.
Numerical recipes 3rd edition: The art of scientific computing
William H Press, Saul A Teukolsky, William T Vetterling, and Brian P Flannery · 2007
Earlier work this paper cites.
Non-linear independent component analysis with diffusion maps
Amit Singer and Ronald R Coifman · 2008
Earlier work this paper cites.

Similar

The graph neural network model
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini · 2009
Cited alongside, same era.
Diffusion interpretation of nonlocal neighborhood filters for signal denoising
Amit Singer, Yoel Shkolnisky, and Boaz Nadler · 2009
Cited alongside, same era.
Detecting intrinsic slow variables in stochastic dynamical systems by anisotropic diffusion maps
Amit Singer, Radek Erban, Ioannis G Kevrekidis, and Ronald R Coifman · 2009
Cited alongside, same era.
Graph kernels
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt · 2010
Cited alongside, same era.
Wavelets on graphs via spectral graph theory
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval · 2011
Cited alongside, same era.
The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst · 2013
Cited alongside, same era.
Empirical intrinsic geometry for nonlinear modeling and time series filtering
Ronen Talmon and Ronald R Coifman · 2013
Cited alongside, same era.
Spectral networks and locally connected networks on graphs
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun · 2014
Cited alongside, same era.
Deep convolutional networks on graph-structured data
Original
Mikael Henaff, Joan Bruna, and Yann LeCun · 2015
Cited alongside, same era.
Convolutional networks on graphs for learning molecular fingerprints
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams · 2015
Cited alongside, same era.
Accelerated filtering on graphs using lanczos method
Original
Ana Susnjara, Nathanael Perraudin, Daniel Kressner, and Pierre Vandergheynst · 2015
Cited alongside, same era.
Dynamics-adapted cone kernels
Dimitrios Giannakis · 2015
Cited alongside, same era.

Then

Learning graph representations with embedding propagation
Alberto Garcia Duran and Mathias Niepert · 2017
Later among the works it cites.
Inductive representation learning on large graphs
William L. Hamilton, Rex Ying, and Jure Leskovec · 2017
Later among the works it cites.
Community detection with graph neural networks
Original
Joan Bruna and Xiang Li · 2017
Later among the works it cites.
Situation recognition with graph neural networks
Ruiyu Li, Makarand Tapaswi, Renjie Liao, Jiaya Jia, Raquel Urtasun, and Sanja Fidler · 2017
Later among the works it cites.
3d graph neural networks for rgbd semantic segmentation
Xiaojuan Qi, Renjie Liao, Jiaya Jia, Sanja Fidler, and Raquel Urtasun · 2017
Later among the works it cites.
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl · 2017
Later among the works it cites.
Automatic differentiation in pytorch
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer · 2017
Later among the works it cites.
Relational inductive biases, deep learning, and graph networks
Original
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al · 2018
Later among the works it cites.
Graph signal processing: Overview, challenges, and applications
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst · 2018
Later among the works it cites.
Multi-scale kernels for nyström based extension schemes
Neta Rabin and Dalia Fishelov · 2018
Later among the works it cites.
Few-shot learning with graph neural networks
Victor Garcia and Joan Bruna · 2018
Later among the works it cites.
Learning deep generative models of graphs
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia · 2018
Later among the works it cites.
Junction tree variational autoencoder for molecular graph generation
Wengong Jin, Regina Barzilay, and Tommi Jaakkola · 2018
Later among the works it cites.
FastGCN: Fast learning with graph convolutional networks via importance sampling
Jie Chen, Tengfei Ma, and Cao Xiao · 2018
Later among the works it cites.
Stochastic training of graph convolutional networks with variance reduction
Jianfei Chen, Jun Zhu, and Le Song · 2018
Later among the works it cites.
Graph attention networks
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio · 2018
Later among the works it cites.
Deep parametric continuous convolutional neural networks
Shenlong Wang, Simon Suo, Wei-Chiu Ma, Andrei Pokrovsky, and Raquel Urtasun · 2018
Later among the works it cites.
Graph partition neural networks for semi-supervised classification
Renjie Liao, Marc Brockschmidt, Daniel Tarlow, Alexander L Gaunt, Raquel Urtasun, and Richard Zemel · 2018
Later among the works it cites.
Inference in probabilistic graphical models by graph neural networks
Original
KiJung Yoon, Renjie Liao, Yuwen Xiong, Lisa Zhang, Ethan Fetaya, Raquel Urtasun, Richard Zemel, and Xaq Pitkow · 2018
Later among the works it cites.
Nervenet: Learning structured policy with graph neural networks
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler · 2018
Later among the works it cites.
Graph networks as learnable physics engines for inference and control
Original
Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia · 2018
Later among the works it cites.
Moleculenet: a benchmark for molecular machine learning
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande · 2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…