Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help?

Eyal Weiss

cs.LGMar 25, 2026

Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help?

Authors: Eyal Weiss

Organizations: Computer Science Faculty, Technion — Israel Institute of Technology

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$ 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 .

Figures & tables

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.

Dataset	Nodes	Edges	Features	Classes	$\mathcal{H}$
Texas	183	287	1,703	5	0.09
Wisconsin	251	458	1,703	5	0.19
Cornell	183	278	1,703	5	0.13
Actor	7,600	26,705	932	5	0.22
Chameleon	2,277	31,396	2,325	5	0.23
Squirrel	5,201	198,423	2,089	5	0.22

Table 1: Dataset statistics.

\mathcal{H}

is the edge homophily ratio.

Method	Texas	Wisconsin	Cornell	Actor	Chameleon	Squirrel
	$\mathcal{H}$ =0.09	$\mathcal{H}$ =0.19	$\mathcal{H}$ =0.13	$\mathcal{H}$ =0.22	$\mathcal{H}$ =0.23	$\mathcal{H}$ =0.22
MLP	77.3 $\pm$ 4.6	83.7 $\pm$ 4.8	72.2 $\pm$ 3.6	35.0 $\pm$ 1.4	51.9 $\pm$ 1.8	34.8 $\pm$ 1.4
GCN	55.7 $\pm$ 9.9	50.6 $\pm$ 8.5	47.0 $\pm$ 8.7	27.3 $\pm$ 1.4	67.3 $\pm$ 1.7	53.4 $\pm$ 0.8
GAT	50.8 $\pm$ 9.8	51.4 $\pm$ 7.8	47.3 $\pm$ 5.8	28.0 $\pm$ 1.4	65.7 $\pm$ 2.2	50.4 $\pm$ 1.4
GraphSAGE	76.5 $\pm$ 6.8	75.9 $\pm$ 5.8	66.2 $\pm$ 7.7	34.1 $\pm$ 0.6	63.9 $\pm$ 2.1	45.8 $\pm$ 1.4
H2GCN	81.9 $\pm$ 4.2	82.4 $\pm$ 5.8	72.2 $\pm$ 4.2	35.6 $\pm$ 0.9	56.8 $\pm$ 2.7	35.0 $\pm$ 1.3

Table 2: Node classification accuracy (%) on heterophily benchmarks. All methods tuned over the same grid. Best in bold , second-best underlined .

Figure 2: Learned concordance scores

s_{ij}

for same-class (green) and different-class (red) edges on three datasets. On adversarial-heterophily datasets (Texas, Cornell), the distributions are well separated; on Actor, overlap is larger. Generated using the extended (

g+h

) variant; similar separation is observed with the lite version.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Variant	Texas	Wisconsin	Cornell	Actor	Chameleon	Squirrel
Full, no samp	77.0	84.1	70.8	35.6	53.0	38.2
Full + samp	74.1	79.8	70.5	36.3	51.8	37.4
Lite, no samp	77.0	79.6	72.7	35.7	54.6	37.8
Lite + samp	75.7	79.6	70.3	35.8	53.5	37.0

Appendix

Table 3: CSNA variant comparison: accuracy (%) on all six datasets. “Full” includes both

g_{ij}

and

h_{ij}

; “lite” uses

g_{ij}

only. “Samp” applies edge sampling during training.

Method	Cora	CiteSeer	PubMed
GCN	77.9	65.7	76.0
CSNA	67.0	56.3	72.2

Appendix

Table 4: Accuracy (%) on homophilous benchmarks. CSNA underperforms GCN by 4–11pp.

Dataset	$\gamma_{\text{con}}$	$\gamma_{\text{dis}}$	$\gamma_{\text{self}}$
Texas	0.30	0.13	0.57
Wisconsin	0.00	0.00	1.00
Cornell	0.12	0.28	0.60
Actor	0.00	0.00	1.00
Chameleon	0.34	0.66	0.00
Squirrel	0.14	0.86	0.00

Appendix

Table 5: Average gate weights

\gamma

across nodes (layer 0).

Method	Texas	Actor	Chameleon	Squirrel	Params (Texas)
MLP	0.2	3	1	2	219K
GCN	0.2	4	7	62	219K
GAT	0.3	11	20	152	110K
GraphSAGE	0.3	15	30	132	219K
H2GCN	0.6	11	27	327	318K
GPRGNN	0.6	9	14	111	219K

Appendix

Table 6: Training time (seconds per split) and parameter count. All on 8-core CPU.

Explore similar work

HeterSEED: Semantics-Structure Decoupling for Heterogeneous Graph Learning under Heterophily
May 6, 2026Xinyi Li, Ming Li, Lu Bai +5Heterogeneous GNNs Node Classification
Zhejiang Normal University · Beijing Normal University · Central University of Finance and Economics +2
Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networks
Aug 14, 2026Preben M. Ness, Fariz Ikhwantri, Dusica MarijanGraph Neural Networks Node Classification
Simula Research Laboratory
Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning
Sep 9, 2024Sitao Luan, Qincheng Lu, Chenqing Hua +3Graph Neural Networks Node Classification
Mila - Quebec Artiﬁcial Intelligence Institute · 1McGill University

May 6, 2026J/K move · Enter open · S save

HeterSEED: Semantics-Structure Decoupling for Heterogeneous Graph Learning under Heterophily

Xinyi Li, Ming Li, Lu Bai, Lixin Cui+4

Zhejiang Normal University · Beijing Normal University · Central University of Finance and Economics+2

Heterogeneous GNNs Node Classification Graph Heterophily

Open paper AskPDF arXiv

Many real-world heterogeneous graphs exhibit pronounced heterophily, where connected nodes often have dissimilar labels or play different semantic roles. In such settings, standard heterogeneous graph neural networks that aggregate messages along metapaths or meta-relations primarily based on feature similarity can propagate misleading information, since feature similarity may be misaligned with underlying relational semantics. In this paper, we propose HeterSEED, a semantics-structure decoupling framework for heterogeneous graph learning under heterophily. HeterSEED decouples representation learning into a heterogeneous semantic channel that captures type- and relation-aware local semantics and a structure-aware heterophily channel that separates homophilic and heterophilic neighborhoods via pseudo-label-guided partitioning and aggregates them using metapath-based structural weights. A node-level adaptive fusion mechanism then combines the two channels to produce context-dependent node representations. Theoretically, we establish that, on heterogeneous graphs under heterophily, HeterSEED is strictly more expressive than standard heterogeneous graph neural networks that rely primarily on feature similarity and provably reduces the prediction bias introduced by heterophilic neighbors. Experiments on five real-world heterogeneous graphs, including two large-scale networks at the million-node and hundred-million-edge scale, demonstrate that HeterSEED consistently outperforms representative heterogeneous graph neural networks and recent heterophily-aware baselines, especially in strongly heterophilic regimes.

Abstract

Explore similar work

HeterSEED: Semantics-Structure Decoupling for Heterogeneous Graph Learning under Heterophily

Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networks

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