Disambiguation means clustering items by the entities they reference.
Examples include figuring out who wrote what, whom a pronoun refers to,
and what RNA molecule a short read came from.

We focus on author disambiguation. There are $n$ items (mentions of
author names) and $O(n)$ clusters (actual authors) to recover. Each
mention has a small number of observed attributes, but $O(n)$ attributes
are observed in total. The induced similarity matrix is dense. In this setting,
standard clustering algorithms either cannot effectively consider
essential attributes, or are intractable due to at least quadratic runtime.

We propose and evaluate a supervised, $O(n \log n)$ disambiguation procedure
based on recursive spectral bipartitioning and an efficient representation of
the similarity matrix.