PaperlayerView exact revision on arXiv

Source-linked AI summary

LanczosNet: Multi-Scale Deep Graph Convolutional Networks

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

arXiv:1901.01484v2cs.LGstat.ML

TL;DR

Graph convolution needs efficient multi-scale processing and adaptable spectral filters, while recurrent graph models are harder to optimize. LanczosNet uses low-rank Lanczos approximations to address these issues, and its adaptive variant learns kernels and embeddings; the models outperform a range of graph networks in most reported tasks.

  • Problem

    Graph convolution methods lack efficient multi-scale schemes and mostly use fixed spectral filters, while recurrent graph networks are generally slower and harder to train.

  • Method

    LanczosNet uses a Lanczos-based low-rank graph-Laplacian approximation for multi-scale convolution and learnable spectral filters, while AdaLanczosNet back-propagates through Lanczos for kernel and node-embedding learning.

  • Results

    LanczosNet achieves state-of-the-art results in most tasks and outperforms a range of graph networks on challenging graph problems.

  • Takeaways & Limitations

    The Lanczos construction connects deep graph networks with graph-based manifold learning, especially diffusion maps, and supports multi-scale information and adaptive representation learning.

  • Takeaways & Limitations

    Lanczos filters whose basis depends on input features require a separate Lanczos run for each graph-convolution layer, making stacking computationally demanding.

Abstract

from arXiv · show

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{https://github.com/lrjconan/LanczosNetwork}.

1 INTRODUCTION

LanczosNet addresses computational and modeling limitations in graph convolution by efficiently capturing multi-scale information and learning spectral filters. Its adaptive variant further supports graph kernel and node embedding learning, with strong results across graph benchmarks.

  • Graph learning methods for classification and regression commonly use graph convolutions or recurrent neural networks.
  • RNN-based graph neural networks repeatedly pass messages between nodes but are generally slower and harder to train because of unstable dynamics and optimization difficulty.
  • Graph convolution approaches lack an efficient, learnable scheme for exploiting multi-scale information, while graph coarsening can introduce bias and matrix-power methods can be memory intensive.
  • Fixed spectral filters limit graph convolution models because learnable filters can adapt the underlying stochastic processes to data.
  • LanczosNet uses a low-rank graph-Laplacian approximation for efficient matrix powers and multi-scale convolution, while enabling learnable spectral filters.
  • AdaLanczosNet back-propagates through the Lanczos algorithm to learn graph kernels and node embeddings, and the models achieve state-of-the-art results in most benchmark tasks.

2 BACKGROUND

The background formulates graph signals, Laplacian-based spectral filtering, and localized polynomial filters. It motivates Lanczos methods through Krylov subspaces while noting that standard polynomial filters use fixed spectral forms.

  • A graph G=(V,E,A) has N nodes, adjacency matrix A, and node-feature matrix X∈R^N×F whose rows represent node features.
  • Graph Laplacians can be defined in multiple ways; the symmetric normalized form is real symmetric, positive semidefinite, and has eigenvalues in [0,2].
  • Using the symmetric affinity matrix S yields a spectral decomposition S=UΛU^⊤, enabling graph Fourier transforms and filters in the eigenbasis shared with the Laplacian.
  • A τ-localized polynomial filter uses learnable coefficients over powers of the graph operator and incorporates information from nodes at most τ hops away.
  • Chebyshev filtering avoids spectral decomposition, but its spectral functional form is fixed and cannot adapt to the data.
  • Generalized polynomial filtering maps node features and operator powers up to order t through g_t and filter coefficients W_t to produce an N×O output.
  • Lanczos methods provide an orthonormal basis for the relevant Krylov subspace, motivating their use for graph filtering.

3 LANCZOS NETWORKS

LanczosNet uses Lanczos-based low-rank approximations to construct efficient multi-scale graph convolutions with learnable spectral filters. Its adaptive variant back-propagates through Lanczos to learn graph kernels and node embeddings.

  • 3.1 LANCZOS ALGORITHM: LanczosNet computes an orthogonal basis and tridiagonal matrix from the affinity matrix using the Lanczos algorithm.The decomposition satisfies Q^⊤SQ = T and provides a basis for the Krylov subspace.
  • 3.2 LANCZOSNET: Using feature-dependent Lanczos bases makes localized polynomial filters compact but requires a separate Lanczos run for each graph convolution layer.The resulting computational demand motivates an alternative feature-independent low-rank approximation.
  • 3.2 LANCZOSNET: The model approximates S^t with V R^t V^⊤, reducing matrix-power computation to powering diagonal Ritz values.This approximation supports efficient filtering over long-range and multi-scale dependencies.
  • 3.2 LANCZOSNET: LanczosNet replaces fixed spectral forms with learnable filters parameterized by MLPs applied to Ritz values and vectors.The learnable filter includes polynomial filtering as a special case.
  • 3.2 LANCZOSNET: Multi-scale graph convolution combines short-scale powers of S with long-scale approximations derived from the Lanczos decomposition.Scale parameters can include short ranges such as {0, 1, . . . , 5} and long ranges such as {10, 20, . . . , 50}.
  • 3.3 ADALANCZOSNET: AdaLanczosNet back-propagates through the Lanczos algorithm to learn graph kernels and/or node embeddings.Its graph-kernel formulation uses an MLP-based anisotropic kernel intended to capture intrinsic geometry in node representations.

4 LANCZOS NETWORK AND DIFFUSION MAPS

The paper connects LanczosNet’s multi-scale graph convolution to diffusion maps, where powers of a random-walk operator provide scale-dependent node representations and frequency features. LanczosNet approximates these representations using Ritz values and applies spectral filters across multiple scales.

  • Diffusion Maps: Diffusion maps use the adjacency weights to define a random walk with transition matrix P = D−1A.P^t aggregates probabilities over paths of length t.
  • Diffusion Maps: For sufficiently large t, diffusion distances can be approximated using only a few largest eigenvalues and eigenvectors.Eigenvalue powers λ_l^t approach zero for the remaining components.
  • Connection to Graph Convolution: Diffusion maps embed node features X at different time scales and can also compute their frequency representations.These representations use graph Fourier eigenvectors and eigenvalue powers.
  • Connection to Graph Convolution: LanczosNet applies spectral filters to frequency representations obtained by projecting X onto multiple diffusion maps with different scales t.The model replaces graph-Laplacian eigenvalues with Ritz-value approximations in its convolution layer.

5 RELATED WORK

Related graph-learning work includes supervised and unsupervised applications, graph signal-processing-based convolutions, recurrent propagation models, and manifold-learning methods that exploit graph affinities.

  • Graph Learning Applications: Deep learning on graphs commonly addresses supervised or semi-supervised prediction and unsupervised node or graph embedding.Graph generative models, including molecule generation, are another recent application.
  • Graph Convolution Based Models: Graph signal-processing models generalize convolution to graph signals using spectral graph theory, graph wavelets, and graph frequency representations.Spectral graph theory-based definitions are described as popular in this model class.
  • Recurrent Neural Networks based Models: Recurrent graph models propagate information over arbitrary graphs, with gated graph neural networks adding gated recurrent units.These models extend recursive neural-network ideas beyond trees.
  • Graph based Manifold Learning: Graph-based manifold-learning methods assume data lie near a low-dimensional manifold and use local graph affinities to learn global features.They support embedding complex data in low-dimensional spaces and regressing functions over graphs.

6 EXPERIMENTS

The experiments compare LanczosNet and AdaLanczosNet with nine recent graph networks on citation classification and QM8 molecular regression. Ablations show benefits from long-range multi-scale convolution, learnable spectral filters, and node embeddings.

  • Experimental setup: LanczosNet and AdaLanczosNet are compared with nine recent graph networks on citation-network classification and QM8 molecular-property regression.The comparisons use three citation networks and the QM8 dataset under shared experimental settings.
  • Citation networks: LanczosNet or AdaLanczosNet achieves state-of-the-art accuracy on difficult random citation splits and performs closely to GAT on public splits.GAT performs best on the public split but poorly on random splits with varying training portions.
  • Quantum chemistry: QM8 models predict 16 electronic spectra and energy quantities per molecule graph using mean absolute error as the evaluation measure.The dataset contains molecular multigraphs with atoms as nodes and chemical bonds as labeled edges.
  • Ablation study: Long graph-convolution scales improve QM8 performance, while combining short and long scales improves it further.This ablation fixes the node embedding to one-hot encoding and omits learnable spectral filters.
  • Ablation study: Lanczos steps of 10 or 20 perform better on QM8, consistent with the dataset’s average graph size of roughly 16 nodes.The Lanczos step affects the accuracy of the induced low-rank approximation.
  • Ablation study: A 3-layer MLP reduces QM8 error relative to no learnable spectral filter, whereas a deeper MLP does not appear helpful.The MLP uses 128 hidden units per layer and ReLU nonlinearities; deeper models may face optimization challenges.
  • Ablation study: Learning node embeddings significantly improves both LanczosNet variants and is more effective than learning graph kernels; tuning scale parameters provides an additional boost.The ablation contrasts learned node-specific functions with a graph-kernel function shared across nodes.

7 CONCLUSION

The paper concludes that LanczosNet uses low-rank graph-Laplacian approximations to support efficient multi-scale graph convolution and learnable spectral filters. AdaLanczosNet additionally supports graph-kernel and node-embedding learning, and experiments show strong performance on challenging graph tasks.

  • Conclusion: LanczosNet uses the Lanczos algorithm to approximate the graph Laplacian, enabling efficient multi-scale graph convolution and learnable spectral filters.The paper also connects LanczosNet with graph-based manifold learning, especially diffusion maps.
  • Conclusion: AdaLanczosNet extends the approach to graph-kernel and node-embedding learning, while experiments report performance exceeding a range of other graph networks.The authors identify customized eigendecomposition methods for tridiagonal matrices as a possible direction for improving AdaLanczosNet.

8 APPENDIX

The appendix states the Lanczos approximation theorem framework, discusses numerical orthogonality, and documents experimental settings and dataset-split notation.

  • 8.1 LOW RANK APPROXIMATION: Lemma 1 bounds how a Krylov subspace approximates leading eigenspaces using Chebyshev polynomials and an eigenvalue-gap parameter.It defines the Krylov subspace from repeated applications of A to v and relates it to the eigendecomposition of A.
  • 8.1 LOW RANK APPROXIMATION: Theorem 1 applies the approximation result to K-step Lanczos outputs Q and T for a symmetric matrix S.The result assumes 1 < j < N and K > j, with Q orthogonal and T tridiagonal.
  • 8.1 LOW RANK APPROXIMATION: The proof identifies the Lanczos span with the Krylov subspace generated by v, S v, through S^(K−1)v and then invokes Lemma 1.The orthogonal projection onto the complement of span{Q} is also introduced in the proof.
  • 8.2 LANCZOS ALGORITHM: Floating-point round-off can destroy Lanczos-vector orthogonality, while full Gram–Schmidt restoration is computationally expensive.The authors omit re-orthogonalization because the issue did not hurt performance for a small iteration count such as K = 20.
  • Experimental settings: For ChebyNet, graph coarsening is omitted because it is computationally demanding on large graphs and can lose information on small molecule graphs.The appendix contrasts coarsening with directly stacking another layer on the original graph.
  • Experimental settings: The appendix reports citation-network and quantum-chemistry training configurations, including optimizer settings, stopping rules, layer counts, and LanczosNet hyperparameters.Citation experiments use Adam with learning rate 1.0e−2 and weight decay 5.0e−4; quantum-chemistry experiments use learning rate 1.0e−4 and no weight decay.
Loading 1901.01484v2…