Efficient Subgraph Mining And Discovery On Massive Graphs

Abstract:

Graphs are powerful tools for modeling complex relationships across a wide range of domains, from social networks and biological systems to financial transaction networks. Among various graph analysis tasks, subgraph finding plays a crucial role in uncovering structural patterns and supporting applications such as fraud detection, community analysis, and recommendation systems.

As graphs grow in size and complexity, efficient subgraph detection faces several challenges. First, general graph mining methods often suffer from high computational overhead and poor scalability due to the exponential growth of the search space. Second, many systems overlook temporal dynamics, treating all edges equally without considering that recent interactions often carry more importance in dynamic environments. Third, node attributes are frequently ignored, limiting the ability of existing methods to capture meaningful semantics in real-world applications.

To address these challenges, this thesis proposes three key solutions. We first introduce BLITZ, a high-performance graph pattern mining system built on the gDAG model. It unifies diverse mining paradigms and employs optimized strategies for significant efficiency gains. BLITZ achieved speedups of two orders of magnitude over other graph pattern mining systems for Frequent Subgraph Mining (FSM) tasks. Next, we present RUSH, a real-time burst subgraph detection framework that incorporates temporal awareness to capture rapid structural changes in dynamic graphs, enabling timely fraud detection. RUSH outperformed existing systems in updating time by one order of magnitude on average. Finally, we propose LouvainX, a scalable and distributed community detection system that extends the Louvain algorithm. It integrates attribute-based modularity and supports distributed computation, enabling efficient detection on billion-scale graphs. LouvainX consistently outperformed existing state-of-the-art methods in both accuracy and runtime efficiency.

Together, these contributions advance the field of subgraph finding by offering efficient, temporal-aware, and attribute-enhanced techniques suitable for both static and dynamic graph analytics in real-world, large-scale settings.