# Nonparametric test to compare link prediction algorithms

I have some experimental data, and I want to use a non-parametric test to verify my results. I am considering link-prediction on complex networks.

I have a complex network $N$ and an algorithm/model $A$ which finds structure in $N$. I then remove some of the edges in $N$, first $10\%$, then $30\%$ up to $90\%$. For each of these states of $N$, I use $A$ to infer the structure, and then compute and AUC-score. I repeat this procedure 3 times, so I get a total of 15 scores.

Now I take a new algorithm $A'$, which is a modification of $A$, and perform the same tests for $A'$. I now have 30 scores, 15 for $A$, and 15 for $A'$.

     10%   30%   50%   70%   90%
A1    x     x     x     x     x
A2    x     x     x     x     x
A3    x     x     x     x     x
A'1   x     x     x     x     x
A'2   x     x     x     x     x
A'3   x     x     x     x     x


Now I want to use a non-parametric test (probably a rank-sum test), to verify that $A$ is better at inferring structure in the networks. How do I go about doing this?

I am using MATLAB for my experiments, so a call to ranksum($x,y$) is the solution to "how to do the test". What I am looking for here, is the arguments $x,y$, and if there are any things I need to consider about independence?

There seem to be two obvious possibilities for the input: $$x = [A_1 (10\%), A_2 (10\%), A_3 (10\%), A_1 (30\%), \ldots , A_3 (90\%)]$$ $$y = [A'_1 (10\%), A'_2 (10\%), A'_3 (10\%), A'_1 (30\%), \ldots , A'_3 (90\%)]$$ or $$x = [A_1 (10\%), A_1 (30\%), \ldots, A_1 (90\%), A_2 (10\%), \ldots, A_3 (90\%)]$$ $$y = [A'_1 (10\%), A'_1 (30\%), \ldots, A'_1 (90\%), A'_2 (10\%), \ldots, A'_3 (90\%)]$$

Are any of these correct, and if only one of them, why?

It sounds like you're trying to do a calibration study to show the non-superiority of the new test. As you know, inverted hypothesis tests are complex. Since updating A to give you A' takes time and energy, wouldn't you be okay with a rule which says something like, "If A' doesn't provide better discrimination, then maintain A", i.e. a superiority test in which you could look at the AUC and even confidence intervals for it.

It also sounds like you have multiple metrics of model performance though the problem description is not clear. As I understand it, you're predicting various levels of complexity in the network, e.g. 10% means you're looking to correctly predict perhaps 10% of the edges of a network graph... or is it 10% sensitivity?

If you have several different outcomes, you should think carefully about how you would like to weight each outcome based on its importance for desired application. Perhaps you're more interested in the 30% network... or 90% network. Or you could just take a flat average of all the predictive performances (as measured by the AUC).

• As stated in the question, the $10\%$ refers to removing 10 percent of the edges from the network. Making $A$ into $A'$ does not take time and energy, actually $A'$ is just a simplification of $A$. – utdiscant May 18 '12 at 20:22
• Yes, but what you haven't stated is how/why this is performed. Are they removed at random? Or do they represent specific nodes that are lower priority? Or are they part of an isolated network, like a hidden layer in a neural net? How do you interpret the differences in predictive accuracy for each of these models? Is A' then a model which can be considered to be nested in A? – AdamO May 18 '12 at 20:32
• To answer your questions: They are removed at random. $A'$ can be viewed as a model nested in $A$. I see your point about the weight of each outcome. I am interested in "proving" that $A$ in general, does not outperform $A'$, and there does not seem to be a most important percentage to consider. – utdiscant May 18 '12 at 20:52

When looking back, I think what I did not know, was the actual meaning of paired-tests. The ranksum-test in MATLAB is non-paired whereas the ranksign-test is a paired non-parametric test. In the paired test, both of the two possible ways of permuting the data are correct.