TL;DR
This paper introduces a high-performance framework for counting subgraphs (motifs) in massive networks with billions of edges. By combining a novel pipelined communication strategy with fine-grained load balancing, the authors achieved a 5x speedup and a 2x reduction in memory usage compared to previous state-of-the-art implementations, successfully scaling to complex templates with up to 15 vertices.
What Problem Does This Paper Address?
Subgraph counting—finding how many times a specific small pattern (like a "treelet") appears in a large graph—is a fundamental task in social network analysis, bioinformatics, and cybersecurity. However, it is computationally "hard" (NP-hard). As the size of the template or the main graph grows, the complexity explodes.
Existing parallel solutions often hit two walls:
- Communication Bottlenecks: When a graph is too big for one machine, it must be split. Moving data between machines to check for connections creates massive network overhead.
- Memory Footprints: Storing intermediate results for large templates can easily exceed the RAM of modern clusters.
- Load Imbalance: Real-world graphs are "skewed" (some nodes have thousands of connections, others have two). Standard parallel approaches often leave most processors idling while one struggles with a "heavy" node.
Methods
The authors build upon the color-coding technique, a randomized approximation algorithm that makes subgraph counting more manageable. Their core contributions are system-level optimizations implemented in the Harp-DAAL framework:
- Pipelined Adaptive-Group Communication: Instead of a traditional "all-to-all" communication where every machine waits for everyone else, they break communication into steps. This allows the system to "overlap" work: while one part of the data is being sent over the network, the CPU is already processing the previously received chunk.
- Adaptive Switching: The system automatically chooses between a standard all-to-all mode (for small, simple templates) and the pipelined mode (for large, complex templates) based on the "computation intensity" of the task.
- Neighbor List Partitioning: To solve the "skewed node" problem, they break down the neighbor lists of high-degree vertices into smaller, equal-sized tasks. This ensures that work is distributed evenly across all CPU threads.
Datasets
The researchers evaluated their system using a mix of massive real-world and synthetic datasets:
- Real-world: Twitter (2B edges), Friendster (5B edges), Orkut (230M edges), and others like Miami, NYC, and Sk-2005.
- Synthetic: RMAT graphs (up to 500M edges), specifically used to test how the system handles different levels of "skewness" or irregular connectivity.
- Templates: Tree-like structures (treelets) ranging from 3 to 15 vertices.
Key Insights and Ideas
- Computation vs. Communication Intensity: The authors found that the shape of a template matters as much as its size. A 12-vertex template with a specific "bushy" shape might require twice the computation of a "stringy" 12-vertex template. Their system adapts to this "intensity."
- Hiding Latency: By using a "cold start" pipeline, they effectively hide the time spent waiting for the network. By the time the first communication step finishes, the computation pipeline is full and stays busy.
- Breaking the Memory Barrier: Previous state-of-the-art tools (like MPI-Fascia) often crashed due to "Out of Memory" errors on templates larger than 12 vertices. This paper’s fine-grained partitioning allows it to process these larger templates by never holding too much intermediate data in RAM at once.
Key Results
- Speedup: The proposed "AdaptiveLB" (Load Balance) version achieved up to a 5x speedup over MPI-Fascia on large templates.
- Memory Efficiency: Peak memory utilization was reduced by a factor of 2 on large templates (12–15 vertices).
- Scalability: The system successfully processed the Friendster graph (0.66 billion vertices and 5 billion edges), a scale that many previous algorithms could not handle.
- Thread Efficiency: On highly skewed graphs, their neighbor-partitioning technique improved execution time by up to 9x compared to naive thread distribution.
Limitations and Future Work
- Template Constraints: The current work focuses primarily on "treelets" (subgraphs without cycles). While color-coding can be extended to graphs with cycles (using treewidth), this paper does not deeply explore those more complex structures.
- Future Directions: The authors suggest applying this pipelined, adaptive approach to other data-intensive irregular graph problems beyond counting, such as finding random subgraphs or more general graph mining tasks.
Reference: Chen, L., et al. (2018). High-Performance Massive Subgraph Counting using Pipelined Adaptive-Group Communication. arXiv:1804.09764v1 [cs.DC].
Summary updated