Removing edges of a weighted graph
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) &amp;= p(y|x) p(x)/p(y)\\
&amp;= {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)$.