Learning Discrete Directed Acyclic Graphs via Backpropagation
This work addresses the challenge of combinatorial optimization in DAG learning for researchers in machine learning, presenting an incremental improvement by applying existing discrete techniques to this domain.
The paper tackles the problem of learning Directed Acyclic Graphs (DAGs) from data by proposing DAG-DB, a framework that uses discrete backpropagation instead of continuous relaxations, achieving competitive performance with methods like I-MLE and Straight-Through Estimation.
Recently continuous relaxations have been proposed in order to learn Directed Acyclic Graphs (DAGs) from data by backpropagation, instead of using combinatorial optimization. However, a number of techniques for fully discrete backpropagation could instead be applied. In this paper, we explore that direction and propose DAG-DB, a framework for learning DAGs by Discrete Backpropagation. Based on the architecture of Implicit Maximum Likelihood Estimation [I-MLE, arXiv:2106.01798], DAG-DB adopts a probabilistic approach to the problem, sampling binary adjacency matrices from an implicit probability distribution. DAG-DB learns a parameter for the distribution from the loss incurred by each sample, performing competitively using either of two fully discrete backpropagation techniques, namely I-MLE and Straight-Through Estimation.