GraphMineSuite

Design Run Compare Profile

Creating high-performance graph mining algorithms made simple using set algebra

One code to rule them all

Focus on what really matters; the algorithm. You can easily switch out graph representations, datastructures and preprocessing routines.

template <class SGraph, class Set>
std::vector<Set> algorithm(const SGraph &graph)
{
    //your code
}

Easy Benchmark code setup

Express your benchmarks using our predefined benchmark kernels or write your own. Use verifiers to check the correctness of your code.

BenchmarkKernel(args, graph,
    CliqueCount<SortedSet, SetGraph>,
    CliqueCountVerifier,
    k, "SortedSet", "SortedGraph");

To Set or not to Set

Although GMS emphesis and strength lies on set algebra, we enable a non setbased design approach, too. Our provided representations offer multiple compression schemes and can be combined with neighbourhood permuters.

//Default
CSRGraph graph;
//Set-based
SortedSetGraph::FromCGraph(graph)
RoaringGraph::FromCGraph(graph)
RobinHoodGraph::FromCGraph(graph)
//Non-set-based
builder.csrToKbit(graph)
builder.csrToVarintByteBased(graph)
builder.csrToVarintWordBased(graph)

Profile your code

Profiling is directly embedded in the build pipeline and can be enabled/disabled using flags in the cmake files. GMS offers a simple API to include PAPI (hardware performance counters), which supports OpenMP.

PAPIW::INIT_PARALLEL(PAPI_L2_TCA, PAPI_L3_TCA);
#pragma omp parallel
{
    PAPIW::START();
    //your code
    PAPIW::STOP();
}
PAPIW::PRINT();

Strong Benchmark suite

GMS is build on top of GAPBS and therefore supports various graph formats and synthetic graph generators. Evaluate your code using an intuitive CLI.

$ ./triangle_count -f ../graphs/graph.el
$ ./triangle_count -g kronecker 10 --deg 64
$ ./triangle_count -g uniform 10 --deg 64

Compare against our state of the art base lines

We provide reference implementation of more than 40 baselines. Some of our variations enhance state of the art including:

- Degeneracy reordering (by up to >2x)
- Maximal clique listing (by up to >9x)
- k-clique listing (by 1.1x)
- Subgraph isomorphism (by up to 2.5x)

Publications

1. GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra

Maciej Besta, Zur Vonarburg-Shmaria, Yannick Schaffner, Leonardo Schwarz, Grzegorz Kwasniewski, Lukas Gianinazzi, Jakub Beranek, Kacper Janda, Tobias Holenstein, Sebastian Leisinger, Peter Tatkowski, Esref Ozdemir, Adrian Balla, Marcin Copik, Philipp Lindenberger, Pavel Kalvoda, Marek Konieczny, Onur Mutlu, Torsten Hoefler

arXiv:2103.03653 [cs.DC] 2021arXiv

2. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality

Maciej Besta, Armon Carigiet, Zur Vonarburg-Shmaria, Kacper Janda, Lukas Gianinazzi, Torsten Hoefler

arXiv:2008.11321 [cs.DC] 2020arXiv

3. SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems

Maciej Besta, Raghavendra Kanakagiri, Grzegorz Kwasniewski, Rachata Ausavarungnirun, Jakub Beránek, Konstantinos Kanellopoulos, Kacper Janda, Zur Vonarburg-Shmaria, Lukas Gianinazzi, Ioana Stefan, Juan Gómez Luna, Marcin Copik, Lukas Kapp-Schwoerer, Salvatore Di Girolamo, Marek Konieczny, Onur Mutlu, Torsten Hoefler

arXiv:2104.07582 [cs.AR] 2021arXiv