Xiao-Ming Wu, Zhenguo Li, Shih-Fu Chang. New Insights into Laplacian Similarity Search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Pages 1949-1957, 2015.
Download paper:
Adobe portable document (pdf) 
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Supplementary material available here
Graph-based computer vision applications rely critically on similarity metrics which compute the pairwise similarity between any pair of vertices on graphs. This paper investigates the fundamental design of commonly used similarity metrics, and provides new insights to guide their use in practice. In particular, we introduce a family of similarity metrics in the form of $(L+\alpha\Lambda)^{-1}$, where $L$ is the graph Laplacian, $\Lambda$ is a positive diagonal matrix acting as a regularizer, and $\alpha$ is a positive balancing factor. Such metrics respect graph topology when $\alpha$ is small, and reproduce well-known metrics such as hitting times and the pseudo-inverse of graph Laplacian with different regularizer $\Lambda$. This paper is the first to analyze the important impact of selecting $\Lambda$ in retrieving the local cluster from a seed. We find that different $\Lambda$ can lead to surprisingly complementary behaviors: $\Lambda = D$ (degree matrix) can reliably extract the cluster of a query if it is sparser than surrounding clusters, while $\Lambda = I$ (identity matrix) is preferred if it is denser than surrounding clusters. Since in practice there is no reliable way to determine the local density in order to select the right model, we propose a new design of $\Lambda$ that automatically adapts to the local density. Experiments on image retrieval verify our theoretical arguments and confirm the benefit of the proposed metric. We expect the insights of our theory to provide guidelines for more applications in computer vision and other domains
Xiao-Ming Wu
Zhenguo Li 
Shih-Fu Chang
@InProceedings{wu2015new,
Author = {Wu, Xiao-Ming and Li, Zhenguo and Chang, Shih-Fu},
Title = {New Insights into Laplacian Similarity Search},
BookTitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
Pages = {1949--1957},
Year = {2015}
}
Get EndNote Reference (.ref)
For problems or questions regarding this web site contact The
Web Master.
This document was translated automatically from BibTEX by bib2html (Copyright 2003 © Eric Marchand, INRIA, Vista Project).