2026-07-22T13:14:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25040 2026-02-09T07:54:01Z ddc:004 open_access

BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing (Poster Abstract) Meidiana, Amyra Hong, Seok-Hee Ma, Kwan-Liu tsNET t-SNE Large Graph Drawing The tsNET algorithm adapts the popular dimensional reduction method t-SNE for graph drawing to compute high-quality drawings, preserving the neighborhood and clustering structure. However, its O(nm) runtime results in poor scalability for large graphs. In this poster, we present three fast algorithms for reducing the time complexity of tsNET to O(n log n) time and O(n) time, by integrating new fast methods for computation of high-dimensional probabilities and entropy computation with fast t-SNE algorithms for computation of KL divergence gradient. Specifically, we present two O(n log n)-time algorithms BH-tsNET and FIt-tsNET, incorporating partial BFS-based high-dimensional probability computation and a new quadtree-based entropy computation with fast t-SNE algorithms, and O(n)-time algorithm L-tsNET, introducing a new fast interpolation-based entropy computation. Extensive experiments using benchmark data sets confirm that BH-tsNET, FIt-tsNET, and L-tsNET outperform tsNET, achieving 93.5%, 96%, and 98.6% faster runtime, respectively, while computing similar quality drawings in terms of quality metrics (neighborhood preservation, stress, shape-based metrics, and edge crossing) and visual comparison. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amyra Meidiana and Seok-Hee Hong and Kwan-Liu Ma 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.54 urn:nbn:de:0030-drops-250400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.54 eng https://creativecommons.org/licenses/by/4.0/legalcode