Robust Model Selection of Gaussian Graphical Models
Authors: Abrar Zahin
Rajasekhar Anguluri
Lalitha Sankar
Oliver Kosut
Gautam Dasarathy
Venue: Accepted by TMLR ()

Abstract: In Gaussian graphical model selection, noise-corrupted samples present significant challenges.
It is known that even minimal amounts of noise can obscure the underlying structure,
leading to fundamental identifiability issues. A recent line of work addressing this “robust
model selection” problem narrows its focus to tree-structured graphical models. Even within
this specific class of models, exact structure recovery is shown to be impossible. However,
several algorithms have been developed that are known to provably recover the underlying
tree-structure up to an (unavoidable) equivalence class.
In this paper, we extend these results beyond tree-structured graphs. We first characterize
the equivalence class up to which general graphs can be recovered in the presence of noise.
Despite the inherent ambiguity (which we prove is unavoidable), the structure that can
be recovered reveals local clustering information and global connectivity patterns in the
underlying model. Such information is useful in a range of real-world problems, including
power grids, social networks, protein-protein interactions, and neural structures. We then
propose an algorithm which provably recovers the underlying graph up to the identified
ambiguity. We further provide finite sample guarantees in the high-dimensional regime for
our algorithm and validate our results through numerical simulations.

Published in Transactions on Machine Learning Research (04/2025)
Robust Model Selection of Gaussian Graphical Models
Abrar Zahin
azahinn eduu
School of Electrical, Computer & Energy Engineering Arizona State University
Rajasekhar Anguluri"
rajangul@umbc..o edu
Department of Computer Science & Electrical Engineering University of Maryland, Baltimore County
Lalitha Sankar
Isankar@aste edu
School of Electricol, Computer Energy Engineering Arizona State University
Oliver Kosut
okosut Wasu edu
School of Electricol, Computer Energy Engineering Arizona State University
Gautam Dasarathy
geutamd@asu.edd edu
School of Electrical, Computer Energy Engineering Arizona State University
Reviewed on OpenReview: https: // openreview. net/ forum? id= AIby9M0Xbu
Abstract
In Gaussian graphical model selection, noise-corrupted samples present significant challenges. It is known that even minimal amounts of noise can obscure the underlying structure, leading to fundamental identifiability issues. A recent line work addressing this "robust model selection" problem narrows its focus to tree-structured graphical models. Even within this specific class of models, exact structure recovery is shown be impossible. However, several algorithms have been developed that known to provably recover the underlying tree-structure up to (unavoidable) equivalence class.
In this paper, extend these results beyond tree-structured graphs. We first characterize the equivalence class up to which general graphs can be recovered in the presence of noise. Despite the inherent ambiguity (which we prove is unavoidable), the structure that can be recovered reveals local clustering information and global connectivity patterns in the underlying model. Such information is useful in range of real-world problems, including power grids, social networks, protein-protein interactions, and neural structures. We then propose an algorithm which provably recovers the underlying graph up the identified ambiguity. We further provide finite sample guarantees in the high-dimensional regime for our algorithu and validate results through nunerical simulations.
1 Introduction
Probabilistic graphical models have emerged as a powerful and flexible formalism for expressing and leveraging relationships among entities large interacting systems (Lauritzen, 1996). They have found application
"The work was primarily done while R.A. Arizona University.

---

Published in Transactions on Machine Learning Research (04/2025)
range of areas including signal processing Kim & Smaragdis 2013
Ott & Stoop
2006
Murphy et al.
2013), power systems (Anguluri et al. 2022 Deka et al.; 2020 2015), (phylo)genoming Zuo et al. 2017
Dasarathy et al., 2014 2022), and neuroscience (Bullmore & Bassett 2011 Vinci et al. 2019
Gaussian
graphical models are an important subclass of graphical models and are the main focus of this paper; our
techniques do apply more broadly, as discussed Section 7
In several applications, we do not know the underlying graph structure, and the goal is learn this from data a problem dubbed graphical model selection. This is important because the graph structure provides succinct representation of the complex multivariate distribution and reveal important relationships c.g..Drton among the underlying variables. See, c.g.. Drton & Maathuis (2017); Maathuis et al.) (0118) and references
therein for more on this problem. Here, we focus on a relatively new but important task where samples from the underlying distribution are corrupted by independent noise with unknown variances. This occurs in a wide variety of applications where sensor data, or experimental measurements suffer from statistical uncertainty or measurement noise. In these situations, we refer to the task of graph structure learning as robust model selection.
This problem recently considered by Katiyar et al. 2019) and line of follow-up work (Katiyar al., 2020 Casanellas et al. 2024 Tandon et al. 2021 who show that unfortunately the conditional independence structure of the underlying distribution can be completely lost in general under such corruption; see Sect ion 3.1 for more on this, The authors show that even in the often tractable case of tree-structured graphical models, one can only identify the structure up to an equivalent class. In fact, the assumption that the underlying uncorrupted graphical model has tree structure critical to the techniques of this line of work. As Casanellas et al. (224g) astutely observe, when the random vector associated with the true underlying graph is corrupted with independent but non-identical additive noise, the robust estimation problem reduces to a latent tree structure learning problem. We improve on the algorithmic and theoretical results of this line of work by considering the robust model selection problem for general graphs. Our main contributions are summarized below.
We establish a fundamental identifiability result (c.f. Theorem 3.1 for general graphs in the robust Gaussian graphical model selection problem. This confirms that the identifiability problem exacerbated if one considers more general graphs. More importantly, this also generalizes the identifiability results from carlier lines of work and identifies an equivalence class up to which one may hope to recover the underlying structure.
We devise a novel algorithm, called NoMAD (for Noisy Model selection based on Ancestor Discovery), that tackles the robust model selection problem for general graphs extending the results of (Katiyar et al. 2019 2020 Casanellas et al., 2024 Tandon et al., 2021). Our algorithm is based on novel "ancestor discovery" procedure (see Section 3.4 that we expect to be of independent interest. It is worth observing that the tree-based algorithms previously proposed fail, often catastrophically, when there are loops in the underlying graph.
We show that NoMAD provably recovers the underlying graph up to a small equivalence class (c.f. Theorem 4.2 and establish sample complexity results (c.f. Theorem 5.3) for partial structure recovery in the high-dinensional regime.
We also show the elficacy of our algorithm through experiments on synthetic and realistic network structures.
2
Related Work
Several lines of research have tackled the problem of robust estimation of high-dimensional graphical models under corruption. This includes graphical modeling with missing data, outlicrs, or bounded noisc, see, for instance, Loh & Wainwright (2011) ; Chen et al. (2013); Wang & Lin (2014); Nguyen et al. (022)) and references therein. For the missing data problem, several other algorithms have been proposed for estimating mean values and covariance matrices from the incomplete dataset available the learner Little & Rubin
(2019); Schneider (2001); Lounici (2014). Zheng & Allen (2024) considered variant of the missing value problem where instead of missing values, the measurements irregular; that is, different. vertex pairs have
2

---

Published in Transactions on Machine Learning Research (04/2025)
vastly different sample sizes. Vinci et al.
explored the situations where one is only able to obtain samples from subsets of varia bles, possibly missing joint observations from
(0199: Chang et al. 2023 Dasarathy 2019
several pairs. Sun & Li (0122) and Yang & Lozano (2015 proposed algorithms for handling the outliers. orror-in-varialles
There is another line of work that treats this problem using the error-in- variables lens (see the books and
papers Hwang
1986);
Carroll et al.
[995]; [[urria el al. (1999); Xu & You| (2007) and references therein).
For the problem of model selection from bounded noisy measurements, sec Wang & Lin (2014); Öllerer &
Croux
2015
Loh & Tan (0018); Chen et al. (2015).
However, these papers do not consider the setting of unknown additive noise and the corresponding implications on the conditional independence structure. Recently, Nikolakakis et al. (2019) considered recovering forest- structured graphical models assuming that noise distribution across all vertices is identical. In contrast, our setting allows for unknown and non-identical noise. The robust model selection problem, as considered here, had not been adequately addressod even for the tree-structured graphical models until the recent work by Katiyar al. (2019 2020) who showod that the structure recovery in the presence of unknown noise is possible only up to an equivalence class. These studies also proposed algorithms to recover the correct equivalence class from noisy samples. Using informationnthhereel methods, Tandon et al. (2021) improved the sample complexity result of Katiyar et al.] (2020); Nikolakakis ct al. (2019) and provided a more statistically robust algorithm for partial tree recovery. Finally, Zhang & Tan 2021 studied the structure recovery problem under noise when the nodes of the GGM are vector-valued random variables. However, these results are limited to tree-structured graphical models, as they inherently use the additive distance metric property to learn the full (or partial) structure. However, the additive distance metric does not hold for general structures (sce more Section 3.3 The results of this paper significantly extend this line of work, and are applicable to general graphs.
3 Preliminaries and Problem Statement
Graph theory. Let G = (V, E) be an undirected graph on vertex set V (with cardinality p) and edge set E c (K). For a vertex v E V, let N₂ a degree deg(v) be the size of N,. A vertex v is said to be leaf if deg(v) = 1. A subgraph of G is any graph whose vertices and edges are subsets of those of G. For V" C V the induced subgraph G(V") has the vertex set V' and the edge set E" [u, E E : u, U V'J. A path between the vertices u, v is a sequence of distinct vertices U1 u. U2,,.... ...,, 2k=
uu E E} be the neighborhood of the vertex e E V and
< such that (uz, 0+41 E, for i k. We let Pue denote the set of all paths between u and v. If Pur is not emply, we say u and v are connected. The graph G is connected if every pair of vertices in G is connected. A set S C V separates two disjoint subsets A, B C V if any path from A to B contains a vertex in S. We denote this separation as A 1L B S. The resemblance of this notation to that of the conditional independence of random variables in the graphical model will be made clear later.
Gaussian graphical models. Let X X= (X1, X2...., Xp) E R be a zero-mean Gaussian random vector with a covariance matrix E E RExP, Compactly, X ~N(OE)) where 0 is the p-dimensional vector of all zeros. Let G (Ip), E) be graph the vertex set [p] & (1,2,.... .........pppp................... .p) representing the coordinates of X. Let K & x-1 is called the precision matriz of X. The distribution of X is said to be Gaussian graphical model (or equivalently, Markov) with respect to G if K,, = 0 for all {i,j} $ E In other words, for any {i,j} & E, X; and Xj are conditionally independent given all the other coordinates of X (see Lauritzen (1996) for more details). In the sequel, we will use a generic set V to denote the vertex set of our graph with the understanding that every clement in V uniquely mapped to a coordinate of the corresponding random vector X. For a vertex v E V, with slight abuse of nolation, we write X, to denote the corresponding coordinate of X. Similarly, we write Enp to mean the covariance between X,, and X,,
3.1 The Robust Model Selection Problem
In this paper, we consider a variant of the model selection problem, which we refer to as robust model selection. Formally, let X ~ (O, Σ) be a Gaussian graphical model with respect to an unknown graph G= (V, (V, E). In the robust model selection problem, the goal is to estimate the edge set E (or equivalently the sparsity
I Hence, the sparsity pattern of K is represented by the edge of
3

---

Published in Transactions on Machine Learning Research (04/2025)
pattern of K= =)=1) when one only has access to noisy samples of X. That is, we suppose we have access to the corrupted version Y of the underlying random vector X such that = + Z, where the noise Z ~ ( D) is independent of X and D is assumed to be diagonal with possibly distinct and even zero entries. In other words, the noise is assumed to be independent and heteroscedastic while potentially allowing for some coordinates of X to be observed uncorrupted. Observe that Y ~ (00, E²), where E _ Σ D. Indoed, D is assumed to be unknown.
Unfortumately, such corruption can completely obliterate the conditional independence structure of X. For instance, suppose that D =eje,, where e, is a vector of zeros except in the jth entry where it is one. By the Sherman-Morrison identity (sce c.g., Horn & Johnson 2012). we have (Σ-)-1 = K eKeeee K for some e 2 0. The term e K can be dense in general and, hence, can fully distort the sparsity of K (the conditional independencee structure of X).
In view of the above example, the robust model selection problem appears intractable. As outlined in Section I recent studies show that this problem is partially tractable for tree-structured graphs. Notably, as Casanella
ct al. 2024 astutely observes, one can reduce the problem of robust structure estimation of trees to the problem of Tearning the structure of latent. tree graphical models, which enjoy several efficient algorithms and rich theoretical results (see, e.g., Choi et al. p011 Erdös et al. (1999; Semple & Steel (0003; Dasarathy et al. 2014). To see this, suppase that X is Markov according to a graph G = (V= = [p]. E) that is tree-structured. Let the joinl graph G' denote the graph obtained by creating a copy of each node in G and linking the copies to their counterparts in G. Formally, we define G' = (V', E²), where V & V U (1 .........pp" and E' 2 EU (*; : E [p]}. In subsequent sections, for any vertex subset B 2", we let 1e denote the vertices associated with the noisy observations from B and call it the noisy counterpart of B.
Notice that with this definition, if we associate the coordinates of Y to the newly added leaf vertices, the concatenated random vector [X; YJ, obtained by stacking X on top of Y, is Markov according to G Casanellas et al. (2024) then uses the fact that when given samples of Y, one can reconstruct a reduced latent tree representation of G², which in turn can be used to infer an equivalence class of trees that contains the true tree G. Indeed, the equivalence class thus obtained the same one identified by Katiyar et al.) (2019 2020 We next state our general identifiability result after introducing some more graph-Cheoretic concepts.
3.2 An Identifiability Result
A connected graph G is said to be biconnected if at least 2 vertices need to be removed to disconnect the graph. A subgraph H of G is said to be biconnected component if it is maximal biconnected subgraph of G. That is, H is not strict subgraph of any other biconnected subgraph of G. The vertex set of such a biconnected component will be referred to as a block. A block is non-trivial if it has more than two vertices. For example, in Fig. Ia the vertex set 21, 3,4] and B1 U (6,8) are non-trivial blocks where B, is an arbitrary set of vertices such that the subgraph on B1 U {6, is a biconnected component, whereas, the set (10,8) 8} is a trivial block. In what follows, we will often be intcrested in the vertices of such non-trivial blocks and toward this we write 8 to denote the set of all vertex sets of non-trivial blocks in G. From these definitions, it follows that trees (which are cycle free) do not have any non-trivis non-trivial blocks. It also follows that two blocks can share at most one vertex; we refer to such shared vertices as cut verticos. In Fig. Ia the vertices 4 and 10 are cut vertices. The vertices in ENT which are not cut vertices are referred to as non-cut vertices. In Fig. Ta the vertex is a non-cut vertex.
With these definitions, we now introduce a novel representation for a graph G that will be crucial to stating our results. This representation is tree-structured graph TAsT(G), which we call the articulated set tree of G, whose vertices correspond to (a) non-trivial blocks in G, and (b) vertices in G that are not member of any non-trivial blocks. Vertices in this tree-structured representation are connected by edges if the corresponding sets in G either share a vertex or are connected by single edge. The vertices in the original graph that are responsible for the edges in the representation are called articulation points We formally define this below. For example, for G in Fig. la the articulated set tree is illustrated in Fig. 1c where the sets (1,2,3.4) 4) and
2 AAtticuaation (points) vertices are cut vertices that separate non-trivial blocks from the rest of the graph.
4

---

Published in Transactions on Machine Learning Research (04/2025)
2
10
18 e
13
12 21
1O
(a) G
(b) G'
(c) (G)
Figure 1: (a) a true underlying graph where both B1 (6,8) (B2 U 9)) are non-trivial blocks where Bi (B2) is an arbitrary set of vertices such that the subgraph on Bi U (6,8) (B, is biconnected component, (b) joint graph G²; noisy vertices associated with the non-trivial blocks containing B and B2, and some other vertices are not numbered to reduce the clutter, and (c) the articulated set tree (G)
{17, 18, 19} are associated to verticos in the articulated set tree representation, and 4,6,7,14, 14, and 17 are examples of articulation points.
Definition 3.1 (Articulated Set Tree). For an undirected graph G = (V, the articulated set tree (G) is a tuple (P,E,A) where (a) the set P = {B: B E U [[o): (P,P") E if and only if (i) vertices v, V are such that u E P, E P', and (v.0"} "ee ewists a vertex v V such that PEPOP and (c) the articulation function A E +VV returns the articulation points of each edge.
UBEB" (b) an edge
E E or (i8) there
Notice that the articulated set tree (AST), as the name suggests, is indeed a tree. Otherwise, by definition, the set of non-trivial blocks BNT would be incorrect (we show this formally in Lemma B.1 in the Appondix). Readers familiar with graph theory may have obsorved that the AST reprosentation is quite similar to the block-cut tree representation (see e.g., Harary 1971: Biggs et al.] 1986), but unlike a block-cut tree, the subgraph associated with any non-trivial block does not matter in the articulated set tree.
We will now define the equivalence class of graphs up to which robust recovery is possible. Let L(G) denote the set of all leaves in G (i.e., all vertices of degree one). A subset R c L(G) is said to be remote if no two elements of R share a common neighbor. Let R be the set of all remote subsets of L(G). For each R E R, define a graph GR on V by exchanging each vertex in R with its (unique) neighbor.
Definition 3.2 (Equivalence Relation, ~). Two graphs G, H are said to be equivalent if and only if BR E R such that (GR) = H)) Symbolically, we write as H G.
We let [G] denote the equivalence class of G with respect to It is not hard to verify that Definition 3.2 is valid equivalence relation. Furthermore, it can be readily checked that this notion of equivalence subsumes the ones defined for trees in Katiyar et al. (2019): Casanellas et al. (024). Fig.
2 Fillustrates three graphs from
the same equivalence class. Notice that G1 can be constructed from G by: (i) exchanging the labels between
the leaf vertices {13, 17, 15) with their corresponding neighbors {10, 21, 14]: (ii) adding an edge {2, 4} inside
a non-trivial block. Similarly, G2 can be constructed from G by: (i) exchanging the labels between the leaf ices {11,20) with their corresponding neighbors {10,21); (ii) removing an edge (1, 4) from non-trivial block g Therefore, for any two graphs in the equivalence class, the non-cut vertices of any non-trivial block remain unchanged, whereas, the edges in the non-trivial block can be arbitrarily changed; the labels of the leaves can be swapped with their neighbor. In the following we will show that our identifiability result also complements the equivalence class. Finally, notice that with the similar operation described above, given a TAST which equals to (G), one can recover all the graphs in [G].
We now state our unidentifiability result, which establishes that the true covariance matrix of any graph in the equivalence class [G], under the noise model of Subsection 3.1 will result in the same observed covariance matrix Eo.
Theorem 3.1 (Undentifiabiility). Fir covariance matria Σ* whose conditional independencce structure
is given by the graph G. Suppose we are given a noisy covariance matriz Σ- Σ + D where D =
Notice that the sets ( (13, 17, 15) and {11, 203 are remote according Definition 3.2
5

---

Published in Transactions on Machine Learning Research (04/2025)
O
10
no
x
(a)
(b) C₁
(c) G2
Figure 2: An illustration of three graphs from the same equivalence class of G in Fig. la For all three graphs, Bi (6,8) (B2
u (7) can have any induced subgraph as long as subgraphs on B1 (6,8) (B2 U (7,9)) is biconnected component.
Dii............................. Drp) 2 O. Then, for any H E [G] where H + G, there erists matrices Eh DH such that E Σn DH, H DH diagonal matrix with non-negative entries, and the sporsity pattern of (En)-1 is described by H.
This theorem is proved in Section D Notice that this undentifiabiliit result shows it is impossible to uniquely recover G as there are other confounding graphs whose noisy observations would be indistinguishable from those of G. However, this theorem does not rule out the possibility of recovering the equivalence class to which G belongs since all the confounding examples are confined to [G]. In Section 3.3 we devise an algorithm that precisely does this. Before we conclude this section, we introduce the notion of partial structure recovery and discuss how recovering the equivalence class still reveals useful information about the true graph.
Partial Structure Recovery of G. Given the noise model described in Subsection 3.1 we know that any graph is only identifiable upto the equivalence relation in Definition 3.2 This is not only the best one can do (by Theorem 3. but also preserves useful partial structure of the graph. In particular, such a partial structure recovery able to identify the (non-cut) constituents of the non-trivial blocks and the set of leaf vertices (and neighbors thereof). As the following examples illustrate, we conclude this subsection by arguing that even such partially recovered graphs are instrumental in several application domains.
Electrical distribution networks usually have radial (or globally tree-like) network structures. Recently, several parts of such networks have become increasingly locally interconnected due to the adoption of technologies like rool-top solar panels and battery power storage that enable more flexible power flow. Nonetheless, practitioners critically rely on (learning) the global structure for most operations and maintenance tasks, such as state estimation, power flow, and cybersccurity.
2. Neuronal networks. Network models are commonly used to describe structural and functional connectivity in the brain Sporus 2018). An important property of networks that model the brain is their modular structure; modules or communities correspond to clusters of nodes that are densely connected (and are presumably functionally related). Such modular structure has long been regarded as a hallmark of many complex systems; see Simon 2012)) for more details. Module detection, that is, understanding which nodes belong to which modules can yield important insights into how works function and also uncover network's latent community structure.
3.3 The Robust Model Selection Algorithm
We now present an algorithm that can recover the partial structure graph for which only noisy samples are available based on the setup from Subsection 3.1 Before we describe our algorithm, we introduce few more concepts that will play key role. We start with a well-known fact about the factorization of pairwise correlations for faithfu Gaussian graphical model. First, recall that for two random variables X; and Xj, the correlation coefficient is defined Pij & V
4The global Markov property for GGMs ensures that graph separation implies conditional independence. The reverse implication need hold. However, for faithful GGM, the reverse implication does hold.

---

Published in Transactions on Machine Learning Research (04/2025)
Fact 1 (see c.g., Soh & Tatikonda (0114) ) For a faithful Gaussian graphical model, X, TT Xx|X, if and only if Pik- = Pij x Pjk-
We now define information distances, which play vital role in designing our algorithm. Definition 3.3 (Information distances). For (X1 (X...... Xp) NN(0, 2), the information distance between X; and X; is defoned by diş- f - log ppyl 2 O, where Pij is the pairwise correlation coefficient between X, and X,.
4
For tree-structured Gaussian graphical models, the strength of the correlation dictates the information (or graphical) distance between vertices and j. Higher the strength, the smaller is the distance, and vice versa. In fact, the information distance defined this way is an additive metric on the vertices of the tree. Although the graphs consider are not necessarily trees, we still refer to this quantity as a distance throughout the paper for convenience. We now define the notion of ancestors for a triplet of verlices using the notion of minimal mutual separator.
Figure 3: Graph with multiple min- imal mutual separa- tors.
Definition 3.4 (Minimal mutual separators, Star triplets, Ancestors). Fix triplet of vertices U E (²)) A verter set S " V is called a mutual separator U U if S separates each pair i,j E U; that is, every path π E Pij contains al least one element of S. The set S is called a minimal mutual separator of the triplet U if no proper subset of is a mutual separator of U. We let Smin (U) separator
U. U is said to be a star triplet if [Smin[U]] and the denote the set of all minimal mutual separators U.
separator in Suin(U) is singleton. The unique vertez that mutually separates U is called the ancestor of U.
For instance, for the graph in Fig- 3 the set [2, 4, 7, 5) is a mutual separator for the triple (1,6, 9) Further notice that minimal mutual separator set may not be unique for triplet: here, the sets 3, 7) and {4, 5, 8 are minimal mutual separators of the triple {1, 9}. In Fig. La for the triplct {1, 11, 12), minimal mutual separator Smin (1,111,12)) = (10). Further, notice that an ancestor of U can be one of the elements of U. In Fig. la the vertex {10} is the ancestor of triplet {4, 10, 11) & U. Notice that for triplet U, the distance between 10 and the ancestor is zero.
For star triplet (i,j,}} with ancestor r, it is clear that the following holds true based on the relationship between graph separation and conditional independence: X; IL X5 Xr, X; 1L X X,, and Xj IL X X As a consequence, from Fact and Definition 3.3 the pairwise distances day, dat. and djs satisfy the following equations: dy de + drj, dik- = dir + dyk, and dzk- djr + drs. Some straightforward algebra results in the following identities that allows us to compute the distance between cach vertex in fi. k) and the ancestor vertex r. In particular, for any ordering {ar y: =} of the set {i,j. k} notice that the following true:
dxr = 0.5 x (day + dxz dyz))
(1)
For a triplet U = ki),, we will let dy A (dl, + d+ dzu). If U is a star triplet, then di reveals the distance between and the ancestor of U. However, we do not restrict this definition to star triplets alone. When U is not star triplet, di is some arbitrary (operationally non-significant) number; in fact, for non-star triplets this quantity may even be negative. Notice that all vertex triplets in tree are star triplets. Hence, for tree-structured graphical model, we can choose any arbitrary triplet and if we can find a vertex for which df = d i E U, then we can identify the ancestor of U. If such vertex does not exist, we can deduce the existence of a latent ancestor. Therefore, itcrating through all possible triplets, one can recover the truc (latent) tree structure underlying the observed variables. In fact, several algorithms in the literature use
similar techniques to learn trees (see e.g., Saitou & Nei 1987); Krishnamurthy & Singh 2012) : Choi et al. 12011 Dasarathy et al. 2014).
3.4
The NoMAD Algorithm
In this section, we introduce our algorithm NoMAD, for Noisy Model selection based on Ancestor Discovery, for robust model selection. We describe NoMAD in the population setting (i.e., in the infinite sample limit) for clarity of presentation; the modifications required for the finite sample setting are discussed in Section j
7

---

Published in Transactions on Machine Learning Research (04/2025)
B.7791
16
B
10
10
20
11re
a
12
20
12
IN
(a)
(b)
(c)
(d)
Figure 4: (a) The joint graph G³, (b) the leaf clusters and internal clusters of G"; Bi (B5) denote the set of noisy vertices associated with the vertices in B1 (B2); Also, recall that clusters are a set of vertices; grey vertices are identified but unlabeled articulation points associated with the clusters, (c) non-trivial blocks and trivial blocks along with the identified and labeled articulation points, and (d) the edges between different articulation points.
In the population setting, NoMAD takes as input the (exact) pairwise information distances dyy, for all i.j in the observed vertex set Vo, and returns articulated set tree Top (Pop. Aop. Eop) (see Definition 3.1 A high level overview of the algorithm is given in Algorithm ! Its operation may be divided into two main steps: (a) learning Pap and Aop; and (b) learning Fop These steps are summarized in the following. A formal algorithmic listing and a full description can be found in the Appendix.
(a) Learning Pop and Aop- Inspired by the aforementioned ancestor based tree reconstruction algorithms, NoMAD first identifies the ancestonn in G³, and learns the pairwise distances between them. Notice that finding the ancestors in G' is challenging for the following reasons: (a) since Go is not tree, some vertex triplets are not star triplets (e-g,, {15,35, 11s} in Fig. 1b and (b) subset of vertices (which may include ancestors) in G are unobserved or latent. Hence, we can not guarantee the identification of a star triplet following the procodure for trees. NoMAD instead uses a novel procedure that compares two triplets vertices to identify the ancestors; we call this the TIA (Test. Identical Ancestor) lest which is defined as follows:
Algorithm NoMAD
1: Input: Pairwise distances D = {dis hijeo.
2: Output: Top & (Pop. Aap- Fap)
3: Y AANTEEeAAnncSSTSssSSuuottnneeee
Accepts: D; Returns: (4) A set Aobs (Ania resp.) of observed (hidden resp.) ancestors, and the corresponding collection of vertex triplets Vabe (2mi resp.), and (II) The set of pairwise distances
{dy} } for each pair i.j E v U Anid
4: LEARNCLUSTERS (Subroutine
Accepts: Aots Abad, and D; Returns: A collection of (I) leaf clusters
C, and (II) internal clusters I.
5: VERTEXSET-ASEE ASSTT-ATTSSurbbnnnnne Accepts: L and I; Returns: (I) the vertex set Pop (II) the articulation points App, and (TII) subset of the edge set Fop-
6: SACESET-AST(Subronne
Accepts: Pop and App: Returns: Eop-
Definition 3.5 (TIA Test). The Test Identical Ancestor (TIA) test accepts a triplet pair U, W. E (V"), and returns TRUE if and only if for all x E U, there exists at least one pair y, 2 E W such that du + d = dzy and d% + d = d
In words, in order for pair of triplets U, W to share an ancestor in G², each vertex in one triplet (say, U) needs to be scparated from at least a pair in W by the (shared) ancestor in G". We now describe the fist step of the NoMAD in three following sub-steps:
Identifying the ancestors in G¹. In the first sub-step, NoMAD (a) uses the TIA test to create the set 20 = (V M each U E V has the same ancestor }, (b) it then assigns each triplet collection V E 23 to
We say that vertex an ancestor if there a triple U such that ancestor of U.
8

---

Published in Transactions on Machine Learning Research (04/2025)
either Vobs Whid: the former is the collection of vertex triples whose ancestor is observed and the latter has ancestors that are hidden, and (c) identifies the observed ancestors and enrolls them into a set of observed ancestors Aobs- Furthermore, for each collection V; E Tnid, NoMAD introduces a hidden vertex, and enrolls it in Anid such that. |Auial equals to the number of hidden ancestors in G¹. For example, consider the joint graph G' in Fig. Ma In G', the verlex {4) is the observed ancestor of the pair {19, 10] and (3", 40, 8 and the vertex {8] is the hidden ancestor of the pair 88,88,9 {19,8 ,- Complete pscudocode for this step appears in Subroutine in Appendix.
Extending the distance set {diy In the next sub-step, using pairwise distances {dez hijevo and Auid, NoMAD learns the following distances: (a) diy for all i, Anid, and (b) di for all i, E Ania UVV For learning (a), notice from the last sub-step that each a, Ani is assigned to a collection of triplets V; E Unid. In order to compute the distance between two hidden ancestors (say ap, ay E Absa), the NoMAD chooses two triplets
: I Vp E Vz). Then, the most frequent element in Apg: i.c., modo(Apg). is declared as dpg- We show in Appendix that NoMAD not only correctly learns the distance set {di but also learus dig for any i E Anaa and j E Vo. A pseudocode for this step appears in Subroutine 3 in Appendix.
VPP E VpP and V E Vg. and computes the set Apy as follows: Apg =
=ddey day -d= + d
Learning Pop and Aop. In the final sub-step, NoMAD learns the clusters of vertices in V \ Aobs using the separation test in Fact 1 which eventually lead to finding Pop and Asp- Specifically, NoMAD learns (a) all the leaf clusters, each of which a set of vertices that are separated from the rest of the graph by a single ancestor, and (b) all the internal clusters, each of which is set of vertices that are separated from the rest of the graph by multiple ancestors. For example, in Fig. 4b the set (17 18 19
is a leaf cluster- separated from the rest of the graph by the (hidden) ancestor ag. The set BA is an internal cluster- separated from the rest of the graph by the set of ancestors {as, 46, 47 Next, NoMAD uses the clusters to learn Pop and Aop for Top by applying the TIA test on each cluster to identify the non-cut vertices and potential cut vertices in it. For example, for the leaf cluster {17", 18 19 20" 21"), 18 and 19 are non-cut vertices, and vertex from 17, 20, and 21 may be declared as cul-vertex arbitrarily (see Fig.
A pseudocode for this step appears as Subroutine and Subroutine f in Appendix.
(b) Learning Eop- In this step, NoMAD learns the edge set Eop. Notice from Definition 3.1 that any two elements of Pap are connected with each other through their respective articulation points. Hence, in order to learn Eap: NoMAD needs to learn the neighborhood of each articulation point in G. To this end, NoMAD first learns this neighborhood for each articulation point in G using Fact ! Then, in the next step, NoMAD creates an edge between two elements of Pop if the articulation points from each element are neighbors in G (dotted lines in Fig. 4d A pscudocode for this step appears Subroutine in Appendix.
4 Performance Analysis of NoMAD in the Population Setting
In this section, we show the correctness of NoMAD in returning the equivalence class of a graph G while having access only to the noisy samples according to the problem setup in Section 3.1 We now make an assumption that will be crucial to show the correctness of NoMAD. This is similar to the faithfulness assumption common in the graphical modcling literature Choi et al. (2011h; Kalisch & Bühlman (2007); Uhler et al. (2013), and like the latter, it rules out "spurious cancellations" " To that end, let Vatar C (3) be the set of all star triplets in G (sce Definition 3.4h. Let Vsep S (3) be the set of triplets V such that one of the vertices in V separates the other two vertices.
Assumption 4.1 (Ancestor faithfulness). Let U, (2) Vatar U Veep- Then, (1) there are no vertices I E U and E W that satisfy dy + dW dza, and (it) there does not erist any verter r V and E for which the distance dur salisfies relation in equation
9

---

Published in Transactions on Machine Learning Research (04/2025)
Notice that Assumption 1.1 is only violated when there are explicit constraints on the corresponding covariance values which, like the faithfulness assumption, only happens on a set of measure zero. We next state the main result of our paper in the population settings.
Theorem 4.2. Consider covariance matrie Σ" whoss conditional independence structure is given by the Suppose that according to the problem selup in Section 3. we are given pairwise distance diy of a vertex paár (i,j) in the observed verter set Vo, that is, dy -log Pij where Pij & Lig/ 22 Then, given the pairwise distance set {diy)i.evo inpuls, NoMAD oulputs the equivalence class [G].
gruph G, and the model salisfies Assumplion
Proof Outline. In order to show that NoMAD correctly learns the equivalence class, it suffices to show that it can correctly deduce the articulated set tree Top Given this, and the equivalence relation from Definition 3.2 the entire equivalence class can be readily generated. Our strategy will be to show that NoMAD learns Top correctly by showing that it learns (a) the vertex set Pop, (b) the articulation points Aop, and (c) the edge set Eop correctly. We will now establish (a) and (b).
From the description of the algorithm in Section B.3 it is clear that NoMAD succeeds in finding the ancestors, which is the first step, provided the TIA tests succeod. Indeod, in the first stage of our proof, we establish Lemma
B.7 in Appendix which shows that the TIA test passes with two triplets and only if they share a common ancestor in G¹.
Next, we show in Lemma B. and Claim g in Appendix that NoMAD correctly learns the distances diş for all vertices i,j that either in the set of observed vertices V or in the set of hidden ancestors Ania- Proposition B.13 establishes the correctness of NoMAD in learning the leaf clusters and internal clusters, and in learning Pop and Aop- The proof correctness of this step crucially depends on identifying the non-cut vertices in G from different clusters which is proved in Lemma B.12
Finally, outline the correctness of NoMAD in learning the edge set Eap- Recall that NoMAD learns the neighbor articulation points of each articulation point. Proposition B.14 in Appendix shows that NoMAD correctly achieves this task. Using the neighbors of different articulation points, NoMAD correctly learns the edges between different elements in Pop-
5 Performance Analysis of NoMAD in Finite Sample Setting
In describing NoMAD (cf. Section 3.4 and the analysis in the population setting (cf. Section +. we lemporarily assumed that we have access to the actual distances dig for the sake of exposition. However, practice, these distances need be estimated from samples {Y....., Y.). In what follows, we show that NoMAD, with high probability, correctly outputs the equivalence class [G] even if we replace di with the
estimate du log 3o Jo where 1o is the (i.j)-th element in 1 EN Y.Y. We recall from
Section 3.4 that the subroutines in NoMAD depend on the TIA test, which relics on the distances day. Thus, we esta blish the correctness of NoMAD in the finite sample setting by showing that the empirical TIA (TIA with estimated distances) correctly identifies the ancestors in Gd with high probability. We begin with the following assumptions.
Assumption 5.2. [r-Strong Failhfulness Assumplion] For any vertex triplet i,j,k E (V)), Tf jik, then (dy daa - ddpx > 7.
~-Strong Faithfulness assumption is a standard assumption used in the literature Kalisch & Bühlman 2007
Chler et al. 2013 ). O-Strong-Paithfulnes Faithfulness is just the usual Faithfulness assumption discussed in Section 3.3 This motivates our next assumption which strengthens our requirement on "spurions cancellations" involving ancestors.
Assumption 5.3 (Strong Ancestor consistency). For any triplet pair U, W E (8) Vetar U Veep and any verter pair (z, a) E U W, there exists constant Ç O,, such that 114 + dW dra S.
10

---

Published in Transactions on Machine Learning Research (04/2025)
10
(a) Syuthelic graph, Gayn
(b) IEEE 33 Bus Graph
Figure 5: Synthetic graph and 1EEE-33 Bus system considered for our simulation
Assumption 5.3 is in direct analogy with Assumption 5.2 As we show in Lemma B.7 for any pair U, W E (3) Vstar Uesp (i.e., any pair that would fail the TIA test), there exists at least one triplet {z, a, b} where x E and a, a. E W such that dza - d% - dW * 0 and dus - dh -d -dl, + 0. This observation motivates us to replace the exact equality testing in the TIA test in Definition 3.5 with the following hypothesis test
against zero: max [ Ly Dw [26 d= 2 } S. We set {
Furthermore, in order to learn the distance between two hidden ancestors in Ani, the mode test introduced in Subsection 3.4 needs to be replaced with finite sample version; we call this the eo-mode test and this is formalized in Appendix C Finally, for any triplet (i,j,k) k) E (W"), in order to check whether IlL jik, the test in Fact needs to be replaced as follows: [dg du dzxl < $ We now introduce two new notations to state our main result. Let Pmin(p) min |Púl and <(p) log((16 (pmin(p)) 22) (pmin(p)) E)),
where ed = min(ff. 7), where y is from Assumption 5.2
Theorem 5.3. Suppose the underkying graph of faithful GGM satisfies Assumptions 5.2 Fir
any T T (0,1]. Then, there erists constant C O such that if the number of samples n satisfies n ((tb)) max (log ( ( (2) log ((m)) then with probability at least 1- I- NoMAD accepting diy outputs the
equicalence class [G].
Remark 5.1. Theorem 5.3 indicales that the sample complexily of the NoMAD is dependent on the absolude minimum and marimum pairwise correlations Pmin and Punax: the number of vertices p, and the magnitude of the quantity from Assumption 5.3 Specifically, in regimes of interest, we see that the sample complexity scales as a logarithm in the number of vertices p and inversely in Pinn (p) and eg thus allowing for robust model selection in the high-dimensional regime. Purther note that our sample requirement can have exponential dependence p based on the degree of G. However, expect that this dependency can be improved; see Section 7 for more on this ovenue for fulure work.
6 Experiments
We perform experiments on both a synthetic graph and an IEEE 33 bus system, which is a graphical representation of established IEEE-33 bus benchmark distribution system (Baran & Wu 1989 to assess the validity of our thcorctical results and to demonstrate the performance of NoMAD. In particular, our experiments demonstrate how an unmodified graphical modeling algorithm (in this case GLASSO Friedman et al. 2008)) compares to NoMAD. The synthetic graph Gsyn we consider and graph associated with the IEEE-33 bus system are given in Fig. ba and Fig, 5b respectively. As first step, we need some new performance metrics to make fair comparison in light of the unidentifiability of the underlying graph structure from noisy data. In the following we will introduce some sets, and show that if an algorithm can recover all these sets, then the output graph (from that algorithm) is in equivalence class.
Families. For a vertex i, define its family F; as {u : deg(u) = and {0,i} E E(G)) U {i}. Notice that the subgraph associated with each family tree. For synthetic graph Gayn: the sets (1,2,3), (8, 9, 10} are some of the familics in Geya: For IEEE 33 Bus Graph (15, 16, 17, 18), (30, 32. are some of the families. Let F Usev F.
11

---

Published in Transactions on Machine Learning Research (04/2025)
NoHAD
NOMAD
Performance in 0-1 Loss
Performance in 0-1 Losss
0.4
0.0
0.
24
0.0
0.5
1.5
24 14
Maximum Allowable Diagonals
Maximum Allowable Diagonals
(a) Performance for Gayn
(b) Performance for IEEE-33 Bus.
Figure 6: Performance of GLASSO and NoMAD for various degree of noises. Up to the values of 2.5 and 1.5 dollars for Gsyn and IEEE-33 Bus, respectively, GLASSO successfully reconstructed an equivalent graph. To investigate this inftuence, we conducted the experiment with a fixed sample size across 15 trials. In contrast, NoMAD consistently demonstrated its ability to recover an equivalent graph under various noise influences.
2. Non-Cut Vertices. For graph G, let Buon-cut be the set of all non-cut vertices in a non-trivial block B. Define Bnon-eut - UBERVY Bnon-cut, where BNT is the set of all non-trivial blocks. Recall from Section g that in all the equivalent graphs the set of non-cut vertices remain unchanged.
3. Global Edges. Let K be the set of cut vertices who do not share an edge with a leaf vertex in
G. For any vertex & E K, let a family F& E F be such that there exists a vertex f E Fk such that (k, [] E E(G). Now, we will note two following condition for any neighbor i E (K):: (a) if K, then {i, k} E E(G), and (b) otherwise, there exists a vertex j E F& such that {j. k} E E(G). If condition (a) and condition (b) are met, global edge associated with i are recovered correctly.
In Lemma B.15 we demonstrate that if an algorithm learns these sets correctly, and the conditions associated with the global odges are met, then equivalent graph can be recovered.
Experimental Setup. We now describe our experimental setup. We generated precision matrices associated with Gsyn; and for IEEE-33 bus system, we added some loops. We then inverted the corresponding precision matrices to obtain the respective covariance matrices in the population setting. Next, we added a diagonal matrix of random positive values to the population covariance matrices at each entry to generate the corresponding noisy covariance matrices.
We will now compare the performance of 0-1 loss of NoMAD to GLASSO under the influence of noise. In order to compare, our goal is to compare NoMAD with the best GLASSO. Our protocol for selecting the best GLASSO is as follows: for a fixed maximum allowable diagonals, we selected the regularization parameter for which the output graph given the noise covariance matrix to GLASSO is in equivalence class. Then, for that fixod regularization parameter we report the performance of GLASSO for varying numbers of (increased) maximum allowable diagonals. Notice that the maximum allowed values of the diagonal elements of the matrix D (which is being added to the generated covariance matrix) contain information about the potential influence of the noise in the setup. In order to study this influence ran the experiment for a fixed sample size over 15 trials. In Fig. 6 we observe that up to the value of 2.5 and 1.5 for Gayn and IEEE-33 Bus, respectively, GLASSO was able to recover an equivalent graph. On the contrary, NoMAD was able to show a consistent performance in recovering an equivalent graph with various influence of noises.
7 Conclusion and Future Directions
Conclusion. In this paper, we consider model selection of Gaussian graphical models when the obscrvations are corrupted by independent but non-identically distributed noise with unknown statistics. We first show that this ambiguity is unavoidable. Finally, we devise a novel algorithm, referred to NoMAD, which learns
12

---

Published in Transactions on Machine Learning Research (04/2025)
structure up to small equivalence class.
Future Directions. This paper opens up several exciting avenues for future research. First, our novel ancestor testing method can be used to identify the ancestors for other graphical models (beyond Gaussians) where information distance satisfies the factorization property in Fact D e.g., Discrete graphical models, where the random vector X takes values in the product space XP, where |X] = k. For any i,j [p], let Tiş E R denote the tabular representation of the marginal distribution of the pair (X, and Ta denote a diagonal matrix with the marginal distribution of X, on the diagonal. Then, it is known that the det(ery) can be taken to be the information distance. We refer the reader to v [det(wae))
following quantity: d,-
Semple & Steel (2003) for more on this, including a proof of an equivalent version of Fact 1 Note that the Ising model a special case, and our results naturally extend to them. Second, it is well known that Amin could scale exponentially in the diameter of the graph; this could imply that the sample complexity will scale polynomially in the number of vertices p even for balanced binary trees, and as bad as exponential for more unbalanced graphs. Now, notice that in Subroutine 3 NoMAD identifies all the star triplets for any ancestor in G Hence, this identification procedure in quite computationally expensive. As we reason this in theoretical section of the appendix that this computaliin is required in order to learn the pairwise distances dy for each pair (i,j) such that E y and j E Auid, where v and Anid is the set of observed vertices, and hidden ancestors, respectively. A promising future rescarch work is to develop a TIA test which can obtain {diy AIEV" without iterating all the triplets in (K'). Furthermore, the Subroutine redesigned to a computationally efficient one by learning the clusters in divide and conquer manner. Another promising avenue for future rescarch work is to obtain an upper bound on the diagonal entrics Dj for which the underlying graph is identifiable. Finally, future research can be done to undersland undersland the behavior of the hyperparameters y and Ç using the stability selection method (see MMinshausen & Bühlmann 2010: in finite sample settings.
1 can be
Acknowledgments
The work was supported in part by the National Science Foundation (NSF) under the grants EPCN-2246655, OAC-1934766, and CCF-2048223. It also supported by the National Institutes of Health (NTH) under the grant 1R01G0140468-01.
References
Rajasekhar Anguluri, Gautam Dasarathy, Oliver Kosut, and Lalitha Sankar. Grid topology identification with hidden nodes via structured norm minimization. IEEE Control Systems Lellers, 6:1244 1249, 2022.
Mesut E Baran and Felix F Wu. Network reconfiguration in distribution systems for loss reduction and load balancing, IEEE Transactions on Power delivery, 4(2):1401-1407, 1989.
Norman Biggs, E Keith Lloyd, and Robin J Wilson. Graph Theory. Oxford University Press, 1986.
Edward T Bullmore and Danielle S Bassett. Brain graphs: graphical models of the human brain connectome. Annual review of clinical psychology, 11113-140, 2011.
Raymond J Carroll, David Ruppert, and Leonard A Stefanski. Meo.surement error in nonlinear models, volume 105. CRC press, 1995.
Marta Casanellas, Marina Marrote-Lópezz and Piotr Zwiernik. Identifiability in robust estimation of tree structured models. Bernoulli, 30(1):1-21, 2024.
Andersen Chang, Lili Zheng, Gautam Dasarathy, and Genevera I Allen. Nonparanormal graph quilting with applications to calcium imaging. Slal, :2(1)) 2023.
Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance matrix estimation via matrix depth. arXiv preprint ar Xiv: 500,00091, 2015.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse regression under adversarial corruption. In International Conference on Machine Learning, pp- 774-787 PMLR, 2013.
Myung Jin Choi, Vincent YF Tan, Animashree Anandkumar, and Alan Willsky, Learning latent tree graphical models. J. of Machine Learning Research, 12:1771-1812, 2011.
Gautam Dasarathy. Gaussian graphical model selection from size constrained measurements. In 2019 IEEE International Symposium on Information Theory (ISTT), pp. 1302-1306. IEEE, 2019.
Gautam Dasarathy, Robert Nowak, and Sebastien Roch. Data requirement for phylogenetic inference from multiple loci: a new distance method. IEEE/ACM transactions on computational biology and bioinformatics, 12(2):422 432, 2014.
Gautam Dasarathy, Elchanan Mossel, Robert Nowak, and Scbastien Roch. A stochastic farris transform for genetic data under the multispecies coalescent. with applications to data requirements. Journal of Mathematical Biology, 84(5):1 37, 2022.
Deepiyoti Deka, Ross Baldick, and Sriram Vishwanath. One breaker is enough: Hidden topology attacks on power grids. In 2015 IEEE Power & Energy Society General Meeting, pp. 1-5. LEEE, 2015.
Deepjyoti Deka, Saurav Talukdar, Michael Chertkov, and Murti V Salapaka. Graphical models in meshed distribution grids: Topology estimation, change detection & limitations. IEEE Transactions Smart Grid, 11(5):4299 4310, 2020.
Mathias Drton and Marloes Н. Maathuis. Structure learning in graphical modeling. Annual Review of Stalislics and Its Application, 4:365 393, 2017.
Péter Erdös, Michael Steel, LászóóA Székely, and Tandy Warnow. few logs suffice to build (almost) all trees: Part ii Theoretical Computer Science, (112))):77-1118 1999.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, (13):432-441, 2008.
F. Harary. Graph Theory. Addison Wesley series in mathematics. Addison- Addison-Wesley, 1971.
Roger Horn and Charles R Johnson. Matriz analysis. Cambridge university press, 2012.
Jiumn T Hwang. Multiplicative errors-in-variables models with applications to recent data released by the us department of energy. Journal of the American Statistical Association, 81(395):680-63) 688, 1986.
Stephen J Iturria, Raymond Carroll, and David Firth. Polynomial regression and estimating functions in the presence of multiplicative measurement error. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64( 561, 1999.
Markus Kalisch and Peter Bühlman. Estimating high-dimensional directed acyclic graphs with the pc-
algorithm. Journal of Machine Learning Research, 8(3), 2007.
Ashish Katiyar, Jessica Hoffmann, and Constantine Caramanis. Robust estimation of tree structured gaussian graphical models. In International Conference on Machine Learning, pp. 3292 3300. PMLR, 2019.
Ashish Katiyar, Vatsal Shah, and Constantine Caramanis. Robust estimation of tree structured ising models.
arXiv preprint ar (f::2006000600 2020.
Minje Kim and Paris Smaragdis. Single channel source scparation using smooth nonnegative matrix factorization with markov random fields. In 2013 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2013.
Akshay Krishnamurthy and Aarti Singh. Robust multi-source network tomography using selective probes. In 2012 Proceedings IEEE INFOCOM, 1629-10290 1637. IEEE, 2012.
Steffen I. Lauritzen. Graphcal models, volume 17. Clarendon Press, 1996.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Roderick JA Little and Donald B Rubin. Statistical analysis with missing data. John Wiley & Sons, 2019.
Po-Ling Loh and Xin Lu Tan. High-dimensional robust precision matrix estimation: Cellwise corruption under epsilon-cotammintton. Electronic Journal of Statistics, 12(1):1429-144) 1467, 2018.
Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in Neural Information Processing Systems, 24, 2011.
Karim Lounici. High-dimensional covariance matrix estimation with missing observations. Bernoulli, 20(3): 1029 1058, 2014.
Marlocs Maathuis, Mathias Drton, Steffen Lauritzen, and Martin Wainwright. Handbook of graphical models. CRC Press, 2018.
Nicolai Meinshausen and Peter Bühhmann. Stability selection. Journal of the Royal Slatislical Sociely Series B: Statistical Methodology, 72(4):417-47) 473, 2010.
Kevin Murphy, Yair Weiss, and Michael T Jordan. Loopy belief propagation for approximate inference: An empirical study. arXiv preprint (XXx::301.6773 2013.
Viet Anh Nguyen, Daniel Kuhn, and Peyman Mohajerin Esfahani. Distributionally robust inverse covariance cstimation: The wasserstein shrinkage estimator. Operations Research, 70(1):490-515, 2022.
Konstantinos E Nikolakakis, Dionysios S Kalogerias, and Anand D Sarwate. Learning tree structures from noisy data, In The 22nd International Conference Artificiol Intelligence and Statistics, pp. 1771-1782. PMLR, 2019.
Viktoria Öllerer and Christophe Croux. Robust high dime-ddiee precision matrix estimation. In Modern nonparametric, robust and multivariate methods, pp. 325-350. Springer, 2015.
Thomas Ott and Ruedi Stoop. The neurodynamics of belief propagation binary markov random fields. Advances in neural informalion processing systems, 19, 2006.
Naruya Saitou and Masatoshi Nei. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular biology and evolution, 4(4):406 1987.
Tapio Schneider. Analysis of incomplete climate data: Estimation of mean values and covariance matrices and imputation of missing values. Journal of climate, 14(5):853-88) 3-71,, 2001.
Charles Semple and Mike Steel. Phylogenetics, volume 24. Oxford University Press on Demand, 2003.
Herbert A Simon. The architecture of complexity. In The Roots of Logistics, pp. 335 335-361. Springer, 2012.
De Wen Soh and Sekhar C Tatikknda. Testing unfaithful gaussian graphical models. Advances in Neural Information Processing Systems, 27:2681 2689, 2014.
Olaf Sporns. Graph theory methods: applications in brain networks. Dialogues in clinical neuroscience, 2018.
Hokeun Sun and Hongzhe Li. Robust gaussian graphical modeling via 11 penalization. Biometrics, 68(4): 1197-1206, 2012.
Anshoo Tandon, Aldric Han, and Vincent Tan. Sga: robust algorithu for partial recovery of tree-structured graphical models with noisy samples. In International Conference on Machine Learning, pp. 10107-1011 PMLR, 2021.
Caroline Uhler, Garvesh Raskutti, Peter Bühlmann, and Bin Yu. Geometry of the faithfulness assumption in causal inference. The Annals of Statistics, pp. 436 436-463, 2013.
Giuseppe Vinci, Gautam Dasarathy, and Genevera Allen. Graph quilting: graphical model selection from partially observed covariances. Xiv preprint mixi::1112 05573, 2019.
15

---

Published in Transactions on Machine Learning Research (04/2025)
Jun-Kun Wang and Shou-de Lin. Robust inverse covariance estimation under noisy measurements. In International Conference on Machine Learning, pp- PMLR, 2014.
Qinfeng Xu and Jinhong You. Covariate selection for linear errors-in-variables regression models. Communi- cations in Slalistics-Thee Theory and Methods, 36(2):375 386, 2007.
Eunho Yang and Aurélie C Tozano. Robust gaussian graphical modeling with the trimmed graphical lasso. Advances in Neural Information Processing Systems, 28, 2015.
Fengzhuo Zhang and Vincent Tan. Robustifying algorithms of learning latent trees with vector variables. Advances in Neural Information Processing Systems, 34, 2021.
Lili Zheng and Genevera Allen. Graphical model inference with erosely measured data. Journal of the American Statistical Association, 119(547):2282-25) -2993, 2024.
Yiming Zuo, Yi Cui, Guoqiang Yu, Ruijiang Li, and Habtom W Ressom. Incorporating prior biological knowledge for network-based differential gene expression analysis using ially weighted graphical lasso, BMC bioinformatics, 18(1):1-14 14, 2017.
16


Reviews:
[{"review_id": "XIRnf26XsO", "reviewer": "Reviewer_k1Ff", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper and reasoning are well structured, explanation as clear and easy to follow\n- Unidentifiability result as well as the NoMAD algorithm and its theoretical analysis as rigorous and sound, giving a strong grounding to the method\n- Method presented opens a number of future research avenues\n- Experimental results look promising\n\n\nWeaknesses:\n- I believe the main weakness of the paper is the fairly limited experimental section: the experiments presented are only on generated data, and the analysis of the results is not very detailed. \n- Following on the previous point, the only benchmark method shown was Graphical Lasso, while it would have been a good reference to show how NoMAD performs compared to other sparse inverse covariance matrix estimation methods, e.g. [1]\n- Another weakness: no code for reproducibility\n\n[1] D. Bertsimas, J. Lamperski, J. Pauphilet, Certifiably Optimal Sparse Inverse Covariance Estimation", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The problem tackled by the paper is how to estimate the underlying graph structure of a Gaussian Graphical Model simply from data, and in the presence of noise. In other words, it is about estimating the sparsity structure of the covariance matrix from data of the form Y = X + D, where D is a diagonal of noise - where each noise component has a potentially different variance or can be 0. \nAfter giving some background presentation of the problem, the paper then introduces its main theoretical result (Theorem 3.1) which states that it is only possible to recover the graph structure up to an equivalence class in the presence of noise. \nIt then introduces the NoMAD algorithm, which aims at estimating this equivalence class. Note that both the theoretical result and the NoMAD algorithm do not assume a given structure of the graph to be estimated (unlike prior literature presented which assumed the structure to be a tree).\nThe paper finally provides some theoretical analysis of both the finite sample and asymptotic performance of NoMAD before showing some experimental results on generated data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TzcALizyX8", "reviewer": "Reviewer_86eb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe authors make a novel contribution by establishing an equivalence class for general graphs, which serves as a foundation for their work. In particular, the introduction of the “articulated set tree” and its innovative use in developing an algorithm to uncover the underlying graph structure in Gaussian graphical models is interesting. The proposed NoMAD algorithm, along with its theoretical guarantees in the population setting, further underscores the novelty and significance of their approach.\n\n**Weaknesses**\n\nMy main concerns are regarding the assumptions:\n1. The proposed work relies on two key assumptions: strong faithfulness and strong ancestor consistency in the finite sample setting. However, the practicality of these assumptions is unclear. Uhler et al. (2013) demonstrated that the strong faithfulness assumption is highly restrictive, with a surprisingly large set of distributions failing to satisfy it, even for small graphs. This raises concerns about the practical applicability of the proposed algorithm. Could the authors comment on this limitation? Furthermore, a discussion on the applicability of the strong ancestor consistency assumption in finite sample settings would also be valuable. Does the proposed approach require prior knowledge of $\\gamma$ and $\\zeta$?\n2. The experimental setup requires further clarification. The experiments appear to be conducted on small graphs, raising questions about the scalability of the algorithm. Additionally, could the authors explain the meaning of the x-axis and y-axis in the plots presented in the main paper? Regarding the noise matrix, how many diagonal entries were non-zero? Furthermore, does the number of non-zero corrupted entries impact the algorithm’s performance? Providing more details on these aspects would help better understand the evaluation framework and its implications.\n3. The authors mention the following as a critic of the existing works\n> unfortunately the conditional independence structure of the underlying distribution can be completely lost in general under such corruption; ..\n\nIs the proposed method (and the underlying assumptions) robust to noise/corruption?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors investigate the problem of structure learning for Gaussian graphical models using noisy samples. While previous studies have primarily focused on tree-structured graphs, this work extends the analysis to a broader class of graphs. The authors first define and characterize an equivalence class for general graphs, establishing a framework for the problem. Building on this, they propose an ancestor-discovery-based algorithm capable of identifying the underlying graph structure up to the specified equivalence class. The correctness of the algorithm is demonstrated under both population and sample settings, highlighting its theoretical validity.  Numerical experiments have been conducted to show the practical applicability of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the weaknesses highlighted in the previous section, I observed that the paper abruptly ends on page 1, with page 3 immediately following. This suggests that a significant portion of the related work section may be missing. The authors should verify whether the correct version of the manuscript was submitted.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PgV5lmXK86", "reviewer": "Reviewer_nXhJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n       \n1.) The paper gets close to a tight characterization of the limits of robust model selection in Gaussian graphical models.\n\n2.) An algorithm for estimating the equivalence class of the underlying graph structure is provided and explored theoretically.\n\n3.) Modulo some issues explained below, the results seem to be more or less correct.\n\n4.) Experiments comparing the proposed algorithm with an existing one are performed.  Both a real and a synthetic dataset are used.\n    \nWeaknesses:\n\n1.) Certain crucial statements may need revision in order to meet the correctness and clarity standards for acceptance, and there are several typos.  Please see the \"Requested changes\" section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the _robust model selection problem_ in the context of Gaussian graphical models (GGM).  Model selection in this context refers to the statistical problem of recovery of the sparsity pattern (an adjacency matrix) of the signal matrix of the GGM.  The word ``robust'' refers to a twist on the basic model selection problem in which Gaussian noise is added, independently to each variable.  The distribution of the noise for each variable need not be identically distributed.\n\nThe primary contributions of the paper toward this problem are \n(i) a non-identifiability result -- namely, that there is a notion of equivalence on graphs that governs the extent to which sparsity patterns are recoverable; \n(ii) an algorithm -- NoMAD for estimating the equivalence class of the underlying graph structure of the model from samples;\n(iii) a theoretical accuracy analysis of NoMAD in both the population and finite-sample regimes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical requests/questions:\n\n1.) Theorem 3.1 seems to say that for a graph $G$, there is at least one graph $H$ in the equivalence class of $G$ whose noisy observations have the same distribution as those for $G$.  Isn't this trivial as stated?  After all, the equivalence class of $G$ contains $G$ itself.  Thus, either Theorem 3.1 is trivial, or needs to be revised.\n\n2.) It seems like the statement at the top of page 6 (``... we know that any graph is only identifiable upto the equivalence relation in Definition 3.2'') is not an accurate interpretation of Theorem 3.1.  In particular, in order for this to be the correct interpretation, Theorem 3.1 would have to say that its conclusions hold _for all $H \\in [G]$_.  As it is stated, it leaves open the possibility that there is potential for confusion among only some subset of elements of $[G]$.  This should be reworded.\n\n3.) On page 5, it is stated that any graph whose AST is equal to $T_{AST}(G)$ is in $[G]$, and hence the authors will use $T_{AST}(G)$ to denote $[G]$.  I understand that the first statement is correct.  However, it is not clear to me that every element $H$ of $[G]$ has the same AST.  It is true, however, that all elements of $[G]$ have isomorphic ASTs.\n\n\n4.) Given issue 2, I think that it would be appropriate to clarify in the introduction whether or not the present work completely solves the problem.  My understanding is that the proposed algorithm correctly identifies the equivalence class of the graph $G$, but the non-identifiability result (Theorem 3.1) does not imply that this is the limit of what can be identified.\n\n\nNon-critical requested changes:\n\n1.) There is a sentence fragment at the end of the first page.  Please correct it.\n\n2.) The caption of Theorem 3.1 seems strange.  Would it be better to call it \"Non-identifiability\"?  If so, please do so.\n\n3.) In Fact 1, page 6, $\\rho$ is not defined yet.\n\n4.) In the appendix, page 16, it is stated that ``... in this phase, it returns a collection $\\mathfrak{B}$ of vertex triplets...''.  I believe that $\\mathfrak{B}$ should be a collection of sets of vertex triplets, right?  This should be corrected, if so.\n\n5.) In Theorem 5.3, the constant $C$ is uniform over all $\\tau$, right?  The ordering of the quantifiers makes this slightly confusing.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After discussion, all reviewers are in favour of acceptance as-is.
Decision: Accept (poster)