REVIEW 12 cited by
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Graph Neural Networks (graph NNs) are a promising deep learning approach for analyzing graph-structured data. However, it is known that they do not improve (or sometimes worsen) their predictive performance as we pile up many layers and add non-lineality. To tackle this problem, we investigate the expressive power of graph NNs via their asymptotic behaviors as the layer size tends to infinity. Our strategy is to generalize the forward propagation of a Graph Convolutional Network (GCN), which is a popular graph NN variant, as a specific dynamical system. In the case of a GCN, we show that when its weights satisfy the conditions determined by the spectra of the (augmented) normalized Laplacian, its output exponentially approaches the set of signals that carry information of the connected components and node degrees only for distinguishing nodes. Our theory enables us to relate the expressive power of GCNs with the topological information of the underlying graphs inherent in the graph spectra. To demonstrate this, we characterize the asymptotic behavior of GCNs on the Erd\H{o}s -- R\'{e}nyi graph. We show that when the Erd\H{o}s -- R\'{e}nyi graph is sufficiently dense and large, a broad range of GCNs on it suffers from the "information loss" in the limit of infinite layers with high probability. Based on the theory, we provide a principled guideline for weight normalization of graph NNs. We experimentally confirm that the proposed weight scaling enhances the predictive performance of GCNs in real data. Code is available at https://github.com/delta2323/gnn-asymptotics.
Forward citations
Cited by 12 Pith papers
-
Distance-Preserving Embeddings in Inhomogeneous Random Graphs
On supercritical inhomogeneous random graphs, multi-scale landmark embeddings achieve (1±ε)-distortion of shortest paths at dimension Ω(n^{1-ε} log n), far below worst-case, with universal kernel extensions and transf...
-
Towards Fair Graph Prompting: A Dual-Prompt Mechanism for Mitigating Attribute and Structural Bias
ADPrompt adds per-node feature gating and layer-wise edge message calibration to frozen pre-trained GNNs, reducing attribute and structural bias while keeping node-classification accuracy competitive.
-
GKNet: Graph-based Keypoints Network for Monocular Pose Estimation of Non-cooperative Spacecraft
A graph-convolution branch fused into a UNet heatmap detector reduces keypoint error for monocular spacecraft pose estimation, with the largest gains on symmetric and occluded targets in a new synthetic dataset.
-
Effects of relational graph modularity and depth on the learning performance of neural networks
Community-structured sparse relational graphs improve 5-layer CIFAR-10 accuracy over fully connected baselines, but the advantage reverses at 8 layers due to over-smoothing.
-
Player-Team Heterogeneous Interaction Graph Transformer for Soccer Outcome Prediction
HIGFormer predicts soccer match outcomes by jointly modeling player-player event interactions and team-team historical win rates with a heterogeneous graph transformer and graph convolution network.
-
Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification
Training a two-hidden-layer GCN with jumping connections and layer-wise edge pruning nearly matches the best achievable error in a class of hierarchical target functions, with shallow layers needing more conservative ...
-
Towards Efficient Few-shot Graph Neural Architecture Search via Partitioning Gradient Contribution
GC splits a graph supernet into sub-supernets by grouping modules with similar gradient contributions, and UGAS searches combined MPNN and graph transformer architectures; the searched GNNs beat several baselines.
-
From Diffusion to Reaction-Diffusion: A Dynamical-Systems View of Oversmoothing in Hypergraph Neural Networks
Hypergraph diffusion provably collapses node representations, and a reaction term that exactly cancels diffusion dissipation keeps a designed transverse energy level nonzero in Hypergraph Neural Reaction–Diffusion (HNRD).
-
GITO: Graph-Informed Transformer Operator for Learning Complex Partial Differential Equations
GITO, a graph-informed transformer operator, reports lower relative L2 errors than existing transformer-based neural operators on Navier-Stokes, heat conduction, and airfoil benchmark datasets.
-
Rethinking Over-Smoothing in Graph Neural Networks: A Perspective from Anderson Localization
A single-author preprint re-frames GNN over-smoothing as Anderson localization, defining a participation-degree metric and proposing degree-dependent edge reweighting as mitigation, without proof or experiments.
-
Comment on "A Note on Over-Smoothing for Graph Neural Networks"
The authors show exponential decay of Dirichlet energy for GNNs with Leaky-ReLU and polynomial filters, but the proof relies on unverified spectral inequalities.
-
Graph Neural Network Approach to Predicting Magnetization in Quasi-One-Dimensional Ising Systems
A GCN+Set2Set+MLP model trained on 80 Monte Carlo datasets predicts magnetization curves of quasi-1D Ising graphs, with test errors between E=0.045 and E=0.389.
Discussion (0). Sign in to comment.