Fast label propagation is extremely slow on some inputs (possible infinite loop)

[szhorvat]

OSS-Fuzz found a testcase on which fast label propagation does not seem to finish (didn't finish after 5 min).

• https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=68970
• https://oss-fuzz.com/testcase-detail/6390855211483136

The affected fuzz target is community, which currently uses an unweighted directed graph.

Profiling result after one minute:

Minimized testcase is attached: slow_good.zip

This is a multigraph with a triangle, a self-loop, and lots of isolated vertices (not shown below). Notice that only one side of the triangle is unidirectional, both others being bidirectional. So this might not be a trivial case of labels running around a circle.

Edge list with 0-based indexing:

49 50
49 55
50 49
50 49
50 50
55 49
55 50
55 50
55 50

The issue affects only IGRAPH_LPA_FAST, not IGRAPH_LPA_RETENTION or IGRAPH_LPA_DOMINANCE.

[szhorvat]

I changed IGRAPH_LPA_FAST to ignore edge directions in the fuzzer until we debug this. This is also useful to discover if the undirected version is affected by these issues.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

[szhorvat]

@vtraag, any suggestions on how to proceed with this?

[ntamas]

Edge list remapped to get rid of isolates (49 becomes 0, 50 becomes 1, 55 becomes 2):

0 1
0 2
1 0
1 0
1 1
2 0
2 1
2 1
2 1

In this graph, for as long as there are exactly two colors in the loop, the algorithm will get stuck in an infinite loop as the membership vectors will evolve like this:

• [2, 2, 1] will lead to [2, 1, 1] (node 1 has three edges from node 2, colored to 1, and only two edges from other nodes colored to 2).
• [2, 1, 1] will lead to [2, 1, 2] (node 2 has only one incoming edge, from node 0, so it will always follow the color of node 0 with a single-step delay)
• [2, 1, 2] will lead to [1, 1, 2] with a probability of 50% (node 0 has one edge from node 2 and one edge from node 1 so if they are not the same label, node 0 will flip colors with probability 50%)
• [1, 1, 2] will lead to [1, 2, 2] (same as the first item but with flipped colors).
• [1, 2, 2] will lead to [1, 2, 1] (same as the second item but with flipped colors).
• [1, 2, 1] will lead to [2, 2, 1] (same as the third item but with flipped colors).

[ntamas]

Added a test case; not included in the test suite yet until we find a fix for it.

[szhorvat]

@vtraag, any input on this? This is the new algorithm you contributed.

Notes:

• Not yet released.
• Interruptible.
• This problem affects directed, unweighted.
• Weighted directed label propagation gets stuck (or is very slow) #2561 is similar but affects the original LPA in the weighted case.

[vtraag]

The critical problem here seems to be that node 50 / 1 has a self-loop. This leads to it not being able to move to the "majority". Presumably it would be best to simply ignore self-loops in counting the labels. What do you think @lovre?

[szhorvat]

The critical problem here seems to be that node 50 / 1 has a self-loop. This leads to it not being able to move to the "majority". Presumably it would be best to simply ignore self-loops in counting the labels. What do you think @lovre?

Do you want me to run the fuzzer on loopless graphs a bit to see if it still finds a similar problem? I can do this on the week after next.