Integrating multi-source local information for global undirected graph reconstruction via integer programming
Abstract
Graphical models are widely used to represent conditional independence structures, but learning them is challenging when data are fragmented across sources that measure different subsets of variables and may not be directly shareable. We develop a general framework for reconstructing a shared global graph from heterogeneous, partially observed sources. Our framework permits both the observed variable sets and source-specific distributions to differ. Under a source-wise faithfulness condition, local conditional independence graphs correspond to latent projections of the shared global graph, which is identifiable up to the equivalence class induced by the observed variable sets. The framework integrates raw data, estimated source graphs, or a combination of both, accommodating settings with restricted access to individual-level data, such as privacy constraints. We develop mixed-integer optimization formulations and scalable approximate algorithms for several classes of graphical models. Unlike standard high-dimensional analyses, our guarantees are governed by new combinatorial notions of signal strength that capture how information propagates across partially observed sources. Extensive simulations further show that integration can substantially improve estimation of source-specific projected graphs relative to separate source methods. Real-data application illustrates the framework's use with partially-observed sources of fatty acid measurements.
Related
- Undirected Network Coding and Faster External-Memory Integer Sorting
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- Accelerated Benders decomposition for bi-objective mixed integer programming
BibTeX
@misc{keret2026integrating,
title = {{Integrating multi-source local information for global undirected graph reconstruction via integer programming}},
author = {Nir Keret and Armeen Taeb and Ali Shojaie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38729},
eprint = {2610.38729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38729},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Integrating multi-source local information for global undirected graph reconstruction via integer programming
AU - Nir Keret
AU - Armeen Taeb
AU - Ali Shojaie
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38729
UR - https://arxiv.org/abs/2610.38729
AB - Graphical models are widely used to represent conditional independence structures, but learning them is challenging when data are fragmented across sources that measure different subsets of variables and may not be directly shareable. We develop a general framework for reconstructing a shared global graph from heterogeneous, partially observed sources. Our framework permits both the observed variable sets and source-specific distributions to differ. Under a source-wise faithfulness condition, local conditional independence graphs correspond to latent projections of the shared global graph, which is identifiable up to the equivalence class induced by the observed variable sets. The framework integrates raw data, estimated source graphs, or a combination of both, accommodating settings with restricted access to individual-level data, such as privacy constraints. We develop mixed-integer optimization formulations and scalable approximate algorithms for several classes of graphical models. Unlike standard high-dimensional analyses, our guarantees are governed by new combinatorial notions of signal strength that capture how information propagates across partially observed sources. Extensive simulations further show that integration can substantially improve estimation of source-specific projected graphs relative to separate source methods. Real-data application illustrates the framework's use with partially-observed sources of fatty acid measurements.
ER -