Leveraging Non-linear Dimension Reduction and Random Walk Co-occurrence for Node Embedding

Ryan DeWolfe

cs.LGFeb 27, 2026

Leveraging Non-linear Dimension Reduction and Random Walk Co-occurrence for Node Embedding

Authors: Ryan DeWolfe

Organizations: Department of Mathematics, Toronto Metropolitan University, Toronto, Canada

Abstract

Leveraging non-linear dimension reduction techniques, we remove the low dimension constraint from node embedding and propose COVE, an explainable high dimensional embedding that, when reduced to low dimension with UMAP, slightly increases performance on clustering and link prediction tasks. The embedding is inspired by neural embedding methods that use co-occurrence on a random walk as an indication of similarity, and is closely related to a diffusion process. Extending on recent community detection benchmarks, we find that a COVE UMAP HDBSCAN pipeline performs similarly to the popular Louvain algorithm.

Figures & tables

Figure 1: Example of embeddings produced by node2vec, node2vec+UMAP, and the proposed COVE+UMAPLE algorithm. The graph is the world-wide airport graph of airports and their connections via direct flights, with ground truth communities (colored) corresponding to the continents. Using node2vec directly to 2 dimensions does not separate any clusters, whereas using node2vec then UMAP or COVE then UMAPLE does (with similar visual quality).

Name	Ref	URL	Domain	$\|V\|$	$\|E\|$	$\|\mathcal{C}\|$	$s_{0}$	$\eta$	$\xi$
Football	[ 15 , 12 ]	[ 18 ]	Competition	115	613	10	12	1.00	0.38
Primary1	[ 46 ]	[ 18 ]	Contact	236	5899	11	0	1.00	0.61
Primary2	[ 46 ]	[ 18 ]	Contact	238	5539	11	0	1.00	0.58
Eu-core	[ 28 ]	[ 18 ]	Email	1005	16385	35	18	1.00	0.68
Eurosis	[ 2 ]	[ 18 ]	Web	1285	6462	13	0	1.00	0.18
Cora	[ 45 ]	[ 18 ]	Citation	2708	5278	7	0	1.00	0.19

Table 1: Table of empirical values for real world datasets with ground truth communities. The columns

|\mathcal{C}|

denotes the number of communities,

s_{0}

the number of outliers, and

\eta

the average number of communities per non-outlier node. The proportion of inter-community edges

\xi

is (approximately) analogous to the

\xi

parameter in the ABCD model.

Figure 2: Evaluating the quality of each embedding method on real networks using an unsupervised framework [ 19 ] . Each bar represents the average of 10 independent embeddings, with the small bar covering the full range of values, for both the global (top) and local (bottom) divergences are reported. In both graphs, a lower score indicates better performance.

Figure 3: Comparing the performance of embedding algorithms for community detection on synthetic ABCD graphs. The embeddings are clustered in 2 (left), 16 (center), and 128 (right) dimensions using HDBSCAN (bottom) and K-Means (top). The COVE+UMAP and COVE+UMAPLE scores are extremely similar (and difficult to visually distinguish).

Figure 4: Comparing embedding methods for community detection on real graphs with known ground truth communities. The embeddings are clustered using HDBSCAN and optimized over the minimum community size parameter. Each bar represent the average score over 10 independent embeddings, with the smaller bar spanning the full range of scores. COVE+UMAP, COVE+UMAPLE, node2vev+UMAP, Louvain, and ECG perfom similarly and better than COVE+SVD or node2vec on most of the graphs.

Figure 5: Performance of a classifier for link prediction on real graphs using edge vectors created by the hadamard product of the end node embeddings. For 10 samples, $5\%$ of edges were removed at random to create a test set and added to an equal number of non-edges to form the test set. Each bar represents the average AUC score, with the smaller black bar spanning the full range of values.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Repeating the experiment from Figure 3 , except using Adjusted Mutual Information to compare clusterings. Since the AMI is only defined for partitions, we cannot evaluate results from HDBSCAN.

Graph	Average	Min	Max	$15\log_{2}\|V\|$
Football	3.36	2	7	102
primary1	5.32	2	13	118
primary2	5.88	2	13	118
eu-core	5.00	2	20	149
eurosis	13.36	4	36	154
cora_small	30.54	4	104	171

Appendix

Table 2: Optimal minimum cluster size values for each of the embedding methods and each real graph used in Figure 4 . Importantly we can see the largest checked value of

15\log_{2}|V|

is larger than the largest optimal value for each graph.

Graph Embedding

Graph embedding maps nodes, edges, or whole graphs into vectors that capture structure for prediction, clustering, retrieval, and analysis.

See all 53 papers

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph
Jul 9, 2026Duen Horng Chau, Donghao Ren, Fred Hohman +1Dimensionality Reduction
Apple
FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling
May 12, 2026Hongmin LiUnsupervised Learning Nyström Method
School of Life Science and Technology, Institute of Science Tokyo · 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan 2Department of Computational Biology and Medical Sciences Graduate School of Frontier Sciences, The University of Tokyo
On Out-of-sample Embedding in UMAP
Jun 3, 2026Mohammad Tariqul Islam, Jason W. FleischerManifold Learning Dimensionality Reduction
Media Lab, Massachusetts Institute of Technology, Cambridge, MA · Electrical and Computer Engineering, Princeton University, Princeton, NJ

Jul 9, 2026J/K move · Enter open · S save

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

Apple

Dimensionality Reduction

Open paper AskPDF arXiv

While UMAP is widely used for exploring high-dimensional data, typical workflows focus on its lower-dimensional embedding, largely overlooking the rich k-nearest-neighbor (kNN) graph that UMAP constructs internally. This graph encodes the data manifold in its original high-dimensional space, before the distortion that UMAP's 2D projection introduces. We demonstrate the untapped potential of this internal representation, showing how standard graph algorithms applied to this graph enhance data sensemaking: (1) PageRank identifies representative data points, (2) k-core decomposition reveals dense core regions versus sparse periphery, and (3) clustering coefficient detects tight-knit neighborhoods with highly-similar data points. Through quantitative and qualitative evaluation on MNIST and Fashion MNIST, we show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods (e.g., k-medoids for exemplar selection, HDBSCAN for density-based clustering).

Abstract

Graph Embedding

Explore similar work

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling

On Out-of-sample Embedding in UMAP