Intro

传统图聚类的局限

图聚类不仅要看结构（比如谁连着谁），还要考虑节点的属性相似性（比如两个用户兴趣标签是否接近）。
现实中很多图是高阶关系图（超图），比如一篇论文的多个作者组成一个“超边”，这不是简单的“点-点”连接关系。

为什么现有方法不够好？

现有的带属性超图聚类方法主要靠 矩阵分解（如NMF），非常依赖预设聚类数，而且计算代价大，不能扩展到大规模数据。
有些方法试图用随机游走传播属性信息，但“为什么属性也要传播”？逻辑站不住脚。

文章的目标

设计一个既高效又高质量的带属性超图聚类方法，满足：

• 不需要提前知道聚类数；
• 能同时整合拓扑结构 + 属性信息；
• 可扩展到大图；
• 可用于现有的对比学习方法。

---

实验的流程

以下是从超图中生成一个聚类的流程，文章依据这个流程进行详细展开：

---

Step1: 处理两部分的输入数据

Step1.1 获取属性相似矩阵 $S_A$

按照定义，输入一个代带属性的超图 $H(V,E,\text{att})$，属性函数 $att$ 自己给定。

使用属性图(Attribute graph)，通过计算每个节点与其他节点的属性相似度，得到属性相似矩阵 $S_A$(Attribute Similarity Matrix，ASM)。
为了衡量超图中节点之间的属性相似性，本文采用了经典的 K 近邻（K-Nearest Neighbor, KNN） 搜索方法。
基本步骤如下：
1.输入：

• 属性超图 $H(V,E,att)$
  • $V$ 表示节点集合
  • $E$ 表示超边集合
  • $att(v)$ 表示节点 $V$ 的属性向量
• 参数：$K$ 表示每个节点要保留的最相似邻居个数

---

2.计算过程：

• 对于每个节点 $v\in V$，找到其最相似的 $K$ 个邻居，记为：
  $$N_K(V)$$

• 使用余弦相似度来计算两个节点属性的相似性
  $$f(att(v_i),att(v_j))=\frac{att(v_i)\cdot att(v_j)}{\Vert att(v_i)\Vert \Vert att(v_j)\Vert }$$

• 构建一个稀疏矩阵，对于任意两个节点 $v_i$ , $v_j\in V$，定义：
  $$M[i,j]=\{\begin{array}{ll}f(att(v_i),att(v_j)),& \text{如果 }{v}_j\in N_K(v_i)\\ & \\ 0,& \text{otherwise}\end{array}$$

• 归一化：由于初始属性相似度矩阵 $M$ 通常不是对称矩阵，为了适用于聚类算法中的随机游走过程，AHCKA 构造了一个对称的属性相似度矩阵 $S_A$：
  $$S_A=M+M^{\top },S_A\in R^{n\times n}$$
  其中 $M[i,j]$ 表示节点 $v_i$ 与 $v_j$ 之间的属性余弦相似度，仅当 $v_j$ 是 $v_i$ 的KNN邻居时才非零。
  #精确计算KNN图的时间复杂度是 $n^2$，研究人员常采用快速的近似 KNN 算法。属性图是基于 $S_A$ 构建的加权图。

---

Step1.2 进行"超图随机游走"，得到结构相似矩阵 $S_T$

超图跳转矩阵 $T$

在普通图中，随机游走就是从一个节点走到相邻节点。但在超图中，一个超边可以连接多个节点，所以游走过程分成三步：

1. 从节点跳到超边：$T_V$

• $T_V$表示节点跳到超边的概率矩阵
• 每一行表示一个节点 $v$；
• 每一列表示一个超边 $e$；
• $T_V[i,e]：$节点 $v_i$跳到它关联的某条超边 $e$ 的概率，公式表达如下：
  $$T_V[i,e]=\frac{H[e,i]}{{\sum }_{e^{\prime }}H[e^{\prime },i]}=\frac{1}{\mathrm{deg}(v_i)}\text{ 如果 }{v}_i\in e$$
  其中：$\mathrm{deg}(v_i)$ 表示节点 $V_i$参与的超边数。

---

2. 从超边到节点：$T_E$
   $$T_V[i,e]=\frac{H[e,j]}{{\sum }_{j^{\prime }}H[e,j^{\prime }]}=\frac{1}{|e|}\text{ 如果 }{v}_j\in e$$
   其中：$|e|$ 表示超边 $e$ 包含的节点数量。

---

3. 最终构造出超图跳转矩阵 $T：$
   $$T=T_V\times T_E$$

---

结构相似矩阵 $S_T$ (Transition Similarity Matrix，TSM)：

$$S_T=\alpha \sum _{\ell =0}^{\gamma }(1-\alpha {)}^{\ell }{T}^{\ell }$$

其中：

• $\alpha$：随机游走中"重启"的概率；
• $\gamma =2$：最多考虑 $2$ 跳；
• $T$：超图跳转矩阵；
• $T^{\ell }$：从一节点到另一节点正好经过 $\ell$ 步的概率。

这个方法保留了超图的高阶连接特性。

---

Step2: 融合结构和属性得到 相似度矩阵(ISM) $S$

Step2.1 归一化矩阵 $S_A$ 和 $S_T$

$S_A$ 和 $S_T$ 的数值范围可能不同，比如一个稀疏一个稠密，为了让两者融合时做出"对等的贡献"，我们需要对每个矩阵按行归一化，也就是概率归一化。
归一化公式：
$${\hat{S}}_T[i,j]=\frac{S_T[i,j]}{{\sum }_k{S}_T[i,k]},{\hat{S}}_A[i,j]=\frac{S_A[i,j]}{{\sum }_k{S}_A[i,k]}$$

这些归一化结果满足每一行的和为 1，即：
$$\sum _j\widehat{S_T}[i,j]=1，\sum _j\widehat{S_A}[i,j]=1$$

---

Step2.2 融合归一化后的矩阵

我们将归一化后的两个矩阵做矩阵乘法，表示在结构路径上传播属性相似性，或者反之。
$$S^{\prime }={\hat{S}}_T\cdot {\hat{S}}_A$$

---

Step2.3 平衡融合结果

如果有些路径过强（可能一端结构或属性权重太大），直接相乘会放大差异，所以我们取平方根作为“soft balance”，来平衡高低值之间的差距，使得 ISM 更稳定、更泛化。
开方公式：
$$S[i,j]=\sqrt{S^{\prime }[i,j]}$$
最终得到的 $S$ 就是 Integrated Similarity Matrix，可用于 Louvain 聚类或对比学习嵌入。

---

Step3 基于ISM进行聚类

本文设计了一个新的聚类质量评估函数： Integrated Multi-hop Modularity（IMM）。

为什么不使用经典的模块度？

经典图聚类中的模块度 $Q$ 定义如下：
$$Q=\frac{1}{2m}\sum _{i,j}\left(A[i,j]-\frac{d_i{d}_j}{2m}\right)\delta (c_i,c_j)$$

其中：

• $A[i,j]$：邻接矩阵；
• $\delta (c_i,c_j)=1$，当 i, j 同属于一个簇；
• 缺点：
  • 只考虑了“结构”（即邻接矩阵）；
  • 容易产生 “分辨率限制”：小簇会被合并成大簇，错过细粒度结构；
  • 需要手动设定聚类数。

---

IMM定义

IMM 直接基于综合相似度矩阵 $S$，其核心思想是：比较簇内的“实际相似度”和“期望相似度”之间的差值，越大说明簇划分越显著。

公式：
$$IMM(C)=\sum _{C_i\in C}\left[\frac{{\sum }_{i,j\in C_i}S[i,j]}{{\sum }_{i,j}S[i,j]}-{\left(\frac{{\sum }_{i\in C_i,j\in V}S[i,j]}{{\sum }_{i,j}S[i,j]}\right)}^2\right]$$

第一项表示簇内实际观察到的相似度比例：
$$\frac{{\sum }_{i,j\in C_i}S[i,j]}{{\sum }_{i,j}S[i,j]}$$

第二项表示在随机条件下，预期的簇内相似度（基于节点度）：
$$(\frac{{\sum }_{i\in C_i,j\in V}S[i,j]}{{\sum }_{i,j}S[i,j]}{)}^2$$

---

使用Louvain算法优化IMM

IMM 是可被 Louvain 聚类算法直接最大化的目标函数。Louvain 是一种快速、贪心的模块度最大化方法，流程为：

• 每个节点初始化为一个独立簇；
• 每次移动一个节点到临近簇，若增加模块度则保留；
• 多次合并簇形成层次结构；
• 可自适应选择聚类数，不需要预设 $k$

---

Step4 对超图进行"稀疏化加速"，简化计算：

问题背景：$S_T$ 计算的开销大

在之前的Step1中，我们通过AHRC的公式计算拓扑相似度矩阵：
$$S_T=\alpha \sum _{\ell =0}^{\gamma }(1-\alpha {)}^{\ell }{T}^{\ell }$$

存在问题：如果 $T$ 是稠密的，$T^2$、$T^3$ 就更稠密;
panning Tree 是连接图中所有节点的最小边集，不形成环。如果图不是连通的，就对每个连通分量生成一棵生成树，这就叫 Spanning Forest（生成森林）。

---

解决办法：Kruskal算法

1.输入跳转矩阵 $T$，将其对称化：
$$T_{sym}=T+T^T$$

2.重复 $\tau$ 次以下过程：

• 使用 Kruskal 最小生成树算法（MST），在 $T_{sym}$中找出一棵“权重最大”的生成森林 $F_i$;
• 每次生成森林后，把这些边从 $T_{sym}$中移除，避免重复；

3.合并所有森林，得到一个重要边组成的稀疏子图。
$$F=F_1\cup F_2\cup ...\cup F_n$$

4.用这个稀疏结构去计算新的 $T^{\prime }$

#举例：稀疏化就像是只考虑每个人最信任的几位朋友（权重大的连接），依然能保留网络的大致结构，但大大减少计算量。

---

Step5 (可选) 将AHRC用于对比学习

功能扩展

在前面的步骤中，AHRC 已经完成了传统意义上的聚类任务：将节点划分为结构 + 属性相似的簇。但在现代图学习领域，节点表示学习也是核心目标，特别是在对比学习方法（如 GRACE、TriCL）中广泛使用。

可以利用AHRC构造出的融合相似度矩阵 $S$，进一步增强GNN对比学习效果。

作者设计了一个新的 GNN 模块 —— AHR Layer，在对比学习模型中作为 Encoder 的一部分。

---

AHR Layer

1. 单节点表示更新形式：
   z v ( i ) = f ( z v ( i − 1 ) , { z u ( i − 1 ) ∣ ( u , v ) ∈ E S } ) z^{(i)}_v = f\left(z^{(i-1)}_v, \{z^{(i-1)}_u \mid (u,v) \in E_S\}\right) zv(i)​=f(zv(i−1)​,{zu(i−1)​∣(u,v)∈ES​})

• $z^{(i)}：$第 $i$ 层后节点 $v$ 的表示；
• $(u,v)\in E_S：$表示节点对 $u,v$在融合图 $S$ 中有连接；
• 实际上就是基于 AHRC 得到的相似图进行传播。

---

2. 矩阵形式（GNN 层传播）：
   $$Z^{(i)}=\sigma \left(D^{-1}B{Z}^{(i-1)}{W}^{(i)}\right)$$

• $B:$二值化后的 $S$ 矩阵；
• $D:$$B$的度矩阵；
• $W^{(i)}:$第 $i$ 层的可学习权重；
• $\sigma :$激活函数；

将 AHRC 构造的融合相似度矩阵 $S$，当作“属性+结构”统一图结构输入到 GNN 对比学习模型中，从而提升嵌入表示质量和最终聚类性能。

---

补充知识

概念

AHC: 带属性超图聚类，是将超图划分为簇，在同一个簇中的节点具有相同的高连通性和同质属性；
AHRC: 用于聚类的带属性超图表示；
Cluster: 图论中，cluster（簇）通常指的是一组相互连接较紧密的节点，与外部节点的连接相对较少。
Clustering: 聚类，是一种无监督学习方法，它的目标是把一组对象（如节点、文档、图像）分成若干“簇”(cluster)，使得同一组内的对象尽可能相似，不同组之间的对象尽可能不同；
Clique: 最大的完全子图，全连接的完全子图；
AGC: Attributed Graph Clustering带属性的图聚类；
最大生成森林(MSF)：最大生成森林 是一个加权无向图中的一个子图，它是所有连通分量的最大生成树的集合。共有 n−c 条边 (n：节点数，c：连通分量数）

---

涉及的内容