When Graph Neighbors Differ, Attention Gets a New Geometry

Graph neural networks (GNNs) learn from nodes and their connections, whether the nodes represent web pages, products or words. In a homophilic graph, neighbors often share a label. In a heterophilic graph, neighbors frequently belong to different classes, so indiscriminately blending their representations can obscure the distinctions a classifier needs.

Yun Young Choi and colleagues propose a way to diagnose part of this problem and use the diagnosis to initialize a graph attention model. Their paper, Learning Pseudo-Riemannian Manifolds for Heterophilic Graphs via Graph Signature, is available as arXiv preprint 2611.06265v1; the landing page says it was accepted at NeurIPS 2026. The authors report competitive node-classification results, with controlled experiments suggesting that their geometry matters on some datasets.

A signature beyond a single homophily score

A conventional edge-homophily score is the fraction of edges connecting nodes with the same label. It is useful, but it compresses all class-to-class relationships into one number. Two graphs can have the same fraction while connecting their classes in different patterns.

The proposed Graph Signature Index starts with a matrix of connection densities between pairs of classes: each entry counts connections between two classes, normalized by the sizes of those classes. The index counts the matrix's positive, zero and negative eigenvalues. Roughly, those counts describe different directions in the pattern of class connectivity, rather than simply how many edges stay within a class.

The authors prove that, for every attainable homophily value strictly between zero and one, a labeled graph can still have a negative eigenvalue. They also show a more specific geometric mismatch: under a surjectivity assumption on the map into label space, a positive-definite Euclidean form cannot reproduce the pullback of an indefinite signature matrix through a smooth coordinate change. That is a statement about the specified mathematical forms, not a proof that every ordinary GNN fails on heterophily.

Learning attention with signed directions

The proposed Pseudo-Riemannian Attention Network, or PRAT, uses a signed quadratic form to score a node and each neighbor. Unlike an ordinary squared Euclidean distance, this quantity can be negative in some directions. It is a mathematical score, not a claim that physical distances are negative.

In practice, the model projects hidden features into a space with one dimension per class. It initializes a diagonal set of weights from the eigenvalues of the signature matrix calculated on the subgraph induced by training nodes. Both the projection and the diagonal weights are learned. A separate self-loop score lets the node's own representation compete with its neighbors; a softmax turns the scores into nonnegative attention weights for aggregation. Thus the signed geometry changes the logits, not the sign of the final attention weights.

The forward pass does not read node labels, though the usual initialization uses training labels. The diagonal entries are not constrained to retain their initial signs. The paper reports that, on its real graphs, entries initialized away from near-zero eigenvalues nevertheless kept their signs during training.

What the experiments show

The authors evaluate 15 node-classification benchmarks, reporting means over 10 data splits, generally with a fixed training seed. On the roman-empire benchmark, PRAT reached 90.08% ± 0.62 accuracy, compared with 88.75% ± 0.41 for GAT-sep, an attention baseline that separates a node's own representation from its neighbors'. On filtered Chameleon, PRAT reached 42.69% ± 2.66, versus 41.90% ± 2.72 for FAGCN; the authors' statistical comparison treats that difference as a tie. The filtered dataset removes duplicate nodes associated with leakage in the original benchmark.

PRAT did not win every comparison. On filtered Squirrel it scored 39.60% ± 2.25 accuracy, below FAGCN's 41.08% ± 2.27. On minesweeper the reported metric is ROC AUC, not accuracy: PRAT scored 92.24 ± 0.68, below GAT-sep's 93.91 ± 0.35. Several other margins are small relative to split variability.

A closer ablation compared PRAT with a variant whose diagonal weights were constrained positive. In a matched run on roman-empire, mean accuracy fell from 90.16% to 87.56%; on filtered Chameleon it fell from 42.45% to 40.39%. Both differences were significant in the authors' paired tests. Filtered Squirrel also had a reported negative signature but showed no significant difference in this ablation. The positive-only variant also uses a different initialization, so this comparison tests the combined effect of removing indefinite directions and changing their starting point; additional initialization controls help investigate those effects.

Limits of the diagnosis

A negative signature is not a guarantee of improvement, and the authors describe the index as a diagnostic rather than a predictor of accuracy. Reported signature counts also round very small eigenvalues to zero, making borderline cases sensitive to the chosen threshold.

The method is studied for semi-supervised node classification on undirected benchmarks. Sparse labels can make the training-subgraph estimate noisy, especially on small graphs; on Cornell, the reported advantage over standard attention nearly disappeared when only 10% of the original training split was used. A two-dataset experiment using feature-based k-means pseudo-labels produced comparable accuracy without labels for initialization, but training still used labels. Fully self-supervised learning, graph-level tasks and shifts in signature between training and test graphs remain open.

The paper also says its released implementation is restricted to research and non-commercial use because of patent-related restrictions. For practitioners, the main result is therefore a conditional one: class connectivity can provide a useful geometric prior, but its reliability and the value of indefinite attention depend on the graph and the available labels.