  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.
