Graph pattern matching (GPM) aims to find subgraphs isomorphic to user-specified patterns within a large graph. Due to its ability to reveal potential relationships among entities in complex networks, it is widely applied in various fields, such as mining molecular structures in bioinformatics, detecting fraud in cloud-based e-commerce, and querying knowledge graphs in large language model. The explosion of data brought by the AI era has rendered traditional GPM systems inadequate for real-world needs. Due to the intricate data dependencies of GPM tasks, most SOTA GPM systems currently have limited scalability and performance, they perform well in small graph mining with single node but cannot scale to modern clusters with GPU acceleration. This paper introduces JUPITER, the first system capable of matching patterns on large graph across multi-node GPU clusters, which can handle graphs 10 times larger than SOTAs with the same memory resources. Its core principle is to delegate computation to the data-residing processing unit rather than pulling data to the computation location, which greatly improves communication efficiency. Experimental results show that JUPITER can reduce communication volume by two orders of magnitude compared to SOTA subgraph matching systems, achieving up to 120× speedup and an average of 21.5× speedup.

Graph Pattern Mining (GPM) has made significant progress in recent years, supporting a range of big data applications. However, GPM applications are memory-intensive as they require a tremendous amount of edge checking, which involves enumerating all possible vertex pairs and checking their connectivity or counting the common neighbors of each pair. Adjacent list or CSR format is widely used in recent GPM systems to overcome the sparsity of real-world graph, at the cost of sacrificing the ability to query the connectivity of two vertices in O(1) compared with the raw adjacent matrix. In this paper, we rethink the format to store graph in GPM systems, by partial "restoring" graph from CSR to adjacent matrix, we can significantly accelerate checking connectivity or counting common neighbors for GPM algorithms. However, directly storing graph in adjacent matrix is cost-prohibitive, thus we propose GLumin, by selectively constructing a lookup table (LUT) at the runtime, which holds the connectivity that can be repeatedly retrieved at low cost. The LUTs are compressed and tailored to fit the hierarchical memory architecture like shared memory of GPU or cache of CPU. We adopt GLumin technique to several SOTA GPM systems like AutoMine, G2Miner and GraphFold, bringing two orders of magnitude speedup to them on more than 100 different graphs and 24 patterns, demonstrating the general applicability and significance of our methods.

Graph pattern matching (GPM) is essential in fields like circuit logic synthesis, anomaly detection, social network analysis, cheminformatics, recommendation systems, and classification systems. Its NP-completeness and the irregular nature of graph data make scaling to distributed systems challenging, especially for complex supercomputers. Although utilizing architecture-specific optimization can improve the performance of Graph Pattern Matching on large-scale data, such ad-hoc solution lacks performance portability that not only causes vendor lock-in but also complicates the parallel evolution of GPM software with hardware architectures. This paper proposes Cosmos, a domain-specific software distributed shared memory model (DSM) that shields diversity of supercomputers from users and developers, achieving both performance portability and performance. This approach enables the same code scaling to thousands of nodes across different supercomputers while maintaining performance comparable to manually optimized versions.