Learning Pseudo-Riemannian Manifolds for Heterophilic Graphs via Graph Signature

AI summary

Overview

Research area: Graph machine learning — specifically geometric deep learning for graph neural networks (GNNs), applied to node classification on heterophilic graphs.

Technical level: Advanced. The paper assumes familiarity with GNN architectures, attention mechanisms, spectral graph theory, and elementary differential/Riemannian geometry (metric tensors, pullbacks, Sylvester's law of inertia).

Scope (one sentence): The paper argues that standard GNNs carry an implicit positive-definite geometric prior that is structurally mismatched to heterophilic graphs, introduces a label-topology invariant called the Graph Signature Index to diagnose this mismatch, and proposes a pseudo-Riemannian attention network whose learned metric is initialized from that index.

What This Paper Is About

Most popular GNNs implicitly assume a positive-definite geometry: graph convolution as heat diffusion needs a positive semi-definite operator, hyperbolic models place features on positive-definite Riemannian manifolds, and dot-product or GAT-style attention uses positive-definite inner products. On heterophilic graphs — where edges often signal dissimilarity or repulsion — this prior is a mismatch, because no positive-definite form can assign a negative squared distance to a direction along which the labels separate. The paper's goal is to measure that mismatch and then fix it by learning an indefinite (pseudo-Riemannian) metric whose sign structure is derived from the graph's label topology.

Key Contributions

1. The Graph Signature Index ($s_\mathcal{G}$). A new diagnostic defined as the inertia (counts of positive, zero, and negative eigenvalues) of a $|L| \times |L|$ graph signature matrix $S_G$ built purely from label topology, whose $(i,j)$-th entry is the number of edges between label classes $i$ and $j$ divided by the product of the class sizes.

2. A proof that homophily indices are insufficient. The authors prove a critical homophily threshold $h_E^* = \sum_k n_k^2 / N^2$ (reducing to $1/|L|$ for balanced classes), and then prove (Theorem 2.4) that for every rational $h \in (0,1)$ there exists a graph with $h_E = h_V = h$ whose signature matrix still has a negative eigenvalue — so no homophily value in $(0,1)$ rules out negative curvature.

3. A geometric mismatch theorem. Theorem 2.5 shows that if $S_\mathcal{G}$ is indefinite and the pushforward of the feature map is surjective, no diffeomorphism can make the pullback of the Euclidean identity form equal $f^*S_\mathcal{G}$. The mismatch is intrinsic and cannot be repaired by any smooth reparameterization of a Riemannian space.

4. The Pseudo-Riemannian Attention Network (PRAT). An attention layer whose logit is a signed squared pseudo-distance $\Delta(h_{v,u})^\top \mathbf{D}^{[i,k]} \Delta(h_{v,u})$ under a learnable diagonal metric $\mathbf{D}^{[l,k]} = (\mathbf{W}^{[l,k]})^\top S^{|L|} \mathbf{W}^{[l,k]}$, with $S^{|L|}$ instantiated as the graph signature matrix and its diagonal initialized from the training-subgraph signature.

Main Findings

• PRAT matches or beats the strongest heterophily-adapted models across fifteen benchmarks (eight standard plus seven Platonov benchmarks). On the standard benchmarks it is best on Actor (37.26 ± 1.44) and Texas (84.32 ± 5.10), second on Squirrel (56.96 ± 1.51), third on Chameleon (68.73 ± 1.74) and fourth on Cornell (71.89 ± 4.71); among homophilic graphs it is best on Citeseer (78.06 ± 1.37) and third on PubMed (90.03 ± 0.47).

• Gains hold after removing known leakage. On the filtered Chameleon and Squirrel benchmarks, where duplicate nodes causing train–test leakage are removed, PRAT reaches 42.69 ± 2.66 and 39.60 ± 2.25. On roman-empire it reaches 90.08 ± 0.62, on tolokers 85.04 ± 0.48.

• Wins are sometimes ties. The paper explicitly reports that only two of the four "best or tied" results on the Platonov suite are wins: a Welch test against SAGE on amazon-ratings gives $p = 0.55$, and against FAGCN on filtered Chameleon $p = 0.52$. On minesweeper PRAT sits 0.05 pp below third place and on questions 0.01 pp below GT-sep at rank 3.

• PRAT leads every ResNet variant on all seven Platonov datasets, by 1.23 to 21.36 points.

• The sign structure, not the architecture, produces the gain. In the ablation, freezing the diagonal metric to its initialized values (PRAT_fixed) drops average accuracy from 71.96 to 68.22, and constraining it to be positive definite (PRAT_pos) drops it to 68.29. The damage concentrates on the graphs whose signature is indefinite (Cornell: 71.89 → 55.15 / 57.58; Texas: 84.32 → 74.89 / 76.78), while Cora, PubMed and Citeseer are essentially unchanged.

• Indefiniteness helps exactly where the theory says it should. On synthetic graphs with $h_E \in {0, 0.05, \ldots, 1.0}$ and the architecture held fixed within the attention family, PRAT holds its accuracy while GAT, GATv2 and FAGCN fall away together below $h_E = 0.5$; the gap to FAGCN averages 40.6 points over the nine levels at $h_E \leq 0.4$. Curves converge above $h_E = 0.8$, where a positive-definite metric is no longer a mismatch.

• The learned metric follows the data. The ratio of positive eigenvalues in the learned metric falls as homophily falls (Figure 3), so the indefinite signature is not merely imposed. On real graphs the learned diagonal keeps the initial sign of every entry with $|\lambda| > 10^{-4}$.

• Attention behaves differently by regime. At $h_E = 0.1$ PRAT concentrates attention on same-class connections (the diagonal of the source-target heatmap) while keeping the node's own signal; at $h_E = 0.9$ it does not.

• The signature separates graphs that scalar homophily cannot. At a fixed $h_E = 0.5$, varying $s_\mathcal{G}$ over $(5,0,0)$, $(4,0,1)$, $(3,0,2)$ makes GAT's accuracy fluctuate with standard deviation 3.99 and GATv2's with 3.42, while PRAT varies by 0.68.

• Cost is comparable to GAT. At equal backbone, width and depth, a training step takes 88.7 ms on questions versus 91.2 ms for GAT and 175.2 ms for GT, and 26.7 ms on tolokers versus 22.8 ms and 32.9 ms.

• Labels are needed only at initialization. The forward pass never reads labels. The paper reports that a signature estimated from $k$-means pseudo-labels on node features recovers the label-based accuracy on both indefinite benchmarks, and examines robustness to few or incorrect training labels in an appendix.

Methodology in Plain English

The approach is deliberately split into a diagnosis step and a learning step.

Diagnose. From the training labels alone, build a small table whose $(i,j)$ entry records how often a node of class $i$ connects to a node of class $j$, normalized by class sizes. Count how many of this table's eigenvalues are positive, zero and negative. That triple is the graph signature index — a compact fingerprint of the label topology that says, in effect, "this graph needs one negative direction" or "this graph is fine with a positive-definite view."

Learn. Replace the usual Euclidean attention score with a signed squared distance: the difference between two node embeddings, sandwiched through a learnable symmetric matrix. That matrix is factored as a weight matrix applied to the signature matrix, and since the signature matrix is diagonalizable, the eigenvector part is absorbed into the weights while the eigenvalue diagonal — normalized and scaled by $1/\sqrt{|L|}$ — becomes a learnable parameter. The model therefore starts from the geometry the labels imply and adjusts it during training, with the sign structure preserved because unconstrained training keeps the values away from zero.

Validate. The authors test the resulting network on fifteen node classification benchmarks, then run controlled synthetic experiments that vary one structural property at a time (homophily level, then signature index) while holding the architecture family fixed, and finally ablate the metric itself — comparing the full model against a frozen metric and a positive-definite-constrained metric, with architecture and protocol identical in all three.

Why This Matters

Impact on research. The paper reframes heterophily from a statistical property (how often edges cross classes) to a geometric one (what sign structure the label topology demands). Theorem 2.4 is a direct challenge to the habit of characterizing datasets by a single homophily scalar, and Theorem 2.5 gives a formal reason why architectural fixes that keep the space positive definite — signed aggregation, high-frequency filters — are working against the geometry rather than with it. The Graph Signature Index is a reusable diagnostic that can be computed for any labeled graph before any model is trained.

Real-world applications (drawn from the benchmark domains):

• Fraud and anomaly detection networks, where connections between accounts often indicate adversarial or anomalous relations rather than similarity — the paper's minesweeper and tolokers benchmarks come from this family.
• Recommender and co-purchase graphs such as amazon-ratings, where a link can encode substitution or comparison rather than shared taste.
• Citation and web networks such as Cora, Citeseer, PubMed and the WebKB datasets, where cross-field citation is common and a positive-definite smoothing prior blurs the distinctions that matter.
• Q&A and discussion platforms such as questions, where reply edges link users who disagree.

Industry relevance. The cost section is the practical argument: PRAT has GAT's asymptotic cost and measured step times at or near GAT's on the two largest graphs, so the geometric upgrade does not require a heavier backbone. Since the only label-dependent step is initialization, deployment does not require label leakage into inference, and the pseudo-label experiment suggests the signature can be estimated even when labels are scarce.

Future Directions

• Signature estimation without ground-truth labels. The paper shows $k$-means pseudo-labels on node features recover label-based accuracy on the two indefinite benchmarks, and an appendix examines how the estimate degrades with few or incorrect labels. How far this can be pushed — and how to detect a wrong signature at training time — remains open.

• Beyond a diagonal metric on a class-sized latent space. The metric is diagonal and acts on a latent space whose dimension is the number of classes; the non-degeneracy discussion notes the form is degenerate whenever hidden width exceeds $|L|$. Richer (non-diagonal, higher-rank) pseudo-metrics are a natural extension.

• The surjectivity condition in Theorem 2.5. The mismatch theorem requires $\mathrm{rank},\mathbf{W} = |L|$; every configuration reported has $h' > |L|$, so the hypothesis holds for almost every weight matrix. What happens in the low-width regime is not resolved.

• Tasks beyond transductive node classification. All fifteen benchmarks are node classification with fixed splits. Whether an indefinite metric helps link prediction, graph-level tasks, or dynamic graphs is not reported.

Target Audience

Researchers and graduate students in geometric deep learning and graph representation learning who already know GNN architectures and are comfortable with metric tensors and spectral arguments. It is also useful for practitioners working on heterophilic or repulsion-heavy relational data who want a cheap, drop-in attention replacement with a principled initialization — though such readers should go straight to Section 3.2 and Tables 3–5, since the theoretical sections assume mathematical maturity. Readers looking for a survey-level introduction to heterophily will find this too specialized.

Authors’ 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 ($s_{\mathcal{G}}$), 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 $(0,1)$ 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 $s_{\mathcal{G}}$. 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 $s_{\mathcal{G}}$ marks as indefinite and leaves the others unchanged.