Research map / Graph learning / GNN architectures
On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives excess-risk upper and lower bounds for SGD (tail-averaged) and ridge regression in one-layer and linearized multi-layer GNNs, linking them via spectral decay to show SGD favors power-law graphs and ridge favors regular graphs.
Problem
How graph structure affects the generalization (excess risk) of learning algorithms such as SGD and ridge regression in GNNs under noisy (generalization) regime, which prior convergence-only theory in the interpolation regime did not address.
Approach
Extends the learning-theory excess-risk bias-variance profiles (fourth-moment / tail-averaged SGD and ridge analyses) to GNN aggregation spaces M = G∘X, then uses a power-law vs. exponential-decay eigenspectrum model to compare SGD and ridge across graph structures; also shows stacking linear GNN layers makes the eigenspectrum decay faster (non-isotropic), reinterpreting over-smoothing.
Key results
- Theory: SGD's excess-risk upper bound is at most a constant times Ridge's lower bound on power-law graphs (large beta), while Ridge is at most a constant times SGD on regular graphs (small beta).
- Empirically on synthetic Barabasi-Albert power-law graphs, SGD outperforms Ridge, while Ridge excels on regular graphs, matching theory.
- Proposition: stacking GNN layers increases the eigenvalue ratio across directions, so the aggregation spectrum decays faster, giving a non-isotropic effect that can help or hurt depending on ground-truth alignment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SGD instead of Ridge regression | One-layer GNN · Power-law graph | excess risk | Helped |
| Use Ridge regression instead of SGD | One-layer GNN · Regular graph | excess risk | Helped |
| Add GNN layers when the ground truth is concentrated in the tail eigenspace | Multi-layer linear GNN · Power-law graph with tail-eigenspace ground truth | excess risk | Hurt |
| Add GNN layers when the ground truth is concentrated in the head eigenspace | Multi-layer linear GNN · Power-law graph with head-eigenspace ground truth | excess risk | Helped |
Surprising findings
- Adding GNN layers can reduce excess risk when the ground truth lies in the head eigenspace, challenging the view that more layers always cause over-smoothing harm.
- The power-law vs. regular comparison reverses the usual intuition that ridge is always the safer choice; SGD is preferred on power-law graphs.
Limitations
- Analysis restricted to one-layer or linearized GNNs with ReLU readout; multi-layer nonlinear GNNs not covered.
- Power-law eigenspectrum is an assumed model mu_i = 1/i^beta rather than derived from real graphs; theorems use 'large enough beta' conditions.
- Empirical validation uses only synthetic graphs with generated ground truth aligned to the spectrum; no real-world benchmarks.
Experimental setup
Datasets: synthetic Barabasi-Albert graphs with Gaussian node features (dimension 200) synthetic regular graphs
Benchmarks: synthetic power-law (Barabasi-Albert) and regular graphs
Metrics: excess risk
Baselines: SGD Ridge regression
Builds on: tail-averaged SGD analysis (Bach & Moulines / Jain et al.) excess risk landscape of ReLU regression SGCN
Closest papers by meaning
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.92)
- Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? (NeurIPS 2023 · similarity 0.92)
- Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects (ICLR 2026 · similarity 0.91)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.91)
- Learning Latent Graph Structures and their Uncertainty (ICML 2025 · similarity 0.90)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.