Efficient large scale commute time embedding
[摘要] Commute time embedding involves computing eigenfunctions of the graph Laplacian matrix. Spectral decomposition requires computational burden proportional to O(n3), which may not be suitable for large scale dataset. This paper proposes computationally efficient commute time embedding by applying Nyström method to the normalized graph Laplacian. The performance of the proposed algorithms is analysed by checking the embedding results on a patch graph.
[发布日期] [发布机构] Department of Information and Communications Eng., Hankuk University of Foreign Studies, 89 Wangsan, Mohyun, Kyonggi-Do, Yongin; 449-791, Korea, Republic of^1
[效力级别] 数学 [学科分类]
[关键词] Commute time embedding;Computational burden;Computationally efficient;Graph Laplacian;Large-scale dataset;M method;Normalized graph Laplacian;Spectral decomposition [时效性]
