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

• URL: http://arxiv.org/abs/2607.08746v1
• Date: Thu, 09 Jul 2026 17:47:08 GMT
• Title: Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph
• Abstract summary: We show how standard graph algorithms applied to this graph enhance data sensemaking.<n>We show that these graph-based analyses are not only practical but also competitive with or complementary to purpose-built methods.
• Score: 37.806680343382595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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).

Related papers

• CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification [52.452902154360565]
  CuBAS is an information-geometric framework for adaptive data selection in supervised classification.<n>A labeled dataset can be viewed as a statistical manifold, on which local curvature, estimated via the ratio of second to first-order observed Fisher information, faithfully encodes the geometric complexity of the data distribution.
  arXiv  Detail & Related papers  (2026-07-03T09:36:02Z)
• Gaussian Rank-Based Neighborhood Degree for Graph Neural Networks in Image Classification [2.7783060691263906]
  We propose GRaNDe (Gaussian Rank-based Neighborhood Degree), which integrates neighborhood ranking with Gaussian distance weighting to better capture node importance.<n>Experiments on five public image classification datasets show consistent accuracy improvements and competitive or superior results compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-23T03:07:56Z)
• Graph Semi-Supervised Learning for Point Classification on Data Manifolds [16.311715311352597]
  We propose a graph semi-supervised learning framework for classification tasks on data manifold.<n>Motivated by the manifold hypothesis, we model data as points sampled from a low-dimensional $mathcalM subset mathbbRF$.<n>We show that, under uniform sampling from $mathcalM$, the generalization gap of the semi-supervised task diminishes with increasing graph size.
  arXiv  Detail & Related papers  (2025-06-13T19:52:54Z)
• Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs)<n>We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN.<n>We verify this theoretical result with experiments on multiple real-world datasets.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• Hub-aware Random Walk Graph Embedding Methods for Classification [44.99833362998488]
  We propose two novel graph embedding algorithms based on random walks that are specifically designed for the node classification problem. The proposed methods are experimentally evaluated by analyzing the classification performance of three classification algorithms trained on embeddings of real-world networks.
  arXiv  Detail & Related papers  (2022-09-15T20:41:18Z)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  Current Graph Neural Networks (GNN) architectures rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance.
  arXiv  Detail & Related papers  (2022-05-31T12:24:01Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Adaptive Graph Convolutional Network with Attention Graph Clustering for Co-saliency Detection [35.23956785670788]
  We present a novel adaptive graph convolutional network with attention graph clustering (GCAGC) We develop an attention graph clustering algorithm to discriminate the common objects from all the salient foreground objects in an unsupervised fashion. We evaluate our proposed GCAGC method on three cosaliency detection benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-13T09:35:59Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.