A Sub-Quadratic Exact Medoid Algorithm

James Newling, François Fleuret

TL;DR

This paper introduces "trimed," a novel algorithm that finds the exact medoid of a dataset in sub-quadratic time (specifically, O(N^(3/2)) expected time in R^d), a significant improvement over previous exact methods. This breakthrough enables faster and more efficient clustering, particularly for large datasets and network analysis.

What Problem Does This Paper Address?

The "medoid" of a dataset is the data point that minimizes the average distance to all other points in the set. This concept is crucial in various fields, including clustering (as the center of a cluster), operations research (facility location problems), and network analysis (identifying central nodes). While finding the medoid is straightforward for small datasets (O(N^2) complexity), existing exact algorithms struggle with larger datasets. Approximate algorithms exist, but they don't guarantee the true medoid. This paper tackles the challenge of developing an exact medoid algorithm that is computationally efficient for large-scale problems, especially in higher dimensions and for network data.

Methods

The core innovation is the "trimed" algorithm. It leverages the triangle inequality to efficiently prune potential medoid candidates. Instead of computing all pairwise distances, trimed maintains lower bounds on the energy (average distance) of each point. If a point's lower bound is already worse than the best medoid candidate found so far, it's immediately discarded. This "elimination" process, combined with a clever update strategy for the lower bounds, allows trimed to avoid computing many distances. Under certain assumptions about the data distribution (specifically, a bounded density around the medoid and strong convexity of the energy function), trimed achieves an expected runtime of O(N^(3/2)) in R^d, making it the first sub-quadratic exact medoid algorithm for d > 1. The paper also shows how trimed can accelerate the K-medoids algorithm (KMEDS) by replacing its quadratic medoid computation step.

Datasets

The paper evaluates its algorithms on a variety of datasets:

  • Synthetic Datasets:
    • 2D datasets (Birch1, Birch2)
    • Uniformly drawn points in R^d (d=2, 3, 4, 5, 6)
    • Points drawn from a ball with increased density beyond a certain radius.
  • Real-World Datasets:
    • Europe (border map)
    • U-Sensor Net, D-Sensor Net (undirected and directed graph data)
    • Europe rail (European rail network)
    • Gnutella (social network)
    • MNIST (0) (digit dataset, specifically '0's)
    • Conflong, Colormo (image feature datasets)
    • MNIST50 (MNIST projected to 50 dimensions)
    • Thyroid, Yeast, Wine, Breast, Spiral (various real-world datasets)

Key Insights and Ideas

  • Triangle Inequality as a Pruning Tool: The paper demonstrates that the triangle inequality isn't just a mathematical property but a powerful algorithmic tool for efficiently eliminating non-medoid candidates.
  • Lower Bounds for Efficiency: Maintaining and updating lower bounds on the energy of each data point is key to avoiding costly distance calculations.
  • Sub-Quadratic Exact Medoid: Achieving an exact medoid in sub-quadratic time (O(N^(3/2))) is a significant theoretical and practical advancement, especially for large datasets where O(N^2) is prohibitive.
  • Dimensionality Impact: While trimed excels in low dimensions, its performance degrades in very high dimensions, a behavior predicted by its theoretical analysis. This contrasts with approximate algorithms like TOPRANK, which can sometimes scale better with dimension.
  • K-Medoids Acceleration: Integrating trimed into K-medoids significantly speeds up the medoid update step, making K-medoids more competitive with K-means.

Key Results

  • trimed Algorithm: Achieves an expected runtime of O(N^(3/2)) in R^d for finding the exact medoid, under certain data distribution assumptions. This is the first sub-quadratic exact medoid algorithm for d > 1.
  • Performance Comparison: trimed consistently computes significantly fewer points than state-of-the-art approximate medoid algorithms (TOPRANK, TOPRANK2) on low-dimensional real and spatial network data, often by two orders of magnitude.
  • K-Medoids Improvement: When integrated into the K-medoids algorithm (as "trikmeds"), trimed dramatically reduces the number of distance calculations compared to the standard KMEDS algorithm, especially in low dimensions.
  • Relaxation for Further Gains: Relaxing the exactness criteria in trikmeds (e.g., "trikmeds-e") leads to even greater savings in distance computations with only a minor impact on cluster quality.
  • Dimensionality Effects: trimed's performance scales roughly as O(N^(1/2)) in low dimensions, but performance degrades in high dimensions. TOPRANK, conversely, can perform better in high dimensions.

Limitations and Future Work

  • Assumptions on Data Distribution: The O(N^(3/2)) theoretical guarantee for trimed relies on assumptions about the data distribution (bounded density around the medoid and strong convexity of the energy function). While experiments suggest it performs well even when these assumptions are slightly violated, its theoretical worst-case complexity might be higher in pathological cases.
  • High-Dimensional Performance: trimed's performance degrades in very high dimensions, a limitation acknowledged by the authors and consistent with their theoretical analysis.
  • Future Work:
    • Explore more complex triangle inequality bounds to potentially improve the O(N^(1/2)) bound on computed points.
  • Integrate strategies from Hamerly (2010) for accelerating K-means into trikmeds, which might be better suited for graph clustering.
  • Further investigate the relaxation of exactness criteria for K-medoids to balance computational cost and cluster quality.

Summary updated

Abstract

We present a new algorithm, trimed, for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under certain assumptions, expected run time O(N^(3/2)) in R^d where N is the set size, making it the first sub-quadratic exact medoid algorithm for d>1. Experiments show that it performs very well on spatial network data, frequently requiring two orders of magnitude fewer distance calculations than state-of-the-art approximate algorithms. As an application, we show how trimed can be used as a component in an accelerated K-medoids algorithm, and then how it can be relaxed to obtain further computational gains with only a minor loss in cluster quality.
BibTeX
@inproceedings{newling2017sub,
  author = {James Newling and François Fleuret},
  title = {{A Sub-Quadratic Exact Medoid Algorithm}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=BvF5vxZhtOlj},
}
Figure