Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models

Pierre Gillot, Pekka Parviainen
Proceedings of The 11th International Conference on Probabilistic Graphical Models, PMLR 186:157-168, 2022.

Abstract

Score-based structure learning in Bayesian networks, where local structures in the graph are given a score and one seeks to recover a high-scoring DAG from data, is an NP-hard problem. While the general learning problem is combinatorial, the more restricted framework of linear structural equation models (SEMs) enables learning Bayesian networks using continuous optimization methods. Large scale structure learning has become an important problem in linear SEMs and many approximate methods have been developed to address it. Among them, feedback arc set-based methods learn the DAG by alternating between unconstrained gradient descent-based step to optimize an objective function and solving a maximum acyclic subgraph problem to enforce acyclicity. In the present work, we build upon previous contributions on such heuristics by first establishing mathematical convergence analysis, previously lacking; second, we show empirically how one can significantly speed-up convergence in practice using simple warmstarting strategies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v186-gillot22a, title = {Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models}, author = {Gillot, Pierre and Parviainen, Pekka}, booktitle = {Proceedings of The 11th International Conference on Probabilistic Graphical Models}, pages = {157--168}, year = {2022}, editor = {Salmerón, Antonio and Rumı́, Rafael}, volume = {186}, series = {Proceedings of Machine Learning Research}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v186/gillot22a/gillot22a.pdf}, url = {https://proceedings.mlr.press/v186/gillot22a.html}, abstract = {Score-based structure learning in Bayesian networks, where local structures in the graph are given a score and one seeks to recover a high-scoring DAG from data, is an NP-hard problem. While the general learning problem is combinatorial, the more restricted framework of linear structural equation models (SEMs) enables learning Bayesian networks using continuous optimization methods. Large scale structure learning has become an important problem in linear SEMs and many approximate methods have been developed to address it. Among them, feedback arc set-based methods learn the DAG by alternating between unconstrained gradient descent-based step to optimize an objective function and solving a maximum acyclic subgraph problem to enforce acyclicity. In the present work, we build upon previous contributions on such heuristics by first establishing mathematical convergence analysis, previously lacking; second, we show empirically how one can significantly speed-up convergence in practice using simple warmstarting strategies.} }
Endnote
%0 Conference Paper %T Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models %A Pierre Gillot %A Pekka Parviainen %B Proceedings of The 11th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2022 %E Antonio Salmerón %E Rafael Rumı́ %F pmlr-v186-gillot22a %I PMLR %P 157--168 %U https://proceedings.mlr.press/v186/gillot22a.html %V 186 %X Score-based structure learning in Bayesian networks, where local structures in the graph are given a score and one seeks to recover a high-scoring DAG from data, is an NP-hard problem. While the general learning problem is combinatorial, the more restricted framework of linear structural equation models (SEMs) enables learning Bayesian networks using continuous optimization methods. Large scale structure learning has become an important problem in linear SEMs and many approximate methods have been developed to address it. Among them, feedback arc set-based methods learn the DAG by alternating between unconstrained gradient descent-based step to optimize an objective function and solving a maximum acyclic subgraph problem to enforce acyclicity. In the present work, we build upon previous contributions on such heuristics by first establishing mathematical convergence analysis, previously lacking; second, we show empirically how one can significantly speed-up convergence in practice using simple warmstarting strategies.
APA
Gillot, P. & Parviainen, P.. (2022). Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models. Proceedings of The 11th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 186:157-168 Available from https://proceedings.mlr.press/v186/gillot22a.html.

Related Material