DROPS

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2025.54

BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing (Poster Abstract)

Authors: Amyra Meidiana, Seok-Hee Hong, and Kwan-Liu Ma

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

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.

Cite as

Amyra Meidiana, Seok-Hee Hong, and Kwan-Liu Ma. BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 54:1-54:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meidiana_et_al:LIPIcs.GD.2025.54,
  author =	{Meidiana, Amyra and Hong, Seok-Hee and Ma, Kwan-Liu},
  title =	{{BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{54:1--54:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.54},
  URN =		{urn:nbn:de:0030-drops-250400},
  doi =		{10.4230/LIPIcs.GD.2025.54},
  annote =	{Keywords: tsNET, t-SNE, Large Graph Drawing}
}

Search Results

Documents authored by Ma, Kwan-Liu

BH-tsNET, FIt-tsNET, L-tsNET: Fast tsNET Algorithms for Large Graph Drawing (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message