Statistical Inference on Errorfully Observed Graphs

Abstract

Statistical inference on graphs is a burgeoning field in the applied and theoretical statistics communities, as well as throughout the wider world of science, engineering, business, etc. In many applications, we are faced with the reality of errorfully observed graphs. That is, the existence of an edge between two vertices is based on some imperfect assessment. In this article, we consider a graph G = (V, E). We wish to perform an inference task—the inference task considered here is “vertex classification,” that is, given a vertex v with unknown label Y(v), we want to infer the label for v based on the graph G and the given labels for some set of vertices in G not containing v. However, we do not observe G; rather, for each potential edge $uv\in \left(\genfrac{}{}{0pt}{}{V}{2}\right)$ we observe an “edge feature” that we use to classify uv as edge/not-edge. Thus, we errorfully observe G when we observe the graph $\tilde{G}=(V,\tilde{E})$ as the edges in $\tilde{E}$ arise from the classifications of the “edge features,” and are expected to be errorful. Moreover, we face a quantity/quality trade-off regarding the edge features we observe—more informative edge features are more expensive, and hence the number of potential edges that can be assessed decreases with the quality of the edge features. We studied this problem by formulating a quantity/quality trade-off for a simple class of random graphs model, namely, the stochastic blockmodel. We then consider a simple but optimal vertex classifier for classifying v and we derive the optimal quantity/quality operating point for subsequent graph inference in the face of this trade-off. The optimal operating points for the quantity/quality trade-off are surprising and illustrate the issue that methods for intermediate tasks should be chosen to maximize performance for the ultimate inference task. Finally, we investigate the quantity/quality tradeoff for errorful observations of the C. elegans connectome graph.

Key Words:

• Classification
• Connectomics
• Error
• Graph
• Social networks

ACKNOWLEDGMENTS

This work is partially funded by the National Security Science and Engineering Faculty Fellowship (NSSEFF), the Johns Hopkins University Human Language Technology Center of Excellence (JHU HLT COE), and the XDATA program of the Defense Advanced Research Projects Agency (DARPA) administered through Air Force Research Laboratory contract FA8750-12-2-0303. We also thank the editors and the anonymous referees for their valuables comments and critiques that greatly improved this work.

Additional information

Notes on contributors

Carey E. Priebe

Carey E. Priebe, Department of Applied Math and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Minh Tang, Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Daniel L. Sussman, Department of Statistics, Harvard University, 1 Oxford St., Cambridge, MA 02138 (E-mail: [email protected]). Joshua T. Vogelstein, Johns Hopkins University, Institute for Computational Medicine and Department of Biomedical Engineering, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]).

Daniel L. Sussman

Carey E. Priebe, Department of Applied Math and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Minh Tang, Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Daniel L. Sussman, Department of Statistics, Harvard University, 1 Oxford St., Cambridge, MA 02138 (E-mail: [email protected]). Joshua T. Vogelstein, Johns Hopkins University, Institute for Computational Medicine and Department of Biomedical Engineering, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]).

Minh Tang

Carey E. Priebe, Department of Applied Math and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Minh Tang, Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Daniel L. Sussman, Department of Statistics, Harvard University, 1 Oxford St., Cambridge, MA 02138 (E-mail: [email protected]). Joshua T. Vogelstein, Johns Hopkins University, Institute for Computational Medicine and Department of Biomedical Engineering, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]).

Joshua T. Vogelstein

Carey E. Priebe, Department of Applied Math and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Minh Tang, Department of Applied Mathematics and Statistics, Johns Hopkins University, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]). Daniel L. Sussman, Department of Statistics, Harvard University, 1 Oxford St., Cambridge, MA 02138 (E-mail: [email protected]). Joshua T. Vogelstein, Johns Hopkins University, Institute for Computational Medicine and Department of Biomedical Engineering, 3400 N. Charles St., Baltimore, MD 21218 (E-mail: [email protected]).