Invariant Theory for Hypothesis Testing on Graphs
Carey E. Priebe1, Glen A. Coppersmith1, Andrey Rukhin2
1Johns Hopkins University; 2NSWC Dahlgren

Hypothesis testing on graphs has application in areas as diverse as connectome inference (wherein vertices are neurons or brain regions), social network analysis (wherein vertices represent individual actors or organizations), and text processing (wherein vertices represent authors or documents). Graph invariants – functions on graphs that do not depend on the particular labeling of the vertices – can be used as test statistics for deciding between a null versus an alternative model.

However, even for simple models the exact distribution is unavailable for most invariants. Furthermore, comparative analyses of statistical power at some given Type I error rate for competing invariants, via both Monte Carlo and large sample approximation, demonstrate that simple settings can yield interesting comparative power phenomena.

In particular, two forthcoming articles investigating comparative power of simple invariants in the independent edge setting show that for small graphs (1000 vertices) the comparative power surface is complicated [1] and limiting behavior may be misleading except for astronomically large graphs [2].

In this paper, limiting null and alternative distributions for various invariants under various latent position models for attributed graphs [3] are derived, and power comparisons are performed using limit theory to provide large sample approximations. Monte Carlo analyses augment the limit theory.


[1] Pao, Coppersmith, and Priebe, Statistical Inference on Random Graphs: Comparative Power Analyses via Monte Carlo, Journal of Computational and Graphical Statistics, to appear.

[2] Rukhin and Priebe, A Comparative Power Analysis of the Maximum Degree and Size Invariants for Random Graph Inference, Journal of Statistical Planning and Inference, to appear.

[3] Lee and Priebe, A Latent Process Model for Time Series of Attributed Random Graphs, Statistical Inference for Stochastic Processes, to appear.

Keywords: Random graph; Invariant theory; Large sample approximation; Statistical power

Biography: Carey E. Priebe is Professor in the Department of Applied Mathematics and Statistics at Johns Hopkins University, Baltimore, Maryland, USA.

His research interests include statistical inference for high-dimensional and graph-valued data.

He is an Elected Member of the International Statistical Institute and a Fellow of the American Statistical Association.