Learning Pseudo-Riemannian Manifolds for Heterophilic Graphs via Graph Signature
Organizations: SolverX Seoul, Republic of Korea · Max Planck Institute for Mathematics Bonn, Germany
Abstract
Several widely used families of Graph Neural Networks carry a positive-definite geometric prior. Graph convolution read as heat diffusion needs a positive semi-definite operator, hyperbolic models place features on positive-definite Riemannian manifolds, and dot-product and GAT-style attention scores use positive-definite inner products. On heterophilic graphs, where edges often signify dissimilarity or structural repulsion, that prior is a mismatch: no positive-definite form can assign a negative squared distance to a direction the labels separate. To measure the mismatch, we introduce the Graph Signature Index (), the inertia of a class-compatibility matrix built from label topology alone, and we prove that no value of the edge or node homophily index in rules out a negative eigenvalue. We then propose the Pseudo-Riemannian Attention Network (PRAT), whose attention logit is a signed squared pseudo-distance under a learnable diagonal metric initialized from . The design is diagnose-then-learn: the signature supplies a sign structure that unconstrained training keeps outside near-zero directions, and the projection learns the rest of the metric around it. Across fifteen node-classification benchmarks PRAT outperforms or matches the strongest heterophily-adapted models. A controlled ablation ties that performance to the sign structure itself: with architecture and protocol fixed, forbidding the metric to be indefinite costs accuracy on the graphs marks as indefinite and leaves the others unchanged.
Figures & tables
| Homophilic | Heterophilic | |||||||
| Cora | PubMed | Citeseer | Chameleon | Squirrel | Actor | Cornell | Texas | |
| 0.810 | 0.802 | 0.736 | 0.230 | 0.222 | 0.217 | 0.123 | 0.061 | |
| GCN | 88.32 1.02 | 88.75 0.43 | 77.69 1.06 | 67.43 2.45 | 54.95 1.19 | 30.56 0.70 | 44.32 6.75 | 58.38 4.86 |
| GIN | 87.38 1.56 | 89.20 0.51 | 76.82 1.29 | 62.52 2.61 | 53.56 1.66 | 30.97 1.56 | 41.62 6.86 | 59.73 3.51 |
| SAGE | 88.80 1.04 | 89.77 0.45 | 77.66 0.81 | 64.91 1.81 | 43.92 1.87 | 36.17 1.26 | 69.46 8.64 | 81.35 3.72 |
| GAT | 88.32 1.09 | 88.87 0.41 | 77.10 1.27 | 69.67 1.67 | 55.18 2.13 | 31.61 1.99 | 50.54 7.55 | 64.59 6.67 |
| Filtered Wikipedia | Large-scale heterophilic | ||||||
| Cham.-filt. | Sq.-filt. | roman-empire | amazon-ratings | minesweeper | tolokers | questions | |
| 0.235 | 0.220 | 0.046 | 0.380 | 0.683 | 0.595 | 0.840 | |
| ResNet † | 41.01 4.54 | 38.37 1.99 | 73.90 0.51 | 51.83 0.57 | 70.88 0.90 | 80.70 0.97 | 75.81 0.96 |
| GCN | 40.89 4.12 | 39.47 1.47 | 73.69 0.74 | 48.70 0.63 | 89.75 0.52 | 83.64 0.67 | 76.09 1.27 |
| SAGE | 37.77 4.14 | 36.09 1.99 | 85.74 0.67 | 53.63 0.39 | 93.51 0.57 | 82.43 0.44 | 76.44 0.62 |
| GAT | 39.21 3.08 | 35.62 2.06 | 80.87 0.30 | 49.09 0.63 | 92.01 0.68 | 83.70 0.47 | 77.43 1.20 |
| Dataset | PRAT | ||
|---|---|---|---|
| Cora | 88.42 1.17 | 88.49 1.27 | 88.18 1.10 |
| PubMed | 90.03 0.47 | 89.94 0.46 | 89.87 0.45 |
| Citeseer | 78.06 1.37 | 77.93 1.38 | 78.09 1.45 |
| Chameleon | 68.73 1.74 | 68.40 2.42 | 65.64 1.60 |
| Squirrel | 56.96 1.51 | 54.01 2.08 | 53.47 1.43 |
| Actor | 37.26 1.44 | 36.93 1.21 | 36.69 0.99 |
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
| Model | Complexity |
|---|---|
| PRAT | |
| GAT | |
| GATv2 | |
| SDP |
| Model | Formula | Count |
|---|---|---|
| PRAT | 5,464 | |
| GAT | 4,288 | |
| GATv2 | 4,288 | |
| SDP | 12,480 |
| Dataset | Model | ms / step | peak memory (MiB) | parameters |
|---|---|---|---|---|
| tolokers (11,758 nodes) | PRAT | 26.72 | 1084.4 | 336,689 |
| GAT | 22.80 | 903.0 | 336,657 | |
| GT | 32.85 | 466.1 | 531,713 | |
| questions (48,921 nodes) | PRAT | 88.73 | 3791.2 | 2,830,201 |
| GAT | 91.23 | 3696.9 | 2,830,121 | |
| GT | 175.17 | 5285.5 | 6,734,081 |
| Hyperparameter | Search Range | Distribution |
|---|---|---|
| Model Architecture | ||
| Hidden channels | 64 | Fixed |
| Number of layers | {1, 2, 3, 4} | Discrete |
| Attention heads | {1, 2, 4, 8, 16} | Discrete |
| Input dropout | Uniform | |
| Output dropout | Uniform | |
| Dataset | Hidden | Layers | Heads | FFN mult. | Dropout | Learning rate | Weight decay | Steps | Warmup |
|---|---|---|---|---|---|---|---|---|---|
| Cham.-filt. | 128 | 1 | 8 | 1 | 0.217 | 2,000 | 0.031 | ||
| Sq.-filt. | 512 | 1 | 8 | 0.5 | 0.627 | 500 | 0.042 | ||
| roman-empire | 512 | 5 | 8 | 1 | 0.2 | 0 | 1,000 | 0 | |
| amazon-ratings | 512 | 2 | 8 | 1 | 0.2 | 2,000 | 0.1 | ||
| minesweeper | 128 | 4 | 8 | 0.5 | 0.1 | 2,000 | 0 | ||
| tolokers | 128 | 4 | 4 | 2 | 0.1 | 0 | 2,000 | 0 |
| Dataset Configuration | Hyperparameters | ||
|---|---|---|---|
| Nodes | 1,000 | Hidden channels | 64 |
| Edges | 2,000 | Number of layers | 2 |
| Features | 1,000 | Attention heads | 8 |
| Classes | 5 | Input dropout | 0.6 |
| Output dropout | 0.6 | ||
| Learning rate | 0.002 | ||
| Dataset | seed 42 | seed 7 | seed 123 | seed-to-seed sd | split-to-split sd |
|---|---|---|---|---|---|
| roman-empire | 90.16 | 90.08 | 89.98 | 0.09 | 0.56 |
| amazon-ratings | 53.79 | 53.56 | 53.39 | 0.20 | 0.59 |
| minesweeper | 92.25 | 92.02 | 91.34 | 0.47 | 0.68 |
| tolokers | 84.93 | 85.09 | 85.14 | 0.11 | 0.65 |
| questions | 78.06 | 78.08 | 77.96 | 0.07 | 1.00 |
| Dataset | PRAT | ||||
|---|---|---|---|---|---|
| Cham.-filt. | (3,0,2) | 42.45 2.20 | 40.39 2.73 | 42.00 2.66 | 0.039 |
| Sq.-filt. | (2,1,2) | 39.58 1.71 | 39.39 2.16 | 40.22 1.59 | 0.770 |
| roman-empire | (6,7,5) | 90.16 0.56 | 87.56 0.57 | 90.02 0.51 | 0.002 |
| amazon-ratings | (3,2,0) | 53.79 0.59 | 53.72 0.48 | 53.70 0.63 | 0.492 |
| minesweeper | (1,1,0) | 92.25 0.68 | 92.28 0.56 | 92.09 0.70 | 0.846 |
| tolokers | (2,0,0) | 84.93 0.65 | 84.83 0.72 | 84.93 0.57 | 0.131 |
| roman-empire (6,7,5) | Cham.-filt. (3,0,2) | |||||
| Initialization | Accuracy | Accuracy | ||||
| signature (PRAT) | 90.16 0.56 | – | – | 42.45 2.20 | – | – |
| abs_pos | 87.91 0.61 | 2.26 | 0.002 | 41.64 2.50 | 0.81 | 0.275 |
| sign | 89.86 0.62 | 0.30 | 0.065 | 39.90 2.22 | 2.55 | 0.008 |
| flip | 89.96 0.64 | 0.21 | 0.084 | 39.44 3.20 | 3.01 | 0.027 |
| random 1 | 89.53 0.31 | 0.63 | 0.010 | 40.81 2.77 | 1.63 | 0.037 |
| roman-empire | Cham.-filt. | |||
|---|---|---|---|---|
| Initialization | Accuracy | inertia | Accuracy | inertia |
| label-based signature | 90.16 0.56 | (8,4,6) | 42.45 2.20 | (3,0,2) |
| -means pseudo-labels | 90.10 0.48 | (7,4,7) | 42.70 2.00 | (1,3,1) |
| uninformed identity | 87.61 0.69 | (18,0,0) | 40.18 2.39 | (5,0,0) |
| fraction of training nodes kept | fraction of training labels flipped | |||||
| Dataset | ||||||
| roman-empire | 0.88 | 0.88 | 0.93 | 0.97 | 0.93 | 0.87 |
| amazon-ratings | 0.74 | 0.85 | 0.91 | 1.00 | 0.87 | 0.80 |
| minesweeper | 0.69 | 0.82 | 0.98 | 1.00 | 1.00 | 1.00 |
| tolokers | 0.99 | 1.00 | 1.00 | 1.00 | 1.00 | 0.96 |
| questions | 0.93 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |
| Dataset | Model | 10% | 20% | 40% | 60% | 100% |
|---|---|---|---|---|---|---|
| Cornell | PRAT | 44.05 4.53 | 49.46 9.37 | 57.03 8.59 | 68.38 6.40 | 71.89 4.71 |
| GAT | 44.32 5.16 | 41.62 8.04 | 45.68 9.00 | 46.76 9.37 | 50.54 7.55 | |
| GATv2 | 44.59 5.44 | 41.35 4.02 | 43.51 3.91 | 46.49 10.38 | 54.32 9.70 | |
| Texas | PRAT | 63.24 6.42 | 67.57 9.82 | 74.05 6.42 | 78.65 5.33 | 84.32 5.10 |
| GAT | 60.54 6.07 | 59.73 9.16 | 61.62 5.51 | 61.08 7.27 | 64.59 6.67 | |
| GATv2 | 57.57 6.95 | 60.54 8.65 | 61.62 4.80 | 62.16 6.16 | 66.76 6.63 |
Graph Neural Networks
Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.
See all 780 papers