Triangle Counting on Large Graphs
Open AccessTriangle counting is a fundamental graph algorithm. It is also used in a wide range of applications such as thematic structures, link recommendation, social network analysis, spam detection, and e-commerce. In addition, it is used as a building block in other graph related problems, such as graph isomorphism (subgraph matching), k-truss, and clustering coefficient. Various triangle counting algorithms are studied for decades. However, the conventional algorithms are designed for sequential execution and have difficulties to scale to high volume of parallelism device such as GPUs or distributed systems. Since the worst case time complexity of this algorithm is high, it takes a long time to execute for big graphs. Also, as graph size increases, external execution takes a large amount of disk I/O operations which as a result is slow. Existing solutions face several drawbacks of suboptimal I/O complexity, limited parallelism, and low scalability.My dissertation research strives to provide high performance solutions of fast triangle counting on big graphs. We identify the most emerging needs for fast triangle counting on large graphs which are two folds. First, scalable parallel triangle counting algorithm designed for GPUs and distributed systems is a key for fast processing on large graphs. Second, external memory algorithm to minimize disk I/Os for the graphs larger than memory size is also important for many large datasets. As a consequence, my dissertation research aims to solve the challenges described above. My first project TriCore is a new GPU based high-performance and scalable triangle counting system that consists of three main techniques. First, we designed a binary search based counting algorithm that tremendously increases both thread parallelism and memory performance. Second, TriCore exploits a 2-D partition method to distribute the CSR representation across multiple GPUs, combined with a new streaming buffer to load the edge list from outside of GPUs. Third, we developed a dynamic workload management technique to balance the workload across multiple GPUs. Our evaluation demonstrates TriCore is 22 times faster than the state-of-the-art parallel triangle counting projects. In addition, TriCore can not only process big graphs that are significant larger than the memory size of one GPU but also achieve 24 times speedup when scaling to 32 GPUs.My second project, TriP, is a set of graph partitioning algorithms for external-memory based triangle counting. Exploring 1-D vertical and 2-D partitioning approaches, we have designed novel, practical algorithms to deliver high parallelism and optimal I/O complexity while satisfying the memory bound. Our experiments shows that TriP is able to achieve 15.8 times speedup over the state-of-the-art sequential implementation, and 6.7 times over state-of-the-art parallel implementation, benefited from 1.3 times lower I/O scaling rate and over 6 times average improvement in computation time.My third project TriX is a scalable triangle counting framework, which is comprised of a 2-D graph partition strategy and a binary search based intersection algorithm designed for GPUs. The DARPA Graph Challenge seeks a scalable solution for triangle counting on big graphs. The 2-D partition provides balanced work division among multiple GPUs. On the other hand, binary search based intersection achieves fine-grained parallelism on GPUs via intra-warp scheduling and coalesced memory access. TriX is able to scale to a large number of GPUs, and count triangles on billion-node graph (2 billion node, 64 billion edges) within 35 minutes, achieving over 16 million traverse edges per second (TEPS).In conclusion, my research has focused on triangle counting algorithms on large graphs. I design a GPU-based triangle counting algorithm for efficient parallel computation, an external memory algorithm to enable large graphs to be processed with good I/O complexity, and combine these two algorithms to develop a highly scalable and distributed solution. My future work will focus on related graph algorithms and hardware-software co-design to develop high performance solutions in Artificial Intelligence fields.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.