TY - JOUR

T1 - Applicable and Partial Learning of Graph Topology Without Sparsity Priors

AU - Yuan, Yanli

AU - Soh, Dewen

AU - Xiong, Zehui

AU - Quek, Tony Q.S.

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2023/1/1

Y1 - 2023/1/1

N2 - This paper considers the problem of learning the underlying graph topology of Gaussian Graphical Models (GGMs) from observations. Under high-dimensional settings, to achieve low sample complexity, many existing graph topology learning algorithms assume structural constraints such as sparsity to hold. Without prior knowledge of graph sparsity, the correctness of their results is difficult to check. In this paper, we aim to do away with these assumptions by developing algorithms for learning degree-bounded GGMs and separable GGMs without any sparsity priors. The proposed algorithms, which are based only on the knowledge of conditional independence relations in the data distribution, require minimal structural assumptions while still achieving low sample complexity, and hence are 'applicable'. Specifically, for any user defined sparsity parameter k, we prove that the proposed algorithms can consistently identify whether a p-dimensional GGM is degree-bounded by k (or strongly k-separable) with Ω (k\log p) sample complexity. Besides, our algorithms also demonstrate 'partial' learning properties whenever the overall graph is not entirely sparse, that is, not all nodes are degree-bounded (or are strongly separable). In this case, we can still learn the sparse portions of the graph, with theoretical guarantees included. Numerical results show that existing algorithms fail even in some simple settings where sparsity assumptions do not hold, whereas our algorithms do not.

AB - This paper considers the problem of learning the underlying graph topology of Gaussian Graphical Models (GGMs) from observations. Under high-dimensional settings, to achieve low sample complexity, many existing graph topology learning algorithms assume structural constraints such as sparsity to hold. Without prior knowledge of graph sparsity, the correctness of their results is difficult to check. In this paper, we aim to do away with these assumptions by developing algorithms for learning degree-bounded GGMs and separable GGMs without any sparsity priors. The proposed algorithms, which are based only on the knowledge of conditional independence relations in the data distribution, require minimal structural assumptions while still achieving low sample complexity, and hence are 'applicable'. Specifically, for any user defined sparsity parameter k, we prove that the proposed algorithms can consistently identify whether a p-dimensional GGM is degree-bounded by k (or strongly k-separable) with Ω (k\log p) sample complexity. Besides, our algorithms also demonstrate 'partial' learning properties whenever the overall graph is not entirely sparse, that is, not all nodes are degree-bounded (or are strongly separable). In this case, we can still learn the sparse portions of the graph, with theoretical guarantees included. Numerical results show that existing algorithms fail even in some simple settings where sparsity assumptions do not hold, whereas our algorithms do not.

UR - http://www.scopus.com/inward/record.url?scp=85139443715&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139443715&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2022.3208732

DO - 10.1109/TNSE.2022.3208732

M3 - Article

AN - SCOPUS:85139443715

SN - 2327-4697

VL - 10

SP - 360

EP - 371

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

IS - 1

ER -