Subgraph Listing

Application Description

This benchmark finds subgraphs of a given pattern in an undirected graph. The pattern is an arbitrary subgraph.

Algorithm

The algorithm is called extend-reduce. A initial worklist contains initial embedding (single vertex or edge). It extends each embedding with a vertex, and insert the new embeddings to the next worklist. Extension is repeated until the size of embedding is the same as the pattern. Each embedding is compared to the pattern, and if it is isomorphic to the pattern, the counter is increased by 1. The isomorphism test is avoided when a macthing order is used.

Performance

Please read the following paper for detailed performance evaluation:

(VLDB 2020) [PDF] [Code]
Xuhao Chen, Roshan Dathathri, Gurbinder Gill, Keshav Pingali,
Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU,
PVLDB, 13(8): 1190-1205, 2020