Adaptive Initial Residual Connections for GNNs with Theoretical Guarantees

AI summary

Overview

• Research area: Graph neural networks (GNNs), specifically message passing architectures, residual connections, and the oversmoothing problem in deep graph networks.
• Technical level: Advanced. The paper is built on spectral graph theory (normalized Laplacian, eigenvalues of the normalized adjacency matrix), singular value decomposition, Neumann series, and Dirichlet energy. The theoretical core will be difficult for readers without linear algebra and spectral graph theory background, although the high-level motivation and the PageRank heuristic are accessible.
• Scope: The paper proposes and analyzes an adaptive initial residual connection (IRC) scheme in which each node has its own residual strength, proves that the Dirichlet energy of the embeddings stays bounded away from zero, and reports experiments showing gains over standard and state-of-the-art message passing, especially on heterophilic graphs.

What This Paper Is About

Deep GNNs suffer from oversmoothing: as layers stack up, repeated neighborhood averaging makes node embeddings increasingly similar until they can no longer be distinguished. Residual connections help by adding either the previous layer's embeddings (residual connections, RC) or the original input embeddings (initial residual connections, IRC) back into each layer's update. Prior IRC work generally uses a single residual strength shared by all nodes, a setting the authors call static IRC. This paper studies adaptive IRC, where every node gets a personalized residual strength, and asks two questions: can this be proven to prevent oversmoothing, and does it improve accuracy in practice.

Key Contributions

1. Theoretical guarantee against oversmoothing. The authors prove that under adaptive IRC the Dirichlet energy of the node embeddings remains bounded away from zero, so the embeddings retain discriminative power even in deep architectures. The abstract claims this is the first theoretical guarantee of its kind not only for the adaptive setting but also for static residual connections with activation functions.
2. Extension of prior static IRC theory. As a special case, the paper proves that static IRC with activation functions mitigates oversmoothing, extending the earlier result of Scholkemper et al. (2025), which considered only the linear case without activation functions.
3. Rank preservation. In a simplified version of adaptive IRC (no activation function, no linear transformation), the authors show the system stabilizes and the embedding matrix keeps full rank throughout propagation, so the embedding space never collapses.
4. A cheaper, non-learnable variant. To cut time complexity, the authors replace learned residual strengths with a heuristic PageRank-based assignment: a higher fixed residual strength for a small fraction of top-ranked nodes and a lower fixed value for the rest. This variant reportedly performs as well as the fully learnable one.

Main Findings

• Adaptive IRC avoids oversmoothing. The abstract states that the Dirichlet energy of the embeddings remains bounded away from zero, meaning embeddings keep their discriminative power with depth. The full statement of Theorem 2 (the main energy result) is truncated in the provided content at the assumption that the initial embedding energy is strictly positive, i.e. E(H^(0)) > 0, and a condition on the smallest non-zero singular values of a weight matrix.
• Rank is fully preserved. Theorem 1: for the simplified propagation rule H^(ℓ+1) = Λ𝒜H^(ℓ) + (I − Λ)H^(0), the system stabilizes to lim_{ℓ→∞} H^(ℓ) = (I − Λ𝒜)^(−1)(I − Λ)H^(0), and rank(H^(ℓ)) = rank(H^(0)) for all ℓ ∈ ℕ. The proof uses the fact that ρ(Λ𝒜) ≤ ‖Λ𝒜‖₂ ≤ ‖Λ‖₂‖𝒜‖₂ < 1, which guarantees convergence of the Neumann series ∑(Λ𝒜)^i = (I − Λ𝒜)^(−1).
• Energy lower bound through aggregation. Corollary 1 states that for X whose rows lie in col(W) and whose columns lie in row(𝒜), E(Λ𝒜XW) ≥ λ_min² σ_r²(𝒜) σ_r²(W) E(X), where σ_r denotes the smallest non-zero singular value. This combines Lemma 1 (a lower bound for ‖fW‖₂ in terms of σ_r(W)) and Lemma 2 (a lower bound for ‖Λ𝒜f‖₂ in terms of λ_min σ_r(𝒜)).
• Activation functions preserve energy up to a constant. Property 1 requires E(σ(f)) ≥ α²E(f) for some α > 0. Lemma 3 proves that leaky ReLU with negative slope 0 < α < 1 satisfies this, via a four-case sign analysis of the normalized inputs across each edge.
• Rank alone is an unreliable diagnostic. The authors argue that numerical rank may remain full even in oversmoothing regimes because of infinitesimal differences, while the effective rank collapses. They therefore use Dirichlet energy, a continuous quantifier, as the more robust measure (the paper also points to mean average distance, spectral rank, and normalized node similarities as alternative equivalent measures).
• Empirical claim. The abstract reports that extensive experiments show the adaptive approach outperforms standard and state-of-the-art message passing mechanisms, especially on heterophilic graphs. The provided content does not report dataset names, dataset sizes, baseline numbers, or accuracy figures, so no specific empirical values can be stated here.
• Reduced complexity. Compared with the closely related adaptive scheme of Zhang et al. (2023), the authors state their personalized residual strengths are shared across layers, reducing the number of learnable parameters, and that the PageRank-based heuristic reduces complexity further.

Methodology in Plain English

The proposed update rule mixes two things at every layer: a transformed aggregation of the current embeddings from neighbors, and a transformed copy of each node's original input features. The balance between them is set by a diagonal matrix Λ whose entries λ_i lie in (0, 1). If Λ equals the identity, the model reduces to vanilla GCN with no residual term; if Λ equals βI for some β in (0, 1), the static IRC model is recovered.

To make the residual strengths work for nodes the model has not seen during training, the authors do not learn one λ per node. Instead they compute Λ = diag(σ(H^(0)W_att)), where W_att is a d₀ × 1 weight matrix and σ is a sigmoid. This applies a fully connected layer to each node's initial features, producing residual strengths between 0 and 1 from shared, input-dependent weights.

The theoretical work proceeds in stages. First, the authors strip away activations and weight matrices to study a pure averaging recursion, and show via matrix power series and the spectral radius condition that it converges and never loses rank. Second, they build up the general case using two technical lemmas that lower-bound how much a weight matrix and the residual-weighted normalized adjacency matrix can shrink a vector, combine them in a corollary about Dirichlet energy, and add a property (satisfied by leaky ReLU) that bounds how much an activation can shrink energy. A further assumption, Property 2, requires tr(XᵀℒY) ≥ 0, meaning the aggregated embeddings X = Λ𝒜H^(ℓ)W^(ℓ) and the initial-feature embeddings Y = (I − Λ)H^(0)Θ^(ℓ) vary in aligned directions across edges, consistent with the homophily assumption.

The motivation for the node-specific retention of initial features comes from the Friedkin-Johnsen opinion dynamics model. For efficiency, the PageRank variant ranks nodes and assigns a higher fixed residual strength to a small fraction of top-ranked nodes and a lower fixed value to the rest.

Why This Matters

Impact on research. The paper turns an experimentally observed behavior into a provable property. Adaptive IRC had previously been studied experimentally (by Zhang et al. 2023, using a more complex variant); here it comes with a Dirichlet energy guarantee. The result also covers static IRC with activation functions, extending Scholkemper et al. (2025), and gives a rank-preservation result for the simplified setting. That gives the community a theoretical reason to prefer adaptive residual strengths over a single shared hyperparameter.

Real-world applications. The introduction lists domains where GNNs are already deployed and where deeper, non-oversmoothing architectures would matter:

• Traffic prediction in transportation systems
• Pandemic analysis in public health
• Economic forecasting
• Social network analysis

Heterophilic graphs, where connected nodes tend to differ, are singled out as the setting where the adaptive approach performs especially well.

Industry relevance. The paper is framed around scalability as well as accuracy: personal residual strengths are shared across layers, and the PageRank heuristic removes the need to learn them at all while reportedly matching the learnable variant. For practitioners running GNNs at scale, that is the difference between a theoretical improvement and a deployable one, since the non-learnable variant avoids the added computational overhead of a learned residual path.

Future Directions

• Test the guarantee under weaker assumptions. The main theorem relies on the initial embedding energy being strictly positive, a lower bound involving smallest non-zero singular values, and Property 2 requiring tr(XᵀℒY) ≥ 0, which is tied to homophily. How the bound behaves on strongly heterophilic graphs, where that trace condition is harder to justify, is an open question the paper's own framing raises.
• Extend beyond initial residual connections. The authors deliberately focus on IRC. Whether the same style of Dirichlet energy guarantee carries over to general residual connections (RC) that mix in outputs from previous layers, and to layer-wise adaptive strengths as in Zhang et al. (2023), is not established here.
• Explore other heuristics and activation functions. PageRank is one centrality-based choice for the non-learnable variant. Whether other centrality measures do as well, and whether the energy guarantee extends to activation functions beyond those satisfying Property 1 (leaky ReLU is proven; ReLU and sigmoid are mentioned as examples of activations in the model but are not shown to satisfy the property in the provided content), are natural next steps.
• Compare against the wider family of depth-preserving designs. The related work lists JKNets, DAGNNs, R-SoftGraphAI, GODNF, and diffusion-based message passing. A systematic theoretical and empirical comparison with these under the same Dirichlet energy lens is not reported in the provided content.

Target Audience

• GNN theory researchers interested in oversmoothing, Dirichlet energy bounds, and rank-based analyses of message passing.
• Machine learning practitioners building deep graph models, particularly on heterophilic graphs, who want a residual scheme that is cheap to train.
• Readers of the residual-connection literature in graph learning, especially those following GCNII, Gasteiger et al., Scholkemper et al., and Zhang et al.
• Graduate students with a background in linear algebra and spectral graph theory; the paper's preliminary section builds up the Laplacian, normalized adjacency, SVD, and column/row space machinery from the ground up.

A note on completeness: the provided content is truncated partway through Theorem 2 and does not include the experimental setup, datasets, baselines, or numerical results. Any figures, dataset names, or benchmark values from the experiments are therefore not reported here.

Authors’ abstract

Message passing is the core operation in graph neural networks, where each node updates its embeddings by aggregating information from its neighbors. However, in deep architectures, this process often leads to diminished expressiveness. A popular solution is to use residual connections, where the input from the current (or initial) layer is added to aggregated neighbor information to preserve embeddings across layers. Following a recent line of research, we investigate an adaptive residual scheme in which different nodes have varying residual strengths. We prove that this approach prevents oversmoothing; particularly, we show that the Dirichlet energy of the embeddings remains bounded away from zero. This is the first theoretical guarantee not only for the adaptive setting, but also for static residual connections (where residual strengths are shared across nodes) with activation functions. Furthermore, extensive experiments show that this adaptive approach outperforms standard and state-of-the-art message passing mechanisms, especially on heterophilic graphs. To improve the time complexity of our approach, we introduce a variant in which residual strengths are not learned but instead set heuristically, a choice that performs as well as the learnable version.