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: 96%
Last extracted: 3/26/2026, 2:16:51 AM
Summary
The paper introduces Cost-Sensitive Neighborhood Aggregation (CSNA), a GNN layer designed for heterophilous graphs. CSNA uses a learned projection to compute pairwise edge distances, which are then used to soft-route messages through concordant and discordant channels. The authors demonstrate that CSNA effectively handles adversarial-heterophily regimes by preserving class-discriminative signal, while noting that it underperforms on informative-heterophily datasets where uniform spectral channels are more effective.
Entities (5)
Relation Signals (3)
CSNA → iscomparedto → ACM-GNN
confidence 100% · ACM-GNN, the most closely related prior work... CSNA shares the dual-channel-plus-gating architecture
CSNA → uses → CSBM
confidence 95% · Under a contextual stochastic block model we show that cost-sensitive weighting preserves class-discriminative signal
CSNA → outperforms → GCN
confidence 90% · CSNA is competitive with state-of-the-art methods on adversarial-heterophily datasets
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 cost-sensitive weighting preserves class-discriminative signal where mean aggregation provably attenuates it, provided $w_+/w_- > q/p$. 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.24291v1
- Canonical: https://arxiv.org/abs/2603.24291v1
Trouble viewing inline? Open PDF directly →
Full Text
42,566 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 cost-sensitive weighting preserves class-discriminative signal where mean aggregation provably attenuates it, provided w+/w−>q/pw_+/w_->q/p. 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 cost-sensitive weighting preserves class signal where mean aggregation degrades it, provided w+/w−>q/pw_+/w_->q/p (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 degradation under mean aggregation) Let ∼CSBM(n,2,p,q,μ)G (n,2,p,q,μ) with q>pq>p. After one round of mean aggregation (1)=~H^(1)= AX, where ~=−1/2(+)−1/2 A=D^-1/2(A+I)D^-1/2 is the symmetrically normalized adjacency, the expected between-class separation satisfies: [‖¯+(1)−¯−(1)‖2]‖+−‖2=(p−qp+q)2+O(1n), E [\| h_+^(1)- h_-^(1)\|^2 ]\| μ_+- μ_-\|^2= ( p-qp+q )^2+O\! ( 1 n ), (9) where ¯c(1) h_c^(1) is the mean representation of class c. When q>pq>p, the leading factor is strictly less than 1; when q≫pq p, it approaches zero. Proof 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). Under mean aggregation: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =p+q++qp+q−+O(1/n)=p−qp+q++O(1/n), = pp+q μ_++ qp+q μ_-+O(1/ n)= p-qp+q μ_++O(1/ n), (10) where the O(1/n)O(1/ n) term follows from concentration of ns(i)/din_s(i)/d_i around p/(p+q)p/(p+q) (Hoeffding’s inequality, di=Θ(n)d_i= (n)). By symmetry, [i(1)|yi=−1]=p−qp+q−+O(1/n)E[h_i^(1)|y_i=-1]= p-qp+q μ_-+O(1/ n). Averaging over n/2n/2 nodes per class and applying the law of large numbers: [‖¯+(1)−¯−(1)‖2]=(p−qp+q)2‖+−‖2+O(1/n).∎E [\| h_+^(1)- h_-^(1)\|^2 ]= ( p-qp+q )^2\| μ_+- μ_-\|^2+O(1/ n). (11) Theorem 4.2(Signal preservation under cost-sensitive aggregation) Under the same CSBM, suppose an aggregation scheme weights 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)‖2]‖+−‖2=(pw+−qw−pw++qw−)2+O(1/n). E [\| h_+^(1)- h_-^(1)\|^2 ]\| μ_+- μ_-\|^2= ( p\,w_+-q\,w_-p\,w_++q\,w_- )^2+O(1/ n). (12) This exceeds the mean-aggregation factor (p−qp+q)2 ( p-qp+q )^2 if and only if w+/w−>q/pw_+/w_->q/p. Proof Replacing uniform weights with w+w_+ (same-class) and w−w_- (different-class) in the proof of Theorem˜4.1: [i(1)|yi=+1] [h_i^(1)|y_i=+1] ∝pw+++qw−−+O(1/n). p\,w_+ μ_++q\,w_- μ_-+O(1/ n). (13) The between-class scatter follows by substituting p→pw+p→ p\,w_+ and q→qw−q→ q\,w_-: [‖¯+(1)−¯−(1)‖2]=(pw+−qw−pw++qw−)2‖+−‖2+O(1/n).E [\| h_+^(1)- h_-^(1)\|^2 ]= ( p\,w_+-q\,w_-p\,w_++q\,w_- )^2\| μ_+- μ_-\|^2+O(1/ n). (14) The condition w+/w−>q/pw_+/w_->q/p is equivalent to pw+>qw−p\,w_+>q\,w_-, ensuring the same-class contribution dominates. ∎ 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. However, Theorem˜4.2 is conditional: it shows what happens if the cost function achieves good separation, not that CSNA will learn such separation. 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 between-class scatter only, not within-class scatter (Appendix˜0.G). (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\. CSNA additionally tunes temperature τ∈0.1,0.5,1.0,2.0τ∈\0.1,0.5,1.0,2.0\. 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 mean accuracy over 10 splits. We report classification accuracy (fraction of correctly labeled test nodes), averaged over the 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 75.9± 5.0 76.1± 6.1 67.8± 7.7 31.3± 1.7 51.5± 2.8 37.3± 2.8 GPRGNN 78.1± 8.0 78.6± 5.1 70.0± 6.7 34.2± 0.7 58.5± 2.8 38.4± 2.3 ACM-GNN 75.9± 6.3 80.0± 6.1 69.5± 5.1 33.5± 1.6 59.3± 2.0 41.6± 1.3 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: 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. CSNA is competitive with the best methods: it achieves the highest mean accuracy on Cornell and Actor (though the margins over MLP are within one standard deviation), and is within 1–4 points of the best on Texas and Wisconsin. GPRGNN and ACM-GNN are also strong on these datasets. Informative heterophily (Chameleon, Squirrel). On these datasets, heterophilous structure itself carries useful signal. GCN and GAT substantially outperform all heterophily-specific methods (CSNA, H2GCN, GPRGNN, ACM-GNN). This is consistent with prior observations [11, 8]: methods that downweight cross-class edges lose the informative signal. CSNA’s cost-based routing cannot distinguish “harmful” from “useful” heterophilous edges. 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 show a similar overall pattern. CSNA slightly outperforms ACM-GNN on Cornell (+3.2p) and Actor (+2.2p), while ACM-GNN is ahead on Chameleon (+4.7p) and Squirrel (+3.8p). The accuracy differences between CSNA and ACM-GNN are generally within one standard deviation, suggesting that the per-edge granularity does not consistently translate to measurable accuracy gains over uniform spectral channels. The methods differ mainly in mechanism, not in overall performance level. 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). Rather than a mere negative result, this failure is diagnostic: it identifies datasets where heterophilous edges are uniformly informative and no per-edge decomposition can improve on uniform aggregation. The pattern—success on adversarial heterophily, failure on informative heterophily—is itself a contribution, as it operationalizes the regime distinction through CSNA’s cost semantics. • Computational cost. CSNA is 3–10× slower than GCN (Appendix˜0.D), though it uses fewer parameters. • Similarity to ACM-GNN. CSNA shares the dual-channel-plus-gating design with ACM-GNN [8]. The per-edge routing is a meaningful architectural difference, but accuracy gains over ACM-GNN are not consistently significant. 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, in our experiments, yields comparable accuracy at higher computational cost. Our theoretical analysis provides a clean condition (w+/w−>q/pw_+/w_->q/p) under which cost-sensitive weighting improves over mean aggregation. The clearest open question is whether per-edge routing can be adapted to the informative-heterophily regime—where CSNA currently fails—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 We provide the complete derivation with explicit concentration bounds. Consider the binary CSBM with n nodes, two equal-sized classes, intra-class edge probability p, and inter-class edge probability 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), so di=ns(i)+nd(i)d_i=n_s(i)+n_d(i). By Hoeffding’s inequality: Pr[|ns(i)di−p+q|>ϵ]≤2exp(−2ϵ2di), \! [ | n_s(i)d_i- pp+q |>ε ]≤ 2 \! (-2ε^2d_i ), (15) and since [di]=(n/2−1)p+(n/2)q=Θ(n)E[d_i]=(n/2-1)p+(n/2)q= (n), we have ns(i)/di=p/(p+q)+Op(1/n)n_s(i)/d_i=p/(p+q)+O_p(1/ n). Under mean aggregation: i(1) _i^(1) =1di∑j∈(i)j=ns(i)di¯+(i)+nd(i)di¯−(i). = 1d_i _j (i)x_j= n_s(i)d_i x_+(i)+ n_d(i)d_i x_-(i). (16) Taking expectations: [i(1)|yi=+1] [h_i^(1)|y_i=+1] =p+q++qp+q−+O(1/n) = pp+q μ_++ qp+q μ_-+O(1/ n) (17) =p−qp+q⋅μ21+O(1/n). = p-qp+q· μ2e_1+O(1/ n). (18) 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). The class means ¯c(1) h_c^(1) concentrate at rate O(1/n)O(1/ n): [‖¯+(1)−¯−(1)‖2]=(p−qp+q)2μ2+O(1/n).E\! [\| h_+^(1)- h_-^(1)\|^2 ]= ( p-qp+q )^2μ^2+O(1/ n). (19) Since ‖+−‖2=μ2\| μ_+- μ_-\|^2=μ^2, the multiplicative attenuation is (p−qp+q)2 ( p-qp+q )^2. ∎ 0.E.2 Detailed Proof of Theorem 4.2 The weighted aggregation assigns weight wijw_ij to each edge. For i∈V+i∈ V_+: i(1)∝∑j∈(i)wijj.h_i^(1) _j (i)w_ij\,x_j. (20) Taking expectations: [i(1)|yi=+1] [h_i^(1)|y_i=+1] ∝[ns(i)]⋅w+⋅++[nd(i)]⋅w−⋅−+O(1/n) [n_s(i)]· w_+· μ_++E[n_d(i)]· w_-· μ_-+O(1/ n) (21) ∝pw+++qw−−+O(1/n) p\,w_+ μ_++q\,w_- μ_-+O(1/ n) (22) =pw+−qw−2μ1+O(1/n). = p\,w_+-q\,w_-2\,μ\,e_1+O(1/ n). (23) By the same concentration argument: [‖¯+(1)−¯−(1)‖2]=(pw+−qw−pw++qw−)2μ2+O(1/n).E\! [\| h_+^(1)- h_-^(1)\|^2 ]= ( p\,w_+-q\,w_-p\,w_++q\,w_- )^2μ^2+O(1/ n). (24) Comparing with mean aggregation: cost-sensitive weighting improves when |pw+−qw−pw++qw−|>|p−qp+q|, | p\,w_+-q\,w_-p\,w_++q\,w_- |> | p-qp+q |, (25) which holds iff w+/w−>q/pw_+/w_->q/p (when q>pq>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 attenuated by (p−qp+(C−1)q)2 ( p-qp+(C-1)q )^2. • Under cost-sensitive aggregation with w+/w−>q/pw_+/w_->q/p, the same improvement applies to each pairwise difference. The qualitative conclusion is unchanged: cost-sensitive weighting preserves between-class scatter better than uniform weighting when w+/w−>q/pw_+/w_->q/p. Appendix 0.G Within-Class Scatter Theorem˜4.2 bounds between-class scatter 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). (26) 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\ • 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. Final results reported on all 10 splits.