SIAM-2011《Weighted Graph Compression for Parameter-free Clustering With PaCCo》

---

核心思想分析

论文提出了一种基于最小描述长度（Minimum Description Length, MDL）原理和二分k均值策略的无参数加权图聚类算法，命名为PaCCo（Parameter-free Clustering by Coding costs）。其核心思想是将图聚类问题转化为数据压缩问题，通过最小化编码成本（coding costs）来自动确定加权图中的聚类结构，而无需用户指定参数（如聚类数目$k$）。PaCCo利用加权图中边的权重信息，结合MDL原理，通过递归的图分割和聚类过程，识别出高度互联且边权重相似的子图，从而实现高效、准确的聚类。

具体而言：

• 数据压缩与MDL：MDL原理认为，一个好的聚类结构能够显著压缩图数据。通过量化图的编码成本，PaCCo将聚类问题转化为寻找编码成本最低的分区方案。
• 加权图的处理：与传统的无权图聚类不同，PaCCo考虑边权重作为节点相似性的重要信息，避免了通过二值化或阈值化丢失权重信息。
• 无参数与自动化：通过MDL作为终止准则，PaCCo自动确定聚类数目，无需用户干预，解决了传统算法（如谱聚类、Metis）需要预设参数的问题。
• 递归二分策略：采用自顶向下的二分k均值策略，逐步分割图，直到进一步分割不再降低编码成本，从而保证计算效率和聚类质量。

---

目标函数分析

PaCCo的目标函数基于MDL原理，旨在通过最小化图分区的编码成本来优化聚类结构。目标函数由两部分组成：聚类成本和模型参数成本，形式化定义如下：

$$\text{Model-Cost}(G\mid C)=\sum _{l=1}^{k}c(C_l)+c(p)$$

其中：

• $G$：输入的加权无向图，包含节点集$V$和边集$E$。
• C = { C 1 , … , C k } C = \{C_1, \ldots, C_k\} C={C1​,…,Ck​}：图的分区，包含$k$个互不相交的聚类。
• $c(C_l)$：第$l$个聚类的编码成本，表示压缩该聚类子图所需的比特数。
• $c(p)$：存储聚类模型参数的成本，与聚类数目$k$相关，用于校正模型复杂性。

每个聚类$C_l$的编码成本$c(C_l)$由节点$v_i$在该聚类中的成本之和构成：

$$c(C_l)=\sum _{v_i\in C_l}c(v_i\mid C_l)$$

节点$v_i$的成本$c(v_i\mid C_l)$进一步分为权重成本和连接成本：

$$c(v_i\mid C_l)=c_{\text{weights}}(v_i\mid C_l)+c_{\text{linkage}}(v_i\mid C_l)$$

1. 权重成本 $c_{\text{weights}}(v_i\mid C_l)$：

   • 假设聚类内边权重服从高斯分布（Gaussian Distribution, GD），以概率密度函数（PDF）$f_{GD}$表示，权重成本基于负对数似然：
     $$c_{\text{weights}}(v_i\mid C_l)=-{\log }_2\left(f_{GD}(v_i;{\mu }_{C_l},{\sigma }_{C_l})\right)$$
     其中，高斯分布定义为：
     $$f_{GD}(w_{ij};{\mu }_{C_l},{\sigma }_{C_l})=\frac{1}{\sqrt{2\pi {\sigma }_{C_l}^2}}\exp \left(-\frac{(w_{ij}-{\mu }_{C_l}{)}^2}{2{\sigma }_{C_l}^2}\right)$$
     对于节点$v_i$，权重成本考虑其与聚类内所有节点的边权重：
     $$f_{GD}(v_i;{\mu }_{C_l},{\sigma }_{C_l})=\frac{1}{|C_l|}\sum _{v_j\in C_l}\frac{1}{\sqrt{2\pi {\sigma }_{C_l}^2}}\exp \left(-\frac{(w_{ij}-{\mu }_{C_l}{)}^2}{2{\sigma }_{C_l}^2}\right)$$
     其中，${\mu }_{C_l}$和${\sigma }_{C_l}$分别是聚类$C_l$内边权重的均值和标准差。

2. 连接成本 $c_{\text{linkage}}(v_i\mid C_l)$：

   • 连接成本衡量节点$v_i$与聚类内和聚类外的连接情况，鼓励聚类内边最大化，聚类间边最小化：
     $$c_{\text{linkage}}(v_i\mid C_l)=-0.5{\log }_2\left(|e_{i,j^{\prime }}|\right)+0.5{\log }_2\left(|e_{i,j^{\prime \prime }}|\right)$$
     其中，$|e_{i,j^{\prime }}|$是$v_i$与聚类$C_l$内节点的边数，$|e_{i,j^{\prime \prime }}|$是$v_i$与所有节点的总边数（包括聚类外）。

目标函数的设计目标是通过最小化$\text{Model-Cost}(G\mid C)$，实现高度互联且边权重相似的子图分区，同时通过$c(p)$控制聚类数目，避免过拟合。

---

目标函数的优化过程

PaCCo采用自顶向下的二分k均值策略，通过递归分割图来优化目标函数。优化过程包括以下步骤：

1. 初始化：

   • 输入加权无向图的邻接矩阵$A$，初始化整个图为一个聚类，使用$k=1$的$k$-PaCCo计算初始编码成本，提供优于随机的初始聚类。

2. 递归分割（splitClusters）：

   • 对每个聚类$C_l$，尝试将其分割为两个子聚类（$k=2$），使用$k$-PaCCo算法。
   • 初始化两个子聚类的权重分布：基于当前聚类$C_l$的高斯分布参数${\mu }_{C_l}$和${\sigma }_{C_l}$，将子聚类的均值设置为${\mu }_{C_l}+{\sigma }_{C_l}$和${\mu }_{C_l}-{\sigma }_{C_l}$，标准差为${\sigma }_{C_l}/2$，以引导非随机的分割。
   • 计算分割后的编码成本$\text{Model-Cost}(G_{l_{\text{split}}}\mid C_{l_{\text{split}}})$，与当前聚类的成本$\text{Model-Cost}(G_l\mid C_l)$比较：
     $$\text{Model-Cost}(G_{l_{\text{split}}}\mid C_{l_{\text{split}}})<\text{Model-Cost}(G_l\mid C_l)$$
     • 若成本降低，接受分割，继续递归处理子聚类。
     • 若成本不降低，保留当前聚类，停止分割。

3. k-PaCCo聚类：

   • 重新分配步骤：对每个节点$v_i$，计算其在每个候选聚类$C_l$中的成本$c(v_i\mid C_l)$，将其分配到成本最低的聚类：
     $$C_{\text{new}}(v_i)=\arg \underset{C_l\in C}{\min }c(v_i\mid C_l)$$
   • 更新步骤：更新每个聚类的权重分布参数${\mu }_{C_l}$和${\sigma }_{C_l}$：
     $${\mu }_{C_l}=\frac{\sum w_{i,j}}{n},\forall v_i,v_j\in C_l,v_i\ne v_j$$
     ${\sigma }_{C_l}$类似更新。
   • 迭代重新分配和更新步骤，直到聚类分配不再变化或达到最大迭代次数。

4. 终止条件：

   • 当所有聚类的进一步分割不再降低编码成本时，算法终止，返回最终聚类结果$V$，其中$k=|V|$为自动确定的聚类数目。

优化过程通过MDL原理自动平衡聚类质量和模型复杂性，确保高效且准确的聚类。

---

主要贡献点

1. 无参数设计：PaCCo无需用户指定聚类数目$k$或社区数量等参数，通过MDL原理自动确定最优聚类数目，解决了传统算法（如谱聚类、Metis）依赖参数的问题。
2. 全自动化：基于MDL的终止准则，PaCCo无需用户干预即可完成聚类，适用于未知结构的加权图。
3. 高效性：采用自顶向下的二分策略，PaCCo在保持高聚类精度的同时，运行时间与参数依赖的算法（如Metis、MCL）相当，比无参数的谱聚类（SpectralZM）快约70倍。
4. 加权图处理：通过考虑边权重信息，PaCCo能够捕捉更丰富的节点相似性信息，相比忽略权重的算法（如Cross-Association）更适合加权图。
5. 生物学应用：在蛋白质交互网络等真实数据集上，PaCCo展示了更高的模块性（modularity）和生物学意义，揭示了功能相关的聚类。

---

实验结果分析

论文通过合成数据和真实数据集（蛋白质交互网络）评估了PaCCo的性能，与三种现有加权图聚类算法（Metis、MCL、SpectralZM）进行了比较。实验结果如下：

1. 合成数据实验：

   • 实验设置：
     • 生成了具有高斯、均匀和拉普拉斯分布边权重的合成加权图，包含1000个节点，$k=20$个聚类，每个聚类50个节点，约70%为聚类内边（约17,000条边）。
     • 进行了三组实验：
       1. 增加噪声边（0至20,000条），测试算法对噪声的鲁棒性。
       2. 改变聚类权重均值间隔（从所有均值相等到均值间隔为1至20），测试对权重分布的适应性。
       3. 改变聚类数目$k$（10至100），测试对数据规模的适应性。
     • 使用调整互信息（Adjusted Mutual Information, AMI）评估聚类性能，AMI值为1表示完美聚类，0表示随机聚类。
   • 结果：
     • 噪声边实验（图4）：PaCCo在所有噪声水平下均优于Metis、MCL和SpectralZM，即使在噪声边达到20,000条时仍保持较高AMI。MCL对噪声敏感，SpectralZM波动大，Metis在拉普拉斯分布数据上表现稍差。
     • 权重间隔实验（图5）：PaCCo在所有分布（高斯、均匀、拉普拉斯）上均取得最高AMI，尤其在拉普拉斯分布上优势明显，表明其对不同权重分布的适应性。Metis在高斯和均匀分布上表现较好，但在拉普拉斯分布上较差；MCL和SpectralZM表现较差（AMI在0至0.5）。
     • 聚类数目实验（图6）：PaCCo在不同$k$值下均保持稳定的高AMI，优于其他算法。Metis在高斯和均匀分布上表现良好，但在拉普拉斯分布上较差；MCL仅在均匀分布大$k$值时表现较好；SpectralZM整体表现不佳。
   • 结论：PaCCo在噪声鲁棒性、权重分布适应性和数据规模扩展性上均优于对比算法，尤其在非高斯分布（如拉普拉斯）上表现出色。

2. 运行时间实验（图7）：

   • 测试了$k$从10到100的运行时间，PaCCo的超线性时间复杂度（远低于SpectralZM的$O(n^3)$）使其在5000节点图上仅需14.1秒，而SpectralZM需16.8分钟，PaCCo快约70倍。PaCCo比MCL快，略慢于Metis，但无需参数调整，综合效率更高。

3. 真实数据实验（图8）：

   • 使用Costanzo等人[4]的酵母蛋白质交互网络（1139个节点），边权重基于基因双敲除实验的生长率变化（±0.15）。
   • 评估指标为加权模块性（weighted modularity），并通过基因本体（Gene Ontology, GO）数据库计算聚类的生物学意义。
   • 结果：
     • PaCCo自动识别11个聚类，模块性最高，且在两个分子功能（水解酶活性、异构酶活性）上显著富集（$p<0.05$和$p<0.01$）。
     • Metis（$k=3$）在水解酶活性上富集，但未发现异构酶活性。MCL（$k=1121$，几乎全是单节点聚类）和SpectralZM（$k=3$）未发现显著富集。
     • PaCCo的聚类结果在生物学意义上更丰富，揭示了并行功能路径的存在（如水解酶和异构酶活性）。

4. 总结：

   • PaCCo在合成数据上展示了优越的聚类精度和鲁棒性，在真实蛋白质网络上取得了最高的模块性和生物学意义，优于Metis、MCL和SpectralZM。
   • PaCCo的无参数和高效特性使其在实际应用中更具优势，尤其适用于未知聚类数目的加权图。

---

算法实现过程详解

PaCCo算法的实现结合了二分k均值策略和MDL原理，通过递归分割图并优化编码成本实现聚类。以下是详细的实现步骤：

1. 算法输入

• 输入：加权无向图的邻接矩阵$A$，其中$a_{i,j}=w_{i,j}$（若边$e_{i,j}\in E$存在），否则$a_{i,j}=0$。对角线元素$a_{i,i}=0$（无自环）。
• 输出：最终聚类结果$V$，包含$k$个互不相交的聚类，$k$由算法自动确定。

2. 主算法（Algorithm 1: PaCCo）

• 初始化：
  • 调用$k$-PaCCo（$k=1$）计算整个图的初始编码成本，获取优于随机的初始聚类$C_{\text{init}}$。
  • 初始化最终聚类结果$V=[]$。
• 递归分割：
  • 调用splitClusters函数，以$C_{\text{init}}$和$A$为输入，递归分割图，直到满足终止条件。
  • 返回$V$，其中$k=|V|$为最终聚类数目。

3. k-PaCCo子例程（Algorithm 2: k-PaCCo）

• 输入：聚类数目$k$（通常$k=2$，用于二分），邻接矩阵$A$，初始高斯分布参数$\mu$和$\sigma$。
• 初始化：
  • 随机分配节点到$k$个聚类，或使用启发式初始化（基于权重分布）。
• 迭代过程：
  • 重新分配：
    • 对每个节点$v_i$，计算其在每个聚类$C_l$中的成本$c(v_i\mid C_l)$：
      $$c(v_i\mid C_l)=c_{\text{weights}}(v_i\mid C_l)+c_{\text{linkage}}(v_i\mid C_l)$$
      其中：
      • 权重成本：
        $$c_{\text{weights}}(v_i\mid C_l)=-{\log }_2\left(\frac{1}{|C_l|}\sum _{v_j\in C_l}\frac{1}{\sqrt{2\pi {\sigma }_{C_l}^2}}\exp \left(-\frac{(w_{ij}-{\mu }_{C_l}{)}^2}{2{\sigma }_{C_l}^2}\right)\right)$$
      • 连接成本：
        $$c_{\text{linkage}}(v_i\mid C_l)=-0.5{\log }_2\left(|e_{i,j^{\prime }}|\right)+0.5{\log }_2\left(|e_{i,j^{\prime \prime }}|\right)$$
    • 将$v_i$分配到成本最低的聚类：
      $$C_{\text{new}}(v_i)=\arg \underset{C_l\in C}{\min }c(v_i\mid C_l)$$
  • 更新：
    • 更新每个聚类的权重分布参数：
      $${\mu }_{C_l}=\frac{\sum w_{i,j}}{n},\forall v_i,v_j\in C_l,v_i\ne v_j$$
      ${\sigma }_{C_l}$类似计算。
  • 终止条件：聚类分配不再变化或达到最大迭代次数。
• 输出：$k$个聚类的分配结果。

4. 分割策略（Algorithm 3: splitClusters）

• 输入：当前聚类分区$C$，邻接矩阵$A$，最终聚类结果$V$。
• 过程：
  • 对每个聚类$C_l\in C$：
    • 若$C_l$包含多于一个节点或$k<|A_l|$，尝试二分：
      • 初始化两个子聚类的高斯分布参数：
        $${\mu }^{\prime }=[{\mu }_{C_l}+{\sigma }_{C_l},{\mu }_{C_l}-{\sigma }_{C_l}],{\sigma }^{\prime }=[{\sigma }_{C_l}/2,{\sigma }_{C_l}/2]$$
      • 调用$k$-PaCCo（$k=2$）生成子聚类$C_{l_{\text{split}}}$。
      • 计算分割后的编码成本$\text{Model-Cost}(G_{l_{\text{split}}}\mid C_{l_{\text{split}}})$，与当前成本比较：
        • 若成本降低，递归调用splitClusters处理子聚类。
        • 否则，将$C_l$加入$V$，停止分割。
    • 若$C_l$为单节点或无法进一步分割，将$C_l$加入$V$。
• 输出：更新后的$V$。

5. 编码成本计算

• 聚类成本：对每个聚类$C_l$，计算所有节点$v_i$的成本总和：
  $$c(C_l)=\sum _{v_i\in C_l}\left(c_{\text{weights}}(v_i\mid C_l)+c_{\text{linkage}}(v_i\mid C_l)\right)$$
• 参数成本：存储每个聚类的${\mu }_{C_l}$和${\sigma }_{C_l}$，以浮点精度编码，成本$c(p)$与$k$成正比。
• 总成本：
  $$\text{Model-Cost}(G\mid C)=\sum _{l=1}^{k}c(C_l)+c(p)$$

6. 终止与输出

• 算法在所有聚类无法进一步分割（即分割不降低成本）时终止。
• 输出最终聚类$V$，其中$k=|V|$为自动确定的聚类数目。

7. 实现细节

• 数据结构：使用邻接矩阵存储图，便于快速访问边权重。
• 启发式初始化：通过权重分布的均值和标准差引导子聚类初始化，避免随机初始化的低效。
• 优化策略：递归二分和k均值迭代确保高效收敛，同时MDL原理自动平衡聚类数目和质量。
• 编程实现：论文中提到PaCCo用Java实现，运行在2.9GHz Windows计算机上，内存3GB。

---

总结

PaCCo通过将加权图聚类问题转化为数据压缩问题，结合MDL原理和二分k均值策略，实现了无参数、自动化的高效聚类。其目标函数通过最小化编码成本优化聚类结构，考虑边权重和连接性，优化过程通过递归分割和迭代更新实现。实验证明PaCCo在合成和真实数据上优于Metis、MCL和SpectralZM，运行时间显著优于无参数的SpectralZM。算法的实现清晰，结合启发式初始化和MDL终止准则，适合处理复杂加权图数据，如蛋白质交互网络，具有广泛的应用前景。