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. To that end,
we propose a study of local graph clustering using noisy node labels as a proxy
for additional node information. In this 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. We
investigate the benefits of incorporating noisy labels for local graph
clustering. By constructing a weighted graph with such 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
with independent noisy node labels. We provide sufficient conditions on the
label noise under which, with high probability, using diffusion in the weighted
graph yields a more accurate recovery of the target cluster. This approach
proves more effective than using the given labels alone or using diffusion in
the label-free original graph. Empirically, 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%.

通过使用噪声节点标签作为附加节点信息的替代，本研究提出了一种对局部图进行聚类的方法。实验证明，使用加权图中的扩散操作可以显著提高局部聚类的性能。