betaFeedback

WorksMathematics

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.

Introduction

Probabilistic graphical models (PGMs) provide a succinct representation of the joint distribution of multiple random variables in a graph where nodes correspond to variables and edges encode conditional dependencies ((Lauritzen 1996)). Such a graph becomes an object of direct scientific interest in many applications: it can reveal regulatory relationships among genes, functional connectivity among brain regions, dependencies among financial assets, or interactions among species in an ecosystem. As such, learning the structure of a PGM from data has become one of the central problems in modern statistics and machine learning ((Drton & Maathuis 2017)).

A substantial body of work has developed methods for estimating the structure of undirected graphical models in high-dimensional settings, where the number of variables can exceed the available sample size. Most notable is the setting of Gaussian graphical models (GGMs), where the graph is encoded in the sparsity pattern of the inverse covariance, or precision, matrix (Dempster 1972). In this case, the graph structure can be efficiently estimated in high dimensions by using penalized regression via the neighborhood selection approach (Meinshausen & Bühlmann 2006a), or by directly solving the penalized likelihood problem (Yuan & Lin 2007), using, e.g., the graphical lasso algorithm (Friedman et al. 2008). Penalized estimation approaches have also been developed for estimation of the graph structure from non-Gaussian observations, including Gaussian copula graphical models (Liu et al. 2012, Xue & Zou 2012), as well as binary and Poisson random variables (Ravikumar et al. 2010, Yang et al. 2013). More generally, penalized estimation of graphical models has also been extended to models with exponential-family node-conditional distributions (Yang et al. 2015), mixed graphical models allowing different node-conditional distribution families (Chen et al. 2015), and models with nonlinear additive conditional means (Voorman et al. 2014).

The above penalized estimation methods have been successfully adopted in applications and have become standard tools for exploratory network analysis. However, their standard formulations assume that all variables are jointly observed on a common set of samples. There are many important applications in which data relevant to a single underlying graphical model cannot be pooled into one data set, either because they are generated and stored separately or because they cannot be shared across sites. In multi-center clinical and genomic studies, patient-level data are often siloed within individual hospitals or institutions due to privacy regulations and data use agreements, preventing the construction of a single combined data set even when all sites measure the same clinical and molecular variables (Tertulino et al. 2024). In neuroscience, large-scale recordings of neural activity are frequently collected across multiple non-simultaneous sessions, multiple animals, or multiple labs, so that any single recording session captures only a subset of the neurons or brain regions of interest (Siegle & Steinmetz 2026). In sensor networks, physical or bandwidth constraints mean that different subsets of sensors report to different collection points, and the full sensor array is never observed simultaneously. In each of these settings, data are fragmented: they are distributed across sources that cannot be merged, whether because of legal, logistical, or physical barriers.

This fragmentation motivates a fundamentally different estimation problem: rather than learning a graphical model from a single data set, we need algorithms that can integrate statistical evidence about a shared underlying graph from multiple, separately-held data sources. This problem is particularly challenging in the setting of graphical models: in addition to the usual challenges of estimation across multiple data sources, namely potential differences among distributions and the lack of access to the raw observations, observing different sets of variables across different sites means that conditional independence relationships inferred in each site, and hence the corresponding graph structures, may be drastically different. Several strands of literature address different aspects of this integration problem.

The first class of methods has focused on integrating multiple data sets that share the same set of observed variables but arise from distinct, possibly heterogeneous, populations. This includes the literature on jointly estimating multiple related GGMs, where each source has its own precision matrix, but these precision matrices are encouraged to have similar sparsity patterns or parameter values (Guo et al. 2011, Danaher et al. 2014, Saegusa & Shojaie 2016, Phan & Le Thi 2017, Liu et al. 2026). A related Bayesian approach shares information about edge inclusion across groups without requiring similar nonzero precision values (Peterson et al. 2015). Related approaches have also leveraged multi-task learning (Honorio & Samaras 2010) and population-prior approaches for improving individual brain connectivity estimates using group-level information (Varoquaux et al. 2010). However, all of these approaches require that the same set of variables be observed in every source, while allowing source-specific distributions. They are therefore not directly applicable when different sources observe different, possibly only partially overlapping, subsets of variables. Jewel and Jewel 2.0 [2, 3] permit different observed variable sets, with the latter also allowing source-specific edges. For a given pair of variables, they encourage the same edge pattern across the different sources. However, edges across sources are not directly comparable, as their presence or absence reflects conditional independence relationships involving different conditioning sets when the observed variable sets differ.

The second class of methods comes from the distributed and federated learning literature, which was developed primarily to address computational and privacy constraints when a large data set is split across multiple machines, or when data reside on different devices or institutions that cannot share raw data (McMahan et al. 2017). Several algorithms have recently leveraged these ideas for estimation and inference (Battey et al. 2018), including estimation of precision matrices (Arroyo & Hou 2016, Wang & Cui 2021, Nezakati & Pircalabelu 2023). Complementary strategies based on combining summary statistics across sites have also been proposed (Liu et al. 2015, Tang et al. 2020). These distributed learning methods are effective at reducing computation and respecting data-access constraints. However, the distributed precision-matrix formulations also assume a common set of observed variables and do not directly address graph reconstruction from different observed subsets. In this setting, the central statistical challenge is no longer simply combining samples across sources with a shared variable set, but inferring a single underlying graph over the union of all variables when no single source observes them all.

The third class of methods allows for partial observations but encourages similarity in distributions across the sources. One such line of work is the “graph quilting” framework in Vinci et al. (2023). In the Gaussian setting, an ℓ1\ell_{1}-regularized partially-observed likelihood estimator, combined with thresholding and Schur-complement calculations, can recover edges connecting jointly observed variable pairs and a superset of edges connecting never-jointly-observed pairs. These guarantees hold under certain conditions, with minimality of the superset established under additional assumptions. Related work uses low-rank covariance completion before graph estimation (Chang et al. 2022) and extends the framework to Gaussian copula models using rank-based correlation estimates (Chang et al. 2023). Another line of work that handles partial observations is (Tozzo et al. 2020), which uses the EM algorithm and couples source-specific precision matrices through ℓ1\ell_{1} penalties on their differences. The methods described in this class all accommodate multiple data sources with different observed variable subsets and sample sizes. However, these formulations rely on a common covariance or latent correlation matrix across sources. They therefore do not directly address sources whose numerical dependence parameters differ while a common graph is preserved. Moreover, although raw observations need not be shared, the procedures require numerical covariance or rank-correlation summaries and cannot operate on estimated graphs alone. Their developed formulations also focus on Gaussian or Gaussian copula graphical models, leaving integration for broader distributional families unaddressed.

A final class of methods reconstructs global undirected graphs directly from supplied marginal graph structures (Kim 2009, Kim et al. 2026). These methods treat the supplied marginal structures as exact, without accounting for estimation errors that may render them mutually incompatible. Moreover, they do not address the integration of raw data.

The above limitations clearly highlight the need for a general framework that jointly addresses heterogeneous variable sets, source-specific distributions, and different forms of shared information.

Our contributions

To address the limitations of existing approaches, this paper develops a general graphical model estimation algorithm by integrating evidence from multiple heterogeneous sources that may differ simultaneously in the variables they observe, the distributions they follow, and the form of information they can share.

At a high level, our procedure connects the sources through the latent projection operator, which maps a candidate global graph to a local graph on each source’s observed variable subset and accounts for connections induced by paths through unobserved variables. We estimate the global graph by jointly assessing how well these source-specific projections fit the available data or graph estimates. The proposed algorithm offers substantial flexibility and, to the best of our knowledge, applies to settings beyond the scope of any single existing procedure by simultaneously addressing the following four challenges. (a) Heterogeneous variable sets: we allow each source to observe a different, possibly only partially overlapping, subset of the full variable set, without requiring any source to observe the full variable set. (b) Distribution shift across sources: we require only that the underlying conditional independence graph is shared across sources, while allowing the full joint distribution to vary; in the Gaussian graphical model setting, for example, this allows each source to have its own distinct precision matrix, as long as all precision matrices share the same support. (c) Flexible forms of information sharing: our framework can integrate either shared raw data, locally estimated (source-specific) graphs, or a mixture of the two, which makes it directly applicable under privacy or data-access constraints where only summary information, rather than individual-level data, can be transmitted or pooled. (d) Generality across model classes: the proposed algorithm applies to a broad class of undirected PGMs, rather than being restricted to specific distributions, such as Gaussian.

To estimate the global graph, we develop a mixed-integer optimization formulation and a scalable coordinate-descent heuristic for the resulting estimation problem. Because fragmented observations need not determine a unique global graph, we also characterize projection-equivalence classes and identifiable graph features.

Our theoretical guarantees show that recovery is governed by new combinatorial notions of signal strength that account for how a local structural error can force additional errors across sources through latent-projection compatibility. These combinatorial notions, in particular, reveal how strong local signals in some sources can compensate for weak local signals in others, yielding recovery guarantees that differ fundamentally from standard high-dimensional beta-min requirements.

Extensive simulations show that integration can substantially improve recovery of source-specific graphs relative to separate-source estimation. Integrating raw data generally yields greater gains than integrating estimated graphs. Comparisons with graph quilting further demonstrate the importance of allowing source-specific distributions: our method remains stable as the source distributions diverge, whereas methods relying on a common distribution deteriorate.

We illustrate the proposed framework by integrating four partially-overlapping fatty-acid panels from the National Health and Nutrition Examination Survey (NHANES), covering 31 distinct fatty acids. The analysis combines individual-level concentration data from three sources with a graph estimated separately from compositional measurements in the fourth. The resulting network exhibits organization by fatty-acid family and chain length, while equivalence-class and subsampling analyses characterize structural ambiguity and assess the stability of the estimated relationships.

Notations

For an undirected graph G\mathcal{G} over vertex set VV, we denote E(G)={(i,j)∈V×V:i adjacent to j in G}E(\mathcal{G}) = \{(i,j) \in V \times V : i\ \text{adjacent to}\ j\ \text{in}\ \mathcal{G}\} as its edge set. For a node ii in an undirected graph G~\widetilde{\mathcal{G}}, we use N(i,G~)N(i,\widetilde{\mathcal{G}}) to denote nodes that are adjacent to ii in G~\widetilde{\mathcal{G}}, i.e., N(i,G~):={j:(i,j)∈E(G~)}N(i,\widetilde{\mathcal{G}}) := \{j : (i,j) \in E(\widetilde{\mathcal{G}})\}. For a positive integer nn, [n][n] denote the set {1,2,…,n}\{1,2,\ldots,n\}.

Setup and Identifiability

Setup

We consider KK data sources, where source kk is associated with a distribution P(k)P^{(k)} on the random vector XVX_V with V={1,…,p}V = \{1,\ldots,p\}. In each source, we observe data from only a subset of the variables Sk⊆VS_k \subseteq V with V=⋃k∈[K]SkV = \bigcup_{k\in[K]} S_k. The subsets can be overlapping.

Let ⊥\perp denote a specified notion of conditional independence. Depending on the setting, this relation may represent probabilistic conditional independence, zero partial correlation, conditional tail independence in the context of multivariate extremes, or another independence notion of interest.

We assume that the full source distributions share a common dependence structure: for every pair of distinct vertices i,j∈Vi,j \in V, Xi⊥Xj∣XV∖{i,j}X_i \perp X_j \mid X_{V\setminus\{i,j\}} under P(k)P^{(k)} either holds for every k∈[K]k \in[K] or fails for every k∈[K]k \in[K]. Thus, although the distributions P(k)P^{(k)} may differ across sources, they induce the same pairwise conditional independence structure over the full collection of variables. The following definition formalizes the graph structure shared across the data sources.

Definition 1 (Population global graph). We define the population global graph as G∗=(V,E∗)G^* = (V,E^*), where:

(i,j)∉E∗⟺Xi⊥Xj∣XV∖{i,j} under P(k) ∀k∈[K].(i,j) \notin E^* \quad\Longleftrightarrow\quad X_i \perp X_j \mid X_{V\setminus\{i,j\}}\ \text{under}\ P^{(k)}\ \forall k \in[K].

Here, G∗G^* represents the global population graph encoding the pairwise conditional independence structure, shared by all source distributions.

Our inferential goals are twofold. The first is to identify G∗G^*, or an equivalence class when it is not identifiable, using only information from each local source. The second is to “pool” the information across the sources to improve the recovery of a given source’s local conditional independence graph. For both of these goals, we must relate the conditional independence structure observed in each source to the common global graph G∗G^*. Because marginalizing variables can induce additional dependencies among the observed variables, the relevant local graph is not generally the subgraph of G∗G^* induced by SkS_k, but rather its latent projection onto SkS_k. We first introduce the notions of separation and latent projection needed to formalize this relationship.

Definition 2 (Separation). Let G=(V,E)\mathcal{G} = (V,E) be an undirected graph. For distinct vertices i,j∈Vi,j \in V, a set T⊆V∖{i,j}T \subseteq V\setminus\{i,j\} is said to separate ii and jj in G\mathcal{G} if every path between ii and $j contains at least one vertex in TT.

In source kk, only the variables indexed by Sk⊆VS_k \subseteq V are observed. The observed data therefore follow the marginal distribution PSk(k)P^{(k)}_{S_k}, obtained from P(k)P^{(k)} by marginalizing over XV∖SkX_{V\setminus S_k}. Marginalizing unobserved variables can induce additional edges among the observed variables, formalized according to a latent projection, which is described next.

Definition 3 (Latent projection). Let G=(V,E)\mathcal{G} = (V, E) be an undirected graph and let S⊆VS \subseteq V. The latent projection of G\mathcal{G} onto SS is the graph

πS(G)=(S,ES),\pi_S(\mathcal{G}) = (S, E_S),

where, for every pair of distinct vertices i,j∈Si,j \in S,

(i,j)∈ES⟺S∖{i,j} does not separate i and j in G.(i,j) \in E_S \quad\Longleftrightarrow\quad S \setminus\{i,j\}\text{ does not separate }i\text{ and }j\text{ in }\mathcal{G}.

Equivalently, ii and jj are adjacent in πS(G)\pi_S(\mathcal{G}) if and only if there exists a path between them in G\mathcal{G} whose internal vertices all belong to V∖SV \setminus S.

The latent projection differs crucially from the subgraph induced by SS. In particular, two variables may be adjacent in πS(G)\pi_S(\mathcal{G}) even when they are not adjacent in G\mathcal{G}, because a path through variables outside SS induces an edge after those variables are marginalized out. Thus, unlike an induced subgraph, the latent projection depends on the structure of G\mathcal{G} outside SS. The distinction between the latent projection and the induced subgraph is especially important, as the conditional-independence relations in SkS_k, induced by PSk(k)P_{S_k}^{(k)}, are not, in general, represented by the induced subgraph.

Definition 4 (Source-wise conditional dependence graph). For each source k∈[K]k \in[K], define its conditional dependence graph GSk⋆(k)=(Sk,Ek)\mathcal{G}_{S_k}^{\star(k)} = (S_k, E_k) as

(i,j)∉Ek⟺Xi⊥Xj∣XSk∖{i,j} under PSk(k) (or equivalently under P(k)).(i,j) \notin E_k \quad\Longleftrightarrow\quad X_i \perp X_j \mid X_{S_k\setminus\{i,j\}}\text{ under }P_{S_k}^{(k)}\text{ (or equivalently under }P^{(k)}\text{)}.

To ensure that these local graphs are compatible with G⋆\mathcal{G}^{\star}, we impose the following condition.

Assumption 1 (Source-wise pairwise faithfulness). For every k∈[K]k \in[K] and every pair of distinct vertices i,j∈Ski,j \in S_k,

Xi⊥Xj∣XSk∖{i,j} under PSk(k) (or equivalently under P(k))⟺Sk∖{i,j} separates i and j in G⋆.X_i \perp X_j \mid X_{S_k\setminus\{i,j\}}\text{ under }P_{S_k}^{(k)}\text{ (or equivalently under }P^{(k)}\text{)} \quad\Longleftrightarrow\quad S_k\setminus\{i,j\}\text{ separates }i\text{ and }j\text{ in }\mathcal{G}^{\star}.

By the definition of latent projection, Assumption 1 implies

GSk⋆(k)=πSk(G⋆),k∈[K].\mathcal{G}_{S_k}^{\star(k)} = \pi_{S_k}(\mathcal{G}^{\star}), \qquad k \in[K].

Thus, the source-specific conditional dependence graphs are compatible in the sense that they are all latent projections of the same global graph G⋆\mathcal{G}^{\star}. Violation of Assumption 1 results in a lack of compatibility. The following simple example shows one settings where the compatibility may fail.

Example 1 (When Assumption 1 is violated). As a simple illustration, suppose K=2K = 2 and each source follows the same Gaussian distribution:

P(k)∼N(0,Σ),Σ=(10.4000.410.40.400.41000.401).P^{(k)} \sim\mathcal{N}(0,\Sigma), \qquad \Sigma= \begin{pmatrix} 1 & 0.4 & 0 & 0 \\ 0.4 & 1 & 0.4 & 0.4 \\ 0 & 0.4 & 1 & 0 \\ 0 & 0.4 & 0 & 1 \end{pmatrix}.

Since the precision matrix Σ−1\Sigma^{-1} is a fully dense matrix, G⋆\mathcal{G}^{\star} is a fully connected graph. Suppose S1={1,2,3}S_1 = \{1,2,3\} and S2={1,3,4}S_2 = \{1,3,4\}. Then, from the precision matrices corresponding to submatrices of Σ\Sigma, we have that G(1)\mathcal{G}^{(1)} is a fully connected graph, and G(2)\mathcal{G}^{(2)} is the fully disconnected graph. We see that πS2(G⋆)≠G(2)\pi_{S_2}(\mathcal{G}^{\star}) \ne\mathcal{G}^{(2)}. In fact, there does not exist a global graph G\mathcal{G} over VV such that πSk(G)=GSk⋆(k)\pi_{S_k}(\mathcal{G}) = \mathcal{G}_{S_k}^{\star(k)}, k=1,2k = 1,2.

Assumption 1 is weaker than the standard faithfulness assumption, which is described next.

Assumption 1′ (Source-wise faithfulness). For every k∈[K]k \in[K] and every collection of pairwise disjoint sets A,B,C⊆VA,B,C \subseteq V,

XA⊥XB∣XC under P(k)⟺C separates A and B in G⋆.X_A \perp X_B \mid X_C\text{ under }P^{(k)} \quad\Longleftrightarrow\quad C\text{ separates }A\text{ and }B\text{ in }\mathcal{G}^{\star}.

Assumption 1′1' is a typical condition in graphical modeling (Lauritzen 1996). This stronger condition implies Assumption 1 by taking A=iA=i, B=jB=j, C=Sk∖{i,j}C=S_k \setminus\{i,j\}. The weaker assumption is sufficient when the local information consists only of pairwise conditional independences given all remaining variables observed in each source.

In several widely studied model classes, faithfulness is generic. For example, for a fixed undirected graph, almost every regular Gaussian distribution that is Markov with respect to the graph is also faithful to it, with the unfaithful parameter values forming a Lebesgue measure zero set (Sadeghi 2017, Amini et al. [1]). Intuitively, violations of faithfulness can arise from special configurations of model parameters or structures that induce conditional independences not implied by graphical separation. Our Assumption 1 is weaker than the standard faithfulness in Assumption 1′1', as it requires only a subset of the implications imposed by standard faithfulness. Nevertheless, the measure-zero result concerns exact violations and does not rule out distributions that are nearly unfaithful, for which some nonzero conditional dependences may be arbitrarily small and graph recovery may be difficult in finite samples.

In several distributional families, both the structure of the graph G∗G^* and Assumption 1 admit algebraic characterizations. We present these characterizations next.

References

  1. [1]Amini, A. A., Aragam, B. & Zhou, Q. (2022), ‘On perfectness in gaussian graphical models’, Electronic Journal of Statistics 16(1), 1361–1389.
  2. [2]Angelini, C., De Canditiis, D. & Plaksienko, A. (2021), ‘Jewel: a novel method for joint estimation of gaussian graphical models’, Mathematics 9(17), 2105.DOI
  3. [3]Angelini, C., De Canditiis, D. & Plaksienko, A. (2022), ‘Jewel 2.0: an improved joint estimation method for multiple gaussian graphical models’, Mathematics 10(21), 3983.DOI

Paper details

vlnc:W_eb8kqmm6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents