-
-
Notifications
You must be signed in to change notification settings - Fork 395
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Weighted directed label propagation gets stuck (or is very slow) #2561
Comments
@vtraag Would you be able to look at this if I produce a small testcase that is in a convenient format? |
I'm guessing that the labels must be running around in circles indefinitely. Something about the graph structure and choice of weights makes it so that the probability of reaching a stable state is very low, or perhaps it is plainly impossible to have a stable state. @vtraag Do you know if directed label propagation has been studied or whether this is an ad-hoc extension in igraph? Are there any results on whether the propagation procedure will stabilize in the directed case? I fear that fixing this may not be feasible ... Perhaps the best approach is to make the function interruptible and document it as a potential issue? I'll leave it to you to investigate and make a decision since you've recently worked with label propagation. |
I'll look at it later. Perhaps @lovre has some useful input? |
As far as I know this is a possibility when the labels are updated synchronously, but an easy way out is to update the labels asynchronously and to use a different, randomized update order in every cycle. But it seems like it doesn't work in this case; this is a potential cycle that I'm getting, but there are many others:
It looks like the algorithm is not able to reach a configuration where each vertex is set to the dominant color of its neighbors. I've let it run for a few seconds and then counted the occurrence of each configuration the output, yielding this (first number is the count), leaving out the initial transient:
I've realigned the columns to make it easier to see which vertices are changing. |
There are two concerns with the current label propagation implementation:
|
The problem is that we also call Ideally, we could get rid of all the RNG_BEGIN/END for release 1.0, and move them to the R interface (CC @krlmlr ) |
aaah. This is something that should be fixed in 1.0 (if we decide not to get rid of these calls -- it might prove to be more tricky than expected). IMHO if we decide to keep these, then only top-level igraph functions that are not expected to be called by other top-level igraph functions should ever call |
Perhaps best to wait to merge my fast label propagation PR (#2451) before diving in further? |
I propose adding interruptibility for 0.10, then merging @vtraag's PR, and continuing work on the 1.0 branch. If we find a good fix, it can always be backported to 0.10 if need be. |
This was found by the fuzzer. Label propagation running on directed weighted graphs can time out even on some small graphs. It gets stuck in some part of the code that is not even interruptible.
https://oss-fuzz.com/testcase-detail/5755444401340416
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=67840
We need to distill this down to a manageable size testcase.
The text was updated successfully, but these errors were encountered: