Abstract
We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity, the presence of a cycle of certain size, or the maximum degree of the graph. To begin with, we study the information-theoretic limits of a large family of combinatorial inference problems. We propose new concepts including structural packing and buffer entropies to characterize how the complexity of combinatorial graph structures impacts the corresponding minimax lower bounds. On the other hand, we propose a family of novel and practical structural testing algorithms to match the lower bounds. We provide numerical results on both synthetic graphical models and brain networks to illustrate the usefulness of these proposed methods.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 795-827 |
| Number of pages | 33 |
| Journal | Annals of Statistics |
| Volume | 47 |
| Issue number | 2 |
| DOIs | |
| State | Published - Apr 1 2019 |
Fingerprint
Keywords
- Graph structural inference
- Minimax testing
- Multiple hypothesis testing
- Post-regularization inference
- Uncertainty assessment
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
Cite this
}
Combinatorial inference for graphical models. / Neykov, Matey; Lu, Junwei; Liu, Han.
In: Annals of Statistics, Vol. 47, No. 2, 01.04.2019, p. 795-827.Research output: Contribution to journal › Article
TY - JOUR
T1 - Combinatorial inference for graphical models
AU - Neykov, Matey
AU - Lu, Junwei
AU - Liu, Han
PY - 2019/4/1
Y1 - 2019/4/1
N2 - We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity, the presence of a cycle of certain size, or the maximum degree of the graph. To begin with, we study the information-theoretic limits of a large family of combinatorial inference problems. We propose new concepts including structural packing and buffer entropies to characterize how the complexity of combinatorial graph structures impacts the corresponding minimax lower bounds. On the other hand, we propose a family of novel and practical structural testing algorithms to match the lower bounds. We provide numerical results on both synthetic graphical models and brain networks to illustrate the usefulness of these proposed methods.
AB - We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity, the presence of a cycle of certain size, or the maximum degree of the graph. To begin with, we study the information-theoretic limits of a large family of combinatorial inference problems. We propose new concepts including structural packing and buffer entropies to characterize how the complexity of combinatorial graph structures impacts the corresponding minimax lower bounds. On the other hand, we propose a family of novel and practical structural testing algorithms to match the lower bounds. We provide numerical results on both synthetic graphical models and brain networks to illustrate the usefulness of these proposed methods.
KW - Graph structural inference
KW - Minimax testing
KW - Multiple hypothesis testing
KW - Post-regularization inference
KW - Uncertainty assessment
UR - http://www.scopus.com/inward/record.url?scp=85060181294&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85060181294&partnerID=8YFLogxK
U2 - 10.1214/17-AOS1650
DO - 10.1214/17-AOS1650
M3 - Article
VL - 47
SP - 795
EP - 827
JO - Annals of Statistics
JF - Annals of Statistics
SN - 0090-5364
IS - 2
ER -