Given an adjacency matrix $A={A^\top}\in {\mathbb{R}^{n \times n}}$ of a simple undirected graph and its degree matrix $D$ .

When adding $Q$ edges into the graph, which is equivalent to adding a $0$-$1$ perturbation matrix $E={E^\top}\in {\mathbb{R}^{n \times n}}$ (the number of 1's in $E$ is $Q$ and the position of 1's is not fixed) into the adjacency matrix $A$, we can get a perturbed adjacency matrix:


$\widetilde A = A + E $

and its perturbed degree matrix $\widetilde D$.


Let $M := \frac{1}{2}({D^{ - 1}}A + {({D^{ - 1}}A)^2})$ and its SVD is:

$M = U\Sigma {V^T}$ is known;

After being perturbed, we get :


$\widetilde M = \frac{1}{2}({\widetilde D^{ - 1}}\widetilde A + {({\widetilde D^{ - 1}}\widetilde A)^2})$ and its SVD:


$\widetilde M = \widetilde U\widetilde \Sigma {\widetilde V^\top}$

Since every column of $U$ is  ${u_i}$ and ${\widetilde u_i}$ is to $\widetilde U$, the question is how can I get the perturbation bound of ${\widetilde u_i}$.

Or are there any probabilistic methods that I can use to deal with this issue?