Algorithm 2 (Generic Subgradient Method)
01 set t := 0 and choose starting point x t ∈ X
02 repeat 03 Direction finding:
04 determine d ∈ X and η > 0 such that f(x t + ηd) *< f(f*(x t)
05 Line search:
06 nd step size η∗ > 0 such that η∗ ≈ arg minη>0 f(x t + ηd)
07 Updating:
08 set x t+1 := x t + η∗d 09 set t := t + 1 10 until some termination criterion is satised convex set of points, called subgradients, at non-dierentiable points. The basic idea of subgradient methods is to generalize the methods for smooth problems by replacing the gradient by an arbitrary subgradient. Algorithm 1 outlines the basic procedure of a generic subgradient method.

At dierentiable points, direction nding generates a descent direction d by exploiting the fact that the direction opposite to the gradient of f is locally the steepest descent direction. At non-dierentiable points, direction nding amounts in generating an arbitrary subgradient. The problem is that a subgradient at a non-dierentiable point is not necessarily a direction of descent.

But according to Rademacher's Theorem, the set of non-dierentiable points is a set of Lebesgue measure zero. Line search determines a step size η∗ > 0 with which the current solution x tis moved along direction d in the updating step.

Subgradient methods use predetermined step sizes ηt,i, instead of some ecient univariate smooth optimization method or polynomial interpolation as in gradient descent methods. One reason for this is that a subgradient determined in the direction nding step is not necessarily a direction of descent. Thus, the viability of subgradient methods depend critically on the sequence of step sizes.

Updating moves the current solution x tto the next solution x t + η∗d. Since the subgradient method is not a descent method, it is common to keep track of the best point found so far, i.e., the one with smallest function value. For more details on subgradient methods and more advanced techniques to minimize locally Lipschitz functions, we refer to [19].

Several dierent subgradient methods for approximating a sample mean have been suggested [15]. For extending k-means to the domain of graphs, we have chosen the incremental arithmetic mean (IAM) method. In an empirical comparison of 8 dierent subgradient methods [15], IAM performed best with respect to computation time and was ranked third with respect to solution quality. In addition, IAM best trades computation time and solution quality. For this reason, we consider IAM as a good candidate for recomputing the centroids of the k-means clusters.