We present computationally efficient algorithms to test various combinatorial structures of large-scale graphical models. In order to test the hypotheses on their topological structures, we propose two adjacency matrix sketching frameworks: neighborhood sketching and subgraph sketching. The neighborhood sketching algorithm is proposed to test the connectivity of graphical models. This algorithm randomly subsamples vertices and conducts neighborhood regression and screening. The global sketching algorithm is proposed to test the topological properties requiring exponential computation complexity, especially testing the chromatic number and the maximum clique. This algorithm infers the corresponding property based on the sampled subgraph. Our algorithms are shown to substantially accelerate the computation of existing methods.

This paper introduces sketching based hypothesis tests for some combinatorial properties of Gaussian graphical models. The authors introduce two sketching procedures --- neighborhood sketching and subgraph sketching, and establish that these procedures control FWER, while being computationally efficient. They supplement their theoretical investigations with simulation experiments and carry out a real data analysis. The article attempts to bring together two disparate lines of research--- developments in minimax global testing and multiple testing communities in Statistics on one hand, and Property testing problems in the theoretical computer science literature on the other. I feel this line of research would be of interest to the community, and could lead to interesting future developments.

We present computationally efficient algorithms to test various combinatorial structures of large-scale graphical models. In order to test the hypotheses on their topological structures, we propose two adjacency matrix sketching frameworks: neighborhood sketching and subgraph sketching. The neighborhood sketching algorithm is proposed to test the connectivity of graphical models. This algorithm randomly subsamples vertices and conducts neighborhood regression and screening. The global sketching algorithm is proposed to test the topological properties requiring exponential computation complexity, especially testing the chromatic number and the maximum clique.