# Removing edges of a weighted graph

I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $[0,1]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ non relevant. What I have tried so far is removing edge values that are below median or 60% - 70% quantile. Another approach I have tried is to generate random graphs and calculate random edge similarity as $randSim = \frac{\#edges\_drawn}{\#edges\_sampled}$ and remove edges with vales <= random similarity. The issue I am facing is that the first approach is too arbitrary and very few edges are removed using the second approach. Do you have suggestions for other edge pruning approaches ?

Thank you.

• You can't possibly do it by the $p$th quantile, since that presupposes the graph can't have more than $pN^2$ edges. – David Richerby Jul 13 '15 at 23:37
• Wether a cut-off is feasible depends heavily on the data at hand; a general answer is impossible. – Raphael Sep 3 '17 at 21:51

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)$.