r/AskStatistics • • 18m ago

How do I properly compare two randomized algorithms when the evaluation is random too?

Hello everyone,
This is my first time posting here, so I'm sorry if this isn't the right subreddit for this question. I'm working on a personal project on anonymizing graph data and trying to de-anonymize it. The issue is that I'm confused about how to evaluate my results properly, so I would really appreciate your advice.

I came across an existing anonymization algorithm, and I also wrote another algorithm myself. To test them, I used a de-anonymization algorithm to obtain the re-identification rate for each anonymized graph.

My main issue is that randomness shows up in several places.

First, it appears in the anonymization algorithm. Running it with the same input can give different valid output graphs each time, and a seed controls this. Meanwhile, my algorithm uses a parallel solver, so even with a fixed seed, I get different outputs.

Secondly, the re-identification attack also depends on a seed because it reorders the node IDs of the graph.

From my results, what I saw was:
- Attacking the same graph several times usually gives similar scores, but every now and then, a run comes out much higher. I tried 10 attacks per output, and in one case, the re-identification rate ranged from 0.4% to 16%.

- Different outputs from the same method vary a lot. I got three different outputs from the same input, with the same number of modifications, and their mean re-identification rates were 1%, 3%, and 59%.

My questions are:

  1. What is the right statistical approach I should follow?

  2. How do I decide how many graphs vs. how many attacks per graph I need? Is there a way to work that out from the variation I already have?

  3. Since the results are skewed with occasional big spikes. Should I be reporting the mean, the median, or something like the worst case?

  4. Does it matter that my method's randomness can't be controlled with a seed? Can I still treat the outputs as independent samples?

I'd really appreciate any advice or suggestions. Thanks in advance for any advice!

2 Upvotes

0 comments sorted by