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}
}

Document

DOI: 10.4230/LIPIcs.GD.2024.17

Connectivity-Faithful Graph Drawing

Authors: Amyra Meidiana, Seok-Hee Hong, and Yongcheng Jing

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

Connectivity is one of the important fundamental structural properties of graphs, and a graph drawing D should faithfully represent the connectivity structure of the underlying graph G. This paper investigates connectivity-faithful graph drawing leveraging the famous Nagamochi-Ibaraki (NI) algorithm, which computes a sparsification G_NI, preserving the k-connectivity of a k-connected graph G. Specifically, we first present CFNI, a divide-and-conquer algorithm, which computes a sparsification G_CFNI, which preserves the global k-connectivity of a graph G and the local h-connectivity of the h-connected components of G. We then present CFGD, a connectivity-faithful graph drawing algorithm based on CFNI, which faithfully displays the global and local connectivity structure of G. Extensive experiments demonstrate that CFNI outperforms NI with 66% improvement in the connectivity-related sampling quality metrics and 73% improvement in proxy quality metrics. Consequently, CFGD outperforms a naive application of NI for graph drawing, in particular with 62% improvement in stress metrics. Moreover, CFGD runs 51% faster than drawing the whole graph G, with a similar quality.

Cite as

Amyra Meidiana, Seok-Hee Hong, and Yongcheng Jing. Connectivity-Faithful Graph Drawing. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{meidiana_et_al:LIPIcs.GD.2024.17,
  author =	{Meidiana, Amyra and Hong, Seok-Hee and Jing, Yongcheng},
  title =	{{Connectivity-Faithful Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.17},
  URN =		{urn:nbn:de:0030-drops-213015},
  doi =		{10.4230/LIPIcs.GD.2024.17},
  annote =	{Keywords: Graph connectivity, Faithful graph drawing, Graph sparsification}
}

Search Results

Documents authored by Meidiana, Amyra

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

Abstract

Cite as

Connectivity-Faithful Graph Drawing

Abstract

Cite as

Thanks for your feedback!

Could not send message