Constraint-Free Structure Learning with Smooth Acyclic Orientations
Riccardo Massidda Francesco Landolfi Martina Cinquini Davide Bacciu
The structure learning problem consists of fitting data generated by a
Directed Acyclic Graph (DAG) to correctly reconstruct its arcs. In this
context, differentiable approaches constrain or regularize the optimization
problem using a continuous relaxation of the acyclicity property. The
computational cost of evaluating graph acyclicity is cubic on the number of
nodes and significantly affects scalability. In this paper we introduce COSMO,
a constraint-free continuous optimization scheme for acyclic structure
learning. At the core of our method, we define a differentiable approximation
of an orientation matrix parameterized by a single priority vector. Differently
from previous work, our parameterization fits a smooth orientation matrix and
the resulting acyclic adjacency matrix without evaluating acyclicity at any
step. Despite the absence of explicit constraints, we prove that COSMO always
converges to an acyclic solution. In addition to being asymptotically faster,
our empirical analysis highlights how COSMO performance on graph reconstruction
compares favorably with competing structure learning methods.