Structural entropy guided hyperbolic graph transformer for graph partitioning

doi:10.1016/j.asoc.2026.116367

Structural entropy guided hyperbolic graph transformer for graph partitioning

2026-09-07

0

PRE

AI

DOI：10.1016/j.asoc.2026.116367

原文链接

原文求助

摘要

En 中文

图划分是一个经典的组合优化问题，旨在将图划分为等大小的子组，并使边割数量最小化。近年来，如图神经网络等图嵌入方法在该领域取得了显著成功。然而，现有方法在欧几里得空间中提取图嵌入，这固有地限制了它们捕获图划分至关重要的层次结构的能力。此外，这些方法通常采用归一化割作为损失函数，这主要强调跨分区连接，仅对细化社区内部结构提供弱监督。为解决这些问题，我们提出了一种端到端的图划分框架，用于揭示图中的层次结构并将结构上紧密的节点分配到同一分区。首先，我们利用双曲图Transformer在双曲空间中学习节点表示。由于双曲几何具有指数级体积增长特性，因此它能以远低于欧几里得空间的失真度编码层次结构。此外，我们设计了用于图划分的可微分残差结构熵损失，引导模型发现自然分区。我们证明结构熵和传统归一化割可以联合优化用于图划分。实验结果表明，我们的模型优于各种划分基线。

Structural entropy guided hyperbolic graph transformer for graph partitioning

摘要

期刊

机构

引用论文