SHF: Small: High Performance Graph Pattern Mining System and Architecture

This research project aims to develop high-performance systems and architectures for graph pattern mining, which the key component for various applications, including mining biochemical structures, finding biological conserved subnetworks, finding functional modules, program control-flow analysis, intrusion network analysis, mining communication graphs, social-network analysis, anomaly detection, and mining XML structures. High-performance graph pattern mining enables fundamental scientific research advance.

The research is motivated by the need for scaling to large graphs and patterns; the significant gap between the fastest algorithm and general graph pattern mining systems; and the inefficiency in current computer architectures when executing such workloads. The project vertically advances the field by seeking synergies between algorithm, system, architecture, and hardware implementations.

The project provides research opportunities to female, minority and undergraduate students to enhance the broader participation of computer science education. In particular, the project involves non-CS major students, introducing them to graph-analytics techniques to solve problems in science and engineering.

This research takes a top-down approach, starting from algorithms and developing efficient graph pattern mining systems and architectures. Based on pattern-decomposition algorithms, it develops efficient and general system mechanisms and compiler optimizations with an accurate cost model. To support distributed graph pattern mining with partitioned graphs, it proposes the idea of breaking down pattern-enumeration algorithms to small tasks with a key abstraction, extendable embedding, and builds an efficient execution model to overlap the communication and computation.

At the architecture level, the research proposes novel instruction-set extensions and architectural components to support the stream and intersection operations. The proposed techniques will be implemented in two hardware prototypes: (1) a RISC-V processor with an instruction-set extension for stream and intersection operations; and (2) a distributed FPGA accelerator for graph pattern mining with extendable embedding as the primitive.

The research outcomes will be published in top system and architecture conferences. The project will deliver several open-source graph pattern mining systems, architecture simulators and hardware prototypes.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.