Learning Propagation Geometry from Message-Passing Feedback
Authors: Yingxu Wang, Kunyu Zhang, Xinwang Liu, Mengzhu Wang, Siyang Gao, Chang Tang, Nan Yin
Organizations: The Chinese University of Hong Kong · The Education University of Hong Kong · National University of Defense Technology · Hebei University of Technology · City University of Hong Kong · Huazhong University of Science and Technology
Learning local geometry enables graph neural networks (GNNs) to adapt how they compare and integrate neighborhood information. However, estimating geometry from aggregated representations can overlook variation among individual messages and dependencies across feature dimensions. We propose GeoF, a recurrent framework that jointly evolves node features and propagation geometry through message-passing feedback. Each node maintains a local symmetric positive-definite geometry, initialized from a structure-aware prototype atlas and parameterized in block log-triangular coordinates. At each step, the geometry determines neighborhood weights, while triangular frame transport maps transformed source messages into the target node's local coordinates before aggregation. Weighted second-order statistics of residuals between aligned messages and the transformed target state capture directional variation and within-block dependencies, yielding a geometric update target. A shared controller learns complementary corrections through task supervision. A bounded log-triangular update combines these corrections, the target, and the previous geometric state while preserving positive definiteness. The geometry governs subsequent propagation, closing the feedback loop. With parameters shared across recurrent steps, task-specific readouts support node classification, link prediction, and graph classification. Experiments on benchmark datasets show that GeoF consistently outperforms state-of-the-art GNN baselines.
Figures & tables
Model
CiteSeer
PubMed
CS
Physics
Photo
Computers
NC
LP
NC
LP
NC
LP
NC
LP
NC
LP
NC
LP
GCN
71.5 ±1.7
92.3 ±0.9
87.6 ±0.5
92.9 ±0.6
93.8 ±0.4
92.7 ±0.6
93.5 ±0.2
92.6 ±1.3
92.1 ±0.5
86.1 ±0.7
87.8 ±0.7
86.9 ±0.8
GIN
70.6 ±1.2
93.0 ±1.0
86.6 ±0.6
89.5 ±0.7
91.3 ±0.6
93.3 ±0.7
94.2 ±0.5
92.1 ±0.8
92.7 ±0.5
87.7 ±0.4
87.1 ±0.8
84.1 ±1.2
ML 2 -GCL
73.7 ±2.0
93.8 ±1.0
87.9 ±0.5
95.8 ±0.3
92.1 ±0.5
97.1 ±0.1
93.4 ±1.6
97.2 ±0.1
92.8 ±0.8
96.7 ±0.1
87.4 ±0.8
95.8 ±0.3
AMPs
74.4 ±1.8
93.5 ±0.9
88.9 ±0.3
96.6 ±0.3
94.6 ±0.3
97.1 ±0.2
96.1 ±0.1
96.6 ±0.6
94.6 ±0.8
96.8 ±0.2
90.2 ±0.6
96.0 ±0.1
WaveGC
75.4 ±1.9
92.8 ±0.7
87.6 ±0.5
97.5 ±0.3
94.4 ±0.3
97.1 ±0.2
96.2 ±0.1
97.2 ±0.2
94.6 ±0.8
97.7 ±0.4
90.2 ±0.8
97.5 ±0.4
Table 1: Performance comparisons (in %) between baselines and GeoF for Node Classification (NC) and Link Prediction (LP) on different datasets. Bold indicates the best performance.
Model
PROTEINS
Mutag
NCI1
FRANK
BBBP
molhiv
GCN
75.3 ±1.9
79.8 ±1.8
76.0 ±1.0
63.3 ±2.2
87.4 ±2.0
75.8 ±2.0
GIN
76.7 ±1.7
80.1 ±1.9
78.0 ±1.2
68.9 ±1.7
89.5 ±2.1
77.3 ±2.0
ML 2 -GCL
77.9 ±1.8
81.9 ±1.9
80.7 ±1.3
70.7 ±1.8
90.9 ±2.2
81.3 ±1.6
AMPs
78.8 ±2.0
83.4 ±1.6
82.0 ±1.1
72.4 ±1.8
92.5 ±2.3
82.0 ±2.4
WaveGC
79.0 ±1.8
82.3 ±2.3
81.6 ±1.8
72.6 ±1.9
92.6 ±1.8
82.0 ±1.9
SPARROW
78.7 ±1.5
83.7 ±1.9
80.9 ±1.2
72.3 ±2.2
91.8 ±1.9
81.5 ±2.3
Table 2: Performance comparisons (in %) between baselines and GeoF for Graph Classification.
Figure 1: (a) Ablations on Mutagenicity and NCI1. (b) Sensitivity to block count B and atlas size K on NCI1. (c), (d) Evolution depth and perturbation stability on PubMed, respectively.
Model
CiteSeer
Photo
PROTEINS
BBBP
GCN
71.5 ±1.7
92.1 ±0.5
75.3 ±1.9
87.4 ±2.0
GCN w/ SO
72.3 ±1.9
92.4 ±1.1
77.0 ±2.4
86.7 ±2.5
GIN
70.6 ±1.2
92.7 ±0.5
76.7 ±1.7
89.5 ±2.1
GIN w/ SO
73.3 ±1.0
93.6 ±1.4
78.5 ±1.5
91.3 ±2.2
ARGNN
75.6 ±1.2
94.9 ±0.5
78.0 ±1.8
92.3 ±1.7
ARGNN w/ SO
74.4 ±2.3
95.3 ±0.6
78.3 ±2.2
91.9 ±2.1
Table 3: Performance comparison (in %) between baselines and their second-order (SO) variants. Bold indicates the best performance.
Feedback
Photo
CS
Mutag.
NCI1
Mean-only
94.9 ±0.6
95.1 ±0.3
83.7 ±1.7
81.9 ±1.6
Diagonal
95.1 ±0.3
95.2 ±0.4
83.2 ±2.0
80.4 ±1.0
One-shot
94.6 ±0.5
94.8 ±0.3
83.1 ±1.8
79.8 ±2.7
Full
96.0 ±0.4
95.8 ±0.3
84.9 ±1.7
83.0 ±1.5
Table 4: Performance comparison (in %) among different residual feedback statistics. Bold indicates the best performance.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Description
G=(V,E,X),A
Attributed graph with node set V , edge set E , feature matrix X , and adjacency matrix A .
n,F0,C
Numbers of nodes, input features, and classes, respectively.
ui,U,q
Fixed structural signature of node i , signature matrix, and signature dimension.
N(i),N(i)
Neighborhood of node i and its extension with a self-loop.
d,B,m
Hidden dimension, number of geometric blocks, and block size, with d=Bm .
K,L
Numbers of geometric prototypes and recurrent evolution steps.
Appendix
Table 5: Summary of key notations.
Datasets
Graphs
Avg. Nodes
Avg. Edges
Classes
CiteSeer
-
3,327
9,104
6
PubMed
-
19,717
88,648
3
CS
-
18,333
163,788
15
Physics
-
34,493
495,924
5
Photo
-
7,650
238,162
8
Computers
-
13,752
491,722
10
Appendix
Table 6: Statistics of the experimental datasets.
Type
Model
NC Avg.
LP Avg.
GC Avg.
Overall Avg.
Avg. Rank
Avg. Gain
pHolm
General GNNs
GCN
87.7
90.6
76.3
84.9
13.2
+5.7
2.91×10−15
GIN
87.1
90.0
78.4
85.2
13.3
+5.4
1.82×10−15
ML 2 -GCL
87.9
96.1
80.6
88.2
9.4
+2.4
1.83×10−7
AMPs
89.8
96.1
81.9
89.3
5.0
+1.3
2.07×10−2
WaveGC
89.7
96.6
81.7
89.4
4.4
+1.2
4.17×10−2
SPARROW
87.8
96.5
81.5
88.6
7.6
+1.9
6.45×10−5
Appendix
Table 7: Cross-task aggregate comparison across all 18 reported dataset–task settings. Bold indicates the best result.
Figure 2: Ablation studies on BBBP and ogbg-molhiv in (a), and PubMed and Computers in (b); sensitivity to geometric blocks B and atlas prototypes K on PubMed in (c) and Mutagenicity in (d).
Methods
PubMed
CS
Computers
NCI1
Mutagenicity
ogbg-molhiv
GCN
0.0086
0.0167
0.0153
0.2094
0.2312
2.1633
AMPs
0.0393
0.0478
0.0761
0.3170
0.3173
2.8410
G 2 Former
0.0637
0.0739
0.0640
0.2011
0.2173
2.2996
SPDGNN
0.0277
0.0321
0.0283
0.2073
0.2287
2.3973
ARGNN
0.0902
0.1573
0.4328
0.2437
0.3383
2.5373
GeoF
0.0683
0.1207
0.1810
0.4391
0.5357
6.0456
Appendix
Table 8: Time consumption of different methods in the training stage for each epoch (in seconds).
Methods
PubMed
CS
Computers
NCI1
Mutagenicity
ogbg-molhiv
GCN
0.7
1.3
1.3
0.8
0.8
0.9
AMPs
2.7
4.9
5.0
1.3
1.6
2.0
G 2 Former
3.3
3.2
3.0
1.5
1.5
1.4
SPDGNN
1.3
2.9
1.9
0.9
1.0
0.9
ARGNN
4.8
8.3
21.3
2.7
2.6
3.8
GeoF
6.4
10.9
15.2
3.5
3.0
4.8
Appendix
Table 9: GPU memory consumption of different methods in the training stage (in GB).
Figure 3: (a), (b) show t-SNE visualizations of node representations learned by ARGNN and GeoF. (c), (d) compare representations with the learned geometric correction disabled and enabled.
Graph Neural Networks (GNNs) have become the de facto standard for learning on relational data. While traditional GNNs' message passing is well suited for vector-valued node features, there are cases in which node features are better represented by probability distributions than real vectors. Concretely, when node features are Gaussians, characterized by a mean and a covariance matrix, naively concatenating their parameters into a single vector and applying standard message passing discards the geometric and algebraic structure that governs means and covariances. We propose Gaussian Sheaf Neural Networks (GSNNs), a principled framework that incorporates these inductive biases into graph-based learning. Building on the theory of cellular sheaves, we derive a new Laplacian operator that generalizes the sheaf Laplacian to this setting and preserves its key properties. We complement our theoretical contributions with experiments on synthetic and real-world data that illustrate the practical relevance of GSNNs.
André Ribeiro, Ana Luiza Tenório, Tiago da Silva +1
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.
Zichao Yue, Zhiru Zhang
School of Electrical and Computer Engineering, Cornell University, Ithaca, New York, USA.
Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.
Hugo Attali, Rachid El Jouhri
Université Sorbonne Paris Nord, CNRS, LIPN, France