Timezone: »

DAGs with No Curl: An Efficient DAG Structure Learning Approach
Yue Yu · Tian Gao · Naiyu Yin · Qiang Ji

Thu Jul 22 09:00 AM -- 11:00 AM (PDT) @ Virtual #None
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 non-acyclic solution to the optimization problem, and $2)$ then we employ the Hodge decomposition of graphs and learn an acyclic graph by projecting the non-acyclic 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.

Author Information

Yue Yu (Lehigh University)
Tian Gao (IBM Research)

Tian is currently a research staff member in IBM T. J. Watson Research Center. His research interests include machine learning, graphical models, causal discovery, reasoning, and applications.

Naiyu Yin (Rensselaer Polytechnic Institute)
Qiang Ji (Renselaer Polytechnic Institute)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors