arXiv:2605.00725cs.LG2026-05

提出统一框架提升拓扑神经网络表达能力,可更好区分复杂结构。

Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks

论文配图:Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks
图 1 · 摘自论文原文
  • 构建组合复形上的统一颜色细化框架,融合四类邻域信息。
  • 理论证明仅用上下邻域即可保持完整区分能力,显著降低计算开销。
  • 设计轻量模型CCIN,在合成与真实数据上表现媲美主流方法。

拓扑神经网络已成为建模超越成对关系的高阶结构(如超图、单纯复形和胞腔复形)的有效工具。然而,现有基于Weisfeiler-Leman的表达能力分析通常针对不同结构域,依赖特定邻域系统,难以在统一形式下比较。本文提出组合复形Weisfeiler-Leman(CCWL)框架,定义于组合复形之上,通过边界、余边界、下邻接和上邻接四类结构邻域实现拓扑颜色细化。在指定提升映射下,CCWL可模拟多种领域特定的WL型细化,为拓扑消息传递提供统一理论基准。进一步研究邻域充分性问题,证明在显式覆盖条件下,仅使用下/上邻域桥接信息的简化细化仍能保持全四邻域CCWL的区分能力。基于此理论结果,我们实例化出简化框架为组合复形同构网络(CCIN)。在合成与真实世界基准上的实验表明,CCIN性能优于或媲美代表性图与拓扑神经网络基线。消融实验与资源效率分析进一步验证了所提下/上邻域设计的有效性。

原文摘要 · Abstract (English)

Topological neural networks have emerged as effective tools for modeling higher-order relational structures beyond pairwise graphs, including hypergraphs, simplicial complexes, and cell complexes. However, existing Weisfeiler-Leman type expressivity analyses are typically developed on different structural domains and rely on domain-specific neighborhood systems, making their expressive powers difficult to compare within a common formalism. In this paper, we introduce the Combinatorial Complex Weisfeiler-Leman (CCWL) framework, a unified expressive power refinement defined on combinatorial complexes. By exploiting the ability of combinatorial complexes to represent both set-type relations and part-whole hierarchies, CCWL performs topological color refinement through four structural neighborhoods: boundary, co-boundary, lower adjacency, and upper adjacency. We show that, under specified lifting maps, CCWL can simulate several domain-specific WL-type refinements, thereby providing a common theoretical baseline for analyzing topological message passing. We further study the neighborhood sufficiency problem and prove that, under explicit coverage conditions, a reduced refinement using only lower- and upper-adjacent bridge information preserves the distinguishing power of the full four-neighborhood CCWL refinement. Guided by this theoretical result, we instantiate the reduced refinement as the Combinatorial Complex Isomorphism Network (CCIN). Experiments on synthetic and real-world benchmarks demonstrate that CCIN achieves competitive performance against representative graph and topological neural network baselines. Ablation studies and resource-efficiency analyses further support the effectiveness of the proposed lower/upper-neighborhood design.

拓扑神经网络表达能力组合复形高效模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。