Does affinity propagation work on sparse data?
If by “sparse”, you mean that you know beforehand that each data point has the potential to be assigned to only a small fraction of the other data points, then the answer is “yes”. Running affinity propagation on such data is equivalent to setting the similarity between two data points that shouldn’t be linked together to negative infinity. However, there is a version of affinity propagation that only exchanges messages between pairs of points when the similarity is not negative infinity. This algorithm’s time and memory requirements scale linearly with the number of similarities, which would be NxN if a full set of pairwise similarities is input, but much, much less if the set of similarities is sparse. For my problem, computing all possible NxN similarities would take too long or require too much memory because N (the number of data points) is too large. I’ve heard that I can still use affinity propagation. How? There are two options that we know of. First, if you know beforehand tha
