Efficient detection and localization on graph structured data

Abstract

The problem of efficiently identifying regions of interest arises in the context of surveillance, monitoring and exploration of a large area or network involving social, sensor, communication network data. We formulate these problems in terms of locating optimum values of signals on graphs. In this perspective we associate features with nodes/edges of a graph where the maxima/minima of these features correspond to interest points. We develop an algorithm that adaptively probes local sub-collection of nodes (local regions) on the graph and sequentially refines the search space from noisy averaged returns from each probed region. The size of the region determines the cost of the probe with larger regions corresponding to lower cost. Our goal is to minimize regret after T rounds with minimal budget/cost. Under suitable smoothness conditions on the signal we show that after T rounds the cumulative regret scales optimally as O(equation) with significant cost gain over other state-of-art techniques.