2025-11-13T01:28:10.704881

Revisiting Madigan and Mosurski: Collapsibility via Minimal Separators

Heng, Sun, He et al.
Collapsibility provides a principled approach for dimension reduction in contingency tables and graphical models. Madigan and Mosurski (1990) pioneered the study of minimal collapsible sets in decomposable models, but existing algorithms for general graphs remain computationally demanding. We show that a model is collapsible onto a target set precisely when that set contains all minimal separators between its non-adjacent vertices. This insight motivates the Close Minimal Separator Absorption (CMSA) algorithm, which constructs minimal collapsible sets using only local separator searches at very low costs. Simulations confirm substantial efficiency gains, making collapsibility analysis practical in high-dimensional settings.
academic

Revisiting Madigan and Mosurski: Collapsibility via Minimal Separators

基本信息

  • 论文ID: 2510.09024
  • 标题: Revisiting Madigan and Mosurski: Collapsibility via Minimal Separators
  • 作者: Pei Heng (Northeast Normal University), Yi Sun (Xinjiang University), Shiyuan He, Jianhua Guo (Beijing Technology and Business University)
  • 分类: stat.ME (Statistics - Methodology)
  • 发表期刊: Biometrika (2025), 103, 1, p. 1
  • 论文链接: https://arxiv.org/abs/2510.09024

摘要

可折叠性为列联表和图模型中的降维提供了一种有原则的方法。Madigan和Mosurski (1990)开创了可分解模型中最小可折叠集的研究，但现有的一般图算法在计算上仍然很苛刻。本文证明了当且仅当目标集包含其非邻接顶点之间的所有最小分离器时，模型可折叠到该目标集上。这一洞察激发了紧密最小分离器吸收(CMSA)算法，该算法仅使用成本极低的局部分离器搜索来构造最小可折叠集。仿真证实了显著的效率提升，使得可折叠性分析在高维设置中变得实用。

研究背景与动机

问题背景

可折叠性是多元统计分析中的经典概念，最早由Yule (1903)和Simpson (1951)引入。在对数线性模型框架内，它提供了一种在不扭曲边际关联的情况下移除变量来简化统计分析的有原则方法。

核心问题

对于给定的目标变量集，如何找到模型能够折叠到的最小超集而不失推断有效性？这样的超集被称为最小可折叠集。

现有方法局限

  1. **Madigan & Mosurski (1990)**的选择性无环超图约简(SAHR)算法仅适用于可分解图模型
  2. **Wang et al. (2011)的凸包方法和Heng & Sun (2023)**的路径吸收方法通常需要全局图操作，在高维模型中计算成本昂贵
  3. 缺乏基于局部图性质的高效算法

研究动机

本文从新的角度重新审视最小可折叠性，旨在：

  1. 提供基于分离器的可折叠性刻画
  2. 开发基于局部操作的高效算法
  3. 使可折叠性分析在高维图模型中变得实用

核心贡献

  1. 理论贡献：证明了图模型可折叠到目标集当且仅当该集合包含其非邻接顶点之间的所有最小分离器
  2. 算法创新：提出了紧密最小分离器吸收(CMSA)算法，通过局部分离器搜索构造最小可折叠集
  3. 计算效率：CMSA算法具有O(nm)时间复杂度和O(n)空间复杂度，优于现有方法
  4. 实用价值：使可折叠性分析在高维设置中变得实际可行

方法详解

任务定义

输入：分层对数线性模型L及其交互图G=(V,E)，目标变量集A⊆V 输出：包含A的最小可折叠集μ 约束：模型L可折叠到μ上，且μ是满足此条件的最小集合

核心理论

关键引理

引理1 (Asmussen & Edwards, 1983): 图模型L可折叠到子集A⊆V当且仅当对于任意X,Y⊆A，X⊥Y|SG蕴含X⊥Y|S∩AG。

主要定理

定理1: 图模型L可折叠到子集A⊆V当且仅当A包含A中每对非邻接顶点x,y的每个最小xy-分离器。

推论1: 图模型L可折叠到子集A⊆V当且仅当A包含A中每对非邻接顶点x,y的至少一个最小xy-分离器。

CMSA算法架构

关键概念

紧密最小分离器 (Definition 2): 对于任意两个非邻接顶点x,y∈V，如果最小xy-分离器S完全位于x的邻域内，即S⊆N_G(x)，则称S为接近x的分离器，记为S_G(x,y)。

算法流程

CMSA算法包含以下主要步骤：

  1. 组件识别：识别G_{V\A}的所有连通组件M₁,...,M_K
  2. 局部处理：对每个连通组件M_i：
    • 初始化μᵢ := A
    • 迭代识别G_{Mᵢ}的连通组件邻域中的非邻接顶点对
    • 吸收它们的紧密最小分离器到μᵢ中
    • 当所有连通组件的邻域形成完全子集时停止
  3. 结果合并：合并所有μᵢ得到最终的最小可折叠集μ = ⋃ᵢμᵢ

技术创新点

  1. 局部化策略：将全局图操作转化为局部分离器搜索
  2. 紧密分离器利用：利用紧密分离器的性质避免全图遍历
  3. 组件分解：通过连通组件分解降低问题复杂度
  4. 增量构造：迭代吸收分离器直至满足终止条件

实验设置

数据集

  1. 可分解图模型：
    • 图规模：n ∈ {250, 500, 750, 1000}
    • 边概率：p ∈ {0.1, 0.01}
    • 每个配置生成100个随机弦图
  2. 一般图模型：
    • 图规模：n ∈ {2500, 5000, 7500, 10000}
    • 边概率：p ∈ {0.1, 0.01, 0.005, 0.001}
    • 基于随机树添加边生成随机图

评价指标

  • 运行时间：算法执行的平均时间（秒）
  • 效率比较：与基线方法的相对性能

对比方法

  1. SAHR (Madigan & Mosurski, 1990)：适用于可分解图
  2. IPA (Heng & Sun, 2023)：诱导路径吸收算法，适用于一般图

实现细节

  • 编程语言：C语言实现核心算法，Python接口
  • 硬件环境：Intel Xeon Silver 4215R CPU，128 GB RAM
  • 每个图随机选择10个目标顶点进行测试

实验结果

可分解图模型结果

节点数2505007501000
平均边数529/33341812/129123567/286526062/52959
CMSA0.0007/0.00120.0021/0.00470.0044/0.01120.0072/0.0248
SAHR0.0113/0.06110.0681/0.54550.1876/2.16480.3808/6.6983

关键发现：

  • CMSA在所有图规模和密度下都显著优于SAHR
  • 随着节点和边数增长，CMSA的优势越来越明显
  • 在最大规模图(1000节点，高密度)中，CMSA比SAHR快约270倍

一般图模型结果

实验结果显示CMSA在密集图上比IPA效率显著更高，性能优势随节点数增长而增加。在稀疏图上，两种算法的运行时间都显著降低，但CMSA始终保持较优的效率。

案例分析

例1：考虑图G和目标集A = {c, b}

  1. 初始连通组件：M₁ = {x}, M₂ = {a, d}, M₃ = {g, l, t}
  2. 处理M₂时发现非邻接对{c, b}，吸收分离器{a}
  3. 处理M₃时同样处理{c, b}对，吸收分离器{l}
  4. 最终得到最小可折叠集{a, c, l, b}

相关工作

可折叠性理论发展

  1. Yule (1903), Simpson (1951)：首次引入可折叠性概念
  2. Asmussen & Edwards (1983)：在Biometrika上给出严格的理论阐述
  3. Madigan & Mosurski (1990)：在Biometrika上提出最小可折叠集问题

算法发展脉络

  1. SAHR算法：仅适用于可分解图，效率高但适用性有限
  2. 凸包方法 (Wang et al., 2011)：扩展到一般图但计算成本高
  3. 路径吸收方法 (Heng & Sun, 2023)：改进效率但仍需全局操作

本文贡献定位

本文通过分离器视角统一了可折叠性理论，提供了首个基于纯局部操作的高效算法。

结论与讨论

主要结论

  1. 理论突破：建立了可折叠性与最小分离器的等价关系
  2. 算法创新：CMSA算法实现了从全局到局部的范式转换
  3. 效率提升：在各种图模型中都取得了显著的计算效率提升
  4. 实用价值：使高维图模型的可折叠性分析变得实际可行

局限性

  1. 理论假设：基于分层对数线性模型框架
  2. 图结构依赖：算法效率可能受特定图结构影响
  3. 实现复杂性：需要高效的分离器搜索实现

未来方向

  1. 扩展到混合图模型（离散和连续变量）
  2. 研究在线/动态图的可折叠性分析
  3. 探索分离器视角在其他图推理问题中的应用

深度评价

优点

  1. 理论深度：提供了可折叠性的全新理论视角，将全局问题转化为局部分离器问题
  2. 算法创新：CMSA算法设计巧妙，充分利用了紧密分离器的局部性质
  3. 实验充分：在多种图规模和密度下进行了全面的性能评估
  4. 实用价值：显著的效率提升使得方法在实际应用中更有价值

不足

  1. 适用范围：主要针对无向图模型，对有向图的扩展性不明确
  2. 比较基线：在一般图模型中只与IPA算法比较，缺乏更多基线方法
  3. 理论分析：缺乏平均情况下的复杂度分析
  4. 实际应用：缺乏真实数据集上的应用案例

影响力

  1. 学术贡献：为图模型中的可折叠性研究提供了新的理论框架
  2. 实用价值：算法效率的显著提升使其在大规模数据分析中具有实际应用潜力
  3. 可复现性：作者提供了完整的开源代码，增强了结果的可复现性
  4. 后续研究：分离器视角可能启发其他图推理问题的研究

适用场景

  1. 高维列联表分析：当需要进行变量降维时
  2. 大规模图模型推理：计算资源受限的情况下
  3. 因果推断：识别最小充分集进行因果效应估计
  4. 数据挖掘：特征选择和降维任务

参考文献

本文主要建立在以下关键文献基础上：

  1. Asmussen, S. & Edwards, D. (1983). Collapsibility and response variables in contingency tables. Biometrika.
  2. Madigan, D. & Mosurski, K. (1990). An extension of the results of asmussen and edwards on collapsibility in contingency tables. Biometrika.
  3. Takata, K. (2010). Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph.
  4. Wang, X., Guo, J. & He, X. (2011). Finding the minimal set for collapsible graphical models.