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} ℓ 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} ℓ 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} G over vertex set V V V , 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}\} E ( G ) = {( i , j ) ∈ V × V : i adjacent to j in G } as its edge set. For a node i i i in an undirected graph G ~ \widetilde{\mathcal{G}} G , we use N ( i , G ~ ) N(i,\widetilde{\mathcal{G}}) N ( i , G ) to denote nodes that are adjacent to i i i in G ~ \widetilde{\mathcal{G}} G , i.e., N ( i , G ~ ) : = { j : ( i , j ) ∈ E ( G ~ ) } N(i,\widetilde{\mathcal{G}}) := \{j : (i,j) \in E(\widetilde{\mathcal{G}})\} N ( i , G ) := { j : ( i , j ) ∈ E ( G )} . For a positive integer n n n , [ n ] [n] [ n ] denote the set { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } .
Setup and Identifiability
Setup
We consider K K K data sources, where source k k k is associated with a distribution P ( k ) P^{(k)} P ( k ) on the random vector X V X_V X V with V = { 1 , … , p } V = \{1,\ldots,p\} V = { 1 , … , p } . In each source, we observe data from only a subset of the variables S k ⊆ V S_k \subseteq V S k ⊆ V with V = ⋃ k ∈ [ K ] S k V = \bigcup_{k\in[K]} S_k V = ⋃ k ∈ [ 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 ∈ V i,j \in V i , j ∈ V , X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V\setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } under P ( k ) P^{(k)} P ( k ) either holds for every k ∈ [ K ] k \in[K] k ∈ [ K ] or fails for every k ∈ [ K ] k \in[K] k ∈ [ K ] . Thus, although the distributions P ( k ) 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^*) G ∗ = ( V , E ∗ ) , where:
( i , j ) ∉ E ∗ ⟺ X i ⊥ X j ∣ X V ∖ { 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]. ( i , j ) ∈ / E ∗ ⟺ X i ⊥ X j ∣ X V ∖ { i , j } under P ( k ) ∀ k ∈ [ K ] . Here, G ∗ 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^* 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^* G ∗ . Because marginalizing variables can induce additional dependencies among the observed variables, the relevant local graph is not generally the subgraph of G ∗ G^* G ∗ induced by S k S_k S k , but rather its latent projection onto S k S_k S 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) G = ( V , E ) be an undirected graph. For distinct vertices i , j ∈ V i,j \in V i , j ∈ V , a set T ⊆ V ∖ { i , j } T \subseteq V\setminus\{i,j\} T ⊆ V ∖ { i , j } is said to separate i i i and j j j in G \mathcal{G} G if every path between i i i and $j contains at least one vertex in T T T .
In source k k k , only the variables indexed by S k ⊆ V S_k \subseteq V S k ⊆ V are observed. The observed data therefore follow the marginal distribution P S k ( k ) P^{(k)}_{S_k} P S k ( k ) , obtained from P ( k ) P^{(k)} P ( k ) by marginalizing over X V ∖ S k X_{V\setminus S_k} X V ∖ 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) G = ( V , E ) be an undirected graph and let S ⊆ V S \subseteq V S ⊆ V . The latent projection of G \mathcal{G} G onto S S S is the graph
π S ( G ) = ( S , E S ) , \pi_S(\mathcal{G}) = (S, E_S), π S ( G ) = ( S , E S ) , where, for every pair of distinct vertices i , j ∈ S i,j \in S i , j ∈ S ,
( i , j ) ∈ E S ⟺ 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}. ( i , j ) ∈ E S ⟺ S ∖ { i , j } does not separate i and j in G . Equivalently, i i i and j j j are adjacent in π S ( G ) \pi_S(\mathcal{G}) π S ( G ) if and only if there exists a path between them in G \mathcal{G} G whose internal vertices all belong to V ∖ S V \setminus S V ∖ S .
The latent projection differs crucially from the subgraph induced by S S S . In particular, two variables may be adjacent in π S ( G ) \pi_S(\mathcal{G}) π S ( G ) even when they are not adjacent in G \mathcal{G} G , because a path through variables outside S S S 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} G outside S S S . The distinction between the latent projection and the induced subgraph is especially important, as the conditional-independence relations in S k S_k S k , induced by P S k ( k ) P_{S_k}^{(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] k ∈ [ K ] , define its conditional dependence graph G S k ⋆ ( k ) = ( S k , E k ) \mathcal{G}_{S_k}^{\star(k)} = (S_k, E_k) G S k ⋆ ( k ) = ( S k , E k ) as
( i , j ) ∉ E k ⟺ X i ⊥ X j ∣ X S k ∖ { i , j } under P S k ( 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{)}. ( i , j ) ∈ / E k ⟺ X i ⊥ X j ∣ X S k ∖ { i , j } under P S k ( k ) (or equivalently under P ( k ) ) .
To ensure that these local graphs are compatible with G ⋆ \mathcal{G}^{\star} G ⋆ , we impose the following condition.
Assumption 1 (Source-wise pairwise faithfulness). For every k ∈ [ K ] k \in[K] k ∈ [ K ] and every pair of distinct vertices i , j ∈ S k i,j \in S_k i , j ∈ S k ,
X i ⊥ X j ∣ X S k ∖ { i , j } under P S k ( k ) (or equivalently under P ( k ) ) ⟺ S k ∖ { 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}. X i ⊥ X j ∣ X S k ∖ { i , j } under P S k ( k ) (or equivalently under P ( k ) ) ⟺ S k ∖ { i , j } separates i and j in G ⋆ .
By the definition of latent projection, Assumption 1 implies
G S k ⋆ ( k ) = π S k ( G ⋆ ) , k ∈ [ K ] . \mathcal{G}_{S_k}^{\star(k)} = \pi_{S_k}(\mathcal{G}^{\star}), \qquad k \in[K]. G S k ⋆ ( k ) = π S k ( G ⋆ ) , k ∈ [ 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} G ⋆ . 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 = 2 K = 2 K = 2 and each source follows the same Gaussian distribution:
P ( k ) ∼ N ( 0 , Σ ) , Σ = ( 1 0.4 0 0 0.4 1 0.4 0.4 0 0.4 1 0 0 0.4 0 1 ) . 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}. P ( k ) ∼ N ( 0 , Σ ) , Σ = 1 0.4 0 0 0.4 1 0.4 0.4 0 0.4 1 0 0 0.4 0 1 . Since the precision matrix Σ − 1 \Sigma^{-1} Σ − 1 is a fully dense matrix, G ⋆ \mathcal{G}^{\star} G ⋆ is a fully connected graph. Suppose S 1 = { 1 , 2 , 3 } S_1 = \{1,2,3\} S 1 = { 1 , 2 , 3 } and S 2 = { 1 , 3 , 4 } S_2 = \{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)} G ( 1 ) is a fully connected graph, and G ( 2 ) \mathcal{G}^{(2)} G ( 2 ) is the fully disconnected graph. We see that π S 2 ( G ⋆ ) ≠ G ( 2 ) \pi_{S_2}(\mathcal{G}^{\star}) \ne\mathcal{G}^{(2)} π S 2 ( G ⋆ ) = G ( 2 ) . In fact, there does not exist a global graph G \mathcal{G} G over V V V such that π S k ( G ) = G S k ⋆ ( k ) \pi_{S_k}(\mathcal{G}) = \mathcal{G}_{S_k}^{\star(k)} π S k ( G ) = G S k ⋆ ( k ) , k = 1 , 2 k = 1,2 k = 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] k ∈ [ K ] and every collection of pairwise disjoint sets A , B , C ⊆ V A,B,C \subseteq V A , B , C ⊆ V ,
X A ⊥ X B ∣ X C 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}. X A ⊥ X B ∣ X C under P ( k ) ⟺ C separates A and B in G ⋆ .
Assumption 1 ′ 1' 1 ′ is a typical condition in graphical modeling (Lauritzen 1996). This stronger condition implies Assumption 1 by taking A = i A=i A = i , B = j B=j B = j , C = S k ∖ { i , j } C=S_k \setminus\{i,j\} C = S k ∖ { 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' 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^* G ∗ and Assumption 1 admit algebraic characterizations. We present these characterizations next.
Example 2 (Gaussian graphical models). Suppose P ( k ) P^{(k)} P ( k ) is a Gaussian distribution with precision matrix Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) . It is well-known that X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V \setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } if and only if Ω i j ∗ ( k ) = 0 \Omega_{ij}^{*(k)} = 0 Ω ij ∗ ( k ) = 0 , so that edges in the population global graph G ∗ G^* G ∗ are encoded by the sparsity pattern of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) . Here, ⊥ \perp ⊥ represents probabilistic conditional independence. Assumption 1 can then be rephrased algebraically as follows: for every k ∈ [ K ] k \in[K] k ∈ [ K ] and i , j ∈ S k i,j \in S_k i , j ∈ S k , Γ i j ∗ ( k ) = 0 \Gamma_{ij}^{*(k)} = 0 Γ ij ∗ ( k ) = 0 if and only if S k ∖ { i , j } S_k \setminus\{i,j\} S k ∖ { i , j } separates i i i and j j j in G ∗ G^* G ∗ , where Γ ∗ ( k ) \Gamma^{*(k)} Γ ∗ ( k ) is the Schur complement
Γ ∗ ( k ) = Ω S k , S k ∗ ( k ) − Ω S k , T k ∗ ( k ) ( Ω T k , T k ∗ ( k ) ) − 1 Ω T k , S k ∗ ( k ) \Gamma^{*(k)} = \Omega_{S_k,S_k}^{*(k)} - \Omega_{S_k,T_k}^{*(k)} \left(\Omega_{T_k,T_k}^{*(k)}\right)^{-1} \Omega_{T_k,S_k}^{*(k)} Γ ∗ ( k ) = Ω S k , S k ∗ ( k ) − Ω S k , T k ∗ ( k ) ( Ω T k , T k ∗ ( k ) ) − 1 Ω T k , S k ∗ ( k ) with T k : = V ∖ S k T_k := V \setminus S_k T k := V ∖ S k .
Example 3 (Pearson partial correlation graphical models). Suppose P ( k ) P^{(k)} P ( k ) has finite second moments and a positive-definite covariance matrix Σ ∗ ( k ) \Sigma^{*(k)} Σ ∗ ( k ) , and let Ω ∗ ( k ) = ( Σ ∗ ( k ) ) − 1 \Omega^{*(k)} = \left(\Sigma^{*(k)}\right)^{-1} Ω ∗ ( k ) = ( Σ ∗ ( k ) ) − 1 . It follows that X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V \setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } if and only if Ω i j ∗ ( k ) = 0 \Omega_{ij}^{*(k)} = 0 Ω ij ∗ ( k ) = 0 , so that edges in the population graph G ∗ G^* G ∗ are encoded by sparsity pattern of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) . Here, ⊥ \perp ⊥ denotes zero Pearson partial correlation. Assumption 1 can be rephrased in a similar algebraic fashion as in Example 2.
Example 4 (Gaussian copula graphical models). Suppose P ( k ) P^{(k)} P ( k ) follows a Gaussian copula model: there exist strictly increasing functions { f j ( k ) : j ∈ V } \{f_j^{(k)}:j \in V\} { f j ( k ) : j ∈ V } such that Z : = ( f j ( k ) ( X j ) , j ∈ V ) ∼ N ( 0 , R ∗ ( k ) ) Z := (f_j^{(k)}(X_j),j \in V) \sim N(0,R^{*(k)}) Z := ( f j ( k ) ( X j ) , j ∈ V ) ∼ N ( 0 , R ∗ ( k ) ) . Let Ω ∗ ( k ) = ( R ∗ ( k ) ) − 1 \Omega^{*(k)} = \left(R^{*(k)}\right)^{-1} Ω ∗ ( k ) = ( R ∗ ( k ) ) − 1 . Since coordinatewise invertible transformations preserve probabilistic conditional independence, X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V \setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } if and only if Ω i j ∗ ( k ) = 0 \Omega_{ij}^{*(k)} = 0 Ω ij ∗ ( k ) = 0 , so that the edges of the global graph G ∗ G^* G ∗ are encoded by the sparsity pattern of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) . Here, ⊥ \perp ⊥ represents probabilistic conditional independence. Moreover, Assumption 1 admits the same algebraic characterization as in Example 2, with the corresponding marginal precision matrix given by the Schur complement of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) over T k : = V ∖ S k T_k := V \setminus S_k T k := V ∖ S k .
Example 5 (Elliptical graphical models). Suppose P ( k ) P^{(k)} P ( k ) follows an elliptical distribution with normalized scatter matrix R ∗ ( k ) R^{*(k)} R ∗ ( k ) , and let Ω ∗ ( k ) = ( R ∗ ( k ) ) − 1 \Omega^{*(k)} = \left(R^{*(k)}\right)^{-1} Ω ∗ ( k ) = ( R ∗ ( k ) ) − 1 . In this setting, X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V \setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } if and only if Ω i j ∗ ( k ) = 0 \Omega_{ij}^{*(k)} = 0 Ω ij ∗ ( k ) = 0 , so edges in the global graph G ∗ G^* G ∗ are encoded by the sparsity pattern of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) . Here, ⊥ \perp ⊥ represents zero generalized partial correlation, which is equivalent to zero Pearson partial correlation under finite second moments. Assumption 1 can then be expressed algebraically in the same manner as in Example 2.
Example 6 (Extremal graphical models). Suppose P ( k ) P^{(k)} P ( k ) in the domain of attraction of a Hüsler–Reiss distribution with a conditionally negative-definite variogram matrix Γ ∗ ( k ) ∈ R p × p \Gamma^{*(k)} \in\mathbb{R}^{p \times p} Γ ∗ ( k ) ∈ R p × p and a precision matrix Ω ∗ ( k ) : = ( Π ( − Γ ∗ ( k ) / 2 ) Π ) + \Omega^{*(k)} := \left(\Pi(-\Gamma^{*(k)}/2)\Pi\right)^{+} Ω ∗ ( k ) := ( Π ( − Γ ∗ ( k ) /2 ) Π ) + , where A + A^{+} A + is the Moore–Penrose pseudoinverse of a matrix A A A , and Π \Pi Π is the orthogonal projection onto the complement of the all-ones vector (Hentschel et al. 2022, Engelke & Hitz 2018). In this setting, X i ⊥ X j ∣ X V ∖ { i , j } X_i \perp X_j \mid X_{V \setminus\{i,j\}} X i ⊥ X j ∣ X V ∖ { i , j } if and only if Ω i j ∗ ( k ) = 0 \Omega_{ij}^{*(k)} = 0 Ω ij ∗ ( k ) = 0 , so edges in the global graph G ∗ G^* G ∗ are encoded by the sparsity pattern of Ω ∗ ( k ) \Omega^{*(k)} Ω ∗ ( k ) (Engelke & Hitz 2018). Here, ⊥ \perp ⊥ represents extremal conditional independence in the limiting Hüsler–Reiss distribution. Appealing to Engelke & Taeb (2024), Assumption 1 can be rephrased in a similar algebraic fashion as in Example 2.
Example 7 (Discrete graphical models). Suppose each X i X_i X i takes values in a finite discrete state space X i \mathcal{X}_i X i , and P ( k ) P^{(k)} P ( k ) is a strictly positive distribution with probability mass function p ( k ) p^{(k)} p ( k ) . Unlike the preceding examples, conditional independence in discrete graphical models is not, in general, characterized by the sparsity pattern of a precision-like matrix. Instead, letting R = S k ∖ { i , j } R=S_k\setminus\{i,j\} R = S k ∖ { i , j } , X i ⊥ X j ∣ X R X_i\perp X_j\mid X_R X i ⊥ X j ∣ X R if and only if p S k ( k ) ( x i , x j , x R ) p S k ( k ) ( x i ′ , x j ′ , x R ) = p S k ( k ) ( x i , x j ′ , x R ) p S k ( k ) ( x i ′ , x j , x R ) p_{S_k}^{(k)}(x_i,x_j,x_R)p_{S_k}^{(k)}(x_i',x_j',x_R)=p_{S_k}^{(k)}(x_i,x_j',x_R)p_{S_k}^{(k)}(x_i',x_j,x_R) p S k ( k ) ( x i , x j , x R ) p S k ( k ) ( x i ′ , x j ′ , x R ) = p S k ( k ) ( x i , x j ′ , x R ) p S k ( k ) ( x i ′ , x j , x R ) for all x i , x i ′ , x j , x j ′ , x R x_i,x_i',x_j,x_j',x_R x i , x i ′ , x j , x j ′ , x R , where p S k ( k ) p_{S_k}^{(k)} p S k ( k ) is the marginalization of p ( k ) p^{(k)} p ( k ) onto S k S_k S k . Here, ⊥ \perp ⊥ denotes probabilistic conditional independence. Equivalently, conditional independence holds if and only if for all 2 × 2 2\times2 2 × 2 minors of the corresponding conditional probability tables vanish. Assumption 1 can therefore be expressed algebraically by requiring, for every k ∈ [ K ] k\in[K] k ∈ [ K ] and i , j ∈ S k i,j\in S_k i , j ∈ S k , these minors vanish if and only if R R R separates i i i and j j j in G ∗ \mathcal{G}^{*} G ∗ .
Identifiability
Given access to the conditional independence relations encoded by P S k ( k ) P_{S_k}^{(k)} P S k ( k ) for k ∈ [ K ] k\in[K] k ∈ [ K ] , can we recover the global graph G ∗ \mathcal{G}^{*} G ∗ ? If G ∗ \mathcal{G}^{*} G ∗ is not uniquely identifiable – particularly when the observed variable sets S k S_k S k have insufficient overlap – what is the corresponding equivalence class of graphs?
Under Assumption 1, we can formalize identifiability purely in graphical terms. Our formalism requires the following definition.
Definition 5 (Equivalence class). Take any graph G \mathcal{G} G over vertex set V V V and subsets S k ⊆ V S_k\subseteq V S k ⊆ V , k ∈ [ K ] k\in[K] k ∈ [ K ] . Then, we define the class of graphs equivalent to G \mathcal{G} G as:
EC ( G ; { S k } k = 1 K ) = { Undirected graph G ′ over vertex set V : π S k ( G ′ ) = π S k ( G ) ∀ k ∈ [ K ] } . (1) \operatorname{EC}(\mathcal{G};\{S_k\}_{k=1}^{K})=\{\text{Undirected graph }\mathcal{G}'\text{ over vertex set }V:\pi_{S_k}(\mathcal{G}')=\pi_{S_k}(\mathcal{G})\ \forall\ k\in[K]\}. \tag*{(1)} EC ( G ; { S k } k = 1 K ) = { Undirected graph G ′ over vertex set V : π S k ( G ′ ) = π S k ( G ) ∀ k ∈ [ K ]} . (1)
The equivalence class EC ( G ; { S k } k = 1 K ) \operatorname{EC}(\mathcal{G};\{S_k\}_{k=1}^{K}) EC ( G ; { S k } k = 1 K ) consists of all global graphs G ′ \mathcal{G}' G ′ whose latent projected graphs onto S k S_k S k coincide with those of G \mathcal{G} G for all k ∈ [ K ] k\in[K] k ∈ [ K ] . With Definition 5, we can formally characterize the equivalence class compatible with the observed local graph structures. The proof is in Appendix § 11 .§ 1 .
Proposition 8 (Identifiability). Under Assumption 1, given access to pairwise conditional independences implied by P S k ( k ) P_{S_k}^{(k)} P S k ( k ) , k ∈ [ K ] k\in[K] k ∈ [ K ] , the global graph G ∗ \mathcal{G}^{*} G ∗ is identifiable up to the equivalence class EC ( G ∗ ; { S k } k = 1 K ) \operatorname{EC}(\mathcal{G}^{*};\{S_k\}_{k=1}^{K}) EC ( G ∗ ; { S k } k = 1 K ) .
Depending on the degree of overlap in the sets S k S_k S k , k ∈ [ K ] k\in[K] k ∈ [ K ] , the size of the equivalence class EC ( G ∗ ; { S k } k = 1 K ) \operatorname{EC}(\mathcal{G}^{*};\{S_k\}_{k=1}^{K}) EC ( G ∗ ; { S k } k = 1 K ) can vary. Moreover, graphs in the equivalence class need not have the same number of edges.
When the full marginal distributions P S k ( k ) P_{S_k}^{(k)} P S k ( k ) are available, rather than only their pairwise conditional independence relations, additional constraints may allow us to rule out certain graphs within the projection-equivalence class. In Gaussian graphical models, covariance rank constraints have been characterized for general undirected graphs (Sullivant et al. 2010), while more complete algebraic characterizations and associated statistical tests have been developed for Gaussian latent-tree models (Shiers et al. 2016, Leung & Drton 2018). Such constraints could be assessed separately for each source and combined to further refine the equivalence class. Developing a computationally efficient and statistically valid procedure for such refinement, particularly across the general graph structures and distributional families considered here, is beyond the scope of this work and is left for future research.
Even if the graph G ∗ G^* G ∗ is not fully identifiable, some of its edges may be. We next formalize edge identifiability, under which the presence or absence of an edge is the same across all members of the equivalence class.
Definition 6 (Edge identifiability). An edge ( i , j ) ∈ V × V (i,j) \in V \times V ( i , j ) ∈ V × V is identifiable with respect to { S k } k = 1 K \{S_k\}_{k=1}^{K} { S k } k = 1 K if it is always present or always absent in the equivalence class of G ∗ G^* G ∗ ; that is, either i i i and j j j are adjacent in every graph G ∈ EC ( G ∗ ; { S k } k = 1 K ) G \in\operatorname{EC}(G^*;\{S_k\}_{k=1}^{K}) G ∈ EC ( G ∗ ; { S k } k = 1 K ) or they are nonadjacent in every graph G ∈ EC ( G ∗ ; { S k } k = 1 K ) G \in\operatorname{EC}(G^*;\{S_k\}_{k=1}^{K}) G ∈ EC ( G ∗ ; { S k } k = 1 K ) .
Since the latent projection operator depends globally on the graph structure, the absence or presence of an edge between a pair of nodes may be identified even if the pair is not co-observed in any source. This phenomenon is highlighted in the following example.
Example 9. Consider the true global graph G ∗ G^* G ∗ among four variables { X 1 , X 2 , X 3 , X 4 } \{X_1, X_2, X_3, X_4\} { X 1 , X 2 , X 3 , X 4 } in the top row of Figure 1 . Suppose we have three sources with S 1 = { 1 , 3 } S_1 = \{1, 3\} S 1 = { 1 , 3 } , S 2 = { 1 , 3 , 4 } S_2 = \{1, 3, 4\} S 2 = { 1 , 3 , 4 } , and S 3 = { 1 , 2 , 3 } S_3 = \{1, 2, 3\} S 3 = { 1 , 2 , 3 } . The latent projected (local) graphs of G ∗ G^* G ∗ in each of the three sources are displayed in top row of the figure. Under Assumption 1, each graph encodes exactly the conditional independence relationships in the associated marginal distribution. The bottom row of Figure 1 shows the two graphs in EC ( G ∗ ; { S k } k = 1 K ) \operatorname{EC}(G^*;\{S_k\}_{k=1}^{K}) EC ( G ∗ ; { S k } k = 1 K ) , highlighting that G ∗ G^* G ∗ cannot be distinguished from the other global graph using the marginal graphs. Nonetheless, the absence or presence of certain edges is identifiable; in particular, the edge between X 1 X_1 X 1 and X 3 X_3 X 3 is absent, whereas the edge between X 2 X_2 X 2 and X 4 X_4 X 4 is present. Interestingly, the edge between X 2 X_2 X 2 and X 4 X_4 X 4 is identifiable even though they are never co-observed in the three sources.
Figure 1. Top row. The true graph G ∗ \mathcal{G}^{*} G ∗ and three latent-projection graphs of G ∗ \mathcal{G}^{*} G ∗ obtained from three sources with S 1 = { 1 , 3 } S_{1}=\{1,3\} S 1 = { 1 , 3 } , S 2 = { 1 , 3 , 4 } S_{2}=\{1,3,4\} S 2 = { 1 , 3 , 4 } , and S 3 = { 1 , 2 , 3 } S_{3}=\{1,2,3\} S 3 = { 1 , 2 , 3 } . Bottom row. The only two graphs in the equivalence class, one being the true graph, whose latent projections match precisely the ones in the top row. The edge between X 2 X_{2} X 2 and X 4 X_{4} X 4 is identified even though they are never co-observed in the three sources.
Summarizing graph equivalence classes without enumeration
For a given graph G \mathcal{G} G the equivalence class EC ( G ; { S k } k = 1 K ) \operatorname{EC}(\mathcal{G};\{S_k\}_{k=1}^{K}) EC ( G ; { S k } k = 1 K ) generally does not admit a compact representation. Although Section 4 provides an integer programming procedure for enumerating its members, the equivalence class may contain many graphs, making exhaustive enumeration computationally costly and the resulting collection difficult to interpret. This motivates seeking informative summaries that can be computed without explicitly enumerating the entire equivalence class.
Here we list few examples of useful summaries: edge identifiability (see Definition 6): for each pair of nodes ( i , j ) (i,j) ( i , j ) , we can ask whether the presence or absence of an edge is identified; local edge implications : whether the presence of an edge between ( i , j ) (i,j) ( i , j ) implies the presence of an edge between ( i ′ , j ′ ) (i',j') ( i ′ , j ′ ) , or whether the two edges are always jointly present or absent; separation statements : given disjoint variable sets A , B , C ⊆ V A,B,C \subseteq V A , B , C ⊆ V , whether in every graph in the equivalence class, C C C separates A A A and B B B . Under faithfulness (e.g., Assumption 1′), this property would mean that all graphs specify the conditional independence relationship X A ⊥ X B ∣ X C X_A \perp X_B \mid X_C X A ⊥ X B ∣ X C ; and bounds on graph attributes : the minimum or maximum number of edges among graphs in the equivalence class, or the minimum or maximum degree of a given node.
All the above summary statistics can be obtained by solving the following optimization problem, without explicitly enumerating the equivalence class of graphs:
min undirected graph G ′ over V f ( G ′ ) subject-to: G ′ ∈ EC ( G ; { S k } k = 1 K ) . (2) \underset{\substack{\text{undirected graph } \mathcal{G}'\\ \text{over } V}}{\min}\quad f(\mathcal{G}') \qquad\text{subject-to:}\quad\mathcal{G}' \in\operatorname{EC}(\mathcal{G};\{S_k\}_{k=1}^{K}). \tag*{(2)} undirected graph G ′ over V min f ( G ′ ) subject-to: G ′ ∈ EC ( G ; { S k } k = 1 K ) . (2)
For edge identifiability, we can set f ( G ′ ) = I [ ( i , j ) ∈ E ( G ′ ) ] f(\mathcal{G}') = \mathbb{I}[(i,j) \in E(\mathcal{G}')] f ( G ′ ) = I [( i , j ) ∈ E ( G ′ )] . An optimal value of one implies that i i i and j j j are adjacent in every graph in the equivalence class; otherwise, there exists at least one graph in the equivalence class in which they are nonadjacent. Taking f ( G ′ ) = I [ ( i , j ) ∉ E ( G ′ ) ] f(\mathcal{G}') = \mathbb{I}[(i,j) \notin E(\mathcal{G}')] f ( G ′ ) = I [( i , j ) ∈ / E ( G ′ )] can similarly verify whether i i i and j j j are nonadjacent in every graph in the equivalence class. For logical edge implications, let f ( G ′ ) = I [ ( i ′ , j ′ ) ∈ E ( G ′ ) ] − I [ ( i , j ) ∈ E ( G ′ ) ] f(\mathcal{G}') = \mathbb{I}[(i',j') \in E(\mathcal{G}')] - \mathbb{I}[(i,j) \in E(\mathcal{G}') ] f ( G ′ ) = I [( i ′ , j ′ ) ∈ E ( G ′ )] − I [( i , j ) ∈ E ( G ′ )] . A non-negative optimal value means that if an edge between $(i,j) appears in a graph, the edge between ( i ′ , j ′ ) (i',j') ( i ′ , j ′ ) also appears. For conditional independence relationships, we set f ( G ′ ) = I [ A and B are separated in G ′ by C ] f(G')=\mathbb{I}[A\text{ and }B\text{ are separated in }G'\text{ by }C] f ( G ′ ) = I [ A and B are separated in G ′ by C ] . Under faithfulness in Assumption 1′, an optimal value of one means that all the graphs agree on the conditional independence relation A ⊥ B ∣ C A\perp B\mid C A ⊥ B ∣ C . Finally, for bounds on graph attributes, let f ( G ′ ) = # edges in G ′ f(G')=\#\text{ edges in }G' f ( G ′ ) = # edges in G ′ . The optimal value gives a lower bound on the number of edges, and an upper bound can be obtained by considering the negative of f ( G ′ ) f(G') f ( G ′ ) . A lower and upper bound on the degree can be similarly obtained by a suitable function f ( G ′ ) f(G') f ( G ′ ) .
In all the settings described above, we show in § 4.5 that the optimization problem (2) can be cast as a linear mixed-integer program (MIP). Crucial to this characterization is that the constraint G ′ ∈ EC ( G ; { S k } k = 1 K ) G'\in\operatorname{EC}(G;\{S_k\}_{k=1}^{K}) G ′ ∈ EC ( G ; { S k } k = 1 K ) can be expressed as linear equalities/inequalities over a collection of binary variables, without explicitly enumerating the equivalence class. Such a formulation enables advanced branch and bound and cutting plane algorithms to be deployed to solve the optimization problem relatively efficiently.
An estimator for reconstructing a global graph
Preliminaries
We suppose that each source provides one of two types of local information. For sources in W 1 ⊆ [ K ] \mathcal{W}_1\subseteq[K] W 1 ⊆ [ K ] , we have access to the local data: source k ∈ W 1 k\in\mathcal{W}_1 k ∈ W 1 provides observations drawn from the marginal distribution P S k ( k ) P_{S_k}^{(k)} P S k ( k ) . For sources in W 2 = [ K ] ∖ W 1 \mathcal{W}_2=[K]\setminus\mathcal{W}_1 W 2 = [ K ] ∖ W 1 , we instead observe only an estimated local graph. This may arise in federated learning settings, where privacy or data-governance constraints prevent the sharing of raw data and only a learned graph can be released. Another example is evidence synthesis across published studies, where the original data are unavailable but estimated graphical structures are reported, potentially for different subsets of variables. Finally, it may also arise when fitting a graph to a particular source requires a specialized procedure with a highly nonconvex loss that is not amenable to convex mixed-integer programming (e.g., real-data analysis in § 8 ). In such cases, the source can first estimate its local graph using an appropriate method and then pass the resulting graph to the integrative procedure. Our goal is to combine these two forms of local information to estimate a global graph.
For each k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 , let G ^ S k ( k ) \widehat{G}_{S_k}^{(k)} G S k ( k ) denote the graph estimate on vertex set S k S_k S k supplied by source k k k . We assume this estimate is obtained from n k n_k n k independent and identically distributed observations drawn from the marginal distribution P S k ( k ) P_{S_k}^{(k)} P S k ( k ) . For each k ∈ W 1 k\in\mathcal{W}_1 k ∈ W 1 , let D k \mathcal{D}_k D k denote the corresponding local dataset of size n k : = ∣ D k ∣ n_k:=|\mathcal{D}_k| n k := ∣ D k ∣ . To incorporate these local datasets into an estimate of the global graph, we require a loss function that evaluates how well a candidate graph G ~ \widetilde{G} G on S k S_k S k fits D k \mathcal{D}_k D k , augmented by a sparsity-promoting penalty proportional to the number of free parameters. We denote this loss function by:
Loss k ( G ~ ; D k ) = min θ ( k ) ∈ Θ k ( G ~ ) ℓ k ( θ ( k ) ; D k ) + λ k ⋅ dim ( Θ k ( G ~ ) ) (3) \operatorname{Loss}_k(\widetilde{G};\mathcal{D}_k)=\min_{\theta^{(k)}\in\Theta_k(\widetilde{G})}\ell_k(\theta^{(k)};\mathcal{D}_k)+\lambda_k\cdot\dim(\Theta_k(\widetilde{G})) \tag*{(3)} Loss k ( G ; D k ) = θ ( k ) ∈ Θ k ( G ) min ℓ k ( θ ( k ) ; D k ) + λ k ⋅ dim ( Θ k ( G )) (3)
where ℓ k ( θ ( k ) ; D k ) \ell_k(\theta^{(k)};\mathcal{D}_k) ℓ k ( θ ( k ) ; D k ) measures the lack of fit of the distribution indexed by θ ( k ) \theta^{(k)} θ ( k ) to the local data, and Θ k ( G ~ ) \Theta_k(\widetilde{G}) Θ k ( G ) denotes the admissible parameter space associated with the chosen loss function and the graph G ~ \widetilde{G} G . Thus, Loss k ( G ~ ; D k ) \operatorname{Loss}_k(\widetilde{G};\mathcal{D}_k) Loss k ( G ; D k ) is the minimum achievable loss over Θ k ( G ~ ) \Theta_k(\widetilde{G}) Θ k ( G ) , augmented by a sparsity-promoting penalty proportional to the dimension of Θ k ( G ~ ) \Theta_k(\widetilde{G}) Θ k ( G ) ; here, dim ( Θ k ( G ~ ) ) \dim(\Theta_k(\widetilde{G})) dim ( Θ k ( G )) is the dimension of the parameter space associated with G ~ \widetilde{G} G . Although the penalty is constant in the optimization over θ ( k ) \theta^{(k)} θ ( k ) for a fixed graph, it varies across candidate graphs and discourages overfitting. We discuss strategies for choosing the regularization parameter in § 7 . In § 3.3 , for Examples 2–7, we describe choices for the loss ℓ k ( ⋅ ) \ell_k(\cdot) ℓ k ( ⋅ ) , the corresponding parameter space Θ k ( G ~ ) \Theta_k(\widetilde{G}) Θ k ( G ) , and its dimension.
To ensure that our procedure is statistically accurate, both the estimators used to obtain the local graphs G ^ S k ( k ) \widehat{G}_{S_k}^{(k)} G S k ( k ) for k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 and the graph estimators obtained by minimizing Loss k ( G ~ ; D k ) \operatorname{Loss}_k(\widetilde{G};\mathcal{D}_k) Loss k ( G ; D k ) for k ∈ W 1 k\in\mathcal{W}_1 k ∈ W 1 must be consistent.
Assumption 2 (Consistency). As n k ⟶ ∞ n_k\longrightarrow\infty n k ⟶ ∞ ,
for every k ∈ W 1 , P P ( k ) ( argmin undirected graph G ~ over S k Loss k ( G ~ ; D k ) = { G S k ∗ ( k ) } ) ⟶ 1 , for every k ∈ W 2 , P P ( k ) ( G ^ S k ( k ) = G S k ∗ ( k ) ) ⟶ 1. \begin{aligned}
&\text{for every }k\in\mathcal{W}_1,\quad\mathbb{P}_{P^{(k)}}\left(\underset{\text{undirected graph }\widetilde{G}\text{ over }S_k}{\operatorname{argmin}}\ \operatorname{Loss}_k(\widetilde{G};\mathcal{D}_k)=\{G_{S_k}^{*(k)}\}\right)\longrightarrow1,\\
&\text{for every }k\in\mathcal{W}_2,\quad\mathbb{P}_{P^{(k)}}\left(\widehat{G}_{S_k}^{(k)}=G_{S_k}^{*(k)}\right)\longrightarrow1.
\end{aligned} for every k ∈ W 1 , P P ( k ) ( undirected graph G over S k argmin Loss k ( G ; D k ) = { G S k ∗ ( k ) } ) ⟶ 1 , for every k ∈ W 2 , P P ( k ) ( G S k ( k ) = G S k ∗ ( k ) ) ⟶ 1.
Here, G S k ∗ ( k ) G_{S_k}^{*(k)} G S k ∗ ( k ) is defined in Definition 4 .
In Section 3.3, we discuss settings where Assumption 2 is satisfied.
Estimator
To learn a global undirected graph, we propose the following estimator for γ ≥ 0 \gamma\ge0 γ ≥ 0 and ω k ≥ 0 \omega_k \ge0 ω k ≥ 0 :
G ^ ∈ arg min undirected graph G over V ∑ k ∈ W 1 ω k Loss k ( π S k ( G ) ; D k ) + γ ∑ k ∈ W 2 ω k SHD ( π S k ( G ) , G ^ S k ( k ) ) . (4) \widehat{\mathcal{G}} \in\underset{\text{undirected graph }\mathcal{G}\text{ over }V}{\arg\min}\ \sum_{k\in\mathcal{W}_1}\omega_k\operatorname{Loss}_k(\pi_{S_k}(\mathcal{G});\mathcal{D}_k)+\gamma\sum_{k\in\mathcal{W}_2}\omega_k\operatorname{SHD}(\pi_{S_k}(\mathcal{G}),\widehat{\mathcal{G}}_{S_k}^{(k)}). \tag*{(4)} G ∈ undirected graph G over V arg min k ∈ W 1 ∑ ω k Loss k ( π S k ( G ) ; D k ) + γ k ∈ W 2 ∑ ω k SHD ( π S k ( G ) , G S k ( k ) ) . (4)
Here, for two undirected graphs G 1 G_1 G 1 and G 2 G_2 G 2 on the same vertex set, SHD ( G 1 , G 2 ) \operatorname{SHD}(G_1,G_2) SHD ( G 1 , G 2 ) denotes their structural Hamming distance, namely, the number of edges on which they differ. For each candidate global graph G \mathcal{G} G , the objective of (4) evaluates how well π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) fits the data from each source k ∈ W 1 k\in\mathcal{W}_1 k ∈ W 1 and how closely it agrees with the estimated local graph provided by sources k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 . The estimator therefore selects a global graph that minimizes the weighted discrepancies across sources.
The weights ω k \omega_k ω k determine the relative contributions of the sources. One possible choice is ω k = n k / ∑ k n k \omega_k=n_k/\sum_k n_k ω k = n k / ∑ k n k , so that sources with more observations receive greater weight. More generally, the weights may reflect differences in source reliability or account for differences in the scales of the source-specific loss functions. The parameter γ \gamma γ additionally controls the relative contribution of sources providing graph estimates rather than raw data; we describe strategies to choose γ \gamma γ in Remark 2.
Notice that since the optimization problem in (4) depends on G \mathcal{G} G only through its latent projections { π S k ( G ) } k = 1 K \{\pi_{S_k}(\mathcal{G})\}_{k=1}^K { π S k ( G ) } k = 1 K , any G ∈ EC ( G ^ ; { S k } k = 1 K ) \mathcal{G}\in\operatorname{EC}(\widehat{\mathcal{G}};\{S_k\}_{k=1}^K) G ∈ EC ( G ; { S k } k = 1 K ) yields exactly the same objective value. Consequently, the estimator cannot distinguish between graphs within the same projection-equivalence class. The following proposition establishes that, under suitable conditions, EC ( G ^ ; { S k } k = 1 K ) \operatorname{EC}(\widehat{\mathcal{G}};\{S_k\}_{k=1}^K) EC ( G ; { S k } k = 1 K ) consistently estimates the population equivalence class EC ( G ⋆ ; { S k } k = 1 K ) \operatorname{EC}(\mathcal{G}^{\star};\{S_k\}_{k=1}^K) EC ( G ⋆ ; { S k } k = 1 K ) . The proof is in Appendix A.2. Throughout, when a source does not contribute to the objective in (4) because ω k = 0 \omega_k=0 ω k = 0 or, for k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 , γ = 0 \gamma=0 γ = 0 , the equivalence classes are understood to be defined only with respect to the remaining sources.
Proposition 10. Suppose Assumptions 1-2 hold. Then, we have that:
P P ( 1 ) , P ( 2 ) , … , P ( K ) ( EC ( G ^ ; { S k } k = 1 K ) = EC ( G ⋆ ; { S k } k = 1 K ) ) ⟶ 1 as n k ⟶ ∞ ∀ k ∈ [ K ] . \mathbb{P}_{P_{(1)},P_{(2)},\ldots,P_{(K)}}\left(\operatorname{EC}(\widehat{\mathcal{G}};\{S_k\}_{k=1}^K)=\operatorname{EC}(\mathcal{G}^{\star};\{S_k\}_{k=1}^K)\right)\longrightarrow1\text{ as }n_k\longrightarrow\infty\ \forall k\in[K]. P P ( 1 ) , P ( 2 ) , … , P ( K ) ( EC ( G ; { S k } k = 1 K ) = EC ( G ⋆ ; { S k } k = 1 K ) ) ⟶ 1 as n k ⟶ ∞ ∀ k ∈ [ K ] . That is, the estimator (4) consistently estimates the population equivalence class of G ⋆ \mathcal{G}^{\star} G ⋆ .
Remark 1. Notice that Proposition 10 assumes the size of the vertex set V V V does not grow with the sample size. In Section 6, we provide high-dimensional consistency guarantees that allow for the the number of vertices to grow with the sample size.
Remark 2 (Choosing γ \gamma γ ). The user may specify γ \gamma γ based on domain knowledge, assigning greater weight to one type of local information than to the other. Alternatively, γ \gamma γ may be selected in a data-driven manner using hold-out validation. Specifically, we partition the data into a training set D k t r a i n \mathcal{D}_k^{\mathrm{train}} D k train and a validation set D k v a l i d \mathcal{D}_k^{\mathrm{valid}} D k valid . For each candidate γ \gamma γ , we solve (4) using the training data to obtain G ^ γ \widehat{\mathcal{G}}_\gamma G γ ; this also gives the associated continuous model parameters Θ ^ γ ( k ) \widehat{\Theta}^{(k)}_\gamma Θ γ ( k ) . The corresponding validation score is ∑ k ∈ W 1 Loss k ( Θ ^ γ ( k ) ; D k v a l i d ) \sum_{k\in\mathcal{W}_1}\operatorname{Loss}_k(\widehat{\Theta}^{(k)}_\gamma;\mathcal{D}_k^{\mathrm{valid}}) ∑ k ∈ W 1 Loss k ( Θ γ ( k ) ; D k valid ) . We can select the value of γ \gamma γ that minimizes this validation score. Another possibility, which we adopt in our experiments, is to calibrate γ \gamma γ to the sparsity penalties in the data-source losses. When these penalties are proportional to the number of edges, we set γ \gamma γ equal to the median penalty per undirected edge across the data-providing sources. Since one unit of SHD represents one edge disagreement, this places its cost on the scale of a typical data-source edge penalty.
Discussion of Assumption 2
Below, we describe choices of loss functions and parameter spaces for the distributional families considered in Examples 2–7, for which Assumption 2 can hold under suitable regularity and tuning conditions. In the following examples, G \mathcal{G} G is an undirected graph over S k S_k S k .
Gaussian graphical models in Example 2. Let ℓ k \ell_k ℓ k be the negative Gaussian log-likelihood, defined for Θ k ( G ) : = { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ i j = 0 if ( i , j ) ∉ E ( G ) } \Theta_k(\mathcal{G}):=\{\theta\in\mathbb{R}^{|S_k|\times|S_k|}:\theta_{ij}=0\text{ if }(i,j)\notin E(\mathcal{G})\} Θ k ( G ) := { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ ij = 0 if ( i , j ) ∈ / E ( G )} :
ℓ k ( θ ( k ) ; D k ) : = − log det ( θ ( k ) ) + tr ( Σ ^ k θ ( k ) ) . (5) \ell_k(\theta^{(k)};\mathcal{D}_k):=-\log\det(\theta^{(k)})+\operatorname{tr}(\widehat{\Sigma}_k\theta^{(k)}). \tag*{(5)} ℓ k ( θ ( k ) ; D k ) := − log det ( θ ( k ) ) + tr ( Σ k θ ( k ) ) . (5)
Here, Σ ^ k ∈ R ∣ S k ∣ × ∣ S k ∣ \widehat{\Sigma}_k\in\mathbb{R}^{|S_k|\times|S_k|} Σ k ∈ R ∣ S k ∣ × ∣ S k ∣ is the sample covariance matrix of the data in source k k k . Further, dim ( Θ k ( G ) ) = ∣ E ( G ) ∣ + ∣ S k ∣ \dim(\Theta_k(\mathcal{G}))=|E(\mathcal{G})|+|S_k| dim ( Θ k ( G )) = ∣ E ( G ) ∣ + ∣ S k ∣ .
Another possible loss, defined for Θ k ( G ~ ) : = { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ i i = 0 ∀ i , θ i j = 0 if ( i , j ) ∉ E ( G ~ ) } \Theta_k(\widetilde{\mathcal{G}}) := \{\theta\in\mathbb{R}^{|S_k|\times|S_k|} : \theta_{ii} = 0\ \forall i, \theta_{ij} = 0\ \text{if } (i,j) \notin E(\widetilde{\mathcal{G}})\} Θ k ( G ) := { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ ii = 0 ∀ i , θ ij = 0 if ( i , j ) ∈ / E ( G )} , is based on pseudo-likelihood approximation (Besag 1974) and takes on the quadratic form:
(6)
ℓ k ( θ ( k ) ; D k ) : = tr ( ( I − θ ( k ) ) T Σ ^ k ( I − θ ( k ) ) ) . (6) \ell_k(\theta^{(k)};D_k) := \operatorname{tr}\left((I-\theta^{(k)})^{\mathsf{T}}\widehat{\Sigma}_k(I-\theta^{(k)})\right). \tag*{(6)} ℓ k ( θ ( k ) ; D k ) := tr ( ( I − θ ( k ) ) T Σ k ( I − θ ( k ) ) ) . (6)
Here, dim ( Θ k ( G ~ ) ) = 2 ∣ E ( G ~ ) ∣ \dim(\Theta_k(\widetilde{\mathcal{G}})) = 2|E(\widetilde{\mathcal{G}})| dim ( Θ k ( G )) = 2∣ E ( G ) ∣ . In our experiments, we favor the quadratic loss (6) over its non-quadratic counterpart (5) since it yields a mixed-integer quadratic program, which is amenable to computationally faster algorithms. See § 4.2.1 for a detailed discussion. Note that the loss (6), augmented with the L 1 L_1 L 1 penalty on the coefficients θ ( k ) \theta^{(k)} θ ( k ) , is the neighborhood selection procedure (Meinshausen & Bühlmann 2006b). Since our formulation already introduces binary variables to encode the latent projections, an L 0 L_0 L 0 penalty on the coefficients, which is equivalently dim ( Θ k ( G ~ ) ) \dim(\Theta_k(\widetilde{\mathcal{G}})) dim ( Θ k ( G )) , can be represented as a linear function of these binary variables and therefore does not require any additional integer variables.
Pearson correlation graphical models in Example 3. The loss (5) or (6) can be used directly, with the same choices for Θ k ( G ~ ) \Theta_k(\widetilde{\mathcal{G}}) Θ k ( G ) and its dimension as in the Gaussian example.
Gaussian copula and Elliptical graphical models in Examples 4-5. The losses (5) or (6) can again be used after replacing Σ ^ k \widehat{\Sigma}_k Σ k with the rank-based estimator R ^ \widehat{R} R , obtained from the sample Kendall correlations via R ^ i j = sin ( π τ ^ i j / 2 ) \widehat{R}_{ij} = \sin(\pi\widehat{\tau}_{ij}/2) R ij = sin ( π τ ij /2 ) . Further, Θ k ( G ~ ) \Theta_k(\widetilde{\mathcal{G}}) Θ k ( G ) and its dimension are the same as in the Gaussian example.
Extremal graphical models in Example 6. Let ℓ k \ell_k ℓ k be the following loss, defined for Θ k ( G ~ ) : = { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ 1 = 0 , θ ⪰ 0 , θ i j = 0 if ( i , j ) ∉ E ( G ~ ) } \Theta_k(\widetilde{\mathcal{G}}) := \{\theta\in\mathbb{R}^{|S_k|\times|S_k|} : \theta\mathbf{1} = 0, \theta\succeq0, \theta_{ij} = 0\ \text{if } (i,j) \notin E(\widetilde{\mathcal{G}})\} Θ k ( G ) := { θ ∈ R ∣ S k ∣ × ∣ S k ∣ : θ 1 = 0 , θ ⪰ 0 , θ ij = 0 if ( i , j ) ∈ / E ( G )} with 1 \mathbf{1} 1 denoting all-ones vector (Hentschel et al. 2022, Engelke & Taeb 2024):
ℓ k ( θ ( k ) ; D k ) : = − log det ( U T θ ( k ) U ) + tr ( − Γ ^ 2 θ ( k ) ) . \ell_k(\theta^{(k)};D_k) := -\log\det(U^{\mathsf{T}}\theta^{(k)}U) + \operatorname{tr}\left(-\frac{\widehat{\Gamma}}{2}\theta^{(k)}\right). ℓ k ( θ ( k ) ; D k ) := − log det ( U T θ ( k ) U ) + tr ( − 2 Γ θ ( k ) ) .
Here, U ∈ R ∣ S k ∣ × ∣ S k ∣ − 1 U \in\mathbb{R}^{|S_k|\times|S_k|-1} U ∈ R ∣ S k ∣ × ∣ S k ∣ − 1 is an orthonormal matrix such that U U T UU^{\mathsf{T}} U U T is the projection matrix onto the subspace orthogonal to the all-ones vector. Further, Γ ^ \widehat{\Gamma} Γ is an empirical estimate of the true variogram matrix, and dim ( Θ k ( G ~ ) ) = ∣ E ( G ~ ) ∣ \dim(\Theta_k(\widetilde{\mathcal{G}})) = |E(\widetilde{\mathcal{G}})| dim ( Θ k ( G )) = ∣ E ( G ) ∣ .
Discrete graphical models in Example 7. Let P ^ S k ( k ) \widehat{P}_{S_k}^{(k)} P S k ( k ) denote the empirical distribution of the data in source k k k , over the finite discrete space X : = ∏ i ∈ S k X i \mathcal{X} := \prod_{i\in S_k}\mathcal{X}_i X := ∏ i ∈ S k X i . We parameterize distributions Markov with respect to G ~ \widetilde{\mathcal{G}} G as p θ ( k ) ( x ) = exp { ∑ C ∈ C ( G ~ ) θ C ( k ) ( x C ) − A ( θ ( k ) ) } p_{\theta^{(k)}}(x) = \exp\{\sum_{C\in\mathcal{C}(\widetilde{\mathcal{G}})}\theta_C^{(k)}(x_C) - A(\theta^{(k)})\} p θ ( k ) ( x ) = exp { ∑ C ∈ C ( G ) θ C ( k ) ( x C ) − A ( θ ( k ) )} , where C ( G ~ ) \mathcal{C}(\widetilde{\mathcal{G}}) C ( G ) is the collection of nonempty cliques in G ~ \widetilde{\mathcal{G}} G , θ ( k ) \theta^{(k)} θ ( k ) is a collection of functions θ C ( k ) : X C → R \theta_C^{(k)}:\mathcal{X}_C \to\mathbb{R} θ C ( k ) : X C → R , A ( θ ( k ) ) A(\theta^{(k)}) A ( θ ( k ) ) is a normalization term, and Θ k ( G ~ ) \Theta_k(\widetilde{\mathcal{G}}) Θ k ( G ) denotes the corresponding parameter space. The negative log-likelihood under an undirected graph G ~ \widetilde{\mathcal{G}} G can then be written as
(7)
ℓ k ( θ ( k ) ; D k ) = − ∑ x ∈ X P ^ S k ( k ) ( x ) log p θ ( k ) ( x ) . (7) \ell_k(\theta^{(k)};D_k) = -\sum_{x\in\mathcal{X}}\widehat{P}_{S_k}^{(k)}(x)\log p_{\theta^{(k)}}(x). \tag*{(7)} ℓ k ( θ ( k ) ; D k ) = − x ∈ X ∑ P S k ( k ) ( x ) log p θ ( k ) ( x ) . (7)
Since for any C ∈ C ( G ~ ) C \in\mathcal{C}(\widetilde{\mathcal{G}}) C ∈ C ( G ) , dim ( θ C ) = ∏ i ∈ C { ∣ X i ∣ − 1 } \dim(\theta_C) = \prod_{i\in C}\{|\mathcal{X}_i|-1\} dim ( θ C ) = ∏ i ∈ C { ∣ X i ∣ − 1 } , we have that dim ( Θ k ( G ~ ) ) = ∑ C ∈ C ( G ~ ) ∏ i ∈ C { ∣ X i ∣ − 1 } \dim(\Theta_k(\widetilde{\mathcal{G}})) = \sum_{C\in\mathcal{C}(\widetilde{\mathcal{G}})}\prod_{i\in C}\{|\mathcal{X}_i|-1\} dim ( Θ k ( G )) = ∑ C ∈ C ( G ) ∏ i ∈ C { ∣ X i ∣ − 1 } .
Alternatively, we parameterize the conditional distribution of each variable X i X_i X i given its neighbors X N ( i , G ~ ) X_{\mathcal{N}(i,\widetilde{\mathcal{G}})} X N ( i , G ) as p θ i ( k ) ( x i ∣ x N ( i , G ~ ) ) = exp { θ i ( k ) ( x i , x N ( i , G ~ ) ) − A i ( θ i ( k ) ) } p_{\theta_i^{(k)}}(x_i\mid x_{\mathcal{N}(i,\widetilde{\mathcal{G}})}) = \exp\{\theta_i^{(k)}(x_i,x_{\mathcal{N}(i,\widetilde{\mathcal{G}})}) - A_i(\theta_i^{(k)})\} p θ i ( k ) ( x i ∣ x N ( i , G ) ) = exp { θ i ( k ) ( x i , x N ( i , G ) ) − A i ( θ i ( k ) )} , where θ i ( k ) : X i × X N ( i , G ~ ) → R \theta_i^{(k)}:\mathcal{X}_i\times\mathcal{X}_{\mathcal{N}(i,\widetilde{\mathcal{G}})}\to\mathbb{R} θ i ( k ) : X i × X N ( i , G ) → R and θ ( k ) = { θ i ( k ) } i ∈ S k \theta^{(k)}=\{\theta_i^{(k)}\}_{i\in S_k} θ ( k ) = { θ i ( k ) } i ∈ S k . We let Θ k ( G ~ ) \Theta_k(\widetilde{\mathcal{G}}) Θ k ( G ) denote the resulting parameter space. The negative pseudo-log-likelihood under an undirected graph G ~ \widetilde{\mathcal{G}} G is then
(8)
ℓ k ( θ ( k ) ; D k ) = − ∑ i ∈ S k ∑ x ∈ X P ^ S k ( k ) ( x ) log p θ i ( k ) ( x i ∣ x N ( i , G ~ ) ) . (8) \ell_k(\theta^{(k)};D_k) = -\sum_{i\in S_k}\sum_{x\in\mathcal{X}}\widehat{P}_{S_k}^{(k)}(x)\log p_{\theta_i^{(k)}}(x_i\mid x_{\mathcal{N}(i,\widetilde{\mathcal{G}})}). \tag*{(8)} ℓ k ( θ ( k ) ; D k ) = − i ∈ S k ∑ x ∈ X ∑ P S k ( k ) ( x ) log p θ i ( k ) ( x i ∣ x N ( i , G ) ) . (8)
Compared to (7), the loss in (8) avoids the global normalization constant, requiring only nodewise normalization of the conditional distributions. Here, dim ( Θ k ( G ~ ) ) = ∑ i ∈ S k ( ∣ X i ∣ − 1 ) ∏ j ∈ N ( i , G ~ ) ∣ X j ∣ \dim(\Theta_k(\widetilde{\mathcal{G}})) = \sum_{i\in S_k}(|\mathcal{X}_i|-1)\prod_{j\in\mathcal{N}(i,\widetilde{\mathcal{G}})}|\mathcal{X}_j| dim ( Θ k ( G )) = ∑ i ∈ S k ( ∣ X i ∣ − 1 ) ∏ j ∈ N ( i , G ) ∣ X j ∣ .
Under suitable regularity and identifiability conditions, consistent graph selection in the fixed-dimensional regime, where ∣ S k ∣ |S_k| ∣ S k ∣ does not grow with n k n_k n k , can be obtained by choosing a penalty parameter that vanishes sufficiently slowly. In particular, when the loss is normalized by sample size and the parameter estimators are n k \sqrt{n_k} n k -consistent, sufficient conditions are λ k → 0 \lambda_k \to0 λ k → 0 and n k λ k → ∞ n_k\lambda_k \to\infty n k λ k → ∞ , as satisfied by λ k = log ( n k ) / n k \lambda_k = \log(n_k)/n_k λ k = log ( n k ) / n k .
Note that other model classes, including pairwise exponential-family graphical models, also admit loss functions that yield consistent graph estimators under suitable regularity conditions (Yang et al. 2015). We focus on the examples above as (i) their underlying distributional families are closed under marginalization, and (ii) they admit an algebraic characterization of Assumption 1 (see § 2 ). The first property provides a coherent model for both the full distributions P ( k ) P^{(k)} P ( k ) , which define the global graph G ∗ \mathcal{G}^* G ∗ , and the observed marginal distributions P S k ( k ) P_{S_k}^{(k)} P S k ( k ) . Additionally, the second property allows us to better understand Assumption 1.
Exact solvers: casting estimator as a convex mixed-integer program
Encoding latent projections via mixed-integer constraints
A candidate global graph G = ( V , E ) \mathcal{G}=(V,E) G = ( V , E ) , together with its latent projection onto the observed vertex set S k S_k S k in source k k k , is represented by the binary decision variables
g i j ∈ { 0 , 1 } ∀ 1 ≤ i < j ≤ p , h i j ( k ) ∈ { 0 , 1 } ∀ i < j , i , j ∈ S k . g_{ij} \in\{0,1\} \qquad\forall1 \le i < j \le p,\qquad h_{ij}^{(k)} \in\{0,1\} \qquad\forall i<j,\ i,j\in S_k. g ij ∈ { 0 , 1 } ∀1 ≤ i < j ≤ p , h ij ( k ) ∈ { 0 , 1 } ∀ i < j , i , j ∈ S k .
Here, g i j = 1 g_{ij}=1 g ij = 1 indicates that ( i , j ) ∈ E (i,j)\in E ( i , j ) ∈ E , while the variables h i j ( k ) h_{ij}^{(k)} h ij ( k ) encode the edges of the latent projection graph π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) . Accordingly, for each k ∈ [ K ] k\in[K] k ∈ [ K ] and each pair i < j i<j i < j with i , j ∈ S k i,j\in S_k i , j ∈ S k , we require h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 if and only if i i i and j j j are adjacent in π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) . Equivalently, we enforce the relation
h i j ( k ) = 1 ⟺ i and j are adjacent in G , or h_{ij}^{(k)}=1 \quad\Longleftrightarrow\quad i\text{ and }j\text{ are adjacent in }\mathcal{G},\text{ or} h ij ( k ) = 1 ⟺ i and j are adjacent in G , or
there exists a path between i and j in G whose internal vertices lie in T k , (9) \text{there exists a path between }i\text{ and }j\text{ in }\mathcal{G}\text{ whose internal vertices lie in }T_k, \tag*{(9)} there exists a path between i and j in G whose internal vertices lie in T k , (9)
where T k : = V ∖ S k T_k:=V\setminus S_k T k := V ∖ S k represents hidden vertices, i.e., vertices that are not observed in source k k k . By introducing additional continuous variables, we will show that relation (9) can be expressed as a collection of linear constraints involving the binary variables g i j g_{ij} g ij and h i j ( k ) h_{ij}^{(k)} h ij ( k ) and the auxiliary continuous variables. This formulation is key to recasting the estimator in (4) as a convex MIP, as well as to designing linear MIPs for enumerating graphs in an equivalence class and computing summary statistics of that equivalence class.
For the direction ⇒ \Rightarrow ⇒ in (9), we use a network-flow formulation . Fix an origin i ∈ S k i\in S_k i ∈ S k , which serves as the source of the flow, and let J k ( i ) : = { j ∈ S k , j > i } J_k(i):=\{j\in S_k,j>i\} J k ( i ) := { j ∈ S k , j > i } denote the set of possible destinations. Each variable h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 , with j ∈ J k ( i ) j\in J_k(i) j ∈ J k ( i ) , creates one unit of demand at destination j j j . The flow may be sent directly from i i i to a destination or along a path whose internal vertices lie in T k T_k T k . Let A k ( i ) A_k(i) A k ( i ) denote the set of directed arcs available to this flow. It consists of arcs from i i i to vertices in T k T_k T k and to destinations in J k ( i ) J_k(i) J k ( i ) , arcs in both directions between distinct vertices of T k T_k T k , and arcs from vertices in T k T_k T k to destinations in J k ( i ) J_k(i) J k ( i ) . For each ( u , v ) ∈ A k ( i ) (u,v)\in A_k(i) ( u , v ) ∈ A k ( i ) , let f u v ( k ) , i ≥ 0 f_{uv}^{(k),i}\ge0 f uv ( k ) , i ≥ 0 denote the amount of flow sent along the arc ( u , v ) (u,v) ( u , v ) . A positive flow f u v ( k ) , i > 0 f_{uv}^{(k),i}>0 f uv ( k ) , i > 0 requires the corresponding undirected edge ( u , v ) (u,v) ( u , v ) to be selected in G \mathcal{G} G , that is, g u v = 1 g_{uv}=1 g uv = 1 , with the indices ordered appropriately. Figure 2 (left) illustrates this flow network.
Figure 2. Left. A flow network with S k = { i , j , l } S_k=\{i,j,l\} S k = { i , j , l } with origin i i i and possible destinations J k ( i ) = { j , l } J_k(i)=\{j,l\} J k ( i ) = { j , l } . Here, T k = { a , b } T_k=\{a,b\} T k = { a , b } represents the set of hidden vertices. The directed arcs are specified by A k ( i ) A_k(i) A k ( i ) , which determines the possible directions of flow; arcs between vertices in T k T_k T k are available in both directions. Suppose h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 . The blue arcs illustrate one possible flow from i i i to j j j , with each displayed arc carrying a strictly positive amount of flow. Right. A global graph G \mathcal{G} G over six vertices. One additional vertex is included relative to the left panel to improve the illustration. Here S k = { i , j , l } S_k=\{i,j,l\} S k = { i , j , l } , T k = { a , b , c } T_k=\{a,b,c\} T k = { a , b , c } , and the connected components of the subgraph induced by T k T_k T k are { a , b } \{a,b\} { a , b } and { c } \{c\} { c } . Because the component { a , b } \{a,b\} { a , b } is attached to i i i , we have m a ( k ) , i , m b ( k ) , i > 0 m_a^{(k),i},m_b^{(k),i}>0 m a ( k ) , i , m b ( k ) , i > 0 , whereas m c ( k ) , i = 0 m_c^{(k),i}=0 m c ( k ) , i = 0 . Moreover, since m b ( k ) , i > 0 m_b^{(k),i}>0 m b ( k ) , i > 0 and l l l is adjacent to b b b , it follows that h i l ( k ) = 1 h_{il}^{(k)}=1 h i l ( k ) = 1 . Finally, because i i i and j j j are directly adjacent, we have h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 .
Formally, for each i ∈ S k i\in S_k i ∈ S k and k ∈ [ K ] k\in[K] k ∈ [ K ] , we impose the following linear constraints, connecting the flow variables to g g g and h ( k ) h^{(k)} h ( k ) :
∑ v : ( i , v ) ∈ A k ( i ) f i v ( k ) , i = ∑ j ∈ J k ( i ) h i j ( k ) , ∑ u ∈ T k f u j ( k ) , i + f i j ( k ) , i = h i j ( k ) ∀ j ∈ J k ( i ) , \sum_{v:(i,v)\in A_k(i)} f_{iv}^{(k),i}=\sum_{j\in J_k(i)}h_{ij}^{(k)},\qquad
\sum_{u\in T_k}f_{uj}^{(k),i}+f_{ij}^{(k),i}=h_{ij}^{(k)}\quad\forall j\in J_k(i), v : ( i , v ) ∈ A k ( i ) ∑ f i v ( k ) , i = j ∈ J k ( i ) ∑ h ij ( k ) , u ∈ T k ∑ f u j ( k ) , i + f ij ( k ) , i = h ij ( k ) ∀ j ∈ J k ( i ) ,
f i t ( k ) , i + ∑ u ∈ T k ∖ { t } f u t ( k ) , i = ∑ v ∈ T k ∖ { t } f t v ( k ) , i + ∑ j ∈ J k ( i ) f t j ( k ) , i ∀ t ∈ T k , f_{it}^{(k),i}+\sum_{u\in T_k\setminus\{t\}}f_{ut}^{(k),i}
=\sum_{v\in T_k\setminus\{t\}}f_{tv}^{(k),i}+\sum_{j\in J_k(i)}f_{tj}^{(k),i}
\quad\forall t\in T_k, f i t ( k ) , i + u ∈ T k ∖ { t } ∑ f u t ( k ) , i = v ∈ T k ∖ { t } ∑ f t v ( k ) , i + j ∈ J k ( i ) ∑ f t j ( k ) , i ∀ t ∈ T k ,
f u v ( k ) , i ≤ [ 1 + ( ∣ J k ( i ) ∣ − 1 ) 1 { v ∈ T k } ] g u v , ∀ ( u , v ) ∈ A k ( i ) . (10) f_{uv}^{(k),i}\leq[1+(|J_k(i)|-1)\mathbb{1}\{v\in T_k\}]g_{uv},\quad\forall(u,v)\in A_k(i). \tag*{(10)} f uv ( k ) , i ≤ [ 1 + ( ∣ J k ( i ) ∣ − 1 ) 1 { v ∈ T k }] g uv , ∀ ( u , v ) ∈ A k ( i ) . (10)
The first constraint requires the origin to emit one unit of flow for each selected destination. The second requires each destination j j j to receive exactly h i j ( k ) h_{ij}^{(k)} h ij ( k ) units, either directly from i i i or through a hidden vertex. The third imposes flow conservation at every hidden vertex. Finally, the fourth constraint allows flow only along edges selected in the global graph: arcs entering a destination have capacity one, whereas arcs entering a hidden vertex have capacity ∣ J k ( i ) ∣ |J_k(i)| ∣ J k ( i ) ∣ . Note that our formulation aggregates all destinations associated with the same origin to avoid a separate flow problem for every pair ( i , j ) (i,j) ( i , j ) and reduces the number of flow variables for source k k k from O ( s k 2 t k ) O(s_k^2t_k) O ( s k 2 t k ) to O ( s k t k + s k 2 ) O(s_k t_k+s_k^2) O ( s k t k + s k 2 ) .
To enforce the direction ⇐ \Leftarrow ⇐ in (9), we introduce an auxiliary continuous variable m u ( k ) , i ∈ [ 0 , 1 ] m_u^{(k),i}\in[0,1] m u ( k ) , i ∈ [ 0 , 1 ] for each i ∈ S k i\in S_k i ∈ S k and u ∈ T k u\in T_k u ∈ T k . This variable indicates whether the connected component containing u u u in the subgraph induced by T k T_k T k is attached to i i i , meaning that i i i is adjacent to at least one vertex in the component. In particular, m u ( k ) , i > 0 m_u^{(k),i}>0 m u ( k ) , i > 0 if and only if the connected component containing u u u is attached to i i i . If a vertex in such a component is also attached to some j ∈ J k ( i ) j \in J_k(i) j ∈ J k ( i ) , then G \mathcal{G} G contains a path from i i i to j j j whose internal vertices lie in T k T_k T k , and the constraints force h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 . The case where i i i and j j j are adjacent in G \mathcal{G} G is handled separately in which h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 . See Figure 2 (right) for an illustration.
Formally, for each i ∈ S k i\in S_k i ∈ S k and k ∈ [ K ] k\in[K] k ∈ [ K ] , we impose the following linear constraints, connecting the auxiliary variables to g g g and h ( k ) h^{(k)} h ( k ) :
m u ( k ) , i − m v ( k ) , i ≤ 1 − g u v , m v ( k ) , i − m u ( k ) , i ≤ 1 − g u v , m u ( k ) , i ≥ g i u , ∀ u , v ∈ T k , u < v , m u ( k ) , i ≤ 1 − g u j + h i j ( k ) , g i j ≤ h i j ( k ) , ∀ u ∈ T k , j ∈ J k ( i ) . (11) \begin{aligned}
m_u^{(k),i}-m_v^{(k),i} &\le1-g_{uv}, & m_v^{(k),i}-m_u^{(k),i} &\le1-g_{uv}, & m_u^{(k),i} &\ge g_{iu}, && \forall\ u,v\in T_k,\ u<v,\\
m_u^{(k),i} &\le1-g_{uj}+h_{ij}^{(k)}, & g_{ij} &\le h_{ij}^{(k)}, && \forall\ u\in T_k,\ j\in J_k(i). \tag*{(11)}
\end{aligned} m u ( k ) , i − m v ( k ) , i m u ( k ) , i ≤ 1 − g uv , ≤ 1 − g u j + h ij ( k ) , m v ( k ) , i − m u ( k ) , i g ij ≤ 1 − g uv , ≤ h ij ( k ) , m u ( k ) , i ≥ g i u , ∀ u ∈ T k , j ∈ J k ( i ) . ∀ u , v ∈ T k , u < v , (11)
If g u v = 1 g_{uv}=1 g uv = 1 for hidden vertices u , v ∈ T k u,v\in T_k u , v ∈ T k , the first two inequalities force m u ( k ) , i = m v ( k ) , i m_u^{(k),i}=m_v^{(k),i} m u ( k ) , i = m v ( k ) , i . Thus, the same value is propagated throughout each connected component of the subgraph induced by T k T_k T k . If the origin i i i is adjacent to a hidden vertex u u u , the third constraint forces m u ( k ) , i = 1 m_u^{(k),i}=1 m u ( k ) , i = 1 , and this value propagates throughout the hidden component containing u u u . The fourth constraint ensures that if a hidden component attached to i i i contains a vertex adjacent to j j j , then h i j ( k ) = 1 h_{ij}^{(k)}=1 h ij ( k ) = 1 . Finally, the last constraint handles the case in which i i i and j j j are adjacent. This construction avoids introducing separate reachability variables for every pair ( i , j ) (i,j) ( i , j ) . Instead, the hidden-component variables are shared across all destinations associated with the same origin i i i . As a result, the formulation uses O ( s k t k ) O(s_kt_k) O ( s k t k ) continuous variables and O ( s k t k + s k 2 t k ) O(s_kt_k+s_k^2t_k) O ( s k t k + s k 2 t k ) constraints, rather than O ( s k 2 t k ) O(s_k^2t_k) O ( s k 2 t k ) variables and O ( s k 2 ) O(s_k^2) O ( s k 2 ) constraints.
The linear constraints (10) and (11) provide an exact characterization of a latent projection: if the graph encoded by h ( k ) h^{(k)} h ( k ) is the latent projection onto S k S_k S k of the global graph encoded by g g g , then ( g , h ( k ) ) (g,h^{(k)}) ( g , h ( k ) ) can be extended to a feasible solution of the constraint set; conversely, any feasible pair ( g , h ( k ) ) (g,h^{(k)}) ( g , h ( k ) ) satisfies this latent-projection relation.
Convex mixed-integer programming reformulation of estimator
Building on the constraints in (10) and (11) for encoding latent projections, for the graphical models in Examples 2–7, we reformulate the estimator (4) as a convex MIP.
MIP formulation for Examples 2–6
These examples share two common attributes:
The loss ℓ k ( θ ( k ) ; D k ) \ell_k(\theta^{(k)};\mathcal{D}_k) ℓ k ( θ ( k ) ; D k ) is parameterized by the matrix parameter θ ( k ) ∈ R ∣ S k ∣ × ∣ S k ∣ \theta^{(k)}\in\mathbb{R}^{|S_k|\times|S_k|} θ ( k ) ∈ R ∣ S k ∣ × ∣ S k ∣ and is convex with respect to θ ( k ) \theta^{(k)} θ ( k ) ;
(ii) The condition θ ( k ) ∈ Θ k ( G ~ ) \theta^{(k)} \in\Theta_k(\widetilde{G}) θ ( k ) ∈ Θ k ( G ) can be expressed as θ i j ( k ) = 0 \theta_{ij}^{(k)} = 0 θ ij ( k ) = 0 if ( i , j ) ∉ E ( G ~ ) (i,j) \notin E(\widetilde{G}) ( i , j ) ∈ / E ( G ) , and θ ( k ) ∈ Ξ k \theta^{(k)} \in\Xi_k θ ( k ) ∈ Ξ k , where Ξ k \Xi_k Ξ k is a convex set that does not depend on G ~ \widetilde{G} G .
Recall that, up to a graph-independent additive constant, dim ( Θ k ( G ~ ) ) = c ⋅ ( # edges in G ~ ) \dim(\Theta_k(\widetilde{G})) = c \cdot(\#\text{ edges in } \widetilde{G}) dim ( Θ k ( G )) = c ⋅ ( # edges in G ) where c = 2 c = 2 c = 2 for the quadratic loss (6) ; otherwise c = 1 c = 1 c = 1 . As a result of the above two properties, for all these problems, (4) can be formulated as follows:
argmin G , { θ ( k ) } k ∈ W 1 ∑ k ∈ W 1 ω k [ ℓ k ( θ ( k ) ; D k ) + c λ k ∣ E { π S k ( G ) } ∣ ] + γ ∑ k ∈ W 2 ω k SHD ( π S k ( G ) , G ^ S k ( k ) ) , subject-to: G undirected graph on V , θ ( k ) ∈ Ξ k ∀ k ∈ W 1 , ( i , j ) not adjacent in π S k ( G ) ⇒ θ i j ( k ) = 0 ∀ i , j ∈ S k , k ∈ W 1 . \begin{aligned}
\underset{\mathcal{G},\{\theta^{(k)}\}_{k\in\mathcal{W}_1}}{\operatorname{argmin}}\quad&\sum_{k\in\mathcal{W}_1}\omega_k\left[\ell_k(\theta^{(k)};D_k)+c\lambda_k\left|E\left\{\pi_{S_k}(\mathcal{G})\right\}\right|\right]+\gamma\sum_{k\in\mathcal{W}_2}\omega_k\operatorname{SHD}\left(\pi_{S_k}(\mathcal{G}),\widehat{\mathcal{G}}_{S_k}^{(k)}\right),\\
\text{subject-to:}\quad&\mathcal{G}\text{ undirected graph on }V,\\
&\theta^{(k)}\in\Xi_k\quad\forall k\in\mathcal{W}_1,\\
&(i,j)\text{ not adjacent in }\pi_{S_k}(\mathcal{G})\Rightarrow\theta_{ij}^{(k)}=0\quad\forall i,j\in S_k,k\in\mathcal{W}_1.
\end{aligned} G , { θ ( k ) } k ∈ W 1 argmin subject-to: k ∈ W 1 ∑ ω k [ ℓ k ( θ ( k ) ; D k ) + c λ k ∣ E { π S k ( G ) } ∣ ] + γ k ∈ W 2 ∑ ω k SHD ( π S k ( G ) , G S k ( k ) ) , G undirected graph on V , θ ( k ) ∈ Ξ k ∀ k ∈ W 1 , ( i , j ) not adjacent in π S k ( G ) ⇒ θ ij ( k ) = 0 ∀ i , j ∈ S k , k ∈ W 1 .
Here and throughout, for notational simplicity, we index the rows and columns of θ ( k ) \theta^{(k)} θ ( k ) by the elements of S k S_k S k ; thus, for i , j ∈ S k i,j\in S_k i , j ∈ S k , θ i j ( k ) \theta_{ij}^{(k)} θ ij ( k ) denotes the entry corresponding to the pair ( i , j ) (i,j) ( i , j ) .
The optimization problem above is nonconvex and computationally challenging, primarily because of the latent-projection operator π S k ( ⋅ ) \pi_{S_k}(\cdot) π S k ( ⋅ ) . We now use the binary variables g g g and h h h and the auxiliary continuous variables f f f and m m m introduced in Section 4.1 to reformulate this problem using the linear constraints in (10) and (11) . To simplify notation, we define their joint domain by:
F ( { S k } k = 1 K ) : = { ( g , h , f , m ) : g i , j ∈ { 0 , 1 } ∀ 1 ≤ i < j ≤ p ; h i j ( k ) ∈ { 0 , 1 } ∀ i ∈ S k , j ∈ J k ( i ) , k ∈ [ K ] , f u , v ( k ) , i ≥ 0 ∀ i ∈ S k , ( u , v ) ∈ A k ( i ) , k ∈ [ K ] ; m u ( k ) , i ∈ [ 0 , 1 ] ∀ i ∈ S k , u ∈ T k , k ∈ [ K ] } . \mathcal{F}(\{S_k\}_{k=1}^{K}):=\left\{(g,h,f,m):
\begin{aligned}
&g_{i,j}\in\{0,1\}\ \forall1\leq i<j\leq p; \ h_{ij}^{(k)}\in\{0,1\}\ \forall i\in S_k,j\in J_k(i),k\in[K],\\
&f_{u,v}^{(k),i}\geq0\ \forall i\in S_k,(u,v)\in A_k(i),k\in[K];\ m_u^{(k),i}\in[0,1]\ \forall i\in S_k,u\in T_k,k\in[K]
\end{aligned}
\right\}. F ({ S k } k = 1 K ) := { ( g , h , f , m ) : g i , j ∈ { 0 , 1 } ∀1 ≤ i < j ≤ p ; h ij ( k ) ∈ { 0 , 1 } ∀ i ∈ S k , j ∈ J k ( i ) , k ∈ [ K ] , f u , v ( k ) , i ≥ 0 ∀ i ∈ S k , ( u , v ) ∈ A k ( i ) , k ∈ [ K ] ; m u ( k ) , i ∈ [ 0 , 1 ] ∀ i ∈ S k , u ∈ T k , k ∈ [ K ] } .
Furthermore, for k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 , let h ^ ( k ) \widehat{h}^{(k)} h ( k ) encode the estimated graph G ^ ( k ) \widehat{\mathcal{G}}^{(k)} G ( k ) , so that h ^ i j ( k ) = 1 \widehat{h}_{ij}^{(k)}=1 h ij ( k ) = 1 if and only if i i i and j j j are adjacent in G ^ S k ( k ) \widehat{\mathcal{G}}_{S_k}^{(k)} G S k ( k ) . The values h ^ ( k ) \widehat{h}^{(k)} h ( k ) are fixed and are therefore not decision variables in the optimization problem. A straightforward calculation shows that for every k ∈ W 2 k\in\mathcal{W}_2 k ∈ W 2 :
SHD ( π S k ( G ) , G ^ S k ( k ) ) = ∑ i , j ∈ S k i < j ∣ h i j ( k ) − h ^ i j ( k ) ∣ = ∑ i , j ∈ S k i < j h ^ i j ( k ) + ( 1 − 2 h ^ i j ( k ) ) h i j ( k ) . \operatorname{SHD}\left(\pi_{S_k}(\mathcal{G}),\widehat{\mathcal{G}}_{S_k}^{(k)}\right)=\sum_{\substack{i,j\in S_k\\i<j}}\left|h_{ij}^{(k)}-\widehat{h}_{ij}^{(k)}\right|=\sum_{\substack{i,j\in S_k\\i<j}}\widehat{h}_{ij}^{(k)}+\left(1-2\widehat{h}_{ij}^{(k)}\right)h_{ij}^{(k)}. SHD ( π S k ( G ) , G S k ( k ) ) = i , j ∈ S k i < j ∑ h ij ( k ) − h ij ( k ) = i , j ∈ S k i < j ∑ h ij ( k ) + ( 1 − 2 h ij ( k ) ) h ij ( k ) .
With this simplification, we can obtain the following reformulation of (4) :
argmin ( g , h , f , m ) , { θ ( k ) } k ∈ W 1 ∑ k ∈ W 1 ω k [ ℓ k ( θ ( k ) ; D k ) + c λ k ∑ i , j ∈ S k i < j h i j ( k ) ] + γ ∑ k ∈ W 2 ∑ i , j ∈ S k i < j ω k ( 1 − 2 h ^ i j ( k ) ) h i j ( k ) , subject-to: ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) , θ ( k ) ∈ Ξ k ∀ k ∈ W 1 , ( g , h , f , m ) satisfy the linear constraints in x r e f ‘ ( 10 ) ‘ and x r e f ‘ ( 11 ) ‘ ∀ k ∈ [ K ] , h i j ( k ) = 0 ⇒ θ i j ( k ) = θ j i ( k ) = 0 ∀ i , j ∈ S k , i < j , ∀ k ∈ W 1 . (12) \begin{aligned}
\underset{(g,h,f,m),\{\theta^{(k)}\}_{k\in\mathcal{W}_1}}{\operatorname{argmin}}\quad&\sum_{k\in\mathcal{W}_1}\omega_k\left[\ell_k(\theta^{(k)};D_k)+c\lambda_k\sum_{\substack{i,j\in S_k\\i<j}}h_{ij}^{(k)}\right]+\gamma\sum_{k\in\mathcal{W}_2}\sum_{\substack{i,j\in S_k\\i<j}}\omega_k\left(1-2\widehat{h}_{ij}^{(k)}\right)h_{ij}^{(k)},\\
\text{subject-to:}\quad&(g,h,f,m)\in\mathcal{F}(\{S_k\}_{k=1}^{K}),\\
&\theta^{(k)}\in\Xi_k\quad\forall k\in\mathcal{W}_1,\\
&(g,h,f,m)\text{ satisfy the linear constraints in }{xref}`(10)`\text{ and }{xref}`(11)`\quad\forall k\in[K],\\
&h_{ij}^{(k)}=0\Rightarrow\theta_{ij}^{(k)}=\theta_{ji}^{(k)}=0\quad\forall i,j\in S_k,\ i<j,\ \forall k\in\mathcal{W}_1. \tag*{(12)}
\end{aligned} ( g , h , f , m ) , { θ ( k ) } k ∈ W 1 argmin subject-to: k ∈ W 1 ∑ ω k ℓ k ( θ ( k ) ; D k ) + c λ k i , j ∈ S k i < j ∑ h ij ( k ) + γ k ∈ W 2 ∑ i , j ∈ S k i < j ∑ ω k ( 1 − 2 h ij ( k ) ) h ij ( k ) , ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) , θ ( k ) ∈ Ξ k ∀ k ∈ W 1 , ( g , h , f , m ) satisfy the linear constraints in x r e f ‘ ( 10 ) ‘ and x r e f ‘ ( 11 ) ‘ ∀ k ∈ [ K ] , h ij ( k ) = 0 ⇒ θ ij ( k ) = θ j i ( k ) = 0 ∀ i , j ∈ S k , i < j , ∀ k ∈ W 1 . (12)
We have omitted additive terms that do not depend on the decision variables. The indicator constraint ensures that whenever an edge is absent from the latent projection, the corresponding model parameters are zero. These indicator constraints can be handled directly by standard mixed-integer optimization solvers such as Gurobi. Alternatively, if a valid finite bound M M M is available, they can be expressed as the linear big-M M M inequalities: − M h i j ( k ) ≤ θ i j ( k ) ≤ M h i j ( k ) -Mh_{ij}^{(k)}\leq\theta_{ij}^{(k)}\leq Mh_{ij}^{(k)} − M h ij ( k ) ≤ θ ij ( k ) ≤ M h ij ( k ) and − M h i j ( k ) ≤ θ i j ( k ) ≤ M h i j ( k ) -Mh_{ij}^{(k)}\leq\theta_{ij}^{(k)}\leq Mh_{ij}^{(k)} − M h ij ( k ) ≤ θ ij ( k ) ≤ M h ij ( k ) . Since the loss ℓ ( θ ( k ) ; D k ) \ell(\theta^{(k)};D_k) ℓ ( θ ( k ) ; D k ) is convex over Ξ k \Xi_k Ξ k , the continuous optimization problem is convex for any fixed assignment of the binary variables. Thus, (12) is a convex MIP.
Perspective strengthening and outer approximation for quadratic losses. Formulation (12) provides a general convex MIP formulation of the estimator (4) . When ℓ k ( θ ( k ) ; D k ) \ell_k(\theta^{(k)};D_k) ℓ k ( θ ( k ) ; D k ) is the quadratic loss (6) , we can exploit additional problem structure to develop more efficient convex mixed-integer formulations using perspective strengthening (Cui et al. 2012) and outer approximation (Duran & Grossmann 1986). In our simulations and real data experiments, we apply this faster algorithm. See Appendix § 12 for details.
MIP formulation for Example 7
We describe in Appendix C how the estimator (4), for the loss ℓ k ( θ ( k ) ; D k ) \ell_k(\theta^{(k)}; \mathcal{D}_k) ℓ k ( θ ( k ) ; D k ) given by either (7) or (8), can be cast as a convex MIP. For the loss (7), after restricting G \mathcal{G} G to be chordal (so that every cycle of length at least four has a chord), we use the fact that chordal graphs admit perfect elimination orderings (Fulkerson & Gross 1965). This allows us to obtain a convex MIP formulation. For the loss (8), we exploit the decomposition of the minimized pseudo-likelihood into nodewise conditional entropies, expressed in terms of precomputed empirical entropies.
Enumerating graphs in an equivalence class
Suppose we obtain a global graph G ^ \widehat{\mathcal{G}} G after solving (12) . We next present an integer programming approach to enumerate members of the equivalence class EC ( G ^ ; { S k } k = 1 K ) \operatorname{EC}(\widehat{\mathcal{G}};\{\mathcal{S}_k\}_{k=1}^K) EC ( G ; { S k } k = 1 K ) . Recall that this equivalence class consists of global graphs whose latent projections onto S k \mathcal{S}_k S k match those of G ^ \widehat{\mathcal{G}} G .
Let g ^ \widehat{g} g be binary variables encoding the graph G ^ \widehat{\mathcal{G}} G . We also obtain binary variables h ^ ( k ) \widehat{h}^{(k)} h ( k ) encoding the latent projections of G ^ \widehat{\mathcal{G}} G onto S k \mathcal{S}_k S k , and hence treat these as known. Remark 3 describes how the h ^ ( k ) \widehat{h}^{(k)} h ( k ) can alternatively be obtained via breadth-first-search algorithm. To enumerate the equivalence class, we initialize the procedure by setting g ^ 1 : = g ^ \widehat{g}^{1}:=\widehat{g} g 1 := g . Suppose that, after L L L iterations, we have obtained distinct global graphs g ^ 1 , … , g ^ L \widehat{g}^{1},\ldots,\widehat{g}^{L} g 1 , … , g L whose latent projections agree with the estimated local graphs h ^ ( k ) \widehat{h}^{(k)} h ( k ) , k ∈ [ K ] k\in[K] k ∈ [ K ] . To obtain another member of the equivalence class, we solve the following linear MIP:
argmin ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) 1 , subject-to: ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] , h ( k ) = h ^ ( k ) ∀ k ∈ [ K ] , ∑ 1 ≤ i < j ≤ p g ^ i j ℓ = 1 ( 1 − g i j ) + ∑ 1 ≤ i < j ≤ p g ^ i j ℓ = 0 g i j ≥ 1 ∀ ℓ ∈ [ L ] . (13) \begin{aligned}
\underset{(g,h,f,m)\in\mathcal{F}(\{\mathcal{S}_k\}_{k=1}^{K})}{\operatorname{argmin}}\quad& 1,\\
\text{subject-to:}\quad& (g,h,f,m)\text{ satisfy the linear constraints in (10) and (11)}\ \forall k\in[K],\\
& h^{(k)}=\widehat{h}^{(k)}\quad\forall k\in[K],\\
& \sum_{\substack{1\le i<j\le p\\ \widehat{g}_{ij}^{\ell}=1}}(1-g_{ij})+\sum_{\substack{1\le i<j\le p\\ \widehat{g}_{ij}^{\ell}=0}}g_{ij}\ge1\quad\forall\ell\in[L]. \tag*{(13)}
\end{aligned} ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) argmin subject-to: 1 , ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] , h ( k ) = h ( k ) ∀ k ∈ [ K ] , 1 ≤ i < j ≤ p g ij ℓ = 1 ∑ ( 1 − g ij ) + 1 ≤ i < j ≤ p g ij ℓ = 0 ∑ g ij ≥ 1 ∀ ℓ ∈ [ L ] . (13)
Here, the first constraint ensures that h ( k ) h^{(k)} h ( k ) encodes the latent projection of the global graph encoded by g g g onto S k \mathcal{S}_k S k . The second constraint ensures that these latent projections match those of G ^ \widehat{\mathcal{G}} G . The final constraint ensures that the global graph encoded by g g g is distinct from each of the previously identified graphs g ^ 1 , … , g ^ L \widehat{g}^{1},\ldots,\widehat{g}^{L} g 1 , … , g L .
If (13) has a solution g ^ L + 1 \widehat{g}^{L+1} g L + 1 , we add it to the collection of identified graphs and repeat the procedure. If (13) is infeasible, we terminate and return g ^ 1 , … , g ^ L \widehat{g}^{1},\ldots,\widehat{g}^{L} g 1 , … , g L as the members of the equivalence class.
Remark 3. If the latent projected graphs of G ^ \widehat{\mathcal{G}} G onto S k \mathcal{S}_k S k are not already available, e.g., from the solution of (12) , they can be obtained via breadth-first-search (BFS). Specifically, for each node i ∈ S k i\in\mathcal{S}_k i ∈ S k , start a BFS traversing on the graph G ^ \widehat{\mathcal{G}} G . If a node j ∈ S k j\in\mathcal{S}_k j ∈ S k , j ≠ i j\ne i j = i is reached, then add edge i − j i-j i − j in the latent projected graph, and do not continue the BFS through j j j .
Computing summary statistics of an equivalence class
In § 2 , we described a general optimization procedure for computing various summary statistics of an equivalence class without enumerating its graphs. In this section, we describe how this optimization can be reformulated as a linear MIP.
As with the previous section, let h ^ ( k ) \widehat{h}^{(k)} h ( k ) encode the latent projections of G ^ \widehat{\mathcal{G}} G onto S k \mathcal{S}_k S k ; the binary variables h ^ ( k ) \widehat{h}^{(k)} h ( k ) are assumed to be known, otherwise they can be learned (see Remark 3).
Edge identifiability. For a pair of nodes ( i , j ) (i,j) ( i , j ) , we can verify whether this edge is present in every member of the equivalence class by solving the linear MIP:
min ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) g i j , subject-to: ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] , h ( k ) = h ^ ( k ) ∀ k ∈ [ K ] . (14) \begin{aligned}
\underset{(g,h,f,m)\in\mathcal{F}(\{\mathcal{S}_k\}_{k=1}^{K})}{\min}\quad& g_{ij},\\
\text{subject-to:}\quad& (g,h,f,m)\text{ satisfy the linear constraints in (10) and (11)}\ \forall k\in[K],\\
& h^{(k)}=\widehat{h}^{(k)}\quad\forall k\in[K]. \tag*{(14)}
\end{aligned} ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) min subject-to: g ij , ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] , h ( k ) = h ( k ) ∀ k ∈ [ K ] . (14)
A solution of one means that i i i and j j j are adjacent in every equivalence class member.
Logical edge implications. For two pairs of nodes ( i , j ) (i,j) ( i , j ) and ( a , b ) (a,b) ( a , b ) , we can verify whether the presence of edge ( a , b ) (a,b) ( a , b ) implies the presence of edge ( i , j ) (i,j) ( i , j ) for all equivalent members by solving the linear MIP (14) with the added constraint that g a , b = 1 g_{a,b}=1 g a , b = 1 . A solution of one means that the implication holds for every member of the equivalence class.
Separation statements. For disjoint variable sets A , B , C ⊆ V A,B,C \subseteq V A , B , C ⊆ V , we can verify whether in every graph in the equivalence class, C C C separates A A A and B B B by solving:
max ( g , h , f , m ) ∈ F ( { S k } k = 1 K + 1 ) ∑ i ∈ A ∑ j ∈ B h i j ( K + 1 ) \max_{(g,h,f,m)\in\mathcal{F}(\{S_k\}_{k=1}^{K+1})} \sum_{i\in A}\sum_{j\in B} h_{ij}^{(K+1)} ( g , h , f , m ) ∈ F ({ S k } k = 1 K + 1 ) max i ∈ A ∑ j ∈ B ∑ h ij ( K + 1 )
subject to: ( g , h , f , m ) (g,h,f,m) ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K + 1 ] \forall k\in[K+1] ∀ k ∈ [ K + 1 ] ,
h b ( k ) = h ^ b ( k ) ∀ k ∈ [ K ] . h_b^{(k)}=\widehat{h}_b^{(k)} \qquad\forall k\in[K]. h b ( k ) = h b ( k ) ∀ k ∈ [ K ] .
Here, S K + 1 : = { A , B , C } S_{K+1}:=\{A,B,C\} S K + 1 := { A , B , C } . A value of zero means that C C C separates A A A and B B B in every equivalence class member. Under faithfulness (i.e., Assumption 1 ′ 1' 1 ′ ), we would have the additional interpretation that all graphs in the equivalence class specify the independence relationship X A ⊥ X B ∣ X C X_A \perp X_B \mid X_C X A ⊥ X B ∣ X C .
Bounds on graph attributes. To find the minimum number of edges in any graph in the equivalence class, we can solve the linear mixed-integer program (14) with the objective changed to ∑ 1 ≤ i < j ≤ p g i j \sum_{1\leq i<j\leq p}g_{ij} ∑ 1 ≤ i < j ≤ p g ij . The maximum number of edges would solve a similar problem, but with a maximization. To find a minimum degree of a node i i i among all equivalence class members, we can solve the linear MIP (14) with the objective changed to ∑ j : 1 ≤ j < i g j i + ∑ j : i < j ≤ p g i j \sum_{j:1\leq j<i}g_{ji}+\sum_{j:i<j\leq p}g_{ij} ∑ j : 1 ≤ j < i g j i + ∑ j : i < j ≤ p g ij . As before, the maximum degree of a node swaps minimization with maximization.
Coordinate descent solvers for increased scalability
The mixed-integer formulations above provide exact approaches to estimator (4), but may become computationally demanding as the number of nodes increases. We therefore also develop a coordinate-descent heuristic. In our experiments, its solution is supplied as a warm start to the mixed-integer solver, which is then run with a fixed time budget to improve the solution or certify its optimality.
For a graph G G G on V V V , let F ( G ) F(G) F ( G ) denote its objective value in (4), and let G ( i , j ) G^{(i,j)} G ( i , j ) denote the graph obtained by flipping the adjacency of nodes i i i and j j j , namely, replacing g i j g_{ij} g ij with 1 − g i j 1-g_{ij} 1 − g ij . Algorithm 1 repeatedly scans the node pairs and accepts objective-improving flips. Since each accepted update strictly decreases the objective and there are finitely many graphs, the procedure terminates at a graph admitting no improving single-edge flip.
Table 1.
Evaluating F ( G ) F(G) F ( G ) first requires computing the latent projections, which can be obtained efficiently using BFS (see Remark 3). For Examples 2–6, the continuous parameters can then be optimized by solving convex programs. When the loss decouples across nodes, as in (6), only the local scores of nodes whose projected neighborhoods change need to be recomputed.
For Example 7 with loss (7), we restrict the global graph to be chordal by setting F ( G ) = + ∞ F(G)=+\infty F ( G ) = + ∞ otherwise. Chordality of a graph G G G can be checked in O ( p + ∣ E ( G ) ∣ ) O(p+|E(G)|) O ( p + ∣ E ( G ) ∣ ) time ((Tarjan & Yannakakis 1984)); nonchordal proposals are rejected before evaluating the remaining objective. Latent projections of chordal graphs remain chordal. Thus, for each projected graph G ~ \widetilde{\mathcal{G}} G , the minimized loss is
min θ ( k ) ∈ Θ k ( G ~ ) ℓ k ( θ ( k ) ; D k ) = ∑ C ∈ C max ( G ~ ) H ^ ( X C ) − ∑ M ∈ M ( G ~ ) H ^ ( X M ) . \min_{\theta^{(k)}\in\Theta_k(\widetilde{\mathcal{G}})} \ell_k(\theta^{(k)};D_k)=\sum_{C\in\mathcal{C}_{\max}(\widetilde{\mathcal{G}})}\widehat{H}(X_C)-\sum_{M\in\mathcal{M}(\widetilde{\mathcal{G}})}\widehat{H}(X_M). θ ( k ) ∈ Θ k ( G ) min ℓ k ( θ ( k ) ; D k ) = C ∈ C m a x ( G ) ∑ H ( X C ) − M ∈ M ( G ) ∑ H ( X M ) .
where C max ( G ~ ) \mathcal{C}_{\max}(\widetilde{\mathcal{G}}) C m a x ( G ) contains the maximal cliques of G ~ \widetilde{\mathcal{G}} G , and M ( G ~ ) \mathcal{M}(\widetilde{\mathcal{G}}) M ( G ) is the multiset of their intersections along the edges of a junction tree. A junction tree connects the maximal cliques so that, for every variable, the cliques containing that variable form a connected subtree. Here, H ^ ( X A ) = − ∑ x A P ^ ( k ) ( x A ) log ( P ^ ( k ) ( x A ) ) \widehat{H}(X_A)=-\sum_{x_A}\widehat{P}^{(k)}(x_A)\log(\widehat{P}^{(k)}(x_A)) H ( X A ) = − ∑ x A P ( k ) ( x A ) log ( P ( k ) ( x A )) denotes the empirical entropy of X A X_A X A . Both the maximal cliques and a junction tree can be computed in polynomial time for chordal graphs (Tarjan & Yannakakis 1984), allowing efficient evaluation of the loss when the maximal cliques are not too large. Although one global edge flip may change multiple projected edges, entropy terms for unchanged variable subsets can be reused. Evaluation is efficient when the resulting cliques are small. The space of chordal graphs on V V V is connected under chordality-preserving single-edge flips (Giudici & Green 1999).
For loss (8), the minimized loss is
min θ ( k ) ∈ Θ k ( G ~ ) ℓ ( θ ( k ) ; D k ) = ∑ i ∈ S k H ^ ( X i ∣ X N ( i , G ~ ) ) \min_{\theta^{(k)}\in\Theta_k(\widetilde{\mathcal{G}})}\ell(\theta^{(k)};D_k)=\sum_{i\in S_k}\widehat{H}(X_i\mid X_{N(i,\widetilde{\mathcal{G}})}) θ ( k ) ∈ Θ k ( G ) min ℓ ( θ ( k ) ; D k ) = i ∈ S k ∑ H ( X i ∣ X N ( i , G ) )
where H ^ ( X i ∣ X A ) = H ^ ( X { i } ∪ A ) − H ^ ( X A ) \widehat{H}(X_i\mid X_A)=\widehat{H}(X_{\{i\}\cup A})-\widehat{H}(X_A) H ( X i ∣ X A ) = H ( X { i } ∪ A ) − H ( X A ) is the empirical conditional entropy. Both this minimized loss and its dimension penalty decouple across nodes. Consequently, as with loss (6), only contributions from nodes whose projected neighborhoods change need to be recomputed. Computation is efficient when these neighborhoods are small.
Remark 4. The initial graph and the ordering of pairs in O \mathcal{O} O determine the initialization of the algorithm. As each run of coordinate descent is relatively fast, we recommend running the algorithm with several different initializations and selecting the solution with the lowest objective value. In our simulations and real-data experiments, we consider two initial graphs: the empty graph and coordinate descent solution of (4) with W 2 = [ K ] \mathcal{W}_2=[K] W 2 = [ K ] , obtained by first estimating a local graph separately for each source. For this preliminary coordinate descent procedure, we initialize at the empty graph and use the canonical ordering O \mathcal{O} O , in which all pairs involving node 1 are updated first, followed by those involving node 2, and so on. For the main procedure, we consider both the canonical ordering and a random ordering of the pairs in O \mathcal{O} O .
Theoretical Guarantees
Setup and definitions
We suppose all sources provide data, i.e. ∣ W 1 ∣ = K |\mathcal{W}_1|=K ∣ W 1 ∣ = K and W 2 = ∅ \mathcal{W}_2=\varnothing W 2 = ∅ . The data D k D_k D k in each source k k k are assumed to be independently sampled from a zero-mean multivariate Gaussian distribution over the observed variable subset S k S_k S k . We denote the covariance matrix of this marginal distribution by Σ k ⋆ \Sigma_k^\star Σ k ⋆ . Motivated by both computational and statistical considerations (see § 3.3 and § 4.2 ), we use the loss in (6) for learning a global graph from this data.
We restrict the class of underlying graphs by controlling their maximum degree and the complexity of their latent projections. Specifically, we assume that the maximum degree is at most r max , n r_{\max,n} r m a x , n and that, for every source k k k , each connected component of G [ V ∖ S k ] \mathcal{G}[V\setminus S_k] G [ V ∖ S k ] has at most b n b_n b n neighbors in S k S_k S k . We denote by G \mathbb{G} G the resulting class of global graphs and restrict the search in estimator (4) to G \mathbb{G} G . These conditions imply that, for every G ∈ G \mathcal{G}\in\mathbb{G} G ∈ G , the maximum degree of each source-specific latent projection π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) is at most d n : = r max , n ( b n − 1 ) d_n:=r_{\max,n}(b_n-1) d n := r m a x , n ( b n − 1 ) . We allow both r max , n r_{\max,n} r m a x , n and b n b_n b n to grow with the sample size and, for concreteness, take r max , n r_{\max,n} r m a x , n and b n b_n b n so that d n ≤ min { C ^ ( min k n k / log ( p ) ) 1 / 4 , p / 2 } d_n\leq\min\{\widehat{C}(\min_k n_k/\log(p))^{1/4},p/2\} d n ≤ min { C ( min k n k / log ( p ) ) 1/4 , p /2 } . We assume that G ⋆ ∈ G \mathcal{G}^\star\in\mathbb{G} G ⋆ ∈ G .
For every G ∈ G \mathcal{G}\in\mathbb{G} G ∈ G , k ∈ [ K ] k\in[K] k ∈ [ K ] , we define the population loss
L ( G ) : = ∑ k ∈ [ K ] ∑ j ∈ S k ω k L k j ( G ) with L k j ( G ) : = min β , support ( β ) ⊆ { j } ∪ N ( j , π S k ( G ) ) , β j = 1 β T Σ k ⋆ β . \mathcal{L}(\mathcal{G}):=\sum_{k\in[K]}\sum_{j\in S_k}\omega_k\mathcal{L}_{kj}(\mathcal{G})\quad\text{with}\quad\mathcal{L}_{kj}(\mathcal{G}):=\min_{\substack{\beta,\operatorname{support}(\beta)\subseteq\{j\}\cup N(j,\pi_{S_k}(\mathcal{G})),\\ \beta_j=1}}\beta^\mathsf{T}\Sigma_k^\star\beta. L ( G ) := k ∈ [ K ] ∑ j ∈ S k ∑ ω k L k j ( G ) with L k j ( G ) := β , support ( β ) ⊆ { j } ∪ N ( j , π S k ( G )) , β j = 1 min β T Σ k ⋆ β .
Here, N ( j , G ) N(j,\mathcal{G}) N ( j , G ) denotes the nodes adjacent to node j j j in the graph G \mathcal{G} G . Minimizing L ( G ) \mathcal{L}(\mathcal{G}) L ( G ) over G ∈ G \mathcal{G}\in\mathbb{G} G ∈ G is the population analogue of the estimator (4). By definition, L k j ( G ) ≥ L k j ( G ⋆ ) \mathcal{L}_{kj}(\mathcal{G})\geq\mathcal{L}_{kj}(\mathcal{G}^\star) L k j ( G ) ≥ L k j ( G ⋆ ) for every G ∈ G \mathcal{G}\in\mathbb{G} G ∈ G and k ∈ [ K ] k\in[K] k ∈ [ K ] , j ∈ S k j\in S_k j ∈ S k . Thus, L ( G ) ≥ L ( G ⋆ ) \mathcal{L}(\mathcal{G}) \ge\mathcal{L}(\mathcal{G}^{\star}) L ( G ) ≥ L ( G ⋆ ) . Define:
A − ( G , G ⋆ ) : = { ( k , j ) : N ( j , π S k ( G ⋆ ) ) ⊈ N ( j , π S k ( G ) ) } . \mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) := \{(k,j) : N(j,\pi_{S_k}(\mathcal{G}^{\star})) \not\subseteq N(j,\pi_{S_k}(\mathcal{G}))\}. A − ( G , G ⋆ ) := {( k , j ) : N ( j , π S k ( G ⋆ )) ⊆ N ( j , π S k ( G ))} .
Thus, A − ( G , G ⋆ ) \mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) A − ( G , G ⋆ ) consists of source–node pairs for which the projected graph of G \mathcal{G} G omits at least one neighbor of j j j present in the projected graph of G ⋆ \mathcal{G}^{\star} G ⋆ .
We next define two population combinatorial quantities that characterize the difficulty of distinguishing the true global graph from competing graphs. The first measures the smallest average population loss incurred by a graph that omits true neighbors in more than r r r source/node pairs:
Γ − ( r ) : = inf G ∈ G : ∣ A − ( G , G ⋆ ) ∣ ≥ r L ( G ) − L ( G ⋆ ) ∣ A − ( G , G ⋆ ) ∣ . (15) \Gamma^{-}(r) := \inf_{\mathcal{G}\in\mathbb{G}:|\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})|\ge r}\frac{\mathcal{L}(\mathcal{G})-\mathcal{L}(\mathcal{G}^{\star})}{|\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})|}. \tag*{(15)} Γ − ( r ) := G ∈ G : ∣ A − ( G , G ⋆ ) ∣ ≥ r inf ∣ A − ( G , G ⋆ ) ∣ L ( G ) − L ( G ⋆ ) . (15)
We use the convention inf ∅ = + ∞ \inf\varnothing=+\infty inf ∅ = + ∞ . The second quantity characterizes the difficulty of recovering a particular source/node neighborhood after restricting attention to graphs that are sufficiently close to G ⋆ \mathcal{G}^{\star} G ⋆ . For a localization radius q ≥ 0 q\ge0 q ≥ 0 , define
δ k j ( q ) : = inf G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q N ( j , π S k ( G ⋆ ) ) ⊈ N ( j , π S k ( G ) ) L ( G ) − L ( G ⋆ ) . (16) \delta_{kj}(q) := \inf_{\substack{\mathcal{G}\in\mathbb{G},|\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})|\le q\\N(j,\pi_{S_k}(\mathcal{G}^{\star}))\not\subseteq N(j,\pi_{S_k}(\mathcal{G}))}}\mathcal{L}(\mathcal{G})-\mathcal{L}(\mathcal{G}^{\star}). \tag*{(16)} δ k j ( q ) := G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q N ( j , π S k ( G ⋆ )) ⊆ N ( j , π S k ( G )) inf L ( G ) − L ( G ⋆ ) . (16)
The quantity δ k j ( q ) \delta_{kj}(q) δ k j ( q ) is the smallest population loss incurred by any graph within this localized class that omits at least one true neighbor of node j j j in source k k k . Larger values of δ k j ( q ) \delta_{kj}(q) δ k j ( q ) indicate a greater separation in population loss between G ⋆ \mathcal{G}^{\star} G ⋆ and competing graphs that fail to recover all true neighbors of node j j j in source k k k . Notice that δ k j ( q ) \delta_{kj}(q) δ k j ( q ) is a decreasing function of q q q .
Remark 5. We emphasize the global nature of the quantity δ k j ( q ) \delta_{kj}(q) δ k j ( q ) , even though it is defined for a particular source and node. In particular, if N ( j , π S k ( G ⋆ ) ) ⊈ N ( j , π S k ( G ) ) N(j,\pi_{S_k}(\mathcal{G}^{\star}))\not\subseteq N(j,\pi_{S_k}(\mathcal{G})) N ( j , π S k ( G ⋆ )) ⊆ N ( j , π S k ( G )) , then A − ( G , G ⋆ ) \mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) A − ( G , G ⋆ ) necessarily contains the pair ( k , j ) (k,j) ( k , j ) . However, it may also contain other pairs because, due to the global dependence structure induced by latent projections, omitting a true neighbor of node j j j in one source can trigger the omission of true neighbors in other source–node pairs.
The following stylized example illustrates the phenomena described above. Suppose G ⋆ \mathcal{G}^{\star} G ⋆ contains m m m internally vertex-disjoint paths i − h ℓ − j i-h_{\ell}-j i − h ℓ − j , ℓ = 1 , … , m \ell=1,\ldots,m ℓ = 1 , … , m , together with an isolated node z z z . Let source 1 observe only { i , j } \{i,j\} { i , j } and source 2 observe all variables except z z z . Then ( i , j ) (i,j) ( i , j ) is present in the latent projection for source 1. If a competing graph G \mathcal{G} G omits this projected edge, then for every ℓ \ell ℓ , at least one of the true source-2 edges ( i , h ℓ ) (i,h_{\ell}) ( i , h ℓ ) or ( j , h ℓ ) (j,h_{\ell}) ( j , h ℓ ) must also be omitted; otherwise, G \mathcal{G} G has a path from i i i to j j j . Hence ( 2 , h ℓ ) ∈ A − ( G , G ⋆ ) (2,h_{\ell})\in\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) ( 2 , h ℓ ) ∈ A − ( G , G ⋆ ) for all ℓ = 1 , 2 , … , m \ell=1,2,\ldots,m ℓ = 1 , 2 , … , m , and together with the omission at ( 1 , i ) (1,i) ( 1 , i ) and ( 1 , j ) (1,j) ( 1 , j ) , this yields ∣ A − ( G , G ⋆ ) ∣ ≥ m + 2 |\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})|\ge m+2 ∣ A − ( G , G ⋆ ) ∣ ≥ m + 2 .
Remark 6. Note that:
δ k j ( q ) = inf G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q N ( j , π S k ( G ⋆ ) ) ⊈ N ( j , π S k ( G ) ) ∑ ( l , m ) ∈ A − ( G , G ⋆ ) ω l { L l m ( G ) − L l m ( G ⋆ ) } , \delta_{kj}(q)=\inf_{\substack{\mathcal{G}\in\mathbb{G},|\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})|\le q\\N(j,\pi_{S_k}(\mathcal{G}^{\star}))\not\subseteq N(j,\pi_{S_k}(\mathcal{G}))}}\sum_{(l,m)\in\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star})}\omega_l\{\mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(\mathcal{G}^{\star})\}, δ k j ( q ) = G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q N ( j , π S k ( G ⋆ )) ⊆ N ( j , π S k ( G )) inf ( l , m ) ∈ A − ( G , G ⋆ ) ∑ ω l { L l m ( G ) − L l m ( G ⋆ )} ,
where by definition, L l m ( G ) − L l m ( G ⋆ ) > 0 \mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(\mathcal{G}^{\star})>0 L l m ( G ) − L l m ( G ⋆ ) > 0 for every ( l , m ) ∈ A − ( G , G ⋆ ) (l,m)\in\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) ( l , m ) ∈ A − ( G , G ⋆ ) . To better understand how small the gap L l m ( G ) − L l m ( G ⋆ ) \mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(\mathcal{G}^{\star}) L l m ( G ) − L l m ( G ⋆ ) can be, let T ⋆ = N ( m , π S l ( G ⋆ ) ) T^{\star}=N(m,\pi_{S_l}(\mathcal{G}^{\star})) T ⋆ = N ( m , π S l ( G ⋆ )) and T : = N ( m , π S l ( G ) ) T:=N(m,\pi_{S_l}(\mathcal{G})) T := N ( m , π S l ( G )) . Define β ⋆ : = ( [ Σ l ⋆ ] T ⋆ , T ⋆ ) − 1 [ Σ l ⋆ ] T ⋆ , m \beta^{\star}:=(\left[\Sigma_l^{\star}\right]_{T^{\star},T^{\star}})^{-1}\left[\Sigma_l^{\star}\right]_{T^{\star},m} β ⋆ := ( [ Σ l ⋆ ] T ⋆ , T ⋆ ) − 1 [ Σ l ⋆ ] T ⋆ , m which encode the strength of true edges adjacent to node m m m in source l l l . Then, a straightforward calculation shows
L l m ( G ) − L l m ( G ⋆ ) = [ β ⋆ ] M T [ Σ l ⋆ ] M ∣ T [ β ⋆ ] M , \mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(\mathcal{G}^{\star})=[\beta^{\star}]_{M}^{\mathsf{T}}[\Sigma_l^{\star}]_{M\mid T}[\beta^{\star}]_{M}, L l m ( G ) − L l m ( G ⋆ ) = [ β ⋆ ] M T [ Σ l ⋆ ] M ∣ T [ β ⋆ ] M ,
where M = T ⋆ ∖ T M=T^{\star}\setminus T M = T ⋆ ∖ T , and [ Σ l ⋆ ] M ∣ T [\Sigma_l^{\star}]_{M\mid T} [ Σ l ⋆ ] M ∣ T is the conditional covariance of the variables in M M M given those in T T T in source l l l . Thus, δ k j ( q ) \delta_{kj}(q) δ k j ( q ) aggregates the signal strengths of all omissions that must accompany an error at node j j j in source k k k , highlighting the benefit of integrating information across sources.
Remark 7. Consider a source-specific neighborhood selection estimator for recovering the neighborhood of node j j j in source k k k . Let ℓ k j ( T ) \ell_{kj}(T) ℓ k j ( T ) denote the population loss obtained by regressing node j j j on a candidate neighborhood T ⊆ S k ∖ { j } T\subseteq S_k\setminus\{j\} T ⊆ S k ∖ { j } . The corresponding population separation is
δ k j l o c a l : = inf T ⊆ S k ∖ { j } N ( j , π S k ( G ⋆ ) ) ⊈ T ℓ k j ( T ) − ℓ k j ( N ( j , π S k ( G ⋆ ) ) ) . \delta_{kj}^{\mathrm{local}}:=\inf_{\substack{T\subseteq S_k\setminus\{j\}\\N(j,\pi_{S_k}(\mathcal{G}^{\star}))\not\subseteq T}}\ell_{kj}(T)-\ell_{kj}(N(j,\pi_{S_k}(\mathcal{G}^{\star}))). δ k j local := T ⊆ S k ∖ { j } N ( j , π S k ( G ⋆ )) ⊆ T inf ℓ k j ( T ) − ℓ k j ( N ( j , π S k ( G ⋆ ))) .
Unlike δ k j ( q ) \delta_{kj}(q) δ k j ( q ) , this quantity depends only on the population neighborhood-selection problem for node j j j in source k k k : it does not involve the neighborhoods of any other nodes or the distributions in any other sources. In contrast, δ k j ( q ) \delta_{kj}(q) δ k j ( q ) is defined through a common global graph and therefore incorporates the cross-source constraints induced by its latent projections.
Theoretical results
Our results rely on a few additional notations. For any disjoint sets A , B ⊆ S k A, B \subseteq S_k A , B ⊆ S k , let
[ Σ k ⋆ ] A ∣ B : = [ Σ k ⋆ ] A , A − [ Σ k ⋆ ] A , B ( [ Σ k ⋆ ] B , B ) − 1 [ Σ k ⋆ ] B , A . [\Sigma_k^\star]_{A|B}:=[\Sigma_k^\star]_{A,A}-[\Sigma_k^\star]_{A,B}([\Sigma_k^\star]_{B,B})^{-1}[\Sigma_k^\star]_{B,A}. [ Σ k ⋆ ] A ∣ B := [ Σ k ⋆ ] A , A − [ Σ k ⋆ ] A , B ([ Σ k ⋆ ] B , B ) − 1 [ Σ k ⋆ ] B , A .
Define:
κ min : = min k ∈ [ K ] A ⊆ S k , ∣ A ∣ ≤ 2 d n B ⊆ S k , ∣ B ∣ ≤ 2 d n , A ∖ B ≠ ∅ σ min ( [ Σ k ⋆ ] A ∣ B ) , κ max : = max k ∈ [ K ] A ⊆ S k , ∣ A ∣ ≤ 2 d n σ max ( [ Σ k ⋆ ] A , A ) . \kappa_{\min}:=\min_{\substack{k\in[K]\\ A\subseteq S_k,\lvert A\rvert\leq2d_n\\ B\subseteq S_k,\lvert B\rvert\leq2d_n,A\setminus B\neq\varnothing}}\sigma_{\min}([\Sigma_k^\star]_{A|B}),\qquad
\kappa_{\max}:=\max_{\substack{k\in[K]\\ A\subseteq S_k,\lvert A\rvert\leq2d_n}}\sigma_{\max}([\Sigma_k^\star]_{A,A}). κ m i n := k ∈ [ K ] A ⊆ S k , ∣ A ∣ ≤ 2 d n B ⊆ S k , ∣ B ∣ ≤ 2 d n , A ∖ B = ∅ min σ m i n ([ Σ k ⋆ ] A ∣ B ) , κ m a x := k ∈ [ K ] A ⊆ S k , ∣ A ∣ ≤ 2 d n max σ m a x ([ Σ k ⋆ ] A , A ) .
Here, for a positive definite matrix M M M , σ min ( M ) \sigma_{\min}(M) σ m i n ( M ) and σ max ( M ) \sigma_{\max}(M) σ m a x ( M ) represent its smallest and largest singular values, respectively. Let C ˉ : = 4 + 8 κ max κ min + 4 κ max 2 κ min 2 \bar{C}:=4+\frac{8\kappa_{\max}}{\kappa_{\min}}+\frac{4\kappa_{\max}^{2}}{\kappa_{\min}^{2}} C ˉ := 4 + κ m i n 8 κ m a x + κ m i n 2 4 κ m a x 2 . Define
t k : = κ max 256 ( d n + 1 ) log ( 2 K p ) n k . t_k:=\kappa_{\max}\sqrt{\frac{256(d_n+1)\log(2Kp)}{n_k}}. t k := κ m a x n k 256 ( d n + 1 ) log ( 2 K p ) .
Let C ≥ 1 C\geq1 C ≥ 1 be any constant satisfying:
max k ∈ [ K ] ω k t k min k ∈ [ K ] ω k t k ≤ C . \frac{\max_{k\in[K]}\omega_k t_k}{\min_{k\in[K]}\omega_k t_k}\leq C. min k ∈ [ K ] ω k t k max k ∈ [ K ] ω k t k ≤ C .
Define
q min : = min { r ∈ N : Γ − ( r ) > ( d n + 1 / 2 ) max k ∈ [ K ] ω k λ k ( 1 + C ( 2 d n + 1 ) ) } . q_{\min}:=\min\left\{r\in\mathbb{N}:\Gamma^{-}(r)>(d_n+1/2)\max_{k\in[K]}\omega_k\lambda_k\left(1+C(2d_n+1)\right)\right\}. q m i n := min { r ∈ N : Γ − ( r ) > ( d n + 1/2 ) k ∈ [ K ] max ω k λ k ( 1 + C ( 2 d n + 1 ) ) } .
We then have the following result, with proof in Appendix A.3.
Theorem 11. For any k ∈ [ K ] k\in[K] k ∈ [ K ] , define δ k , min : = min i ∈ S k δ k i ( q min ) \delta_{k,\min}:=\min_{i\in S_k}\delta_{ki}(q_{\min}) δ k , m i n := min i ∈ S k δ k i ( q m i n ) . Suppose for every k ∈ [ K ] k\in[K] k ∈ [ K ] ,
n k ≥ 1024 ( d n + 1 ) κ max 2 κ min 2 log ( 2 K p ) , n_k\geq\frac{1024(d_n+1)\kappa_{\max}^{2}}{\kappa_{\min}^{2}}\log(2Kp), n k ≥ κ m i n 2 1024 ( d n + 1 ) κ m a x 2 log ( 2 K p ) , n k ≥ 4096 C 2 C ˉ 2 q min 2 ω k 2 κ max 2 ( d n + 1 ) 3 δ k , min 2 log ( 2 K p ) . n_k\geq\frac{4096C^{2}\bar{C}^{2}q_{\min}^{2}\omega_k^{2}\kappa_{\max}^{2}(d_n+1)^{3}}{\delta_{k,\min}^{2}}\log(2Kp). n k ≥ δ k , m i n 2 4096 C 2 C ˉ 2 q m i n 2 ω k 2 κ m a x 2 ( d n + 1 ) 3 log ( 2 K p ) . Suppose for every k ∈ [ K ] k\in[K] k ∈ [ K ] , λ k \lambda_k λ k is chosen as to satisfy:
2 C C ˉ t k ≤ λ k ≤ δ k , min 2 C q min ( d n + 1 / 2 ) ω k , 2C\bar{C}t_k\leq\lambda_k\leq\frac{\delta_{k,\min}}{2Cq_{\min}(d_n+1/2)\omega_k}, 2 C C ˉ t k ≤ λ k ≤ 2 C q m i n ( d n + 1/2 ) ω k δ k , m i n , while satisfying max k ∈ [ K ] ω k λ k / min k ∈ [ K ] ω k λ k ≤ C \max_{k\in[K]}\omega_k\lambda_k/\min_{k\in[K]}\omega_k\lambda_k\leq C max k ∈ [ K ] ω k λ k / min k ∈ [ K ] ω k λ k ≤ C . Then, with probability greater than 1 − 1 / p 1-1/p 1 − 1/ p , G ^ ∈ E C ( G ⋆ , { S k } k = 1 K ) \widehat{G}\in\mathrm{EC}(G^\star,\{S_k\}_{k=1}^{K}) G ∈ EC ( G ⋆ , { S k } k = 1 K ) .
Theorem 11 highlights four main drivers of the sample size requirement. First, the logarithmic factor log ( K p ) \log(Kp) log ( K p ) is the expected high-dimensional dependence arising from uniform control over all source-node pairs. Second, d n d_n d n controls the local complexity of the projected graphs. Larger projected neighborhoods make estimation harder and thus require a larger sample size. Third, the conditional number of the covariance matrices matters through κ max / κ min \kappa_{\max}/\kappa_{\min} κ m a x / κ m i n . Thus, poorly conditioned covariance matrices require more samples. Finally, and most importantly, the recovery difficulty is governed by the ratio q min / δ k , min q_{\min}/\delta_{k,\min} q m i n / δ k , m i n . Here, q min q_{\min} q m i n measures how large a neighborhood of competing graphs must be considered after localization, while δ k , min \delta_{k,\min} δ k , m i n measures the smallest population separation from a graph that makes an error in some source. Larger δ k , min \delta_{k,\min} δ k , m i n reduces the required sample size, while larger q min q_{\min} q m i n increases it.
The recovery guarantee in Theorem 11 is expressed in terms of the population separation quantity δ k , min \delta_{k,\min} δ k , m i n . We next provide sufficient conditions that relate this abstract quantity to the strengths of the true local regression coefficients. Let T k j ⋆ : = N ( j , π S k ( G ⋆ ) ) T_{kj}^\star:=N(j,\pi_{S_k}(G^\star)) T k j ⋆ := N ( j , π S k ( G ⋆ )) . Define β k j ⋆ : = ( [ Σ k ⋆ ] T k j ⋆ , T k j ⋆ ) − 1 [ Σ k ⋆ ] T k j ⋆ , j \beta_{kj}^\star:=([\Sigma_k^\star]_{T_{kj}^\star,T_{kj}^\star})^{-1}[\Sigma_k^\star]_{T_{kj}^\star,j} β k j ⋆ := ([ Σ k ⋆ ] T k j ⋆ , T k j ⋆ ) − 1 [ Σ k ⋆ ] T k j ⋆ , j and define β k j i ⋆ : = e i ⊤ β k j ⋆ \beta_{kji}^\star:=e_i^\top\beta_{kj}^\star β k j i ⋆ := e i ⊤ β k j ⋆ with e i e_i e i denoting a standard basis element. Suppose W ⊆ { ( k , j ) : k ∈ [ K ] , j ∈ S k } \mathcal{W}\subseteq\{(k,j):k\in[K],j\in S_k\} W ⊆ {( k , j ) : k ∈ [ K ] , j ∈ S k } is the set of weak source-node pairs and let
β k , min : = min ( i , j ) ∈ E ( π S k ( G ⋆ ) ) , ( k , j ) ∉ W ∣ β k j i ⋆ ∣ . \beta_{k,\min}:=\min_{(i,j)\in E(\pi_{S_k}(G^\star)),(k,j)\notin\mathcal{W}}\lvert\beta_{kji}^\star\rvert. β k , m i n := ( i , j ) ∈ E ( π S k ( G ⋆ )) , ( k , j ) ∈ / W min ∣ β k j i ⋆ ∣ .
Thus, outside W W W , every true edge in source k k k has strength at least β k , min \beta_{k,\min} β k , m i n . The next proposition shows that if the strong signals dominate the stochastic error level, then q min q_{\min} q m i n can be controlled explicitly, and δ k , min \delta_{k,\min} δ k , m i n is lower bounded by the cumulative contribution of the strong omissions that necessarily accompany an error in source k k k . The proof is in Appendix A.4.
Proposition 12. If
κ min min k ∈ [ K ] { ω k β k , min 2 } > 2 ( d n + 1 / 2 ) max k ∈ [ K ] ω k λ k , \kappa_{\min}\min_{k\in[K]}\{\omega_k\beta_{k,\min}^{2}\}>2(d_n+1/2)\max_{k\in[K]}\omega_k\lambda_k, κ m i n k ∈ [ K ] min { ω k β k , m i n 2 } > 2 ( d n + 1/2 ) k ∈ [ K ] max ω k λ k , then:
δ k , min ≥ min j ∈ S k inf G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q 0 N ( j , π S k ⋆ ) ⊈ N ( j , π S k ( G ) ) ∑ ( l , m ) ∈ A − ( G , G ⋆ ) ( l , m ) ∉ W κ min ω l β l , min 2 . \delta_{k,\min}\geq\min_{j\in S_k}\inf_{\substack{G\in\mathcal{G},\,|A^{-}(G,G^\star)|\leq q_0\\N(j,\pi_{S_k}^\star)\not\subseteq N(j,\pi_{S_k}(G))}}\sum_{\substack{(l,m)\in A^{-}(G,G^\star)\\(l,m)\notin W}}\kappa_{\min}\omega_l\beta_{l,\min}^{2}. δ k , m i n ≥ j ∈ S k min G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q 0 N ( j , π S k ⋆ ) ⊆ N ( j , π S k ( G )) inf ( l , m ) ∈ A − ( G , G ⋆ ) ( l , m ) ∈ / W ∑ κ m i n ω l β l , m i n 2 . where q 0 : = ( 2 ∣ W ∣ + 1 ) ( 1 + C ( 2 d n + 1 ) ) q_0 := (2|W|+1)(1+C(2d_n+1)) q 0 := ( 2∣ W ∣ + 1 ) ( 1 + C ( 2 d n + 1 )) .
The bound makes explicit the benefit of integration: δ k , min \delta_{k,\min} δ k , m i n need not be determined solely by the weakest signal at the target source. If an error there forces additional omissions elsewhere, the corresponding strong signals also contribute to the separation. In particular, a locally weak source-node pair can still be recoverable when the shared global graph structures link that error to sufficiently strong signals in other sources.
Synthetic Experiments
Data generating process
7.1. Data generating process. We generate G ⋆ G^\star G ⋆ from an Erdős–Rényi model with P { ( i , j ) ∈ E ⋆ } = d p − 1 \mathbb{P}\{(i,j)\in E^\star\}=\frac{d}{p-1} P {( i , j ) ∈ E ⋆ } = p − 1 d , where d d d is the expected node degree. Conditional on G ⋆ G^\star G ⋆ , each source ℓ \ell ℓ has a Gaussian distribution with precision matrix Ω ( k ) \Omega^{(k)} Ω ( k ) . The off-diagonal support of every Ω ( k ) \Omega^{(k)} Ω ( k ) is E ⋆ E^\star E ⋆ . For each ( i , j ) ∈ E ⋆ (i,j)\in E^\star ( i , j ) ∈ E ⋆ , independently across edges and sources, we draw U i j ( ℓ ) ∼ Unif ( 0.5 , 0.75 ) U_{ij}^{(\ell)}\sim\operatorname{Unif}(0.5,0.75) U ij ( ℓ ) ∼ Unif ( 0.5 , 0.75 ) and P ( ξ i j = 1 ) = P ( ξ i j = − 1 ) = 1 2 \mathbb{P}(\xi_{ij}=1)=\mathbb{P}(\xi_{ij}=-1)=\frac{1}{2} P ( ξ ij = 1 ) = P ( ξ ij = − 1 ) = 2 1 . We then set Ω i j ( k ) = Ω j i ( k ) = ξ i j ( k ) U i j ( k ) \Omega_{ij}^{(k)}=\Omega_{ji}^{(k)}=\xi_{ij}^{(k)}U_{ij}^{(k)} Ω ij ( k ) = Ω j i ( k ) = ξ ij ( k ) U ij ( k ) for ( i , j ) ∈ E ⋆ (i,j)\in E^\star ( i , j ) ∈ E ⋆ and set all other off-diagonal entries to zero. The diagonal entries are Ω i i ( k ) = 0.5 + ∑ j ≠ i ∣ Ω i j ( k ) ∣ \Omega_{ii}^{(k)}=0.5+\sum_{j\neq i}|\Omega_{ij}^{(k)}| Ω ii ( k ) = 0.5 + ∑ j = i ∣ Ω ij ( k ) ∣ . This makes Ω ( k ) \Omega^{(k)} Ω ( k ) strictly diagonally dominant and positive definite. The sources share the graph G ⋆ G^\star G ⋆ , while their edge weights and covariance matrices Σ ( k ) = ( Ω ( k ) ) − 1 \Sigma^{(k)}=(\Omega^{(k)})^{-1} Σ ( k ) = ( Ω ( k ) ) − 1 may differ.
Source k k k observes a subset S k ⊆ V S_k\subseteq V S k ⊆ V containing q = ( 1 − m ) p q=(1-m)p q = ( 1 − m ) p variables, where m m m is the missingness fraction. For a set T ⊆ V T\subseteq V T ⊆ V denote cc ( G ⋆ [ T ] ) \operatorname{cc}(G^\star[T]) cc ( G ⋆ [ T ]) as the collection of connected components with nodes in T T T . For a candidate set S ⊆ V S\subseteq V S ⊆ V and a connected component C ∈ cc ( G ⋆ [ V ∖ S ] ) C\in\operatorname{cc}(G^\star[V\setminus S]) C ∈ cc ( G ⋆ [ V ∖ S ]) , define the subset ∂ S ( C ) : = { i ∈ S : ( i , j ) ∈ E ⋆ for some j ∈ C } \partial_S(C):=\{i\in S:(i,j)\in E^\star\text{ for some }j\in C\} ∂ S ( C ) := { i ∈ S : ( i , j ) ∈ E ⋆ for some j ∈ C } . This subset collects vertices in S S S that are connected to some node in the connected component C C C . The collection of admissible observed sets is
H q ( G ⋆ , l ) : = { S ⊆ V : ∣ S ∣ = q , max C ∈ cc ( G ⋆ [ V ∖ S ] ) ∣ ∂ S ( C ) ∣ ≤ l } . \mathcal{H}_q(G^\star,l):=\left\{S\subseteq V:|S|=q,\max_{C\in\operatorname{cc}(G^\star[V\setminus S])}|\partial_S(C)|\leq l\right\}. H q ( G ⋆ , l ) := { S ⊆ V : ∣ S ∣ = q , C ∈ cc ( G ⋆ [ V ∖ S ]) max ∣ ∂ S ( C ) ∣ ≤ l } .
This restriction limits the edges introduced by marginalization: each connected component of unobserved vertices makes its observed boundary a clique on at most l l l vertices.
We generate each S k S_k S k using a Markov chain on H q ( G ⋆ , l ) \mathcal{H}_q(G^\star,l) H q ( G ⋆ , l ) . A randomized search first provides a feasible initial state S ( 0 ) S^{(0)} S ( 0 ) . At iteration t t t , the current state is S ( t ) S^{(t)} S ( t ) . With probability 0.05, the chain stays at S ( t ) S^{(t)} S ( t ) . Otherwise, it selects a radius r ∈ { 1 , … , min ( q , p − q ) } r\in\{1,\ldots,\min(q,p-q)\} r ∈ { 1 , … , min ( q , p − q )} . Conditional on making a proposal, radius one has probability 0.80, radius two has probability 0.15, and total probability 0.05 is distributed uniformly over the remaining radii. Given r r r , the chain samples r r r nodes uniformly from S ( t ) S^{(t)} S ( t ) and r r r nodes uniformly from V ∖ S ( t ) V\setminus S^{(t)} V ∖ S ( t ) . Denote these sets by A A A and B B B . The proposed state is S ′ = ( S ( t ) ∖ A ) ∪ B S'=(S^{(t)}\setminus A)\cup B S ′ = ( S ( t ) ∖ A ) ∪ B . If S ′ ∈ H q ( G ⋆ , l ) S'\in\mathcal{H}_q(G^\star,l) S ′ ∈ H q ( G ⋆ , l ) , the proposal is accepted and S ( t + 1 ) = S ′ S^{(t+1)}=S' S ( t + 1 ) = S ′ . Otherwise, the proposal is rejected and S ( t + 1 ) = S ( t ) S^{(t+1)}=S^{(t)} S ( t + 1 ) = S ( t ) . It is straightforward to show that this chain is reversible, irreducible, and aperiodic, and thus the procedure samples uniformly from H q ( G ⋆ , l ) \mathcal{H}_q(G^\star,l) H q ( G ⋆ , l ) . We run one chain for each source for 10,000 transitions and retain the terminal state as S k S_k S k . Given S k S_k S k , source k k k provides observations X 1 ( k ) , … , X n ( k ) ∼ i i d N q ( 0 , Σ S k , S k ( k ) ) X_1^{(k)},\ldots,X_n^{(k)}\mathrel{\overset{\mathrm{iid}}{\sim}}N_q(0,\Sigma_{S_k,S_k}^{(k)}) X 1 ( k ) , … , X n ( k ) ∼ iid N q ( 0 , Σ S k , S k ( k ) ) .
In the simulation settings we consider p ∈ { 10 , 25 , 50 } p\in\{10,25,50\} p ∈ { 10 , 25 , 50 } , K ∈ { 5 , 10 } K\in\{5,10\} K ∈ { 5 , 10 } , n ∈ { 100 , 500 , 1000 } n\in\{100,500,1000\} n ∈ { 100 , 500 , 1000 } , m ∈ { 0.2 , 0.4 } m\in\{0.2,0.4\} m ∈ { 0.2 , 0.4 } , and ( d , l ) ∈ { ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 3 ) } (d,l)\in\{(2,2),(2,3),(3,3)\} ( d , l ) ∈ {( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 3 )} , where d d d is the expected node degree and l l l is the maximum allowed boundary size in H q ( G ⋆ , l ) \mathcal{H}_q(G^\star,l) H q ( G ⋆ , l ) . Each setting contains 50 replications.
Performance evaluation
We evaluate the estimated global graph G ^ \widehat{G} G using the projected-SHD:
τ ( G ^ ) : = 1 K ∑ k = 1 K SHD ( π S k ( G ^ ) , π S k ( G ⋆ ) ) ⏟ projected-SHD . \tau(\widehat{G}) := \frac{1}{K} \sum_{k=1}^{K} \underbrace{\operatorname{SHD}\left(\pi_{S_k}(\widehat{G}),\pi_{S_k}(G^\star)\right)}_{\text{projected-SHD}}. τ ( G ) := K 1 k = 1 ∑ K projected-SHD SHD ( π S k ( G ) , π S k ( G ⋆ ) ) .
This metric measures how accurately the joint procedure recovers the marginal graphs. Notice that G ^ \widehat{G} G is in the population equivalence class, i.e., G ^ ∈ EC ( G ⋆ ) \widehat{G} \in\operatorname{EC}(G^\star) G ∈ EC ( G ⋆ ) , if and only if τ ( G ^ ) = 0 \tau(\widehat{G}) = 0 τ ( G ) = 0 . We say that the projection-equivalence class is recovered exactly when τ ( G ^ ) = 0 \tau(\widehat{G}) = 0 τ ( G ) = 0 .
We compare four procedures: (i) data-integrated coordinate descent where an approximate solution to (4) is obtained (see § 5 ); (ii) data-integrated MIP that solves (4) initialized with the coordinate descent solution and run until solution is found or the time limit of 300 seconds is reached; (iii) graph-integrated coordinate descent that first estimates a local graph for each source and then combines these local graphs by approximately solving (4) via coordinate descent; and (iv) separate-source baseline that does not combine the local graphs. For the separate-source baseline, projected-SHD is computed as K − 1 ∑ k = 1 K SHD ( G ^ S k ( k ) , π S k ( G ⋆ ) ) K^{-1}\sum_{k=1}^{K}\operatorname{SHD}(\widehat{G}_{S_k}^{(k)},\pi_{S_k}(G^\star)) K − 1 ∑ k = 1 K SHD ( G S k ( k ) , π S k ( G ⋆ )) , where G ^ S k ( k ) \widehat{G}_{S_k}^{(k)} G S k ( k ) denotes the estimated local graph for source k k k . Thus, a lower projected-SHD for any of our integration approaches (i)–(iii) than for the separate-source baseline indicates a benefit from integration.
For the two data-integrated procedures, we use the quadratic loss in (6) from Example 2, with the Bayesian Information Criterion (BIC)-based penalty λ 1 = ⋯ = λ K = log ( n ) / n \lambda_1 = \cdots= \lambda_K = \log(n)/n λ 1 = ⋯ = λ K = log ( n ) / n . For both graph integration and the separate-source baseline, source graphs are estimated by neighborhood selection (Meinshausen & Bühlmann 2006b). Specifically, in each source, every observed variable is regressed on all other observed variables using the lasso, with the regularization parameter selected by the BIC. An undirected edge is retained only when both corresponding directed regressions select it, corresponding to the AND rule. We also compared this estimator with neighborhood selection using the OR rule, with regularization parameters selected by cross-validation or stability-based tuning and either symmetrization rule, as well as graphical lasso with BIC or cross-validation. Figure 7 –Figure 9 in Appendix D compare the chosen estimator with an oracle-best alternative selected separately in each setting from the other seven procedures. Despite this retrospective advantage, the oracle alternative is usually less accurate than the neighborhood selection with the AND rule.
Figure 7. Projected SHD per source for neighborhood selection with BIC and the AND rule and the oracle-best alternative when d = 2 d = 2 d = 2 and ℓ = 2 \ell= 2 ℓ = 2 . The oracle alternative is selected separately in each simulation setting using its mean SHD across the 50 paired replications, and its identity is reported above each group of boxplots.
Figure 9. Projected SHD per source for neighborhood selection with BIC and the AND rule and the oracle-best alternative when d = 3 d = 3 d = 3 and l = 3 l = 3 l = 3 . The oracle alternative is selected separately in each simulation setting using its mean SHD across the 50 paired replications, and its identity is reported above each group of boxplots.
The exact MIP-based procedures were given a time limit of 300 seconds, measured after initialization. The coordinate descent procedures used to construct warm starts were not subject to this time limit and ran until their convergence criterion was satisfied or a maximum of 40 iterations (in our simulations they always converged within 40 iterations).
Results with data available from all sources
Figure 3 and Figure 4 present the results for ( d , l ) = ( 2 , 2 ) (d,l)=(2,2) ( d , l ) = ( 2 , 2 ) and ( 3 , 3 ) (3,3) ( 3 , 3 ) , respectively. Rows correspond to sample size, columns to the number of variables, and groups within each panel to combinations of source count and missingness. The boxplots summarize projected-SHD τ ( G ^ ) \tau(\widehat{G}) τ ( G ) across the 50 replications, with exact projection-equivalence-class recovery rates reported above them. Results for ( d , l ) = ( 2 , 3 ) (d,l)=(2,3) ( d , l ) = ( 2 , 3 ) appear in Figure 10 in Appendix D.
Figure 3. Projected-SHD for expected degree d = 2 d = 2 d = 2 and maximum boundary size l = 2 l = 2 l = 2 . Boxes summarize the 50 replications. Percentages at the top of each panel report exact recovery of the projection-equivalence class.
Figure 4. Projected-SHD for expected degree d = 3 d = 3 d = 3 and maximum boundary size l = 3 l = 3 l = 3 . Boxes summarize the 50 replications. Percentages at the top of each panel report exact recovery of the projection-equivalence class.
Figure 10. Projected SHD per source in the harder regime with expected degree d = 2 d = 2 d = 2 and maximum boundary size l = 3 l = 3 l = 3 . Boxes summarize the 50 replications. Percentages at the top of each panel report exact recovery of the projection-equivalence class.
The figures show a consistent ordering: the data-integrated solutions generally have the lowest τ ( G ^ ) \tau(\widehat{G}) τ ( G ) , followed by graph integration and then separate-source estimation. Among the two data-integrated approaches, the coordinate descent and MIP results are often nearly indistinguishable, in part because the coordinate descent solution initializes the MIP. Nevertheless, the MIP incumbent achieves lower projected-SHD in 55 of the 108 settings and ties coordinate descent in another 36; its exact recovery rate is higher in 37 settings and equal in 67. Both data-integrated solutions have lower projected-SHD than graph integration in all 108 settings and generally attain equal or higher exact recovery rates. The separate-source baseline also tends to exhibit greater variability, particularly for larger p p p , greater missingness, or greater structural complexity.
Increasing the sample size shifts the projected-SHD distributions toward zero in nearly every panel, with the largest gains generally occurring between n = 100 n=100 n = 100 and n = 500 n=500 n = 500 . For example, in Figure 3 , when p = 50 p=50 p = 50 , K = 10 K=10 K = 10 , and m = 0.2 m=0.2 m = 0.2 , exact recovery for both data-integrated solutions increases from 4% at n = 100 n=100 n = 100 to 100% at n = 500 n=500 n = 500 and remains at 100% at n = 1000 n=1000 n = 1000 . Over the same range, graph integration improves from 0% to 60% and then to 90%, whereas separate-source estimation remains at 0%. The same pattern appears in Figure 4 , although recovery is generally more difficult under ( d , l ) = ( 3 , 3 ) (d,l)=(3,3) ( d , l ) = ( 3 , 3 ) .
Within each panel, the effect of increasing the number of sources can be assessed by comparing the first and third groups at 20% missingness and the second and fourth groups at 40% missingness. Additional sources most consistently benefit the data-integrated solutions, with smaller gains for graph integration and, obviously, no benefit for separate-source estimation. For example, in Figure 3 , when n = 1000 n = 1000 n = 1000 , p = 50 p = 50 p = 50 , and m = 0.4 m = 0.4 m = 0.4 , exact recovery increases from 16% to 56% for coordinate descent, from 24% to 60% for the MIP incumbent, and from 8% to 18% for graph integration, while remaining at 0% for separate-source estimation. This improvement is notable because exact recovery becomes more stringent as the number of sources increases.
Increasing the missingness fraction from 20% to 40% substantially degrades recovery, as reflected by higher projected-SHD and lower exact recovery across panels. In Figure 4 , for example, when n = 1000 n = 1000 n = 1000 , p = 25 p = 25 p = 25 , and K = 10 K = 10 K = 10 , exact recovery decreases from 98% to 18% for coordinate descent, from 98% to 32% for the MIP incumbent, and from 20% to 0% for graph integration. Greater missingness both reduces the information available within each source and decreases the amount of overlap across sources.
Recovery also becomes more difficult as p p p increases, with projected-SHD shifting upward and becoming more variable across the columns of Figure 3 and Figure 4 . For example, in Figure 3 , with n = 1000 n = 1000 n = 1000 , K = 5 K = 5 K = 5 , and m = 0.4 m = 0.4 m = 0.4 , exact recovery for coordinate descent decreases from 76% at p = 10 p = 10 p = 10 to 48% at p = 25 p = 25 p = 25 and 16% at p = 50 p = 50 p = 50 ; the corresponding rates are 76%, 56%, and 24% for the MIP incumbent and 62%, 26%, and 8% for graph integration.
Comparing Figure 3 with 10 in Appendix D isolates the effect of increasing the maximum boundary size while holding the expected degree at d = 2 d = 2 d = 2 . The values of projected-SHD τ ( G ) \tau(\mathcal{G}) τ ( G ) are generally higher under l = 3 l = 3 l = 3 , and exact recovery is lower. A larger boundary allows more edges to be induced through unobserved variables. These dependences can be weaker than direct relationships, making recovery more difficult even when the total number of edges in the projected graphs changes little. For example, when n = 500 n = 500 n = 500 , p = 50 p = 50 p = 50 , K = 10 K = 10 K = 10 , and m = 0.4 m = 0.4 m = 0.4 , projected-SHD for coordinate descent increases from 0.50 under l = 2 l = 2 l = 2 to 1.98 under l = 3 l = 3 l = 3 , while exact recovery decreases from 44% to 12%. For the MIP incumbent, projected-SHD increases from 0.49 to 1.96, and exact recovery decreases from 46% to 10%. Graph integration is affected more strongly, with projected-SHD increasing from 3.01 to 9.61 and exact recovery decreasing from 2% to 0%.
Comparing Appendix Figure 10 with Figure 4 , we observe that increasing the expected degree from d = 2 d = 2 d = 2 to d = 3 d = 3 d = 3 substantially worsens recovery across methods, although the relative ordering of the approaches generally remains unchanged. Higher degrees increase the number of relationships to estimate. Under our precision-matrix construction, they also produce larger diagonal entries, which can reduce absolute partial correlations even when the off-diagonal coefficients remain comparable. Recovery therefore becomes harder both because there are more edges to identify and because their conditional dependences can be weaker.
Results when some sources provide data and others just graphs
We consider a hybrid setting with five sources with an expected degree d = 2 d = 2 d = 2 , in which three sources provide data and two provide estimated graphs. That is, W 1 = { 1 , 2 , 3 } \mathcal{W}_1 = \{1, 2, 3\} W 1 = { 1 , 2 , 3 } and W 2 = { 4 , 5 } \mathcal{W}_2 = \{4, 5\} W 2 = { 4 , 5 } . We apply the coordinate descent procedure and compare the prespecified graph-source weight c = 1 c = 1 c = 1 with a value selected by cross-validation (see Remark 2). Fixed c = 1 c = 1 c = 1 generally provides better graph recovery. It attains lower projected-SHD in 32 of the 36 settings, while the cross-validated choice performs better in four. Its exact recovery rate is higher in 19 settings, equal in 13, and lower in four. Relative to the previously reported all-data and all-graph results, the hybrid procedure with c = 1 c = 1 c = 1 lies between the two information endpoints. In particular, averaging projected-SHD over the 50 replications within each setting, we obtain all data < three data and two graph sources < all graph sources in 35 of the 36 settings. Similarly, in 33 settings, the hybrid exact recovery rate is no higher than that of the all-data procedure and no lower than that of the all-graph procedure.
Comparison with graph quilting procedures
We compare the proposed method with the procedures in Vinci et al. (2019), Chang et al. (2023). These procedures, called graph quilting (GQ), reconstruct a global graph assuming all the sources provide data, and the data are generated from the same distribution. As we show in the following experiment, their performances deteriorate under distribution shifts.
We generate Gaussian data with p = 10 p = 10 p = 10 variables, K = 5 K = 5 K = 5 data sources, 20% missingness in each source, expected degree d = 2 d = 2 d = 2 , maximum boundary size l = 2 l = 2 l = 2 , and sample sizes n ∈ { 100 , 500 , 1000 } n \in\{100, 500, 1000\} n ∈ { 100 , 500 , 1000 } . We draw a matrix Γ ∈ R p × p \Gamma\in\mathbb{R}^{p \times p} Γ ∈ R p × p in a similar fashion as in Section 7. For each source k ∈ [ K ] k \in[K] k ∈ [ K ] and true edge ( i , j ) (i,j) ( i , j ) , independently draw B i j ( k ) ∼ Unif ( − log 2 , log 2 ) B_{ij}^{(k)} \sim\operatorname{Unif}(-\log2, \log2) B ij ( k ) ∼ Unif ( − log 2 , log 2 ) and U i j ( k ) ∼ Unif ( 0 , 1 ) U_{ij}^{(k)} \sim\operatorname{Unif}(0, 1) U ij ( k ) ∼ Unif ( 0 , 1 ) . Then, for α ∈ [ 0 , 1 ] \alpha\in[0, 1] α ∈ [ 0 , 1 ] , we generate the precision matrix
Ω ( k ) ( α ) \Omega^{(k)}(\alpha) Ω ( k ) ( α ) for source k k k as follows. For each true edge ( i , j ) (i,j) ( i , j ) , let
Ω i j ( k ) ( α ) = Γ i j exp ( α B i j ( k ) ) ( − 1 ) I { U i j ( k ) ≤ α / 2 } . \Omega^{(k)}_{ij}(\alpha)=\Gamma_{ij}\exp\left(\alpha B^{(k)}_{ij}\right)(-1)^{\mathbb{I}\{U^{(k)}_{ij}\leq\alpha/2\}}. Ω ij ( k ) ( α ) = Γ ij exp ( α B ij ( k ) ) ( − 1 ) I { U ij ( k ) ≤ α /2 } .
All other off-diagonal entries remain zero, and symmetry is enforced. The diagonal entries are set to 0.5 + ∑ j ≠ i ∣ Ω i j ( k ) ( α ) ∣ 0.5 + \sum_{j\ne i}\lvert\Omega^{(k)}_{ij}(\alpha)\rvert 0.5 + ∑ j = i ∣ Ω ij ( k ) ( α )∣ , ensuring positive definiteness. We then rescale each source distribution so that every variable has variance one. Thus, when α = 0 \alpha= 0 α = 0 , the source distributions are identical. Increasing α \alpha α introduces greater magnitude variation and more sign differences across sources, while preserving the common graph support.
The GQ methods in Vinci et al. (2019), Chang et al. (2023) involve three or more tuning parameters. We consider tuning these either via cross-validation or via an oracle that minimizes the projected-SHD. For pairs of nodes that are never jointly observed, GQ returns a candidate superset U ^ \widehat{U} U rather than a uniquely identified edge set. We therefore give GQ an additional oracle selection within this superset: for every H ⊆ U ^ H\subseteq\widehat{U} H ⊆ U , we form the graph with edge set E ^ o b s ∪ H \widehat{E}_{\mathrm{obs}}\cup H E obs ∪ H , where E ^ o b s \widehat{E}_{\mathrm{obs}} E obs is the edge set returned by GQ among co-observed nodes, and retain the choice that minimizes the projected-SHD.
Figure 5 shows that GQ performs well, particularly with oracle tuning, when the source distributions are nearly identical (α ≈ 0 \alpha\approx0 α ≈ 0 ). Its error nevertheless increases rapidly as the source distributions diverge, even after oracle selection within its returned superset. In contrast, the proposed method remains stable because it assumes only a common graph and allows source-specific precision matrices.
Figure 5. Projected-SHD across 50 replications for different heterogeneity levels of our approach compared with graph quilting (GQ). At α = 0 \alpha= 0 α = 0 , all sources share a common precision matrix; For α > 0 \alpha> 0 α > 0 , each source has a source-specific precision matrix, where the degree of heterogeneity increases with larger α \alpha α . The tuning parameters of GQ are selected either by cross-validation or via an oracle.
Real data analysis
NHANES (National Center for Health Statistics 2024) is a nationally representative study of the U.S. population that combines interviews, physical examinations, and laboratory measurements. We use NHANES fatty-acid data to study conditional relationships among circulating fatty acids, whose concentrations are strongly interdependent because they share dietary sources, transport mechanisms, and metabolic pathways (Hodson et al. 2008, Calder 2015). A conditional dependence graph can help distinguish direct dependences from those explained by the broader fatty-acid profile.
Fatty-acid measurements were available from four NHANES cycles, with panel sizes ∣ S 1 ∣ = 24 |S_1| = 24 ∣ S 1 ∣ = 24 , ∣ S 2 ∣ = ∣ S 3 ∣ = 30 |S_2| = |S_3| = 30 ∣ S 2 ∣ = ∣ S 3 ∣ = 30 and ∣ S 4 ∣ = 21 |S_4| = 21 ∣ S 4 ∣ = 21 . The first three measured absolute fatty-acid concentrations in plasma or serum in 2003–2004, 2011–2012, and 2013–2014, whereas the fourth measured relative fatty-acid composition in red blood cells in 2021–2023. Together, the partially overlapping panels covered p = 31 p = 31 p = 31 distinct fatty acids. The 2011–2012 and 2013–2014 serum panels were identical. Of the 31 distinct fatty acids, 21 were measured in all four cycles, two in the first three cycles only, seven in the two serum cycles only, and one in 2003–2004 cycle only. After restricting to nonpregnant participants aged 20 years or older with complete analysis variables, the respective sample sizes were n 1 = 1,333 n_1 = 1{,}333 n 1 = 1 , 333 , n 2 = 1,215 n_2 = 1{,}215 n 2 = 1 , 215 , n 3 = 1,545 n_3 = 1{,}545 n 3 = 1 , 545 , and n 4 = 5,115 n_4 = 5{,}115 n 4 = 5 , 115 . Although the measurement platforms differ, both circulating plasma/serum and red-cell fatty acids reflect systemic fatty-acid status, and controlled dietary studies have found broadly similar changes across these compartments (Skeaff et al. 2006, Harris & Thomas 2010, Hodson et al. 2014). We therefore use the four sources to learn a common conditional-independence graph.
Prior work has typically analyzed selected fatty acids, predefined biological groups, or low-dimensional summaries rather than estimating a joint conditional-dependence structure. Network-based metabolomics studies have recovered biologically plausible fatty-acid relationships (Krumsiek et al. 2011), while NHANES studies have focused on selected fatty acids or principal-component summaries in relation to specific outcomes (Yu et al. 2018, Petersen et al. 2020, Murphy et al. 2021, Chen et al. 2024). To our knowledge, no previous NHANES analysis has learned a fatty-acid conditional-independence graph by integrating its partially overlapping measurement panels.
NHANES provides survey weights tailored to each examination or laboratory subsample to account for unequal selection probabilities and survey nonresponse. For sources 1–3, we regressed each log-transformed fatty-acid concentration on age, modeled using a restricted cubic spline with knots at the weighted 5th, 35th, 65th, and 95th percentiles, sex, race and ethnicity, and fasting duration. We centered and standardized the residuals using the same weights and retained these weights in the graph-estimation loss.
Source 4 requires additional care because its fatty-acid measurements are compositional, reported as percentages constrained to sum to one. Since directly incorporating an appropriate compositional graph-learning procedure into our joint optimization is less straightforward, we first estimate the source-4 graph separately and then incorporate this estimated graph G ^ S 4 ( 4 ) \widehat{\mathcal{G}}_{S_4}^{(4)} G S 4 ( 4 ) into the integration procedure. Specifically, we use a survey-weighted adaptation of CARE (Zhang et al. 2025), after adjusting for the same covariates in centered log-ratio space using the NHANES phlebotomy weights. Further details are provided in Appendix E.
Letting W 1 = { 1 , 2 , 3 } \mathcal{W}_1 = \{1,2,3\} W 1 = { 1 , 2 , 3 } and W 2 = { 4 } \mathcal{W}_2 = \{4\} W 2 = { 4 } , we obtain estimator (4) using a survey-weighted version of the loss in (6), replacing the usual sample covariance matrix with a weighted covariance matrix in which each observation is weighted by its NHANES survey weight. We set γ = median k ∈ W 1 { 2 log ( n k ) / n k } = 0.0107 \gamma= \operatorname{median}_{k \in\mathcal{W}_1}\{2\log(n_k)/n_k\} = 0.0107 γ = median k ∈ W 1 { 2 log ( n k ) / n k } = 0.0107 .
The MIP was run for 10 hours and returned an 80-edge incumbent graph G ^ \widehat{G} G with a relative optimality gap of 15.8%. Conditional on its fitted source projections, the equivalence class EC ( G ^ ) \operatorname{EC}(\widehat{G}) EC ( G ) contains two graphs, which differ only in the inclusion of a single edge. Within its equivalence class all 80 selected edges were always present (AP), 384 unselected pairs were always absent (AA), and one unselected pair was ambiguous. To assess the sensitivity of these classifications to sampling variability, we generated 100 replicates by independently subsampling 80% of the participants in each of sources 1–3 while holding the fourth-source graph fixed. For tractability, each replicate used multistart coordinate descent, including the full-data MIP graph as a warm start, without rerunning the MIP, followed by a complete equivalence-class analysis. An edge was considered stable-AP or stable-AA if it received that classification in at least 90% of the replicates. Figure 6 presents the full-data and stability classifications jointly.
Figure 6. Full-data equivalence and subsampling-stability classifications for all 465 pairs of the 31 fatty acids in the integrated analysis of the four NHANES cycle data. Fatty acids are ordered by family and chain length, with black boundaries separating families.
The fatty acids were grouped into saturated, n n n -5/n n n -7 Monounsaturated Fatty Acids (MUFAs), n n n -9 fatty acids, and n n n -6/n n n -3 Polyunsaturated Fatty Acids (PUFAs). The network showed clear organization by family and chain length: 34.0% of within-family pairs were connected, compared with 11.1% of between-family pairs, with particularly strong connectivity within the n n n -6 and n n n -3 PUFAs and between these two families. Connectivity was also higher among fatty acids with the same chain length or differing by two carbons than among more distant pairs. This pattern is consistent with fatty-acid metabolism, where desaturation preserves chain length, elongation typically adds two carbons, and n n n -3 and n n n -6 fatty acids share desaturase and elongase pathways ((Schaeffer et al. 2006, Guillou et al. 2010)).
Eicosadienoic acid (C 20 : 2 n - 6 \mathrm{C20:2n\text{-}6} C20 : 2n - 6 ) had the highest degree, with nine stable connections, followed by DHA (C 22 : 6 n - 3 \mathrm{C22:6n\text{-}3} C22 : 6n - 3 ), with eight. C 20 : 2 n - 6 \mathrm{C20:2n\text{-}6} C20 : 2n - 6 is an intermediate in long-chain PUFA synthesis ((Park et al. 2009)), whereas DHA is a terminal product of the n n n -3 pathway and an important membrane component ((Sprecher et al. 1995)). Notably, DHA was connected to five n n n -6 fatty acids, and Mead acid to both n n n -3 and n n n -6 fatty acids, highlighting cross-family relationships that may reflect shared dietary, transport, or FADS/ELOVL pathways. Lauric and erucic acids had the lowest degrees, with two connections each.
Several established reaction pairs, including stearic acid–oleic acid, dihomo-gamma-linolenic acid–arachidonic acid, and C 20 : 1 n - 9 \mathrm{C20:1n\text{-}9} C20 : 1n - 9 –C 22 : 1 n - 9 \mathrm{C22:1n\text{-}9} C22 : 1n - 9 , were consistently classified as AA ((Schaeffer et al. 2006, Paton & Ntambi 2009)). Biochemical reactions serve here as biological annotations rather than as ground-truth conditional edges. Their stable absence indicates that these pairs did not retain distinct dependences after conditioning on the other measured fatty acids, not that the underlying reactions are absent. Contrasting stable AP and AA relationships may therefore help distinguish pathway relationships that structure population-level variation from those represented indirectly through the surrounding network.
These interpretations are subject to estimation uncertainty and incomplete measurement. After adjustment for the specified covariates, the analysis estimates the conditional-dependence structure of the marginal distribution of the 31 measured fatty acids. Other unmeasured variables may therefore induce or obscure dependences among them. Finite-sample and laboratory measurement variability may also affect edge selection, although the subsampling analysis assesses sensitivity to sampling variation. Finally, the MIP returned an incumbent rather than a certified globally optimal solution, so the full-data equivalence classifications are conditional on the fitted projections of that incumbent.
Discussion
We developed a general framework for reconstructing a shared global graph from heterogeneous sources that observe different subsets of variables and could contribute raw data, estimated graphs, or both. The framework links each source-specific graph to a common global graph through latent projections, allowing information to be integrated coherently despite incomplete variable coverage and data-access restrictions. Our theoretical and empirical results showed that this integration recovered the global projection-equivalence class and could substantially improve the estimation of source-specific graph structure relative to analyzing each source separately.
Our work opens several directions for future research. First, we assumed that all sources arise from a common global graph. This assumption could be relaxed by allowing the underlying graphs to differ slightly across sources while encouraging them to share substantial structure, building on ideas from Danaher et al. (2014). Second, when a source does not observe a hub node of the global graph, its latent projection can become substantially denser, potentially degrading both statistical and computational performance. In such settings, one could instead use a sparse-plus-low-rank decomposition (Chandrasekaran et al. 2012). The SHD term would then compare the graph encoded by the estimated sparse component with the induced subgraph of a candidate global graph, rather than with its latent projection. Third, in federated settings, it would be interesting to consider an iterative procedure over several rounds. The central estimator would send each source its current projected graph estimate. Sources would refine these estimates using local data and return the updated graphs for reintegration. Finally, while our exact MIP formulations allow certification of
global optimality, they do not scale to very large graphs. Tailored cutting-plane methods that exploit the latent-projection constraints could improve scalability.
Acknowledgements
We acknowledge funding from NIH grants RF1-AG090462 and U01 HG013177 (Nir Keret and Ali Shojaie) and NSF grant DMS-2413074 (Armeen Taeb).
Proofs
Proof of Proposition 8
Proof. By Assumption 1, we have that ( i , j ) ∈ E ( π S k ( G ∗ ) ) ⟺ X i ⊥̸ X j ∣ X S k ∖ { i , j } (i,j) \in E(\pi_{S_k}(\mathcal{G}^{\ast})) \Longleftrightarrow X_i \not\perp X_j \mid X_{S_k\setminus\{i,j\}} ( i , j ) ∈ E ( π S k ( G ∗ )) ⟺ X i ⊥ X j ∣ X S k ∖ { i , j } under P S k ( k ) P_{S_k}^{(k)} P S k ( k ) . Since the pairwise conditional independences in P S k ( k ) P_{S_k}^{(k)} P S k ( k ) are known, π S k ( G ∗ ) \pi_{S_k}(\mathcal{G}^{\ast}) π S k ( G ∗ ) is uniquely identifiable from P S k ( k ) P_{S_k}^{(k)} P S k ( k ) . Suppose G \mathcal{G} G is indistinguishable from G ∗ \mathcal{G}^{\ast} G ∗ given pairwise conditional independences of P S k ( k ) P_{S_k}^{(k)} P S k ( k ) , k ∈ [ K ] k \in[K] k ∈ [ K ] . From the earlier analysis, it must be that π S k ( G ) = π S k ( G ∗ ) \pi_{S_k}(\mathcal{G}) = \pi_{S_k}(\mathcal{G}^{\ast}) π S k ( G ) = π S k ( G ∗ ) for every k ∈ [ K ] k \in[K] k ∈ [ K ] and thus G ∈ EC ( G ∗ ; { S k } k = 1 K ) \mathcal{G} \in\operatorname{EC}(\mathcal{G}^{\ast};\{S_k\}_{k=1}^{K}) G ∈ EC ( G ∗ ; { S k } k = 1 K ) . On the other hand, if G ∈ EC ( G ∗ ; { S k } k = 1 K ) \mathcal{G} \in\operatorname{EC}(\mathcal{G}^{\ast};\{S_k\}_{k=1}^{K}) G ∈ EC ( G ∗ ; { S k } k = 1 K ) , then π S k ( G ) = π S k ( G ∗ ) \pi_{S_k}(\mathcal{G}) = \pi_{S_k}(\mathcal{G}^{\ast}) π S k ( G ) = π S k ( G ∗ ) for every k ∈ [ K ] k \in[K] k ∈ [ K ] and so the pairwise conditional independences from the marginal distributions cannot distinguish G \mathcal{G} G from G ∗ \mathcal{G}^{\ast} G ∗ .
Proof of Proposition 10
Proof. For each k ∈ [ K ] k \in[K] k ∈ [ K ] , define
E k : = { { arg min G ~ Loss k ( G ~ ; D k ) = { G S k ∗ ( k ) } } , k ∈ W 1 , { G ^ S k ( k ) = G S k ∗ ( k ) } , k ∈ W 2 . \mathcal{E}_k :=
\begin{cases}
\left\{\underset{\widetilde{\mathcal{G}}}{\arg\min}\ \operatorname{Loss}_k(\widetilde{\mathcal{G}};\mathcal{D}_k)=\{\mathcal{G}_{S_k}^{\ast(k)}\}\right\}, & k\in\mathcal{W}_1,\\
\left\{\widehat{\mathcal{G}}_{S_k}^{(k)}=\mathcal{G}_{S_k}^{\ast(k)}\right\}, & k\in\mathcal{W}_2.
\end{cases} E k := ⎩ ⎨ ⎧ { G arg min Loss k ( G ; D k ) = { G S k ∗ ( k ) } } , { G S k ( k ) = G S k ∗ ( k ) } , k ∈ W 1 , k ∈ W 2 .
By Assumption 2 P ( E k ) ⟶ 1 \mathbb{P}(\mathcal{E}_k)\longrightarrow1 P ( E k ) ⟶ 1 for every k ∈ [ K ] k \in[K] k ∈ [ K ] . Since K K K is fixed,
P ( ⋂ k = 1 K E k ) ≥ 1 − ∑ k = 1 K P ( E k c ) ⟶ 1. \mathbb{P}\left(\bigcap_{k=1}^{K}\mathcal{E}_k\right)\geq1-\sum_{k=1}^{K}\mathbb{P}(\mathcal{E}_k^c)\longrightarrow1. P ( k = 1 ⋂ K E k ) ≥ 1 − k = 1 ∑ K P ( E k c ) ⟶ 1.
On the event ⋂ k = 1 K E k \bigcap_{k=1}^{K}\mathcal{E}_k ⋂ k = 1 K E k , the true graph G ∗ \mathcal{G}^{\ast} G ∗ attains the minimum possible value of every source-specific term in (4). Hence any minimizer G ^ \widehat{\mathcal{G}} G of (4) must satisfy
π S k ( G ^ ) = G S k ∗ ( k ) = π S k ( G ∗ ) , ∀ k ∈ [ K ] . \pi_{S_k}(\widehat{\mathcal{G}})=\mathcal{G}_{S_k}^{\ast(k)}=\pi_{S_k}(\mathcal{G}^{\ast}),\qquad\forall k\in[K]. π S k ( G ) = G S k ∗ ( k ) = π S k ( G ∗ ) , ∀ k ∈ [ K ] .
Therefore,
EC ( G ^ ; { S k } k = 1 K ) = EC ( G ∗ ; { S k } k = 1 K ) . \operatorname{EC}\left(\widehat{\mathcal{G}};\{S_k\}_{k=1}^{K}\right)=\operatorname{EC}\left(\mathcal{G}^{\ast};\{S_k\}_{k=1}^{K}\right). EC ( G ; { S k } k = 1 K ) = EC ( G ∗ ; { S k } k = 1 K ) .
Consequently,
P ( EC ( G ^ ; { S k } k = 1 K ) = EC ( G ∗ ; { S k } k = 1 K ) ) ⟶ 1. \mathbb{P}\left(\operatorname{EC}\left(\widehat{\mathcal{G}};\{S_k\}_{k=1}^{K}\right)=\operatorname{EC}\left(\mathcal{G}^{\ast};\{S_k\}_{k=1}^{K}\right)\right)\longrightarrow1. P ( EC ( G ; { S k } k = 1 K ) = EC ( G ∗ ; { S k } k = 1 K ) ) ⟶ 1.
Proof of Theorem 11
The proof relies on two propositions. We state these first, prove Theorem 11, and then prove the propositions.
Proposition 13. Let
ε n , k : = max A , B ⊆ S k , ∣ A ∣ ≤ d n , ∣ B ∣ ≤ d n ∥ [ Σ ^ k ] A , B − [ Σ k ∗ ] A , B ∥ 2 . \varepsilon_{n,k}:=\max_{\substack{A,B\subseteq S_k,\,|A|\leq d_n,\,|B|\leq d_n}}\left\|[\widehat{\Sigma}_k]_{A,B}-[\Sigma_k^{\ast}]_{A,B}\right\|_2. ε n , k := A , B ⊆ S k , ∣ A ∣ ≤ d n , ∣ B ∣ ≤ d n max [ Σ k ] A , B − [ Σ k ∗ ] A , B 2 .
Suppose for every k ∈ [ K ] k\in[K] k ∈ [ K ] :
ω k λ k ≥ 2 C ‾ ω k ε n , k , \omega_k\lambda_k\geq2\overline{C}\omega_k\varepsilon_{n,k}, ω k λ k ≥ 2 C ω k ε n , k ,
and
max k ω k λ k / min k ω k λ k ≤ C . \max_k\omega_k\lambda_k/\min_k\omega_k\lambda_k\leq C. k max ω k λ k / k min ω k λ k ≤ C .
Define:
q − : = min { r ∈ N : Γ − ( r ) > max k ω k λ k ( d n + 1 / 2 ) } . q_-:=\min\left\{r\in\mathbb{N}:\Gamma^-(r)>\max_k\omega_k\lambda_k(d_n+1/2)\right\}. q − := min { r ∈ N : Γ − ( r ) > k max ω k λ k ( d n + 1/2 ) } .
Then,
∣ A ( G ^ , G ⋆ ) ∣ ≤ ( 1 + C ( 2 d n + 1 ) ) q − . |\mathcal{A}(\widehat{G},G^\star)| \le(1+C(2d_n+1))q_-. ∣ A ( G , G ⋆ ) ∣ ≤ ( 1 + C ( 2 d n + 1 )) q − .
Proposition 14. Suppose ∣ A ( G ^ , G ⋆ ) ∣ ≤ q |\mathcal{A}(\widehat{G},G^\star)| \le q ∣ A ( G , G ⋆ ) ∣ ≤ q . Suppose λ k \lambda_k λ k satisfies the condition described in Proposition 13 and that additionally, for every k ∈ [ K ] k \in[K] k ∈ [ K ] and i ∈ S k i \in S_k i ∈ S k
( d n + 1 / 2 ) q max j ω j λ j ≤ δ k i ( q ) / 2. (d_n+1/2)q\max_j\omega_j\lambda_j \le\delta_{ki}(q)/2. ( d n + 1/2 ) q j max ω j λ j ≤ δ k i ( q ) /2. Suppose also that
ε n , k ≤ κ min / 2. \varepsilon_{n,k} \le\kappa_{\min}/2. ε n , k ≤ κ m i n /2. Then, π S k ( G ^ ) = π S k ( G ⋆ ) \pi_{S_k}(\widehat{G})=\pi_{S_k}(G^\star) π S k ( G ) = π S k ( G ⋆ ) for every k ∈ [ K ] k \in[K] k ∈ [ K ] .
Proof. Define:
t k = κ max 256 ( d n + 1 ) log ( 2 K p ) n k . t_k=\kappa_{\max}\sqrt{\frac{256(d_n+1)\log(2Kp)}{n_k}}. t k = κ m a x n k 256 ( d n + 1 ) log ( 2 K p ) .
For any A , B ⊆ S k A,B\subseteq S_k A , B ⊆ S k , ∣ A ∣ , ∣ B ∣ ≤ d n |A|,|B|\le d_n ∣ A ∣ , ∣ B ∣ ≤ d n , writing U = A ∪ B U=A\cup B U = A ∪ B , we have:
∥ [ Σ ^ k ] A , B − [ Σ k ⋆ ] A , B ∥ 2 ≤ ∥ [ Σ ^ k ] U , U − [ Σ k ⋆ ] U , U ∥ 2 , ∣ U ∣ ≤ 2 d n . \left\|[\widehat{\Sigma}_k]_{A,B}-[\Sigma_k^\star]_{A,B}\right\|_2\le\left\|[\widehat{\Sigma}_k]_{U,U}-[\Sigma_k^\star]_{U,U}\right\|_2,\quad|U|\le2d_n. [ Σ k ] A , B − [ Σ k ⋆ ] A , B 2 ≤ [ Σ k ] U , U − [ Σ k ⋆ ] U , U 2 , ∣ U ∣ ≤ 2 d n .
Since t k ≤ 8 κ max t_k\le8\kappa_{\max} t k ≤ 8 κ m a x and n k ≥ 128 d n κ max 2 / t k 2 n_k\ge128d_n\kappa_{\max}^2/t_k^2 n k ≥ 128 d n κ m a x 2 / t k 2 , standard Gaussian concentration results mean that:
P ( ∥ [ Σ ^ k ] U , U − [ Σ k ⋆ ] U , U ∥ 2 > t k ) ≤ 2 exp ( − n k t k 2 128 κ max 2 ) = 2 ( 2 K p ) − 2 ( d n + 1 ) . \mathbb{P}\left(\left\|[\widehat{\Sigma}_k]_{U,U}-[\Sigma_k^\star]_{U,U}\right\|_2>t_k\right)\le2\exp\left(-\frac{n_kt_k^2}{128\kappa_{\max}^2}\right)=2(2Kp)^{-2(d_n+1)}. P ( [ Σ k ] U , U − [ Σ k ⋆ ] U , U 2 > t k ) ≤ 2 exp ( − 128 κ m a x 2 n k t k 2 ) = 2 ( 2 K p ) − 2 ( d n + 1 ) .
Since the number of subsets U ⊆ S k U\subseteq S_k U ⊆ S k of size at most 2 d n 2d_n 2 d n is bounded by p 2 d n + 1 p^{2d_n+1} p 2 d n + 1 , a union bound gives:
P ( ∃ k : ε n , k > t k ) ≤ 2 K p 2 d n + 1 ( 2 K p ) − 2 ( d n + 1 ) ≤ 1 p . \mathbb{P}(\exists k:\varepsilon_{n,k}>t_k)\le2Kp^{2d_n+1}(2Kp)^{-2(d_n+1)}\le\frac{1}{p}. P ( ∃ k : ε n , k > t k ) ≤ 2 K p 2 d n + 1 ( 2 K p ) − 2 ( d n + 1 ) ≤ p 1 .
Thus, with probability at least 1 − 1 / p 1-1/p 1 − 1/ p , simultaneously for all k k k , ε n , k ≤ t k ≤ κ min / 2 \varepsilon_{n,k}\le t_k\le\kappa_{\min}/2 ε n , k ≤ t k ≤ κ m i n /2 . On this event, since λ k ≥ 2 C ‾ t k \lambda_k\ge2\overline{C}t_k λ k ≥ 2 C t k , we have for every k ∈ [ K ] k\in[K] k ∈ [ K ] :
ω k λ k ≥ 2 C ‾ ω k t k ≥ 2 C ‾ ω k ε n , k . \omega_k\lambda_k\ge2\overline{C}\omega_kt_k\ge2\overline{C}\omega_k\varepsilon_{n,k}. ω k λ k ≥ 2 C ω k t k ≥ 2 C ω k ε n , k .
Moreover, by assumption
max k ω k λ k min k ω k λ k ≤ C . \frac{\max_k\omega_k\lambda_k}{\min_k\omega_k\lambda_k}\le C. min k ω k λ k max k ω k λ k ≤ C .
Hence, Proposition 13 applies and yields ∣ A ( G ^ , G ⋆ ) ∣ ≤ q min |\mathcal{A}(\widehat{G},G^\star)|\le q_{\min} ∣ A ( G , G ⋆ ) ∣ ≤ q m i n . Since max j ω j λ j ≤ C ω k λ k \max_j\omega_j\lambda_j\le C\omega_k\lambda_k max j ω j λ j ≤ C ω k λ k , we have that:
max j ω j t j ≤ C ω k t k for every k ∈ [ K ] . \max_j\omega_jt_j\le C\omega_kt_k\quad\text{for every }k\in[K]. j max ω j t j ≤ C ω k t k for every k ∈ [ K ] .
So we have for every k ∈ [ K ] k\in[K] k ∈ [ K ]
( d n + 1 / 2 ) q min max j ω j λ j ≤ 2 C C ‾ ( d n + 1 / 2 ) q min ω k t k ≤ δ k , min 2 . (d_n+1/2)q_{\min}\max_j\omega_j\lambda_j\le2C\overline{C}(d_n+1/2)q_{\min}\omega_kt_k\le\frac{\delta_{k,\min}}{2}. ( d n + 1/2 ) q m i n j max ω j λ j ≤ 2 C C ( d n + 1/2 ) q m i n ω k t k ≤ 2 δ k , m i n .
Here, the last inequality comes from the sample size requirement. Thus, all the conditions of Proposition 14 are satisfied on the event ε n , k ≤ t k \varepsilon_{n,k}\le t_k ε n , k ≤ t k for all k k k .
Proof of Proposition 13
The proof relies on the following lemma. Let L ^ \widehat{\mathcal{L}} L be the empirical version of L \mathcal{L} L . We let:
A ( G , G ⋆ ) : = { ( k , j ) : N ( j , π S k ( G ) ) ≠ N ( j , π S k ( G ⋆ ) ) } . \mathcal{A}(\mathcal{G},\mathcal{G}^{\star}) := \{(k,j):N(j,\pi_{S_k}(\mathcal{G})) \ne N(j,\pi_{S_k}(\mathcal{G}^{\star}))\}. A ( G , G ⋆ ) := {( k , j ) : N ( j , π S k ( G )) = N ( j , π S k ( G ⋆ ))} .
We also let A + ( G , G ⋆ ) = A ( G , G ⋆ ) ∖ A − ( G , G ⋆ ) \mathcal{A}^{+}(\mathcal{G},\mathcal{G}^{\star})=\mathcal{A}(\mathcal{G},\mathcal{G}^{\star})\setminus\mathcal{A}^{-}(\mathcal{G},\mathcal{G}^{\star}) A + ( G , G ⋆ ) = A ( G , G ⋆ ) ∖ A − ( G , G ⋆ ) .
Lemma 15. We have:
max G ∈ G max k ∈ [ K ] , j ∈ S k L ^ k j ( G ) − L k j ( G ) ≤ max k C ‾ ω k ε n , k \max_{\mathcal{G}\in\mathcal{G}}\max_{k\in[K],j\in S_k}\widehat{L}_{kj}(\mathcal{G})-L_{kj}(\mathcal{G})\leq\max_k\overline{C}\omega_k\varepsilon_{n,k} G ∈ G max k ∈ [ K ] , j ∈ S k max L k j ( G ) − L k j ( G ) ≤ k max C ω k ε n , k and
max G ∈ G [ L ^ ( G ) − L ( G ) ] − [ L ^ ( G ⋆ ) − L ( G ⋆ ) ] ∣ A ( G , G ⋆ ) ∣ ≤ max k C ‾ ω k ε n , k . \max_{\mathcal{G}\in\mathcal{G}}\frac{\left[\widehat{\mathcal{L}}(\mathcal{G})-\mathcal{L}(\mathcal{G})\right]-\left[\widehat{\mathcal{L}}(\mathcal{G}^{\star})-\mathcal{L}(\mathcal{G}^{\star})\right]}{|\mathcal{A}(\mathcal{G},\mathcal{G}^{\star})|}\leq\max_k\overline{C}\omega_k\varepsilon_{n,k}. G ∈ G max ∣ A ( G , G ⋆ ) ∣ [ L ( G ) − L ( G ) ] − [ L ( G ⋆ ) − L ( G ⋆ ) ] ≤ k max C ω k ε n , k .
Proof of Lemma 15. Note that:
L ^ k j ( G ) − L k j ( G ) : = ω k [ [ Σ ^ k ] j j − [ Σ k ⋆ ] j j − [ Σ ^ k ] j T ( [ Σ ^ k ] T T ) − 1 [ Σ ^ k ] T j + [ Σ k ⋆ ] j T ( [ Σ k ⋆ ] T T ) − 1 [ Σ k ⋆ ] T j ] . \widehat{L}_{kj}(\mathcal{G})-L_{kj}(\mathcal{G}):=\omega_k\left[\left[\widehat{\Sigma}_k\right]_{jj}-\left[\Sigma_k^{\star}\right]_{jj}-\left[\widehat{\Sigma}_k\right]_{jT}\left(\left[\widehat{\Sigma}_k\right]_{TT}\right)^{-1}\left[\widehat{\Sigma}_k\right]_{Tj}+\left[\Sigma_k^{\star}\right]_{jT}\left(\left[\Sigma_k^{\star}\right]_{TT}\right)^{-1}\left[\Sigma_k^{\star}\right]_{Tj}\right]. L k j ( G ) − L k j ( G ) := ω k [ [ Σ k ] j j − [ Σ k ⋆ ] j j − [ Σ k ] j T ( [ Σ k ] T T ) − 1 [ Σ k ] T j + [ Σ k ⋆ ] j T ( [ Σ k ⋆ ] T T ) − 1 [ Σ k ⋆ ] T j ] .
Then it follows that:
max G ∈ G ∣ [ L ^ ( G ) − L ^ ( G ⋆ ) ] − [ L ( G ) − L ( G ⋆ ) ] ∣ ∣ A ( G , G ⋆ ) ∣ = max G ∈ G ∣ ∑ ( k , j ) ∈ A ( G , G ⋆ ) [ L ^ k j ( G ) − L k j ( G ) − L ^ k j ( G ⋆ ) + L k j ( G ⋆ ) ] ∣ ∣ A ( G , G ⋆ ) ∣ \max_{\mathcal{G}\in\mathcal{G}}\frac{\left|\left[\widehat{\mathcal{L}}(\mathcal{G})-\widehat{\mathcal{L}}(\mathcal{G}^{\star})\right]-\left[\mathcal{L}(\mathcal{G})-\mathcal{L}(\mathcal{G}^{\star})\right]\right|}{|\mathcal{A}(\mathcal{G},\mathcal{G}^{\star})|}
=
\max_{\mathcal{G}\in\mathcal{G}}
\frac{\left|\sum_{(k,j)\in\mathcal{A}(\mathcal{G},\mathcal{G}^{\star})}\left[\widehat{L}_{kj}(\mathcal{G})-L_{kj}(\mathcal{G})-\widehat{L}_{kj}(\mathcal{G}^{\star})+L_{kj}(\mathcal{G}^{\star})\right]\right|}{|\mathcal{A}(\mathcal{G},\mathcal{G}^{\star})|} G ∈ G max ∣ A ( G , G ⋆ ) ∣ [ L ( G ) − L ( G ⋆ ) ] − [ L ( G ) − L ( G ⋆ ) ] = G ∈ G max ∣ A ( G , G ⋆ ) ∣ ∑ ( k , j ) ∈ A ( G , G ⋆ ) [ L k j ( G ) − L k j ( G ) − L k j ( G ⋆ ) + L k j ( G ⋆ ) ]
≤ 2 max k ∈ [ K ] , j ∈ S k ∣ L ^ k j ( G ) − L k j ( G ) ∣ \leq2\max_{k\in[K],j\in S_k}\left|\widehat{L}_{kj}(\mathcal{G})-L_{kj}(\mathcal{G})\right| ≤ 2 k ∈ [ K ] , j ∈ S k max L k j ( G ) − L k j ( G )
≤ 2 [ max k ∈ [ K ] , j ∈ S k ω k ∣ [ Σ ^ k ] j j − [ Σ k ⋆ ] j j ∣ ] + 2 [ max k ∈ [ K ] , j ∈ S k max T ⊆ S k ∖ { j } ∣ T ∣ ≤ d n ω k ∣ [ Σ ^ k ] j T ( [ Σ ^ k ] T T ) − 1 [ Σ ^ k ] T j − [ Σ k ⋆ ] j T ( [ Σ k ⋆ ] T T ) − 1 [ Σ k ⋆ ] T j ∣ ] ≤ max k C ‾ ω k ε n , k . \begin{aligned}
\leq2\left[\max_{k\in[K],j\in S_k}\omega_k\left|\left[\widehat{\Sigma}_k\right]_{jj}-\left[\Sigma_k^{\star}\right]_{jj}\right|\right] \\
&+2\left[\max_{k\in[K],j\in S_k}\max_{\substack{T\subseteq S_k\setminus\{j\}\\ |T|\leq d_n}}\omega_k\left|\left[\widehat{\Sigma}_k\right]_{jT}\left(\left[\widehat{\Sigma}_k\right]_{TT}\right)^{-1}\left[\widehat{\Sigma}_k\right]_{Tj}-\left[\Sigma_k^{\star}\right]_{jT}\left(\left[\Sigma_k^{\star}\right]_{TT}\right)^{-1}\left[\Sigma_k^{\star}\right]_{Tj}\right|\right] \\
&\leq\max_k\overline{C}\omega_k\varepsilon_{n,k}.
\end{aligned} ≤ 2 [ k ∈ [ K ] , j ∈ S k max ω k [ Σ k ] j j − [ Σ k ⋆ ] j j ] + 2 k ∈ [ K ] , j ∈ S k max T ⊆ S k ∖ { j } ∣ T ∣ ≤ d n max ω k [ Σ k ] j T ( [ Σ k ] T T ) − 1 [ Σ k ] T j − [ Σ k ⋆ ] j T ( [ Σ k ⋆ ] T T ) − 1 [ Σ k ⋆ ] T j ≤ k max C ω k ε n , k .
The last inequality follows from ε k , n ≤ κ min / 2 \varepsilon_{k,n}\leq\kappa_{\min}/2 ε k , n ≤ κ m i n /2 and C ‾ : = 4 + 8 κ max κ min + 4 κ max 2 κ min 2 \overline{C}:=4+\frac{8\kappa_{\max}}{\kappa_{\min}}+\frac{4\kappa_{\max}^{2}}{\kappa_{\min}^{2}} C := 4 + κ m i n 8 κ m a x + κ m i n 2 4 κ m a x 2 .
Proposition 13
We have from the optimality condition that:
L ^ ( G ^ ) + 2 ∑ k ω k λ k ∣ E ( π S k ( G ^ ) ) ∣ ≤ L ^ ( G ⋆ ) + 2 ∑ k ω k λ k ∣ E ( π S k ( G ⋆ ) ) ∣ . \widehat{\mathcal{L}}(\widehat{\mathcal{G}})+2\sum_k\omega_k\lambda_k|E(\pi_{S_k}(\widehat{\mathcal{G}}))|\leq\widehat{\mathcal{L}}(\mathcal{G}^{\star})+2\sum_k\omega_k\lambda_k|E(\pi_{S_k}(\mathcal{G}^{\star}))|. L ( G ) + 2 k ∑ ω k λ k ∣ E ( π S k ( G )) ∣ ≤ L ( G ⋆ ) + 2 k ∑ ω k λ k ∣ E ( π S k ( G ⋆ )) ∣.
The optimality condition above implies:
0 ≥ L ^ ( G ^ ) − L ^ ( G ⋆ ) − ∑ ( k , j ) ∈ A − ( G ^ , G ⋆ ) ω k λ k d n + ∑ ( k , j ) ∈ A + ( G ^ , G ⋆ ) ω k λ k . 0\geq\widehat{\mathcal{L}}(\widehat{\mathcal{G}})-\widehat{\mathcal{L}}(\mathcal{G}^{\star})-\sum_{(k,j)\in\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\omega_k\lambda_kd_n+\sum_{(k,j)\in\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\omega_k\lambda_k. 0 ≥ L ( G ) − L ( G ⋆ ) − ( k , j ) ∈ A − ( G , G ⋆ ) ∑ ω k λ k d n + ( k , j ) ∈ A + ( G , G ⋆ ) ∑ ω k λ k .
Therefore, by Lemma 15,
L ( G ^ ) − L ( G ⋆ ) − ∑ ( k , j ) ∈ A − ( G ^ , G ⋆ ) [ ω k λ k d n + C ‾ ω k ε n , k ] + ∑ ( k , j ) ∈ A + ( G ^ , G ⋆ ) [ ω k λ k − C ‾ ω k ε n , k ] ≤ 0. (17) \mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star})-\sum_{(k,j)\in\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\left[\omega_k\lambda_kd_n+\overline{C}\omega_k\varepsilon_{n,k}\right]+\sum_{(k,j)\in\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\left[\omega_k\lambda_k-\overline{C}\omega_k\varepsilon_{n,k}\right]\leq0. \tag*{(17)} L ( G ) − L ( G ⋆ ) − ( k , j ) ∈ A − ( G , G ⋆ ) ∑ [ ω k λ k d n + C ω k ε n , k ] + ( k , j ) ∈ A + ( G , G ⋆ ) ∑ [ ω k λ k − C ω k ε n , k ] ≤ 0. (17)
Since
ω k λ k ≥ 2 C ‾ ω k ε n , k , \omega_k\lambda_k\geq2\overline{C}\omega_k\varepsilon_{n,k}, ω k λ k ≥ 2 C ω k ε n , k ,
we have that:
0 ≥ L ( G ^ ) − L ( G ⋆ ) − ∣ A − ( G ^ , G ⋆ ) ∣ max k ω k λ k ( d n + 1 / 2 ) + 1 2 ∣ A + ( G ^ , G ⋆ ) ∣ min k ω k λ k . (18) 0\geq\mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star})-|\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})|\max_k\omega_k\lambda_k(d_n+1/2)+\frac{1}{2}|\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})|\min_k\omega_k\lambda_k. \tag*{(18)} 0 ≥ L ( G ) − L ( G ⋆ ) − ∣ A − ( G , G ⋆ ) ∣ k max ω k λ k ( d n + 1/2 ) + 2 1 ∣ A + ( G , G ⋆ ) ∣ k min ω k λ k . (18)
Take any r r r satisfying
Γ − ( r ) > max k ω k λ k ( d n + 1 / 2 ) . \Gamma^{-}(r)>\max_k\omega_k\lambda_k(d_n+1/2). Γ − ( r ) > k max ω k λ k ( d n + 1/2 ) .
Suppose, as a point of contradiction, that
∣ A − ( G ^ , G ⋆ ) ∣ ≥ r . \lvert\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\ge r. ∣ A − ( G , G ⋆ )∣ ≥ r .
Then,
L ( G ^ ) − L ( G ⋆ ) ∣ A − ( G ^ , G ⋆ ) ∣ ≥ Γ − ( r ) > max k ω k λ k ( d n + 1 / 2 ) , \frac{\mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star})}{\lvert\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert} \ge\Gamma^{-}(r) > \max_{k}\omega_k\lambda_k(d_n+1/2), ∣ A − ( G , G ⋆ )∣ L ( G ) − L ( G ⋆ ) ≥ Γ − ( r ) > k max ω k λ k ( d n + 1/2 ) ,
implying that
L ( G ^ ) − L ( G ⋆ ) > ∣ A − ( G ^ , G ⋆ ) ∣ max k ω k λ k ( d n + 1 / 2 ) . \mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star}) > \lvert\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\max_{k}\omega_k\lambda_k(d_n+1/2). L ( G ) − L ( G ⋆ ) > ∣ A − ( G , G ⋆ )∣ k max ω k λ k ( d n + 1/2 ) .
This however contradicts the inequality (18). Hence, defining
q − : = min { r ∈ N : Γ − ( r ) > max k ω k λ k ( d n + 1 / 2 ) } , q^{-}:=\min\left\{r\in\mathbb{N}:\Gamma^{-}(r)>\max_{k}\omega_k\lambda_k(d_n+1/2)\right\}, q − := min { r ∈ N : Γ − ( r ) > k max ω k λ k ( d n + 1/2 ) } ,
we have
∣ A − ( G ^ , G ⋆ ) ∣ ≤ q − . \lvert\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\le q^{-}. ∣ A − ( G , G ⋆ )∣ ≤ q − .
Moreover, since L ( G ^ ) − L ( G ⋆ ) ≥ 0 \mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star})\ge0 L ( G ) − L ( G ⋆ ) ≥ 0 , inequality (17) implies:
1 2 min k ω k λ k ∣ A + ( G ^ , G ⋆ ) ∣ ≤ max k ω k λ k ( d n + 1 / 2 ) ∣ A − ( G ^ , G ⋆ ) ∣ . \frac{1}{2}\min_{k}\omega_k\lambda_k\lvert\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\le\max_{k}\omega_k\lambda_k(d_n+1/2)\lvert\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert. 2 1 k min ω k λ k ∣ A + ( G , G ⋆ )∣ ≤ k max ω k λ k ( d n + 1/2 ) ∣ A − ( G , G ⋆ )∣ .
Therefore,
∣ A + ( G ^ , G ⋆ ) ∣ ≤ ( 2 d n + 1 ) max k ω k λ k min k ω k λ k q − ≤ C ( 2 d n + 1 ) q − . \lvert\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\le(2d_n+1)\frac{\max_k\omega_k\lambda_k}{\min_k\omega_k\lambda_k}q^{-}\le C(2d_n+1)q^{-}. ∣ A + ( G , G ⋆ )∣ ≤ ( 2 d n + 1 ) min k ω k λ k max k ω k λ k q − ≤ C ( 2 d n + 1 ) q − .
Hence,
∣ A ( G ^ , G ⋆ ) ∣ ≤ ( 1 + C ( 2 d n + 1 ) ) q − . \lvert\mathcal{A}(\widehat{\mathcal{G}},\mathcal{G}^{\star})\rvert\le(1+C(2d_n+1))q^{-}. ∣ A ( G , G ⋆ )∣ ≤ ( 1 + C ( 2 d n + 1 )) q − .
□
Proof of Proposition 14. Let T k j : = N ( j , π S k ( G ) ) T_{kj}:=N(j,\pi_{S_k}(\mathcal{G})) T k j := N ( j , π S k ( G )) , T k j ⋆ : = N ( j , π S k ( G ⋆ ) ) T_{kj}^{\star}:=N(j,\pi_{S_k}(\mathcal{G}^{\star})) T k j ⋆ := N ( j , π S k ( G ⋆ )) , M k j = T k j ⋆ ∖ T k j M_{kj}=T_{kj}^{\star}\setminus T_{kj} M k j = T k j ⋆ ∖ T k j and Σ M k j ∣ T k j ( k ) \Sigma_{M_{kj}\mid T_{kj}}^{(k)} Σ M k j ∣ T k j ( k ) be the conditional covariance of X M k j ( k ) X_{M_{kj}}^{(k)} X M k j ( k ) conditioned on X T k j ⋆ ( k ) X_{T_{kj}^{\star}}^{(k)} X T k j ⋆ ( k ) .
Suppose for any k ∈ [ K ] k\in[K] k ∈ [ K ] and i ∈ S k i\in S_k i ∈ S k , N ( i , π S k ( G ⋆ ) ) ⊈ N ( i , π S k ( G ^ ) ) N(i,\pi_{S_k}(\mathcal{G}^{\star}))\not\subseteq N(i,\pi_{S_k}(\widehat{\mathcal{G}})) N ( i , π S k ( G ⋆ )) ⊆ N ( i , π S k ( G )) . Then, we have by Lemma 15
δ k i ( q ) ≤ L ( G ^ ) − L ( G ⋆ ) ≤ L ^ ( G ^ ) − L ^ ( G ⋆ ) + ∑ ( l , m ) ∈ A ( G ^ , G ⋆ ) C ‾ ω l ε n , l = [ L ^ ( G ^ ) + 2 ∑ k λ k ω k ∣ E ( π S k ( G ^ ) ) ∣ ] − [ L ^ ( G ⋆ ) + 2 ∑ k λ k ω k ∣ E ( π S k ( G ⋆ ) ) ∣ ] \begin{aligned}
\delta_{ki}(q)\le\mathcal{L}(\widehat{\mathcal{G}})-\mathcal{L}(\mathcal{G}^{\star}) \\
&\le\widehat{\mathcal{L}}(\widehat{\mathcal{G}})-\widehat{\mathcal{L}}(\mathcal{G}^{\star})+\sum_{(l,m)\in\mathcal{A}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\overline{C}\omega_l\varepsilon_{n,l} \\
&=\left[\widehat{\mathcal{L}}(\widehat{\mathcal{G}})+2\sum_k\lambda_k\omega_k\lvert E(\pi_{S_k}(\widehat{\mathcal{G}}))\rvert\right]-\left[\widehat{\mathcal{L}}(\mathcal{G}^{\star})+2\sum_k\lambda_k\omega_k\lvert E(\pi_{S_k}(\mathcal{G}^{\star}))\rvert\right]
\end{aligned} δ k i ( q ) ≤ L ( G ) − L ( G ⋆ ) ≤ L ( G ) − L ( G ⋆ ) + ( l , m ) ∈ A ( G , G ⋆ ) ∑ C ω l ε n , l = [ L ( G ) + 2 k ∑ λ k ω k ∣ E ( π S k ( G ))∣ ] − [ L ( G ⋆ ) + 2 k ∑ λ k ω k ∣ E ( π S k ( G ⋆ ))∣ ]
− 2 ∑ k λ k ω k ( ∣ E ( π S k ( G ^ ) ) ∣ − ∣ E ( π S k ( G ⋆ ) ) ∣ ) + ∑ ( l , m ) ∈ A ( G ^ , G ⋆ ) C ‾ ω l ε n , l ≤ ∑ ( l , m ) ∈ A − ( G ^ , G ⋆ ) d n ω l λ l − ∑ ( l , m ) ∈ A + ( G ^ , G ⋆ ) ω l λ l + ∑ ( l , m ) ∈ A ( G ^ , G ⋆ ) C ‾ ω l ε n , l . \begin{aligned}
\quad-2\sum_k\lambda_k\omega_k\left(\lvert E(\pi_{S_k}(\widehat{\mathcal{G}}))\rvert-\lvert E(\pi_{S_k}(\mathcal{G}^{\star}))\rvert\right)+\sum_{(l,m)\in\mathcal{A}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\overline{C}\omega_l\varepsilon_{n,l} \\
&\le\sum_{(l,m)\in\mathcal{A}^{-}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}d_n\omega_l\lambda_l-\sum_{(l,m)\in\mathcal{A}^{+}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\omega_l\lambda_l+\sum_{(l,m)\in\mathcal{A}(\widehat{\mathcal{G}},\mathcal{G}^{\star})}\overline{C}\omega_l\varepsilon_{n,l}.
\end{aligned} − 2 k ∑ λ k ω k ( ∣ E ( π S k ( G ))∣ − ∣ E ( π S k ( G ⋆ ))∣ ) + ( l , m ) ∈ A ( G , G ⋆ ) ∑ C ω l ε n , l ≤ ( l , m ) ∈ A − ( G , G ⋆ ) ∑ d n ω l λ l − ( l , m ) ∈ A + ( G , G ⋆ ) ∑ ω l λ l + ( l , m ) ∈ A ( G , G ⋆ ) ∑ C ω l ε n , l .
The second inequality follows from Lemma 15, and the final inequality follows from the optimality of G ^ \widehat{\mathcal{G}} G . Since, by the condition of Proposition 13:
ω l λ l ≥ 2 C ‾ ω l ε n , l , \omega_l\lambda_l\ge2\overline{C}\omega_l\varepsilon_{n,l}, ω l λ l ≥ 2 C ω l ε n , l ,
we have from the inequality above:
δ k i ( q ) ≤ ( d n + 1 / 2 ) q max l ω l λ l . \delta_{ki}(q)\le(d_n+1/2)q\max_l\omega_l\lambda_l. δ k i ( q ) ≤ ( d n + 1/2 ) q l max ω l λ l .
This however contradicts the assumption of Proposition 14. So we conclude that π S k ( G ⋆ ) \pi_{S_k}(\mathcal{G}^{\star}) π S k ( G ⋆ ) is a subgraph of π S k ( G ^ ) \pi_{S_k}(\widehat{\mathcal{G}}) π S k ( G ) .
Finally, we need to argue that π S k ( G ^ ) = π S k ( G ⋆ ) \pi_{S_k}(\widehat{G}) = \pi_{S_k}(G^\star) π S k ( G ) = π S k ( G ⋆ ) . We have that A − ( G ^ , G ⋆ ) = ∅ \mathcal{A}^{-}(\widehat{G},G^\star) = \varnothing A − ( G , G ⋆ ) = ∅ . Thus, inequality (17) gives
0 ≥ L ( G ^ ) − L ( G ⋆ ) + ∑ ( l , m ) ∈ A + ( G ^ , G ⋆ ) ( ω l λ l − C ω ‾ l ε n , l ) ≥ 1 2 ∑ ( l , m ) ∈ A + ( G ^ , G ⋆ ) ω l λ l ≥ 0 , 0 \ge\mathcal{L}(\widehat{G})-\mathcal{L}(G^\star)+\sum_{(l,m)\in\mathcal{A}^{+}(\widehat{G},G^\star)}(\omega_l\lambda_l-C\overline{\omega}_l\varepsilon_{n,l})\ge\frac{1}{2}\sum_{(l,m)\in\mathcal{A}^{+}(\widehat{G},G^\star)}\omega_l\lambda_l\ge0, 0 ≥ L ( G ) − L ( G ⋆ ) + ( l , m ) ∈ A + ( G , G ⋆ ) ∑ ( ω l λ l − C ω l ε n , l ) ≥ 2 1 ( l , m ) ∈ A + ( G , G ⋆ ) ∑ ω l λ l ≥ 0 ,
where the second inequality uses L ( G ^ ) − L ( G ⋆ ) ≥ 0 \mathcal{L}(\widehat{G})-\mathcal{L}(G^\star)\ge0 L ( G ) − L ( G ⋆ ) ≥ 0 and ω l λ l ≥ 2 C ω ‾ l ε n , l \omega_l\lambda_l\ge2C\overline{\omega}_l\varepsilon_{n,l} ω l λ l ≥ 2 C ω l ε n , l . Since ω l λ l > 0 \omega_l\lambda_l>0 ω l λ l > 0 for every l l l , this implies A + ( G ^ , G ⋆ ) = ∅ \mathcal{A}^{+}(\widehat{G},G^\star)=\varnothing A + ( G , G ⋆ ) = ∅ . We conclude that π S k ( G ^ ) = π S k ( G ⋆ ) \pi_{S_k}(\widehat{G})=\pi_{S_k}(G^\star) π S k ( G ) = π S k ( G ⋆ ) for every k ∈ [ K ] k\in[K] k ∈ [ K ] .
Proof of Proposition 12
Proof. Let
s min : = κ min min k { ω k β k , min 2 } . s_{\min}:=\kappa_{\min}\min_{k}\{\omega_k\beta_{k,\min}^{2}\}. s m i n := κ m i n k min { ω k β k , m i n 2 } .
For any G ∈ G \mathcal{G}\in\mathbb{G} G ∈ G , every pair ( l , m ) ∈ A − ( G , G ⋆ ) ∖ W (l,m)\in\mathcal{A}^{-}(\mathcal{G},G^\star)\setminus\mathcal{W} ( l , m ) ∈ A − ( G , G ⋆ ) ∖ W omits at least one true neighbor. Hence, building on the results in Remark 6, by the definition of β l , min \beta_{l,\min} β l , m i n and the lower eigenvalue bound,
ω l { L l m ( G ) − L l m ( G ⋆ ) } ≥ κ min ω l β l , min 2 ≥ s min . \omega_l\{\mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(G^\star)\}\ge\kappa_{\min}\omega_l\beta_{l,\min}^{2}\ge s_{\min}. ω l { L l m ( G ) − L l m ( G ⋆ )} ≥ κ m i n ω l β l , m i n 2 ≥ s m i n .
Since at most ∣ W ∣ |\mathcal{W}| ∣ W ∣ elements of A − ( G , G ⋆ ) \mathcal{A}^{-}(\mathcal{G},G^\star) A − ( G , G ⋆ ) belong to W \mathcal{W} W , it follows that
L ( G ) − L ( G ⋆ ) ≥ s min ( ∣ A − ( G , G ⋆ ) ∣ − ∣ W ∣ ) + . \mathcal{L}(\mathcal{G})-\mathcal{L}(G^\star)\ge s_{\min}\left(|\mathcal{A}^{-}(\mathcal{G},G^\star)|-|\mathcal{W}|\right)_{+}. L ( G ) − L ( G ⋆ ) ≥ s m i n ( ∣ A − ( G , G ⋆ ) ∣ − ∣ W ∣ ) + .
Recall:
Γ − ( r ) : = inf G ∈ G : ∣ A − ( G , G ⋆ ) ∣ ≥ r L ( G ) − L ( G ⋆ ) ∣ A − ( G , G ⋆ ) ∣ . \Gamma^{-}(r):=\inf_{\mathcal{G}\in\mathbb{G}:|\mathcal{A}^{-}(\mathcal{G},G^\star)|\ge r}\frac{\mathcal{L}(\mathcal{G})-\mathcal{L}(G^\star)}{|\mathcal{A}^{-}(\mathcal{G},G^\star)|}. Γ − ( r ) := G ∈ G : ∣ A − ( G , G ⋆ ) ∣ ≥ r inf ∣ A − ( G , G ⋆ ) ∣ L ( G ) − L ( G ⋆ ) .
Therefore, for every r > ∣ W ∣ r>|\mathcal{W}| r > ∣ W ∣ ,
Γ − ( r ) ≥ s min ( 1 − ∣ W ∣ r ) . \Gamma^{-}(r)\ge s_{\min}\left(1-\frac{|\mathcal{W}|}{r}\right). Γ − ( r ) ≥ s m i n ( 1 − r ∣ W ∣ ) .
By the assumption of the proposition,
s min > 2 ( d n + 1 / 2 ) max k ∈ [ K ] ω k λ k . s_{\min}>2(d_n+1/2)\max_{k\in[K]}\omega_k\lambda_k. s m i n > 2 ( d n + 1/2 ) k ∈ [ K ] max ω k λ k .
Set r 0 : = 2 ∣ W ∣ + 1 r_0:=2|\mathcal{W}|+1 r 0 := 2∣ W ∣ + 1 . Then
Γ − ( r 0 ) ≥ s min ( 1 − ∣ W ∣ r 0 ) > s min 2 > ( d n + 1 / 2 ) max k ∈ [ K ] ω k λ k . \Gamma^{-}(r_0)\ge s_{\min}\left(1-\frac{|\mathcal{W}|}{r_0}\right)>\frac{s_{\min}}{2}>(d_n+1/2)\max_{k\in[K]}\omega_k\lambda_k. Γ − ( r 0 ) ≥ s m i n ( 1 − r 0 ∣ W ∣ ) > 2 s m i n > ( d n + 1/2 ) k ∈ [ K ] max ω k λ k .
Thus, r 0 r_0 r 0 satisfies the threshold condition in the definition of q min q_{\min} q m i n , and therefore
q min ≤ r 0 ( 1 + C ( 2 d n + 1 ) ) = ( 2 ∣ W ∣ + 1 ) ( 1 + C ( 2 d n + 1 ) ) = : q 0 . q_{\min}\le r_0(1+C(2d_n+1))=(2|\mathcal{W}|+1)(1+C(2d_n+1))=:q_0. q m i n ≤ r 0 ( 1 + C ( 2 d n + 1 )) = ( 2∣ W ∣ + 1 ) ( 1 + C ( 2 d n + 1 )) =: q 0 .
Since δ k j ( q ) \delta_{kj}(q) δ k j ( q ) is nonincreasing in q q q , we have:
δ k , min = min j ∈ S k δ k j ( q min ) ≥ min j ∈ S k δ k j ( q 0 ) . \delta_{k,\min}=\min_{j\in S_k}\delta_{kj}(q_{\min})\ge\min_{j\in S_k}\delta_{kj}(q_0). δ k , m i n = j ∈ S k min δ k j ( q m i n ) ≥ j ∈ S k min δ k j ( q 0 ) .
Since all loss differences L l m ( G ) − L l m ( G ⋆ ) \mathcal{L}_{lm}(\mathcal{G})-\mathcal{L}_{lm}(G^\star) L l m ( G ) − L l m ( G ⋆ ) are nonnegative for ( l , m ) ∈ A − ( G , G ⋆ ) (l,m)\in\mathcal{A}^{-}(\mathcal{G},G^\star) ( l , m ) ∈ A − ( G , G ⋆ ) , we have:
δ k j ( q 0 ) ≥ inf G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q 0 N ( j , π S k ( G ⋆ ) ) ⊈ N ( j , π S k ( G ) ) ∑ ( l , m ) ∈ A − ( G , G ⋆ ) ( l , m ) ∉ W κ min ω l β l , min 2 . \delta_{kj}(q_0)\ge\inf_{\substack{\mathcal{G}\in\mathbb{G},\ |\mathcal{A}^{-}(\mathcal{G},G^\star)|\le q_0\\N(j,\pi_{S_k}(G^\star))\not\subseteq N(j,\pi_{S_k}(\mathcal{G}))}}\sum_{\substack{(l,m)\in\mathcal{A}^{-}(\mathcal{G},G^\star)\\(l,m)\notin\mathcal{W}}}\kappa_{\min}\omega_l\beta_{l,\min}^{2}. δ k j ( q 0 ) ≥ G ∈ G , ∣ A − ( G , G ⋆ ) ∣ ≤ q 0 N ( j , π S k ( G ⋆ )) ⊆ N ( j , π S k ( G )) inf ( l , m ) ∈ A − ( G , G ⋆ ) ( l , m ) ∈ / W ∑ κ m i n ω l β l , m i n 2 .
Taking the minimum over j ∈ S k j\in S_k j ∈ S k yields the claimed result.
Perspective strengthening
Let δ k ∈ R + + ∣ S k ∣ \delta^k \in\mathbb{R}_{++}^{|S_k|} δ k ∈ R ++ ∣ S k ∣ be a strictly positive vector with the property that Σ ^ k − D δ k ⪰ 0 \widehat{\Sigma}_k-D_{\delta^k}\succeq0 Σ k − D δ k ⪰ 0 where D δ k = diag ( δ 1 k , … , δ ∣ S k ∣ k ) D_{\delta^k}=\operatorname{diag}(\delta^k_1,\ldots,\delta^k_{|S_k|}) D δ k = diag ( δ 1 k , … , δ ∣ S k ∣ k ) .
By splitting the quadratic term, we have ( I − Θ ( k ) ) T Σ ^ k ( I − Θ ( k ) ) = ( I − Θ ( k ) ) T Q k ( I − Θ ( k ) ) + ( I − Θ ( k ) ) T D δ k ( I − Θ ( k ) ) (I-\Theta^{(k)})^{\mathsf{T}}\widehat{\Sigma}_k(I-\Theta^{(k)})=(I-\Theta^{(k)})^{\mathsf{T}}Q_k(I-\Theta^{(k)})+(I-\Theta^{(k)})^{\mathsf{T}}D_{\delta^k}(I-\Theta^{(k)}) ( I − Θ ( k ) ) T Σ k ( I − Θ ( k ) ) = ( I − Θ ( k ) ) T Q k ( I − Θ ( k ) ) + ( I − Θ ( k ) ) T D δ k ( I − Θ ( k ) ) where Q k : = Σ ^ k − D δ k ⪰ 0 Q_k:=\widehat{\Sigma}_k-D_{\delta^k}\succeq0 Q k := Σ k − D δ k ⪰ 0 . Note we can replace tr ( ( I − Θ ( k ) ) T D δ k ( I − Θ ( k ) ) ) \operatorname{tr}((I-\Theta^{(k)})^{\mathsf{T}}D_{\delta^k}(I-\Theta^{(k)})) tr (( I − Θ ( k ) ) T D δ k ( I − Θ ( k ) )) with ∑ i , j ∈ S k , i ≠ j ( Θ i j ( k ) ) 2 δ i k + ∑ i ∈ S k δ i k \sum_{i,j\in S_k,i\ne j}(\Theta^{(k)}_{ij})^2\delta^k_i+\sum_{i\in S_k}\delta^k_i ∑ i , j ∈ S k , i = j ( Θ ij ( k ) ) 2 δ i k + ∑ i ∈ S k δ i k . We can then obtain the following equivalent formulation:
argmin ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) Θ ( k ) ∈ R ∣ S k ∣ × ∣ S k ∣ ∀ k ∈ [ K ] Θ i i ( k ) = 0 ∀ k ∈ [ K ] , i ∈ S k ∑ k = 1 K ω k [ tr ( ( I − Θ ( k ) ) T Q k ( I − Θ ( k ) ) ) + ∑ i , j ∈ S k i ≠ j ( Θ i j ( k ) ) 2 δ i k h min { i , j } , max { i , j } ( k ) + 2 λ k ∑ i , j ∈ S k i < j h i j ( k ) ] , (19) \underset{\substack{(g,h,f,m)\in\mathcal{F}(\{S_k\}_{k=1}^{K})\\ \Theta^{(k)}\in\mathbb{R}^{|S_k|\times|S_k|}\ \forall k\in[K]\\ \Theta^{(k)}_{ii}=0\ \forall k\in[K],i\in S_k}}{\operatorname{argmin}}\
\sum_{k=1}^{K}\omega_k\left[\operatorname{tr}\left((I-\Theta^{(k)})^{\mathsf{T}}Q_k(I-\Theta^{(k)})\right)+\sum_{\substack{i,j\in S_k\\i\ne j}}\frac{(\Theta^{(k)}_{ij})^2\delta^k_i}{h^{(k)}_{\min\{i,j\},\max\{i,j\}}}+2\lambda_k\sum_{\substack{i,j\in S_k\\i<j}}h^{(k)}_{ij}\right], \tag*{(19)} ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) Θ ( k ) ∈ R ∣ S k ∣ × ∣ S k ∣ ∀ k ∈ [ K ] Θ ii ( k ) = 0 ∀ k ∈ [ K ] , i ∈ S k argmin k = 1 ∑ K ω k tr ( ( I − Θ ( k ) ) T Q k ( I − Θ ( k ) ) ) + i , j ∈ S k i = j ∑ h m i n { i , j } , m a x { i , j } ( k ) ( Θ ij ( k ) ) 2 δ i k + 2 λ k i , j ∈ S k i < j ∑ h ij ( k ) , (19)
subject-to: ( g , h , f , m ) (g,h,f,m) ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] \forall k\in[K] ∀ k ∈ [ K ] .
We have omitted the graph-independent additive constant ∑ k = 1 K ω k ∑ i ∈ S k δ i k \sum_{k=1}^{K}\omega_k\sum_{i\in S_k}\delta^k_i ∑ k = 1 K ω k ∑ i ∈ S k δ i k , which does not affect the optimizers. Here, in the ratios of the form ( Θ i j ( k ) ) 2 δ i k / h i j ( k ) (\Theta^{(k)}_{ij})^2\delta^k_i/h^{(k)}_{ij} ( Θ ij ( k ) ) 2 δ i k / h ij ( k ) , we adopt the convention that 0 / 0 = 0 0/0=0 0/0 = 0 . Since the perspective of a convex quadratic is convex, each term ( Θ i j ( k ) ) 2 δ i k / h min { i , j } , max { i , j } ( k ) (\Theta^{(k)}_{ij})^2\delta^k_i/h^{(k)}_{\min\{i,j\},\max\{i,j\}} ( Θ ij ( k ) ) 2 δ i k / h m i n { i , j } , m a x { i , j } ( k ) is jointly convex over Θ ( k ) \Theta^{(k)} Θ ( k ) and h ( k ) h^{(k)} h ( k ) . Thus, (19) is a convex mixed-integer program.
To establish that (19) and (12) have the same optimizers, first note that h i j ( k ) = 0 h^{(k)}_{ij}=0 h ij ( k ) = 0 necessarily implies Θ i j ( k ) = Θ j i ( k ) = 0 \Theta^{(k)}_{ij}=\Theta^{(k)}_{ji}=0 Θ ij ( k ) = Θ j i ( k ) = 0 at the optimum of (19). Moreover, since h i j ( k ) ∈ { 0 , 1 } h^{(k)}_{ij}\in\{0,1\} h ij ( k ) ∈ { 0 , 1 } , for such feasible h ( k ) h^{(k)} h ( k ) and Θ ( k ) \Theta^{(k)} Θ ( k ) , we have that for h ( k ) h^{(k)} h ( k ) and Θ ( k ) \Theta^{(k)} Θ ( k ) satisfying h i j ( k ) = 0 ⇒ Θ i j ( k ) = Θ j i ( k ) = 0 h^{(k)}_{ij}=0\Rightarrow\Theta^{(k)}_{ij}=\Theta^{(k)}_{ji}=0 h ij ( k ) = 0 ⇒ Θ ij ( k ) = Θ j i ( k ) = 0 : ( Θ i j ( k ) ) 2 δ i k / h i j ( k ) = ( Θ i j ( k ) ) 2 δ i k (\Theta^{(k)}_{ij})^2\delta^k_i/h^{(k)}_{ij}=(\Theta^{(k)}_{ij})^2\delta^k_i ( Θ ij ( k ) ) 2 δ i k / h ij ( k ) = ( Θ ij ( k ) ) 2 δ i k . Hence, the two formulations are equivalent. However, the continuous relaxation of (19), obtained by replacing the binary domains of g g g and h h h , yields a tighter lower bound. Indeed, for h i j ( k ) ∈ ( 0 , 1 ] h^{(k)}_{ij}\in(0,1] h ij ( k ) ∈ ( 0 , 1 ] , ( Θ i j ( k ) ) 2 δ i k / h i j ( k ) ≥ ( Θ i j ( k ) ) 2 δ i k (\Theta^{(k)}_{ij})^2\delta^k_i/h^{(k)}_{ij}\ge(\Theta^{(k)}_{ij})^2\delta^k_i ( Θ ij ( k ) ) 2 δ i k / h ij ( k ) ≥ ( Θ ij ( k ) ) 2 δ i k . Since larger δ \delta δ results in a tighter lower bound, we choose δ \delta δ by maximizing ∑ i δ i k \sum_i\delta^k_i ∑ i δ i k subject to Σ ^ k − D δ ⪰ 0 \widehat{\Sigma}_k-D_\delta\succeq0 Σ k − D δ ⪰ 0 for δ i k > ϵ \delta^k_i>\epsilon δ i k > ϵ , i = 1 , … , ∣ S k ∣ i=1,\ldots,|S_k| i = 1 , … , ∣ S k ∣ , for some small ϵ > 0 \epsilon>0 ϵ > 0 . This is a convex semidefinite program that can be solved efficiently.
To reduce the number of continuous variables, we can project out the continuous variables Θ ( k ) \Theta^{(k)} Θ ( k ) and obtain a convex MIP over fewer variables. Specifically, minimizing over Θ ( k ) \Theta^{(k)} Θ ( k ) , k ∈ [ K ] k\in[K] k ∈ [ K ] , we obtain the following MIP:
argmin ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) t k j ∈ R ∀ k ∈ [ K ] , j ∈ S k ∑ k = 1 K ω k [ ∑ j ∈ S k t k j + 2 λ k ∑ i , j ∈ S k i < j h i j ( k ) ] , (20) \underset{\substack{(g,h,f,m)\in\mathcal{F}(\{S_k\}_{k=1}^{K})\\ t_{kj}\in\mathbb{R}\ \forall k\in[K],j\in S_k}}{\operatorname{argmin}}\
\sum_{k=1}^{K}\omega_k\left[\sum_{j\in S_k}t_{kj}+2\lambda_k\sum_{\substack{i,j\in S_k\\i<j}}h^{(k)}_{ij}\right], \tag*{(20)} ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) t k j ∈ R ∀ k ∈ [ K ] , j ∈ S k argmin k = 1 ∑ K ω k j ∈ S k ∑ t k j + 2 λ k i , j ∈ S k i < j ∑ h ij ( k ) , (20)
subject-to: ( g , h , f , m ) (g,h,f,m) ( g , h , f , m ) satisfy the linear constraints in (10) and (11) ∀ k ∈ [ K ] \forall k\in[K] ∀ k ∈ [ K ] ,
t k j ≥ F k j ( h ( k ) ) ∀ k ∈ [ K ] , j ∈ S k t_{kj}\ge F_{kj}(h^{(k)})\ \forall k\in[K],j\in S_k t k j ≥ F k j ( h ( k ) ) ∀ k ∈ [ K ] , j ∈ S k ,
where
F k j ( h ( k ) ) : = { ( Q k + diag i ∈ S k ( { δ i k h min { i , j } , max { i , j } ( k ) , i ≠ j , 0 , i = j ) ) − 1 } j j − 1 . F_{kj}(h^{(k)}):=\left\{\left(Q_k+\operatorname{diag}_{i\in S_k}\left(\left\{\begin{array}{ll}
\dfrac{\delta^k_i}{h^{(k)}_{\min\{i,j\},\max\{i,j\}}}, & i\ne j,\\
0, & i=j
\end{array}\right.\right)\right)^{-1}\right\}_{jj}^{-1}. F k j ( h ( k ) ) := ⎩ ⎨ ⎧ Q k + diag i ∈ S k ⎩ ⎨ ⎧ h m i n { i , j } , m a x { i , j } ( k ) δ i k , 0 , i = j , i = j − 1 ⎭ ⎬ ⎫ j j − 1 .
Since each F k j ( h ( k ) ) F_{kj}(h^{(k)}) F k j ( h ( k ) ) is obtained by partial minimization of a jointly convex function, it is convex. Thus, (20) is a convex MIP. We use outer approximation to solve (20), a cutting-plane method that finds the optimal solution by constructing a sequence of piecewise-affine lower bounds of each F k j ( h ( k ) ) F_{kj}(h^{(k)}) F k j ( h ( k ) ) using the first-order condition for convex functions. Specifically, at each candidate h ˉ ( k ) \bar{h}^{(k)} h ˉ ( k ) , we evaluate the nodewise terms and add the supporting-hyperplane cut t k j ≥ F k j ( h ˉ ( k ) ) + ∇ F k j ( h ˉ ( k ) ) T ( h ( k ) − h ˉ ( k ) ) t_{kj}\ge F_{kj}(\bar{h}^{(k)})+\nabla F_{kj}(\bar{h}^{(k)})^{\mathsf{T}}(h^{(k)}-\bar{h}^{(k)}) t k j ≥ F k j ( h ˉ ( k ) ) + ∇ F k j ( h ˉ ( k ) ) T ( h ( k ) − h ˉ ( k ) ) for each violated epigraph constraint. These cuts progressively refine the mixed-integer linear relaxation within a single branch-and-bound search, which terminates when the prescribed optimality tolerance or time limit is reached.
Appendix C. Convex MIP for Example 7
With the loss (7)
For the loss (7), we restrict attention to chordal graphs G \mathcal{G} G , in which every cycle of length at least four has a chord. Since latent projection preserves chordality, π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) is chordal whenever G \mathcal{G} G is chordal. The chordal restriction results in improved tractability of solving (4) for discrete graphical models. In particular, we use the property that a graph is chordal if and only if it has a perfect elimination ordering (Fulkerson & Gross 1965). A perfect elimination ordering of G = ( V , E ) \mathcal{G}=(V,E) G = ( V , E ) is an injective map σ : V → R \sigma:V\to\mathbb{R} σ : V → R where σ ( i ) < σ ( j ) \sigma(i)<\sigma(j) σ ( i ) < σ ( j ) means that vertex i i i appears before vertex j j j . The ordering is a perfect elimination ordering if, for every i ∈ V i\in V i ∈ V , its later neighbors,
N i ( G , σ ) : = { j ∈ V : { i , j } ∈ E , σ ( j ) > σ ( i ) } , N_i(\mathcal{G},\sigma):=\{j\in V:\{i,j\}\in E,\ \sigma(j)>\sigma(i)\}, N i ( G , σ ) := { j ∈ V : { i , j } ∈ E , σ ( j ) > σ ( i )} ,
form a clique. Fix any such perfect elimination ordering σ \sigma σ . Then,
min θ ( k ) ∈ Θ k ( G ~ ) ℓ ~ k ( θ ( k ) ; D k ) = ∑ i ∈ S k H ^ ( X i ∣ X N i ( G ~ , σ ) ) , \min_{\theta^{(k)}\in\Theta_k(\widetilde{\mathcal{G}})}\widetilde{\ell}_k(\theta^{(k)};\mathcal{D}_k)=\sum_{i\in S_k}\widehat{H}(X_i\mid X_{N_i(\widetilde{\mathcal{G}},\sigma)}), θ ( k ) ∈ Θ k ( G ) min ℓ k ( θ ( k ) ; D k ) = i ∈ S k ∑ H ( X i ∣ X N i ( G , σ ) ) ,
where for any A ⊆ S k A\subseteq S_k A ⊆ S k , H ^ ( X i ∣ X A ) \widehat{H}(X_i\mid X_A) H ( X i ∣ X A ) computes the conditional entropy of X i X_i X i conditioned on X A X_A X A using the empirical distribution P ^ S k ( k ) \widehat{P}_{S_k}^{(k)} P S k ( k ) . Thus, (4) can be reformulated here as:
argmin G , { σ j ( k ) ∈ [ 1 , ∣ S k ∣ ] } j ∈ S k , k ∈ W 1 ∑ k ∈ W 1 ω k [ ∑ i ∈ S k H ^ ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) + log ( n k ) 2 n k dim ( Θ k ( π S k ( G ) ) ) ] + γ ∑ k ∈ W 2 ω k SHD ( π S k ( G ) , G ^ S k ( k ) ) (21) \begin{aligned}
\underset{\mathcal{G},\{\sigma_j^{(k)}\in[1,|S_k|]\}_{j\in S_k,k\in\mathcal{W}_1}}{\operatorname{argmin}}\quad
&\sum_{k\in\mathcal{W}_1}\omega_k\left[\sum_{i\in S_k}\widehat{H}\left(X_i\mid X_{N_i(\pi_{S_k}(\mathcal{G}),\sigma^{(k)})}\right)+\frac{\log(n_k)}{2n_k}\dim\left(\Theta_k(\pi_{S_k}(\mathcal{G}))\right)\right]\\
&+\gamma\sum_{k\in\mathcal{W}_2}\omega_k\operatorname{SHD}\left(\pi_{S_k}(\mathcal{G}),\widehat{\mathcal{G}}_{S_k}^{(k)}\right) \tag*{(21)}
\end{aligned} G , { σ j ( k ) ∈ [ 1 , ∣ S k ∣ ] } j ∈ S k , k ∈ W 1 argmin k ∈ W 1 ∑ ω k [ i ∈ S k ∑ H ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) + 2 n k log ( n k ) dim ( Θ k ( π S k ( G )) ) ] + γ k ∈ W 2 ∑ ω k SHD ( π S k ( G ) , G S k ( k ) ) (21)
subject to σ ( k ) \sigma^{(k)} σ ( k ) induces a perfect elimination ordering of π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) , k ∈ W 1 k\in\mathcal{W}_1 k ∈ W 1 .
Where dim ( Θ k ( π S k ( G ) ) \dim(\Theta_k(\pi_{S_k}(\mathcal{G})) dim ( Θ k ( π S k ( G )) is described in Section 3.3. To cast (21) as a convex MIP, on top of reformulating latent projections via (10) and (11), we must formulate three combinatorial features: (i) the constraint (21b) that σ ( k ) \sigma^{(k)} σ ( k ) is a perfect elimination ordering of π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) , (ii) the entropy function H ^ ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) \widehat{H}(X_i\mid X_{N_i(\pi_{S_k}(\mathcal{G}),\sigma^{(k)})}) H ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) in the objective (21a), and (iii) dim ( Θ k ( π S k ( G ) ) \dim(\Theta_k(\pi_{S_k}(\mathcal{G})) dim ( Θ k ( π S k ( G )) in the objective (21a). We first handle constraint (21b). Let h ( k ) h^{(k)} h ( k ) be the binary variables encoding the graph π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) . Then, (21b) can be equivalently expressed as:
Constraint (21b) ⟺ ∃ { d i j ( k ) ∈ { 0 , 1 } } i < j , { d j i ( k ) ∈ [ 0 , 1 ] } i < j , i , j ∈ S k , such that: d j i ( k ) = h i j ( k ) − d i j ( k ) , ∀ i < j , σ j ( k ) ≥ σ i ( k ) + 1 − ∣ S k ∣ ( 1 − d i j ( k ) ) , ∀ i ≠ j , d i j ( k ) + d i m ( k ) ≤ 1 + h j m ( k ) , ∀ i , j , m ∈ S k distinct. (22) \begin{aligned}
\text{Constraint (21b)}\quad\Longleftrightarrow\quad&\exists\ \{d_{ij}^{(k)}\in\{0,1\}\}_{i<j},\{d_{ji}^{(k)}\in[0,1]\}_{i<j},\ i,j\in S_k,\ \text{such that:}\\
&d_{ji}^{(k)}=h_{ij}^{(k)}-d_{ij}^{(k)}, &&\forall i<j,\\
&\sigma_j^{(k)}\geq\sigma_i^{(k)}+1-|S_k|(1-d_{ij}^{(k)}), &&\forall i\ne j,\\
&d_{ij}^{(k)}+d_{im}^{(k)}\leq1+h_{jm}^{(k)}, &&\forall i,j,m\in S_k\text{ distinct.} \tag*{(22)}
\end{aligned} Constraint (21b) ⟺ ∃ { d ij ( k ) ∈ { 0 , 1 } } i < j , { d j i ( k ) ∈ [ 0 , 1 ] } i < j , i , j ∈ S k , such that: d j i ( k ) = h ij ( k ) − d ij ( k ) , σ j ( k ) ≥ σ i ( k ) + 1 − ∣ S k ∣ ( 1 − d ij ( k ) ) , d ij ( k ) + d im ( k ) ≤ 1 + h j m ( k ) , ∀ i < j , ∀ i = j , ∀ i , j , m ∈ S k distinct. (22)
The first two constraints orient every edge of π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) according to the ordering induced by σ ( k ) \sigma^{(k)} σ ( k ) . The final constraint requires that any two later neighbors of a node be adjacent, thereby ensuring that σ ( k ) \sigma^{(k)} σ ( k ) induces a perfect elimination ordering of π S k ( G ) \pi_{S_k}(\mathcal{G}) π S k ( G ) . To handle the entropy function H ^ ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) \widehat{H}(X_i\mid X_{N_i(\pi_{S_k}(\mathcal{G}),\sigma^{(k)})}) H ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) in the constraint, we can replace it with a new continuous decision variable t i ( k ) t_i^{(k)} t i ( k ) and add the following set of constraints:
t i ( k ) ≥ H ^ ( X i ∣ X A ) − U i [ ∑ j ∈ A ( 1 − d i j ( k ) ) + ∑ j ∈ S k ∖ ( A ∪ { i } ) d i j ( k ) ] ∀ A ⊆ S k ∖ { i } (23) t_i^{(k)}\geq\widehat{H}(X_i\mid X_A)-U_i\left[\sum_{j\in A}(1-d_{ij}^{(k)})+\sum_{j\in S_k\setminus(A\cup\{i\})}d_{ij}^{(k)}\right]\qquad\forall A\subseteq S_k\setminus\{i\} \tag*{(23)} t i ( k ) ≥ H ( X i ∣ X A ) − U i j ∈ A ∑ ( 1 − d ij ( k ) ) + j ∈ S k ∖ ( A ∪ { i }) ∑ d ij ( k ) ∀ A ⊆ S k ∖ { i } (23)
where U i ≥ max A ⊆ S k ∖ { i } H ^ ( X i ∣ X A ) − min A ⊆ S k ∖ { i } H ^ ( X i ∣ X A ) U_i\geq\max_{A\subseteq S_k\setminus\{i\}}\widehat{H}(X_i\mid X_A)-\min_{A\subseteq S_k\setminus\{i\}}\widehat{H}(X_i\mid X_A) U i ≥ max A ⊆ S k ∖ { i } H ( X i ∣ X A ) − min A ⊆ S k ∖ { i } H ( X i ∣ X A ) . For any fixed selection of the variables d i j ( k ) d_{ij}^{(k)} d ij ( k ) , the bracketed term is zero precisely when A = N i ( π S k ( G ) , σ ( k ) ) A=N_i(\pi_{S_k}(\mathcal{G}),\sigma^{(k)}) A = N i ( π S k ( G ) , σ ( k ) ) and is at least one otherwise; hence the corresponding constraint reduces to t i ( k ) ≥ H ^ ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) t_i^{(k)}\geq\widehat{H}(X_i\mid X_{N_i(\pi_{S_k}(\mathcal{G}),\sigma^{(k)})}) t i ( k ) ≥ H ( X i ∣ X N i ( π S k ( G ) , σ ( k ) ) ) for the selected neighborhood, while the remaining constraints are rendered nonbinding by the choice of U i U_i U i . Note that if X i X_i X i could take on ∣ X i ∣ |\mathcal{X}_i| ∣ X i ∣ values, U i = log ∣ X i ∣ U_i=\log|\mathcal{X}_i| U i = log ∣ X i ∣ is a sufficient choice. Finally, it is straightforward to show that dim ( Θ k ( π S k ( G ) ) = \dim(\Theta_k(\pi_{S_k}(\mathcal{G}))= dim ( Θ k ( π S k ( G )) = ∑ i ∈ S k ( ∣ X i ∣ − 1 ) ∏ j ∈ S k ∖ { i } ∣ X j ∣ d i j ( k ) \sum_{i\in S_k}(|\mathcal{X}_i|-1)\prod_{j\in S_k\setminus\{i\}}|\mathcal{X}_j|^{d_{ij}^{(k)}} ∑ i ∈ S k ( ∣ X i ∣ − 1 ) ∏ j ∈ S k ∖ { i } ∣ X j ∣ d ij ( k ) , which induces a convex continuous relaxation. We thus arrive at the following convex mixed integer program:
argmin g , h , f , m , t , σ , d ∑ k ∈ W 1 ω k [ ∑ i ∈ S k t i ( k ) + log ( n k ) 2 n k ∑ i ∈ S k ( ∣ X i ∣ − 1 ) ∏ j ∈ S k ∖ { i } ∣ X j ∣ d i j ( k ) ] + γ ∑ k ∈ W 2 ω k ∑ i , j ∈ S k i < j ( 1 − 2 h ^ i j ( k ) ) h i j ( k ) subject to: ( g , h , f , m ) ∈ F ( { S k } k = 1 K ) , t ( k ) ∈ R ∣ S k ∣ , σ j ( k ) ∈ [ 1 , ∣ S k ∣ ] , d i j ( k ) ∈ { 0 , 1 } , d j i ( k ) ∈ [ 0 , 1 ] ∀ k ∈ W 1 , j ∈ S k , i < j ∈ S k , linear constraints (22) ∀ k ∈ W 1 , t i ( k ) ≥ H ^ ( X i ∣ X A ) − U i D i , A ( k ) ∀ i ∈ S k , A ⊆ S k ∖ { i } , k ∈ W 1 . (24) \begin{aligned}
\underset{g,h,f,m,t,\sigma,d}{\operatorname{argmin}}\quad
&\sum_{k\in W_1}\omega_k\left[\sum_{i\in S_k}t_i^{(k)}+\frac{\log(n_k)}{2n_k}\sum_{i\in S_k}(|\mathcal{X}_i|-1)\prod_{j\in S_k\setminus\{i\}}|\mathcal{X}_j|^{d_{ij}^{(k)}}\right]
+\gamma\sum_{k\in W_2}\omega_k\sum_{\substack{i,j\in S_k\\i<j}}(1-2\widehat{h}_{ij}^{(k)})h_{ij}^{(k)}\\
\text{subject to:}\quad
&(g,h,f,m)\in\mathcal{F}(\{S_k\}_{k=1}^{K}),\\
&t^{(k)}\in\mathbb{R}^{|S_k|},\ \sigma_j^{(k)}\in[1,|S_k|],\ d_{ij}^{(k)}\in\{0,1\},\ d_{ji}^{(k)}\in[0,1]\quad\forall k\in W_1,\ j\in S_k,\ i<j\in S_k,\\
&\text{linear constraints (22)}\quad\forall k\in W_1,\\
&t_i^{(k)}\geq\widehat{H}(X_i\mid X_A)-U_iD_{i,A}^{(k)}\quad\forall i\in S_k,\ A\subseteq S_k\setminus\{i\},\ k\in W_1. \tag*{(24)}
\end{aligned} g , h , f , m , t , σ , d argmin subject to: k ∈ W 1 ∑ ω k i ∈ S k ∑ t i ( k ) + 2 n k log ( n k ) i ∈ S k ∑ ( ∣ X i ∣ − 1 ) j ∈ S k ∖ { i } ∏ ∣ X j ∣ d ij ( k ) + γ k ∈ W 2 ∑ ω k i , j ∈ S k i < j ∑ ( 1 − 2 h ij ( k ) ) h ij ( k ) ( g , h , f , m ) ∈ F ({ S k } k = 1 K ) , t ( k ) ∈ R ∣ S k ∣ , σ j ( k ) ∈ [ 1 , ∣ S k ∣ ] , d ij ( k ) ∈ { 0 , 1 } , d j i ( k ) ∈ [ 0 , 1 ] ∀ k ∈ W 1 , j ∈ S k , i < j ∈ S k , linear constraints (22) ∀ k ∈ W 1 , t i ( k ) ≥ H ( X i ∣ X A ) − U i D i , A ( k ) ∀ i ∈ S k , A ⊆ S k ∖ { i } , k ∈ W 1 . (24)
where we use the shorthand notation D i , A ( k ) : = ∑ j ∈ A ( 1 − d i j ( k ) ) + ∑ j ∈ S k ∖ ( A ∪ { i } ) d i j ( k ) D_{i,A}^{(k)}:=\sum_{j\in A}(1-d_{ij}^{(k)})+\sum_{j\in S_k\setminus(A\cup\{i\})}d_{ij}^{(k)} D i , A ( k ) := ∑ j ∈ A ( 1 − d ij ( k ) ) + ∑ j ∈ S k ∖ ( A ∪ { i }) d ij ( k ) . The exponentially many constraints indexed by A ⊆ S k ∖ { i } A\subseteq S_k\setminus\{i\} A ⊆ S k ∖ { i } can be added lazily. At an incumbent solution, d i ( k ) d_i^{(k)} d i ( k ) determines the active set A i ( k ) : = { j : d i j ( k ) = 1 } A_i^{(k)}:=\{j:d_{ij}^{(k)}=1\} A i ( k ) := { j : d ij ( k ) = 1 } , for which D i , A i ( k ) ( k ) = 0 D_{i,A_i^{(k)}}^{(k)}=0 D i , A i ( k ) ( k ) = 0 . If t i ( k ) < H ^ ( X i ∣ X A i ( k ) ) t_i^{(k)}<\widehat{H}(X_i\mid X_{A_i^{(k)}}) t i ( k ) < H ( X i ∣ X A i ( k ) ) , the corresponding constraint is added and the optimization continues.
With the loss (8)
For any candidate neighborhood A ⊆ S k ∖ { i } A\subseteq S_k\setminus\{i\} A ⊆ S k ∖ { i } , define the local score
s i , A ( k ) : = H ^ ( X i ∣ X A ) + log ( n k ) 2 n k ( ∣ X i ∣ − 1 ) ∏ j ∈ A ∣ X j ∣ . s_{i,A}^{(k)}:=\widehat{H}(X_i\mid X_A)+\frac{\log(n_k)}{2n_k}(|\mathcal{X}_i|-1)\prod_{j\in A}|\mathcal{X}_j|. s i , A ( k ) := H ( X i ∣ X A ) + 2 n k log ( n k ) ( ∣ X i ∣ − 1 ) j ∈ A ∏ ∣ X j ∣.
Introduce variables z i , A ( k ) z_{i,A}^{(k)} z i , A ( k ) indicating whether A A A is selected as the neighborhood of node i i i , with
∑ A ⊆ S k ∖ { i } z i , A ( k ) = 1 , h i j ( k ) = ∑ A ⊆ S k ∖ { i } j ∈ A z i , A ( k ) . \sum_{A\subseteq S_k\setminus\{i\}}z_{i,A}^{(k)}=1,\qquad
h_{ij}^{(k)}=\sum_{\substack{A\subseteq S_k\setminus\{i\}\\j\in A}}z_{i,A}^{(k)}. A ⊆ S k ∖ { i } ∑ z i , A ( k ) = 1 , h ij ( k ) = A ⊆ S k ∖ { i } j ∈ A ∑ z i , A ( k ) .
The pseudo-likelihood contribution of source k k k can then be written as
∑ i ∈ S k ∑ A ⊆ S k ∖ { i } s i , A ( k ) z i , A ( k ) . \sum_{i\in S_k}\sum_{A\subseteq S_k\setminus\{i\}}s_{i,A}^{(k)}z_{i,A}^{(k)}. i ∈ S k ∑ A ⊆ S k ∖ { i } ∑ s i , A ( k ) z i , A ( k ) .
The local scores s i , A ( k ) s_{i,A}^{(k)} s i , A ( k ) can be precomputed for every candidate neighborhood A ⊆ S k ∖ { i } A\subseteq S_k\setminus\{i\} A ⊆ S k ∖ { i } . The optimization then only selects among these precomputed scores using binary variables z i , A ( k ) z_{i,A}^{(k)} z i , A ( k ) , while the latent-projection constraints enforce compatibility with a common global graph. This yields a mixed-integer linear program, and hence convex MIP. To avoid explicitly introducing all exponentially-many candidate neighborhoods, the variables and associated constraints can be generated only as needed.
Appendix D. Additional simulation results
Figure 8. Projected SHD per source for neighborhood selection with BIC and the AND rule and the oracle-best alternative when d = 2 d = 2 d = 2 and l = 3 l = 3 l = 3 . The oracle alternative is selected separately in each simulation setting using its mean SHD across the 50 paired replications, and its identity is reported above each group of boxplots.
Figure 11. Projected SHD per source in the hybrid setting, where three sources provide raw data and two provide estimated graphs. Fixed c = 1 c = 1 c = 1 is compared with c c c selected by predictive cross-validation. Panels correspond to combinations of sample size n n n and number of variables p p p , and the groups within each panel correspond to boundary sizes l ∈ { 2 , 3 } l \in\{2, 3\} l ∈ { 2 , 3 } and missingness levels of 20% and 40%. Boxes summarize 50 paired replications. Percentages at the top of each panel report exact recovery of the projection-equivalence class. Results are based on the coordinate-descent procedure with five sources.
Appendix E. Adaptation of CARE
The graph of the 21 red-blood-cell fatty acids was estimated using the alternative two-stage CARE estimator in Supplement S.2 of Zhang et al. (2025), adapted to incorporate NHANES survey weights, covariate adjustment, common-parameter tuning, and stability-based coefficient thresholding. After the eligibility and complete-case restrictions described in the main text, source four contained 5,115 participants. Each centered log-ratio coordinate was regressed on age, sex, race/ethnicity, and fasting duration using phlebotomy weights w i = W T P H 2 Y R i w_i = \mathrm{WTPH2YR}_i w i = WTPH2YR i . Age was modeled using a restricted cubic spline with knots at its weighted 5th, 35th, 65th, and 95th percentiles. CARE was applied to S w S_w S w , the survey-weighted covariance matrix of the resulting residuals. Both CARE tuning parameters were set to a common λ \lambda λ . Following Supplement S.2, the two columnwise estimates for each off-diagonal pair were symmetrized by assigning the estimate with smaller absolute value to both corresponding entries. The common λ \lambda λ was selected over { 0 , 0.02 , … , 4 } \{0, 0.02, \ldots, 4\} { 0 , 0.02 , … , 4 } using five repeated random 50/50 training–validation splits, minimizing the mean validation loss L ( Ω ; S w ) = 1 2 tr ( Ω T S w Ω ) − tr ( P T Ω ) L(\Omega; S_w) = \frac{1}{2}\operatorname{tr}(\Omega^{\mathsf{T}}S_w\Omega) - \operatorname{tr}(P^{\mathsf{T}}\Omega) L ( Ω ; S w ) = 2 1 tr ( Ω T S w Ω ) − tr ( P T Ω ) , where S w S_w S w here denotes the validation residual covariance and P = I 21 − 1 1 T / 21 P = I_{21} - \boldsymbol{1}\boldsymbol{1}^{\mathsf{T}}/21 P = I 21 − 1 1 T /21 is the centering matrix across the 21 fatty-acid coordinates. Within each split, all preprocessing parameters were estimated from the training observations and applied unchanged to the validation observations.
With CARE’s regularization parameter fixed at the CV-selected λ ^ \hat{\lambda} λ ^ , a separate coefficient threshold was selected using a StARS-inspired procedure (Liu et al. 2010). Covariate adjustment and CARE estimation were repeated on 100 independently drawn subsamples, each containing ⌊ 10 n ⌋ = 715 \lfloor10\sqrt{n}\rfloor= 715 ⌊ 10 n ⌋ = 715 participants sampled uniformly without replacement, retaining their survey weights. For each candidate threshold t t t , an edge was selected in a subsample when its estimated precision-matrix entry exceeded t t t in absolute value. Letting π ^ j k ( t ) \hat{\pi}_{jk}(t) π ^ j k ( t ) denote the proportion of subsamples selecting pair ( j , k ) (j,k) ( j , k ) , the average instability and selected threshold were
D ( t ) = ( 21 2 ) − 1 ∑ j < k 2 π ^ j k ( t ) { 1 − π ^ j k ( t ) } , t ^ = min { t : max s ≥ t D ( s ) ≤ 0.05 } . D(t) = \binom{21}{2}^{-1}\sum_{j<k}2\hat{\pi}_{jk}(t)\{1-\hat{\pi}_{jk}(t)\}, \qquad\hat{t} = \min\left\{t:\max_{s\ge t}D(s)\le0.05\right\}. D ( t ) = ( 2 21 ) − 1 j < k ∑ 2 π ^ j k ( t ) { 1 − π ^ j k ( t )} , t ^ = min { t : s ≥ t max D ( s ) ≤ 0.05 } .
Candidate thresholds were evaluated on a grid of 100 equally spaced values from zero to the largest absolute off-diagonal estimate across the subsample fits. For each candidate t t t , the maximum was taken over all grid values s ≥ t s \ge t s ≥ t . The final graph retained pairs satisfying ∣ Ω ^ j k ∣ > t ^ |\hat{\Omega}_{jk}| > \hat{t} ∣ Ω ^ j k ∣ > t ^ in the full-data CARE estimate.
To evaluate whether the proposed tuning and thresholding strategy recovered graph structure accurately, a simulation study compared it with the original CARE procedure and several alternative choices. Each replicate generated a graph with 21 nodes and 20 edges according to one of three structures. Random graphs selected 20 distinct node pairs uniformly at random. Band graphs arranged the 21 nodes in a random order and connected each node only to its immediate predecessor and successor, forming a single chain. Hub graphs divided the nodes randomly into three groups of seven, each with one central node connected to the other six, and added two edges linking the three centers into a chain.
For each graph, with adjacency matrix A A A , the population precision matrix Ω 0 \Omega_0 Ω 0 had off-diagonal entries ( Ω 0 ) j k = − ρ A j k (\Omega_0)_{jk}=-\rho A_{jk} ( Ω 0 ) j k = − ρ A j k and diagonal entries ( Ω 0 ) j j = 0.20 + 0.40 deg ( j ) (\Omega_0)_{jj}=0.20+0.40\deg(j) ( Ω 0 ) j j = 0.20 + 0.40 deg ( j ) . Thus, absent edges corresponded to zero precision-matrix entries, while larger ρ \rho ρ produced stronger nonzero entries. The diagonal construction ensured positive definiteness. Each dataset contained n = 400 n=400 n = 400 independent latent observations Y i ∼ N ( 0 , Ω 0 − 1 ) Y_i\sim N(0,\Omega_0^{-1}) Y i ∼ N ( 0 , Ω 0 − 1 ) . These were converted to positive measurements by exponentiation and then normalized to produce compositions, X i j = exp ( Y i j ) / ∑ h exp ( Y i h ) X_{ij}=\exp(Y_{ij})/\sum_h\exp(Y_{ih}) X ij = exp ( Y ij ) / ∑ h exp ( Y ih ) . Only these compositions were supplied to the estimation procedures. There were 100 independent replicates per setting, yielding 900 datasets.
The comparison examined regularization selection and subsequent coefficient thresholding. The reference procedure was the original CARE estimator, which uses a single estimation stage and selects a separate regularization parameter for each column by cross-validation. The remaining procedures used the alternative estimator in Supplement S.2 of Zhang et al. (2025). This estimator has two estimation stages: a preliminary fit controlled by λ 1 \lambda_1 λ 1 , followed by an adaptive fit controlled by λ 2 \lambda_2 λ 2 that uses the preliminary estimates to scale its constraints. To simplify tuning, we imposed λ 1 = λ 2 = λ \lambda_1=\lambda_2=\lambda λ 1 = λ 2 = λ . The common value was selected either by cross-validation using repeated random 50/50 training–validation splits or by minimizing the BIC-type criterion n L ( Ω ^ ; S ) + ∣ E ^ ∣ log n nL(\hat{\Omega}; S)+|\hat{E}|\log n n L ( Ω ^ ; S ) + ∣ E ^ ∣ log n , where S S S is the sample covariance matrix of the centered log-ratio measurements and L L L is the quadratic loss defined above. Both selection rules searched the grid ${0}\cup{0.05,0.10,\ldots,0.50}\cup { 0.75 , 1.00 , … , 2.00 } \{0.75, 1.00, \ldots, 2.00\} { 0.75 , 1.00 , … , 2.00 } . An additional comparison fixed λ 1 = λ 2 = 0 \lambda_1 = \lambda_2 = 0 λ 1 = λ 2 = 0 . Each of these three tuning choices was evaluated with and without subsequent coefficient thresholding, as described next.
For each common-λ \lambda λ rule, graph recovery was evaluated in three ways: using the estimated nonzero entries directly, applying bootstrap-based coefficient thresholding, or applying subsampling-based coefficient thresholding. This yielded nine alternatives in addition to original CARE. Bootstrap thresholding used 100 samples of 400 observations drawn with replacement. Subsampling thresholding used 100 subsets of 200 observations drawn without replacement, where 200 = 10 400 200 = 10\sqrt{400} 200 = 10 400 . In both cases, λ \lambda λ was selected once from the full dataset and held fixed throughout resampling. The resampled fits were used only to select the coefficient threshold, using 60 candidate cutoffs and the instability bound of 0.05 described above. The selected cutoff was then applied to the full-data estimate.
Graph recovery depended on both signal strength and graph structure, as seen in Figure 12 . Thresholding markedly improved the common-λ \lambda λ CV and fixed-zero estimators, whereas its benefit for BIC depended on the setting. Recovery generally improved as signals strengthened, and hub graphs were consistently harder than random or band graphs for the four CV/BIC thresholded procedures. At the weakest signal, BIC plus subsampling performed best for random and band graphs, while CV plus subsampling performed best for hub graphs. At the strongest signal, CV plus bootstrap outperformed CV plus subsampling in all three structures. Thus, no procedure dominated throughout. Nevertheless, CV plus subsampling improved on original CARE in every setting and achieved the lowest SHD averaged across settings, 5.15 compared with 15.87 for original CARE. These results motivated its use for source four.
Figure 12. Graph recovery for CARE and its tuning and thresholding variants, across graph structures (columns) and signal strengths ρ \rho ρ (rows). Each point represents mean SHD over 100 replicates with n = 400 n = 400 n = 400 observations, 21 nodes, and 20 true edges. Bootstrap and subsampling refer to the resampling scheme used to select the coefficient threshold.
Applying the selected CV-plus-subsampling procedure to source four yielded λ ^ = 0 \hat{\lambda} = 0 λ ^ = 0 and a coefficient threshold of t ^ = 25.6313 \hat{t} = 25.6313 t ^ = 25.6313 , with average subsample instability 0.04469. Although CV selected zero for both stage-specific tuning parameters, the final graph was sparsified by the separately selected coefficient threshold. It contained 12 edges among the 21 fatty acids, with eight isolated nodes, see Figure 13 .
Figure 13. Estimated source-four graph obtained from survey-weighted, covariate-adjusted CARE with CV-selected regularization and subsampling-selected coefficient thresholding. All 21 fatty acids are shown, grouped by family and ordered by chain length within each family. Colors identify fatty-acid families, and lines indicate the 12 selected edges.