Revisiting Pre-Propagation GNNs: Robust Diffusion Operators and Hidden-State Re-Propagation
This paper introduces robust diffusion operators and hidden-state re-propagation, significantly improving pre-propagation GNN performance on heterophilic graphs.
Key Findings
Methodology
The authors develop stable diffusion bases based on orthogonal polynomials (Jacobi, polynomial) and Lanczos/Krylov subspaces to enhance spectral diversity and conditioning of precomputed multi-hop features. They introduce a few-shot hidden-state re-propagation (HRP) mechanism, which periodically re-diffuses intermediate hidden representations during training, effectively coupling feature propagation with learned representations. The approach employs RNN-based hop aggregators to reduce computational overhead while maintaining performance. Extensive experiments on heterophilic and homophilic datasets demonstrate that these techniques narrow the accuracy gap with message-passing GNNs, achieving state-of-the-art results.
Key Results
- On heterophilic datasets like Roman-Empire and Minesweeper, the improved PP-GNNs gained an average of 2.18% in test accuracy, surpassing several message-passing baselines. The spectral conditioning of diffusion bases reduced the maximum accuracy gap from 11.22% to 3.2%, especially on heterophilic graphs. The few-shot HRP mechanism enhanced expressivity without sacrificing efficiency, with performance gains consistent across 12 datasets. Incorporating RNN hop aggregation further reduced training time while maintaining accuracy comparable to attention-based methods.
Significance
This work advances the scalability and expressivity of pre-propagation GNNs, crucial for large-scale and complex graph data such as social networks and knowledge graphs. By improving spectral design and dynamic feature coupling, it addresses longstanding limitations in heterophilic graph learning, enabling more accurate and efficient models. The proposed framework bridges the gap between traditional message passing and scalable pre-processing, opening avenues for real-world applications requiring high performance on large, heterogeneous graphs.
Technical Contribution
The paper introduces orthogonal polynomial and Krylov subspace-based diffusion bases, improving spectral diversity and conditioning of precomputed features. It proposes a few-shot hidden-state re-propagation mechanism, dynamically coupling feature diffusion with learned representations. An RNN-based hop aggregator reduces computational complexity compared to multi-head attention, maintaining performance while enhancing efficiency. These innovations collectively enable scalable, expressive GNNs capable of handling heterophilic graphs with high accuracy.
Novelty
This is the first systematic integration of orthogonal polynomial and Krylov subspace methods for stable, spectrally diverse diffusion bases in pre-propagation GNNs. The few-shot HRP introduces a dynamic, iterative feature refinement process, bridging static pre-processing and message passing. The combination of spectral conditioning, adaptive re-propagation, and RNN aggregation constitutes a novel framework that significantly narrows the performance gap on heterophilic graphs, setting new standards in scalable GNN design.
Limitations
- Despite spectral improvements, the computational cost of Lanczos/Krylov methods may still be high for extremely large graphs. Numerical stability issues can arise in high-dimensional feature spaces, requiring further optimization. The approach's effectiveness in highly noisy or dynamic graphs remains to be validated, and real-time adaptation mechanisms are needed for dynamic scenarios.
Future Work
Future directions include developing adaptive spectral calibration strategies, integrating dynamic graph handling, and optimizing the computational efficiency of Lanczos/Krylov procedures. Extending the framework to dynamic and multi-modal graphs, as well as exploring self-supervised pre-training, could further enhance scalability and robustness in real-world applications.
AI Executive Summary
Graph neural networks (GNNs) have revolutionized the analysis of structured data, but their scalability and expressivity remain challenging, especially on heterophilic graphs where neighboring nodes often belong to different classes. Traditional message passing (MP) methods excel in capturing complex dependencies but suffer from high computational costs and limited scalability. Pre-propagation GNNs (PP-GNNs) emerged as a promising alternative by decoupling feature diffusion from learnable transformations, enabling efficient training on large-scale graphs. However, their performance on heterophilic data has lagged behind MP-GNNs, with empirical gaps up to 11%. This paper addresses this critical gap by proposing a suite of robust spectral diffusion operators and a few-shot hidden-state re-propagation (HRP) mechanism. The diffusion operators leverage orthogonal polynomial bases—Jacobi and Lanczos/Krylov—to produce well-conditioned, spectrally diverse features that better capture high-frequency information essential for heterophily. The HRP mechanism periodically re-diffuses intermediate hidden states during training, dynamically coupling feature propagation with evolving representations, thus enhancing expressivity without sacrificing efficiency. An RNN-based hop aggregator further reduces computational overhead compared to attention mechanisms. Extensive experiments across 12 datasets, including challenging heterophilic graphs like Roman-Empire and Minesweeper, demonstrate that the proposed methods narrow the performance gap with message passing, with average accuracy improvements of 2.18% and maximum gap reduction from 11.22% to 3.2%. These advances significantly improve the scalability and robustness of PP-GNNs, making them viable for real-world large-scale heterogeneous graph analysis. The framework opens new avenues for spectral design, dynamic feature coupling, and efficient graph learning, promising impactful applications in social networks, knowledge graphs, and beyond. Future work will explore adaptive spectral calibration, dynamic graph handling, and hardware-optimized implementations to further push the boundaries of scalable graph neural modeling.
Deep Analysis
Background
Graph neural networks (GNNs)自Gilmer等人提出的消息传递机制以来，已成为处理结构化图数据的核心工具。早期代表如GCN（Kipf & Welling, 2017）实现了高效的邻域信息聚合，但在大规模异质图中面临计算瓶颈。预传播GNN（PP-GNN）通过在训练前一次性扩散特征，极大简化了训练流程，符合现代硬件优化需求。近年来，学者们尝试结合谱滤波、正交多项式、Lanczos方法等提升特征表达能力，但在异质图上的性能仍有限。当前研究关注如何在保持高效的同时，增强模型的表达力，特别是在异质图中捕获高频信息。
Core Problem
现有PP-GNN在异质图上的性能差距明显，最大达11.22%的准确率差异，主要源于扩散算子谱条件差和特征表达有限。简单的扩散算子（如归一化邻接矩阵）多为低通滤波，难以捕获高频信息，导致模型在异质场景中表现不佳。此外，一次性特征扩散未能动态适应节点特征的演变，限制了模型的表达能力。如何设计更稳健的谱条件优化策略，结合动态特征重传播，成为亟待解决的问题。
Innovation
本研究提出两大创新：一是基于正交多项式（Jacobi、多项式）和Lanczos/Krylov子空间的稳健扩散基，改善特征的谱条件，增强多阶特征的表达能力；二是引入少样本隐藏状态重传播（HRP）机制，动态调节特征传播与学习的关系，提升模型的表达力。结合RNN聚合器，有效降低了多头注意力的计算成本。这些创新突破了传统PP-GNN在异质图上的性能瓶颈，为谱设计与动态特征融合提供新思路。
Methodology
- �� 设计基于正交多项式（Jacobi、多项式）和Lanczos/Krylov子空间的稳健扩散算子，改善特征的谱条件。
- �� 采用一阶谱校准策略，根据图的谱密度自动调节参数（α, β），实现自适应谱优化。
- �� 引入少样本隐藏状态重传播（HRP），在训练过程中定期对中间隐藏表示进行多轮扩散，增强特征的动态适应能力。
- �� 结合RNN聚合器，将不同阶特征作为序列输入，提升特征融合效率。
- �� 在多个异质与同质图数据集上进行广泛验证，比较不同扩散算子与重传播策略的性能差异。
Experiments
- �� 采用六个异质图（Roman-Empire、Minesweeper等）和六个同质图（Cora、Citeseer等）进行评估。
- �� 比较基线包括GCN、GAT、GraphSAGE及其异质变体。
- �� 评估指标为节点分类准确率、ROC-AUC等，采用10次随机重抽样。
- �� 逐步验证鲁棒扩散算子（Jacobi、多项式、Lanczos）对性能的影响，以及少样本HRP的贡献。
- �� 通过消融实验分析不同参数设置（如扩散阶数、重传播轮次）对性能的影响。
Results
- �� 改进后PP-GNN在异质图上的平均性能提升2.18%，在12个数据集中的7个超越传统MP-GNN。
- �� 鲁棒扩散算子显著缩小最大性能差距，从11.22%降至3.2%，在异质场景中表现更稳健。
- �� 少样本重传播机制在保持训练效率的同时，增强了模型的表达能力，验证了其在复杂图结构中的有效性。
- �� RNN聚合器在减少计算成本的同时，保持了与多头注意力机制相当的性能。
Applications
- �� 适用于大规模异质图分析，如社交网络、知识图谱中的节点分类与链接预测。
- �� 结合预处理扩散与动态特征重传播，提升模型在复杂场景中的适应性与鲁棒性。
- �� 未来可扩展至动态图、异构多模态图等多样化应用场景，为工业界提供高效解决方案。
Limitations & Outlook
- �� 计算复杂度仍较高，Lanczos和Krylov方法在高维特征空间中存在数值稳定性挑战。
- �� 在极端异质性或噪声较多的图结构中表现有限，需结合自适应机制进一步提升鲁棒性。
- �� 目前主要验证在静态图上，动态场景和大规模图的扩展仍需优化。
Plain Language Accessible to non-experts
想象你在一个工厂里，工厂每天都要处理大量的原材料（节点信息）。传统的方法就像用一个简单的筛子筛一遍原料，只能筛出比较粗的东西，效率快但不够细致。预传播GNN就像提前把原料经过多次筛选，得到一份已经准备好的原料袋，工人只需简单加工即可完成任务。这种方法快但有时筛子太简单，不能筛出所有细节，特别是在复杂的工厂（异质图）中。本文提出用更先进的筛子（正交多项式和Lanczos基），让筛子更聪明，能筛出更多细节。同时，工厂还引入了“回炉”机制，偶尔重新筛好已筛好的原料（隐藏状态重传播），让工艺更灵活。最后，用一个聪明的机器人助手（RNN聚合器）帮忙把不同的筛选结果组合得更巧妙。这样一来，不仅筛得更快，还能筛出更复杂、更漂亮的产品。这些改进让工厂的生产变得更快、更细致，能应对更复杂的任务。
Abstract
Pre-propagation graph neural networks (PPGNNs) 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 PPGNNs 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 PPGNNs, enabling them to match the accuracy of message-passing GNNs while maintaining training efficiency.