Measuring distances among graphs en route to graph clustering

Ivan Kyosev, Iulia Paun, Yashar Moshfeghi, Nikos Ntarmos

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

1 Downloads (Pure)

Abstract

The graph data structure offers a highly expressive way of representing many real-world constructs such as social networks, chemical compounds, the world wide web, street maps, etc. In essence, any collection of entities and the relationships between them can be modelled using a graph, thus preserving more information about the real-world objects than a simple vector space model. An issue that arises when operating on collections of graphs, however, is that most statistical analysis and machine learning methods expect their input data to be in the form of multidimensional vectors, where all items can be compared with each other using well-understood metrics such as Euclidean or Manhattan distance. This paper presents a variety of approaches for computing distances between graphs with known node correspondence, with the aim of applying those measures alongside clustering algorithms to discover patterns in a given dataset. The performance of each distance measure is then evaluated through its ability to identify communities of graphs with similar features. We show that because the considered distance metrics highlight different structural properties, the method that produces the highest quality result will depend on the characteristics of the processed graph population.

Original languageEnglish
Title of host publication2020 IEEE International Conference on Big Data
EditorsXintao Wu, Chris Jermaine, Li Xiong, Xiaohua Tony Hu, Olivera Kotevska, Siyuan Lu, Weijia Xu, Srinivas Aluru, Chengxiang Zhai, Eyhab Al-Masri, Zhiyuan Chen, Jeff Saltz
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages3632-3641
Number of pages10
ISBN (Electronic)9781728162515
DOIs
Publication statusPublished - 19 Mar 2021
Event8th IEEE International Conference on Big Data, Big Data 2020 - Virtual, Atlanta, United States
Duration: 10 Dec 202013 Dec 2020

Conference

Conference8th IEEE International Conference on Big Data, Big Data 2020
CountryUnited States
CityVirtual, Atlanta
Period10/12/2013/12/20

Keywords

  • graph clustering
  • graph distance
  • graph mining

Fingerprint Dive into the research topics of 'Measuring distances among graphs en route to graph clustering'. Together they form a unique fingerprint.

Cite this