Poster
Sketching Method for Large Scale Combinatorial Inference
Wei Sun · Junwei Lu · Han Liu

Wed Dec 5th 10:45 AM -- 12:45 PM @ Room 210 #88

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. We validate our theory and method through both synthetic simulations and a real application in neuroscience.

Author Information

Will Wei Sun (University of Miami Business School)
Junwei Lu
Han Liu (Northwestern)

More from the Same Authors