Efficiently Manipulating Structural Graph Clustering Under Jaccard Similarity
Chuanyu Zong, Rui Fang, Mengxiang Wang, Tao Qiu, Anzhen Zhang · 2024
Graph clustering plays a crucial role in analyzing graph data. Among various clustering techniques, Structural Graph Clustering (SCAN) stands out for its ability to not only identify clusters but also recognize hubs and outliers. Evaluating the robustness of graph clustering methods is essential, and manipulating SCAN is an effective approach for this purpose. However, the scarcity of efficient manipulation techniques for SCAN poses a significant challenge, hindering the development of robust structural graph clustering algorithms. To address this issue, we investigate the problem of efficiently manipulating SCAN by strategically inserting a maximum number of$\tau$edges to maximize the increment of the$\epsilon$-neighborhood$(\Delta N_{\epsilon}[t])$under Jaccard similarity around a given target vertex$t$. This problem termed Maximum$\epsilon$. Neighborhood (MaxN), is NP-hard and non-monotonic. To tackle this, we first develop efficient edge insertion strategies and present a basic algorithm MaxNS. Then, we propose an effective algorithm, IncreMaxNS, that incrementally calculates the vertex costs in each round. Furthermore, we explore a pruning and optimization algorithm, called pMaxNS, which uses a novel strategy to select a valid candidate vertex set based on the budget$\tau$, eliminating the need to evaluate all vertices in the graph. Finally, we conduct extensive experiments on seven real-world datasets, which demonstrate that our algorithm pMaxNS significantly improves manipulation efficiency, achieving 1-1.5 orders of magnitude speedup compared to the state-of-the-art approach, while consistently delivering high-quality results.