Combinatorial inference for graphical models

Matey Neykov; Junwei Lu; Han Liu

doi:10.1214/17-AOS1650

Combinatorial inference for graphical models

Matey Neykov, Junwei Lu, Han Liu

Computer Science

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

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	https://doi.org/10.1214/17-AOS1650
State	Published - Apr 2019

Funding

2Supported by NSF Grant DMS-1454377-CAREER; NSF Grant IIS1546482-BIGDATA; NIH Grant R01MH102339; NSF Grant IIS1408910; NIH Grant R01GM083084. The authors would like to thank the Editor, Associate Editor and two referees for their suggestions, comments and remarks which led to significant improvements in the presentation of this manuscript.

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

Access to Document

10.1214/17-AOS1650

Cite this

@article{dc1ed8ecc4054a0b86f164c3e99fbb3d,

title = "Combinatorial inference for graphical models",

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.",

keywords = "Graph structural inference, Minimax testing, Multiple hypothesis testing, Post-regularization inference, Uncertainty assessment",

author = "Matey Neykov and Junwei Lu and Han Liu",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2019.",

year = "2019",

month = apr,

doi = "10.1214/17-AOS1650",

language = "English (US)",

volume = "47",

pages = "795--827",

journal = "Annals of Statistics",

issn = "0090-5364",

publisher = "Institute of Mathematical Statistics",

number = "2",

}

TY - JOUR

T1 - Combinatorial inference for graphical models

AU - Neykov, Matey

AU - Lu, Junwei

AU - Liu, Han

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2019.

PY - 2019/4

Y1 - 2019/4

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

AN - SCOPUS:85060181294

SN - 0090-5364

VL - 47

SP - 795

EP - 827

JO - Annals of Statistics

JF - Annals of Statistics

IS - 2

ER -

Combinatorial inference for graphical models

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this