A sketch propagation framework for hub queries on unmaterialized relational graphs

Publication Type

Conference Proceeding Article

Publication Date

5-2025

Abstract

Relational graphs encapsulate nontrivial inherent interactions among entities in heterogeneous data sources. Iden-tifying hubs in relational graphs is vital in various applications such as fraud detection, influence analysis, and protein complex discovery. However, building relational graphs induced by meta-paths on heterogeneous data entails substantial costs, thus hin-dering efficient hub discovery. In this paper, we propose a novel sketch propagation framework for approximate hub queries in induced relational graphs that avoids explicitly materializing those graphs. Our framework specifically supports hub queries that ask for all nodes whose centrality scores, based on degree or h-index, are in the top quantile with provable guarantees under the notion of ∊-separable sets. In addition, we devise pruning techniques that efficiently process personalized hub queries asking whether a given node is a hub. Extensive experiments on real-world and synthetic data confirm the efficacy and efficiency of our proposals, which achieve orders of magnitude speed-ups over exact methods while consistently attaining accuracy beyond 90%.

Keywords

hub query, relational graph, degree centrality, h-index, KMV sketch

Discipline

Artificial Intelligence and Robotics | Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 2025 IEEE 41st International Conference on Data Engineering (ICDE), Hong Kong, May 19-23

ISBN

9798331536046

Identifier

10.1109/ICDE65448.2025.00225

Publisher

IEEE

City or Country

Piscataway, NJ

Additional URL

https://doi.org/10.1109/ICDE65448.2025.00225

This document is currently not available here.

Share

COinS