用于有符号超图的光谱聚类方法

《Neurocomputing》：Spectral clustering methods for signed hypergraphs

　　李明伟|王云平|宋佳琪|齐兴琴
山东大学数学与统计学院，中国山东省威海市264209

**摘要**
作为数据挖掘领域新引入的结构，带符号的超图能够同时描绘个体与其所属群体之间的友好或敌对关系，这种数据表示形式比带符号的网络或超图更为通用。在复杂网络分析中，图划分或图聚类是一个经典且重要的优化问题，其目标是找到这样的群体：同一群体中的个体彼此非常相似，而不同群体中的个体则彼此不同。尽管已经有很多关于普通带符号图或无符号超图的聚类研究，但专为带符号超图设计的聚类算法却非常少。因此，为带符号超图设计聚类方法是一个非常紧迫的研究课题。在本文中，我们在为划分目标与不同核矩阵对应的二次优化问题之间建立坚实的数学基础后，提出了一种针对这种新数据结构——带符号超图的谱聚类方法。广泛的实验表明，直接应用于带符号超图的谱划分方法优于将带符号超图降级为带符号网络或普通超图后获得的谱划分结果，这也验证了将这种新数据结构引入数据挖掘领域的必要性。

**引言**
随着互联网驱动的数字化和智能化的快速发展，对复杂系统及大规模数据之间关系的研究日益深入。基于图论的建模方法在许多应用场景中提供了简单有效的解决方案。复杂网络研究领域逐渐发展起来，能够通过节点和边的结构有效地表示和分析各种复杂系统[1][2]。由于传统图结构在模拟复杂系统中个体间关系方面的局限性，人们衍生出了两种新的数据形式：带符号网络和超图。带符号网络引入了边的符号（正或负），使网络能够更准确地模拟现实世界中的复杂关系，如喜好与厌恶、合作与竞争[3]。超图扩展了传统图的概念，允许一条边连接多个节点（数量可以超过两个），从而捕捉高阶交互关系[4][5]。如果同一超边中的多个节点对该超边持有不同的态度，就提出了称为带符号超图的更精确的数据模型，在这种模型中，超边中的每个节点对该超边都有一个“正（+）”或“负（-）”的符号。这一概念最初由Shi等人在1992年为解决超大规模集成电路（VLSI）设计中的约束路径最小化（CVM）问题提出[6]。直到1999年，Shi和Brzozowski才对带符号超图进行了更深入的研究，提出了平衡带符号超图的概念，并对其结构进行了初步描述[7]。近年来，随着大数据技术的发展和数据挖掘的进步，新数据结构的获取和使用变得越来越普遍，相关研究也受到了广泛关注[8]。作为一种创新的图结构，带符号超图结合了带符号网络和超图的特点，能够更准确地表示和分析包含正面和负面关系以及高阶交互的复杂系统。它在现实世界中有许多应用。例如，在餐厅评价中，对同一家餐厅给出相同评价的顾客可以形成一条超边。传统的（无符号）超图忽略了顾客对餐厅的个别情感（正面/负面）。但一个顾客可能会“推荐”这家餐厅（即给出正面评价），而另一个顾客可能会“批评”它（即给出负面评价）。忽略符号会导致关键信息的丢失。带符号超图通过在超边中的节点成员关系上添加符号标签来解决这个问题。再举一个例子，议会成员总是对法案进行投票。对同一法案投票的成员可以形成一条超边。如果一名成员支持该法案，可以将其建模为正的节点-超边关联；否则，可以将其建模为负的节点-超边关联。传统的无符号超图忽略了节点与超边之间关系的定性方面，可能导致不准确甚至错误的数据挖掘结果，而带符号超图可以克服这一限制。

在复杂网络分析中，社区结构是一个核心概念。它指的是由具有相似特征或功能的节点以及紧密连接的边组成的子图结构[9]。社区检测或网络划分有助于深入探索网络的固有信息和特征，揭示网络中的相似群体结构及其动态演化机制[10]。例如，在推荐系统中，可以根据用户的特征和偏好将用户聚类到不同的社区中，从而为同一社区内的用户提供定制化的推荐。目前已经有许多用于社区检测的算法，例如基于模块度优化的算法[11]或随机游走算法[12]，这些算法也分别被扩展到了带符号网络[13]和超图[14][15]。近年来，基于神经网络和深度学习的聚类和社区检测算法逐渐流行起来。Wang等人[16]提出了一个自校正聚类框架（Self-CC），以克服聚类算法中的误差累积问题。Teng等人分别将图神经网络框架应用于多层网络[17]和动态网络[18]，有效地嵌入和学习节点特征，从而完成了社区检测。2025年，Xie等人[19]提出了一种新颖的K-hop超图神经网络（KHGNN），提高了神经网络的学习能力，并在节点分类任务中表现优异。

值得一提的是，根据网络划分的目标，即同一子组中的节点具有密集的连接，而不同子组中的节点具有稀疏的连接，网络划分问题可以转化为求解某些矩阵的特征值问题，这通常被称为谱划分方法[20]。2006年，Zhou等人[21]将谱划分方法扩展到了超图。Kunegis等人[22]在2010年、Chiang等人[23]在2012年提出了带符号网络的谱划分理论。最近，Du等人[24]给出了带符号超图上的模块度定义，并提出了一种基于模块度优化的社区检测算法，但他们对带符号超图的定义与我们的不同。在[24]中，带符号超图的符号是定义在超边上，而不是节点-超边关联上。但这表明符号问题正在吸引研究人员的关注。

与针对普通图划分的大量研究相比，专为带符号超图设计的聚类算法非常少。据我们所知，只有Han等人在2023年提出了一种基于遗传算法的带符号超图划分方法[25]。目前尚未探索有多少现有的聚类算法可以扩展到带符号超图。由于考虑带符号超图时聚类的目标发生了变化，现有的聚类方法不能直接应用于带符号超图。因此，在本文中，我们将提出基于谱方法的带符号超图划分（或聚类）算法，并提供相关的数学证明和仿真实验来证明这些谱方法的有效性。

本文的结构如下：第2节给出了带符号超图和划分指标的相关定义。第3节提出了这些新的带符号超图谱划分方法并提供了相关证明。第4节进行了相关实验并展示了实验结果。第5节给出了本文的结论。

**术语**
带符号超图可以用三元组表示，其中V表示顶点集，E表示超边集，每条超边e属于V的子集，f是赋予顶点-超边对符号的关联函数。对于一个具有V个顶点和E条超边的带符号超图，设A为关联矩阵，其中每个元素a_ij编码了顶点v和超边e之间的带符号关系。a_ij=1表示顶点v和超边e之间存在正关联，a_ij=0表示负关联，a_ij=2表示无关联。

**带符号超图的双分优化目标**
如前所述，我们为双分引入了一些平衡和不平衡的度量标准。类似于一般图的最优目标，我们也可以为带符号超图定义比率割和比率关联[29]，其中“比率”用于避免极端大小不平衡的分割。

**定义4 带符号超图的正面/负面比率割**
设P和Q是带符号超图的两个子集。正面比率割定义为：
\[
\frac{|P| + |Q|}{|P||Q|} \geq \lambda
\]
其中|P|和|Q|分别是子集P和Q中的节点数。

**定义5 带符号超图的正面/负面比率关联**
设P和Q是带符号超图的两个子集。负面比率关联定义为：
\[
\frac{|P| - |Q|}{|P||Q|} \geq \lambda
\]

**实验**
在本节中，我们首先介绍数据集（真实的和生成的），并介绍几种用于比较的基线核矩阵，然后介绍评估标准。将通过详细的实验结果来展示这些谱划分方法的效率。

在本文中，所有实验的计算机配置是一致的。处理器为AMD Ryzen 7 8845H w/ Radeon 780M Graphics（3.80 GHz），内存为32.0 GB。

**讨论与结论**
在这项工作中，我们通过计算每条超边中平衡/不平衡的节点对来构建图划分的目标，其中超边的权重和大小都被简化了。然而，如果考虑这些因素，则需要相应调整定义3中的节点对指标。例如，a_ij将被定义为：
\[
a_ij = \frac{w_e}{|e|} \cdot \frac{n_e}{|P| + |Q|}
\]
其中w_e是超边e的权重，n_e是超边e中的节点数，|P|和|Q|分别是子集P和Q中的节点数。相应地，邻接矩阵也需要调整以适应新的定义。

**作者贡献声明**
李明伟：撰写——原始草案，验证，软件，方法论，概念化。
王云平：软件，资源，数据整理。
宋佳琪：监督，形式分析。
齐兴琴：撰写——审稿与编辑，监督，项目管理，方法论，概念化。

**利益冲突声明**
作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。

**致谢**
本研究得到了中国国家自然科学基金（项目编号：12471330）和山东省自然科学基金（项目编号：ZR2025MS71）的支持。
李明伟于2022年在中国山东大学数学与统计学院获得学士学位，目前正在同一学院攻读硕士学位。他的研究兴趣包括复杂网络中的聚类算法和社区检测。