CS Graph
前言
这其实是去年暑假跟师兄做的一个课题了，一开始设想我觉得是挺好的，但是后面做出来一点发现并没有达到一个很好的效果，在很多小细节上都达不到预期甚至出现跟设想的差错，最后就放弃了。
为什么现在发出来呢，因为当时做这个事情是想发 paper 来着，但是这个方向没做下去然后就一直咕了，现在想了想其实也没什么价值，这个优化过的代码我花了几天实现成 C++，但跑起来实际效果可能还不如之前的 SOTA，只能说是一次科研小尝试，发出来看看有没有高手指点一下。
但这个密集子图挖掘相关的科研确实是很困难，大部分时候面对一堆 np-hard 问题无从下手，感觉不管怎么想都是指数级的而且几乎没法优化，确实令人头疼。
但当时那几个月的科研经历还是挺有意思的，至少学到了很多东西，主要也是感受了一下理论计算机科学科研。
Motif (Higher-order) Densest Subgraph Discovery
核心思想
- motif-based 都可以有一个 lp 的方程
- 然后这个方程都可以转成 counting based
- 满足层次关系的 motif 都可以有一个缩图
整篇论文可以分成两个 part：一个是带层次关系的 motif（比如说 clique, k-plex 之类的），可以先用 CCAS 的缩图技巧，再做 MDS；另一个是一个 general motif（size 尽量要小于等于 $5$）的MDS问题
LP 方程
可以根据 CDS 问题的 LP 方程来写，对于一个图 $G(V,E)$
$$
\max \sum_{m \in M} y^m \\ \\
\text{s.t. } y^m \leq x_v \ \ \forall m \in M, v \in m \\
\sum_{v \in V} x_v \leq 1 \\
x_v \in [0,1], y^m \in [0,1]
$$
其中：
$M$：所有 motif 实例
$y_m$：motif实例 $m$ 被选的程度
$x_v$：顶点 $v$ 被选的程度
其Dual DP方程就是
$$
\min \max_{v \in V} r(v) \\ \\
\text{s.t. } r(v) = \sum_{m \in M(G)} \alpha_v^m , \forall v \in V \\
\sum_{v \in m} \alpha_v^m = 1, \forall m \in M \\
\alpha_v^m \in [0, 1]
$$
其中：
$\alpha_v^m$：包含 $v$ 的motif $m$ 给这个节点分配的权重，且一个motif $m$ 给它的节点分配的权重和为1
$r(v)$：节点 $v$ 从所有包含它的 motif 收到的权重和
然后，我们有：
$$
\rho_m = \frac{1}{\max_{v \in V} r(v)}
$$
算法流程
Baseline
根据上述 Dual DP 方程，再加上 Frank-Wolfe 算法，可以有以下算法（Algorithm 1）：
输入：一个图 $G$，一个motif $m$，迭代次数 $T$
输出：Approximate MDS $S_m(G)$
- foreach motif $m \in M(G)$ do ${\alpha_v^{m}}^{(0)} \leftarrow \frac{1}{\lvert m \rvert}, \forall v \in m$;
- foreach $v \in V(G)$ do $r^{(0)}(v) \leftarrow \sum_{m \in M(G): v \in m}{\alpha_v^{m}}^{(0)}$;
- foreach $t \leftarrow 1,2,3,\dots,T$ do
- foreach motif $m \in M(G)$ do
- $x \leftarrow \arg \min_{v \in m} r^{(t-1)}(v)$
- foreach $v \in m$ do
- $\hat{\alpha}_v^m \leftarrow 1$ if $v = x$ and $0$ otherwise;
- foreach motif $m \in M(G)$ do
- foreach $v \in m$ do
- ${\alpha_v^{m}}^{(t)} \leftarrow (1 - \gamma_t) · {\alpha_v^{m}}^{(t-1)} + \gamma_t · \hat{\alpha}_v^m$, with $\gamma_t = \frac{2}{t+2}$;
- foreach $v \in m$ do
- foreach $v \in V(G)$ do $r^{(t)}(v) \leftarrow \sum_{m \in M(G):v \in m}{\alpha_v^{m}}^{(t)} $
- foreach motif $m \in M(G)$ do
- foreach $1 \leq i \leq \lvert V(G) \rvert$ do
- $v_i \leftarrow$ the vertex with the $i$-th highest weight in $V(G)$;
- $G_i \leftarrow$ the induced subgraph of top-$i$ highest weight vertices;
- $y_i \leftarrow \lvert M(v_i, G_i) \rvert$;
- $s^* \leftarrow \arg \max_{1 \leq s \leq n} \frac{1}{s} \sum_{i=1}^s y_i$;
- return $S_m(G) \leftarrow $ the subgraph induced by the first $s^*$ vertices;
Baseline 的思考与改进
观察这个 Baseline，我们会发现在第1步（对于每个 motif $m$，都去更新对于这个 motif 的节点的 $\alpha_v^m$，这已经是一个对于 motif 的 enumeration，在时间复杂度上肯定是不允许的
我们要学习KCCA，将 enumeration 问题转换成 counting 问题，这里需要改的地方就是，所有 $\alpha_v^m$ 都要删掉，进而换成直接对 $r(v)$ 的更新
关键点在于这句话
$$
{\alpha_v^{m}}^{(t)} \leftarrow (1 - \gamma_t) · {\alpha_v^{m}}^{(t-1)} + \gamma_t · \hat{\alpha}_v^m
$$
根据KCCA推的式子，$r(v)$ 可以表示成
$$
r^{(t)}(v) = (1 - \gamma_t) · r^{(t-1)}(v) + \gamma_t · \hat{r}(v)
$$
其中，有
$$
\hat{r}(v) = \sum_{m \in M(v, G)} \hat{\alpha}_v^m
$$
然后在KCCA中，有 $\hat{r}(v)$ 等于包含 $v$ 的Clique，且这个 $v$ 是 $r^{(t-1)}(v)$ 是每个Clique里面权重最小的，数量，即
$$
\hat{r}(v) = \sum_{C \in \Psi_k(v, G)}
\begin{cases}
1 & \text{if } v = \arg \min_{u \in C}r^{(t-1)}(u), \\
0 & \text{if otherwise}
\end{cases}
$$
然后就能写出这样的式子
$$
\hat{r}(v) = \sum_{m \in M(v, G)}
\begin{cases}
1 & \text{if } v = \arg \min_{u \in m}r^{(t-1)}(u), \\
0 & \text{if otherwise}
\end{cases}
$$
这样，就可以把 $\alpha$ 删掉，我们的proposed framework就变成了
优化成Counting-based
Counting-based 算法（Algorithm 2）：
输入：一个图 $G$，一个motif $m$，迭代次数 $T$
输出：Approximate MDS $S_m(G)$
- foreach $v \in V(G)$ do $r^{(0)}(v) \leftarrow \frac{\lvert M(v, G) \rvert}{\lvert m \rvert}$;
- foreach $t \leftarrow 1,2,3,\dots,T$ do
- sort the vertices in $V(G)$ by ascending $r$ values;
- $\gamma_t \leftarrow \frac{2}{t+2}$;
- $G’ \leftarrow G$;
- foreach $v \in V(G)$ do
- $\hat{r}(v) \leftarrow \lvert M(v, G’) \rvert$
- $r^{(t)}(v) = (1 - \gamma_t) · r^{(t-1)}(v) + \gamma_t · \hat{r}(v)$;
- remove $v$ and its connected edges from $G’$;
- foreach $1 \leq i \leq \lvert V(G) \rvert$ do
- $v_i \leftarrow$ the vertex with the $i$-th highest weight in $V(G)$;
- $G_i \leftarrow$ the induced subgraph of top-$i$ highest weight vertices;
- $y_i \leftarrow \lvert M(v_i, G_i) \rvert$;
- $s^* \leftarrow \arg \max_{1 \leq s \leq n} \frac{1}{s} \sum_{i=1}^s y_i$;
- return $S_m(G) \leftarrow $ the subgraph induced by the first $s^*$ vertices;
这样子的话，核心部分就是如何快速地去算这个 $\lvert M(v, G) \rvert$，也就是 local counting（包含 $v$ 的 motif 的个数），或者是说能不能找到一个像 clique 那样的式子来快速更新
剪枝优化
缩图技巧，给定最大下界，做剪枝 prune，参考论文 CCAS 的 HCGR 算法。大概思想就是根据小的 motif 子图去删掉一些密度不够的区域。
Journal: Clique 最密图 Motif Enumration 版本
- Frank-wolfe baseline 所有的 motif，需要看 motif enumeration
- 有继承性的 motif 可以做类 KCCA 算法，看 www 论文