Meek Separators and Their Applications in Targeted Causal Discovery
Meek 分隔集及其在目标导向因果发现中的应用AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要直接讨论干预数据下的目标导向因果结构学习；因果图的连通分量不构成经济网络或干扰效应的研究依据。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
Meek 分隔集及其在目标导向因果发现中的应用
- 研究问题
- 当只需恢复因果图中的部分信息时，如何减少子集搜索和因果匹配所需的干预次数，而无需恢复整张因果图？
- 方法与思路
- 作者提出 Meek 分隔集，通过干预将未定向边拆分为较小连通分量，并据此设计分治式随机算法。
- 材料陈述的贡献
- 摘要称，两类随机算法分别实现对数近似，并为子集搜索和因果匹配提供作者所称的首个平均情形可证明保证。
- 阅读关注点
- 应核对子集搜索与因果匹配的形式化目标、允许的干预类型、平均情形的随机性来源，以及近似保证的基准。
- 阅读边界
- 这是 arXiv 预印本，不能据此认定已同行评审或期刊接收；摘要未给出图结构条件、复杂度细节或保证的完整形式。
原文摘要
Learning causal structures from interventional data is a fundamental problem with broad applications across various fields. While many previous works have focused on recovering the entire causal graph, in practice, there are scenarios where learning only part of the causal graph suffices. This is called $targeted$ causal discovery. In our work, we focus on two such well-motivated problems: subset search and causal matching. We aim to minimize the number of interventions in both cases. Towards this, we introduce the $Meek~separator$, which is a subset of vertices that, when intervened, decomposes the remaining unoriented edges into smaller connected components. We then present an efficient algorithm to find Meek separators that are of small sizes. Such a procedure is helpful in designing various divide-and-conquer-based approaches. In particular, we propose two randomized algorithms that achieve logarithmic approximation for subset search and causal matching, respectively. Our results provide the first known average-case provable guarantees for both problems. We believe that this opens up possibilities to design near-optimal methods for many other targeted causal structure learning problems arising from various applications.