Mode-seeking on graphs via random walks

Mode-seeking has been widely used as a powerful data analysis technique for clustering and filtering in a metric feature space. We introduce a versatile and efficient mode-seeking method for “graph” representation where general embedding of relational data is possible beyond metric spaces. Exploiting the global structure of the graph by random walks, our method intrinsically combines mode-seeking with ranking on the graph, and performs robust analysis by seeking high-ranked authoritative data and suppressing low-ranked noise and outliers. This enables mode-seeking to be applied to a large class of challenging real-world problems involving graph representation which frequently arises in computer vision. We demonstrate our method on various synthetic experiments and real applications dealing with noisy and complex data such as scene summarization and object-based image matching.