Motivation. Traffic congestion on roadways has been identified by the US Department of Transportation as one of “the largest threats to the economic prosperity of the nation”. [5]. A common contributor to congestion include traffic incidents. Detection congestion events and resolving incidents is of paramount importance: research has shown that early incident detection resulted in reduction of 143.3 million man-hours and savings of $3.06 million in 2007 [6]. Fortunately, data collected by a variety of sensors positioned along highways can serve as important early indicators of traffic incidents. Each of these sensors continuously acquire and store multiple time series corresponding to (average) vehicle speed, (average) road occupancy, weather conditions, and so on [1, 2]. These sensors can be naturally modeled as nodes of a graph (which reflects the topology of the road network), and the data corpus can be modeled as a multi-dimensional time series. Quickly identifying anomalies in this corpus enables rapid incident detection and timely response.