Source-linked AI summary
Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, Doina Precup
TL;DR
Existing GCNs have limited expressive power because shallow architectures and activation functions constrain deep, multi-scale representation learning. The paper analyzes these limits, reformulates graph convolution in block Krylov form, and proposes snowball and truncated Krylov architectures. Across node-classification tasks, both architectures outperform many state-of-the-art methods, including without validation, while their practical analysis is limited by assumptions and computational difficulties in truncation and adaptive Krylov construction.
Problem
Existing GCNs have limited expressive power because shallow learning mechanisms restrict compositionality and label propagation.
Method
The paper generalizes spectral graph convolution and deep GCNs into block Krylov forms and proposes snowball and truncated Krylov architectures that use multi-scale features differently.
Results
The proposed architectures achieve state-of-the-art performance across multiple transductive node-classification tasks, with or without validation data.
Takeaways & Limitations
The architectures provide deeper GCN designs with stronger expressive power and richer graph representations through multi-scale information.
Takeaways & Limitations
Truncated Krylov methods lack a practical error bound because existing bounds require assumptions on X or L that do not hold for variable training inputs.
Abstract
from arXiv · showhide
Recently, neural network based approaches have achieved significant improvement for solving large, complex, graph-structured problems. However, their bottlenecks still need to be addressed, and the advantages of multi-scale information and deep architectures have not been sufficiently exploited. In this paper, we theoretically analyze how existing Graph Convolutional Networks (GCNs) have limited expressive power due to the constraint of the activation functions and their architectures. We generalize spectral graph convolution and deep GCN in block Krylov subspace forms and devise two architectures, both with the potential to be scaled deeper but each making use of the multi-scale information in different ways. We further show that the equivalence of these two architectures can be established under certain conditions. On several node classification tasks, with or without the help of validation, the two new architectures achieve better performance compared to many state-of-the-art methods.
1 Introduction and Motivation
Existing GCNs achieve strong results on graph-learning tasks but remain limited by shallow learning mechanisms and underuse of deep, multi-scale representations. The paper analyzes these bottlenecks and proposes two deeper architectures that exploit multi-scale information.
- Existing GCNs have limited expressive power because their learning mechanisms are shallow.
- Deepening GCNs can cause over-smoothing, making node representations indistinguishable, while graph coarsening can reproduce longer-range information flow.
- Shallow mechanisms violate deep-learning compositionality and restrict label propagation.
- The paper proposes two architectures that use multi-scale information differently and can scale to deeper, richer structures.
- The proposed architectures achieve state-of-the-art performance across multiple transductive tasks, with or without validation data.
2 Preliminaries
The paper formulates graph signals and convolution through a general diffusion operator and its spectral decomposition. Spectrum-free GCNs avoid explicit eigendecomposition while applying graph propagation to multi-channel features.
- A graph is represented with a symmetric adjacency matrix, degree matrix, diffusion operator, and node feature matrix.
- The diffusion operator can be a graph Laplacian, normalized Laplacian, or affinity matrix and decomposes into graph Fourier eigenvectors and eigenvalues.
- Graph convolution filters graph signals in the graph Fourier domain using a Hadamard product.
- The GCN formulation generalizes convolution to multiple input and output channels.
- Spectrum-free GCNs use L = D^-1/2 ÃD^-1/2 and avoid explicit eigendecomposition and frequency-domain operations.
3 Why GCN is not Scalable?
The paper argues that simply increasing GCN depth reduces expressive power: representations converge toward stationary graph information, while activation functions can further reduce feature independence. Tanh preserves independence better than ReLU in the reported analysis.
- A conventionally deep GCN repeatedly applies graph propagation, activation, and learned channel transformations before softmax classification.
- Theorem 1 states that, for graphs without bipartite components, the deep model's output rank is at most k almost surely as n approaches infinity.
- Theorem 1 implies that increasing depth can leave only stationary graph information and lose node-feature information.
- In a 100-layer synthetic experiment, hidden-feature rank decreases rapidly with ReLU but fluctuates little with Tanh, while identity also outperforms ReLU.
- The paper therefore proposes replacing ReLU with Tanh to better preserve linear independence among column features.
4 Spectral Graph Convolution and Block Krylov Subspace Methods
The paper represents spectral graph convolution and deep GCNs in block Krylov form, exposing a common multi-scale structure. Because adaptive Krylov computation is difficult during training, it motivates architectures that stack multi-scale features more practically.
- Block Krylov preliminaries: A block inner product maps pairs of block vectors into a matrix space with linearity, definiteness, and related structural conditions.
- Block Krylov preliminaries: The order-m block Krylov subspace spans B, AB, through A^(m−1)B, and its matrix concatenates these iterates as columns.
- Spectral convolution: Any graph convolution with a well-defined analytic spectral filter can be written as a block Krylov matrix multiplied by a structured learnable parameter matrix.
- Deep GCN formulation: The resulting deep GCN form iteratively applies analytic filters, point-wise activations, and learned transformations to block Krylov features.
- Connections to existing models: This general form includes fully connected networks, GCN, and ChebNet as special cases under particular filters and parameter choices.
- Computational difficulties: Direct Krylov implementation is difficult because feature-dependent subspace sizes require adaptive parameters and QR factorization is hard to integrate with backpropagation.
5 Deep GCN Architectures
The paper proposes snowball and truncated Krylov GCN architectures that concatenate multi-scale features differently while supporting deeper structures. The designs address over-smoothing by preserving local information, but practical error bounds for truncation remain unavailable when features vary during training.
- Snowball and truncated Krylov concatenate multi-scale feature information differently while both having the potential to scale to deeper architectures.
- 5.1 Snowball: The densely connected snowball network concatenates all previously learned features so each node receives a richer multi-scale representation.Its construction is analogous to DenseNet and is described as supporting feature reuse, propagation, compactness, and mitigation of vanishing gradients.
- 5.2 Truncated Krylov: Truncated Krylov fixes the per-layer subspace size m_i as a hyperparameter, producing a truncated block Krylov network.This compromise makes the architecture compatible with the block Krylov framework.
- 5.2 Truncated Krylov: Practical truncation error bounds cannot be obtained without restricting the varying training features X or their relation to the diffusion operator L.Existing analyses require assumptions such as Gaussian X or eigenvalue conditions on L.
- 5.3 Equivalence of Linear Snowball GCN and Truncated Block Krylov Network: A linear snowball GCN with identity activation, identity classifier, and p = 1 is equivalent to a one-layer block Krylov network with a special parameter matrix.
- 5.4 Intuition behind Multi-scale Information Concatenation: Multi-scale concatenation preserves local information that would otherwise be diluted as graph convolution reaches farther-hop neighbors.Deep propagation can make nodes in the same connected component indistinguishable by replacing individual features with increasingly global ones.
6 Experiments
The experiments evaluate the proposed GCN variants across multiple graph node-classification settings, including public and smaller data splits, with and without validation. The proposed architectures achieve strong performance, while linear Snowball GCN reaches state-of-the-art performance at lower computational cost.
- Experimental setup: The study evaluates linear Snowball GCN, Snowball GCN, and truncated block Krylov networks on Cora, Citeseer, PubMed, and smaller splits.The comparison includes several existing graph-learning methods and covers settings with different training-set sizes.
- Experimental setup: The experiments use best hyperparameters, repeated runs, and early stopping to obtain average accuracy.Hyperparameter search includes optimizer settings, layer widths and depths, dropout, and Krylov-block counts.
- Results: The proposed architectures achieve overwhelming performance in all reported test cases.The paper especially emphasizes their advantage when training sets are small.
- Results: The proposed architectures extract good features from small training data, particularly the truncated Krylov model.This conclusion is based on the t-SNE visualization of output-layer features for Cora.
- Results: Linear Snowball GCN achieves state-of-the-art performance with much less computational cost.The claim is presented as an additional result of the experiments.
- Experimental setup: Tables report accuracy without and with validation, using greener cells for better performance and boldface when the authors' methods outperform all others.The supplied table passages identify the two evaluation settings and the comparison encoding.
Appendix I: Proof of Theorem 1, 2
The appendix proves how activation functions and repeated graph diffusion affect feature independence and rank in deep GCNs. It establishes that Tanh generally preserves or increases independence, whereas deep diffusion with ReLU can collapse representations toward graph-stationary information.
- ReLU analysis: Point-wise ReLU generally preserves independence between linearly independent vectors, but its behavior depends on the sign relationship between dependent vectors.The proof analyzes positive and negative components and identifies a probability-one conclusion under the stated sampling assumptions.
- Assumptions: The appendix formulates the ReLU and Tanh results under continuous random sampling and point-wise activation assumptions.These assumptions are used throughout the lemmas and theorem proofs.
- Theorem 1: Theorem 1 states that, for graphs without bipartite components, sufficiently deep GCN outputs have rank at most the number of connected components almost surely.The proof bounds the output rank by the rank of the repeatedly diffused feature matrix, whose limiting rank is at most k.
- Tanh analysis: Point-wise Tanh breaks linear dependencies with probability one and increases independence among vectors in the analyzed setting.The proof extends the argument from R2 to RN by showing that the exceptional solution set has probability zero.
Appendix II: Numerical Experiments on Synthetic Data
The synthetic experiments evaluate whether network structures and activation functions retain expressive features in deep architectures. They use 100-layer networks and measure output-feature rank across hidden layers.
- Experimental design: The experiments assess the potential of network structures and activation functions to scale to deep architectures using numerical output-feature rank.The rank is motivated by Theorem 3.
- Synthetic setup: 100-layer networks are evaluated on synthetic data generated from a normalized Erdős-Rényi graph and feature matrix.The graph is G(1000, 0.01), and each network layer has 128 output channels.
- Synthetic setup: The synthetic graph is an Erdős-Rényi G(1000, 0.01) graph with independently sampled edges.The edge probability is p = 0.01.
- Comparisons: Figures 4 and 5 compare column ranks across activation functions and architectures, respectively.Figure 4 holds architecture fixed, while Figure 5 holds activation function fixed.
Appendix V: Experiment Settings and Hyperparameters
The experiments compare methods under public-split settings and report results with and without validation. Hyperparameters are searched computationally, but hardware limits constrain the depth and width tested.
- Evaluation settings: The experiments compare against cited best results, including methods evaluated with validation and methods that did not use validation originally.The paper notes that some reproduced results may improve without validation and uses their best reported results.
- Search and implementation: Hyperparameters are searched using Bayesian optimization on compute clusters with mixed-precision acceleration.Experiments use NVIDIA GPUs and the NVIDIA Apex AMP plugin for PyTorch.
- Search and implementation: Smaller training sets call for larger dropout probabilities and longer early stopping.This is given as an experimental tuning guideline.
- Hardware boundary: Current GPUs cannot afford deeper and wider structures, although performance improves as network size increases.The paper expects more advanced devices to enable larger structures.