Learning chordal extensions
On the map: Offline RL and imitation learning from data → Imitation learning methods
Abstract (arXiv)
A highly influential ingredient of many techniques designed to exploit sparsity in numerical optimization is the so-called chordal extension of a graph representation of the optimization problem. The definitive relation between chordal extension and the performance of the optimization algorithm that uses the extension is not a mathematically understood task. For this reason, we follow the current research trend of looking at Combinatorial Optimization tasks by using a Machine Learning lens, and we devise a framework for learning elimination rules yielding high-quality chordal extensions. As a first building block of the learning framework, we propose an on-policy imitation learning scheme that mimics the elimination ordering provided by the (classical) minimum degree rule. The results show that our on-policy imitation learning approach is effective in learning the minimum degree policy and, consequently, produces graphs with desirable fill-in characteristics.
Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Placed in Imitation learning methods, one of 13 directions in Offline RL and imitation learning from data. First posted on arXiv 16 Oct 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 2; 2022: 2; 2023: 0; 2024: 0; 2025: 1.
5 papers.
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2022LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisationcited by 8
- 2022A machine learning framework for neighbor generation in metaheuristic searchcited by 4
- 2021Revisiting local branching with a machine learning lenscited by 1
- 2025Deep RL Dual Sourcing Inventory Management with Supply and Capacity Risk Awarenesscited by 1
- 2025Deep RL Dual Sourcing Inventory Management with Supply and Capacity Risk Awareness19 Jul 2025
- 2022A machine learning framework for neighbor generation in metaheuristic search22 Dec 2022
- 2022LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation20 May 2022
- 2021Revisiting local branching with a machine learning lens3 Dec 2021
- 2021Combinatorial optimization and reasoning with graph neural networks18 Feb 2021
Similar, not cited
Close in wording, no citation either way
- 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
- 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networks
- 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization
- 2022Yordle: An Efficient Imitation Learning for Branch and Bound
- 2020Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
- 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
- 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
- 2022An Improved Reinforcement Learning Algorithm for Learning to Branch