Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2025

Abstract

How can we efficiently identify the densest subgraph over relational graphs? Existing dense subgraph discovery (DSD) approaches assume that a relational graph H is already derived from a heterogeneous data source and they focus on efficient discovery of the densest subgraph on the materialized H. Unfortunately, materializing relational graphs can be resource-intensive, which thus limits the practical usefulness of existing algorithms over large datasets. To mitigate this, we propose a novel Summary-bAsed deNsest Subgraph discovery (SANS) system. Our unique summary-based peeling algorithm forms the core of SANS. Following the peeling paradigm, it utilizes summaries of each node's neighborhood to efficiently estimate peeling coefficients and subgraph densities at each peeling iteration and thus avoids materializing the relational graph completely. Through extensive experiments, we demonstrate the efficacy and efficiency of SANS, reaching orders of magnitude speedups compared to the conventional baselines with materialization, while consistently achieving at least 95% accuracy compared to peeling algorithms based on materialization.

Keywords

Relational Graphs, Meta-path, Densest Subgraph Discovery

Discipline

Artificial Intelligence and Robotics | Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

WWW '25: The ACM Web Conference 2025, Sydney, Australia, April 28 - May 2

First Page

4250

Last Page

4263

Identifier

10.1145/3696410.3714603

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.1145/3696410.3714603

Download

Share

COinS