Abstract
Subgraph counting aims to count the number of occurrences of a subgraph $T$ (template) in a given graph $G$. This problem is computationally challenging, with complexity growing as a function of both $T$ and $G$. Recent applications require solving these problems on massive networks with billions of vertices. This paper presents several system-level strategies to substantially improve performance in massive subgraph counting. We propose: 1) a novel pipelined Adaptive-Group communication pattern to improve inter-node scalability, 2) a fine-grained pipeline design to reduce the memory space of intermediate results, and 3) partitioning neighbor lists of subgraph vertices to achieve better thread concurrency and workload balance. Experimentation on an Intel Xeon E5 cluster shows that our implementation achieves a 5x speedup and reduces peak memory utilization by a factor of 2 on large templates (12 to 15 vertices) and input graphs with up to 5 billion edges.
Introduction
Subgraph counting—identifying the frequency of specific small patterns or "motifs" within a large graph—is a foundational task in social network analysis, bioinformatics, and cybersecurity. However, the problem is NP-hard, and as the size of the template or the target graph increases, the computational requirements explode.
Existing parallel solutions typically encounter three major bottlenecks:
- Communication Overhead: Large graphs must be partitioned across multiple machines, leading to massive network traffic during connectivity checks.
- Memory Constraints: Storing intermediate results for complex templates often exceeds the available RAM in modern clusters.
- Load Imbalance: Real-world graphs are often highly skewed, with a few high-degree nodes causing most processors to idle while one struggles with a "heavy" vertex.
Methodology
The framework builds upon the color-coding technique, a randomized approximation algorithm. The core algorithmic approach involves partitioning the template into smaller components and counting colorful embeddings.
To address the system-level bottlenecks, the authors implemented several optimizations within the Harp-DAAL framework:
Pipelined Adaptive-Group Communication
Instead of traditional "all-to-all" communication where nodes wait for a global synchronization, the system breaks communication into discrete steps. This allows for the overlapping of computation and communication; while one data chunk is being transmitted, the CPU processes the previously received chunk. The system adaptively switches between standard all-to-all mode for simple templates and this pipelined mode for high-intensity tasks.
Fine-Grained Load Balancing
To mitigate the "skewed node" problem, the system employs neighbor list partitioning. By breaking down the neighbor lists of high-degree vertices into smaller, equal-sized tasks, the workload is distributed evenly across all available CPU threads, preventing idle time.
Experimental Evaluation
The system was evaluated using massive real-world datasets, including Twitter (2B edges) and Friendster (5B edges), alongside synthetic RMAT graphs to test various levels of connectivity skewness. The templates used were tree-like structures (treelets) ranging from 3 to 15 vertices.
Key Results
- Performance: The "AdaptiveLB" (Load Balance) version achieved up to a 5x speedup over state-of-the-art tools like MPI-Fascia.
- Memory Efficiency: Peak memory utilization was reduced by 50% on large templates (12–15 vertices), allowing the system to process complex structures that previously caused out-of-memory errors.
- Scalability: The system successfully handled the Friendster graph (5 billion edges), a scale beyond the reach of many previous algorithms.
- Thread Efficiency: Neighbor-partitioning improved execution time by up to 9x on highly skewed graphs compared to naive thread distribution.
Conclusion
This work demonstrates that combining algorithmic approximations like color-coding with system-level pipelining and adaptive load balancing can significantly push the boundaries of subgraph counting. While the current focus is on treelets (subgraphs without cycles), the pipelined approach offers a robust foundation for future extensions into more general graph mining tasks and templates with cycles.
Reference: Chen, L., et al. (2018). High-Performance Massive Subgraph Counting using Pipelined Adaptive-Group Communication. arXiv:1804.09764v1 [cs.DC].
Summary updated