Graph Shift: A Robust Approach Towards Graph Mode Analysis
Prof. Shuicheng Yan, National University of Singapore
Monday, June 7, 2010 - 11:00am
EE Dept. Conference Room, Mudd 1300
Abstract
Graph is a general and popular representation method, which can describe complex high order relations through pairwise relations (edges). Since a high order relation can be regarded as the ensemble of all pairwise relations within it, for a graph, its underlying high order relations usually constitute dense subgraphs. Such dense subgraphs are hardly produced by accident, and also very robust to noises and outliers. In this paper, we define graph modes, which are the local maxima of graph density functions, to represent such dense subgraphs. We also propose the graph shift procedure, which starts from every vertex, iteratively shifts towards the nearest graph mode along a certain trajectory, to efficiently enumerate such dense subgraphs. The relation of graph modes and the modes of density functions in feature space is also established, which reveals the advantages of graph modes. Algorithms for two general tasks, correspondence problems and cluster analysis, are described as applications. Both theoretic analysis and experimental results show that graph shift procedure is very efficient and robust, especially when there exists large amount of noises and outliers.
Speaker Bio
Dr. Shuicheng Yan is currently an Assistant Professor in the Department of Electrical and Computer Engineering at National University of Singapore, and the founding lead of the Learning and Vision Research Group. Dr. Yan's main research areas include computer vision, multimedia and machine learning area. He is an associate editor of IEEE Transactions on Circuits and Systems for Video Technology, and has been serving as the guest editor of the special issue for Computer Vision and Image Understanding. He is an ad hoc reviewer for more than 10 international journals such as TPAMI, TCSVT, TIP, and TKDE, and program committee members for more than 10 international conferences such as ICCV, CVPR and ACM MM.