Towards Deeper Graph Neural Networks

Meng Liu; Hongyang Gao; Shuiwang Ji

Source-linked AI summary

Towards Deeper Graph Neural Networks

Meng Liu, Hongyang Gao, Shuiwang Ji

arXiv:2007.09296v1Jul 18, 2020cs.LGstat.ML

TL;DR

Graph neural networks need larger receptive fields than one-hop aggregation provides, yet deeper graph convolutions often degrade as representations become overly similar. The paper separates transformation from propagation, analyzes the resulting deep models theoretically and empirically, and proposes DAGNN, which adaptively uses large receptive fields and outperforms baselines across several dataset types.

Problem
Graph convolutions aggregate one-hop neighborhoods, while deeper stacking needed for larger receptive fields can cause representations from different classes to become indistinguishable.
Method
The paper analyzes deep GCN degradation, decouples representation transformation from propagation, and proposes DAGNN to adaptively incorporate large-receptive-field information.
Results
DAGNN outperforms representative baselines across citation, co-authorship, and co-purchase datasets, including 4.6%, 3.0%, and 3.0% improvements over GCN on randomly split Cora, CiteSeer, and PubMed.
Takeaways & Limitations
Separating transformation from propagation enables deeper models to use large receptive fields, while adaptive local-global aggregation produces more discriminative node representations.
Takeaways & Limitations
The analysis identifies over-smoothing as performance-relevant only for extremely large receptive fields and discusses dependence on graph connectivity and initial features.

Abstract

from arXiv · show

Graph neural networks have shown significant success in the field of graph representation learning. Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Nevertheless, one layer of these neighborhood aggregation methods only consider immediate neighbors, and the performance decreases when going deeper to enable larger receptive fields. Several recent studies attribute this performance deterioration to the over-smoothing issue, which states that repeated propagation makes node representations of different classes indistinguishable. In this work, we study this observation systematically and develop new insights towards deeper graph neural networks. First, we provide a systematical analysis on this issue and argue that the key factor compromising the performance significantly is the entanglement of representation transformation and propagation in current graph convolution operations. After decoupling these two operations, deeper graph neural networks can be used to learn graph node representations from larger receptive fields. We further provide a theoretical analysis of the above observation when building very deep models, which can serve as a rigorous and gentle description of the over-smoothing issue. Based on our theoretical and empirical analysis, we propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields. A set of experiments on citation, co-authorship, and co-purchase datasets have confirmed our analysis and insights and demonstrated the superiority of our proposed methods.

1 INTRODUCTION

Graph neural networks achieve broad success, but conventional graph convolutions struggle when deeper layers are used to obtain larger receptive fields. This work attributes the degradation primarily to entangled transformation and propagation, then proposes DAGNN to adaptively use large receptive fields.

Graph neural networks have achieved success in node classification, graph classification, and link prediction across many graph applications.
Single-layer graph convolutions aggregate information from local neighborhoods, limiting the receptive field to immediate neighbors.
Stacking graph convolution layers causes performance degradation, which the paper primarily attributes to entangled representation transformation and propagation.
Decoupling transformation from propagation enables deeper graph neural networks to learn representations from larger receptive fields without performance deterioration.
DAGNN adaptively incorporates information from large receptive fields, and experiments on citation, co-authorship, and co-purchase datasets demonstrate its superiority.

2 BACKGROUND AND RELATED WORKS

Graph convolutional networks learn node representations by aggregating neighborhood information and applying transformations, but deeper stacking is needed for multi-hop context and can trigger over-smoothing. Related work therefore examines smoothing, spectral filtering, and methods for extending receptive fields under limited supervision.

A graph is defined as G = (V, E), with nodes V, edges E, and node and edge counts n = |V| and m = |E|.
The adjacency matrix A encodes graph topology, the degree matrix D contains node degrees, and each node feature vector x_i is stored in feature matrix X.
Graph convolutions use neighborhood aggregation to propagate neighbor representations and apply transformations; GCN, GraphSAGE, GAT, and GIN instantiate this framework differently.
GCN propagates neighboring representations and then applies a nonlinear transformation, allowing labeled-node information to reach unlabeled neighbors.
One GCN layer covers one-hop neighborhoods, so multiple layers are required for multi-hop information but may make representations from different classes indistinguishable through over-smoothing.
Over-smoothing concerns motivate limited receptive fields, although long-range dependencies and broader propagation remain important for peripheral nodes and graphs with few labeled training nodes.

3 EMPIRICAL AND THEORETICAL ANALYSIS OF DEEP GNNS

The analysis finds that deep GCN degradation is primarily linked to entangling representation transformation with propagation, while over-smoothing becomes decisive only at extremely large receptive fields. Decoupling these operations enables deeper models to preserve distinguishable representations and use larger receptive fields.

3.1 Quantitative Metric for Smoothness: A smoothness metric and t-SNE visualization are used to systematically investigate why stacking GCN layers degrades performance.The metric measures representation similarity, while t-SNE visualizes class separability.
3.2 Why Deeper GNNs Fail?: On Cora, test accuracy rises initially but degrades dramatically from 3 GCN layers, while representations from 6 layers become difficult to separate.This degradation is accompanied by reduced discriminative power in the t-SNE visualization.
3.2 Why Deeper GNNs Fail?: The authors argue that entangling representation transformation with propagation is the prominent factor compromising deep GNN performance.The entanglement ties transformation parameters to receptive-field size, potentially making large-receptive-field models harder to train.
3.2 Why Deeper GNNs Fail?: After decoupling transformation and propagation, deeper models can exploit larger receptive fields without performance degradation until over-smoothing appears at extremely large scales.On Cora, performance begins to suffer at about 75 hops, whereas 50-hop representations remain distinguishable.
3.3 Theoretical Analysis of Very Deep Models: The theoretical analysis shows that infinite propagation converges to representations that are linearly inseparable, making over-smoothing inevitable in very deep models.The practical impact depends importantly on convergence speed, which is governed by propagation-matrix eigenvalues.

4 DEEP ADAPTIVE GRAPH NEURAL NETWORK

DAGNN separates feature transformation from propagation and adaptively combines information from local and global neighborhoods. This design supports large, adaptive receptive fields without adding more trainable parameters for the larger neighborhood.

Architecture: DAGNN decouples representation transformation from propagation and adaptively balances information from local and global neighborhoods for each node.The model uses a shared MLP for transformation, propagation across multiple hops, and learnable retainment scores for adaptive adjustment.
Propagation: The transformed features are propagated across k-hop neighborhoods, with k controlling model depth and the reachable receptive field.The propagation uses symmetrical normalization, and H ℓ represents information gathered from nodes ℓ hops away.
Adaptive adjustment: Adaptive adjustment selects suitable combinations of local and global neighborhood information because a fixed propagation depth may be insufficient or overly broad.Small receptive fields may miss sufficient information, while larger ones include more global information; retainment scores adjust this balance per node.
Efficiency: DAGNN derives large neighborhoods without introducing more trainable parameters and becomes computationally efficient by transforming representations into a low-dimensional space early.The sequential computation of propagated representations has stated time complexity O(n2c), while the implementation discusses the cost of calculating the propagation matrix.
Training objective: The model uses final representations directly for prediction and trains them with cross-entropy over labeled nodes.The labeled-node set and class-indicator matrix define the supervised loss.

5 EXPERIMENTAL STUDIES

Experiments evaluate DAGNN on seven citation, co-authorship, and co-purchase datasets under multiple data-splitting and training-size settings. DAGNN achieves strong performance across datasets, with especially large gains when labeled training data are scarce, while depth behavior varies with graph structure.

Experimental setup: DAGNN is evaluated on seven citation, co-authorship, and co-purchase datasets for semi-supervised node classification.The datasets are Cora, CiteSeer, PubMed, Coauthor CS, Coauthor Physics, Amazon Computers, and Amazon Photo.
Overall results: On citation datasets, DAGNN outperforms representative baselines and improves over GCN by 4.6%, 3.0%, and 3.0% on randomly split Cora, CiteSeer, and PubMed.The citation experiments use fixed and random splits, with average test accuracy computed over 100 runs.
Overall results: On co-authorship and co-purchase datasets, DAGNN improves over current state-of-the-art models by 1.5%, 1.0%, 1.0%, and 0.6% on four datasets.The reported datasets are Coauthor CS, Coauthor Physics, Amazon Computers, and Amazon Photo; the paper also reports an 11% average error-rate reduction.
Training set sizes: 23.7% is DAGNN’s improvement over GCN when using only one training node per class on Cora.DAGNN’s advantage increases as the number of training nodes decreases, which the paper connects to large receptive fields propagating signals to distant nodes.
Depth studies: For citation and co-authorship datasets, very deep DAGNN models maintain stable or slightly decreasing performance, whereas co-purchase performance decreases obviously with depth.The paper attributes the co-purchase behavior to higher edge density, which can make node representations indistinguishable after fewer propagation iterations.

6 CONCLUSION

The paper identifies entanglement between transformation and propagation as a key factor in deep GNN performance deterioration and proposes decoupling them. DAGNN then uses adaptive receptive fields and achieves better performance than state-of-the-art models, especially with limited training samples.

Conclusion: The paper argues that entanglement of representation transformation and propagation compromises the performance of deep graph neural networks.It frames this issue as the central performance-deterioration problem addressed by the work.
Conclusion: Decoupling transformation from propagation enables deep graph neural networks to leverage large receptive fields without performance deterioration.The paper also provides a theoretical analysis describing the over-smoothing issue in very deep models.
Conclusion: DAGNN captures information from large and adaptive receptive fields and outperforms current state-of-the-art models by significant margins, especially when training samples are limited.The conclusion presents these comprehensive experimental results as evidence of DAGNN’s superiority.

A APPENDIX

The appendix provides additional material supporting the paper’s insights and experimental results. It includes further quantitative and qualitative results, proofs, and dataset details.

Appendix contents: The appendix contains additional quantitative results and qualitative visualizations on more datasets supporting the paper’s insights.It also includes proofs of lemmas and detailed dataset descriptions.

A.1 Test Accuracy and Smoothness Metric Value of GCNs

Figure 7 examines how varying GCN depth affects test accuracy and the smoothness of node representations on CiteSeer and PubMed.

Figure 7 reports test accuracy across different numbers of GCN layers for CiteSeer and PubMed.
The same figure reports the smoothness metric value of node representations across GCN depths.
The smoothness metric value of the original data is обозначated as “Init.”

A.2 Test Accuracy and Smoothness Metric Value of Models as Eq.(6)

Figure 8 evaluates test accuracy and representation smoothness as the number of layers increases in models defined by Eq.(6) on CiteSeer and PubMed. The results indicate that decoupling transformation from propagation permits deeper models without performance degradation.

Figure 8 reports test accuracy for different layer counts in models defined by Eq.(6) on CiteSeer and PubMed.
After transformation and propagation are decoupled, deeper models can be applied without suffering from performance degradation.
Figure 8 also reports the smoothness metric value of node representations across those layer counts.

A.3 Visualization of Representations Derived by GCNs

Figures 9 and 10 visualize node representations produced by different numbers of GCN layers on CiteSeer and PubMed. With several layers, the representations become indistinguishable.

Figures 9 and 10 show t-SNE visualizations of node representations derived from different GCN layer counts.
Figure 9 presents the visualization for CiteSeer, while Figure 10 presents the visualization for PubMed.
The node representations become indistinguishable when several GCN layers are deployed.

A.4 Visualization of Representations Derived by Models as Eq.(6)

Figures 11 and 12 visualize representations from Eq.(6)-based models with different layer counts on CiteSeer and PubMed. After decoupling transformation and propagation, distinguishability persists at a 50-hop receptive field but is affected at an extremely large 200-hop field.

Figures 11 and 12 show representations from Eq.(6)-based models with different layer counts on CiteSeer and PubMed.
After removing transformation–propagation entanglement, a large receptive field such as 50-hop still generates distinguishable node representations.
The over-smoothing issue affects distinguishability only when the receptive field becomes extremely large, such as 200-hop.

A.5 Proof for Lemma 3.3

The proof establishes spectral properties of the normalized adjacency matrices bA⊕ and bA⊙, showing that they share eigenvalues and have a dominant eigenvalue under graph connectivity assumptions.

Eigenvalue equivalence: bA⊕ and bA⊙ have the same eigenvalues, established by transforming their left and right eigenvector equations with degree-normalization factors.The corresponding eigenvectors are related through multiplication by eD^−1/2 and eD^1/2.
Eigenvectors: The eigenvectors associated with eigenvalue 1 are derived explicitly for bA⊕ and bA⊙ using row normalization, symmetry, and the eigenvector transformation lemma.The proof identifies e^T as a right eigenvector of bA⊕ and uses symmetry to relate left and right eigenvectors of bA⊙.
Spectral bounds: bA⊕ has eigenvalue 1 because each row sums to 1, while all eigenvalues satisfy |λ| ≤ 1.An eigenvalue with magnitude greater than 1 would make bA⊕^k v grow exponentially, yielding a contradiction.
Primitive-matrix argument: For a connected graph with self-loops, bA⊕ is a non-negative primitive matrix, so Perron–Frobenius theory gives a unique dominant eigenvalue 1 and |λ| < 1 for all others.Connectivity supplies eventual positive reachability, while self-loops ensure a suitable power is simultaneously positive.