Although numerous clustering algorithms have been developed, many existing
methods still leverage k-means technique to detect clusters of data points.
However, the performance of k-means heavily depends on the estimation of
centers of clusters, which is very difficult to achieve an optimal solution.
Another major drawback is that it is sensitive to noise and outlier data. In
this paper, from manifold learning perspective, we rethink k-means and present
a new clustering algorithm which directly detects clusters of data without mean
estimation. Specifically, we construct distance matrix between data points by
Butterworth filter such that distance between any two data points in the same
clusters equals to a small constant, while increasing the distance between
other data pairs from different clusters. To well exploit the complementary
information embedded in different views, we leverage the tensor Schatten p-norm
regularization on the 3rd-order tensor which consists of indicator matrices of
different views. Finally, an efficient alternating algorithm is derived to
optimize our model. The constructed sequence was proved to converge to the
stationary KKT point. Extensive experimental results indicate the superiority
of our proposed method.

该论文提出了一种基于流形学习和张量正则化的聚类算法，不同于传统的基于 k-means 的方法，该算法通过构建距离矩阵来直接检测数据簇，同时应用于多视图数据中，证明了其优越性能。

从流形学习的角度重新思考 k-means

Rethinking k-means from manifold learning perspective

Graph Neural Networks (GNNs) are often used for tasks involving the geometry
of a given graph, such as molecular dynamics simulation. While the distance
matrix of a graph contains the complete geometric structure information,
whether GNNs can learn this geometry solely from the distance matrix has yet to
be studied. In this work, we first demonstrate that Message Passing Neural
Networks (MPNNs) are insufficient for learning the geometry of a graph from its
distance matrix by constructing families of geometric graphs which cannot be
distinguished by MPNNs. We then propose $k$-DisGNNs, which can effectively
exploit the rich geometry contained in the distance matrix. We demonstrate the
high expressive power of our models and prove that some existing well-designed
geometric models can be unified by $k$-DisGNNs as special cases. Most
importantly, we establish a connection between geometric deep learning and
traditional graph representation learning, showing that those highly expressive
GNN models originally designed for graph structure learning can also be applied
to geometric deep learning problems with impressive performance, and that
existing complex, equivariant models are not the only solution. Experimental
results verify our theory.

该研究提出了一种新型的图神经网络 $k$-DisGNNs，用于从距离矩阵中学习图的几何结构，实现了图结构学习和几何深度学习的统一，并证明了其高表达能力与卓越性能。

距离矩阵是否足以支持几何深度学习？

Is Distance Matrix Enough for Geometric Deep Learning?

A distance matrix $A \in \mathbb R^{n \times m}$ represents all pairwise
distances, $A_{ij}=\mathrm{d}(x_i,y_j)$, between two point sets $x_1,...,x_n$
and $y_1,...,y_m$ in an arbitrary metric space $(\mathcal Z, \mathrm{d})$. Such
matrices arise in various computational contexts such as learning image
manifolds, handwriting recognition, and multi-dimensional unfolding.
In this work we study algorithms for low-rank approximation of distance
matrices. Recent work by Bakshi and Woodruff (NeurIPS 2018) showed it is
possible to compute a rank-$k$ approximation of a distance matrix in time
$O((n+m)^{1+\gamma}) \cdot \mathrm{poly}(k,1/\epsilon)$, where $\epsilon>0$ is
an error parameter and $\gamma>0$ is an arbitrarily small constant. Notably,
their bound is sublinear in the matrix size, which is unachievable for general
matrices.
We present an algorithm that is both simpler and more efficient. It reads
only $O((n+m) k/\epsilon)$ entries of the input matrix, and has a running time
of $O(n+m) \cdot \mathrm{poly}(k,1/\epsilon)$. We complement the sample
complexity of our algorithm with a matching lower bound on the number of
entries that must be read by any algorithm. We provide experimental results to
validate the approximation quality and running time of our algorithm.

本文研究了距离矩阵的低秩近似算法及其样本复杂度，在实验中得到了验证。