Large-Scale Graph Sinkhorn Distance Approximation for Resource-Constrained Devices

Sinkhorn distance plays an important role in graph analysis. One drawback of Sinkhorn distance is high computational cost, where Sinkhorn iteratively calculates the matrix-vector product of an n×n matrix K and an n×1 vector. With a moderate large n, this calculation is time consuming, especially in the case of limited computational resources. One promising solution is low-rank approximation, K=LLT, where L∈Rn×r. The matrix-vector product then can be done in O(nr) instead of O(n2). In this paper, we propose an efficient method to accurately approximate K and hence accelerate Sinkhorn calculation. We give the error upper bound of approximating K and suggest using kernel k-means to select landmarks. We further show that the optimal L, in terms of error upper bound, can be efficiently obtained by an eigendecompostion of complexity O(r3), rather than the original O(n3). Experimental results show that our method obtains 31× speedup when n=5000 compared with the original Sinkhorn. On MNIST36, our error is 0.31% of that of Recursive Nyström. On STL-10 with a small Gaussian kernel scale parameter, the proposed method can deal with 86.2% of distances while the competing methods fail to work, indicating our robustness against the rank decay problem.