Similarity Graphs, Density, and Connectivity

A node's k-occurrence count is the number of other points whose neighbour list it appears in. That is its degree in the k-NN graph. In enough dimensions, that count starts predicting something else: whether the node sits on the shortest paths between regions.

This was measured, not asserted. In 2010, working over 50 real data sets and over i.i.d. uniform data, Radovanović and colleagues tracked each node's k-occurrence count against its betweenness centrality in the graph. In i.i.d. uniform data the Spearman correlation between the two rises from 0.311 at d = 3, to 0.539 at d = 20, to 0.647 at d = 100. Over the same uniform data the sample skewness of N10 under Euclidean distance runs 0.121, 1.541 and 5.445 at d = 3, 20 and 100. The neighbour-count distribution grows a long right tail. The points in that tail move onto the shortest paths.

Across the 50 real data sets, the correlation between that betweenness measure and the skewness of N10 is 0.548. Their reading of it, in the Journal of Machine Learning Research: “This indicates that real data sets which exhibit strong skewness in the distribution of N10 also tend to have strong correlation between N10 and betweenness centrality of nodes, giving hubs a broader significance for the structure of the k-NN graphs.”

The phenomenon has been re-measured since. Feldbauer and Flexer, at OFAI in Vienna, ran it over 50 public machine learning data sets in 2019: “Hubness is typically measured as the skewness of the k-occurrence distribution”.

So a high-degree node is not merely popular. In enough dimensions it is structurally central, and the traffic between regions runs through it. Building the graph converts a metric into edges. That conversion can reveal local organization. It can also introduce shortcuts, disconnected islands, and density artifacts.

Each stage changes which local relationships become available to downstream methods. The first two stages already carry an approximation that is easy to forget.

At scale, the k-nearest-neighbour graph a pipeline builds is not the exact one. NN-Descent is how it usually gets built, and the 2011 paper from Princeton that introduced it says in its abstract what that costs: “We have shown with a variety of datasets and similarity measures that the proposed method typically converges to above 90% recall with each point comparing only to several percent of the whole dataset on average.” The same paper puts the empirical cost at “the empirical cost is around O(n1.14) for all datasets we experimented with”.

Above 90% recall is not 100%. And this is not a niche option. UMAP's own paper says the search for the k nearest neighbours “can be performed via any nearest neighbour or approximate nearest neighbour search algorithm”, and that the UMAP implementation prefers nearest neighbor descent. So the edges handed to the embedding are approximately, not exactly, each point's k nearest neighbours. That is settled before any of the weighting and inspection choices in the later stages are made.

The right graph balances local coverage, density variation, and computational cost. The radius family is the one whose threshold has a documented history, and that history is instructive about how such thresholds get set.

DBSCAN's density parameter was set by fiat in 1996, and its authors said so in the section on choosing Eps and MinPts: “our experiments indicate that the k-dist graphs for k > 4 do not significantly differ from the 4-dist graph and, furthermore, they need considerably more computation. Therefore, we eliminate the parameter MinPts by setting it to 4 for all databases (for 2-dimensional data).” That parenthesis is the whole warning. It is also the part that travelled least well.

Twenty-one years later the same authors, now writing with Erich Schubert, revisited the heuristic and pointed instead to a value that scales: Sander et al. “suggest setting it to twice the dataset dimensionality, i.e., minPts = 2 · dim”. On the radius itself they add that “The way DBSCAN is designed, ε should be chosen as small as possible.”

A threshold that reflects an absolute neighbourhood scale inherits the dimension it was measured in. It inherits the scaling of the representation too.

Treat building the graph as an auditable preprocessing stage. Perturbing the neighbour count is not a hygiene ritual. The authors of a mainstream tool document exactly what it changes.

UMAP's own paper, in its section on hyper-parameters, warns: “With smaller n values the manifold tends to be broken into many small connected components (care needs to be taken with the spectral embedding for initialization in such cases).” That initialisation is defined in the paper's own Algorithm 4. It takes the 1-skeleton of the graph as a weighted adjacency matrix and returns eigenvectors of its normalised Laplacian. So the neighbour count sets the number of connected components, and the components set the starting layout.

The same dependence turns up independently in a 2021 study by Wang and colleagues in the Journal of Machine Learning Research: “t-SNE uses random values, UMAP applies spectral embedding (Shi and Malik, 1997), and TriMap first runs PCA”.

Varying k, the radius, the bandwidth and the scaling is therefore a test of something specific: whether the component structure survives a defensible change of parameter. Everything initialised from that structure rides on the answer.

A graph should be inspected as an object before it becomes hidden inside another algorithm. How badly connectivity can be misread is measurable.

A widely used community-detection algorithm returns groups that are not connected inside the graph it was given. The 2019 paper in Scientific Reports that reported this is blunt about the scale of it: “In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected.” Its authors then introduced the Leiden algorithm, with a proof that its communities are guaranteed to be connected.

A similarity graph can expose local structure that coordinate-space algorithms miss. It can also amplify hubs, bridges, and scale mistakes. Spectral clustering, UMAP, and several density methods will rely on these relationships, and their output cannot be more trustworthy than the graph assumptions they inherit.

One usable rule for k comes from von Luxburg's spectral clustering tutorial. For n points drawn from a density with connected support, the kNN and mutual kNN graphs “will be connected if we choose k on the order of log(n)”. She notes that the result holds only in the limit. It is a starting point, not a setting.

How much a peer-reviewed conclusion can rest on one inherited graph default is on the record. Becht et al. had reported in Nature Biotechnology that UMAP preserved global structure better than t-SNE. Kobak and Linderman answered in the same journal in 2021: “this alleged superiority of UMAP can be entirely attributed to different choices of initialization in the implementations used by Becht et al.” The t-SNE implementations started from random values. The UMAP implementation started from Laplacian eigenmaps, the spectral embedding of the neighbour graph. Once informative initialisation is used, the two preserve global structure similarly well.

The same conclusion came out of a separate set of experiments, run by Wang and colleagues and published in the Journal of Machine Learning Research that year: “we found that the initialization has a much larger influence on the success rate than simply faster convergence and stability.”

The comparison was never between two methods. It was between two graph-derived defaults.