Please note: This PhD seminar will take place online.
Shenghao Yang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Kimon Fountoulakis
The growing interest in machine learning problems over graphs with additional node information such as texts, images, or labels has popularized methods that require the costly operation of processing the entire graph. Yet, little effort has been made to the development of fast local methods (i.e., without accessing the entire graph) that extract useful information from such data.
In this talk, I will introduce two closely related local graph clustering methods for modern graph datasets. The first applies to attributed graphs, and the second applies to a more general setting where we use noisy node labels (e.g., output of a classification oracle which takes input raw features and generates binary predictions) as a proxy for additional node information of any kind (e.g., texts, images). In the latter setting, nodes receive initial binary labels based on cluster affiliation: 1 if they belong to the target cluster and 0 otherwise. Subsequently, a fraction of these labels is flipped. For both cases, we investigate the benefits of incorporating additional node information for local graph clustering. By constructing a weighted graph using either node attributes or noisy node labels, we study the performance of graph diffusion-based local clustering method on both the original and the weighted graphs.
From a theoretical perspective, we consider recovering an unknown target cluster with a single seed node in a random graph. We provide sufficient conditions on node-level signal under which, with high probability, using diffusion in the weighted graph yields a more accurate recovery of the target cluster. Empirically, this approach proves much more effective than traditional methods. We show that reliable node labels can be obtained with just a few samples from an attributed graph. Moreover, utilizing these labels via diffusion in the weighted graph leads to significantly better local clustering performance across several real-world datasets, improving F1 scores by up to 13%.
Based on the following papers —
- Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees, S. Yang and K. Fountoulakis. ICML 2023.
- Local Graph Clustering with Noisy Labels, A. de Luca, K. Fountoulakis, S. Yang. ICLR 2024.