abstract bibtex

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 paper, we consider a graph G = (V,E). We wish to perform an inference task - the it surrogate inference task considered here is "vertex classification". However, we do not observe G; rather, for each potential edge uv in Vchoose2 we observe an "edge-feature" which we use to classify uv as edge/not-edge. Thus we it errorfully observe G when we observe the graph widetildeG = (V,widetildeE). 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 derive the optimal quantity/quality operating point for subsequent graph inference in the face of this trade-off.

@article{ title = {Statistical inference on errorfully observed graphs}, type = {article}, year = {2013}, identifiers = {[object Object]}, websites = {http://arxiv.org/abs/1211.3601}, id = {4c1a1a99-5850-336c-a0da-65e9da8ea72a}, created = {2015-06-19T08:32:46.000Z}, file_attached = {false}, profile_id = {182bbbf9-24a3-3af3-9ed6-563e8f89259b}, group_id = {8d229673-0aec-3014-b0f6-eda47f83e147}, last_modified = {2015-06-19T08:33:07.000Z}, read = {false}, starred = {true}, authored = {true}, confirmed = {true}, hidden = {false}, citation_key = {Priebe2012}, 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 paper, we consider a graph G = (V,E). We wish to perform an inference task - the it surrogate inference task considered here is "vertex classification". However, we do not observe G; rather, for each potential edge uv in Vchoose2 we observe an "edge-feature" which we use to classify uv as edge/not-edge. Thus we it errorfully observe G when we observe the graph widetildeG = (V,widetildeE). 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 derive the optimal quantity/quality operating point for subsequent graph inference in the face of this trade-off.}, bibtype = {article}, author = {Priebe, Carey E. and Sussman, Daniel L. and Tang, Minh and Vogelstein, Joshua T.}, journal = {arXiv preprint} }

Downloads: 0