1
$\begingroup$

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ Thanks, could you please add a couple of references to read up a little bit more ? $\endgroup$ – deeps Jul 14 '15 at 7:57
  • $\begingroup$ @deeps, if you want to read about maximum likelihood methods, good textbooks on mathematical statistics should have some material on maximum likelihood. If you want references on applying this to graphs, the question is too broad/vague for me to give a specific reference -- you'd need to tell a lot more about the probabilistic process. $\endgroup$ – D.W. Jul 14 '15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.