Introduction
Local Graph Clustering (LGC) is a critical tool for navigating massive networks, such as social media platforms or e-commerce databases. Unlike global clustering, which partitions an entire graph, LGC identifies a cohesive community around a specific "seed" node. This local focus is computationally efficient and highly relevant for real-time queries. However, traditional LGC algorithms rely predominantly on graph topology—the physical links between nodes. This reliance is problematic because real-world graphs are often "noisy," containing spurious connections or missing vital links.
To address these issues, the authors propose LACA (Adaptive Local Clustering over Attributed Graphs). LACA is designed to seamlessly integrate node attributes into the clustering process, allowing the algorithm to "jump" over missing links when attribute similarity is high.
The Challenge of Attributed Graphs
While nodes in modern networks often possess rich attributes (e.g., user profiles or product descriptions), integrating this information into LGC remains a challenge. Existing methods typically use attributes to re-weight existing edges, which does little to help when the edges themselves are missing. Furthermore, global embedding techniques like Graph Neural Networks (GNNs), while effective at handling attributes, are often too slow for local, real-time applications where exploring the entire graph is prohibitive.
The LACA Framework
LACA's effectiveness stems from three primary technical innovations:
- Bidirectional Diffusion Distribution (BDD): Instead of simply measuring the probability of a random walk from a seed hitting a target, BDD calculates the "affinity" based on where random walks from both the seed and the target are likely to "meet." By treating attributes as potential destinations, LACA identifies clusters based on shared node "personalities" rather than just direct physical links.
- Transformed Node Attribute Matrix (TNAM): Comparing all node attributes is computationally expensive ($O(n^2)$). LACA utilizes randomized techniques, including k-truncated SVD and Orthogonal Random Features, to compress attributes into low-dimensional vectors. This reduces similarity calculations to simple dot products in a latent space, maintaining high performance even on massive datasets.
- AdaptiveDiffuse: Traditional diffusion engines often struggle with high-degree "hub" nodes, which can trap the diffusion process and slow down convergence.
AdaptiveDiffuseis a new engine that dynamically switches between greedy node-by-node updates and non-greedy matrix-vector operations. This maintains the locality of the search while drastically speeding up convergence.
Experimental Evaluation
The researchers evaluated LACA across eight diverse datasets, ranging from citation networks (Cora, PubMed) to massive web graphs like Amazon2M, which contains 2.4 million nodes and 61.9 million edges.
- Superior Accuracy: LACA achieved the top-2 best average ranks in precision across all 8 datasets, outperforming 17 competitors, including state-of-the-art embedding methods like PANE and CFANE.
- Massive Speedups: On the Amazon2M dataset, LACA was 152x faster than the best-performing competitor. It could identify a local cluster in approximately 36 seconds, whereas other high-quality methods took over an hour or failed to finish within three days.
- Robustness to Noise: In a case study on the AMiner co-author network, LACA successfully identified a cluster of researchers with matching expertise. In contrast, topology-only methods like PR-Nibble often pulled in unrelated researchers simply because they shared a common, high-degree co-author.
Theoretical Significance and Future Work
Beyond empirical success, the paper provides a formal proof (Lemma V.6) showing that LACA’s local exploration is mathematically equivalent to the smoothing process used in GNNs. This suggests that LACA offers GNN-quality clusters at a fraction of the computational cost.
A current limitation of the framework is its performance on heterophilic graphs, where connected nodes are more likely to have different attributes (e.g., a "buyer" linked to a "seller"). Because LACA assumes that nodes in a cluster should share similar attributes (homophily), its performance may degrade on these specific networks. The authors have identified the study of local clustering on heterophilic graphs as their primary direction for future research.
Summary updated