Paper deep dive
Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help?
Eyal Weiss
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/1/2026, 1:14:14 AM
Summary
The paper introduces Cost-Sensitive Neighborhood Aggregation (CSNA), a GNN layer designed for heterophilous graphs. CSNA uses per-edge learned routing to separate concordant and discordant messages, addressing the limitations of uniform spectral channels in adversarial-heterophily regimes. Theoretical analysis using a Contextual Stochastic Block Model (CSBM) demonstrates that cost-sensitive weighting can preserve label-aligned signal direction where standard mean aggregation fails. Empirical results show CSNA is competitive on adversarial-heterophily datasets but underperforms on informative-heterophily datasets, where per-edge routing provides no additional benefit.
Entities (5)
Relation Signals (3)
CSNA → uses → per-edge routing
confidence 100% · CSNA’s routing is per-edge: each edge receives an individualized routing weight based on the learned distance
CSBM → demonstrates → signal distortion
confidence 90% · Under a contextual stochastic block model we show that mean aggregation can reverse the label-aligned signal direction
CSNA → outperforms → GCN
confidence 85% · CSNA is competitive with state-of-the-art methods on adversarial-heterophily datasets where standard GNNs (GCN, GAT) perform poorly.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 this https URL .
Tags
Links
- Source: https://arxiv.org/abs/2603.24291v2
- Canonical: https://arxiv.org/abs/2603.24291v2
Trouble viewing inline? Open PDF directly →
Full Text
43,374 characters extracted from source content.
Expand or collapse full text
11institutetext: Computer Science Faculty, Technion — Israel Institute of Technology 11email: eweiss@campus.technion.ac.il 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/pw_+/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× 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 gijg_ij in a learned projection; an extended version adds a learned component hijh_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/pw_+/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|⋅d)O(|E|· d) per channel, but with fixed structure), while CSNA requires an additional O(|E|⋅d)O(|E|· 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 =(V,E)G=(V,E) be an undirected graph with n=|V|n=|V| nodes and feature matrix ∈ℝn×dX ^n× d. Each node i has a label yi∈1,…,Cy_i∈\1,…,C\. The edge homophily ratio is ℋ=|(i,j)∈E:yi=yj|/|E|H=|\(i,j)∈ E:y_i=y_j\|/|E|. In standard message-passing [4], node i’s representation at layer ℓ+1 +1 is: i(ℓ+1)=σ(∑j∈(i)αij(ℓ)j(ℓ)),h_i^( +1)=σ\! ( _j (i) _ij\,W^( )\,h_j^( ) ), (1) where (i)N(i) includes i itself, αij _ij are aggregation weights, and σ 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)(i,j) at layer ℓ , we compute a distance in a learned projection: gij(ℓ)=‖gi(ℓ)−gj(ℓ)‖2,g_ij^( )=\|W_g\,h_i^( )-W_g\,h_j^( )\|_2, (2) where g∈ℝd′×dW_g ^d × d is a learned projection matrix. Low gijg_ij indicates the endpoints are similar in the projected space (likely concordant); high gijg_ij indicates divergence (likely discordant). This is the only cost component in the default (lite) version of CSNA. Step 2: Concordance routing. The cost is converted to a soft concordance score: sij(ℓ)=σ(−gij(ℓ)τ)∈(0,1),s_ij^( )=σ\! ( -g_ij^( )τ )∈(0,1), (3) where τ>0τ>0 is a temperature parameter and σ is the sigmoid function. High concordance (low cost) routes the message toward the concordant channel; low concordance (high cost) routes it toward the discordant channel. Step 3: Dual-channel aggregation. Messages are routed through two channels with independent transformations: icon _i^con =∑j∈(i)s~ijconj(ℓ), = _j (i) s_ij\,W_con\,h_j^( ), (4) idis _i^dis =∑j∈(i)d~ijdisj(ℓ), = _j (i) d_ij\,W_dis\,h_j^( ), (5) where s~ij=softmaxj∈(i)(sij) s_ij=softmax_j (i)(s_ij), d~ij=softmaxj∈(i)(1−sij) d_ij=softmax_j (i)(1-s_ij), and con,dis∈ℝd′×dW_con,W_dis ^d × d are independent weight matrices. The concordant channel emphasizes likely same-class neighbors; the discordant channel processes likely different-class neighbors through a separate transformation. Step 4: Gated combination. The final output combines both channels with the ego representation via per-node gating: i(ℓ+1)=∑k∈con,dis,selfγk(i)⋅ik,h_i^( +1)= _k∈\con,dis,self\ _k(h_i)·h_i^k, (6) where iself=selfi(ℓ)h_i^self=W_self\,h_i^( ) and γ(i)=softmax(γ[icon‖idis‖iself])∈ℝ3γ(h_i)=softmax(W_γ[h_i^con\|h_i^dis\|h_i^self]) ^3. Extended variant: g+hg+h. An optional extension adds a learned cost component: fij(ℓ)=gij(ℓ)+hij(ℓ),wherehij(ℓ)=softplus(⊤[gi(ℓ)∥gj(ℓ)]),f_ij^( )=g_ij^( )+h_ij^( ), h_ij^( )=softplus (a [W_gh_i^( )\|W_gh_j^( )] ), (7) where [⋅∥⋅][·\|·] denotes vector concatenation, ∈ℝ2d′a ^2d is a learnable parameter vector, and fijf_ij replaces gijg_ij in Equation˜3. In our experiments, the extended variant wins clearly only on Wisconsin (84.1 vs. 79.6); on all other datasets the lite version performs comparably or better (Appendix˜0.A). We therefore present the lite version (gijg_ij only) as the default. Calibration regularization. When training with labels, we add a regularizer that penalizes cost overestimation on same-class edges: ℒcal=1|Etrain|∑(i,j)∈Etrain[ReLU(gij−[yi≠yj])]2,L_cal= 1|E_train| _(i,j)∈ E_train [ReLU(g_ij-1[y_i≠ y_j]) ]^2, (8) where EtrainE_train denotes edges between labeled nodes. The full objective is ℒ=ℒCE+λcalℒcalL=L_CE+ _cal\,L_cal, with λcal=0.1 _cal=0.1 fixed across all experiments. Note that gijg_ij and the binary indicator [yi≠yj]1[y_i≠ y_j] are on different scales; the regularizer acts as a soft penalty that directly shapes the routing signal, encouraging lower costs (and thus higher concordance) for same-class edges. Architecture details. We apply an input MLP before the first CSNA layer, add residual connections, and initialize the gate bias to [0,0,1][0,0,1] (favoring the ego channel so the model starts near MLP-like behavior). Self-loops are added before cost computation; they receive gii=0g_i=0, so ego information flows primarily through the concordant and self channels. The softmax normalization of concordance weights is performed per source node; we also tested per-destination normalization (more common in message-passing GNNs) and found no consistent difference across datasets. The CSNA layer is summarized in Algorithm 1. Algorithm 1 CSNA Layer (Lite Version) 0: Node features (ℓ)∈ℝn×dH^( ) ^n× d, edge index E, temperature τ 0: Updated features (ℓ+1)∈ℝn×d′H^( +1) ^n× d 1: for each edge (i,j)∈E(i,j)∈ E do 2: gij←‖gi−gj‖2g_ij←\|W_gh_i-W_gh_j\|_2 Pairwise distance in learned projection 3: sij←σ(−gij/τ)s_ij←σ(-g_ij/τ) Concordance score 4: end for 5: for each node i∈Vi∈ V do 6: icon←∑j∈(i)s~ijconjh_i^con← _j (i) s_ij\,W_conh_j Concordant channel 7: idis←∑j∈(i)d~ijdisjh_i^dis← _j (i) d_ij\,W_dish_j Discordant channel 8: iself←selfih_i^self _selfh_i Ego transform 9: i(ℓ+1)←∑kγk(i)⋅ikh_i^( +1)← _k _k(h_i)·h_i^k Gated combination 10: end for 4 Theoretical Analysis We analyze the advantage of cost-sensitive aggregation over mean aggregation in heterophilous settings using the contextual stochastic block model (CSBM) [16]. Our analysis uses the binary (C=2C=2) case for tractability; our experimental datasets have C=5C=5, and we discuss the multi-class extension in Appendix˜0.F. Importantly, the theorems below apply to any weighted aggregation scheme—they are not specific to the g+hg+h decomposition or the lite variant. Definition 1(Contextual Stochastic Block Model) A graph G is drawn from CSBM(n,2,p,q,μ)CSBM(n,2,p,q,μ) with n nodes in two equal-sized classes V+,V−V_+,V_-. Edges are drawn independently: probability p within classes, probability q between classes. Node features: i∼(yi,d)x_i ( μ_y_i,I_d), with +=+μ21 μ_+=+ μ2e_1 and −=−μ21 μ_-=- μ2e_1. The homophily ratio is ℋ=p/(p+q)H=p/(p+q). The heterophilous regime is q>pq>p, i.e., ℋ<1/2H<1/2. Theorem 4.1(Signal distortion under mean aggregation) Let ∼CSBM(n,2,p,q,μ)G (n,2,p,q,μ) with constant p,q∈(0,1)p,q∈(0,1) and equal class sizes. After one round of symmetrically normalized aggregation with self-loops, (1)=~H^(1)= AX, where ~=−1/2(+)−1/2 A=D^-1/2(A+I)D^-1/2, the expected class-mean representations satisfy: [¯+(1)−¯−(1)]=p−qp+q(+−)+O(1/n),E[ h_+^(1)- h_-^(1)]= p-qp+q( μ_+- μ_-)+O(1/n), (9) where ¯c(1) h_c^(1) is the mean representation of class c. The scaling factor λ=(p−q)/(p+q)λ=(p-q)/(p+q) is signed: when q>pq>p, it is negative, reversing the label-aligned signal direction. The magnitude |λ||λ| is attenuated (strictly less than 11) whenever q≠pq≠ p, and is minimized near p=qp=q. In the extreme heterophily limit q≫pq p, |λ||λ| approaches 11—strong heterophily distorts but does not collapse the signal. Proof Under the dense CSBM, di=Θ(n)d_i= (n), so the self-loop in +A+I contributes O(1/n)O(1/n) per node and does not affect the leading coefficient. For a node i∈V+i∈ V_+, same-class neighbors number ns(i)∼Bin(n/2−1,p)n_s(i) (n/2-1,p) and different-class neighbors nd(i)∼Bin(n/2,q)n_d(i) (n/2,q). At leading order: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =p+q++qp+q−+O(1/n)=p−qp+q⋅μ21+O(1/n), = pp+q μ_++ qp+q μ_-+O(1/n)= p-qp+q· μ2e_1+O(1/n), (10) where the O(1/n)O(1/n) term absorbs both the self-loop contribution and the concentration error (by Hoeffding’s inequality, ns(i)/din_s(i)/d_i concentrates around p/(p+q)p/(p+q) at rate O(1/n)O(1/ n), giving O(1/n)O(1/n) after averaging over n/2n/2 nodes per class). By symmetry and averaging: [¯+(1)−¯−(1)]=p−qp+q(+−)+O(1/n)E[ h_+^(1)- h_-^(1)]= p-qp+q( μ_+- μ_-)+O(1/n). ∎ Theorem 4.2(Cost-sensitive aggregation preserves signal direction) Under the same CSBM, suppose an aggregation scheme weights each edge (i,j)(i,j) by wijw_ij, with [wij|yi=yj]=w+E[w_ij|y_i=y_j]=w_+ and [wij|yi≠yj]=w−E[w_ij|y_i≠ y_j]=w_-, where w+>w−≥0w_+>w_-≥ 0. Then: [¯+(1)−¯−(1)]=pw+−qw−pw++qw−(+−)+O(1/n).E[ h_+^(1)- h_-^(1)]= p\,w_+-q\,w_-p\,w_++q\,w_-( μ_+- μ_-)+O(1/n). (11) The scaling factor is positive—preserving the original class direction—if and only if w+/w−>q/pw_+/w_->q/p. Proof Replacing uniform weights with w+w_+ and w−w_- in the proof of Theorem˜4.1: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =pw+pw++qw−++qw−pw++qw−−+O(1/n). = p\,w_+p\,w_++q\,w_- μ_++ q\,w_-p\,w_++q\,w_- μ_-+O(1/n). (12) Setting w+=w−=1w_+=w_-=1 recovers Theorem˜4.1. The numerator pw+−qw−>0p\,w_+-q\,w_->0 iff w+/w−>q/pw_+/w_->q/p. ∎ Remark 1(Applicability to CSNA) Theorem˜4.2 applies to CSNA’s concordant channel with wij=sijw_ij=s_ij. The condition s+/s−>q/ps_+/s_->q/p requires the cost function to assign sufficiently higher concordance to same-class edges; the calibration regularizer (Equation˜8) encourages this. Theorem˜4.2 is conditional: it shows what happens if the cost function achieves the separation, not that CSNA will learn it. Remark 2(Scope and limitations) (i) The CSBM analysis is for C=2C=2; experiments have C=5C=5. The qualitative conclusion carries over (Appendix˜0.F), but the quantitative bound changes. (i) Theorem˜4.2 bounds the class-mean difference, not classification accuracy: a sign-reversed but well-separated representation can be corrected by a downstream linear classifier. The theorems show that cost-sensitive weighting preserves the label-aligned signal direction where mean aggregation may reverse it; they do not prove improved classification in isolation. (i) The analysis covers a single layer; multi-layer interactions between evolving representations and the cost function are not analyzed. 5 Experiments 5.1 Datasets We evaluate on six heterophily benchmarks (Table 1). Texas, Wisconsin, and Cornell are webpage graphs from WebKB [10]. Chameleon and Squirrel are Wikipedia article networks [10]. Actor is a co-occurrence network from film databases [10]. We note that Chameleon and Squirrel have known data quality issues (duplicate nodes) [11]. Table 1: Dataset statistics. ℋH is the edge homophily ratio. Dataset Nodes Edges Features Classes ℋ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 5.2 Setup Baselines. We compare against: (1) MLP (no graph structure), (2) GCN [6], (3) GAT [14], (4) GraphSAGE [5], (5) H2GCN [16], (6) GPRGNN [3], and (7) ACM-GNN [8]. Protocol. We use 10 random 60%/20%/20% splits (seed 42). All methods are tuned over the same hyperparameter grid: learning rate ∈0.01,0.005∈\0.01,0.005\, hidden dimension ∈64,128∈\64,128\ on small datasets (Texas, Wisconsin, Cornell) and 64\64\ on large datasets (Actor, Chameleon, Squirrel) for computational efficiency. CSNA additionally tunes temperature τ∈0.1,0.5,1.0,2.0τ∈\0.1,0.5,1.0,2.0\. Tuning uses 3 validation splits on small datasets and 2 on large datasets. All models use 2 layers, dropout 0.5, Adam with weight decay 5×10−45× 10^-4, and early stopping (patience 50, max 300 epochs). We save the checkpoint with best validation accuracy and evaluate it once on test. We report classification accuracy (fraction of correctly labeled test nodes), averaged over 10 splits, with standard deviation reflecting split-to-split variability. CSNA here is the lite version (gijg_ij only, no sampling). Complete details in Appendix˜0.H. 5.3 Main Results Results are in Table 2. Table 2: Node classification accuracy (%) on heterophily benchmarks. All methods tuned over the same grid. Best in bold, second-best underlined. Method Texas Wisconsin Cornell Actor Chameleon Squirrel ℋH=0.09 ℋH=0.19 ℋH=0.13 ℋH=0.22 ℋH=0.23 ℋH=0.22 MLP 77.3± 4.6 83.7± 4.8 72.2± 3.6 35.0± 1.4 51.9± 1.8 34.8± 1.4 GCN 55.7± 9.9 50.6± 8.5 47.0± 8.7 27.3± 1.4 67.3± 1.7 53.4± 0.8 GAT 50.8± 9.8 51.4± 7.8 47.3± 5.8 28.0± 1.4 65.7± 2.2 50.4± 1.4 GraphSAGE 76.5± 6.8 75.9± 5.8 66.2± 7.7 34.1± 0.6 63.9± 2.1 45.8± 1.4 H2GCN 81.9± 4.2 82.4± 5.8 72.2± 4.2 35.6± 0.9 56.8± 2.7 35.0± 1.3 GPRGNN 77.8± 6.9 75.7± 7.7 58.6± 9.9 36.0± 0.8 65.0± 2.1 43.6± 1.8 ACM-GNN 77.3± 8.2 78.0± 4.4 68.6± 7.2 35.3± 1.2 65.9± 2.9 51.0± 1.8 CSNA (ours) 77.0± 8.3 79.6± 6.2 72.7± 4.3 35.7± 1.2 54.6± 2.7 37.8± 1.9 The results reveal a clear split between two types of heterophily benchmarks. Note that many differences across methods are within one standard deviation; we focus on patterns rather than strict mean rankings. Adversarial heterophily (Texas, Wisconsin, Cornell, Actor). On these datasets, cross-class edges are adversarial: aggregating neighbor features degrades classification. MLP is a strong baseline, and standard GNNs (GCN, GAT) perform poorly. H2GCN is the strongest method on Texas (81.9) and Wisconsin (82.4), where its ego-separated multi-hop design is effective. CSNA is competitive: it is statistically tied for first on Cornell (72.7 vs. H2GCN 72.2 and MLP 72.2, all within ∼ 0.5p) and on Actor (35.7 vs. GPRGNN 36.0 and H2GCN 35.6, all within ∼ 0.4p—well within one standard deviation). On Texas and Wisconsin, CSNA trails H2GCN but remains within one standard deviation of the other heterophily-aware methods. Informative heterophily (Chameleon, Squirrel). On these datasets, heterophilous structure itself carries useful signal. GCN remains the top performer (67.3 on Chameleon, 53.4 on Squirrel), but ACM-GNN is close on both datasets (65.9 and 51.0, within 1–2p of GCN), while CSNA (54.6 and 37.8) and H2GCN (56.8 and 35.0) trail substantially. CSNA’s cost-based routing cannot distinguish “harmful” from “useful” heterophilous edges—methods that apply uniform spectral filters (ACM-GNN, GPRGNN) or standard aggregation (GCN) handle this regime better. This distinction—between adversarial and informative heterophily—is increasingly recognized [8, 11] and suggests that no single approach dominates all heterophily regimes. CSNA’s cost semantics make the distinction explicit: on adversarial datasets, learned costs successfully separate edge types (Fig. 2); on informative datasets, they cannot. Figure 2: Learned concordance scores sijs_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+hg+h) variant; similar separation is observed with the lite version. Comparison with ACM-GNN. ACM-GNN and CSNA share the dual-channel-plus-gating architecture but differ in routing granularity. On adversarial-heterophily datasets, their accuracy is comparable: CSNA leads on Cornell (+4.1p) and Actor (+0.4p), while ACM-GNN edges ahead on Wisconsin. The clearest separation appears on informative-heterophily datasets, where ACM-GNN’s uniform spectral channels are substantially more effective: ACM-GNN outperforms CSNA by 11.3p on Chameleon and 13.2p on Squirrel. This suggests that when heterophilous edges carry uniformly useful signal, fixed spectral filters preserve it better than per-edge routing, which may over-differentiate edges that are equally informative. Routing quality as a diagnostic. To quantify the cost function’s ability to discriminate edge types, we compute the AUC of the concordance score sijs_ij as a binary classifier for same-class vs. different-class edges. On the adversarial-heterophily datasets, AUC ranges from 0.48 (Texas) to 0.83 (Wisconsin), while on informative-heterophily datasets it is 0.55–0.57 (Chameleon, Squirrel). Interestingly, CSNA’s accuracy gain over GCN does not correlate simply with AUC: Texas has near-random AUC (0.48) yet CSNA outperforms GCN by 21p, while Wisconsin has the highest AUC (0.83) and the largest gain (+29p). This suggests that CSNA’s benefit comes not only from edge-type separation but also from the dual-channel architecture and gating mechanism, which can learn useful representations even when the cost function’s discrimination is weak. On informative-heterophily datasets, both the low AUC and the poor accuracy confirm that the cost function cannot usefully decompose the neighborhood. Ablation highlights. We tested four CSNA variants in a factorial design (Appendix˜0.A): the extended model (g+hg+h) vs. the lite default (g only), each with and without stochastic edge sampling [12]. The extended variant wins clearly only on Wisconsin (84.1 vs. 79.6); on all other datasets the lite version matches or exceeds it. Edge sampling slightly reduces accuracy (1–3p) but provides regularization and scaling benefits. These results motivate presenting the lite version without sampling as the default. 6 Discussion Limitations—and what they reveal. • Homophilous graphs. CSNA underperforms GCN by 4–11p on Cora, CiteSeer, and PubMed (Appendix˜0.B). The per-edge routing is not justified when standard aggregation suffices; this is expected, since the cost function has little to separate when most edges are already same-class. • Informative heterophily. CSNA underperforms GCN on Chameleon (by 12.7p) and Squirrel (by 15.6p), and trails ACM-GNN by 11–13p on both. Rather than a mere negative result, this failure is diagnostic: it identifies datasets where heterophilous edges are uniformly informative and per-edge routing over-differentiates edges that carry equally useful signal. Fixed spectral filters (ACM-GNN) and standard aggregation (GCN) better preserve this signal. • Computational cost. CSNA is 3–10× slower than GCN (Appendix˜0.D), though it uses fewer parameters. • Comparison with ACM-GNN. CSNA shares the dual-channel-plus-gating design with ACM-GNN [8]. On adversarial-heterophily datasets the methods achieve comparable accuracy; on informative-heterophily datasets ACM-GNN is clearly superior. The per-edge routing is a meaningful architectural difference whose value is regime-dependent. 7 Conclusion We presented CSNA, a GNN layer that computes pairwise distance in a learned projection and uses it to soft-route messages through concordant and discordant channels, with per-node gating. The key architectural difference from the closely related ACM-GNN is per-edge routing rather than uniform spectral channels—a finer-grained mechanism that is competitive on adversarial-heterophily datasets but underperforms on informative-heterophily datasets where uniform filters are more effective. Our theoretical analysis provides a clean condition (w+/w−>q/pw_+/w_->q/p) under which cost-sensitive weighting preserves the label-aligned signal direction that mean aggregation may reverse. The results operationalize the adversarial/informative heterophily distinction: CSNA’s cost function achieves meaningful edge-type separation only in the adversarial regime, serving as a diagnostic for the nature of heterophily in a given graph. The clearest open question is whether per-edge routing can be adapted to the informative-heterophily regime—possibly by learning to leverage rather than suppress cross-class signal. References [1] U. Alon and E. Yahav (2021) On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), Cited by: §2. [2] D. Bo, X. Wang, C. Shi, and H. Shen (2021) Beyond low-frequency information in graph convolutional networks. In AAAI Conference on Artificial Intelligence, Cited by: §2. [3] E. Chien, J. Peng, P. Li, and O. Milenkovic (2021) Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations (ICLR), Cited by: §1, §2, §5.2. [4] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl (2017) Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), Cited by: §3.1. [5] W. L. Hamilton, R. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2, §5.2. [6] T. N. Kipf and M. Welling (2017) Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), Cited by: §1, §2, §5.2. [7] Q. Li, Z. Han, and X. Wu (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI Conference on Artificial Intelligence, Cited by: §2. [8] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X. Chang, and D. Precup (2022) Revisiting heterophily for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2, §5.2, §5.3, 4th item. [9] K. Oono and T. Suzuki (2020) Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), Cited by: §2. [10] H. Pei, B. Wei, B. Chang, Y. Lei, and B. Yang (2020) Geom-GCN: geometric graph convolutional networks. In International Conference on Learning Representations (ICLR), Cited by: §1, §5.1. [11] O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova (2023) A critical look at the evaluation of GNNs under heterophily: are we really making progress?. In International Conference on Learning Representations (ICLR), Cited by: §5.1, §5.3. [12] Y. Rong, W. Huang, T. Xu, and J. Huang (2020) DropEdge: towards deep graph convolutional networks on node classification. In International Conference on Learning Representations (ICLR), Cited by: Appendix 0.D, §5.3. [13] J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein (2022) Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations (ICLR), Cited by: §2. [14] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph attention networks. In International Conference on Learning Representations (ICLR), Cited by: §1, §2, §5.2. [15] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu (2021) A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 32 (1), p. 4–24. Cited by: §1. [16] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra (2020) Beyond homophily in graph neural networks: current limitations and effective designs. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §1, §2, §4, §5.2. Appendix Appendix 0.A CSNA Variant Comparison We compare four CSNA variants in a factorial design: full (g+hg+h) vs. lite (g only) × edge sampling vs. no sampling. Results are in Table 3. Table 3: CSNA variant comparison: accuracy (%) on all six datasets. “Full” includes both gijg_ij and hijh_ij; “lite” uses gijg_ij only. “Samp” applies edge sampling during training. 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 Discussion. The full variant (g+hg+h) wins clearly only on Wisconsin (84.1 vs. 79.6), where the learned component hijh_ij provides a useful correction beyond observed divergence. On all other datasets, the lite version matches or exceeds the full version, suggesting that feature divergence gijg_ij alone is a sufficient routing signal. Since hijh_ij introduces additional learnable parameters without a clear consistent advantage, it risks overfitting—particularly on the small datasets in our benchmark suite. We therefore use the lite version (gijg_ij only) as the default. Edge sampling slightly hurts accuracy on most datasets (1–3p) but may act as a regularizer on Actor (36.3 vs. 35.6 for the full variant). The accuracy cost of sampling is modest, making it a viable strategy for scaling to larger graphs. Appendix 0.B Homophily Benchmarks To understand CSNA’s behavior across the homophily spectrum, we evaluate on three standard homophilous datasets (Table 4). Table 4: Accuracy (%) on homophilous benchmarks. CSNA underperforms GCN by 4–11p. Method Cora CiteSeer PubMed GCN 77.9 65.7 76.0 CSNA 67.0 56.3 72.2 CSNA underperforms GCN by 10.9p on Cora, 9.4p on CiteSeer, and 3.8p on PubMed. This is expected: on homophilous graphs, standard aggregation is already effective, and the per-edge routing overhead adds complexity without benefit. The cost function cannot improve on uniform aggregation when most edges are already same-class. These results suggest CSNA’s per-edge routing overhead is not justified on homophilous graphs, where standard aggregation already performs well. Appendix 0.C Gate Weight Analysis Table 5 shows the average gate weights at layer 0, revealing dataset-dependent routing strategies. Table 5: Average gate weights γ across nodes (layer 0). Dataset γcon _con γdis _dis γself _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 The gate weights reveal three distinct strategies: • Self-dominant (Wisconsin, Actor): The model ignores graph structure entirely (γself=1.0 _self=1.0), effectively reducing to MLP. This is consistent with CSNA matching MLP-level accuracy on these datasets. The collapse to MLP-like behavior is itself informative: it indicates that on these datasets, the cost function does not find a useful decomposition of the neighborhood, and the gating mechanism correctly learns to ignore the graph channels. • Mixed (Texas, Cornell): The model uses a combination of ego and graph channels. On Cornell, the discordant channel receives substantial weight (γdis=0.28 _dis=0.28), indicating that different-class neighbor information is actively processed. • Graph-dominant (Chameleon, Squirrel): The model relies entirely on graph channels, with the discordant channel dominant (γdis=0.66 _dis=0.66 and 0.860.86 respectively). Ironically, these are the datasets where CSNA underperforms GCN, suggesting the discordant channel’s separate transformation does not capture the useful heterophilous signal as effectively as GCN’s uniform aggregation. Appendix 0.D Runtime and Parameter Comparison Table 6: Training time (seconds per split) and parameter count. All on 8-core CPU. 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 CSNA 1 34 37 205 144K CSNA is 3–10× slower than GCN due to the per-edge distance computation. On the largest dataset (Squirrel, 198K edges), a single split takes ∼ 205 seconds vs. 62 for GCN. However, CSNA uses fewer parameters (144K vs. 219K for GCN on Texas) because the projection gW_g is shared between cost computation and the channels. For scaling to larger graphs, edge sampling [12] is a natural option; our ablation (Appendix˜0.A) shows it costs only 1–3p in accuracy. Appendix 0.E Proof Details 0.E.1 Detailed Proof of Theorem 4.1 Consider the binary CSBM with n nodes, two equal-sized classes, constant edge probabilities p,q∈(0,1)p,q∈(0,1) with q>pq>p. Let V+=i:yi=+1V_+=\i:y_i=+1\ and V−=i:yi=−1V_-=\i:y_i=-1\, each of size n/2n/2. Features: i∼(yi,d)x_i ( μ_y_i,I_d), with +=+μ21 μ_+=+ μ2e_1 and −=−μ21 μ_-=- μ2e_1. For a node i∈V+i∈ V_+: ns(i)∼Bin(n/2−1,p)n_s(i) (n/2-1,p) and nd(i)∼Bin(n/2,q)n_d(i) (n/2,q), with di=1+ns(i)+nd(i)d_i=1+n_s(i)+n_d(i) (including the self-loop). Since [di]=Θ(n)E[d_i]= (n), the self-loop contributes O(1/n)O(1/n) per node and vanishes at leading order. By Hoeffding’s inequality, ns(i)/din_s(i)/d_i concentrates around p/(p+q)p/(p+q) at rate O(1/n)O(1/ n). At leading order: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =p+q++qp+q−+O(1/n)=p−qp+q⋅μ21+O(1/n). = pp+q μ_++ qp+q μ_-+O(1/n)= p-qp+q· μ2e_1+O(1/n). (13) By symmetry, [i(1)|yi=−1]=p−qp+q⋅(−μ21)+O(1/n)E[h_i^(1)|y_i=-1]= p-qp+q·(- μ2e_1)+O(1/n). Averaging over n/2n/2 nodes per class (the O(1/n)O(1/ n) per-node errors average to O(1/n)O(1/n)): [¯+(1)−¯−(1)]=p−qp+q(+−)+O(1/n).∎E[ h_+^(1)- h_-^(1)]= p-qp+q( μ_+- μ_-)+O(1/n). (14) 0.E.2 Detailed Proof of Theorem 4.2 The weighted aggregation assigns expected weight w+w_+ to same-class edges and w−w_- to different-class edges. The self-loop contributes O(1/n)O(1/n) as in Theorem 4.1 and does not affect the leading coefficient. At leading order: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =pw+pw++qw−++qw−pw++qw−−+O(1/n). = p\,w_+p\,w_++q\,w_- μ_++ q\,w_-p\,w_++q\,w_- μ_-+O(1/n). (15) Averaging over classes: [¯+(1)−¯−(1)]=pw+−qw−pw++qw−(+−)+O(1/n).E[ h_+^(1)- h_-^(1)]= p\,w_+-q\,w_-p\,w_++q\,w_-\,( μ_+- μ_-)+O(1/n). (16) Setting w+=w−=1w_+=w_-=1 recovers Theorem 4.1. Sign preservation: The scaling factor is positive iff pw+>qw−p\,w_+>q\,w_-, i.e., w+/w−>q/pw_+/w_->q/p. ∎ Appendix 0.F Multi-Class Extension The binary CSBM analysis extends to C>2C>2 classes as follows. In a C-class CSBM with intra-class probability p and uniform inter-class probability q: • The expected fraction of same-class neighbors is p/(p+(C−1)q)=ℋp/(p+(C-1)q)=H. • The between-class scatter matrix BS_B has rank C−1C-1. • Under mean aggregation, each pairwise class-mean difference is scaled by the signed factor (p−q)/(p+(C−1)q)(p-q)/(p+(C-1)q), which is negative when q>pq>p (signal direction reversal). • Under cost-sensitive aggregation, the factor becomes (pw+−qw−)/(pw++(C−1)qw−)(p\,w_+-q\,w_-)/(p\,w_++(C-1)q\,w_-). Sign preservation (positive factor) requires w+/w−>q/pw_+/w_->q/p. The qualitative conclusion is unchanged: cost-sensitive weighting preserves the label-aligned signal direction where mean aggregation may reverse it. Appendix 0.G Within-Class Scatter Theorem˜4.2 bounds the class-mean difference but not within-class scatter tr(W)tr(S_W). For a node i∈V+i∈ V_+: i(1)−¯+(1)=∑j∈(i)wij(j−[j|yj])+(edge-composition terms).h_i^(1)- h_+^(1)= _j (i)w_ij(x_j-E[x_j|y_j])+(edge-composition terms). (17) The first term involves feature noise averaged over di=Θ(n)d_i= (n) neighbors (variance O(d/n)O(d/n)). Under cost-sensitive weighting, same-class neighbors receive higher weight, so the aggregated representation is dominated by same-class features. The within-class scatter is bounded by [tr(W)]≤nd/deffE[tr(S_W)]≤ n\,d/d_eff, where deff=[∑jwij2]−1d_eff=E[ _jw_ij^2]^-1. A complete formal bound requires tracking the correlation between the random graph and the cost function (which depends on features), making a tight bound technically challenging. Appendix 0.H Reproducibility Hardware. All experiments on a single machine with an 8-core CPU and 32GB RAM. Software. Python, PyTorch, PyTorch Geometric. Source code: https://github.com/eyal-weiss/CSNA-public. Splits. 10 random 60/20/20 train/validation/test splits per dataset, generated with seed 42. Training. Early stopping with patience 50, maximum 300 epochs. Model checkpoint: best validation accuracy. Test evaluation: once, using saved checkpoint. Tuning protocol. All methods tuned over the same grid: • Learning rate: 0.01,0.005\0.01,0.005\ • Hidden dimension: 64,128\64,128\ on small datasets (Texas, Wisconsin, Cornell); 64\64\ on large datasets (Actor, Chameleon, Squirrel) • CSNA additionally: τ∈0.1,0.5,1.0,2.0τ∈\0.1,0.5,1.0,2.0\ Best configuration selected by mean validation accuracy over 3 tuning splits (small datasets) or 2 tuning splits (large datasets), with tuning epochs capped at 200 (small) or 150 (large). Final results reported on all 10 splits with full 300-epoch training.