Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation
Zichao Yue, Zhiru Zhang · 2026
Read Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation by Zichao Yue, Zhiru Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25111.txt.
Introduction
Zichao Yue and Zhiru Zhang revisit graph neural networks that propagate node features once, before training, instead of passing messages at every step. That shortcut makes training cheap and batch-friendly. It has lagged behind message-passing models, however, especially on graphs where neighbors tend to differ. The authors add sturdy diffusion operators for the preprocessing step and a few-shot scheme that re-propagates hidden states during training, closing the accuracy gap while keeping the speed advantage.
Catalog record
| CREATOR | Zichao Yue, Zhiru Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67749 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25111
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation Zichao Yue, Zhiru Zhang Abstract Pre-propagation graph neural networks (PP-GNNs) decouple node feature propagation from transformation: graph diffusion is performed once as preprocessing, and training reduces to dense per-node transformations. This design enables mini-batch training without inter-node dependencies, avoids repeated sparse matrix–matrix multiplications, and better matches modern accelerators optimized for dense compute. However, their expressivity remains unclear, and empirical results show a gap between PP-GNNs and their message-passing counterparts on commonly used graph benchmarks, especially heterophilic ones. In this paper, we propose a suite of robust graph diffusion operators for preprocessing and a few-shot hidden-state re-propagation scheme during training. Our methods improve the validation and test accuracy of PP-GNNs, enabling them to match the accuracy of message-passing GNNs while maintaining training efficiency. 1 Introduction The message-passing scheme ( 13 ) underlies most graph neural networks (GNNs), but its memory and computation costs grow exponentially with neighborhood expansion ( 14 ) , making large-scale training challenging. Prepropagation GNNs (PP-GNNs) have emerged as a scalable alternative ( 36 ; 10 ; 9 ; 39 ; 21 ; 4 ; 8 ; 40 ) by decoupling feature propagation from transformation. In PP-GNNs, node features are diffused over the graph once as a preprocessing step, and learning proceeds on the resulting diffused features via dense per-node transformations. This decoupling eliminates inter-node dependencies during training, making mini-batch optimization straightforward, avoiding repeated sparse matrix–matrix multiplications (SpMM), and better matching modern accelerators optimized for dense compute, while substantially improving efficiency and scalability compared to message-passing GNNs (MP-GNNs) ( 38 ) . Table 1 : Motivating accuracy gap between MP-GNNs and PP-GNNs on heterophilic benchmarks. Entries report mean test accuracy on roman-empire and ROC AUC on minesweeper . Model Minesweeper Roman-Empire MP-GNNs SAGE 93.51 \pm 0.57 85.74 \pm 0.67 GAT 93.91 \pm 0.35 88.75 \pm 0.41 DIR-GNN 87.05 \pm 0.69 91.23 \pm 0.32 PP-GNNs SIGN 90.71 \pm 0.56 80.01 \pm 0.50 HOGA 90.53 \pm 0.66 79.39 \pm 0.56 GAMLP 90.47 \pm 0.66 78.87 \pm 0.65 Best MP – Best PP gap 3.20 11.22 PP-GNNs show competitive performance on large graph benchmarks (e.g., OGB), which are predominantly homophilic graphs. However, recent theoretical study suggests the scalability advantage of PP-GNNs may come with a sacrifice in expressivity ( 3 ) . Empirically, we find this limitation is most pronounced on heterophilic graphs: as shown in Table 1 , the test accuracy gap between MP-GNNs and PP-GNNs can reach up to 11% on several heterophilic benchmarks. We hypothesize that two design aspects of PP-GNNs contribute to this gap: (i) diffusion operator limitations and (ii) one-shot feature propagation, and address them with more robust diffusion operators and hidden-state re-propagation (HRP). First, diffusion-operator limitations. A central design choice in PP-GNNs is the preprocessing diffusion operator that generates multi-hop features. Most existing PP-GNNs adopt simple operators—e.g., normalized adjacency or random-walk variants—whose spectral responses behave largely as low-pass graph filters ( 25 ; 12 ) , which can be suboptimal on heterophilic graphs that benefit from higher-frequency or band-pass components ( 6 ; 1 ) . In principle, combining hop features from multi-step diffusion (e.g., \{\Phi^{k}X\}_{k=0}^{K} ) enables richer spectral shaping; in practice, the hop budget K is typically kept small due to efficiency considerations and the oversmoothing issue ( 19 ) . Under such small K , the standard monomial diffusion basis induced by powers of \Phi can be poorly conditioned and yield highly correlated hop features, limiting approximation quality and destabilizing the learned hop combination. To address this, we construct better-conditioned diffusion bases using orthogonal-polynomial recurrences and Lanczos/Krylov subspace methods (Jacobi-polynomial and Krylov-subspace bases), which reduce approximation error under the same hop budget and improve the stability of hop aggregation ( 22 ; 34 ) . Second, one-shot propagation . Although PP-GNNs incorporate multi-hop information in preprocessing, this propagation is performed only once on the raw inputs and is not coupled to evolving hidden representations. Inspired by polynomial-filter GNNs like ChebNet ( 7 ) , where depth still increases expressivity even with large receptive fields per layer, we introduce hidden-state re-propagation to PP-GNNs, effectively adding additional rounds of graph filtering on task-adapted hidden states. A related idea is to reuse model predictions by treating logits—the learned soft labels—as additional node features ( 35 ; 39 ) . However, we empirically show that replacing hidden states with logits in the re-propagation step leads to a substantial accuracy drop, suggesting that re-propagated hidden representations carry complementary information beyond class probabilities. In practice, only a few hidden-state re-propagation rounds are needed for convergence, preserving the training efficiency and scalability of vanilla PP-GNNs. To summarize, we study how to close the accuracy gap of PP-GNNs and MP-GNNs, especially on heterophilic graphs, while preserving their training efficiency and scalability. Our approach improves PP-GNNs by (i) using more robust diffusion operators and (ii) lightweight recoupling of feature propagation with representation learning. While motivated by heterophily, we observe that these improvements also transfer to homophilic benchmarks, yielding gains on a majority of them. Our main contributions are as follows: • We adapt Jacobi-polynomial and Krylov-subspace diffusion bases to the preprocessing regime of PP-GNNs, improving the conditioning of precomputed hop features and enabling richer spectral responses under a fixed hop budget. • We introduce hidden-state re-propagation, a mechanism that recouples feature propagation with learned representations and outperforms label-based reuse. • Across 4 PP-GNNs and 12 datasets, our method boosts test accuracy by \mathbf{+2.18} avg on heterophilic ones and \mathbf{+1.96} avg on homophilic ones, outperforming MP-GNN baselines on \mathbf{7} out of 12 datasets. • Additionally, we explore an RNN-based hop aggregator as an efficient alternative to multi-head-attention-based aggregation, achieving comparable accuracy while significantly reducing end-to-end training time. 2 Preliminaries 2.1 Graph Notation Let G=(V,E) be a graph with |V|=n nodes and adjacency matrix A\in\mathbb{R}^{n\times n} . Let X\in\mathbb{R}^{n\times d} denote input node features and Y\in\{1,\dots,C\}^{n} node labels for a C -class node classification task. We use \mathcal{V}_{\text{tr}},\mathcal{V}_{\text{va}},\mathcal{V}_{\text{te}} to denote train/val/test node splits. Let D=\mathrm{diag}(d_{1},\dots,d_{n}) be the degree matrix with d_{i}=\sum_{j}A_{ij} . For a node i , \mathcal{N}(i) denotes its neighbor set. We write \sigma(\cdot) for a pointwise nonlinearity and \|\cdot\| for concatenation. 2.2 Graph Spectral Theory and Spectral Graph Filters For an undirected graph, the normalized Laplacian is L\;=\;I-D^{-1/2}AD^{-1/2}. (1) Since L is real symmetric, it admits an eigendecomposition L\;=\;U\Lambda U^{\top}, (2) where U=[u_{1},\dots,u_{n}] is orthonormal and \Lambda=\mathrm{diag}(\lambda_{1},\dots,\lambda_{n}) with 0=\lambda_{1}\leq\cdots\leq\lambda_{n}\leq 2 . Given a graph signal x\in\mathbb{R}^{n} (e.g., one feature channel of X ), its graph Fourier transform is \hat{x}=U^{\top}x and inverse is x=U\hat{x} . A spectral graph filter is defined by a scalar response function g:\mathbb{R}\to\mathbb{R} applied to the Laplacian spectrum: g(L)x\;=\;U\,g(\Lambda)\,U^{\top}x,\quad g(\Lambda)=\mathrm{diag}\big(g(\lambda_{1}),\dots,g(\lambda_{n})\big). (3) Intuitively, smaller eigenvalues correspond to smoother (low-frequency) components, while larger eigenvalues correspond to more oscillatory (high-frequency) components; g(\lambda) specifies how each frequency band is attenuated. In practice, explicit eigendecomposition can be avoided by approximating the matrix function g(L) directly as an operator on L , rather than evaluating g on individual eigenvalues. A common choice is a polynomial filter , which approximates g(L) by a degree- K polynomial in L : g(L)\;\approx\;\sum_{k=0}^{K}\alpha_{k}\,p_{k}(L), (4) 2.3 From Spectral Filters to Message-Passing GNNs Spectral GNNs can be viewed as learning the filter g(L) in ( 3 ). ChebNet-style models approximate g(L)