Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help?
Eyal Weiss · 2026
Read Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help? by Eyal Weiss (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-2603-24291.txt.
Introduction
Weiss asks when per-edge routing helps graph networks on heterophilous graphs, where linked nodes often differ. His layer, Cost-Sensitive Neighborhood Aggregation, measures pairwise distance in a learned projection. It then routes each message through agreeing or disagreeing channels with separate transforms. Theory shows plain averaging can flip the label signal under heterophily, while cost weighting can keep its sign. On six benchmarks, the method matches top results where heterophily is adversarial. It lags where heterophily itself carries the signal, a pattern Weiss calls the finding.
Catalog record
| CREATOR | Eyal Weiss |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38372 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.24291
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help? Eyal Weiss Abstract Recent work distinguishes two heterophily regimes: adversarial , where cross-class edges dilute class signal and harm classification, and informative , where the heterophilous structure itself carries useful signal. We ask: when does per-edge message routing help, and when is a uniform spectral channel sufficient? To operationalize this question we introduce Cost-Sensitive Neighborhood Aggregation (CSNA), a GNN layer that computes pairwise distance in a learned projection and uses it to soft-route each message through concordant and discordant channels with independent transformations. Under a contextual stochastic block model we show that mean aggregation can reverse the label-aligned signal direction under heterophily, and that cost-sensitive weighting with w + / w − > q / p w_{+}/w_{-}>q/p preserves the correct sign. On six benchmarks with uniform tuning, CSNA is competitive with state-of-the-art methods on adversarial-heterophily datasets (Texas, Wisconsin, Cornell, Actor) but underperforms on informative-heterophily datasets (Chameleon, Squirrel)—precisely the regime where per-edge routing has no useful decomposition to exploit. The pattern is itself the finding: the cost function’s ability to separate edge types serves as a diagnostic for the heterophily regime, revealing when fine-grained routing adds value over uniform channels and when it does not. Code is available at https://github.com/eyal-weiss/CSNA-public . 1 Introduction Message-passing Graph Neural Networks (GNNs) [ 6 , 14 , 5 ] aggregate features from a node’s neighborhood under an implicit homophily assumption: connected nodes share labels or properties. When this assumption holds, aggregation smooths representations within a class and yields strong node classification [ 15 ] . However, many real-world graphs exhibit heterophily —connected nodes frequently differ in label [ 10 , 16 ] —and on such graphs standard GNNs can perform worse than a simple Multi-Layer Perceptron (MLP) that ignores graph structure entirely, because aggregation dilutes rather than reinforces class signal [ 16 ] . Several architectures address heterophily: H2GCN [ 16 ] separates ego from multi-hop neighbor representations; GPRGNN [ 3 ] learns polynomial graph filter coefficients; ACM-GNN [ 8 ] mixes low-pass, high-pass, and identity channels with per-node gating. These methods share a common intuition—that different edges carry different quality of information for classification—but differ in how they distinguish edges. ACM-GNN, the most closely related prior work, uses three fixed spectral channels (aggregation, diversification, identity) that are uniform within each channel: every edge receives the same treatment within a given channel. We propose Cost-Sensitive Neighborhood Aggregation (CSNA), which takes a different approach: compute pairwise distance in a learned projection space, and use this distance to soft-route each message through two channels—concordant (low cost, likely same-class) and discordant (high cost, likely different-class)—each with its own learned transformation. A per-node gating mechanism then combines the channels with an ego (the node’s own) representation. The key difference from ACM-GNN is that CSNA’s routing is per-edge : each edge receives an individualized routing weight based on the learned distance between its endpoints, rather than a uniform spectral filter applied identically to all edges. This finer granularity comes at the cost of additional per-edge computation (3–10 \times overhead vs. GCN; see Appendix 0.D ). Contributions. (1) We characterize when per-edge routing helps: CSNA’s learned cost function achieves strong edge-type separation on adversarial-heterophily datasets but not on informative-heterophily datasets, operationalizing the regime distinction through a concrete diagnostic ( Section 5 ). (2) We introduce CSNA, a dual-channel message-passing layer with per-edge cost-based routing ( Section 3 ); the default (“lite”) version uses only observed divergence g_{ij} in a learned projection; an extended version adds a learned component h_{ij} . (3) Under a contextual stochastic block model (CSBM), we prove that mean aggregation can reverse the label-aligned signal direction under heterophily, and that cost-sensitive weighting with w_{+}/w_{-}>q/p preserves the correct sign ( Section 4 ). 2 Related Work Heterophily-aware GNNs. Standard GNNs (GCN [ 6 ] , GAT [ 14 ] , GraphSAGE [ 5 ] ) degrade as homophily decreases [ 16 ] . H2GCN [ 16 ] separates ego from higher-order neighbor embeddings. GPRGNN [ 3 ] learns polynomial graph filter coefficients that can model both low-pass and high-pass responses. FAGCN [ 2 ] assigns positive or negative attention weights. ACM-GNN [ 8 ] is the most closely related method: it decomposes aggregation into three spectral channels (low-pass, high-pass, identity) and combines them with per-node gating. CSNA shares the dual-channel-plus-gating architecture but replaces uniform spectral filters with per-edge learned routing. Distinction from ACM-GNN. Both ACM-GNN and CSNA route messages through multiple channels and gate the output per-node. The difference is in channel construction: ACM-GNN’s channels are defined by fixed spectral operations (mean aggregation for low-pass, signed aggregation for high-pass), so every edge within a channel is treated identically. CSNA computes a per-edge concordance score from learned pairwise distance and uses it to route each edge independently. This is finer-grained but more expensive: ACM-GNN has the same asymptotic cost as GCN ( O(|E|\cdot d) per channel, but with fixed structure), while CSNA requires an additional O(|E|\cdot d) distance computation. When per-edge routing helps: a toy example. Figure 1 illustrates the key scenario where per-edge routing outperforms uniform spectral channels. Consider a heterophilous graph in which most edges are cross-class, but the cross-class edges have mixed utility : some neighbors’ features, when transformed, carry complementary information that aids classification, while others are misleading. A uniform high-pass channel (as in ACM-GNN) treats all cross-class edges identically—it cannot distinguish helpful from harmful heterophilous neighbors. CSNA’s per-edge cost function assigns an individual routing weight to each edge, so the model can upweight informative cross-class edges and downweight misleading ones. This advantage materializes when node features within a class are not homogeneous—some cross-class neighbors provide complementary signal while others contribute noise—precisely the adversarial-heterophily regime. On informative-heterophily datasets, where nearly all heterophilous edges carry useful structural signal, the per-edge decomposition has no useful separation to exploit and the extra routing overhead buys nothing. Figure 1: Toy example: a heterophilous graph where cross-class edges have mixed utility. Left: ACM-GNN’s uniform high-pass channel assigns identical weight to all cross-class edges. Right: CSNA’s per-edge cost routing upweights helpful cross-class edges (thick green) and downweights harmful ones (thin dashed red). This distinction is possible only when the cost function can separate edge types—the adversarial-heterophily regime. Over-smoothing and over-squashing. These pathologies [ 7 , 9 , 1 , 13 ] are compounded under heterophily. Cost-based routing reduces cross-class smoothing but does not address over-squashing, which is a topological bottleneck issue. 3 Method 3.1 Preliminaries Let \mathcal{G}=(V,E) be an undirected graph with n=|V| nodes and feature matrix \mathbf{X}\in\mathbb{R}^{n\times d} . Each node i has a label y_{i}\in\{1,\ldots,C\} . The edge homophily ratio is \mathcal{H}=|\{(i,j)\in E:y_{i}=y_{j}\}|/|E| . In standard message-passing [ 4 ] , node i ’s representation at layer \ell+1 is: \mathbf{h}_{i}^{(\ell+1)}=\sigma\!\Bigl(\sum_{j\in\mathcal{N}(i)}\alpha_{ij}\,\mathbf{W}^{(\ell)}\,\mathbf{h}_{j}^{(\ell)}\Bigr), (1) where \mathcal{N}(i) includes i itself, \alpha_{ij} are aggregation weights, and \sigma is a nonlinearity. 3.2 Cost-Sensitive Neighborhood Aggregation The core idea is simple: compute pairwise distance in a learned projection, use it to soft-route messages through two channels. Step 1: Edge cost (observed divergence). For each edge (i,j) at layer \ell , we compute a distance in a learned projection: g_{ij}^{(\ell)}=\|\mathbf{W}_{g}\,\mathbf{h}_{i}^{(\ell)}-\mathbf{W}_{g}\,\mathbf{h}_{j}^{(\ell)}\|_{2}, (2) where \mathbf{W}_{g}\in\mathbb{R}^{d^{\prime}\times d} is a learned projection matrix. Low g_{ij} indicates the endpoints are similar in