In this work, we introduce the quark decomposition framework to find motif-driven subgraphs in networks with directed edges and categorical attributes on nodes/edges.
Our framework builds subgraphs, called quarks, in varying quality and with hierarchical relations.
A \(k\) -quark is a motif-parameterized subgraph where each node/edge (or small motif) participates in a number of (larger) motifs. The parameter \(k\)  denotes the extent of participation and not an input: quark decomposition finds non-empty \(k\) -quarks for all \(k\)  values.
Our framework is inspired by the peeling approach in simple graphs, namely core, truss, and nucleus decompositions [1]}, [2]}, [3]}, which first locate the outer sparse parts of the graph and then find the inner dense regions.
Given the practicality and effectiveness of the peeling techniques, we adapt them to the directed networks with categorical attributes in a principled way.
Note that it is beyond nontrivial to consider a generalization since edge directions and node/edge attributes create a wide and diverse spectrum of motifs (see fig:dirmotifs and fig:signedmotifs for examples).
