Your current approaches are very ad hoc, so they don't sound promising. Instead, I think you're going to need some domain knowledge. I suggest you start by characterizing the process by which the graph was generated. First, try to develop a probabilistic model that describes the distribution on such graphs (absent noise). Then, develop a probabilistic noise that describes the noise.
Suppose $X$ is a random variable that represents the original graph, and $Y$ is the random graph after adding noise to $X$. You observe the value of $Y$, say $y$. Now your goal is to estimate $X$. So, this becomes a probabilistic inference problem. One approach will be to use maximum likelihood methods: find the value $x$ that maximizes $p(x|y)$ (where $p(x|y) = \Pr[X=x|Y=y]$). To do this, you'll need to know the probability distribution $p(x)$ on $X$ and the probability distribution $p(y|x)$ on $Y$ (conditioned on $X$); then you can use Bayes rule and find the $x$ that maximizes the likelihood value $p(x|y)$ by noting that
$$\begin{align*}
p(x|y) &= p(y|x) p(x)/p(y)\\
&= {p(y|x) p(x) \over \sum_{x'} p(y|x') p(x')}.\end{align*}$$
Since $y$ is fixed, the denominator is a constant (it does not depend on $x$). Therefore, maximizing $p(x|y)$ is equivalent to maximizing $p(y|x) p(x)$. So, once you have a probabilistic model for $X$ and $Y$ and know the distributions $p(x)$ and $p(y|x)$, you can then try to infer the original noiseless graph by finding the value $x$ that maximizes $p(y|x) p(x)$.
