An iterated graph laplacian approach for ranking on manifolds
An iterated graph laplacian approach for ranking on manifolds
复制标题
DOI：
10.1145/2020408.2020556
复制
发表时间：
2011-08
影响因子：
8.3
通讯作者：
Xueyuan Zhou;M. Belkin;N. Srebro
中科院分区：
文献类型：
--
作者：
Xueyuan Zhou;M. Belkin;N. Srebro
排序是信息检索中的关键问题之一。最近，基于假设数据是从嵌入在高维欧氏空间中的低维流形采样的一类排序算法引起了极大的兴趣。在本文中，我们使用分析方法研究了一种流行的基于图拉普拉斯的排序算法[23]，它为超越直观的“扩散”概念的排序算法提供了理论上的见解。我们的分析表明，由于使用了对称的归一化图拉普拉斯，该算法对一个常用的参数很敏感。我们还证明了在无限样本的极限下，排序函数可以在查询点发散到无穷远。为了解决这些问题，我们提出了一种改进的基于迭代非归一化图拉普拉斯的格林函数的流形排序算法，该算法具有更强的健壮性和密度自适应性，并且在无限样本的限制下是逐点连续的。我们还首次在排名文献中经验性地探索了来自二次正规化图拉普拉斯的家族的两个变体。在文本和图像数据上的实验结果支持我们的分析，这也表明了二次归一化图拉普拉斯在实际应用中的潜在价值。
Ranking is one of the key problems in information retrieval. Recently, there has been significant interest in a class of ranking algorithms based on the assumption that data is sampled from a low dimensional manifold embedded in a higher dimensional Euclidean space. In this paper, we study a popular graph Laplacian based ranking algorithm [23] using an analytical method, which provides theoretical insights into the ranking algorithm going beyond the intuitive idea of "diffusion." Our analysis shows that the algorithm is sensitive to a commonly used parameter due to the use of symmetric normalized graph Laplacian. We also show that the ranking function may diverge to infinity at the query point in the limit of infinite samples. To address these issues, we propose an improved ranking algorithm on manifolds using Green's function of an iterated unnormalized graph Laplacian, which is more robust and density adaptive, as well as pointwise continuous in the limit of infinite samples. We also for the first time in the ranking literature empirically explore two variants from a family of twice normalized graph Laplacians. Experimental results on text and image data support our analysis, which also suggest the potential value of twice normalized graph Laplacians in practice.