A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems

基本信息

• 论文ID: 2511.03157
• 标题: A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
• 作者: Yi Zhou (University of Electronic Science and Technology of China), Chunyu Luo (University of Electronic Science and Technology of China), Zhengren Wang (Peking University), Zhang-Hua Fu (Shenzhen Institute of Artificial Intelligence and Robotics for Society, CUHK Shenzhen)
• 分类: cs.DS (Data Structures and Algorithms)
• 发表时间: 2025年11月6日 (arXiv v2)
• 论文链接: https://arxiv.org/abs/2511.03157v2

摘要

本文研究最大低直径f(·)-稠密子图问题（MfDS）。f(·)-稠密图是指具有n个顶点且至少有f(n)条边的图，其中f(·)是一个定义良好的函数。这一概念涵盖了γ-拟团、k-缺陷团和稠密团等多种团松弛模型。然而，f(·)-稠密图可能不连通或弱连通。为解决此问题，本文研究寻找直径不超过2的最大f(·)-稠密子图。具体而言，提出了一种基于分解的分支定界算法来最优求解该问题。算法的关键特征是将图分解为n个较小子图，允许在每个子图中独立搜索。论文还引入了退化排序和两跳退化排序等分解策略，以及带有新颖排序上界的分支定界算法。在139个真实图上的实验结果表明，该算法优于MIP求解器和纯分支定界方法，在一小时内最优求解的实例数量几乎是后者的两倍。

研究背景与动机

1. 要解决的问题

在网络分析中，识别紧密连接的子图（cohesive subgraph）是一个核心任务，应用于社区发现、蛋白质复合物识别、金融网络分析等领域。经典的团（clique）模型要求所有顶点对之间都有边，但这一要求过于严格，尤其在存在噪声和错误的实际应用中。因此，出现了多种松弛团模型，如：

• γ-拟团：n个顶点的导出子图至少有γ(n choose 2)条边
• s-缺陷团：至少有(n choose 2) - s条边
• 平均s-plex：至少有n(n-s)/2条边

这些模型可以统一表示为f(·)-稠密图：n个顶点的图至少有f(n)条边。

2. 问题的重要性

现有的f(·)-稠密图模型存在严重缺陷：可能不连通或连通性很弱。论文通过图1展示了两个例子：

• G1：200个顶点的团加上10个顶点的路径，从v1到v210需要10跳
• G2：200个顶点的团加上10个孤立顶点，v1和v210之间无路径

这两个图都满足f(n)=0.9(n choose 2)的稠密性要求，但显然不是紧密连接的社区。

3. 现有方法的局限性

• MIP方法：虽然存在针对特定f(·)函数的混合整数规划模型（如GF3），但对于大规模图效率低下，且没有针对低直径约束的MIP模型
• 分支定界方法：已有针对特定问题（如最大s-缺陷团、最大γ-拟团）的算法，但缺乏通用的f(·)-稠密图求解框架
• 连通性约束：Santos et al. (2024)提出基于生成树的连通约束，但直径约束更能保证紧密连接性

4. 研究动机

本文引入低直径f(·)-稠密图概念：要求图是连通的、有至少f(n)条边、且直径不超过2。直径为2的约束（称为2-club）确保任意两个顶点之间的最短路径不超过2，保证了强连通性。论文旨在设计高效的精确算法来求解这一NP-hard问题。

核心贡献

1. 问题形式化：
   • 首次系统定义f(·)-稠密图及其遗传性质（hereditary property）
   • 形式化最大低直径f(·)-稠密子图问题（MfDS）
   • 提供MIP-fD混合整数线性规划模型
2. 算法框架：
   • 提出基于图分解的预处理框架，将输入图分解为n个较小子图
   • 引入两种分解策略：退化排序（degeneracy ordering）和两跳退化排序（two-hop degeneracy ordering）
   • 设计带有新颖排序上界的分支定界算法
   • 提供各组件和整体算法的最坏情况复杂度分析
3. 实验验证：
   • 在139个真实图上测试两种f(·)函数（γ-拟团和s-缺陷团）
   • 证明分解框架显著提升性能，一小时内求解实例数是纯分支定界的两倍
   • 展示排序上界方法大幅减少搜索树规模

方法详解

任务定义

输入：

• 无向简单图G=(V,E)
• 密度函数f: ℤ≥0 → ℝ，满足f(i) ≤ (i choose 2)
• f(·)的计算oracle（常数时间）

输出：最大顶点集S⊆V，使得：

1. |E(S)| ≥ f(|S|)（f(·)-稠密性）
2. diam(GS) ≤ 2（低直径约束）

目标：ωf(G) = max{|S| : S⊆V, |E(S)|≥f(|S|), diam(GS)≤2}

复杂度：NP-hard、W1-hard、难以多项式时间近似（因为最大团是特例）

核心算法框架

1. 整体分解框架（Algorithm 1）

关键引理（Lemma 3）：给定图G的任意顶点排序π=⟨v1,...,vn⟩，对每个顶点vi，定义：

• Vi = {vi} ∪ {N^(2)_G(vi) ∩ {vi+1,...,vn}}
• Gi = GVi

如果S_i是Gi中包含vi的最大低直径f(·)-稠密子图，则： **ωf(G) = max(|S_1|,...,|S*_n|)**

算法流程：

1. 用启发式算法获得初始解S（下界）
2. 用排序算法确定顶点顺序π
3. For each vi in π:
   - 构造子图Gi = G[Vi]
   - 用ExactSearch(Gi, f(·), {vi}, N^(2)_G(vi), lb)求解
4. 返回所有子问题的最大解

时间复杂度：O(Theur(G) + Torder(G) + poly(αG)2^αG)

• αG = max(|V1|,...,|Vn|)：最大子图规模
• 关键是最小化αG以控制指数部分

2. 高效启发式算法（Algorithm 2）

基于退化排序（degeneracy ordering）：

• 定义：k-退化排序是顶点排序⟨v1,...,vn⟩，使得每个vi在{vi,...,vn}导出子图中的度数≤k
• 计算：用peel算法，O(|V|+|E|)时间，反复删除最小度数顶点
• 退化度dG：最小的k值

启发式流程：

1. 计算退化排序⟨v1,...,vn⟩
2. For each vi:
   - Si ← {vi} ∪ {NG(vi) ∩ {vi+1,...,vn}}
   - Gi ← G[Si]（直径≤2）
   - While |Ei| < f(|Si|):
       删除Gi中最小度数顶点
   - 更新最优解S*
3. 返回S*

时间复杂度：O(|E| + |V|d²G)

• 实际图中dG << |V|（如ca-dblp-2010: dG=74, |V|=226413）

3. 顶点排序策略

方案1：退化排序

• 优势：O(|V|+|E|)时间
• 界限：αG ≤ min(dG·ΔG, |V|)
• 证明：|Vi| = 1 + |NG(vi)∩{vi+1,...,vn}| + |N^(2)_G(vi)\NG(vi)∩{vi+1,...,vn}| ≤ 1 + dG + dG·ΔG

方案2：两跳退化排序（Algorithm 3）

• 定义：k-两跳退化排序使得每个vi在{vi,...,vn}中的两跳邻居数≤k
• 计算：类似peel，反复删除最小|N^(2)_G(v)|的顶点
• 时间复杂度：O(|V||E|·min(tdG, ΔG))
• 界限：αG ≤ tdG
• 优势：tdG通常远小于dG·ΔG（如ca-dblp-2010: tdG=238 vs dG·ΔG=17612）

分支定界算法（Algorithm 4）

核心结构

BranchBound(G, S, C, lb):
  输入：图G，当前解S，候选集C，下界lb
  
  1. 如果G[S]是可行解且|S|>lb：更新lb和最优解
  
  2. 如果f(·)是遗传的且|E(S)|<f(|S|)：剪枝返回
  
  3. UB ← SortBound(G, f(·), S, C)  // 计算上界
  
  4. 如果UB ≤ lb：剪枝返回
  
  5. 如果f(·)是遗传的：应用削减规则（Lemma 5）
  
  6. 随机选择u∈C
  
  7. 如果满足Lemma 4的条件：只递归S∪{u}分支
     否则：递归两个分支S∪{u}和S

削减规则（Lemma 4 & 5）

Lemma 4（通用削减）：如果u∈C满足：

1. |NG(u)| = |V|-1，或
2. |NG(u)| = |V|-2 且 GS∪{u}可行

则存在包含u的最优解 → 只需搜索包含u的分支

Lemma 5（遗传函数削减）：如果f(·)是遗传的：

1. 若|E(S)| < f(|S|)，则无包含S的可行解
2. 若v∈C使得|E(S∪{v})| < f(|S|+1)，则无包含v的可行解

排序上界算法（Algorithm 5）

简单上界（Section 4.6.1）

对v∈C，定义wS(v) = |S\N(v)|（S中非v邻居的数量）

1. 按wS(v)非递减排序C得⟨v1,...,v|C|⟩
2. 找最大k使得wS(Sk) + |E(S)| ≤ gf(|S|+k)，其中gf(n)=(n choose 2)-f(n)
3. 返回|S|+k

正确性（Lemma 6）：wS(S') + |E(S)|低估了|E(S∪S')|

改进的排序上界（SortBound）

核心思想：

1. 简单上界忽略了S和C之间的边
2. 简单上界未考虑两跳约束

算法流程：

1. 用贪心算法将C划分为χ个独立集Π1,...,Πχ
   （最小化χ ≈ 图着色问题，用O(|C|³)贪心）

2. For each Πi:
   a. 按wS(v)排序Πi
   b. 进一步划分Πi为多个Rσ，使得Rσ中任意两顶点距离>2
   c. 从每个Rσ选择wS(·)最小的顶点加入C'
   d. 计算w'S(uj) = wS(uj) + j - 1

3. 按w'S(·)排序C'，找最大k使得|E(S)| + w'S(Sk) ≤ gf(|S|+k)

4. 返回|S|+k

时间复杂度：O(|C|³ + |S||C|)

正确性（Theorem 3）：

• 每个独立集Πi中至多选s'i个顶点
• 每个Rσ中因两跳约束至多选1个顶点
• |E(S*)| ≥ |E(S)| + Σw'S(v^(ij)m) ≥ |E(S)| + Σ^{|S'|} w'S(vj)

优势：

• 考虑了独立集结构（减少边数高估）
• 考虑了两跳约束（每个Rσ至多1个顶点）
• 比LP松弛更快，界限接近

实验设置

数据集

• 来源：Network Data Repository
• 规模：139个真实无向图
• 范围：最多5.87×10⁷个顶点，1.06×10⁸条边
• 领域：社交网络、生物网络、协作网络、道路网络等

f(·)函数配置

1. γ-拟团：f(i) = γ(i choose 2)，γ ∈ {0.99, 0.95, 0.90, 0.85}
   • 非遗传函数
2. s-缺陷团：f(i) = (i choose 2) - s，s ∈ {1, 3}
   • 遗传函数

对比算法

1. Deg-BnB：退化排序 + 分支定界
2. TwoDeg-BnB：两跳退化排序 + 分支定界
3. BnB：纯分支定界（无分解）
4. MIP：Gurobi求解器 + MIP-fD模型
5. Deg-MIP：退化排序分解 + MIP求解子问题
6. TwoDeg-MIP：两跳退化排序分解 + MIP求解子问题

实验环境

• CPU：Intel Xeon Platinum 8360Y @ 2.40GHz
• 系统：Ubuntu 22.04
• 编译：g++ 9.3.0 with -Ofast
• 时间限制：3600秒（1小时）
• 代码：https://github.com/cy-Luo000/MDSL

评价指标

• 在不同时间节点求解的实例数量
• 具体图的运行时间
• 上界紧度（与最优解的差距）
• 搜索树节点数

实验结果

主要结果

1. 整体性能（Figure 4 & 5）

γ-拟团（γ=0.99, 0.95）：

• TwoDeg-BnB和Deg-BnB在所有时间段全面优于其他算法
• 1小时内，TwoDeg-BnB求解约100个实例，BnB仅50个
• MIP几乎无法求解任何实例

γ-拟团（γ=0.90, 0.85）：

• 1000秒后，TwoDeg-MIP和Deg-MIP与分支定界方法性能接近
• 分解框架使MIP性能显著提升

s-缺陷团（s=1, 3）：

• TwoDeg-BnB和Deg-BnB求解约110个实例
• 纯BnB约60个实例
• 遗传性质使分支定界方法更有优势

关键发现：分解框架使求解实例数翻倍

2. 大规模图详细结果（Table 1 & 2）

显著案例（γ=0.99）：

• web-uk-2005（129,632顶点）：TwoDeg-BnB 634秒，MIP超时
• inf-road-usa（23,947,347顶点）：TwoDeg-BnB 70秒，其他方法超时
• scc_infect-dublin：Deg-BnB 0.54秒，TwoDeg-BnB超时（排序选择影响）

加速效果：

• TwoDeg-BnB比BnB快2-3个数量级（如web-indochina-2004: 0.25秒 vs 超时）
• 39个实例TwoDeg-BnB或Deg-BnB求解但BnB失败
• 分解+MIP有时优于纯组合算法（如web-sk-2005）

s-缺陷团（Table 2）：

• 遗传性质带来更多削减
• scc_infect-dublin (s=1): TwoDeg-BnB 0.83秒 vs Deg-MIP超时
• rec-amazon: TwoDeg-BnB 0.08秒 vs BnB 264秒

消融实验

上界有效性分析（Table 3 & 4）

上界紧度比较：

LP松弛 > SortBound > Simple Bound

具体案例（γ=0.95）：

• ca-CondMat：
  • Optimal: 28
  • LP: 29, Simple: 280, SortBound: 142
  • SortBound在紧度和可扩展性间取得平衡
• inf-roadNet-CA：
  • Optimal: 4
  • LP: 无法计算, Simple: 13, SortBound: 5
  • LP在大图上失效

搜索树规模影响：

• inf-roadNet-CA (γ=0.95)：
  • TwoDeg-BnB: 5秒，10节点
  • TwoDeg-BnB/ub（无SortBound）: 10秒，14,138,820节点
  • 搜索树缩减6个数量级
• ca-MathSciNet (s=3)：
  • TwoDeg-BnB: 7.62秒，80节点
  • TwoDeg-BnB/ub: 1228秒，256,325,020节点
  • 加速100倍

关键发现：SortBound在保持紧度的同时可扩展到百万级顶点图

αG与运行时间关系（Figure 6 & 7）

观察：

• 近半数实例αG ≤ 1000（远小于|V|）
• 运行时间与αG呈正相关
• 两跳退化排序通常产生更小的αG

典型案例：

• ca-dblp-2010：|V|=226,413, dG=74, tdG=238, dG·ΔG=17,612
  • 两跳退化排序优势明显

验证：支持最小化αG的设计理念

案例分析

图分解效果示例

以web-indochina-2004为例（|V|=11,358, |E|=47,606）：

• 退化度：dG=49
• 两跳退化度：tdG=199
• 分解后：αG=199（两跳排序）vs αG≈2450（退化排序）
• 性能：TwoDeg-BnB 0.25秒 vs Deg-BnB 0.18秒 vs BnB 12.10秒

上界算法示例（Figure 2 & 3）

输入：10个顶点，S={v1,v2}，C={v3,...,v10}

步骤：

1. 划分为独立集：Π1={v3,v5,v7,v9}, Π2={v4,v6,v8,v10}
2. 计算wS：wS(v3)=0, wS(v5)=1, wS(v7)=2...
3. 按距离进一步划分：R¹₁={v3,v7}, R²₁={v5,v9}, R¹₂={v8,v4}, R²₂={v10,v6}
4. 选择最小wS：C'={v3,v5,v8,v10}
5. 计算w'S：w'S(v3)=0, w'S(v8)=0, w'S(v5)=2, w'S(v10)=2

结果：

• f(i)=0.8(i choose 2): 上界=4
• f(i)=(i choose 2)-4: 上界=5

相关工作

1. 松弛团模型

• γ-拟团（Abello et al. 2002）：NP-hard for γ∈(0,1]
  • MIP方法（Pattillo et al. 2013a）
  • 分支定界（Mahdavi Pajouh et al. 2014, Ribeiro & Riveaux 2019）
• s-缺陷团（Yu et al. 2006）：NP-hard for s≥1
  • 低直径约束（Luo et al. 2024）：O(nc·1.2ⁿ)
  • 分支定界（Chen et al. 2021b, Gao et al. 2022, Chang 2023）
• 平均s-plex（Veremyev et al. 2016）

2. 通用f(·)-稠密图

• Veremyev et al. 2016：
  • 提出多个MIP模型（GF3最优）
  • 未考虑低直径约束
• 复杂度结果（Asahiro et al. 2002）：
  • f(n)=Θ(n^(1+ε))或f(n)=n+Ω(n^ε)时NP-hard
  • f(n)=n+c时多项式可解

3. 2-club问题

• 定义：直径≤2的子图
• MIP方法（Pajouh et al. 2016, Lu et al. 2022）
• 分支定界（Hartung et al. 2012, Komusiewicz et al. 2019）
• 本文贡献：首次结合2-club与f(·)-稠密约束

4. 连通性约束

• Santos et al. 2024：基于生成树的连通γ-拟团
• 本文优势：直径约束比单纯连通性更强

5. 图分解技术

• 退化排序（Matula & Beck 1983）：O(|V|+|E|)
• 两跳退化（Wünsche 2021）：首次用于k-plex和k-club
• 本文创新：系统应用于通用f(·)-稠密图

结论与讨论

主要结论

1. 理论贡献：
   • 系统化f(·)-稠密图理论框架
   • 证明遗传性质的充要条件
   • 提供分解框架的正确性和复杂度分析
2. 算法贡献：
   • 分解框架将问题分解为n个独立子问题
   • 两跳退化排序有效控制子图规模
   • 排序上界在紧度和效率间取得平衡
3. 实验验证：
   • 139个真实图上求解实例数翻倍
   • 可扩展到千万级顶点图
   • 排序上界减少搜索树6个数量级

局限性

1. 算法局限：
   • 仍是指数时间算法（O(2^αG)）
   • 对稠密图αG可能接近|V|
   • 两种排序策略难以预先判断优劣
2. 模型局限：
   • 直径=2的约束可能过于严格
   • 未考虑顶点权重或边权重
   • f(·)需满足特定条件才有遗传性
3. 实验局限：
   • 仅测试两种f(·)函数
   • 未与所有相关工作直接比较
   • 缺少对超大规模图（亿级顶点）的测试

未来方向

1. 算法扩展：
   • 并行化分解框架（子图独立可并行）
   • 扩展到其他直径约束（k-club, k≥3）
   • 结合其他结构约束（顶点连通度）
2. 理论深化：
   • 更多f(·)函数的遗传性分析
   • 参数化复杂度研究
   • 近似算法设计
3. 应用拓展：
   • 动态图上的增量算法
   • 加权图扩展
   • 特定领域模型（如生物网络）

深度评价

优点

1. 理论严谨性：
   • 完整的数学证明（附录A）
   • 清晰的复杂度分析
   • 遗传性质的充要条件（Lemma 1 & 2）
2. 算法创新性：
   • 分解框架：Lemma 3巧妙地将全局问题分解为局部问题
   • 两跳退化排序：针对直径约束的创新排序策略
   • 排序上界：多层嵌套划分（独立集+距离约束）设计精妙
3. 实验全面性：
   • 139个真实图，6种算法，2类f(·)函数
   • 详细的消融实验（Table 3 & 4）
   • 可视化分析（Figure 6 & 7）
   • 开源代码保证可复现性
4. 实用价值：
   • 可扩展到千万级顶点
   • 比MIP快数个数量级
   • 通用框架适用多种团松弛模型
5. 写作清晰度：
   • 引言动机明确（Figure 1直观）
   • 算法伪代码详细
   • 定理证明完整

不足

1. 排序策略选择：
   • 缺乏理论指导何时用退化vs两跳退化
   • Table 1显示有时Deg-BnB更快（如scc_infect-dublin）
   • 建议：可设计自适应策略或提供选择启发式
2. 上界算法复杂度：
   • O(|C|³)可能成为瓶颈
   • 贪心着色非最优
   • 改进方向：用更快的着色算法或放松最优性
3. 实验对比：
   • 未与Santos et al. 2024的生成树方法比较
   • 缺少与特定问题最优算法的对比（如Chang 2023的k-defective clique算法）
   • MIP模型可能有改进空间（如添加有效不等式）
4. 可扩展性分析：
   • 对αG>10,000的情况讨论不足
   • 稠密图性能未充分测试
   • 内存消耗分析缺失
5. 理论空白：
   • 未提供近似比分析
   • 参数化复杂度（如以αG为参数）未讨论
   • 平均情况复杂度未分析

影响力

1. 学术贡献：
   • 统一多种团松弛模型的理论框架
   • 分解技术可迁移到其他子图提取问题
   • 引用价值高（结合NP-hard问题、图分解、分支定界）
2. 实用价值：
   • 社区发现、生物信息学等领域直接应用
   • 开源代码促进技术转化
   • 可作为其他算法的baseline
3. 可复现性：
   • 算法描述详细
   • 代码开源（https://github.com/cy-Luo000/MDSL）
   • 数据集公开（Network Data Repository）
   • 实验设置明确
4. 局限性：
   • 工业级应用需进一步优化（如并行化）
   • 对特定f(·)的定制算法可能更优
   • 需要更多领域专家验证实用性

适用场景

推荐场景：

1. 社交网络分析：寻找紧密连接的社区（直径≤2保证快速通信）
2. 生物网络：蛋白质复合物识别（允许少量缺失边）
3. 协作网络：核心研究团队识别
4. 中等规模图：|V|<10⁶, αG<5000时性能最优

不推荐场景：

1. 超大规模稠密图：αG接近|V|时指数爆炸
2. 实时应用：最坏情况仍需指数时间
3. 近似解足够场景：精确算法代价高

改进建议：

1. 结合启发式算法提供快速近似解
2. 并行化处理超大规模图
3. 针对特定f(·)设计专用算法

参考文献

核心相关工作

1. Veremyev et al. (2016): "Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs" - 提出GF3 MIP模型
2. Luo et al. (2024): "A faster branching algorithm for the maximum k-defective clique problem" - ECAI 2024，O(nc·1.2ⁿ)算法
3. Chang (2023): "Efficient maximum k-defective clique computation with improved time complexity" - PACMMOD，改进的分支定界
4. Santos et al. (2024): "Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems" - 生成树连通约束
5. Wünsche (2021): "Mind the gap when searching for relaxed cliques" - 首次提出两跳退化排序

理论基础

6. Matula & Beck (1983): "Smallest-last ordering and clustering and graph coloring algorithms" - 退化排序的经典工作
7. Asahiro et al. (2002): "Complexity of finding dense subgraphs" - f(·)-稠密图的复杂度结果
8. Downey & Fellows (2012): "Parameterized complexity" - W1-hardness理论

总体评价：这是一篇理论严谨、算法创新、实验充分的优秀论文。分解框架和排序上界方法具有较高的通用性和实用价值。主要贡献在于统一了多种团松弛模型并提供了高效求解算法。建议接收，对图算法和网络分析领域有重要贡献。