ASEHybrid: When Geometry Matters Beyond Homophily in Graph Neural Networks

Shalima Binta Manir, Tim Oates · 2026

Read ASEHybrid: When Geometry Matters Beyond Homophily in Graph Neural Networks by Shalima Binta Manir, Tim Oates (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18912.txt.

Introduction

Shalima Binta Manir and Tim Oates ask why graph neural nets fail on some graphs but not on others. These nets pass notes along links to guess labels for nodes. They tend to do poorly when linked nodes hold unlike labels, a trait called low homophily. But that trait alone does not tell the whole story.

Pairs of graphs can share the same homophily score yet give very unlike scores for the same net. Some unlike label graphs stay easy even for a plain graph net. The authors argue that shape, not just label match, drives the gap, and they test a hybrid method built on that view.

Catalog record

CREATORShalima Binta Manir, Tim Oates
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18912

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ASEHybrid: When Geometry Matters Beyond Homophily in Graph Neural Networks Shalima Binta Manir, Tim Oates Abstract Standard message-passing graph neural networks (GNNs) often struggle on graphs with low homophily, yet homophily alone does not explain this behavior, as graphs with similar homophily levels can exhibit markedly different performance and some heterophilous graphs remain easy for vanilla GCNs. Recent work suggests that label informativeness (LI), the mutual information between labels of adjacent nodes, provides a more faithful characterization of when graph structure is useful. In this work, we develop a unified theoretical framework that connects curvature-guided rewiring and positional geometry through the lens of label informativeness, and instantiate it in a practical geometry-aware architecture, ASEHybrid . Our analysis provides a necessary-and-sufficient characterization of when geometry-aware GNNs can improve over feature-only baselines: such gains are possible if and only if graph structure carries label-relevant information beyond node features. Theoretically, we relate adjusted homophily and label informativeness to the spectral behavior of label signals under Laplacian smoothing, show that degree-based Forman curvature does not increase expressivity beyond the one-dimensional Weisfeiler–Lehman test but instead reshapes information flow, and establish convergence and Lipschitz stability guarantees for a curvature-guided rewiring process. Empirically, we instantiate ASEHybrid using Forman curvature and Laplacian positional encodings and conduct controlled ablations on Chameleon , Squirrel , Texas , Tolokers , and Minesweeper , observing gains precisely on label-informative heterophilous benchmarks where graph structure provides label-relevant information beyond node features, and no meaningful improvement in high-baseline regimes. 1 Introduction Graph neural networks (GNNs) implement a message-passing paradigm in which node representations are iteratively updated by aggregating information from their neighbors ( 16 ; 8 ) . This mechanism underlies many successful architectures and performs particularly well on graphs with homophilous structure, where adjacent nodes tend to share labels ( 9 ) . However, on heterophilous graphs where neighbors often belong to different classes—standard GNNs can fail dramatically, and in some cases simple feature-only classifiers match or outperform graph-based models ( 21 ; 13 ) . The degree of homophily by itself is insufficient to characterize when message passing helps. Different homophily definitions can disagree sharply and are not directly comparable across datasets with varying class counts or imbalance ( 21 ) . Moreover, there exist heterophilous graphs on which vanilla GCNs perform well, as well as graphs with similar homophily levels but markedly different GNN performance ( 10 ) . To address these limitations, recent work has proposed adjusted homophily and label informativeness (LI) as more principled structural descriptors ( 13 ) . LI captures how informative a neighbor’s label is about a node’s label, and empirically correlates more strongly with GNN performance than homophily alone. Platonov et al. ( 13 ) view label informativeness as an intrinsic property of the data distribution. We build on this insight by adopting a model-level perspective, characterizing when graph structure can be exploited by learning architectures via the conditional mutual information I(Y;E\mid X) , which quantifies how much label-relevant information about Y the graph structure E contains beyond node features X , and analyzing how curvature-based signals, positional encodings, and rewiring operationalize (or fail to operationalize) this information. Our model is designed for settings in which graph structure provides label-relevant information beyond node features, rather than for feature-dominated regimes. Since homophily alone does not determine whether edges are informative in this sense, our analysis and experiments focus on datasets where label informativeness, rather than homophily, is the primary explanatory factor. In parallel, there has been growing interest in geometric augmentations for GNNs, including structural encodings, positional encodings, and graph rewiring. Local Curvature Profiles (LCP), based on discrete Ricci curvature, provide node-level summaries of local graph geometry and have been shown to improve performance, especially when combined with Laplacian positional encodings (LapPE) ( 5 ; 3 ) . Curvature-guided rewiring modifies the graph structure by adding edges to mitigate over-squashing ( 18 ) . While recent work has explored combining structural and positional encodings ( 5 ) , integrating curvature-based encodings with curvature-guided rewiring to jointly influence both representations and topology remains unexplored. In contrast, our proposed model, ASEHybrid , integrates node-level structural encodings (LCP), global positional encodings (LapPE), edge-level curvature conditioning, and curvature-guided rewiring within a single architecture, allowing geometric information to jointly shape feature representations and message passing. This variability raises several fundamental questions: • When should curvature and positional geometry help? • What is the role of homophily and label informativeness? • Can curvature-guided rewiring be formalized? In this work, we address these questions by developing a unified theoretical framework that connects curvature-guided rewiring and positional geometry from the perspective of label informativeness, and by grounding the analysis in carefully controlled experiments on heterophilous benchmarks. 1.1 Our Contributions (A) Structural characterization via adjusted homophily and label informativeness We adopt adjusted homophily and label informativeness (LI) as the primary structural descriptors of node-classification graphs ( 13 ) . Within this framework: • We relate adjusted homophily to the spectral concentration of label signals under Laplacian smoothing, explaining why standard GCNs are biased toward low-frequency, homophilous label structure. • We show that LI naturally arises in an information-theoretic comparison between models that can exploit graph edges and those restricted to node features (and positional encodings), yielding a condition of the form I(Y;E\mid X)>0 under which access to edges strictly reduces Bayes risk. (B) Curvature-weighted diffusion and expressivity We formalize Forman curvature as a local, degree-based edge attribute ( 7 ; 17 ) and analyze its role in message passing: • We show that incorporating Forman curvature as a local edge feature does not increase expressive power beyond the one-dimensional Weisfeiler–Lehman (1-WL) test, as standard message-passing GNNs are at most as powerful as 1-WL in distinguishing graph structures ( 19 ) . • In contrast, we show that non-local edge attributes and sufficiently rich positional encodings can strictly increase the distinguishing power of GNNs over plain 1-WL. (C) Curvature-guided rewiring: convergence and stability We study a simple curvature-guided rewiring process inspired by discrete geometric flows ( 18 ) . We prove finite termination and convergence under a Lyapunov-style objective based on curvature regularization, and establish Lipschitz stability with respect to bounded edge-edit perturbations. (D) ASEHybrid: a practical geometry-aware architecture We instantiate the framework in ASEHybrid , a geometry-aware architecture that combines node features, Forman curvature summaries (LCP-style statistics), and Laplacian positional encodings ( 4 ) , followed by curvature-aware attention. Figure 1 provides an overview of ASEHybrid. Figure 1 : ASEHybrid overview. Node-side inputs (features x , LCP, LapPE) are concatenated and processed sequentially by GCNConv and curvature-conditioned GATv2 attention (edge_attr =F_{ij} ), followed by a linear classifier. Curvature-guided rewiring R is a separate operator that edits the graph topology and is enabled only in rewiring-based variants ( +Rewire and +Both ). (E) Empirical validation and limitations Through controlled ablations on the Chameleon , Squirrel , Texas , Tolokers , and Minesweeper datasets, we show that geometry-aware GNNs yield large gains precisely when graph structure is label-informative, and offer negligible benefit otherwise. These results empirically validate our theoretical characterization of when geometric augmentation can improve over feature-only and position-only baselines, and complement prior work that identified label informativeness as a descriptive dataset property. 2 Background and

Read the complete text