Meaningful deviation measure with strongly varying datapoints

Question

I'm trying to compare several methods by their performance on a set of synthetic data samples. For each method, I obtain a performance value between 0 and 1 for each of those samples. Then I plot a graph with the average performance per method

The problem now is that the achievable quality per sample varies strongly between different samples (if you wonder why, I generate random graphs and evaluate community detection methods on them, and sometimes strange things happen, like elements from the same community get disconnected due to sparseness etc). So showing error bars based on standard deviation or standard error tend to get really large.

Imagine one method yields [1, 0.5, 1], and the other one (one the same three samples) [0.5, 0.25, 0.5]. Which measure can I apply to *de*emphasize the between-sample variance in the series and emphasize the fact that method 1 always outperforms method 2? Or, to put it differently, how can I test whether method 1 is significantly better than method 2 without being mislead by the different range of the indiviual datapoints? (Also note that I typically have more than two methods to compare, this is just for the example)

Thanks, Nic

Update One thing I've done is to count, for each method, how many times its performance is within 95% of the top performance. The picture pretty much speaks in favor of sample-based variance, not robust vs less robust methods. However, I'm still uncertain about how to generate a statistically valid statement from that..?

Update two years after Just found this answer again. Simply for anyone who stumbles across this: I went with a sign-test: How many times is method x better than method y. Then the null-hypothesis is that one should be better than the other 50% of the time if there's no difference - computing the probability that the actual number of wins/losses stems from a 0.5 coinflip can be computed via the binomial distribution, and serves as your $p$.

Answer 1

You need to use some paired test, maybe paired t-test or a sign test is the distribution is really weired.

Answer 2

I am not at all sure if ignoring the performance spread is a good idea. Ideally, you would want a method to be both reliable (i.e., have low spread) and be valid (i.e., give a performance measure of close to 1). Consider the following two output measures:

Method 1. [0.80, 0.60]

Method 2. [0.71, 0.69].

Unlike your example, there is no method that clearly dominates and in fact both methods perform equally well on average. Thus you may want to choose the one that is more reliable (i.e., has lower spread).

If you accept the above reasoning then your null hypothesis should be:

$$\frac{\mu_1}{\sigma_1} = \frac{\mu_2}{\sigma_2}$$

The above is analagous to the Sharpe ratio from finance and I am sure there is an extensive financial literature which discusses how to test hypothesis like the above and its extensions to more than 2 groups. Unfortunately, I am not well read up on that literature to help you.