Large-Scale Inference in Errorfully Observed Attributed Graphs

• Activity Number: 4
• Type: Invited
• Date/Time: Sunday, July 29, 2012 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Carey E Priebe*+ and Daniel Sussman+ and Minh Tang+ and Donniell Fishkind+ and Joshua Vogelstein+
• Companies: The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University
• Keywords: stochastic block model ; graph ; network ; inference ; content-derived attributes ; errorful attributes

Abstract

Attributed graphs -- interaction profiles with content-derived attributes on the edges and the vertices -- provide a rich data representation for important applications. Inference tasks such as structure identification, vertex assignment, change and anomaly detection, etc., arise in numerous applications. One class of approaches involves inference on the graphs directly, via invariant theory. Alternatively, embedding such graphs in some low-dimensional space can, in some cases, provide consistent inference. In either case, realistically, the graphs will be errorfully observed -- mis-attributed and/or missing edges and vertices, for instance. A particularly promising design of experiments research and development program involves optimizing the quantity/quality/cost trade-off under errorful observation constraints for some class of inference tasks.