Multi-relation graph summarization

Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization su...

Full description

Saved in:
Bibliographic Details
Main Authors: Ke, Xiangyu, Khan, Arijit, Bonchi, Francesco
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2022
Subjects:
Online Access:https://hdl.handle.net/10356/162984
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-162984
record_format dspace
spelling sg-ntu-dr.10356-1629842022-11-14T07:23:34Z Multi-relation graph summarization Ke, Xiangyu Khan, Arijit Bonchi, Francesco School of Computer Science and Engineering Engineering::Computer science and engineering Graph Summarization Multi-Relation Graph Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In this paper, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for the classic problem of lossless single-relation graph summarization. Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of k-Median clustering for the single relation solution can be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms. Ministry of Education (MOE) Arijit Khan is supported by MOE Tier 1 and Tier 2 grants RG117/19 and MOE2019T2-2-042. 2022-11-14T07:23:34Z 2022-11-14T07:23:34Z 2022 Journal Article Ke, X., Khan, A. & Bonchi, F. (2022). Multi-relation graph summarization. ACM Transactions On Knowledge Discovery From Data, 16(5), 82.1-82.30. https://dx.doi.org/10.1145/3494561 1556-4681 https://hdl.handle.net/10356/162984 10.1145/3494561 2-s2.0-85131167028 5 16 82.1 82.30 en RG117/19 MOE2019T2-2-042 ACM Transactions on Knowledge Discovery from Data © 2022 held by the owner/author(s). Publication rights licensed to ACM. All rights reserved.
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Graph Summarization
Multi-Relation Graph
spellingShingle Engineering::Computer science and engineering
Graph Summarization
Multi-Relation Graph
Ke, Xiangyu
Khan, Arijit
Bonchi, Francesco
Multi-relation graph summarization
description Graph summarization is beneficial in a wide range of applications, such as visualization, interactive and exploratory analysis, approximate query processing, reducing the on-disk storage footprint, and graph processing in modern hardware. However, the bulk of the literature on graph summarization surprisingly overlooks the possibility of having edges of different types. In this paper, we study the novel problem of producing summaries of multi-relation networks, i.e., graphs where multiple edges of different types may exist between any pair of nodes. Multi-relation graphs are an expressive model of real-world activities, in which a relation can be a topic in social networks, an interaction type in genetic networks, or a snapshot in temporal graphs. The first approach that we consider for multi-relation graph summarization is a two-step method based on summarizing each relation in isolation, and then aggregating the resulting summaries in some clever way to produce a final unique summary. In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for the classic problem of lossless single-relation graph summarization. Then, we demonstrate the shortcomings of these two-step methods, and propose holistic approaches, both approximate and heuristic algorithms, to compute a summary directly for multi-relation graphs. In particular, we prove that the approximation bound of k-Median clustering for the single relation solution can be maintained in a multi-relation graph with proper aggregation operation over adjacency matrices corresponding to its multiple relations. Experimental results and case studies (on co-authorship networks and brain networks) validate the effectiveness and efficiency of the proposed algorithms.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Ke, Xiangyu
Khan, Arijit
Bonchi, Francesco
format Article
author Ke, Xiangyu
Khan, Arijit
Bonchi, Francesco
author_sort Ke, Xiangyu
title Multi-relation graph summarization
title_short Multi-relation graph summarization
title_full Multi-relation graph summarization
title_fullStr Multi-relation graph summarization
title_full_unstemmed Multi-relation graph summarization
title_sort multi-relation graph summarization
publishDate 2022
url https://hdl.handle.net/10356/162984
_version_ 1751548490971873280