近日，我校郭建华教授团队在因果推断算法研究上取得重要突破。郭建华教授团队在国际机器学习与人工智能顶级会议——第四十二届国际机器学习会议（International Conference on Machine Learning, ICML）上提交的论文“An Improved Clique-Picking Algorithm for Counting Markov Equivalent DAGs via Super Cliques Transfer”（基于超团转移的团选取算法快速计算马尔可夫等价类规模），入选全部投稿论文前1%，被评选为口头报告论文。

该会议共收到专家学者投稿论文共计12107篇，其中仅有120篇被评选为口头报告。会议审稿人对郭建华教授团队提交的论文给予高度认可，一致认为：“这篇论文解决了高效计算马尔可夫等价类规模这一重要的算法问题，极大提升了现有方法的效率。这种计算能力对贝叶斯实验设计方法尤其重要。论文在算法方面作出了重要的贡献，并提供了扎实的理论支撑”。

图1:会议论文截图

本项论文成果由郭建华教授（通讯作者）带领研究，东北师范大学数学与统计学院博士研究生刘力夫、obao欧宝娱乐 数学与统计学院副教授贺诗源为共同第一作者。该研究聚焦因果推理领域，具体针对高效计算有向无环图（Directed Acyclic Graph, DAG）的马尔可夫等价类（Markov Equivalence Class, MEC）规模这一关键科学问题，从算法设计与理论分析两个维度，对提升计算效率、减少算法冗余及理论支撑方面作出了重要且创新性的贡献。

在因果推理中，有向无环图（DAG）是描述变量之间因果关系的基础工具。但在实际研究中，研究人员从有限观测数据无法唯一确定变量间的因果关系结构，只能识别出一组代表相同条件独立关系的DAG，即马尔可夫等价类（MEC）。MEC的规模代表了因果结构的不确定程度，对进一步的科研实证环节至关重要。在流行病学、经济因果分析、医疗干预设计、政策评估以及智能系统自动推理等诸多领域中，精确量化因果结构的不确定性，能够助力科研人员和决策者更高效地获取因果结构、设计干预实验、评估潜在风险并制定优化策略，为决策过程提供更为精准的科学依据。

在既有的MEC规模计算研究中，已知的Clique-Picking算法，通过选取不同的团为根节点，不断将MEC拆分为不同的子类，并递归计算每个子类中的DAG数量。但由于子类之间存在大量结构上的重复与相似性，计算过程中产生大量冗余，严重影响计算效率。

图2：传统Clique-Picking算法

通过选取不同团为根，对马尔可夫等价类分类

针对这一难题，研究团队发现，不同子类在图结构上存在高度的相似性，特别是在图结构的无向部分——即连通分量集合上，结构相似性可以被精确识别与利用。借助图论中“团树”（Clique tree）工具，研究团队提出了高阶图结构—— “超团”（Super Clique）和“超残差”（Super Residual），以此清晰刻画和高效处理不同MEC子类间复杂的相互关系。

在引入高阶图结构的基础之上，研究团队提出了超团转移（Super Cliques Transfer，SC-Trans）算法。这一创新算法能够在迭代计算新子类图结构时，巧妙利用前序计算的“超团”和“超残差”结构，直接获取重叠的结构信息，并通过局部的转移操作迅速补充不重叠的部分，从而极大减少冗余计算，提升计算效率。

图3:研究团队在团树中构造“超团”结构，

并设计算法实现不同团树间的结构快速转换

研究团队不仅从理论上给出了SC-Trans算法的完整证明，更通过大量模拟验证了算法的高效性，展现算法在实际应用中的巨大潜力。这一研究成果为复杂因果结构评估和贝叶斯实验设计提供了重要的理论支撑与算法工具，进一步打通了从大数据到精准决策的关键通道。

作者：吴慧中
编辑：曹薇
审核：王远芳
审定：倪国华