用整数规划实现图结构的精确学习，突破传统方法局限。
Exact Graph Learning via Integer Programming
- 基于条件独立性测试与整数规划重构图结构
- 可精确恢复更大规模图，且求解更快
- 适合需严格保证最优解的研究场景
复杂系统中变量间依赖关系的识别是医学、自然科学和社会科学中的核心问题。这些关系可自然地以图形式表示，从数据中推断此类图的任务称为图学习或因果发现。现有方法通常依赖数据生成过程的严格假设，采用贪心启发式算法，或求解图学习问题的近似形式，因此对关键假设的违反敏感，且无法保证全局最优解。本文提出一种基于条件独立性检验和整数规划的非参数图学习框架，将图学习问题重构为混合整数规划，并证明求解该规划可获得原问题的全局最优解。方法利用高效的图分离判据编码，实现了此前难以处理的更大规模图的精确恢复。我们发布了开源R包'glip'，支持学习(无环)有向(混合)图和链图。实验表明，本方法在模拟数据和基准数据上均显著优于现有精确图学习方法，在所有上述图类型中表现达到当前最佳水平。
原文摘要 · Abstract (English)
Learning the dependence structure among variables in complex systems is a central problem across medical, natural, and social sciences. These structures can be naturally represented by graphs, and the task of inferring such graphs from data is known as graph learning or causal discovery. Existing approaches typically rely on restrictive assumptions about the data-generating process, employ greedy oracle algorithms, or solve approximate formulations of the graph learning problem. Therefore, they are either sensitive to violations of central assumptions or fail to guarantee globally optimal solutions. We address these limitations by introducing a nonparametric graph learning framework based on conditional independence testing and integer programming. We reformulate the graph learning problem as a mixed-integer program and prove that solving this integer-programming problem provides a globally optimal solution to the original graph learning problem. Our method leverages efficient encodings of graphical separation criteria, enabling the exact recovery of larger graphs than was previously feasible. We provide an open-source R package 'glip' which supports learning (acyclic) directed (mixed) graphs and chain graphs. We demonstrate that our approach is often faster than existing exact graph learning procedures and achieves state-of-the-art performance on simulated and benchmark data across all aforementioned classes of graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。