Could the sum-product algorithm be used instead of the max-product algorithm?
Yes, the sum-product can be used instead of the max-product algorithm, however, affinity propagation would no longer be invariant to constant multiples of the similarities so the multiplier would need to be tuned. In addition, it needs to be implemented in the log-domain as is the case with the max-product algorithm to mitigate numerical precision issues, but requires computationally-expensive log-sum operations (unlike log-domain max-product a.k.a. min-sum which only needs maxes and sums). Finally, the O(NxN) implementation of sum-product affinity propagation has numerical precision issues arising from subtracting relatively large numbers from each other meaning that an O(NxNxN) implementation may be required. We have performed limited experiments with sum-product affinity propagation and have not found the results to be better than the current max-product affinity propagation.
