按边路由消息能提升异质图分类,但仅在特定情况下有效。
Cost-Sensitive Neighborhood Aggregation for Heterophilous Graphs: When Does Per-Edge Routing Help?
- 基于学习投影计算边距离,软性分配消息到同质/异质通道
- 在6个基准上,对抗性异质图表现优于主流方法
- 路由价值可作为判断异质类型是否适合细粒度建模的指标
现有研究区分两种异质性模式:对抗性异质中跨类边会稀释标签信号并损害分类;信息性异质中异质结构本身携带有用信号。本文提出成本敏感邻域聚合(CSNA),通过学习投影计算边间距离,将消息软性路由至同质与异质通道,并分别进行独立变换。在上下文随机块模型下,我们证明均值聚合会在异质性下反转标签对齐信号方向,而当 $w_+/w_- > q/p$ 时,成本敏感加权可保留正确符号。在六个基准数据集上使用统一调参,CSNA在对抗性异质图(Texas、Wisconsin、Cornell、Actor)上表现与最先进方法相当,但在信息性异质图(Chameleon、Squirrel)上表现较差——这正是边级路由无法利用有效分解的场景。该模式本身即为发现:成本函数分离边类型的性能,可作为异质性范式诊断工具,揭示何时细粒度路由有价值,何时无需。
原文摘要 · Abstract (English)
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 .
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。