Technical Summary: Revisiting Pre-Propagation GNNs

1. Problem Statement

Pre-propagation Graph Neural Networks (PP-GNNs) offer a scalable alternative to traditional Message-Passing GNNs (MP-GNNs) by decoupling feature propagation from transformation. In PP-GNNs, graph diffusion is performed once as a preprocessing step to generate multi-hop features, allowing the subsequent training phase to utilize dense, mini-batchable transformations without inter-node dependencies. While this design improves efficiency and matches modern hardware accelerators optimized for dense computation, PP-GNNs exhibit a significant performance gap compared to MP-GNNs, particularly on heterophilic graphs (where connected nodes often have different labels).

The authors identify two primary design limitations contributing to this gap:

1. Diffusion Operator Limitations: Standard PP-GNNs rely on simple operators (e.g., normalized adjacency, random walks) that act as low-pass filters. These are suboptimal for heterophilic graphs, which often require higher-frequency or band-pass components. Furthermore, standard monomial diffusion bases (powers of the diffusion matrix) are often poorly conditioned and yield highly correlated features, limiting approximation quality.
2. One-Shot Propagation: PP-GNNs propagate raw input features only once. Unlike MP-GNNs, which iteratively interleave propagation with nonlinear transformations to refine task-adapted representations, PP-GNNs cannot update the propagated features based on evolving hidden states during training.

2. Methodology

The paper proposes a suite of improvements to close the accuracy gap while preserving the training efficiency of PP-GNNs. The approach consists of three main components:

A. Robust Diffusion Operators

To address the limitations of standard diffusion bases, the authors introduce two orthogonal, better-conditioned diffusion bases for the preprocessing stage:

• Jacobi-Polynomial Basis: Instead of using monomials $\Phi^k$, the authors utilize Jacobi polynomials $P_k^{(\alpha, \beta)}(\tilde{L})$, where $\tilde{L}$ is a shifted Laplacian. The parameters $(\alpha, \beta)$ are calibrated in a single, lightweight preprocessing step based on the graph's spectral density (using stochastic Chebyshev moments) to allocate resolution where the graph spectrum concentrates. This creates an orthogonal basis that reduces feature correlation.
• Lanczos/Krylov-Subspace Basis: To capture channel-specific spectral content, the authors construct a Krylov subspace for each feature channel using the Lanczos iteration. This generates a set of Ritz vectors and values that form an orthogonal, signal-aligned diffusion bank. This method decomposes features into decorrelated components, providing a more stable coordinate system for aggregation under a fixed hop budget.

B. Hidden-State Re-Propagation (HRP)

To overcome the "one-shot" limitation, the authors introduce Hidden-State Re-Propagation (HRP). This mechanism recouples feature propagation with learned representations:

• Mechanism: Training is split into multiple stages. At the end of each stage, the best hidden representation (before the final output projection) is selected and detached. This hidden state is then re-propagated through the diffusion operator to generate a new set of multi-hop features.
• Integration: These re-propagated hidden features are blended with the original precomputed features to form the input for the next training stage.
• Distinction: The authors explicitly contrast HRP with label-based reuse (e.g., using logits or one-hot labels as features). They argue that re-propagating high-dimensional hidden states carries complementary relational information beyond class probabilities, whereas label propagation can introduce shortcuts or noise, especially on heterophilic graphs.

C. RNN-Based Hop Aggregator

As an optional efficiency improvement, the authors propose replacing Multi-Head Attention (MHA) aggregators (used in models like HOGA) with a Recurrent Neural Network (RNN) to process the sequence of hop features. This reduces computational overhead and memory usage while maintaining comparable accuracy.

3. Key Contributions

1. Adaptation of Robust Diffusion Bases: The paper adapts Jacobi-polynomial and Krylov-subspace diffusion bases to the PP-GNN preprocessing regime. These bases improve the conditioning of precomputed features and enable richer spectral responses under a fixed hop budget.
2. Hidden-State Re-Propagation (HRP): A lightweight mechanism that iteratively refines PP-GNNs by re-propagating intermediate hidden states, effectively bridging the gap between one-shot propagation and iterative message passing without sacrificing scalability.
3. Efficient Aggregation: An RNN-based hop aggregator that serves as a computationally cheaper alternative to attention-based aggregation.
4. Empirical Validation: Extensive experiments across 12 datasets (6 heterophilic, 6 homophilic) and 4 PP-GNN backbones (SIGN, HOGA, GAMLP, GARNN).

4. Experimental Results

The proposed methods were evaluated on both heterophilic and homophilic benchmarks:

• Heterophilic Graphs: On six heterophilic datasets (including Roman-Empire, Minesweeper, and Pokec), the enhanced PP-GNNs significantly narrowed the accuracy gap with MP-GNNs.
  • The average test accuracy improvement over baseline PP-GNNs was +2.18% on heterophilic datasets.
  • The enhanced models outperformed strong MP-GNN baselines (e.g., GraphSAGE, GAT) on 4 out of 6 heterophilic graphs.
  • On the Roman-Empire dataset, the accuracy gap between MP-GNNs and PP-GNNs was reduced from ~11% to near parity.
• Homophilic Graphs: The improvements also transferred to homophilic datasets (e.g., Cora, Citeseer, OGBN-Arxiv), with an average improvement of +1.96%. The enhanced PP-GNNs outperformed MP-GNNs on 3 out of 6 homophilic datasets.
• Ablation Studies:
  • Robust diffusion operators alone provided an average gain of ~2.09% (validation) / 1.99% (test).
  • HRP provided an additional gain of ~1.54% (validation) / 1.61% (test).
  • HRP significantly outperformed label-as-input and label propagation strategies, particularly on heterophilic graphs where label smoothness is low.
• Efficiency:
  • The Lanczos operator adds a cost comparable to a few standard diffusion steps.
  • HRP introduces a small number of stages (typically < 4, max 7), with the re-propagation diffusion accounting for only ~2% of total training time.
  • The RNN-based aggregator (GARNN) achieved similar accuracy to HOGA but with significantly reduced training time (2.4s/epoch vs. 8.4s/epoch on Pokec).
  • Overall, the enhanced PP-GNNs achieve a favorable accuracy-runtime trade-off, moving the PP-GNN family closer to the Pareto frontier of MP-GNNs.

5. Significance and Claims

The paper claims that the proposed framework successfully addresses the expressivity limitations of Pre-Propagation GNNs without reverting to the computational bottlenecks of iterative message passing.

• Scalability vs. Expressivity: The work demonstrates that PP-GNNs do not inherently sacrifice expressivity for scalability; rather, the gap stems from suboptimal diffusion operators and the lack of iterative refinement. By using robust diffusion bases and HRP, PP-GNNs can match or exceed the accuracy of MP-GNNs while retaining their training efficiency and mini-batch capabilities.
• General Applicability: While motivated by the challenges of heterophily, the methods are shown to be beneficial across both heterophilic and homophilic graph structures.
• Practical Impact: The approach offers a pathway to deploy highly scalable GNNs on large-scale graphs (e.g., social networks, recommendation systems) with performance competitive to state-of-the-art message-passing models, potentially reducing computational costs and energy consumption for large-scale graph learning.

The authors maintain a modest stance, noting that while the methods improve performance, they do not introduce new data modalities or inherently prevent downstream ethical risks associated with graph learning (such as bias amplification), emphasizing the need for responsible ML practices in deployment.