Local Partition in Rich Graphs

Scott Freitas, Nan Cao, Yinglong Xia, Duen Horng (Polo) Chau, Hanghang Tong

Abstract

Traditional graph partitioning methods often overlook node metadata, leading to incomplete clusters and poor performance on sparse networks. This paper presents AttriPart, a scalable algorithm designed for "rich graphs" that integrate network topology with node attributes. By introducing a "parallel conductance" metric and the LocalProximity subgraph extraction technique, AttriPart identifies communities that are up to 1.6x denser and computes them 43x faster than state-of-the-art methods like PageRank-Nibble. The framework also includes LocalForecasting to predict community evolution in dynamic or sparse networks.

Introduction

Graph partitioning—identifying a cluster of related nodes around a specific seed—is fundamental to network analysis. However, most existing algorithms, such as the Nibble algorithm, rely almost exclusively on topology. In real-world "rich graphs," nodes are accompanied by rich metadata, such as user interests in social networks or research keywords in citation graphs. Ignoring these attributes leads to two primary issues: the failure to capture hidden relationships and the "cold-start" problem, where sparsely connected new nodes cannot be accurately partitioned using structural data alone.

Methodology

The researchers propose a three-stage framework to treat attributes as first-class citizens in the partitioning process.

1. LocalProximity

To ensure scalability, the framework first employs LocalProximity. Instead of running expensive calculations on a massive graph, it uses Random Walks with Restart (RWR) to identify a small, highly relevant subgraph around the seed node. This localized search transforms a potentially quadratic-time problem into one that scales with the size of the target cluster rather than the entire graph.

2. AttriPart and Parallel Conductance

The core of the system is AttriPart, which utilizes a novel metric called Parallel Conductance. While standard conductance measures the quality of a cut based on structural edges, parallel conductance incorporates attribute similarity weights. It seeks partitions that are cohesive both structurally and characteristically.

Conceptual model of a rich graph, integrating topology (a) and attribute similarity (b) into a unified structure (c).

3. LocalForecasting

For dynamic networks, LocalForecasting predicts community growth by calculating Jaccard similarity between node attributes. By adding "attribute edges" before partitioning, the model can identify potential community members even before physical links are established, effectively addressing the cold-start problem.

Experimental Evaluation

The approach was evaluated on three diverse real-world networks: Aminer (1.5M nodes, co-authorship), Musician (6k nodes, genre-based), and Wikipedia (237k nodes, keyword-based).

Visualization of a local partition where edge weights represent the integration of structural connectivity and attribute similarity.

Performance and Quality

  • Efficiency: AttriPart achieved a massive 43x speedup over PageRank-Nibble on the Aminer dataset, primarily due to the efficiency of the LocalProximity step.
  • Density: The resulting partitions were 1.1x to 1.6x denser than those produced by topology-only methods, indicating that the clusters are more cohesive and meaningful.
  • Predictive Accuracy: In simulations where 15% of edges were removed to simulate future states, LocalForecasting successfully recovered missing nodes and edges that baseline methods missed.

Key Insights

  • Attributes as Soft Edges: Treating attribute similarity as weighted parallel edges allows the algorithm to "see" through sparse regions of the graph where physical connections may be missing.
  • Localized Efficiency: By proving that accuracy is maintained when searching only a relevant subgraph, the authors turned a computationally prohibitive problem into a scalable solution for massive datasets.
  • Leading Indicators: Attributes often serve as leading indicators for future network growth, making them essential for predictive community detection in dynamic environments.

Conclusion and Future Work

AttriPart demonstrates that integrating node attributes significantly improves both the speed and quality of local partitioning. While the method faces challenges in extremely sparse networks without a giant connected component—as seen in the Musician dataset—it provides a robust framework for analyzing modern rich graphs. Future research will focus on validating these findings using true time-series snapshots and refining hyperparameter tuning for diverse graph types.

Summary updated

BibTeX
@inproceedings{freitas2018local,
  author = {Scott Freitas and Nan Cao and Yinglong Xia and Duen Horng (Polo) Chau and Hanghang Tong},
  title = {{Local Partition in Rich Graphs}},
  booktitle = {IEEE BigData},
  year = {2018},
  doi = {10.1109/bigdata.2018.8622227},
}
Figure