Scalable Triadic Analysis of Large-Scale Graphs: Multi-Core vs. Multi- Processor vs. Multi-Threaded Shared Memory Architectures

George Chin Jr., Andrès Márquez, Sutanay Choudhury, John FeoSBAC-PAD 2012 · OpenReview

TL;DR

This paper tackles the challenge of performing triadic analysis (counting specific three-node subgraphs) on massive, real-world graphs, which current algorithms struggle with. The authors developed and optimized a parallel triad census algorithm for shared-memory architectures and evaluated its performance across three distinct systems: the Cray XMT, HP Superdome, and an AMD multi-core NUMA machine, providing valuable insights into their scalability.

What Problem Does This Paper Address?

Analyzing large-scale graphs is crucial in many fields, from social sciences to cybersecurity. A common analysis is "triadic analysis," which focuses on understanding relationships within groups of three nodes (triads). This often involves calculating a "triad census" – a count of all possible three-node subgraph configurations. However, as graphs grow to millions or even billions of nodes and edges, existing triadic census algorithms become computationally prohibitive, failing to scale effectively. This paper aims to bridge this gap by developing and evaluating a highly scalable parallel triad census algorithm specifically designed for shared-memory architectures, which are common in high-performance computing.

Methods

The core of this paper is the development and optimization of a parallel triad census algorithm. The authors chose to parallelize the subquadratic algorithm by Batagelj and Mrvar [13], which has a computational complexity of O(m) (where m is the number of edges), making it suitable for large, sparse graphs. Key optimizations include:

  • Compact Data Structure: A novel representation of the graph using a compact data structure that stores edges in a single array. This structure uses two bits per edge to encode direction (unidirectional, bidirectional), effectively creating a compressed sparse row format. This improves spatial locality and enables efficient edge traversal.
  • Optimized Neighbor Traversal: Instead of explicitly generating union sets, the algorithm uses two pointers to traverse sorted neighbor arrays of nodes u and v to efficiently identify the third node w of a triad. This strategy is crucial for maintaining performance on large graphs.
  • Local Triad Census Vectors: To mitigate memory hotspotting and contention from incrementing a single global census vector, the authors implemented 64 local triad census vectors. These are later summed to produce the final census, distributing the load.
  • Shared Memory Architectures: The algorithm is designed for shared-memory systems, leveraging their capabilities for parallel execution.

Datasets

The authors evaluated their algorithm on three large, real-world, scale-free graphs:

  • US Patent Datasets: A citation network with 37.8 million nodes and 16.5 million edges, exhibiting a power-law exponent of 3.126.
  • Orkut Network: A social networking dataset with 3.1 million nodes and 234.4 million edges, with a power-law exponent of 2.127.
  • Web Graph: A portion of the .uk domain Web graph with 105.2 million nodes and 2.5 billion edges, and a power-law exponent of 1.516.

These datasets are representative of the large-scale, scale-free graphs commonly encountered in various domains.

Key Insights and Ideas

  • Shared Memory Scalability Varies Greatly: The performance of parallel graph algorithms on shared-memory systems is highly dependent on the specific architecture's ability to manage parallelism and memory access.
  • Cray XMT's Strength in Massive Concurrency: The Cray XMT, with its massive hardware multithreading, excels at exploiting fine-grained parallelism, especially as the number of processors increases. It can effectively hide memory latency through thread switching.
  • NUMA and Superdome Excel at Lower Concurrency: For smaller numbers of cores/threads, NUMA and Superdome architectures can outperform the XMT due to their efficient on-node memory access and architectural advantages.
  • Memory Bandwidth is a Bottleneck: As the number of threads/cores increases, the memory systems of NUMA and Superdome architectures become a bottleneck, leading to performance degradation. The XMT's architecture is less susceptible to this issue at higher thread counts.
  • Algorithm Design is Crucial for Locality: The compact data structure and optimized traversal strategy are critical for achieving good spatial locality and enabling efficient parallel execution on shared-memory systems.

Key Results

  • The optimized parallel triad census algorithm achieved high CPU utilization (60-70%) on the Cray XMT, significantly outperforming previous implementations.
  • On the Orkut network, the NUMA machine showed superior performance at lower core counts, but its performance degraded as more cores were utilized, crossing execution time thresholds with the XMT around 36 processors.
  • The Superdome also outperformed the XMT at lower core counts but experienced degradation at cabinet boundaries.
  • The Cray XMT demonstrated superior scaling performance, eventually outperforming both NUMA and Superdome as processor counts increased, particularly on the massive Webgraph dataset.
  • The algorithm achieved good linear speedup on the Cray XMT for the Webgraph dataset, scaling from 64 to 512 processors.

Limitations and Future Work

  • Limited Scope of Architectures: The study focused on three specific shared-memory architectures. Further evaluation on a wider range of systems would be beneficial.
  • Scheduling Policy Impact: While the paper notes the importance of scheduling policies (e.g., "dynamic" vs. "guided"), a more in-depth analysis of their impact across different architectures could be valuable.
  • Dynamic Data Access Patterns: The authors acknowledge that graph algorithms often have unpredictable data access patterns, limiting the effectiveness of static prefetching. Future work could explore adaptive prefetching or other techniques to mitigate this.
  • Further Optimization: While significant optimizations were made, there's always room for further improvements, especially in areas like memory access patterns and inter-processor communication for distributed-memory systems.
  • Broader Application: The authors suggest that the developed algorithm and optimization techniques are applicable to other graph mining algorithms and could be extended to distributed-memory environments.

Summary updated

Abstract

Triadic analysis encompasses a useful set of graph mining methods that are centered on the concept of a triad, which is a subgraph of three nodes. Such methods are often applied in the social sciences as well as many other diverse fields. Triadic methods commonly operate on a triad census that counts the number of triads of every possible edge configuration in a graph. Like other graph algorithms, triadic census algorithms do not scale well when graphs reach tens of millions to billions of nodes. To enable the triadic analysis of large-scale graphs, we developed and optimized a triad census algorithm to efficiently execute on shared memory architectures. We then conducted performance evaluations of the parallel triad census algorithm on three specific systems: Cray XMT, HP Superdome, and AMD multi-core NUMA machine. These three systems have shared memory architectures but with markedly different hardware capabilities to manage parallelism.
BibTeX
@inproceedings{jr2012scalable,
  author = {George Chin Jr. and Andrès Márquez and Sutanay Choudhury and John Feo},
  title = {{Scalable Triadic Analysis of Large-Scale Graphs: Multi-Core vs. Multi- Processor vs. Multi-Threaded Shared Memory Architectures}},
  booktitle = {SBAC-PAD},
  year = {2012},
  url = {https://openreview.net/forum?id=NSYtCplDLv},
}
Figure