cs.LGNov 4, 2026

Learning Pseudo-Riemannian Manifolds for Heterophilic Graphs via Graph Signature

Authors: Yun Young Choi, Asung Kil, Sun Woo Park, Minho Lee, Seokhwan Kim

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 (sGs_{\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)(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 sGs_{\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 sGs_{\mathcal{G}} marks as indefinite and leaves the others unchanged.

Figures & tables

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning

    Sep 9, 2024Sitao Luan, Qincheng Lu, Chenqing Hua +3Graph Neural NetworksNode Classification

  2. Heterophily-Agnostic Hypergraph Neural Networks with Riemannian Local Exchanger

    Feb 28, 2026Li Sun, Ming Zhang, Wenxin Jin +5Hypergraph Neural NetworksGraph Representation Learning

  3. Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification

    Sep 26, 2026Harshit Kumar, Sujan Chakraborty, Priyanka Saha +2Graph RewiringGraph Structure Learning