Now suppose that Y 6= YX is a candidate centroid for X. Then we apply the technique of "delayed (distance) evaluation". We rst test whether the upper bound u(X) is out-of-date, i.e. if u(X) 	 D (*X, Y*X). If u(X) is out-of-date we improve the upper bound by setting u(X) = D (*X, Y*X). Since improving u(X)
might eliminate Y as being a candidate centroid for X, we again check conditions
(C2) and (C3). If both conditions are still violated despite the updated upper bound u(X), we have the following situation

$$u(X)=D\left(X,Y_{X}\right)>\frac{1}{2}D\left(Y_{X},Y\right)u(X)=D\left(X,Y_{X}\right)$$
2
D (YX, Y ) u(X) = D (X, YX) > l(*X, Y* ).
Since the distances on the left and right hand side of the inequality of condition
(C2) are known, we may conclude that the situation for condition (C2) can not be altered. Therefore, we re-examine condition (C3) by calculating the distance D(*X, Y* ) and updating the lower bound l(X) = D(*X, Y* ). If condition (C3) is still violated, we have

$\Rightarrow$ ? 
u(X) = D (X, YX) > D(*X, Y* ) = l(*X, y*).

This implies that X is closer to centroid Y than to YX and therefore has to be assigned to centroid Y .

Crucial for avoiding distance calculations are good estimates of the lower and upper bounds l(*X, Y* ) and u(X) in each iteration. For this, we compute the change δ(Y ) of each centroid Y by the distance

 (3)  $\binom{4}{2}$
δ(Y ) = D(Y, Yˇ ),
where Yˇ is the recomputed centroid of cluster C(Y ). Based on the triangle inequality, we set the bounds according to the following rules

$$l(X,Y)=\max\left\{l(X,Y)-\delta(Y),0\right\}$$ $$u(X)=u(X)+\delta\left(Y_{X}\right).\tag{1}$$

In addition, u(X) is then declared as out-of-date.1 Both rules guarantee that l(*X, Y* ) is always a lower bound of D (*X, Y* ) and u(X) is always an upper bound of D (*X, Y*X).

Algorithm 4 presents a detailed description of Elkan's k-means algorithm for graphs. During each iteration, k(k − 1)/2 pairwise distances between all centers must be recomputed (Algorithm 4, line 07). Recomputing the centroids using incremental arithmetic mean (see Section 3.2) requires additional O(N) distance calculations (Algorithm 4, line 19-20). To update the lower and upper bounds, k distances between the current and the new centroids must be calculated (Algorithm 4, line 21-25). This gives a minimum of ON + k 2distance calculations at each iteration ignoring the delayed distance evaluations in line 09-18 of Algorithm 4. As the centroids converge, one would expect that the partition of the training sample becomes more and more stable, which results in a decreasing number of delayed distance evaluations.

1 In the original formulation of Elkan's algorithm for feature vectors, the upper bounds u(X) are declared as out-of-date regardless of the value δ(Y ).