A Missing Details and Proofs We denote the degree of vertex v

We stress that unweighted and weighted in the linkage measure names refer to the linkage methods. Recall that our approach is based on geometric layering, where we group the edges based on their weights and process all edges within the same layer in parallel. A similar idea is used in the Affinity Clustering algorithm of Bateni et al. [ Our algorithm starts by first randomly coloring the active vertices red and blue with equal probability. Directly applying the random-mate approach (e.g., as applied in Let D be initialized to the identity clustering. O (log n) layers are required to represent every weight in this weight range.Lemma 2.1.