Applicable and Partial Learning of Graph Topology Without Sparsity Priors

Yanli Yuan, Dewen Soh, Zehui Xiong, Tony Q.S. Quek

研究成果: Article同行評審


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.

頁(從 - 到)360-371
期刊IEEE Transactions on Network Science and Engineering
出版狀態Published - 2023 1月 1

All Science Journal Classification (ASJC) codes

  • 控制與系統工程
  • 電腦科學應用
  • 電腦網路與通信


深入研究「Applicable and Partial Learning of Graph Topology Without Sparsity Priors」主題。共同形成了獨特的指紋。