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 \leq x_u, x_v, \forall e = (u, v) \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$ 范围内，在的话终止迭代，否则继续更新参数
Efficient Algorithms for DSD
General Motif DS 了解通常模体最密子图
概念
$k$-Core：是指图G中的一个极大连通子图H，其中H的每个节点的度数至少为k
$(k,\Psi)$-Core：G的子图H中每个节点的度数至少为k，而且是个Clique
Motif/Pattern：模体，一般是具有某种固定特征的小图，比如说一个四边形就可以是一个Motif/Pattern
Isomorphism：同构，一个图 $G(V,E)$ 说是和一个模体 $\Psi(V_\Psi,E_\Psi)$ 同构，当且仅当存在一个映射关系 $\phi:V_\Psi \rightarrow V$，对于 $\forall v,v’ \in V_\Psi$，如果 $(v,v’) \in E_\Psi$，节点$v$的模体度数$\deg_G(v,\Psi)$是包含$v$的模体实例的数量，那么$(\phi(v),\phi(v’)) \in E$。简单来讲就是如果有两个点在$\Psi$里面有边直接相连，他们对应的点在$G$里面也要有边直接相连
Pattern-Degree：模体度数，给一个图$G
Pattern-Density：模体密度，即：
$$
\rho(G,\Psi) = \frac{\mu(G,\Psi)}{\lvert V \rvert}
$$
$\mu(G,\Psi)$是$G$里面的$\Psi$模体实例数量
Pattern Densest Subgraph：即模体密度最大的子图
核心思想
作者团队认为现有的DSD方法时间复杂度太高了，然后发现DS其实就定位在图的k-Core之间，通过寻找$(k,\Psi)$-Core来，可以快速准确地找到SDS
Scalable Temporal Motif DSD
Temporal Motif DS 了解时态模体最密子图
A New Dynamic Algorithm for Densest Subhypergraphs
DSD on Hypergraph 主要看定义
概念
Hypergraph：超图，与普通图一条边只能连两个点不同，超图中的一条边（称为Hyperedge，超边）可以同时连接任意数量的的节点，表示多元关系。超图的节点集跟普通图一样，都是$V={v_1,v_2,\dots,v_n}$，但是边集$E={e_1,e_2,\dots,e_n}$里的每个超边$e_i$表示的是V的一个子集，可以包含1个、2个或多个节点
Subhypergraph Density：子超图密度，对于一个图$G(V,E,w)$的子节点集合$U \subseteq V$，它的密度是：
$$
\rho_G(U) = \frac{\sum_{e \in E[U]}w_e}{\lvert U \rvert}
$$
如果没有权值的话，可以简化为：
$$
\rho_G(u) = \frac{\lvert E[U] \rvert}{\lvert U \rvert}
$$
其中，$E[U]$表示的是完全被节点子集$U$覆盖的超边集合
Distance-generalized Core Decomposition
H-Distance DS 主要看最密图定义
概念
$(k,h)$-Core：$h$-neighborhood $k$-core,是指图G中的一个极大连通子图H，其中H的每个节点至少有$k$个节点与其距离$\leq h$。通常我们说的$k$-Core可以认为是这里的$(k,1)$-Core
Distance-$h$ Densest Subgraph：在图$G(V,E)$中找到一个子图$S$，最大化其Distance-$h$密度：
$$
\rho_G(S) = \frac{\sum_{v \in S}\deg^h_{G[S]}(v)}{\lvert S \rvert}
$$
其中，$\deg^h_{G[S]}(v)$表示在子图$G[S]$中，节点$v$的$h$-hop度数，即$v$在距离其不超过$h$的节点的邻居数量
Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
Biclique DS 了解双团最密子图
概念
$(p,q)$-Biclique：$(p,q)$-双团，一个无向二分图$G(L \cup R, E)$，如果满足$\lvert L \rvert = p$，$\lvert R \rvert = q$且
$$
(u,v) \in E, \forall u \in L, \forall v \in R$$
我们认为其是一个$(p,q)$-双团
$(p,q)$-Biclique Density：$(p,q)$-双团密度，一个无向二分图$G(L \cup R, E)$，对于$S \subseteq L \cup R$，我们认为其双团密度是：
$$
\rho_{p,q}(S) = \frac{\mu_{p,q}(S)}{\lvert S \rvert}
$$
其中，$\mu_{p,q}(S)$是$S$中$(p,q)$-双团的数量
CCAS
Efficient k-Clique DSD: Towards Bridging Practice and Theory
Motivation
作者团队认为，现有的CDS算法，例如Enumeration-based的KCList++和SCTL，还有Counting-based的KCCA和PSCTL，在实际应用中，尤其是高密度大数据中的表现不尽人意。
核心思想
- 找到一种缩图技巧
- 利用现有的Counting-based算法发展出一种更高效的CDS算法
作者团队发现在SuperGreedy++的每次迭代中，节点权重的变化可以用k-cliques counting来计算，通常会比k-clique enumeration快很多。然后又设计出了一种非常少迭代的方法，比原来的S++要快很多。
除此之外，作者团队还设计出了一种高效算法，可以找到所有k的CDS，和找单个k的CDS速度很接近。
关于CDS的缩图，现有的两种缩图方法，k-core-based和k-clique engagement-based都有限制和缺陷。作者团队发现，大的k-clique一定由很多小的k-clique组成（遗传性），且数小的k-clique数量会比数大的要快很多，所以，作者团队提出了一种HCGR算法，用小的k-clique engagement去估计大的k-clique engagement。
Fast Local Subgraph Counting
一个非常高效的，计算在图$G(V,E)$中，每个节点所具有pattern $p$的数量（所具有表示$p$包含这个节点），称之为Loacl Counting。
概念
Homomorphism：同态，一个图$G(V,E)$和一个pattern $p(V_p, E_p)$，如果有一种映射$f:V_p \mapsto V$使得$\forall (u,u’) \in E_p, (f(u),f(u’)) \in E$，那么称其为同态。同态不一定要一一对应。可以$p$的多个点对应$G$的一个点。匹配简称homo-match。
Isomorphism：同构，在满足同态映射关系的同时还要单射，即一个$p$的点只能映射到一个$G$的点，要一一对应，而且不能出现一对多或者多对一。匹配简称iso-match。
Automorphism：自同构，可以理解为对称的情况。用$\text{Aut}(G)$表示自同构的集合，$\lvert \text{Aut}(G) \rvert$就表示自同构的数量。
Automorphism Orbit：自同构轨道，在自同构中，有对称关系的几个节点可以被算进同一个自同构轨道。用这个自同构轨道上的节点$o$表示一个轨道。
Local Subgraph的计算公式：
$$
\lvert \text{SubG}_{p,o}(v) \rvert = \frac{\lvert \text{ISO}_{p,o}(v) \rvert \cdot \lvert \theta \rvert}{\lvert \text{Aut}(p) \rvert}
$$
其中，$\lvert \text{SubG}_{p,o}(v) \rvert$表示对于子图$p$中的一个节点$v$满足$f(o)=v$，它在$G$中的子图数量。它的数量不受自同构结构影响，所以要在同构子图数量上稍作计算。
$\lvert \text{ISO}_{p,o}(v) \rvert$表示对于子图$p$中的一个节点$v$满足$f(o)=v$，它在$G$中的同构子图数量。
注意，这两个$f$指的都是前面提到的映射关系，所以就是Local Counting。
$\lvert \theta \rvert$表示子图$p$的自同构轨道数。
Tree Decomposition：树分解。
给定一个无向Pattern $p$，它的树分解就是树$T=(V_T,E_T)$。我们用$\tau_i$表示$V_T$里面的一个节点，是$V_p$的一个非空子集，这样的话$p$的一个缩减子图就是$p(\tau_i)$。这个$T$满足以下三个条件：
$V_p=\bigcup_{\tau_i \in V_T}V(\tau_i)$
$\forall (u, v) \in E_p$，$u$和$v$同时出现在至少一个$\tau_i$里面
如果$\tau_i$与$\tau_j$相连，说明它们包含$p$的同一个节点
tISO：对于$p$的一个树分解$T$，记$T_i$是它的一个子树，$p(T_i)$的tiso-match就是，$p(T_i)$在$G$里的homo-match，并且$T_i$里的每一个$\tau_j$都相互iso-match。用$\lvert \text{tISO}_{p,o,T}(v) \rvert$来表示给定一个树分解$T$，$G$中的$v$对应到$p$中的$o$之后的tiso-match的数量。$V_C(\tau)$表示$V(\tau)$和$V(\text{parent}(\tau))$共有的节点，
$\lvert \text{HOM} \rvert$ and $\lvert \text{ISO} \rvert$
HOM的数量就是$p$的所有子集的ISO数量之和。
$$
\lvert \text{HOM}_{p, o}(v) \rvert = \sum_{p’ \in {p} \cup \text{Sub}(p)} \lvert \text{ISO}_{p’, o(p’)}(v) \rvert
$$
这个式子在结构上是
$$
f(p) = \sum_{p’ \subseteq p} g(p’)
$$
那么根据莫比乌斯反演，可以得到
$$
g(p) = \sum_{p’ \subseteq p} \mu(p, p’)f(p’)
$$
其中有莫比乌斯函数
$$
\mu(p,p’) = (-1)^{|p| - |p’|}
$$
原来的式子就可以写成
$$
\lvert \text{ISO}_{p,o}(v) \rvert = \sum_{p’ \in {p} \cup \text{Sub}(p)} \mu(p,p’) \cdot \lvert \text{HOM}_{p’, o(p’)}(v) \rvert
$$
如何计算$\lvert \text{tISO} \rvert$？
通过枚举每一个$\tau \in T$在G里面的iso-match，记为$R_\tau = \text{ISO}(p(\tau))$。对于每一个叶子节点$\tau \in T$，其iso-match的数量记为$X(V_C(\tau), C)$且有
$$
X_{\tau}(V_C(\tau), C) = {_{V_C(\tau)}}\Upsilon_{count(*) \rightarrow C}(R_\tau)
$$
意思就是对$V_C(\tau)$进行数数然后把输出数量命名成$C$。
对于非叶子节点，且不是根节点的：
$$
X_{\tau}(V_C(\tau), C) = {_{V_C(\tau)}}\Upsilon_{sum{(C_1 \times C_2 \times \dots \times C_k)}\rightarrow C}(J_{\tau})
$$
对于根节点：
$$
X_{\tau}(o, C) = {_o}\Upsilon_{sum{(C_1 \times C_2 \times \dots \times C_k)}\rightarrow C}(J_{\tau})
$$
其中：
$$
J_{\tau} = R_{\tau} \bowtie X_{\tau_1} \bowtie X_{\tau_2} \bowtie \dots \bowtie X_{\tau_k}
$$
$\bowtie$是自然连接符号。
如何计算$\lvert \text{ISO} \rvert$？
在上面的tree decomposition中，我们其实得到了pattern $p$的subpattern $p’$，也就是一些pattern的子图。对于每个$p’$，可以有以下集合：
$\mathcal{I} = {I_1, I_2, \dots, I_{\lvert V_{p’} \rvert}}$，$I_k$表示一个独立点集而且它们内部在$p$里面没有直接边相连，这样就可以做homo-match。
$\text{Cov}(p,T)$：给定一个 $p$ 的树分解，$p_i$ 是 $p$ 的一个子图，它对应的partition是$\mathcal{I}={I_1, I_2, \dots}$。如果两个节点$u$和$v$在相同的$I_k$里面出现了，而且没有在任何$T$的节点$\tau$里面一起出现，我们称$T$覆盖了$p_i$。$p$被$T$覆盖的子图集合，记为$\text{Cov}(p,T) (\subseteq \text{Sub}(p))$。
SCOPE
- 对给定pattern $p$做tree decomposition $T$。
- 在$T$上做tISO Counting
- 将tISO Counting转换成ISO Counting
- 再用公式算Local Subgraph Counting
优化：Symmetry-Breaking Rules和Multi-join Algorithms
Counting Cohesive Subgraphs with Hereditary Properties
概念
Hereditary：遗传性，指的是一个具有性质A的图，它的子图还是具有性质A，比如Clique。常见的例子有 s-defective clique, s-plex, s-clique, quasi-clique, k-core, k-truss, k-edge connected subgraph。
Hereditary Cohesive Subgraphs：Clique, s-defective clique and s-plex。
S-Defective Clique：对比一个Clique，最多删掉s条边的图。它具有继承性是因为删掉一个节点并不会增加少边的数量。
S-Plex：对比一个Clique，每个节点最多删掉s条边。它具有继承性是因为删点只会让邻居节点少一个边，而且Clique也少了一层，非邻居节点不受任何影响。
Motivation
计算小的clique数量在很多方面有很基础的应用，但是clique性质太严格了，所以作者团队研究出了一种算法，可以高效地计算具有遗传性和紧密性的子图（HCS）的数量。并且有local counting！
核心思想
算法HCSPivot可以高效地通过递归树和组合数学算出HCS的数量，这个也可以应用在motif里面（如果把一个HCS当成motif）