Efficient large scale commute time embedding

7th International Conference on Applied Physics and Mathematics

物理学;数学

Hahn, H.I.^1

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;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/814/1/012010/pdf
DOI  :  10.1088/1742-6596/814/1/012010

来源: IOP

【 摘 要 】

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.