Exact Graph Learning via Integer Programming

• URL: http://arxiv.org/abs/2601.20589v1
• Date: Wed, 28 Jan 2026 13:24:04 GMT
• Title: Exact Graph Learning via Integer Programming
• Authors: Lucas Kook, Søren Wengel Mogensen,
• Abstract summary: We introduce a nonparametric graph learning framework based on nonparametric conditional independence testing and integer programming.<n>We show that our approach is faster than other existing exact graph learning procedures for a large fraction of instances and graphs of various sizes.
• Score: 3.0556942817031456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the dependence structure among variables in complex systems is a central problem across medical, natural, and social sciences. These structures can be naturally represented by graphs, and the task of inferring such graphs from data is known as graph learning or as causal discovery if the graphs are given a causal interpretation. Existing approaches typically rely on restrictive assumptions about the data-generating process, employ greedy oracle algorithms, or solve approximate formulations of the graph learning problem. As a result, they are either sensitive to violations of central assumptions or fail to guarantee globally optimal solutions. We address these limitations by introducing a nonparametric graph learning framework based on nonparametric conditional independence testing and integer programming. We reformulate the graph learning problem as an integer-programming problem and prove that solving the integer-programming problem provides a globally optimal solution to the original graph learning problem. Our method leverages efficient encodings of graphical separation criteria, enabling the exact recovery of larger graphs than was previously feasible. We provide an implementation in the openly available R package 'glip' which supports learning (acyclic) directed (mixed) graphs and chain graphs. From the resulting output one can compute representations of the corresponding Markov equivalence classes or weak equivalence classes. Empirically, we demonstrate that our approach is faster than other existing exact graph learning procedures for a large fraction of instances and graphs of various sizes. GLIP also achieves state-of-the-art performance on simulated data and benchmark datasets across all aforementioned classes of graphs.

Related papers

• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  We propose a Multi-Level Embedding framework of nodes on a heterogeneous graph (HeteroMILE) HeteroMILE repeatedly coarsens the large sized graph into a smaller size while preserving the backbone structure of the graph before embedding it. It then refines the coarsened embedding to the original graph using a heterogeneous graph convolution neural network.
  arXiv  Detail & Related papers  (2024-03-31T22:22:10Z)
• The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
  Graph Lottery Ticket (GLT) Hypothesis: There is an extremely sparse backbone for every graph. We study 8 key metrics of interest that directly influence the performance of graph learning algorithms. We propose a straightforward and efficient algorithm for finding these GLTs in arbitrary graphs.
  arXiv  Detail & Related papers  (2023-12-08T00:24:44Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures. We propose NLGraph, a benchmark of graph-based problem solving simulating in natural language.
  arXiv  Detail & Related papers  (2023-05-17T08:29:21Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Explanation Graph Generation via Pre-trained Language Models: An Empirical Study with Contrastive Learning [84.35102534158621]
  We study pre-trained language models that generate explanation graphs in an end-to-end manner. We propose simple yet effective ways of graph perturbations via node and edge edit operations. Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs.
  arXiv  Detail & Related papers  (2022-04-11T00:58:27Z)
• Graph Pooling via Coarsened Graph Infomax [9.045707667111873]
  We propose Coarsened GraphPool Infomaxing (CGI) to maximize the mutual information between the input and the coarsened graph of each pooling layer. To achieve mutual information neural, we apply contrastive learning and propose a self-attention-based algorithm for learning positive and negative samples.
  arXiv  Detail & Related papers  (2021-05-04T03:50:21Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Graph topology inference benchmarks for machine learning [16.857405938139525]
  We introduce several benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.
  arXiv  Detail & Related papers  (2020-07-16T09:40:32Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Learning Product Graphs Underlying Smooth Graph Signals [15.023662220197242]
  This paper devises a method to learn structured graphs from data that are given in the form of product graphs. To this end, first the graph learning problem is posed as a linear program, which (on average) outperforms the state-of-the-art graph learning algorithms.
  arXiv  Detail & Related papers  (2020-02-26T03:25:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.