Metropolis Algorithms for Representative Subgraph Sampling

• 概
• 主要内容
  • Metropolis graph sampling

H\¨{u}bler C. and Kriegel H., Borgwardt K. and Ghahramani Z. Metropolis algorithms for representative subgraph sampling. ICDM, 2008.

概

提出了一种尽可能保持拓扑结构的子图采样方法.

主要内容

• 假设我们有一个大图 \(G\), 这导致我们在上面推理的时候会比较费时.

• 本文的想法是, 采样一个近似的子图 \(S\), 它的规模更小, 但是具有类似的拓扑结构, 所以在上面会有一个比较好的模拟效果, 严格来说 (\(n' \ll n = |G|\)):

  \[S* = \text{argmin}_{S \sqsubseteq G \wedge |S|=n'} \Delta (\sigma(S), \sigma(G)), \]

  这里 \(\sigma(\cdot)\) 统计图的一些性质 (如 degree 分布, 半径等), \(\Delta(\cdot, \cdot)\) 则度量两个统计量的差距.

• 但是, 一般来说, 精确求解是困难的 (这需要穷尽所有的组合).

Metropolis graph sampling

• 本文在 \(\Xi :=\{S \sqsubseteq G: |S| = n\}\) 上定义一个分布:

  \[p(S) = \frac{\varrho(S)}{\sum_{S' \in \Xi} \varrho (S')}, \]

  \(\varrho\) 和 \(\sigma(S)\) 有关. 但是归一化因子 \(Z = \sum_{S' \in \Xi} \varrho (S')\) 依旧需要穷举所有的, 所以直接构建分布然后采样是不可行的.

• 于是作者求助 Metropolis 采样. 转而定义如下的条件分布:

  \[p(S'|S) = q(S'|S) \cdot a(S', S), \]

  其中 \(q(S'|S)\) 为 proposal distribution (一般为方便采样 \(S'\) 的分布), \(a(S'|S)\) 为接受概率.

• 因为条件概率:

  \[p(S'|S) = p(S', S) / p(S), \]

  故

  \[\frac{a(S', S)}{a(S, S')} = \frac{p(S') q(S|S')}{p(S)q(S'|S)}, \]

  倘若我们定义接受概率为:

  \[a(S', S) := \min(1, \frac{p(S') q(S|S')}{p(S)q(S'|S)}) \]

  上面性质就自然成立了. 这是因为只有如下的两种情况发生:

  \[a(S', S) := 1, a(S, S') = \frac{p(S) q(S'|S)}{p(S')q(S|S')}, \\ a(S', S) := \frac{p(S') q(S|S')}{p(S)q(S'|S)}, a(S, S') = 1. \]

• 这种方式有一个好处, \(p(S') / p(S)\) 使得归一化因子 \(Z\) 被约掉了, 所以实际上变成了:

  \[a(S', S) := \min(1, \frac{\varrho(S') q(S|S')}{\varrho(S)q(S'|S)}). \]

• 所以整体的思路就是:

  1. 随机选择 \(S\);
  2. 然后不断 propsal 新的 \(S'\);
  3. 构成一条马氏链收敛到最后的平稳分布.

• 具体的算法是:

  1. 随机选择 \(n'\) 个点得到它的子图 \(S\);
  2. 在剩下的点中随机选一个点 \(v'\), 然后在 \(S\) 中选择一个点 \(v\);
  3. \(S'\) 为 \(S\) 删除点 \(v\) 加上点 \(v'\);
  4. 计算接受概率 \(a(S', S)\), 判断是否接受.
  5. 不断循环直到收敛.

• 现在的问题是 \(\varrho\) 的选择:

  \[\varrho_{p, T} (S) = [\Delta(\sigma(S), \sigma(G))]^{-p/T}, \]

  \(p\) 是一个固定的超参数, \(T\) 在采样中会逐渐退火. 总体来说, 和 \(G\) 统计性质越接近的子图越受青睐.

• 此外, 可以证明上面算法中 \(q(S|S') = q(S'|S)\), 所以这使得结构概率的计算更加简单了.