Adaptive Graph-Based Algorithms for Online Semi-Supervised Learning and Conditional Anomaly Detection

We present graph-based methods for online semi-supervised learning and conditional anomaly detection. When data arrive in a stream, the problems of computation and data storage arise for any graph-based method. We propose a fast approximate online algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local representative points that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties.

We also present a graph-based method for detecting conditional outliers and apply it to the identification of unusual outcomes and patient-management decisions. Our hypothesis is that patient-management decisions that are unusual with respect to past patients may be due to errors and that it is worthwhile to raise an alert if such a condition is encountered. Conditional anomaly detection extends standard unconditional anomaly framework but also faces new problems known as fringe points and unconditional anomalies. We present an extensive human evaluation study of our methods by 15 experts in critical care.