Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence

Fast Algorithm for Afﬁnity Propagation†

Yasuhiro Fujiwara† , Go Irie‡ , Tomoe Kitahara∗
NTT Cyber Space Laboratories, ‡ NTT Cyber Solutions Laboratories, ∗ Nihon University{fujiwara.yasuhiro, irie.go}@lab.ntt.co.jp, csto10004@g.nihon-u.ac.jp

Abstract

similarities that are not symmetric or do not satisfy the triangle inequality, and (3) it is deterministic, i.e., its clusteringresults do not depend on initialization, unlike most clustering
methods such as k-means. Therefore, it has been successfully
used in many applications in various disciplines such as initial training set selection in active learning [Hu et al., 2010],
keyphrase extraction [Liu et al., 2009], image clustering [Jiaet al., 2008] [Dueck and Frey, 2007], representative image
extraction [Zha et al., 2009], and supervised dimensionality
reduction [Chang and Zheng, 2009].
Although Afﬁnity Propagation has been receiving a lot of
attention for use in many applications, one of the most important research issues is its speed, especially for large scale
datasets [Jia et al., 2008]. This is because the original Afﬁnity Propagation algorithm requires quadratic CPU time in thenumber of data points to compute the messages. For resolving this issue, Jia et al. recently proposed FSAP, a fast algorithm for Afﬁnity Propagation [Jia et al., 2008]. However,their algorithm achieves its efﬁciency at the expense of clustering result accuracy; its clustering results are not the sameas those of the original Afﬁnity Propagation algorithm. Sacriﬁcing clustering accuracy makes it difﬁcult to realize truly
effective applications.
In this paper, we propose an efﬁcient clustering algorithm
for Afﬁnity Propagation that gives the same clustering result
as the original algorithm after convergence. In order to reduce computation cost without loss of clustering accuracy,
the proposal (1) prunes unnecessary message exchanges between data pairs in the iterations to compute the convergencevalues, and (2) computes the convergence values of pruned
messages from those of unpruned messages. Moreover, ouralgorithm does not require users to set any inner-parameters,
unlike FSAP. FSAP has a speciﬁc inner-parameter that must
be carefully set if the clustering results are not to be negatively impacted. We conduct evaluation experiments on several different datasets to compare our algorithm against existing algorithms. The results demonstrate the superiority of
our algorithm. It is much faster than the existing algorithms
while it guarantees exactness of the clustering results. This
conﬁrms the practicality of our algorithm for real world applications. With our method, many applications can be processed more efﬁciently.
The remainder of this paper is organized as follows. Section 2 gives a brief review of the original Afﬁnity Propagation

Afﬁnity Propagation is a state-of-the-art clustering method recently proposed by Frey and Dueck.
It has been successfully applied to broad areas ofcomputer science research because it has much better clustering performance than traditional clustering methods such as k-means. In order to obtainhigh quality sets of clusters, the original Afﬁnity
Propagation algorithm iteratively exchanges realvalued messages between all pairs of data points
until convergence. However, this algorithm does
not scale for large datasets because it requires
quadratic CPU time in the number of data points tocompute the messages. This paper proposes an efﬁcient Afﬁnity Propagation algorithm that guarantees the same clustering result as the original algorithm after convergence. The heart of our approachis (1) to prune unnecessary message exchanges in
the iterations and (2) to compute the convergencevalues of pruned messages after the iterations to determine clusters. Experimental evaluations on several different datasets demonstrate the effectivenessof our algorithm.

1 Introduction
Cluster analysis is an important component of scientiﬁc andindustrial data analysis, and many clustering methods havebeen proposed [Jain et al., 1999]. When a set of data points
is given, clustering assigns each data point into a group (cluster). By using clustering, we can extract representative examples from the dataset or discover the structures present in theraw data.
Recently, Frey and Dueck proposed a novel clustering
method, named Afﬁnity Propagation [Frey and Dueck, 2007].
Afﬁnity Propagation recursively transmits real-valued messages between all pairs of data points until message values
converge. And it determines a set of clusters and their representative data points called ’exemplars’, based on the converged message values. Afﬁnity Propagation has a numberof noteworthy advantages. For instance, (1) it achieves much
lower clustering error than existing clustering methods suchas k-means clustering [Jain et al., 1999], (2) it can support

2238


s[i, j] − maxk=j {a[i, k] + s[i, k]} (i = j)(2)s[i, j] − maxk=j {s[i, k]}(i = j)
min{0, r[j, j]+ k=i,j max{0, r[k, j]}}(i = j)
α[i, j] = (3)(i = j)k=i max{0, r[k, j]}

Table 1: Deﬁnition of main symbols.
SymbolNTs[i, j]r[i, j]a[i, j]ρ[i, j]α[i, j]λρ[i, j] =Deﬁnition
Number of data points
Number of iterations
Similarity between data point i and j
Responsibility between data point i and j
Availability between data point i and j
Propagating responsibility between data point i and j
Propagating availability between data point i and j
Damping factor, 0 ≤ λ < 1

That is, messages between data points are computed from thecorresponding propagating messages. The exemplar of data
point i is ﬁnally deﬁned as:arg max{r[i, j] + a[i, j] : j = 1, 2, . . . , N }As described above, the original algorithm requiresO(N 2 T ) time to update massages, where N and T are thenumber of data points and the number of iterations, respectively. This incurs excessive CPU time, especially when thenumber of data points is large. Therefore, a fast Afﬁnity Propagation algorithm is demanded as pointed out in [Jia et al.,2008].

algorithm and FSAP. Section 3 introduces the main ideas anddetails of our algorithm. Section 4 reviews the results of ourexperiments. Section 5 provides our conclusions.

2 Preliminary
In this section, we brieﬂy review the original Afﬁnity Propagation algorithm proposed by Frey and Dueck [Frey and
Dueck, 2007], as well as FSAP [Jia et al., 2008], a state-ofthe-art fast algorithm for Afﬁnity Propagation. Table 1 lists
the main symbols and their deﬁnitions.

2.1

2.2

Afﬁnity Propagation

Afﬁnity Propagation is a clustering algorithm that identiﬁes a set of ’exemplars’ that represents the dataset [Freyand Dueck, 2007]. The input of Afﬁnity Propagation is
the pair-wise similarities between each pair of data points,
s[i, j](i, j = 1, 2, . . . , N ) 1 . Any type of similarities is acceptable, e.g. negative Euclidean distance for real valued
data and Jaccard coefﬁcient for non-metric data, thus Afﬁnity
Propagation is widely applicable.
Given similarity matrix s[i, j], Afﬁnity Propagation attempts to ﬁnd the exemplars that maximize the net similarity, i.e. the overall sum of similarities between all exemplars
and their member data points. The process of Afﬁnity Propagation can be viewed as a message passing process with two
kinds of messages exchanged among data points: responsibility and availability. Responsibility, r[i, j], is a message
from data point i to j that reﬂects the accumulated evidence
for how well-suited data point j is to serve as the exemplar
for data point i. Availability, a[i, j], is a message from data
point j to i that reﬂects the accumulated evidence for how appropriate it would be for data point i to choose data point j as
its exemplar. All responsibilities and availabilities are set to
0 initially, and their values are iteratively updated as follows
to compute convergence values:
r[i, j] = (1 − λ)ρ[i, j] + λr[i, j]a[i, j] = (1 − λ)α[i, j] + λa[i, j](1)where λ is a damping factor introduced to avoid numerical oscillations, and ρ[i, j] and α[i, j] are, we call, propagating responsibility and propagating availability, respectively. ρ[i, j]and α[i, j] are computed by the following equations:1(4)s[i, i] for each data point is called preference and impacts the number of clusters.

2239

FSAP

For resolving the computation time issue of the original Afﬁnity Propagation algorithm, Jia et al. recently proposed FSAP
[Jia et al., 2008]. One promising idea for improving the
speed of Afﬁnity Propagation is to reduce the number of message values that need to be computed. FSAP aims to reﬂect
this idea as follows. The ﬁrst stage of FSAP constructs a
K-nearest neighbor graph. If data point i is among the Kdata points that have the largest similarity with data point j,then data point i and j are connected by an edge, otherwisenot. Since FSAP performs message transmissions on the Knearest neighbor graph, too many exemplars (at least N/K)
might be generated. Therefore, in order to merge multiple exemplars into one cluster, the second stage adds further edges
based on the following three criteria:
1. If data point i is the exemplar of data point j, then data
point i and j are connected by an edge;
2. For two data points i and j, if there exists two data points
m and n that take data point i and j as their exemplar, respectively, and data point m and n are K-nearest neighbor to each other, and so data point i and j are connectedby an edge; and3. For two data points i and j, if they are connected by
criterion 2, then all data points that choose data point i
as exemplar are connected to data point j, and vise versa.
After convergence, the exemplar of data point i is ﬁnally determined by Equation (4).
They showed that their approach is much faster than theoriginal algorithm described in Section 2.1. However, FSAP
is based on heuristic ideas, i.e., the linked edges are determined based on K-nearest neighbor approximation andheuristic criteria. Therefore, FSAP does not guarantee thesame result as the original Afﬁnity Propagation algorithm.
As we will show in Section 4, this fact seriously degrades
the clustering accuracy. Our algorithm presented in this paper is faster than FSAP while it still theoretically guarantees
the exactness of the clustering results after convergence.

3 Proposed method
In this section, we present our fast Afﬁnity Propagation algorithm which gives the same clustering result as the originalalgorithm after convergence. First, we give an overview of
the ideas underlying the proposed algorithm and then a fulldescription. We also give some theoretical analyses of its performance.

3.1

Ideas

In order to improve running speed, we construct a sparsegraph structure G = [V, E] where node set V and edge set
E correspond to data points and a part of the messages between any two of the data points, respectively. This allows us
to compute the message values efﬁciently. This is because thepropagating responsibility and propagating availability thatneed to be computed are limited to those on existing edges.
However, one may easily raise the following questions: how
can we identify a set of necessary edges that yields the sameclustering result as the original algorithm?
We can identify the edges whose convergence values do
not need to be computed by estimating their upper and lower
bounds. Based on this idea, we can construct a sparse graphthat has no unnecessary edges. Moreover, as we describe
later, the convergence values of pruned (unnecessary) messages can be computed from that of unpruned (necessary)
messages. Therefore, after the iterations, we can computethe convergence values of pruned messages. This is our answer to the question. As a result, we can efﬁciently obtain thesame clustering result as the original algorithm.
These new ideas provide a further advantage. Our upper/lower bound estimation does not need any user-deﬁned
inner-parameters, whereas FSAP has one parameter, K, fordetermining the K-nearest neighbor graph. The value of K
impacts the clustering result. That is, our algorithm is user
friendly.

3.2

By utilizing the above lemma, upper/lower values of convergence messages can be obtained from just pair-wise similarities. Formally, the following equations give upper/lower
values of convergence message values:
Deﬁnition 1 (Upper/lower bound) The following deﬁnitions give upper/lower bounding estimations a[i, j], r[i, j],and a[i, j] for convergence messages:
min{0, r[j, j]} (i = j)(5)a[i, j] =0(i = j)s[i, j] − maxk=j {a[i, k] + s[i, k]} (i = j)(6)
r[i, j] =s[i, j] − maxk=j {s[i, k]}(i = j)
min{0, r[j, j]+ k=i,j max{0, r[k, j]}}(i = j)(7)a[i, j] = (i = j)k=i max{0, r[k, j]}Note that a[i, j] can be computed just from pair-wise similarities s[i, j](i, j = 1, 2, . . . , N ) since r[j, j] = s[j, j] −maxk=j {s[j, k]} (Equation (2)). In addition, r[i, j] and a[i, j]
can be computed from a[i, j] and r[i, j], respectively. Therefore, we do not need any iterations to compute these upper/lower bounding values.
We show the following lemmas to introduce the upper/lower properties of a[i, j], r[i, j], and a[i, j].
Lemma 2 (Upper/lower bound) For any node pairs i and j
in graph G, a[i, j] ≤ a[i, j], r[i, j] ≥ r[i, j], and a[i, j] ≥a[i, j] hold after convergence.
Proof.
We ﬁrst prove that a[i, j] ≤ a[i, j]. From
Lemma 1, a[i, j] = α[i, j] holds after convergence. If
i = j, then a[i, j] ≥ min{0, r[j, j]} = a[i, j] holds sincer[k, j]} ≥ 0. If i = j, then a[i, j] ≤ a[i, j]k=i,j max{0,
holds since k=i max{0, r[k, i]} ≥ 0. We next prove thatr[i, j] ≥ r[i, j]. This is obvious from Lemma 1, Equation (2),and a[i, j] ≤ a[i, j]. We ﬁnally prove that a[i, j] ≥ a[i, j].
This is similarly obvious given Lemma 1, Equation (3), andr[i, j] ≥ r[i, j].
2
We construct the sparse graph structure by pruning unnecessary messages by using upper/lower bound estimations.
Formally, we obtain the edge between node i and j as follows:

Approach

We ﬁrst describe how to construct the sparse graph structure,and give some theoretical highlights of the sparse graph structure. And then, we detail our clustering algorithm.
Sparse graph structure
We reduce the number of messages between data points in
the iterations in order to compute the convergence values at
low cost. To realize efﬁcient computation, we construct graph
G = [V, E] where node set V consists of data points. We
prune unnecessary messages by estimating upper/lower values of convergence values. We show the following lemma of
convergence message values:

Deﬁnition 2 (Sparse graph) The sparse graph G, where
node set V consists of data points, has an edge between nodei and j if and only if:(1)r[i, j] ≥ 0, or(2)a[i, j] + s[i, j] ≥ max{a[i, k] + s[i, k]}
k=j

(8)

We introduce the following two lemmas to describe theproperty of our graph structure:

Lemma 1 (Convergence message) After convergence, message values of responsibility and availability are r[i, j] =
ρ[i, j] and a[i, j] = α[i, j], respectively.

Lemma 3 (Convergence availability values) For any nodepair i and j, convergence values of availabilities can be exactly computed just from the convergence responsibilities thatsatisfy r[i, j] ≥ 0.

Proof. It is easily found from Equation 1.
2
This lemma implies that if the Afﬁnity Propagation algorithm
converges, its convergence values can be computed from thedeﬁnition of propagating messages (Equation (2) and (3)).

Proof. From Lemma 1, a[i, j] = α[i, j] holds after convergence. If r[i, j] < 0 holds for a pair, the responsibility of thepair does not affect the values of k=i,j max{0, r[k, j]} andk=i max{0, r[k, j]} in Equation (3) after convergence. 22240

Algorithm 1 Proposed algorithm

after the iterations (Lemma 1). We ﬁnally compute exemplars
for all data points (lines 17-19).
Note that, our algorithm itself does not require any userdeﬁned inner-parameters. Thus it provides to the user with asimple solution to Afﬁnity Propagation with enhanced clustering speed.

Input: pair-wise similarities
Output: exemplars of each data point
1: for each data point pair [i, j] do
2:compute a[i, j], r[i, j], and a[i, j] by Equation (5-7);
3: end for
4: for each data point pair [i, j] do
5:
if r[i, j] ≥ 0 or a[i, j]+s[i, j] ≥ maxk=j {a[i, k]+s[i, k]}then6:link data point pair [i, j];7:
end if
8: end for
9: for t = 1 to T do
10:
for each linked data point pair [i, j] do
11:
update r[i, j] and a[i, j] by Equation (1);12:
end for
13: end for
14: for each unlinked data point pair [i, j] do
15:compute r[i, j] = ρ[i, j] and a[i, j] = α[i, j];
16: end for
17: for each data point i do
18:
compute exemplar by Equation (4);19: end for

3.3

Theoretical analyses

We provide theoretical analyses with regard to the clusteringresults and computation cost of our algorithm. Let M be thenumber of edges in the graph. That is M = |E|.
Theorem 1 (Clustering results) After convergence, theclustering results of our algorithm are same as those of theoriginal Afﬁnity Propagation.
Proof. It is obvious from Lemma 5.

2

Theorem 2 (Computation cost) Our algorithm requiresO(N 2 + M T ) time to obtain exemplars for all data points.
Proof. In the clustering process of our algorithm, we ﬁrst
compute the upper/lower values of convergence messages ofall data point pairs, and construct the graph structure. These
procedures require O(N 2 ) time since the upper/lower values
can be computed just from pair-wise similarities. Then, we
iteratively compute the convergence message values for alledges in the graph, which needs O(M T ) time. We ﬁnallycompute convergence message values of unlinked edges andexemplars for all data points which require O(N 2 − M ) andO(N 2 ) time, respectively. Therefore, the computation cost of
our algorithm is O(N 2 + M T ).
2

Lemma 4 (Convergence responsibility values) For
anynode pair i and j, convergence values of responsibilities canbe exactly computed just from the convergence availabilities
that satisfy a[i, j] + s[i, j] ≥ maxk=j {a[i, k] + s[i, k]}.
Proof. From Lemma 1, r[i, j] = ρ[i, j] holds after convergence. If i = j, r[i, j] = s[i, j] − maxk=j {a[i, k] +s[i, k]} holds from Equation (2) after convergence. Sincemaxk=j {a[i, k] + s[i, k]} ≥ maxk=j {a[i, k] + s[i, k]} holds,
if maxk=j {a[i, k] + s[i, k]} > a[i, j] + s[i, j] holds for nodepair i and j, then maxk=j {a[i, k] + s[i, k]} > a[i, j] + s[i, j]holds for the node pair. Therefore, the availability values ofthe pair does not affect the values of responsibilities. If i = j,
responsibilities can be computed just from pair-wise similarities (see Equation (2)).
2
From Lemma 3 and 4, we introduce the following lemma:

4 Experimental evaluation
We conducted evaluation experiments to conﬁrm the effectiveness of our algorithm. In these evaluations, we compare
our algorithm to the original Afﬁnity Propagation algorithm[Frey and Dueck, 2007] and FSAP [Jia et al., 2008].
Our experiments will demonstrate that:• Efﬁciency: Our algorithm outperforms the original algorithm and FSAP in terms of computation time (Section 4.1).
• Exactness: Unlike FSAP, our algorithm yields the sameclustering result as the original algorithm (Section 4.2).
• Applicability: Case-studies on real world datasets showsthat our algorithm and FSAP output different clusteringresults, and that the results of our algorithm are reasonable (Section 4.3). That is, our algorithm can be a better
alternative for the original algorithm.
In this section, Proposed and Original represent the results of our algorithm and the original algorithm, respectively. FSAP is tested under several different values of K.
FSAP(5%), FSAP(10%), and FSAP(20%) refer to the resultsof FSAP gained with K values of 0.05N , 0.1N , and 0.2N ,respectively. We iteratively computed responsibilities andavailabilities a thousand times to obtain convergence values.
We set the damping parameter, λ, to 0.5.
In the experiments, we used the following three datasets ofdifferent application domains that have different characteristics each other:Lemma 5 (Convergence in the sparse graph structure)
For any node pair i and j, convergence values of messages
can be exactly obtained by computing convergence values ofedge messages in sparse graph G.
Proof. This is obvious given Lemma 1, 3, and 4.
2
Lemma 5 provides our algorithm with the property of clustering results which is the same as the original Afﬁnity Propagation algorithm.
Clustering algorithm
Algorithm 1 is the full description of our algorithm. We
ﬁrst compute the upper/lower values of convergence messages by Deﬁnition 1 (lines 1-3), and then construct the graphstructure by Deﬁnition 2 (lines 4-8). Since we can computethe convergence message values of all data point pairs fromthose of graph edges (Lemma 5), we iteratively update themessage values of graph edges to compute convergence values (lines 9-13). Then we compute convergence message values of unlinked data point pairs after the iterations (lines 1416). These values can be computed by propagating messages

2241

10

4

3

4

103

10

2

Proposed
FSAP(5%)
FSAP(10%)
FSAP(20%)
Original

1

102

10
2000
Geo

Dictionary

Traffic

4000

1

1

0.8

0.8
Recall10

Proposed
FSAP(5%)
FSAP(10%)
FSAP(20%)
Original

Precision

105Wall clock time [s]Wall clock time [s]

10

0.6
0.4

0.4
Proposed
FSAP(5%)
FSAP(10%)
FSAP(20%)

0.2

6000
8000
Number of data points

0
2000

10000

0.6

4000
6000
8000
Number of data points

Proposed
FSAP(5%)
FSAP(10%)
FSAP(20%)

0.2

10000

0
2000

4000
6000
8000
Number of data points(1) Precision

Figure 1: Clustering time.

(2) Recall

Figure 3: Accuracy of our algorithm and FSAP.

Figure 2: Scalability.

• Geo: This dataset was collected by downloading geotagged photographs from Flickr 2 using the site’s public
API 3 . The crawled data consists of 10, 000 photographs
and their associated geotag data. All photos were takenin the central area of New York City, the United States
between January 1st, 2006 and June 31st, 2009. Geolocation of each photo is represented as its longitude andlatitude (x, y). Similarity between photo i and j is thenegative Euclidean distance.
• Dictionary 4 : This dataset was taken from word network in FOLDOC 5 . FOLDOC is a famous on-line,
searchable, encyclopedic dictionary of computing subjects. Similarity between term i and j is computed byrandom walk with restart [Tong et al., 2008] where relevance from term i to j is the frequency with which termj is used to describe the meaning of term i. The numberof terms is 13, 356.
• Trafﬁc 6 : This dataset contains loop sensor measurements of the Freeway Performance Measurement System. This loop sensor dataset was collected in Los Angeles from April 10th, 2005 to October 1st, 2005 (5 minutecount aggregates). We extracted 10, 000 sequences fromthe sensor measurements. Similarity between sequence
i and j is taken as the negative Euclidean distance.
All experiments were conducted on a Linux quad 3.33 GHzIntel Xeon server with 32GB of main memory. We implemented all algorithms using GCC.

4.1

10000

Efﬁciency

We evaluated the clustering performance of each algorithm
through wall clock time. Figure 1 shows the results. We also
show the scalability of each algorithm in Figure 2; this ﬁgureshows the wall clock time as a function of the number of data
points. We show only the result of Geo in Figure 2 due tospace limitations.
These ﬁgures show that our algorithm is signiﬁcantly fasterthan the original algorithm under all conditions examined.
Speciﬁcally, our algorithm is more than 30 times faster thanthe original algorithm. As described in Section 2, the original algorithm requires O(N 2 T ) while our algorithm requires
O(M T ) time (see Theorem 2) in the iterations. And, as
2

http://www.ﬂickr.com/
http://maps.google.com/
4
http://vlado.fmf.uni-lj.si/pub/networks/data/dic/foldoc/foldoc.zip
5
http://foldoc.org/
6
http://archive.ics.uci.edu/ml/datasets/Dodgers+Loop+Sensor
3

Table 2: Number of edges in each algorithm.
Algorithm
Proposed
Original

Geo
10,009,002
100,000,000

Data set
Dictionary
2,799,319
178,382,736

Trafﬁc10,034,228
100,000,000

shown in Table 2, there are very few edges in our sparsegraph (i.e., M  N 2 ) 7 . This is because a signiﬁcant number of messages are pruned by our upper and lower bounding
strategies. Therefore, our algorithm is an extremely efﬁcientvariant of the original algorithm.
And our algorithm is much faster than FSAP whose efﬁciency depends on the value of inner-parameter K as shownin the results. FSAP is a two-stage approach and it needs
iterations in each stage (see Section 2.2). Therefore, our algorithm is faster than FSAP.

4.2

Exactness

One major advantage of our algorithm is that it guarantees
the same clustering result as that of the original algorithm
after convergence. However, this raises the following simple question: how successful is FSAP in providing the sameclustering results?
To answer this question, we compared the exemplars extracted by our algorithm and FSAP to those extracted by theoriginal algorithm. As the measures of accuracy, we used precision and recall. Precision is the fraction of exemplars by ouralgorithm that are match those of the original algorithm. And
recall is the fraction of exemplars extracted by the originalalgorithm that were successfully extracted by our algorithm.
We used Geo as the dataset in these experiments.
Figure 3-(1) and 3-(2) show the precision and recall, respectively. As we can see from Figure 3-(1) and 3-(2), theprecision and recall of our algorithm are always 1. Because
our algorithm is theoretically designed to compute convergence message values exactly, our algorithm does not sacriﬁce clustering accuracy. FSAP, on the other hand, has lower
precision and recall. This is because FSAP determines edges
based on heuristic ideas (see Section 2.2). The results shownin Figure 1, 2, and 3 conﬁrm that our algorithm is superior tothe original algorithm in terms of speed, and to FSAP in bothof accuracy and speed.
7

Our additional experiments conﬁrmed that a data pair which has higher similarity
value has a higher chance to have an edge.

2242

5th: American Museumof Natural History

3th: Rockefeller
Center

4th: Times Square

1th: Empire State

2th: Grand Central
Terminal

Building

1th: Times Square

3th: Empire State

5th: Rockefeller
Center

4th: Times Square

4th: Times Square

2th: Empire State
Building

5th: Empire State
Building

1th: Grand Central
Terminal

3th: Empire State
Building

Building

5th: Times Square
4th: Times Square

2th: Empire State
Building

1th: Grand Central
Terminal

3th: Empire State
Building

2th: Washington
Square Park

(1) Proposed(2) FSAP(5%)(3) FSAP(10%)(4) FSAP(20%)

Figure 4: Top ﬁve popular landmarks to take photos in New York City detected by each algorithm.

4.3

Application example

To demonstrate the impact of our algorithm on real world applications, we give some examples of its clustering performance on Geo. The clustering of a geo-tagged photo dataset
is regarded as the detection of popular landmarks that are frequently taken into photos, and this is recognized as a key
process in many geo-location oriented applications such as
geo-referenced image browsing [Crandall et al., 2009] andlandmark image search [Kennedy and Naaman, 2008].
Figure 4 shows exemplars of the top 5 (largest) clusters
extracted by our algorithm and FSAP. To ﬁnd a place namefor a given exemplar (longitude/latitude), we used a public
reverse geocoding tool based on georeferenced Wikipedia articles8 . All algorithms detected famous landmarks such as
the Empire State Building, Times Square, and Grand Central
Terminal. However, FSAP detected the same landmark morethan once. For instance, FSAP(5%) redundantly detected theEmpire State Building (3rd and 5th) and Times Square (1stand 4th). On the other hand, all popular landmarks extracted
by our algorithm were different from each other. The resultof our algorithm is reasonable, and is consistent with our intuition. Note that the result of our algorithm equals that of theoriginal algorithm. These results imply that our algorithm canbe another option for the research community for clusteringlarge datasets.

5 Conclusions
This paper proposed an efﬁcient clustering algorithm for
Afﬁnity Propagation that gives the same clustering result as
the original algorithm after convergence. Our algorithm isbased on two ideas: (1) it prunes unnecessary message exchanges in the iterations, and (2) it computes the convergencevalues of pruned messages from those of unpruned messages.
Experiments show that our algorithm can achieve efﬁcient
clustering without sacriﬁcing clustering accuracy. Afﬁnity
Propagation is fundamental for many applications in various
disciplines. The proposed solution allows many applications
to be processed more efﬁciently, and helps to improve the effectiveness of future applications.

References[Chang and Zheng, 2009] Xueping Chang and Zhonglong
Zheng. Laplacian discriminant projection based on afﬁn8

http://www.geonames.org/export/wikipedia-webservice.html

2243

ity propagation. In Int. Conf. Artiﬁcial Intelligence andComputational Intelligence (AICI), pages 313–321, 2009.
[Crandall et al., 2009] David J. Crandall, Lars Backstrom,
Daniel Huttenlocher, and Jon Kleinberg. Mapping theworld’s photos. In Int. World Wide Web Conf. (WWW),
pages 761–770, 2009.
[Dueck and Frey, 2007] Delbert Dueck and Brendan J. Frey.
Non-metric afﬁnity propagation for unsupervised image
categorization. In IEEE Int. Conf. Computer Vision(ICCV), pages 1–8, 2007.
[Frey and Dueck, 2007] Brendan J. Frey and Delbert Dueck.
Clustering by passing messages between data points. Science, 315:2007, 2007.
[Hu et al., 2010] Rong Hu, Brian Mac Namee, andSarah Jane Delany. Off to a good start: Using clustering to select the initial training set in active learning.
In Florida Artiﬁcial Intelligence Research Society Conf.
(FLAIRS), 2010.
[Jain et al., 1999] Anil K. Jain, M. Narasimha Murty, andPatrick J. Flynn. Data clustering: A review. ACM Comput.
Surv., 31(3):264–323, 1999.
[Jia et al., 2008] Yangqing Jia, Jingdong Wang, Changshui
Zhang, and Xian-Sheng Hua. Finding image exemplars
using fast sparse afﬁnity propagation. In ACM Int. Conf.
Multimedia (ACM MM), pages 639–642, 2008.
[Kennedy and Naaman, 2008] Lyndon S. Kennedy and Mor
Naaman. Generating diverse and representative image
search results for landmarks. In Int. World Wide Web Conf.
(WWW), pages 297–306, 2008.
[Liu et al., 2009] Zhiyuan Liu, Peng Li, Yabin Zheng, andMaosong Sun. Clustering to ﬁnd exemplar terms for
keyphrase extraction. In Conf. Empirical Methods in Natural Language Processing (EMNLP), pages 257–266, 2009.
[Tong et al., 2008] Hanghang Tong, Christos Faloutsos, andJia-Yu Pan. Random walk with restart: fast solutions andapplications. Knowl. Inf. Syst., 14(3):327–346, 2008.
[Zha et al., 2009] Zheng-Jun Zha, Linjun Yang, Tao Mei,
Meng Wang, and Zengfu Wang. Visual query suggestion.
In ACM Int. Conf. Multimedia (ACM MM), pages 15–24,
2009.