Speaker
Description
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)=\text{diag}(W\textbf{1})-W,\qquad \textbf{1}=(1,\dots,1)^T\in\mathbb{R}^n,
$$
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 in [1]. 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. Similarly to [2], 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.
[1] E. Andreotti, D. Edelmann, N. Guglielmi, C. Lubich, Measuring the stability of spectral clustering, Linear Algebra and its Applications, 2021
[2] N. Guglielmi, C. Lubich, S. Sicilia, Rank-1 matrix differential equations for structured eigenvalue optimization, arXiv preprint arXiv:2206.09338, 2022
