Interrelating Fruchterman-Reingold Graph Visualization and Agglomerative Clustering
Authors: Alexandre Benatti, Luciano da F. Costa
Organizations: Institute of Mathematics and Statistics - DCC University of S˜ao Paulo Rua do Mat˜ao, 1010, S˜ao Paulo, SP 05508-090 Brazil · S˜ao Carlos Institute of Physics - DFCM University of S˜ao Paulo Av. Trabalhador S˜ao-Carlense, 400, S˜ao Carlos, SP 13566-590 Brazil
Graph visualization methods and agglomerative clustering have been frequently considered in data analysis and pattern recognition. Because these approaches are interrelated and complementary, it is of particular interest to investigate their associations. In this work, we study the possible relationship between the Fruchterman-Reingold graph visualization method and four types of agglomerative clustering adopting single- and complete-linkage, average, and Ward's linkage criteria. Three types of datasets have been considered in 2 and 10 dimensions, as well as the PCA projection of the latter to two dimensions. The results obtained suggest that the relationship between the methods considered did not vary much for the three types of data mentioned above. At the same time, the agglomerative methods tended to yield results that are mostly similar to each other, while presenting moderate similarity with the original data. The Fruchterman-Reingold visualization resulted similar to the original data, but exhibited relatively smaller similarity to the agglomerative methods.
Figures & tables
Figure 1 : Flow diagram illustrating the approach adopted for relating Fructerman-Reingold graph visualization and four types of agglomerative clustering.
Figure 2 : Example of 2D dataset considered in our study (a) and respective visualization by using the Fruchterman-Reingold method on the reciprocal of the Euclidean distances.
Figure 3 : Dendrograms obtained by the agglomerative clustering approaches adopting single- (a), complete- (b), average (c), and Ward’s (d) linkage criteria. Observe that different upper limits of the distance axes have been chosen for the sake of improved visualization.
Figure 4 : Coincidence similarity matrix ( D=1 ) obtained for the dataset in Fig. 2 (a).
Figure 5 : Average coincidence similarity matrix ( D=1 ) obtained for 5,000 datasets, considering two-dimensional data.
Figure 6 : Average coincidence similarity matrix ( D=1 ) obtained for 5,000 ten-dimensional datasets (a) and for its two-dimensional PCA projection.
Figure 7 : Correlograms relating the similarities between the visualization and agglomerative clustering obtained for three data sets considering two and ten dimensions, and the 2D PCA projection of the latter. The dashed line indicates the linear data regression.
Graphs are commonly visualized in 2D, where humans readily interpret spatial relationships, yet such layouts often distort higher-dimensional structure. We propose to embed graphs in high-dimensional space and search for informative 2D viewpoints that optimize aesthetic and readability metrics (e.g., edge crossings and angular resolution), enabled by a novel differentiable surrogate for edge crossings. Numerical experiments show that these viewpoints consistently outperform standard 2D layouts, and can even surpass methods explicitly designed to optimize these metrics. We further introduce DataFly, an interactive system for exploring multiple candidate viewpoints through seamless navigation. A usability study demonstrates that our approach reveals structural patterns that remain hidden in conventional 2D visualizations.
Ya Ji, Xuefeng Li, Timo Brand +4
Khoury College of Computer Sciences, Northeastern University, Seattle · School of Computation, Information and Technology, Technical University of Munich, Heilbronn, Germany
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).
We present AdaGraph, a graph-native clustering algorithm born from the Structure-Centric Machine Learning (SC-ML) paradigm -- a new field of unsupervised learning that replaces geometry-centric (distance-based) computation with structure-centric (topology-based) computation, fundamentally dissolving the curse of dimensionality. AdaGraph operates entirely within the kNN graph topology, a representation that retains meaningful relational structure in arbitrarily high dimensions where Euclidean distance metrics become uninformative. AdaGraph requires no a priori specification of the number of clusters k, handles noise natively, and scales via the SLCD (Sample-Learn-Calibrate-Deploy) prototype-deployment framework. As its unsupervised tuning objective, AdaGraph pairs with Graph-SCOPE, the topology-based cluster validity index introduced as a separate SC-ML contribution. On 10 synthetic benchmarks spanning d=10 to d=5000, Graph-SCOPE achieves mean ARI=0.900 and correctly selects k on 9/10 datasets -- outperforming Silhouette, Davies-Bouldin, and Calinski-Harabasz -- while maintaining Kendall tau >= 0.92 with ground-truth cluster quality across all dimensionalities (Silhouette: tau ~= 0.46). We validate AdaGraph across three scientific domains: (1) gene co-expression discovery in hepatocellular carcinoma (GSE14520, 10,000 genes, 488 patients, no dimensionality reduction), where AdaGraph identifies condition-specific gene modules that WGCNA, ICA, NMF, and Spectral Biclustering fail to resolve; (2) natural language text clustering, where AdaGraph achieves ARI=0.751 on 20NG-6cat versus HDBSCAN's 0.464 (62% relative improvement); (3) materials science clustering of superconductors (145-dimensional Magpie features), perovskites, and JARVIS-DFT materials, where AdaGraph achieves the highest Graph-SCOPE on all three datasets.