AFFINITY PROPAGATION
and the
VERTEX SUBSTITUTION HEURISTIC

Brendan J. Frey and Delbert Dueck, University of Toronto

Affinity propagation (AP) can be viewed as a generalization of the vertex substitution heuristic (VSH), whereby probabilistic exemplar substitutions are performed concurrently. Although results on small data sets (<900 points) demonstrate that VSH is competitive with AP, we found VSH to be prohibitively slow for moderate-to-large problems.  VSH took ~10 days to find 454 clusters in 17,770 Netflix movies, whereas AP took ~2 hours and achieved lower error. <more>

Download software ...

Affinity
Propagation
MATLAB function
(easy to use/modify, but no sparse capability)
DOWNLOAD apcluster.m
Compiled MEX-file for MATLAB
(faster, but more complicated)
Windows (32-bit):
7.5 (2007b)
7.4 (2007a)
7.2 (2006a)
7.0 (R14)
6.5 (R13)
Linux (32-bit):
7.0 (R14)
Linux (64-bit):
(R2007b)
(R2007a)
(R2006a)
Vertex
Substitution
Heuristic
(VSH)
MATLAB function
(slow; contains many nested loops)
DOWNLOAD vshcluster.m
Compiled MEX-file for MATLAB
(faster)
Windows (32-bit):
7.5 (2007b)
7.4 (2007a)
7.2 (2006a)
7.0 (R14)
6.5 (R13)
Linux (32-bit):
7.0 (R14)
Linux (64-bit):
(R2007b)
C source code for MEX file: vshmex_.c

WARNING: VSH will produce different results based on the machine-dependant random seed, so numbers in the table may change slightly.

Also, to compute the total similarity between exemplars and their cluster members, use the following code:
   dpsim = sum(max(S(setdiff(1:N,exs(:)'),exs(:)'),[],2),1)
To compute relative error as reported in the table, use the following code:
   relative_error_pct = (dpsimAP-dpsimVSH) / abs(max(dpsimAP,dpsimVSH)) * 100

Comparison and datasets ...

Problem n k preference Relative error CPU time
VSH:AP
 
AP (%) VSH (%)
Random S 400 34 -0.8 0 1.110 0.57:1 Download (1.1 MB)
Random S (100 runs) 400 34 -0.8 0 0.264 3.11:1
Extended circuit board 1272 103 -200000 0 0.176 5.19:1 Download (11 MB)
Face Video 1965 239 -30000 0 0.0021 10.84:1 Download (9.5 MB)
Putative exons 10,000 542 -2 0.0003 0 29.42:1 Download (8.0 MB)
Gene expression 10,000 566 +20 0 0 86.07:1 Download (340 MB)
Netflix movies 17,770 454 -1 0 0.019 123.09:1 Download (670 MB)

 

The MATLAB code for the replicated pattern experiment (see below) can be found here.




Last updated: 26-Jan-2008