2.1. Implications for spectral clustering

The first step in spectral clustering of a set of points $\{x_1,\ldots,x_n\}\subset \mathbb{R}^d$ into p clusters involves computation of a pairwise affinity kernel $w(x_i,x_j)$ , resulting in an $n \times n$ matrix W. The kernel is commonly chosen to be a Gaussian with bandwidth $\sigma$ :

\begin{equation*}w(x_i,x_j) = \exp\big({-}\|x_i-x_j\|^2/\sigma^2\big).\end{equation*}

W defines a graph with n nodes where the weight of the edge between $x_i$ and $x_j$ is $w(x_i,x_j)$ . The normalized symmetric graph Laplacian [Reference von Luxburg43] $L_{\textrm{sym}} $ is defined as

\begin{equation*}L_{\textrm{sym}} = I - D^{-1/2}WD^{-1/2},\end{equation*}

where D is a diagonal matrix with the sum of each row on the diagonal. The eigenvectors $\{v_1,\ldots,v_p \}$ corresponding to the p smallest eigenvalues of $L_{\textrm{sym}}$ are then calculated and concatenated into the $n\times p$ matrix V. The rows of V are normalized to have unit norm and are then clustered into p clusters using the k-means algorithm. Crucially, the multiplicity of eigenvalue 0 of $L_{\textrm{sym}}$ equals the number of connected components of the graph defined by $L_{\textrm{sym}}$ , and the eigenvectors corresponding to eigenvalue 0 span a p-dimensional subspace that contains the vectors $\{D^{1/2} \mathds{1}_j\}_{j=1}^p$ , where $\mathds{1}_j$ is piecewise constant on the jth connected component. In the case of p well-separated clusters, each connected component corresponds to a cluster, and the first p eigenvectors contain the information necessary to separate the clusters. In practice, eigenvalues corresponding to distinct clusters in the datasets will have eigenvalues close to zero, and even this happens only in the well-separated case.

The computational complexity and memory storage requirements of computing a full affinity matrix W scale quadratically with n, typically making computation intractable when n exceeds tens of thousands of points. Notably, as the distance between any two points x and y increases, w(x, y) decays exponentially. Therefore W can be approximated by a sparse matrix Wʹ, where $W^{\prime}_{ij} =w(x_i,x_j)$ if $x_j$ is among $x_i$ ’s k nearest neighbors or $x_i$ is among $x_j$ ’s nearest neighbors, and 0 otherwise.

Fast algorithms have been developed to find approximate nearest neighbors (e.g. [Reference Jones, Osipov and Rokhlin14]), allowing for efficient computation of Wʹ, and Lanczos methods can be used to efficiently compute its eigenvectors. When the number of neighbors, k, is chosen sufficiently large, Wʹ is a sufficiently accurate approximation of W for most applications. However, when k cannot be chosen large enough (e.g. due to memory limitations when n is of the order of millions of points), the connectivity of the k-nearest-neighbor graph represented by Wʹ can be highly sensitive to noise, leading Wʹ to overfit the data and poorly model the overall structure. In the extreme case, Wʹ can lead to a large number of disconnected components within each cluster, such that the smallest eigenvectors correspond to each of these disconnected components and not the true structure of the data.

On the other hand, choosing a random k-sized subset of K nearest neighbors, for $K>k$ , results in a graph with the same number of edges which is much more likely to be connected within each cluster and hence allow for spectral clustering (Figure 4). This strategy is a more effective ‘allocation’ of the k edges, in the resource-limited setting. A naïve implementation is to calculate the K nearest neighbors of every point, and then select a random subset of k neighbors to connect to. This does not alleviate the nearest-neighbor search time, but has reduced memory requirements. In the following, we refer to this approach as the ‘random near neighbors’ or ‘near’ method.

2.2. Potential implementation

In order to apply this method to large datasets on resource-limited machines, an efficient algorithm for finding a k-sized subset for the K nearest neighbors of each point is needed. The naïve implementation of the near method is prohibitive for large datasets. Given a dataset so large that K nearest neighbors cannot be computed, how can we find k-sized random subsets of the K nearest neighbors for each point? Interestingly, this corresponds to an ‘inaccurate’ nearest-neighbor algorithm, in that the ‘near’ neighbors of each point are sought, not the ‘nearest’. From this perspective, it seems an easier problem than that of finding the nearest neighbors. We suggest a simple and fast implementation which we have found to be empirically successful (Algorithm 1). Our approach is probabilistic: first we perform a random partition of the data into $ {{K}/{k}}$ subsets of equal size. For simplicity we assume that the number of data points n is a multiple of K and that K is a multiple of k. Then, for each point $x_i$ we search for the k nearest neighbors among one of the preallocated subsets. Thus, on average k points from the K nearest neighbors in A will be among the subset samples. A k-nearest-neighbor search will therefore yield k out of the $\sim K$ nearest neighbors. We emphasize that the resulting graph is simply an approximation to the graphs described in Theorems 1.1 and 1.2, and hence these results do not necessarily apply directly.

Figure 4:

$16\,000$ points arranged in four clusters and a spiral. We compare connecting every point to its two nearest neighbors (a) and connecting every point to two randomly chosen out of its seven nearest neighbors (b). Connected components are colored: graph (a) has $\sim 700$ connected components; graph (b) consists of the actual five clusters.

We use $ K/k $ preallocated subsets since this enables us to use special data structures to enhance the searching speed. For example, our MATLAB implementation constructs a Kd-tree on each partition and searches for all the neighbors of all points assigned to that partition simultaneously. As in [Reference Kusner, Tyree, Weinberger and Agrawal16], where a k-nearest-neighbor classifier is constructed using a subset of the points, we find that searching a much smaller number of points leads to a speed-up of several orders of magnitude (Tables 4 and 5).

2.3. Numerical results

As proof of concept, we applied spectral clustering to two large datasets and compared the quality of the embedding and computational times between the traditional nearest-neighbor approach (denoted nearest-k), random near neighbors (denoted near- $k/K$ ), and the partition method described in Algorithm 1 (denoted partition- $k/K$ ). For all three approaches the graph edges are weighted using the Gaussian kernel from above with an adaptive bandwidth $\sigma_i$ equal to the point’s squared distance to its kth neighbor. The first dataset is InfiMNIST [Reference Loosli, Canu and Bottou20], where we chose digits 0, 3, 6, 7, resulting in a dataset of $n \sim 3\,271\,995$ in a $d=784$ -dimensional space. The second dataset is Reuters [Reference Lewis, Yang, Rosen and Li17], composed of $645\,564$ articles, across four root categories in a $d=2000$ -dimensional space. Note that while InfiMNIST is a balanced dataset, in Reuters the largest cluster is twice as large as two of the other clusters, and six times larger than the smallest cluster. The full details of the datasets and their preprocessing appear in Appendix A.

We used the Lanczos iterations as implemented in MATLAB’s ‘eigs’ function to compute the first four eigenvectors of the Laplacians for InfiMNIST and first 20 for Reuters. For Reuters, we used more eigenvectors than the number of expected clusters, as some of the categories are composed of multiple smaller clusters, requiring more eigenvectors to reveal the underlying structure of the data.

For the InfiMNIST dataset, we plot the embedding of the datapoints computed with the first three eigenvectors of nearest-10, nearest-50 and nearest-100 in Figure 5(a–c) and near-2/100 and partition-2/100 in Figure 5(d, e). The first three eigenvectors of nearest-10 do not separate the digits, and for nearest-50 the embedding collapses to a curve with multiple outliers, providing a poor visualization of the data, that is, neither reveals the underlying manifold on which the digits lie. Increasing the number of nearest neighbors in nearest-100 provides a meaningful embedding. Remarkably, the same quality embedding can be obtained with near-2/100 and partition-2/100, despite it being a much sparser graph.

Table 2.

Clustering quality metrics (NMI and ACC) for spectral clustering of four digits 0, 3, 6, 7 of InfiMNIST ( $\sim$ 3.27 million points) using a k-nearest-neighbor graph compared to using the near-neighbor and partition approaches. The subspace angle between leading eigenvectors of each construction and the leading eigenvectors of nearest-100 is also computed

To quantify our results, we perform K-means on the eigenvectors and compare the resulting clusters to the true labels. To assess the quality of the clusters we use two different popular measures: normalized mutual information (NMI) and unsupervised clustering accuracy (ACC). The definition and details of these measures can be found in the Appendix A. Results are presented in Tables 2 and 3 (more detailed results across a wider range of k values for the near and partition approaches appear in Appendix A). We note that results for Reuters are comparable to those achieved by SpectralNet in [Reference Shaham, Stanton, Li, Basri, Nadler and Kluger31], where a deep neural network is trained to map datapoints to the corresponding eigenspace of their associated graph Laplacian matrix.

We also calculate the subspace angle (principal angle) between the embedding for nearest-K versus near- $k/K$ and partition- $k/K$ embeddings for increasing k, where we consider the embedding obtained from nearest-K to be the ‘ground-truth’ embedding. For InfiMNIST, the angle between the ‘ground-truth’ embedding and the embeddings of both near-neighbor methods is very small, while for nearest-k the angle is practically maximal. For Reuters, the subspace angles near- $k/K$ are small and decrease as k increases (see Appendix A). For partition- $k/K$ , the angle is large but drops around $k=50$ and decreases further as k increases.

Table 3.

Quality metrics as in Table 2 for spectral clustering of Reuters ( $\sim 650\,000$ points)

Figure 5:

Datapoints embedding of four digits from the InfiMNIST data set computed by the sparse graph Laplacian leading eigenvectors. Connecting to k nearest neighbors when k is too small leads to catastrophic results (a, b), while a successful embedding is obtained for $k=100$ (c). Connecting to two randomly chosen out of the 100 nearest neighbors gives a comparable embedding (d), while using far fewer edges. The partition method (Algorithm 1) also produces an embedding of equivalent quality (e).

To compute these spectral embeddings there are two computationally intensive steps: near(est)-neighbor search and computation of the leading eigenvectors of the Laplacian (Tables 4 and 5). The partition method described in Algorithm 1 is 1–2 orders of magnitude faster than searching for the number of nearest neighbors necessary to obtain the above results. For the second step, the time taken to compute the eigenvectors is mainly determined by two factors: (i) the sparseness of the Laplacian matrix, which determines the complexity of a single iteration, and (ii) the spectrum of the Laplacian matrix, which determines the rate of convergence. The near-neighbor approach has an obvious advantage over the nearest-neighbor approach in terms of sparsity of the Laplacian. In terms of its spectral decay, however, the comparison depends on the values of k and K. If K is insufficient for a good embedding (i.e $K=20$ for InfiMNIST) the convergence is extremely slow. On the other hand, if K is sufficient, then the convergence rate improves dramatically and thus might require fewer iterations than the k-near-neighbor approach. For InfiMNIST, the partition method took only 5 minutes for the near-neighbor search, and computing the first three eigenvectors took 6 minutes (in contrast to many hours for the nearest-neighbor approach). Similar speed-ups can be seen with the Reuters dataset, where both the near-neighbor search and eigenvector computation took less than a minute in total (in contrast to longer than an hour using the nearest-neighbor approach).

Table 4.

Time taken by neighbor search and computation of leading eigenvectors for the InfiMNIST dataset ( $\sim$ 3.27 million points)

Table 5.

Run-time as in Table 4 for the Reuters dataset ( $\sim 650\,000$ points)

2.4. Further outlook

We demonstrate the application of our approach in the context of spectral clustering but this is only one example. There are a great many other methods of dimensionality reduction that start by constructing a graph that roughly approximates the data, for example t-distributed stochastic neighborhood embedding (t-SNE) [Reference Linderman and Steinerberger19, Reference van der Maaten and Hinton42], diffusion maps [Reference Coifman and Lafon8], or Laplacian eigenmaps [Reference Belkin and Niyogi6]. This refinement could be valuable for a very wide range of algorithms that construct graph approximations out of underlying point sets. Determining the precise conditions under which this method is effective for which algorithm will strongly depend on the context, but needless to say, we consider the experiments shown in this section to be extremely encouraging. We believe this paper suggests many possible directions for future research. Are there other natural randomized near-neighbor constructions? Other questions include the behavior of the spectrum and the induced random walk. Here we would like to point out briefly that random graphs are natural expanders [Reference Kolmogorov and Barzdin15, Reference Margulis23, Reference Pinsker29]. This should imply several additional degrees of stability that the standard k-nearest-neighbor construction does not have.

3.1. The Erdős–Rényi lemma

Before embarking on the proof, we give a short description. The proof is not subtle and follows along completely classical lines but occurs in an unfamiliar regime: we are interested in ensuring that the likelihood of obtaining a disconnected graph is very small. The subsequent argument, which is not new but not easy to immediately spot in the literature, is included for the convenience of the reader (much stronger and more subtle results usually focus on the threshold $p = (1 \pm \varepsilon) (\!\log{n})/n$ ).

Lemma 3.1. Let G(n,p) be an Erdős–Rényi graph with $p > 10\log{n}/n$ . Then, for n sufficiently large,

\begin{equation*} \mathbb{P}( \textit{\textit{G}(\textit{n},\,\textit{p}) is disconnected}) \lesssim {\textrm{e}}^{-pn/3}.\end{equation*}

Proof. It suffices to bound the likelihood of finding an isolated set of k vertices from above, where $1 \leq k \leq n/2$ . For any fixed set of k vertices, the probability of being isolated is bounded from above by

\begin{equation*} \mathbb{P}(\mbox{fixed set of \textit{k} vertices being disconnected}) \leq (1-p)^{k(n-k)}\end{equation*}

and thus, using the union bound,

\begin{equation*} \text{$\mathbb{P}( G(n,p)$ is not connected}) \leq \sum_{k=1}^{n/2}{ \binom{n}{k}(1-p)^{k(n-k)}}.\end{equation*}

We use

\begin{equation*} \binom{n}{k} \leq \biggl( \dfrac{ n e }{k}\biggr)^k\end{equation*}

to rewrite the expression as

\begin{align*} \sum_{k=1}^{n/2}{ \binom{n}{k}(1-p)^{k(n-k)}} &\leq \sum_{k=1}^{n/2}{ {\textrm{e}}^{k + k \log{n} + k \log{k} + [\log{(1-p)}] k (n-k)}} \\[2pt] &\leq \sum_{k=1}^{n/2}{ {\textrm{e}}^{k (3 \log{n} + [\log{(1-p)}] (n-k)) }} \\[2pt] &\leq \sum_{k=1}^{n/2}{ {\textrm{e}}^{k (3 \log{n} + [\log{(1-p)}] (n/2)) }}\\[2pt] &\lesssim {\textrm{e}}^{3 \log{n} + [\log{(1-p)}] n/2},\end{align*}

where the last step is merely the summation of a geometric series and is valid as soon as

\begin{equation*} 3 \log{n} + [\log{(1-p)}] \dfrac{n}{2} < 0,\end{equation*}

which is eventually true for n sufficiently large since $p > 10\log{n}/n$ .

3.2. A mini-percolation lemma

The purpose of this section is to derive rough bounds for a percolation-type problem. These problems have been of great interest in mathematical physics and probability theory (see e.g. Penrose and Pisztora [Reference Penrose26]). We provide a simple self-contained argument that, while not being sharp, results in a simple estimate sufficient for our purpose.

Proof of Lemma 3.2. The proof is actually fairly lossy and proceeds by massive overcounting. The only way to remove mass from the giant block is to remove points in an organized manner: adjacent squares have to be removed in a way that encloses a number of squares that are not removed (see Figure 6).

Figure 6:

Removing tiny squares randomly: this random sample ends up removing a bit more from the giant component but is quite unlikely.

The next question is how many other points can possibly be captured by a connected component on $\ell$ -nodes. The isoperimetric principle implies

\begin{equation*} \#\ \text{blocks captured by $\ell$ nodes $ \lesssim_d \ell^{{{d}/{({d-1})}}} \leq \ell^2$.}\end{equation*}

Altogether, this implies that we expect to capture at most

\begin{equation*}\sum_{\ell=1}^{n^d} n^d (2^{3^d -1})^{\ell} (\!\log{n})^{-c \ell} \ell^2 \leq n^d \sum_{\ell=1}^{\infty}\biggl( \dfrac{ 2^{3^d -1}}{ (\!\log{n})^{c}}\biggr)^{\ell} \ell^2 \lesssim \dfrac{ n^d}{(\!\log{n})^c},\end{equation*}

where the last inequality holds as soon as $\log{n}^c \gg 2^{3^d-1}$ and follows from the derivative geometric series

\begin{align*} \sum_{\ell=1}^{\infty}{ \ell^2 q^{\ell} } = \dfrac{q(1+q)}{(1-q)^3} \quad \mbox{whenever}\ |q| < 1.\\[-40pt] \end{align*}

□

Remark. There are two spots where the argument is fairly lossy. First of all, every connected component on $\ell$ nodes is, generically, counted as $\ell$ connected components of length $\ell -1$ , as $\sim \ell^2$ connected components of size $\ell - 2$ , and so on. The second part of the argument is the application of the isoperimetric inequality: a generic connected component on $\ell$ nodes will capture $ \ll \ell^{2}$ other nodes. These problems seem incredibly close to existing research, and it seems likely that either they have been answered already or that techniques from percolation theory might provide rather immediate improvements.

We now show a separate result which we will use later. We call a subset $A \subset \{1, 2, \dots, n \}^d$ connected if the resulting graph is connected: here, edges are given by connecting every node to all of its adjacent nodes that differ by at most one in each coordinate (that number is bounded from above by $3^{d}-1$ ).

Lemma 3.3. The number of connected components A in the grid graph over $\{1,2,\dots,n \}^d$ with cardinality $|A| = \ell$ is bounded from above:

\begin{equation*} \#\ \textit{{connected} components of size $\ell \leq n^d \big(2^{3^d -1}\big)^{\ell}$.}\end{equation*}

Proof. The proof proceeds in a fairly standard way by constructing a combinatorial encoding. We show how this is done in two dimensions, giving an upper bound of $n^2 256^{\ell}$ ; the construction immediately transfers to higher dimensions in the obvious way. The encoding is given by a direct algorithm. See Figure 7.

1. (1) Pick an initial vertex $x_0 \in A$ . Describe which of the eight adjacent squares are occupied by picking a subset of $\{1,2,\dots, 8\}$ .

2. (2) Implement a depth-first search as follows: pick the smallest number in the set attached to $x_0$ and describe its neighbors, if any, that are distinct from previously selected nodes as a subset of $\{1,2,\dots, 8\}$ .

3. (3) Repeat until all existing neighbors have been mapped out (the attached set is the empty set) and then go back and describe the next branch.

Figure 7:

Fixing labels for the eight immediate neighbors.

Just for clarification, we quickly show the algorithm in practice. Suppose we are given an initial point $x_0$ and the sequence of sets

\begin{equation*} \{4,5\}, \{3,4\}, \{\}, \{\}, \{5\}, \{4\}, \{\}.\end{equation*}

Then this uniquely identifies the set shown in Figure 8.

Figure 8:

The starting point followed by generating the connected component described by the sequence of sets $ \{4,5\}, \{3,4\}, \{\}, \{\}, \{5\}, \{4\}, \{\}$ .

Clearly, this description returns $\ell$ subsets of $\{1,\dots, 8\}$ , of which there are 256. Every element in A generates exactly one such subset and every connected component can thus be described by giving the $n^d$ initial points and then a list of $\ell$ subsets of $\{1,\dots, 8\}$ . This implies the desired statement; we note that the actual number should be much smaller since this way of describing connected components has massive amounts of redundancy and overcounting.

3.3. Outline of the proof

The proof proceeds in three steps.

1. (1) Partition the unit cube into smaller cubes such that each small cube has an expected number of $\sim \log{n}$ points (and thus the number of cubes is $\sim n/\log{n}$ ). Show that the likelihood of a single cube containing significantly more or significantly fewer points is small.

2. (2) Show that graphs within the cube are connected with high probability.

3. (3) Show that there are connections between the cubes that ensure connectivity.

3.4. Step 1

We start by partitioning $[0,1]^d$ in the canonical manner into axis-parallel cubes having side-length $\sim (c\log{n}/n)^{1/d}$ for some constant c to be chosen later. There are roughly $\sim n/(c \log{n})$ cubes and they have measure $\sim c \log{(n)}/n$ . We start by bounding the likelihood of one such cube containing $\leq \log{n}/100$ points. Clearly, this likelihood can be written as a Bernoulli random variable:

\begin{equation*} \mbox{number of points in cube} = \mathcal{B}\biggl(n, \dfrac{c\log{n}}{n}\biggr).\end{equation*}

The Chernoff–Hoeffding theorem [Reference Hoeffding13] implies

\begin{equation*}\mathbb{P}\biggl( \mathcal{B}\biggl(n, \dfrac{c\log{n}}{n}\biggr) \leq \dfrac{\log{n}}{100} \biggr) \leq \exp\biggl( - n D\biggl(\dfrac{\log{n}}{100n} || \dfrac{c \log{n}}{n} \biggr)\biggr),\end{equation*}

where D is the relative entropy

\begin{equation*} D(a || b) = a \log{\dfrac{a}{b}} + (1-a) \log{\dfrac{1-a}{1-b} }.\end{equation*}

Here, we have, for n large,

\begin{equation*}D\biggl(\dfrac{\log{n}}{100n} || \dfrac{c \log{n}}{n} \biggr) \sim \dfrac{\log{n}}{n}\biggl(c - \dfrac{1}{100} + \dfrac{1}{100}\log{\dfrac{1}{100c}}\biggr).\end{equation*}

This implies that, for c sufficiently large, we have

\begin{equation*} \mathbb{P}(\text{{a} fixed cube has {fewer} than ${{\log{n}}/{100}}$ points}) \lesssim_{c, \varepsilon} \dfrac{1}{n^{c-\varepsilon}}\end{equation*}

and the union bound implies

\begin{equation*} \mathbb{P}(\text{there exists {a cube with fewer} than ${{\log{n}}/{100}}$ points}) \lesssim_{c, \varepsilon} \dfrac{1}{n^{c - 1 -\varepsilon}}{.}\end{equation*}

The same argument also shows that

\begin{equation*}\mathbb{P} (\text{{there exists a} cube with more than $10c \log{n} $ points}) \lesssim \dfrac{1}{n^{c}}.\end{equation*}

This means we have established the existence of a constant c such that, with likelihood tending to 1 as $n \rightarrow \infty$ (at arbitrary inverse polynomial speed provided c is big enough), for all cubes Q,

\begin{equation*} \dfrac{\log{n}}{100} \leq \#\ \{\mbox{points in \textit{Q}}\} \leq 10 c \log{n}.\end{equation*}

Henceforth we only deal with cases where these inequalities are satisfied for all cubes.

3.5. Step 2

We now study what happens within a fixed cube Q. The cube is surrounded by at most $3^d-1$ other cubes, each of which contains at most $10c \log{n}$ points. This means that if, for any $x \in Q$ , we compile a list of its $3^d 10 c \log{n}$ nearest neighbors, we are guaranteed that every other element in Q is on that list. Let us suppose that the rule is that each point is connected to each of its $3^d 10 c \log{n}$ nearest neighbors with likelihood

\begin{equation*} p = \dfrac{m}{3^d 10 c \log{n}}.\end{equation*}

Then Lemma 3.1 implies that, for $m \gtrsim 10 \log{(3^d 10 c \log{(n)})} \sim_{d,c} \log \log{n}$ , the likelihood of obtaining a connected graph strictly within Q is at least $(\!\log{n})^{-c}$ . Lemma 3.2 then implies the result provided we can ensure that points in cubes connect to their neighboring cubes.

3.6. Step 3

We now establish that the likelihood of a cube Q having, for every adjacent cube R, a point that connects to a point in R is large. The adjacent cube has $\sim \log{n}$ points. The likelihood of a fixed point in Q not connecting to any point in R is

\begin{equation*}\leq \biggl( 1 - \dfrac{{{\log{n}}/{100}}}{ 3^d 10c \log{n}} \biggr)^{c\log{\log{n}}} = \biggl( 1 - \dfrac{1}{3^d 1000c} \biggr)^{c\log{\log{n}}} \lesssim (\!\log{n})^{-\varepsilon_{c,d}}.\end{equation*}

The likelihood that this is indeed true for every point is then bounded from above by

\begin{equation*} (\!\log{n})^{-\varepsilon_{c,d} \log{n}/100} \lesssim n^{-1},\end{equation*}

which means, appealing again to the union bound, that this event occurs with a likelihood going to 0 as $n \rightarrow \infty$ . □

Connectedness. It is not difficult to see that this graph is unlikely to be connected. For a fixed vertex v, there are $\sim c \log{n}$ possible other vertices it could connect to and $\sim c \log{n}$ other vertices might possibly connect to v. Thus

\begin{equation*} \mathbb{P}(\text{\textit{v} is isolated}) \lesssim \biggl(1 - \dfrac{c_2 \log{\log{n}}}{\log{n}}\biggr)^{c_3 \log{n}} \leq {\textrm{e}}^{-c_2 c_3 \log{\log{n}}} = \dfrac{1}{(\!\log{n})^{c_2 c_3}}.\end{equation*}

This shows that we can expect at least $n (\!\log{n})^{-c_2 c_3}$ isolated vertices. This also shows that the main obstruction to connectedness is the non-trivial likelihood of vertices not forming edges to other vertices.

A.1. Data and preprocessing

The first dataset is the MNIST8M dataset generated by InfiMNIST [Reference Loosli, Canu and Bottou20], which provides an unlimited supply of handwritten digits derived from MNIST using random translations and permutations. For simplicity of visualization, we chose digits 0, 3, 6, 7, resulting in a dataset of $n \sim 3\,271\,995$ in a $d=784$ -dimensional space. The second dataset is Reuters [Reference Lewis, Yang, Rosen and Li17], composed of $645\,564$ articles, across four root categories: corporate/industrial, government/social, markets, and economics (documents with multiple root categories were removed). Each article is represented using tf-idf features on the 2000 most frequently occurring word stems, as in [Reference Xie, Girshick and Farhadi44]. In addition, we removed all points that were exact duplicates. For both datasets, we reduced the dimensionality of the samples via the randomized PCA algorithm [Reference Rokhlin, Szlam and Tygert30] implemented in [Reference Li, Linderman, Szlam, Stanton, Kluger and Tygert18]. All neighbor searches were done in the reduced dimension.

A.2. Clustering measures

Normalized mutual information (NMI) is defined as

\begin{equation*}\textrm{NMI}(l,c) = \dfrac{I(l;\,c)}{\max\{ H(l),H(c) \}} ,\end{equation*}

where H(c), H(l) denote the entropy of the clustering result c and the true labels l, respectively, and $I(l;\,c)$ denote the mutual information between them. Unsupervised clustering accuracy (ACC), is defined as

\begin{equation*}\textrm{ACC}(l,c) = \dfrac{1}{n}\max_{\pi \in \Pi} \sum_{i=1}^n \mathds{1} \{l_i=\pi(c_i) \},\end{equation*}

where $\Pi$ is the collection of all permutations of $\{1, \dots, k\}$ . The optimal permutation $\pi$ can be computed using the Kuhn–Munkres algorithm [Reference Munkres25].

A.3. Extended simulations

Table 6.

Measures for InfiMNIST dataset

Table 7.

Measures for Reuters dataset