局部社区发现（五）：超图上的局部图聚类
难以置信这个系列居然还连载到第五章。局部社区发现是图数据挖掘的一种技术，对于给定的节点，局部社区发现旨在找到一个包含给定节点子图，在不少下游任务如图像语义分割、图神经网络中被广泛应用。本文将介绍如何将局部社区发现技术推广到超图上，介绍一篇来自WWW2021的论文：
（答应我，一定要先看完本系列的 第四章 再看本文好吗~可以先收藏本文再去看第四章，以防后续找不到捏）
广义图割问题
在讨论超图局部社区发现之前，我们先来回顾一下局部社区发现的优化问题描述形式：
- 对外隔离 ：局部社区与外界连边较少
- 规模较小 ：局部社区应当是规模较小的子图
考虑图 G=(V,E) ，假设 S \subset V 是局部社区的节点集合，优化对外隔离这个性质其实就是求最小割问题（这里的 \textbf{x} 用于指示节点在局部社区内的概率， B 是图的关联矩阵），即：
\begin{matrix} min. & cut(S) ＝ ||B\textbf{x}||_1 \\ s.t. & \textbf{x} \geq 0 \end{matrix}
接着为了保证规模较小，我们可以在上述问题的基础上添加一个对节点度的惩罚项，保证局部社区尽可能不选择大度节点，进而保证局部社区规模较小：
\begin{matrix} min. & ||Bx||_1 + \textbf{d} \textbf{x} \\ s.t. & \textbf{x} \geq 0 \end{matrix}
最后我们考虑连边权重 \textbf{w}^T ，为惩罚项添加一个松弛比例 \kappa ，并将1范数求绝对值的过程抽象为一个损失函数 l ，就得到了广义图割问题（可以理解为局部社区发现的优化问题描述）：
\begin{matrix} min. & \textbf{w}^T l(Bx) + \kappa \textbf{d} \textbf{x} \\ s.t. & \textbf{x} \geq 0 \end{matrix}
不过我们如何将它推广到超图上呢？
注意到，超图和图的区别在于连边，图的连边能够关联两个节点，而超图的连边（即超边）可以关联多个节点，因此超边可以理解为是节点的集合，即 e \in V
在超图上做局部社区发现，一种直观的思路是： 将超图转换（规约）为图 ，保留超图上割和度的性质，仍然用解决广义图割的技术来解决超图上局部社区发现的问题。
那么我们应该遵循怎样的规约方式，才能保证图保留超图上的割和度的性质呢？
当当当，这里我直接给出答案，正如下图所示，一种可行的规约方式是 gadget展开 ：即为每个超边设置两个辅助节点D和d，并添加一条辅助连边 D \rightarrow d ，接着将超边的所有节点指向D，而d指向所有超边节点
超边分割函数与超图规约
我们自然会问，为什么这种规约方式能够保留超图上的性质呢？
注意到，超图割与度都与超边分割函数有关，即：
cut_H(S)=\sum_{e \in E}f_e(e \cap S)
d_i = \sum_{e:i \in e}f_e(\{ i \})
假如规约后的图能够遵循超边分割函数的性质，那这种规约自然也能保留超图割与度的性质
最常见的超边分割函数是基于势（cardinality-based）的，比如：
- All-or-nothing： f_e(U)= \left\{\begin{matrix} 1 & if\ U \in \{e,\emptyset\}\\ 0 & otherwise \end{matrix}\right.
- 二次惩罚： f_e(U) = |U| \cdot |e \backslash U|
势（cardinality）指的是集合元素个数
这类分割函数中， 具有次模（Submodular）特性的能够通过gadget展开保留分割函数的性质
次模（Submodular）特性指的是 f_e(A) + f_e(B) ≥ f_e(A \cup B) + f_e (A \cap B) \ \forall A, B ⊆ e
那非次模的分割函数就不能用gadget展开了么？gadget展开这种方法是不是存在缺陷？
害，已经有 研究证明 ，要是采用不具备次模性质的cardinality-based超边分割函数，那么对应的超图割问题就是NP难的，那还求个啥呢。。。
综上所述，gadget展开方法其实还不错啦
熟悉超图的uu们可能还会问，为啥不用其他展开方式呢，比如团展开（Clique expandsion）和星展开（Star expandsion），这些超图规约方式也是很常见的呢
实际上， 这些展开方式都是gadget展开的特例啦 ，区别就是辅助节点的构成方式（gadget）不一样，如下表所示， \hat{V} 是辅助节点集合， E' 是辅助连边集合：
超图上的Local Push
到这里为止，我们已经知道如何将超图规约为图了，那么接下来我们就可以用图上的局部社区发现方法来解辣。具体操作起来就是Local Push（我们在 第一章 提到过，不清楚的话可以跳转过去看看捏），但这里有一个小细节和之前的Local Push不太一样： 辅助节点不需要保留残差
个人理解，辅助节点不是真实存在的节点，所以将它划入局部社区是没有意义的
于是在规约后的超图上执行Local Push的过程可以分为两步
第一步将残差push到辅助节点，如下图所示：
第二步再将残差push到超边关联的其他节点上，如下图所示：
其他步骤和之前的Local Push类似捏
以上就是本文的所有内容啦~
局部社区发现系列文章：
局部社区发现（一）：PageRank竟然可以做局部社区发现？女少啊！
