PhD Dissertation Defense by NIU Yudong | Community Discovery over Attributed Graphs

ABOUT THE TALK

Community discovery finds applications in various domains such as system optimization and fraud detection. Although many efforts have been made to address community discovery based on graph topology, few works have considered node or edge attributes for community discovery. Thus, this thesis is devoted to designing innovative solutions for community discovery over both homogeneous and heterogeneous attributed graphs and discovering communities that satisfy requirements from various downstream applications. 

First, we examine community search over homogeneous attributed graphs and propose an index-free approach based on “sweep” over attribute-related personalized page-rank (PPR) vector, where the PPR vector is computed over a weighted graph generated by reweighting each edge according to the number of query-aware motifs containing the edge. Results show that our proposal achieves upto 90% relative improvement on F1-scores while consuming 10x fewer memory than baselines. 

Second, we investigate the problem of characteristic community discovery, which aims at finding the largest community where the query node is top-k influential from a set of hierarchical communities. We propose the local reclustering technique to obtain query attributes related hierarchical communities and compressed influence estimation to evaluate the influence rank of the query node across corresponding hierarchical communities efficiently. In experiments, our proposal discovers larger and better characteristic communities than baselines while achieving upto 25x speedups. 

Finally, we study community discovery over heterogeneous graphs and formulate the densest subgraph discovery (DSD) problem over relational graphs induced by meta-paths. We propose the sketch-based peeling algorithm to avoid the time-consuming relational graph materialization and devise a novel system through which users can implement the sketch-based peeling algorithm for DSD based on different density objectives. A case study on real-world heterogeneous data from Grab demonstrates that our sketch-based methods achieve 97.55% precision for fraud detection.

ABOUT THE SPEAKER

NIU Yudong is a PhD candidate in Computer Science, focusing his research primarily on graph processing. In particular, he is interested in community discovery, graph sketches and LLM for graphs. 

Before joining SMU, Yudong obtained his Bachelor's degree in Computer Science from Wuhan University. He attended ICDE in 2022 and 2024 and made presentations in these conferences. He likes playing go, reading movies in his leisure time.