局部社区发现（四）：最小割、PageRank、局部社区...它们 ...

JamesB

最小割、PageRank、局部社区......看似完全不同的问题，实际上可以被归纳到同一个优化问题框架下。理解这个优化问题，可以为后续算法设计提供指导，以更抽象的层次实现降维打击。本文介绍一篇来自ICML 2014的一篇论文，讨论如何将这些问题统一到相同框架下：
（答应我，一定要先看完本系列的第一章再看本文好吗~可以先收藏本文再去看第一章，以防后续找不到捏）
背景知识

• s-t最小割问题：给定一个图、源节点和目标节点，s-t最小割问题旨在寻找一组最少的连边，将图划分为包含源节点和目标节点的两个子图
  
• PageRank：给定一个图，PageRank旨在计算图中各节点的重要性
  
• 局部社区发现：给定一个图和源节点，局部社区发现旨在寻找一个包含源节点的子图，且该子图对内连接紧密，对外连接稀疏
  

最小割的优化问题表述

在图论中，我们可以用关联矩阵 B（incidence matrix）来表示一个图 G=(V,E) ，其中 B 的维度是 |E|\times|V| 。对于简单图而言，关联矩阵的每一行都是 (\bm{e}_i-\bm{e}_j)^T ，用于表示从节点 i 到节点 j 的一条连边 (i,j) ，这里 \bm{e}_i 表示有且仅有第 i 个元素是1，其余都是0的向量。
于是，对于给定的节点集合 S\subset V ，我们可以将割表示为集合内节点与集合外节点之间的连边数量，即：
cut(S)=||\bm{Bx}||_1=\sum\limits_{(i,j)\in E}|\bm{x}_i-\bm{x}_j|
这里的 \bm{x} 用于指示哪些节点在给定节点集合中，即 \bm{x}=\bm{e}_S=\sum\limits_{i\in S}\bm{e}_i
如果需要考虑连边的权重，可以设计一个连边权重矩阵 C ，这是一个对角矩阵，规模为 |E|\times|E| ，其中每一的对角元素都对应着连边权重。此时，对于节点集合 S 的割可以表示为：
cut(S)=||\bm{Bx}||_{C,1}=\sum\limits_{(i,j)\in E}C_{(i,j)}|\bm{x}_i-\bm{x}_j|
接下来开始描述最小割问题：

在图 G 中找到一个节点集合 S ，使得 cut(S) 最小

我们不妨在图 G 中创建两个虚拟的源节点 s 和目标节点 t ，其中 s 与节点集合 S 内任一节点都有连边，而节点 t 与其余节点集合 \bar{S} 内任一节点都有连边，将上述问题转化为s-t最小割问题，正如下图所示：


细心的读者可能会发现，这里的s-t最小割问题其实与s-t最大流问题互偶，考虑到通过节点的最大流量与节点的度有关，因此这里源节点与其他节点之间的连边权重为 \alpha \bm{d}_S ，类似的，目标节点与其他节点之间的连边权重为 \alpha \bm{d}_\bar{S}，这里的 \bm{d}_S 和 \bm{d}_{\bar{S}} 分别表示节点集合 S 和 \bar{S} 中节点的度。
此时，新增虚拟节点后的关联矩阵为：
\bm{B}(S)=\begin{bmatrix} \bm{e} & -\bm{I}_S & 0 \\  0 & \bm{B} & 0\\  0 & -\bm{I}_{\bar{S}} & \bm{e} \end{bmatrix}
需要说明的是，这里的 \bm{I}_{S} 是一个标识矩阵，其对角线元素表示节点是否在 S 中，同理有 \bm{I}_{\bar{S}} 。此外，新增虚拟节点后的连边权重矩阵表示为 \bm{C}(\alpha) 。
由此我们可以给出s-t最小割的最优化问题表述：
\begin{matrix} min. & ||\bm{B}(S)\bm{x}||_{C(\alpha),1} \\  s.t. & x_s=1,x_t=0,\bm{x}\geq 0 \end{matrix}
PageRank的优化问题表述

除了关联矩阵外，我们还可以用邻接矩阵 A （adjacency matrix）来表示一个图，邻接矩阵的任一行都表示节点与其他节点之间的关联情况。对于有连边权重的情况，邻接矩阵的任一元素可以表示为：
A_{i,j}=\left\{\begin{matrix}  C_{(i,j)} & (i,j)\in E\\  0 & otherwise \end{matrix}\right.
由邻接矩阵我们可以得到图的度矩阵 D 和拉普拉斯矩阵 L ：
D=diag(A\bm{e}) \\ L=B^TCB=D-A
接下来开始描述PageRank方程：

考虑 \bm{z} 是图的PageRank向量，那么： (\alpha D+L)\bm{z}=\alpha\bm{v}

其中 \beta=1/(1+\alpha) 是PageRank方程的阻尼系数； \bm{v} 是PageRank的起始向量，满足 \bm{e}^T\bm{v}=1
类似s-t最小割的表述方式，我们不妨在图 G 中选择一个节点集合 S ，新增两个虚拟的源节点 s 和目标节点 t，并构建出 B(S) 和 C(\alpha) ，此时PageRank向量是以下优化问题的最优解：
\begin{matrix} min. & ||\bm{B}(S)\bm{x}||_{C(\alpha),2} \\  s.t. & x_s=1,x_t=0 \end{matrix}
证明过程简要描述如下：优化目标的平方是与原问题等价的，即
f(\bm{x}) = ||\bm{B}(S)\bm{x}||_{C(\alpha),2}^2 \\ =\bm{x}^T\bm{B}(S)^T\bm{C}(\alpha)\bm{B}(S)\bm{x} \\ =\begin{bmatrix}  1 & \bm{x}_G^T & 0 \end{bmatrix} \begin{bmatrix}  \alpha vol(S) & -\alpha \bm{d}_S^T & 0 \\  -\alpha \bm{d}_S & L+\alpha D & -\alpha \bm{d}_{\bar{S}}\\  0 & -\alpha \bm{d}_{\bar{S}}^T & \alpha vol(\bar{S}) \end{bmatrix} \begin{bmatrix}  1 \\  \bm{x}_G\\  0 \end{bmatrix} \\ =\bm{x}_G^T(L+\alpha D)\bm{x}_G - 2\alpha \bm{x}_G^T \bm{d}_S + \alpha vol(S)
当 \frac{\partial f}{\partial \bm{x}}=0 时， f 能取到最优解，此时有：
(\alpha D+L)\bm{x}_G=\alpha \bm{d}_S
对上等式两侧同除 vol(S) ，此时原问题的最优解满足 \bm{z}=\bm{x}_G/vol(S) 且 \bm{v}=\bm{d}_S/vol(S) 的PageRank方程
局部社区发现的优化问题表述

在之前的ACL算法介绍中，我们提到局部社区发现可以分为两个阶段，即计算APPR向量和Sweep过程。事实上，Sweep过程依赖于APPR向量，因此准确表述APPR向量的计算问题在某种程度上就是在描述局部社区发现。
于是接下来我们描述APPR的计算过程：

对于给定的起始残差向量 \bm{r}=\bm{e}_k ，计算APPR需要反复执行Local Push过程，直到 \forall i\in V,r_i \leq \epsilon d_i ，而Loacl Push过程可以描述为 ：z_i=z_i+(1-\beta)(r_i - \epsilon d_i) \\ r_j=r_j+\beta(r_i - \epsilon d_i), if \ A_{i,j}>0在此过程中，残差向量与PageRank向量满足不变性，即： \bm{r}=(1-\beta)\bm{e}_k-(I-\beta AD^{-1})\bm{z}

类似s-t最小割的表述方式，我们不妨在图 G 中选择一个节点集合 S ，新增两个虚拟的源节点 s 和目标节点 t，并构建出 B(S) 和 C(\alpha) ，此外，令 \kappa=\epsilon vol(S)/\beta ，APPR向量是下面这个优化问题的极值：
\begin{matrix} min. & \frac{1}{2}||\bm{B}(S)\bm{x}||_{C(\alpha),2}^2 + \kappa||D\bm{x}||_1 \\  s.t. & x_s=1,x_t=0,\bm{x}\geq0 \end{matrix}
证明过程简要描述如下：考虑 \bm{x}=\begin{bmatrix}  1 & \bm{x}_G^T & 0 \end{bmatrix}^T ，则原问题可以转化为
\begin{matrix} min. & f(\bm{x}_G) =\frac{1}{2}\bm{x}_G^T(\alpha D+L)x_G-\alpha \bm{x}_G^T\bm{d}_S+\alpha^2vol(S)+\kappa\bm{d}^T\bm{x}_G \\ s.t. & \bm{x}_G \geq 0 \end{matrix}
当该问题获得极值时，需要满足原问题的约束条件和KKT条件，考虑拉普拉斯乘子 \bm{s} ，则：
\frac{\partial f}{\partial\bm{x}_G}=(\alpha D+L)\bm{x}_G-\alpha\bm{d}_S+\kappa\bm{d}-\bm{s}=0 \\ \bm{s} \geq 0 \\ \bm{x}_G \geq 0 \\ \bm{x}_G^T \bm{s}=0  
对第一个等式变换，有：
(\alpha D+L)\bm{x}_G-\alpha\bm{d}_S+\kappa\bm{d}-\bm{s}=0 \\ \Leftrightarrow (I-\beta AD^{-1})D\bm{x}_G-(1-\beta)\bm{d}_S+\beta\kappa\bm{d}-\beta\bm{s}=0 \\ \Leftrightarrow (I-\beta AD^{-1})D\bm{x}_G/vol(S)-(1-\beta)\bm{d}_S/vol(S)+\beta\kappa\bm{d}/vol(S)-\beta\bm{s}/vol(S)=0
此时，我们令 \bm{s}=\frac{vol(S)}{\beta}(\epsilon\bm{d}-\bm{r}) ，则有 \beta\bm{s}/vol(S)=\beta\kappa/vol(S)\bm{d}-\bm{r}=\epsilon \bm{d}-\bm{r} \geq 0 ，这正是APPR计算过程中Local Push的终止条件。接着我们引入APPR计算过程中的不变性，则可以发现原问题的解经过正则化恰好就是APPR向量，即 \bm{z}=D\bm{x}_G/vol(S)
广义图割问题

总结上述优化问题，我们可以猜想，是否存在统一的优化问题框架，能够描述这类问题？
答案仍在探索中，不过截止到本文发布时，已经有相关工作对这个方向进行了探索，本系列将继续讨论这个课题~
我们不妨也设定两个函数 \sigma, \delta ，尝试将上述问题都统一到相同的框架下吧：
\begin{matrix} min. & \bm{e}^TC(\alpha)\sigma(B(S)\bm{x}) + \kappa \delta(D\bm{x}) \\ s.t. & \bm{x}_s=1,\bm{x}_t=0, \bm{x}\geq0. \end{matrix}
以上就是本文的所有内容辣~

局部社区发现系列文章：
局部社区发现（一）：PageRank竟然可以做局部社区发现？女少啊！
局部社区发现（二）：motif局部社区发现-MAPPR算法
局部社区发现（三）：如何在带权有向图上进行局部社区发现
局部社区发现（四）：最小割、PageRank、局部社区...它们都是同一个优化问题！