TL;DR
This paper introduces a novel algorithm for local graph clustering that effectively combines graph structure with node attributes. It provides theoretical guarantees for recovering target clusters and demonstrates improved performance over methods that ignore attributes, especially in noisy or sparse graph settings.
What Problem Does This Paper Address?
In today's data-rich world, graphs often come with rich node attributes (like user profiles, item descriptions, or gene annotations) in addition to their structural connections. Traditional local graph clustering algorithms, which aim to find small clusters around a "seed" node without processing the entire graph, have largely ignored these valuable attributes. This is a significant limitation, as attributes can provide crucial information for identifying meaningful clusters, especially when the graph structure itself is noisy or sparse. The authors aim to bridge this gap by developing a local clustering algorithm that leverages both structural and attribute information and provides theoretical assurances of its effectiveness.
Methods
The core of the proposed method is an extension of the "flow diffusion" algorithm, a technique previously used for local graph clustering on attribute-less graphs. The key innovation is to reweight the edges of the graph based on the similarity of node attributes. Specifically, they use a Gaussian kernel to measure attribute similarity: edges connecting nodes with similar attributes are given higher weights, making it easier for "mass" to flow between them. This reweighted graph is then used in the flow diffusion process.
The algorithm works by:
- Constructing a reweighted graph: Edge weights $w_{ij}$ are modified to $w'_{ij} = w_{ij} \exp(-\gamma ||X_i - X_j||^2)$, where $w_{ij}$ is the original edge weight, $X_i$ and $X_j$ are node attributes, and $\gamma$ is a hyperparameter controlling the influence of attributes.
- Running flow diffusion: A source mass is injected at a seed node, and a sink capacity is defined for nodes. The flow diffusion process then spreads this mass through the reweighted graph.
- Identifying the cluster: The cluster is formed by the set of nodes that receive a significant amount of mass (i.e., the support of the solution vector $x^*$).
The authors also provide theoretical guarantees for their algorithm under a "contextual random graph model," which is a general framework for generating graphs with attributes. They derive conditions under which the algorithm can accurately recover a target cluster, with performance depending on the signal-to-noise ratio of the attributes and the graph structure.
Datasets
The paper evaluates its algorithm on:
- Synthetic data: Generated using a contextual random graph model, allowing for controlled variations in graph structure and attribute signal strength.
- Real-world co-authorship networks: Two datasets from the Microsoft Academic Graph (KDD Cup 2016 challenge), one for Computer Science and one for Physics. Nodes are authors, edges represent co-authorship, and attributes are paper keywords.
- Amazon co-purchase graph: A segment of this graph where nodes are products, edges indicate co-purchase, and attributes are bag-of-words encoded product reviews.
- Orkut online social network: A large social network dataset used to evaluate scalability and performance on a massive graph.
Key Insights and Ideas
- Attributes are crucial for local clustering: The paper strongly demonstrates that incorporating node attributes significantly improves local graph clustering performance, especially when the graph structure alone is insufficient.
- Weighted flow diffusion elegantly combines information: The reweighting mechanism provides a principled way to integrate attribute similarity into the existing flow diffusion framework, guiding the mass flow towards more relevant nodes.
- Theoretical guarantees are possible: The authors provide rigorous statistical guarantees, showing that their algorithm can recover target clusters under specific conditions related to attribute signal strength and graph connectivity. This is a significant contribution, as provable guarantees for local clustering with attributes are rare.
- Attribute signal strength matters: The performance gains are directly tied to how informative the node attributes are. When attributes are strong and distinguishable, the algorithm excels. When attributes are weak or noisy, the graph structure plays a more dominant role, and the benefits are reduced.
- Local nature is preserved: The algorithm remains "local," meaning it doesn't need to process the entire graph, making it scalable to very large networks.
Key Results
- Synthetic Data: Experiments show that the weighted flow diffusion algorithm can achieve near-perfect recovery of target clusters when node attributes have a strong signal, significantly outperforming methods that ignore attributes. The required attribute signal strength for good performance is shown to depend on the graph's structural properties.
- Real-world Co-authorship Networks: Incorporating node attributes improved the F1 score by an average of 4.3% across 20 clusters in two co-authorship networks.
- Amazon Co-purchase Graph: While the attribute signal was weaker in this dataset, node attributes still provided a small but consistent improvement in F1 scores.
- Orkut Social Network: On a large online social network, weighted flow diffusion achieved significantly higher F1 scores compared to unweighted flow diffusion, with performance increasing as attribute strength increased.
- Comparison with Global Methods: On synthetic data, the proposed local method (WFD) achieved competitive or superior F1 scores compared to global methods (like spectral clustering) when attributes were informative, while maintaining its local nature.
Limitations and Future Work
- Hyperparameter Tuning: While the algorithm is described as having few hyperparameters, the choice of $\gamma$ (controlling attribute influence) and the source mass $\Delta_s$ can impact performance. The paper suggests that a rough estimate of the target cluster size is sufficient for setting $\Delta_s$.
- Attribute Noise: The theoretical guarantees rely on assumptions about the signal-to-noise ratio of attributes. When attributes are very noisy, their benefit might be limited or even detrimental.
- Future Work: The authors suggest incorporating node embedding and learning the relative importance of attributes and structural information simultaneously within the local diffusion process. They also mention extending the algorithm to directed graphs and exploring other similarity metrics for node attributes.
Summary updated