标题： 一种用于谱聚类稳定性的低秩微分方程 显示英文标题

标题： A low rank ODE for spectral clustering stability

摘要： 谱聚类是一种已知的技术，通过利用其图拉普拉斯矩阵 $L(W)$，在具有权矩阵 $W\in\mathbb{R}^{n\times n}$的无向图中识别 $k$个簇，其特征值 $0=\lambda_1\leq \lambda_2 \leq \dots \leq \lambda_n$ 和特征向量与 $k$ 个簇有关。 由于计算$\lambda_{k+1}$和$\lambda_k$影响该方法的可靠性，因此常将第$k$个谱间隙$\lambda_{k+1}-\lambda_k$视为稳定性指标。 此差异可视为$L(W)$与一个具有消失的$k$个谱间隙的任意对称矩阵$L_\star$之间的非结构化距离。 一种更合适的结构化距离到歧义，使得$L_\star$表示图的拉普拉斯矩阵，由 Andreotti 等人提出（2021）。 略有不同的是，我们考虑目标泛函$ F(\Delta)=\lambda_{k+1}\left(L(W+\Delta)\right)-\lambda_k\left(L(W+\Delta)\right)$，其中$\Delta$是一个扰动，使得$W+\Delta$具有非负元素且与$W$具有相同的模式。 我们寻找一个可接受的扰动$\Delta_\star$，其弗罗贝尼乌斯范数最小，使得$F(\Delta_\star)=0$。 为了解决这个优化问题，我们利用其低秩的底层结构。 我们构建了一个秩-4对称矩阵ODE，其平稳点即为所求的优化器。 该方程的积分得益于低秩结构，计算量和内存需求适中，如一些示例数值实验所示。 显示英文摘要

摘要： Spectral clustering is a well-known technique which identifies $k$ clusters in an undirected graph with weight matrix $W\in\mathbb{R}^{n\times n}$ by exploiting its graph Laplacian $L(W)$, whose eigenvalues $0=\lambda_1\leq \lambda_2 \leq \dots \leq \lambda_n$ and eigenvectors are related to the $k$ clusters. Since the computation of $\lambda_{k+1}$ and $\lambda_k$ affects the reliability of this method, the $k$-th spectral gap $\lambda_{k+1}-\lambda_k$ is often considered as a stability indicator. This difference can be seen as an unstructured distance between $L(W)$ and an arbitrary symmetric matrix $L_\star$ with vanishing $k$-th spectral gap. A more appropriate structured distance to ambiguity such that $L_\star$ represents the Laplacian of a graph has been proposed by Andreotti et al. (2021). Slightly differently, we consider the objective functional $ F(\Delta)=\lambda_{k+1}\left(L(W+\Delta)\right)-\lambda_k\left(L(W+\Delta)\right)$, where $\Delta$ is a perturbation such that $W+\Delta$ has non-negative entries and the same pattern of $W$. We look for an admissible perturbation $\Delta_\star$ of smallest Frobenius norm such that $F(\Delta_\star)=0$. In order to solve this optimization problem, we exploit its low rank underlying structure. We formulate a rank-4 symmetric matrix ODE whose stationary points are the optimizers sought. The integration of this equation benefits from the low rank structure with a moderate computational effort and memory requirement, as it is shown in some illustrative numerical examples.