Combinatorial inference for graphical models

Matey Neykov, Junwei Lu, Han Liu

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 languageEnglish (US)
Pages (from-to)795-827
Number of pages33
JournalAnnals of Statistics
Volume47
Issue number2
DOIs
StatePublished - Apr 1 2019

Fingerprint

Graphical Models
Testing
Graph in graph theory
Lower bound
Graph Connectivity
Point Estimation
Statistical Inference
Maximum Degree
Minimax
Packing
Buffer
Entropy
Cycle
Numerical Results
Graphical models
Inference
Graph
Family
Lower bounds

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

Neykov, Matey ; Lu, Junwei ; Liu, Han. / Combinatorial inference for graphical models. In: Annals of Statistics. 2019 ; Vol. 47, No. 2. pp. 795-827.
@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",
year = "2019",
month = "4",
day = "1",
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",

}

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 journalArticle

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 -