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.