SSGC: A relaxed semi-streaming framework for Scalable Signed Graph Clustering

Résumé fourni par la source

Clustering signed networks—graphs with positive (trust) and negative (distrust) edges—is fundamental in social computing, yet existing methods remain difficult to scale. Classical spectral formulations can require O ( n 3 ) time and O ( n 2 ) memory, while tested batch graph neural-network baselines exceed available memory at larger scales. We propose SSGC , a relaxed semi-streaming framework that retains a bounded edge reservoir for selective post-stream refinement. SSGC processes edges in one pass using Top- C candidate pruning and a k × k signed sketch, then applies Selective Refinement to conflicted nodes using reservoir-based Sign-Aware Local Vote . The memory usage is O ( n + k 2 + B ) , where B is a tunable retained-edge budget. On synthetic signed stochastic block models (SSBM), SSGC with Selective Refinement achieves Adjusted Rand Index (ARI) 0.980–1.000 for k = 50 –10000, compared with ARI = 0.25 for greedy-only streaming. On Epinions (709K edges), SSGC reaches Louvain-level Disagreement (0.044 vs 0.047, p = 0.018 ) with a 36 × runtime speedup, but lower Signed Modularity ( Q s = 0.51 vs 0.71), reflecting a local-purity/global-modularity trade-off. On the 1.8B-edge Friendster throughput benchmark with synthetic signs, SSGC runs within 14GB memory at approximately 1.0M edges/sec; Birdwatch and Friendster are reported primarily as scalability studies.