DAGs with No Curl: An Efficient DAG Structure Learning Approach
DAGs with No Curl: An Efficient DAG Structure Learning Approach
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Yue Yu;Tian Gao;Naiyu Yin;Q. Ji
中科院分区：
文献类型：
--
作者：
Yue Yu;Tian Gao;Naiyu Yin;Q. Ji
最近，有向无环图（DAG）结构学习被表述为具有连续无环约束的约束连续优化问题，并通过子问题优化迭代求解。为了进一步提高效率，我们提出了一种新的学习框架，直接在DAG空间中建模和学习加权邻接矩阵。具体来说，我们首先表明，一组的加权邻接矩阵的DAG是等价的图势函数的加权梯度的集合，和一个可以执行结构学习搜索在这个等价的DAG。为了实例化这个想法，我们提出了一个新的算法，DAG-NoCurl，它有效地解决了优化问题的两个步骤：1）首先，我们找到一个初始的循环解决方案的优化问题，和2）然后我们采用Hodge分解的图形和学习一个非循环图通过投影的循环图的梯度的潜在功能。基准数据集上的实验研究表明，我们的方法提供了可比的准确性，但更好的效率比基线DAG结构学习方法的线性和广义结构方程模型，往往超过一个数量级。
Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints and was solved iteratively through subproblem optimization. To further improve efficiency, we propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. Specifically, we first show that the set of weighted adjacency matrices of DAGs are equivalent to the set of weighted gradients of graph potential functions, and one may perform structure learning by searching in this equivalent set of DAGs. To instantiate this idea, we propose a new algorithm, DAG-NoCurl, which solves the optimization problem efficiently with a two-step procedure: 1) first we find an initial cyclic solution to the optimization problem, and 2) then we employ the Hodge decomposition of graphs and learn an acyclic graph by projecting the cyclic graph to the gradient of a potential function. Experimental studies on benchmark datasets demonstrate that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models, often by more than one order of magnitude.