基于粒球的多粒度自适应超图表示学习

# 基于粒球的多粒度自适应超图表示学习
来源：https://arxiv.org/html/2609.05574
关一凡\*所属机构：重庆邮电大学
所属机构：重庆邮电大学 金元源
所属机构：重庆邮电大学 徐高杰
所属机构：重庆邮电大学 张旭、连晓雨、刘毅、王毅、王伟

###### 摘要

超图表示学习旨在通过构建同时连接多个节点的超边来捕捉图中的高阶信息。这些超边适应图的拓扑特征，有助于提取多粒度下的高阶关系。大多数现有工作依赖预定义的定义来生成超边，忽略了图拓扑结构的多样性和超边的多粒度特性，从而限制了其有效且自适应地发现高阶关系以及高效处理复杂结构信息的能力。为解决这一局限，我们提出一种新颖的框架——多粒度超图表示学习（MGHRL）。MGHRL引入自适应粒球超图生成策略，通过粒球的自适应分裂在多粒度层级上生成超边，从而基于图的拓扑结构有效捕捉高阶关系。此外，我们提出了一种包含多个子网络的多粒度超图网络，通过分层可逆连接捕获不同粒度超边的特征并进行整合。实验结果表明，MGHRL在基准数据集上显著优于基线模型。

## 1 引言

传统图仅捕捉成对关系，这限制了其对现实世界系统（如社交网络或生物信息学）中常见高阶交互的建模能力（Kipf and Welling \(2017\) (https://arxiv.org/html/2609.05574#bib.bib9); Hamilton et al\. \(2017\) (https://arxiv.org/html/2609.05574#bib.bib10); Wu et al\. \(2020\) (https://arxiv.org/html/2609.05574#bib.bib11)）。为克服这一限制，研究者提出了超图结构，利用超边同时连接多个节点，从而更好地建模复杂关系（Zhou et al\. \(2006a\) (https://arxiv.org/html/2609.05574#bib.bib21); Battaglia et al\. \(2018\) (https://arxiv.org/html/2609.05574#bib.bib12)）。

早期工作（Ramadan et al\. \(2004\) (https://arxiv.org/html/2609.05574#bib.bib13); Zhou et al\. \(2006b\) (https://arxiv.org/html/2609.05574#bib.bib15)）使用超图建模此类结构，但捕捉这些交互存在技术挑战（Madan et al\. \(2011\) (https://arxiv.org/html/2609.05574#bib.bib16); Li et al\. \(2010\) (https://arxiv.org/html/2609.05574#bib.bib17)），即使可观察，许多数据集的超图版本（Newman \(2004\) (https://arxiv.org/html/2609.05574#bib.bib18); Sarigöl et al\. \(2014\) (https://arxiv.org/html/2609.05574#bib.bib19)）也常未公开。为解决此问题，研究者采用启发式方法（Feng et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib28); Gao et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib33)）生成超边，如k跳邻居超图和k最近邻超图。超图神经网络（HGNNs）（Feng et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib28); Gao et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib33); Wang et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib29)）使用这些超边进行节点与超边之间的信息传递。尽管有效，但先前方法通常依赖预定义规则，忽略了图拓扑结构的多样性以及超边的多粒度特性。

参考图片说明图1：传统固定粒度与本文提出的自适应多粒度超图生成对比。\((a)\) 传统方法（如基于三角形）施加固定超边，忽略了层次结构。\((b)\) 我们的方法通过检测节点内聚性自适应分裂超边，从粗到细粒度细化以捕捉更丰富的拓扑结构。在现实超图场景中，超边由节点内聚群组之间的关系形成，这些关系跨越多个粒度层级。图1 (https://arxiv.org/html/2609.05574#S1.F1)对比了传统固定粒度和我们的自适应方法。传统方法（如基于三角形）忽略了层次结构。相反，我们的方法通过检测节点内聚性动态分裂超边，从粗到细粒度细化以捕捉更丰富的拓扑结构。例如，\(h_{2}^{1}\)反映了最佳粒度，而\(h_{1}^{1}\)可被分裂为\(h_{1}^{2}\)和\(h_{2}^{2}\)以获得更精细的结构洞察。

建模超边的多粒度特性是一项非平凡任务，主要由于两个关键挑战：（1）超边生成需要自适应性，因为内聚节点群组通常具有固定规则无法捕捉的复杂拓扑结构。受粒球计算（Granular-Ball Computing）中多粒度区分（Xia et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib31); Xie et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib26)）的启发，我们提出通过粒球的自适应分裂在多粒度层级上生成超边，从而基于图的拓扑结构有效捕捉高阶关系。（2）超图建模通常不区分粒度。现有大多数方法主要关注节点与超边之间的信息传播，忽略了不同粒度超边各自独特的学习能力。这一疏忽显著限制了模型有效捕捉和表示多层次关系模式的能力。

为解决上述问题，我们提出一种新颖的多粒度超图表示学习（MGHRL）框架。MGHRL引入自适应粒球超图生成策略，通过自适应分裂逐步构建多粒度超图。该方法以从粗到细的方式生成超图，确保生成的超边准确反映节点之间的关系以及整体图的拓扑结构（Liu et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib24); Kang et al\. \(2022\) (https://arxiv.org/html/2609.05574#bib.bib25)）。此外，我们提出了一种新颖的多粒度超图网络，包含多个子网络（称为列）。每个列从不同的图副本中独立学习，参数解耦。这使得每个列能够独立地从不同粒度的超边中提取特征表示，同时通过列之间的多层可逆连接逐步积累和精炼信息。

总之，本工作做出以下贡献：

- • 我们强调了超边多粒度特性在超图表示学习中的关键作用。
- • 我们提出了一个新颖的MGHRL框架，通过粒球的自适应分裂在多粒度层级上生成超边。此外，我们引入了多粒度超图网络，该网络独立地从不同粒度的超边中提取特征表示，并通过这些超边之间的多层可逆连接逐步精炼信息。
- • 我们在八个真实数据集上进行了大量实验，MGHRL有效提升了超图表示学习的性能。

## 2 相关工作

图神经网络（GNNs）在图结构数据的表示和分析方面取得了巨大进展（Kipf and Welling \(2017\) (https://arxiv.org/html/2609.05574#bib.bib9); Veličković et al\. \(2018\) (https://arxiv.org/html/2609.05574#bib.bib14); Hamilton et al\. \(2017\) (https://arxiv.org/html/2609.05574#bib.bib10)）。传统的图卷积网络（GCNs）通过局部卷积聚合相邻节点的特征，在半监督任务中表现出色（Kipf and Welling \(2017\) (https://arxiv.org/html/2609.05574#bib.bib9)）。在GCNs的基础上，图注意力网络（GATs）引入了注意力机制，在聚合过程中优先考虑重要邻居（Veličković et al\. \(2018\) (https://arxiv.org/html/2609.05574#bib.bib14)），而GraphSAGE（Hamilton et al\. \(2017\) (https://arxiv.org/html/2609.05574#bib.bib10)）通过为大规模图采样固定大小的邻域实现归纳学习。图同构网络（GINs）（Xu et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib22)）使用健壮的聚合函数来区分不同的图结构。尽管有效，但传统图仅限于捕捉成对关系，这限制了它们建模高阶交互的能力（Kipf and Welling \(2017\) (https://arxiv.org/html/2609.05574#bib.bib9); Hamilton et al\. \(2017\) (https://arxiv.org/html/2609.05574#bib.bib10)）。

为克服传统图结构的局限性，超图（Ramadan et al\. \(2004\) (https://arxiv.org/html/2609.05574#bib.bib13); Zhou et al\. \(2006b\) (https://arxiv.org/html/2609.05574#bib.bib15)）成为一种更具表达力的图结构，用于表示高阶关系，其中超边同时连接多个节点。超图神经网络（HNNs）的最新进展（Feng et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib28); Kang et al\. \(2022\) (https://arxiv.org/html/2609.05574#bib.bib25)）增强了复杂高阶关系的表示，解决了传统GNNs在捕捉超出简单成对关系的连接方面的局限性（Ding et al\. \(2020\) (https://arxiv.org/html/2609.05574#bib.bib30)）。HyperGCN（Yadati et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib27)）利用团扩展技术将真实超图转换为简单图，从而能够使用标准的图卷积操作。然而，在许多领域，获取超边数据面临技术挑战（Madan et al\. \(2011\) (https://arxiv.org/html/2609.05574#bib.bib16); Li et al\. \(2010\) (https://arxiv.org/html/2609.05574#bib.bib17)），并且此类数据通常不公开。HGNN（Feng et al\. \(2019\) (https://arxiv.org/html/2609.05574#bib.bib28)）基于距离或相似性，将与中心节点最近的k个节点连接起来构建超边，并引入适用于超图结构的谱卷积。它聚合节点特征生成超边表示，然后用于更新相邻节点特征，使模型能够学习超图内复杂的关系模式。UniGCN和UniGAT（Huang and Yang \(2021b\) (https://arxiv.org/html/2609.05574#bib.bib23)）通过将图和超图神经网络集成到一个统一框架中，代表了重大进展。这种集成能够更全面地理解信息在网络结构中的传播，提高了模型在不同数据表示之间传输和分析信息的能力。此外，HGNN+（Gao et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib33)）使用k跳邻居构建超边，并引入了一个用于高阶和多模态分析的通用框架，该框架捕捉每个模态内的潜在相关性并有效地跨模态整合它们。ED-HNN（Wang et al\. \(2023\) (https://arxiv.org/html/2609.05574#bib.bib29)）利用星型扩展和消息传递神经网络来有效逼近连续等变超图扩散算子，使模型能够捕捉复杂的高阶关系并提高在异配超图上的性能。HyperNAS（Lin et al\. \(2024\) (https://arxiv.org/html/2609.05574#bib.bib38)）进一步引入了一种超图神经架构搜索方法，该方法定义了专门的搜索空间，使用可微搜索算法，并根据超图结构感知准则优化架构。然而，先前方法通常依赖预定义的标准来生成超边，忽略了图结构的多样性和超边的多粒度特性。

## 3 方法

图2 (https://arxiv.org/html/2609.05574#S3.F2)展示了所提出的框架，包含自适应粒球超图生成（AGHG）策略和多粒度超图网络（MGHN）。AGHG初始化粗粒度粒球，并根据节点特征和拓扑结构通过二分分裂自适应地细化它们。MGHN采用多列架构与可逆连接，整合跨粒度的信息，增强对复杂超图结构的建模。

### 3.1 自适应粒球超图生成

图2：我们提出的MGHRL框架概述。它主要包含两个模块：自适应粒球超图生成过程，以及多粒度超图网络架构。本节将详细解释AGHG。为形式化该方法，我们引入粒球方法，该方法将图细化为多个子域。

###### 定义 1\.

拓扑粒球分解。令\(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{A})\)表示一个基于图的结构域，赋予度量\(d:\mathcal{V}\times\mathcal{V}\rightarrow\mathbb{R}_{\geq 0}\)，其中\(\mathbf{X}\)表示节点特征，\(\mathbf{A}\)是邻接矩阵。该度量在\(\mathcal{V}\)上诱导出一个拓扑\(\tau_{d}\)，其中基本邻域由闭度量球定义。

粒球\(\widetilde{\mathcal{G}}_{i}\)被定义为\((\mathcal{V},d)\)中的一个闭球：
\[\widetilde{\mathcal{G}}_{i}=\left\{v\in\mathcal{V}\mid d\left(v,c_{i}\right)\leq r_{c_{i}}\right\},\]
(1)
其中\(c_{i}\in\mathcal{V}\)是中心节点，\(r_{c_{i}}\)是选择的半径，用于保持局部连通性和语义内聚性。\(\mathcal{G}\)的粒球分解是此类子空间的有限集合：
\[\widetilde{\mathbb{G}}=\left\{\left(\widetilde{\mathcal{V}}_{i},\tilde{\mathcal{E}}_{i}\right)\right\}_{i=1}^{n},\]
(2)
其中族\(\{\widetilde{\mathcal{V}}_{i}\}_{i=1}^{n}\)构成\(\mathcal{V}\)的一个拓扑覆盖。

我们的目标是找到一个覆盖\(\widetilde{\mathbb{G}}\)，使得子空间结构在拓扑上一致且在语义上有意义，形式化为以下优化：
\[\min_{\widetilde{\mathbb{G}}}\sum_{i=1}^{n}\frac{1}{Q\left(\widetilde{\mathcal{G}}_{i}\right)}+\lambda\cdot n,\]
(3)
其中\(Q\left(\widetilde{\mathcal{G}}_{i}\right)\)表示子图\(\widetilde{\mathcal{G}}_{i}\)的拓扑或结构质量。

如图2 (https://arxiv.org/html/2609.05574#S3.F2)所示，初始图\(\mathcal{G}\)被视为一个粗粒度粒球，并通过自适应二分分裂进行迭代分解。在每一步\(t\)，一个粒球\(\widetilde{\mathcal{G}}^{t}\)根据结构和特征相似性被分割为更细的子球\(\{\widetilde{\mathcal{G}}^{t+1}\}\)。这个过程产生一个拓扑覆盖。