TL;DR
This paper introduces AttriPart, a scalable algorithm for local graph partitioning that leverages both network topology and node attributes to identify dense communities around a specific seed node. By combining these two data sources into a novel "parallel conductance" metric and utilizing a fast subgraph extraction technique, the authors achieve up to 1.6x denser partitions while running 43x faster than traditional methods like PageRank-Nibble.
What Problem Does This Paper Address?
Graph partitioning is the bread and butter of network analysis, helping us find "communities"—groups of nodes like people in a social network or proteins in a cell that are more connected to each other than to the rest of the graph. Traditional local partitioning focuses on finding a cluster around a specific "seed" node without needing to process the entire massive graph.
However, most existing algorithms only look at the structure (who is connected to whom). They ignore the attributes (the "rich" data, like a person's interests or a protein's function). Ignoring this data leads to two problems:
- Missed Context: Two nodes might be connected but have nothing in common, or they might be highly similar but not yet connected.
- Scalability: Even "local" algorithms can be slow on massive graphs if they don't efficiently narrow their search space.
Methods
The authors propose a three-step framework to solve these issues:
- The Rich Graph Model: They define three layers: a structure graph $G$, an attribute graph $A$ (where edge weights represent Jaccard similarity of node attributes), and a combined graph $B$ that merges both. Example of the three graph models: structure, attribute, and combined.
- Parallel Conductance: Traditional conductance measures how "leaky" a cluster is by comparing internal edges to external ones. The authors introduce a Parallel Conductance metric that weights these edges based on attribute similarity, ensuring that a "good" cluster is both structurally tight and attribute-consistent. A toy example calculating the parallel cut and conductance.
- The Algorithms:
- LocalProximity: A preprocessing step that uses Random Walks with Restart (RWR) to quickly extract a small, relevant subgraph around the seed node. This drastically reduces the computational load for the next steps.
- AttriPart: The core partitioning algorithm that runs on the extracted subgraph, using PageRank and the parallel conductance metric to find the optimal cluster.
- LocalForecasting: An extension that uses "Expanded Neighborhoods" (predicting future links based on attribute similarity) to guess how a community might grow over time, particularly useful for "cold-start" nodes with few initial connections.
Datasets
The algorithms were evaluated on three real-world undirected networks:
- Aminer: A large co-authorship network (1.5M nodes, 4.2M edges) where node attributes are paper keywords.
- Musician: A network of musicians who played in the same band (6k nodes), with music genres as attributes.
- Wikipedia: A subset of Wikipedia entries (237k nodes) where edges are hyperlinks and attributes are abstract keywords.
Key Insights and Ideas
-
The Power of the Subgraph: The authors found that random walk counts follow a scale-free distribution (a long tail). By only keeping nodes that appear significantly more often than the average in a random walk, they can discard the vast majority of the graph without losing the local community structure. Distribution of node walk counts showing the scale-free nature.
-
Attributes as "Hidden" Edges: In the
LocalForecastingtask, treating high attribute similarity as a "potential edge" allowed the model to accurately predict community membership even when 15% of structural edges were missing. - Efficiency via Truncation: By combining subgraph extraction with PageRank truncation (ignoring nodes with very low rank scores), the algorithm achieves massive speedups without sacrificing the "density" of the resulting cluster.
Key Results
- Speed: AttriPart is approximately 43x faster than the standard PageRank-Nibble algorithm.
- Density: The partitions found by AttriPart were 1.1x to 1.6x denser than those found by structure-only methods.
- Scalability: The algorithm's runtime scales nearly independently of the total graph size because it focuses so effectively on the local neighborhood.
- Real-world Deployment: The system is not just theoretical; it is deployed on the PathFinder web platform, providing real-time interactive graph mining. Close-up of the AttriPart algorithm on the PathFinder web platform.
Limitations and Future Work
The authors noted that the Musician dataset performed less effectively in the forecasting task. They attribute this to the dataset's extreme sparsity and the lack of a "giant connected component," which makes it harder for random walks to capture meaningful proximity.
Future work could involve exploring different similarity metrics beyond Jaccard similarity for the attribute graph or adapting the framework for directed or multi-partite graphs. Additionally, while LocalForecasting helps with cold-start nodes, extremely isolated nodes with no attributes would still pose a significant challenge for this approach.
Summary updated