Balancing Between the Local and Global Structures (LGS) in Graph Embedding

Jacob Miller, Vahan Huroyan, Stephen Kobourov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. Some embedding methods aim to capture global structures, while others attempt to preserve local neighborhoods. Few methods attempt to do both, and it is not always possible to capture well both local and global information in two dimensions, which is where most graph drawing live. The choice of using a local or a global embedding for visualization depends not only on the task but also on the structure of the underlying data, which may not be known in advance. For a given graph, LGS aims to find a good balance between the local and global structure to preserve. We evaluate the performance of LGS with synthetic and real-world datasets and our results indicate that it is competitive with the state-of-the-art methods, using established quality metrics such as stress and neighborhood preservation. We introduce a novel quality metric, cluster distance preservation, to assess intermediate structure capture. All source-code, datasets, experiments and analysis are available online.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 31st International Symposium, GD 2023, Revised Selected Papers
EditorsMichael A. Bekos, Markus Chimani
PublisherSpringer Science and Business Media Deutschland GmbH
Pages263-279
Number of pages17
ISBN (Print)9783031492716
DOIs
StatePublished - 2023
Event31st International Symposium on Graph Drawing and Network Visualization, GD 2023 - Palermo, Italy
Duration: Sep 20 2023Sep 22 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14465 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference31st International Symposium on Graph Drawing and Network Visualization, GD 2023
Country/TerritoryItaly
CityPalermo
Period9/20/239/22/23

Keywords

  • Dimensionality Reduction
  • Graph Visualization
  • Graph embedding
  • Local and global structures
  • Multi-dimensional Scaling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Balancing Between the Local and Global Structures (LGS) in Graph Embedding'. Together they form a unique fingerprint.

Cite this