Densest Subgraph Discovery on Large Graphs

CUHKSZ PPT

无向图上的密集子图

对于一个无向图$G(V,E)$，图的密度就是边的密度，即
$$
\rho (G) = \frac{\lvert E \rvert}{\lvert V \rvert}
$$

那么，最密子图挖掘就是找到密度$\rho(G)$最大的子图

目前对于这种DSD问题的exact solution有两种：

• 基于最大流的算法
• 基于线性规划的算法
  当然还有一些其他approximation solution和DSD问题的变种

Maxflow-based Algorithm

二分+网络流最小割

二分最大密度$\rho$从$0$到$m$
每次建立超级源点和超级汇点跑网络流最小割来判断$\rho$是不是合法的

LP-based Algorithm

Original LP

$S$是点集，$E(S)$是其边集

$x_v=\frac{1}{\lvert S \rvert}$表示节点$v$属于点集$S$，$y_e=\frac{1}{\lvert S \rvert}$表示边$e$属于边集$E$

$$
\text{maximize }\sum_{e \in E}y_e \\ \\
\text{subject to }y_e < x_u, x_v, \forall e = uv \in E \\
\sum_{v \in V} x_v \leq 1 \\
x_v, y_e \geq 0, \forall e \in E, \forall v \in V
$$

Dual LP

$\alpha_u^e$是节点$u$从边$e$接收到的权重，例如：$\alpha_u^e = \frac{w_e}{2}$

$$
\text{min } \rho \\ \\
\text{s.t. } \rho \geq \sum_{e:u \in e} \alpha_u^e, \forall u \in V \\
\sum_{u \in e} \alpha_u^e \geq w_e, \forall e \in E \\
\alpha_u^e \geq 0, \forall u \in e \in E
$$

然后要用Frank-Wolfe算法来解决Dual LP问题，再用网络流算法来准确计算最大密度

有向图上的密集子图

对于一个有向图$G(V,E)$，图的密度是针对两个点集的，即
$$
\rho(S,T) = \frac{\lvert E(S,T) \rvert}{\sqrt{\lvert E \rvert \lvert T \rvert}}
$$

那么，最密子图挖掘就是找到两个点集$S’$和$T’$，使得其有最大密度

KClist++

A Simple Algorithm for Finding k-Clique Densest Subgraph in Large Graphs

概念

k-Clique：大小为k的团，其里面每一对子节点都有相应的边直接连接

k-Clique Density：k团密度，其在无向图$G(V,E)$中的定义为

$$
\rho(G) = \frac{\lvert \Psi \rvert}{\lvert V \rvert}
$$

期中$\Psi$表示$G$中所有k-Clique的集合，$\lvert \Psi \rvert$则表示$G$中k-Clique的数量

k-Clique Densest Subgraph：k团最密子图，即k团密度最大的子图。其在k=2的时候是最基础的最密子图(DSD)，在k=3的时候是有最多平均三角形数量的子图

核心思想

我们针对每一个节点$u$给一个分数$r(u)$，初始化为0，然后在之后的每一次迭代里，我们都会根据边对这些分数进行一些操作，当迭代次数足够多的时候，我们会发现maximal k-clique densest subgraph会有更多的分数。这可以高效地分理出这些子图，而且仅具有线性的内存空间

KCCA

A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery

前置算法

Frank-Wolfe算法在CSD的应用

先给每一个节点$v$分配一个权重$r(v)$，初始化为包含$v$的k-Clique数量（除以k？）。然后在每次迭代里，对于每一个k-Clique，它找到最小权重的节点$v$，并更新这个节点的权重$r(v)$

CDS问题的CP公式

LP公式

$$
\text{LP}(G,k):\ \ \ \ \ \text{maximize} \sum_{C \in \Psi_k(G)} y^C \\ \\
\text{s.t.} \forall v \in C, y^C \leq x_v, \forall C \in \Psi_k(G) \
\sum_{v \in V}x_v \leq 1 \
y^C \geq 0, x_v \geq 0, \forall C \in \Psi_k(G), \forall v \in V
$$

Dual LP公式

$$
\text{DP(G, k)}:\ \ \ \ \ \min \max_{v \in V} r(v) \\ \\
\text{s.t.} r(v) = \sum_{C \in \Psi_k(v,G)} \alpha_v^C, \forall v \in V \
\sum_{v \in C} \alpha_v^C = 1, \forall C \in \Psi_k(G) \\
\forall v \in C, \alpha_v^C \geq 0, \forall C \in \Psi_k(G)
$$

其中，$\alpha_v^C$是Clique $C$给它的一个节点$v$分配的权重，$r(v)$是$v$从所有包含其的k-Cliques中获得的权重和

核心思想

现有的基于枚举k-Clique的CDS挖掘算法在k变大时复杂度会变得巨大，所以作者团队就在思考能不能不枚举所有的k-Clique，而是通过计算k-Clique的数量来找CDS

通过深度解析Frank-Wolfe算法，作者团队发现在该算法的每次迭代中，$r(v)$的变化，可以通过包含$v$的k-Clique数量来计算，这可以极大的减少解决CDS问题的时间复杂度

In-depth Analysis of DSD

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework

DSD的统一框架

Graph Reduction：简化图形，旨在在一个小的子图里定位出最密子图

VWU：Vertex Weight Update，更新T次迭代之后的节点权重

CSV：Candidate Subgraph Extract and Verify，基于节点权重分离候选子图，然后验证其是否在误差$\epsilon$范围内，在的话终止迭代，否则继续更新参数