\(H\)  is connected if all pairs of nodes are connected.
Definition 1 
Let \(S \subseteq V\) .
The induced hypergraph \(H|_S\)  has node set \(S\)  and contains every hyperedge of \(H\)  completely contained in \(S\) , i.e., \(\forall e \in H|_S\) , iff \(v \in e\)  then \(v \in S\) .
[\(\bullet \) ]
The degree of node \(v\)  \(\in \)  \(H|_S\)  is denoted by \(d_S(v)\)  (or \(d(v)\)  when clear).

The minimum degree in \(H|_S\)  is denoted by \(\delta _S\) .
Induced hypergraph is also known as section hypergraph.
Dense subgraphs.
We call a subgraph dense if it has many motifs (also called motif-based or -driven dense subgraph). Formally, we use average motif degree to quantify the density of a subgraph with respect to a given motif.
Definition 2 
For a subgraph \(S\)  and a motif \(N\) , the average motif degree of \(S\)  is the number of instances of \(N\)  in \(S\)  divided by the number of nodes in \(S\) .

Quark decomposition framework
We first define the motif hypergraph.
Definition 3 
Given a graph \(G\)  and template motifs \(M\)  and \(N\)  s.t. \(M \subset N\) .
Let \(\lbrace M\rbrace \)  and \(\lbrace N\rbrace \)  be the set of instances of \(M\)  and \(N\)  in \(G\) , respectively, and \(f, g\)  be bijective functions.
Motif hypergraph \(H_G(M, N)=(V_G, E_G)\)  is a hypergraph constructed as follows:
[\(\bullet \) ]
Each instance of \(M\in G\)  forms a node \(u \in V_G\)  by \(f\) :\(\lbrace M\rbrace \rightarrow {V_G}\) .

Each instance of \(N\in G\)  forms a hyperedge \(e \in E_G\)  by \(g\) :\(\lbrace N\rbrace \rightarrow {E_G}\) .

Iff \(M\subset N\)  in \(G\) , then \(f(M)\in g(N)\)  in \(H_G\) .
Note that \(H_G(M,N)\)  is a \(t\) -uniform hypergraph (i.e., \(s(e)=t~~\forall e\in E_G\) ) where \(t\)  is the number of occurrences of \(M\)  in \(N\) .
We also refer to the degree of each node \(u \in H_G\)  as the motif degree, denoted by \(d_{H_G}(u)\)  (or \(d(u)\)  when \(H_G\)  is obvious).
We now introduce the notion of k-quark subgraph.
Definition 4 
Given a graph \(G\)  and template motifs \(M\) , \(N\)  such that \(M \subset N\) , say \(H_G(M,N)\)  is the motif hypergraph defined as above.
[\(\bullet \) ]
For any \(k \in \mathbb {N}\) , a \(\mathbf {\textit {k}}\)  -quark of \(H_G(M,N)\)  is a connected and maximal induced sub-hypergraph \(H|_S\)  such that \(\delta _S \ge k\) .

For a node \(u\)  in \(H_G(M,N)\)  (corresponding to an instance of motif \(M\)  in \(G\) ), the quark number of \(u\) , denoted by \({\mathcal {K}({u})}\) , is the largest value of \(k\)  such that \(u\)  belongs to a non-empty \(k\) -quark.
We also refer to \(k\) -quark as quark when \(k\)  is irrelevant or clear.
Definition 5 
\(k\) -quarks form a hierarchy by containment.
[\(\bullet \) ]
Let \(S\)  be a \(k\) -quark and \(T\)  be a \(k^{\prime }\) -quark such that \(k^{\prime }<k\)  and \(S \subset T\) . \(S\)  is the child of \(T\)  (and \(T\)  is the parent of \(S\) ) if there is no \(\bar{k}\) -quark \(U\)  such that \(k^{\prime }<\bar{k}<k\)  and \(S \subset U \subset T\) .

A \(k\) -quark is leaf (childless) if there is no \(k^+\) -quark in it s.t. \(k^+>k\) .

Maximum quark number of a graph is the largest \(k\)  for which there is a non-empty \(k\) -quark.

Maximum \(k\) -quark is a quark where \(k\)  is the maximum quark number in the graph.
Quark decomposition is the process of finding the quark numbers and \(k\) -quarks for a given pair of motifs \(M, N\)  in a graph \(G\) . Leaf \(k\) -quarks are the locally optimal subgraphs; they are surrounded by less dense quarks (with lower \(k\)  values) and hence often contain the most interesting information.
If \(G\)  is a simple undirected graph where \(M\)  is \(r\) -clique and \(N\)  is \(s\) -clique (\(r<s\) ), then \(k\) -quark is nothing but a \(k\) -\((r,s)\)  nucleus [1]}, [2]}.
If \(G\)  is a simple undirected bipartite graph where \(M\)  is edge and \(N\)  is \(2,2\) -biclique, then \(k\) -quark reduces to be a \(k\) -wing [3]}.
In the quark decomposition, each \(M\)  instance is given a quark number and the \(k\) -quarks along with the hierarchical relationships among them can be constructed accordingly.
Note that, \(N\)  is the motif of interest for which dense regions are to be found.
Motif \(M\)  can be any subset of \(N\)  but it should satisfy some requirements such that non-trivial \(k\) -quarks can be obtained (more details given in sec:limits).
When \(M\)  is edge or a larger motif, the resulting \(k\) -quarks may overlap with each other because quarks are defined as a group of \(M\) s.
This is useful since the overlapping communities can better capture the network organization [4]}.
<FIGURE>
Limitations & practical instantiations
It is important to consider the necessary and sufficient conditions for the \(M\)  and \(N\)  in def:quark so that the \(k\) -quarks are non-trivial. For instance, if \(M\)  has only one occurrence in \(N\) , the size of each hyperedge in the motif hypergraph becomes one, thus it is not possible to consider any connectivity among \(M\) s.
This is related to the automorphism orbits [5]}, [6]}.
Automorphism orbit (or just orbit) of a node in a given motif is the set of other nodes that have the same topological connectivity patterns.
For directed triangle motifs, shown in fig:dirmotifs, orbits of the nodes are denoted with colors.
For instance, in+ has two orbits; the first has one node with two incoming edges (white node) and the second has two nodes where each has one outgoing and one bidirectional edge (black nodes).
Note that automorphism orbits are defined only for the nodes.
In our framework, we can also consider an edge or a larger structure as \(M\)  in def:quark, thus automorphism orbits of such structures need to be taken into account.
To define the orbits of any \(M\) , we consider the ordered list of node orbits in it.
Enforcing the automorphism orbits restricts the use of any motif since def:quark requires that at least one orbit should have multiple instances in \(N\) .
E.g., when \(M\)  is node or edge; acyclic, cycle+, and cycle++ motifs have three different orbits, i.e., no orbit has multiple members. Thus those cannot be considered as \(N\) .
To remedy this problem, we use a vanilla motif \(M\) , which has only one orbit. A vanilla motif has no node/edge labels and its edges are directionlesswe do not say bidirectional to avoid any confusion. Any motif \(N \supset M\)  will contain multiple instances of \(M\) , thus the size of hyperedges will be greater than one.
fig:role gives an example when \(M\)  is a vanilla edge and \(N\)  is acyclic.
Role confusion problem
Another problem in \(k\) -quarks is the conflation of the orbits for \(M\) s.
An instance of \(M\)  can be a part of multiple instances of \(N\) .
Furthermore, orbit of an \(M\)  instance in one \(N\)  instance can be different than its orbit in another \(N\)  instance. E.g., if \(M\)  is node and \(N\)  is out+, a node may appear as white node in one out+ instance while being black node in another out+ instance (see fig:dirmotifs).
We call this the role confusion problem.
Note that choosing \(M\)  as a vanilla motif does not help with the role confusion problem.
For example, consider cycle+ with nodes \(A, B, C\)  and edges \(A\)\(\rightarrow \)\(B\) , \(B\)\(\rightarrow \)\(C\) , \(A\)\(\leftrightarrow \)\(C\) .
This can be a structure in Twitter network; e.g., A is a grad student, C is her advisor (a professor), and B is a junior faculty working in the same field—B is an interesting person for A but not for C, professor C is a well-known person followed by many and she follows A since she is A's advisor.
In the motif-driven subgraphs for cycle+, each node has ideally a single role; i.e., a grad student is better characterized as the node A in all the cycle+ instances she participates in.
The solution is to construct the subgraphs in a way that abide by the orbits.
To do that, we define role-aware quark numbers for each \(M\) .
If \(M\)  has \(b\)  orbits in \(N\) , each \(M\)  will have \(b\)  role-aware quark numbers, one for each orbit.
Definition 6 
Given a graph \(G\)  and motifs (vanilla) \(M\)  and \(N\)  (s.t. \(M \subset N\) ), let \(H_G(M,N)\)  be the motif hypergraph as defined in def:motifhypergraph. Let \(b\)  be the number of orbits of \(M\)  in \(N\) .
[\(\bullet \) ]
Orbit degree of an \(M\)  instance is the number of instances of \(N\)  that contain it such that the orbit of the \(M\)  instance in each \(N\)  instance is the same. Each \(M\)  instance has \(b\)  orbit degrees.

For any \(k \in \mathbb {N}\) , a role-aware \(\mathbf {\textit {k}}\)  -quark of \(H_G(M,N)\)  is a connected and maximal induced sub-hypergraph \(H|_S\)  such that each \(M\)  instance has one orbit degree of at least \(k\) .

For a node \(u\)  in \(H_G(M,N)\)  (corresponding to an instance of motif \(M\)  in \(G\) ), the role-aware quark numbers of \(u\)  are \(b\)  numbers, denoted by \({\mathcal {K}_i({u})}\)  for \(1\le i \le b\) .
\({\mathcal {K}_i({u})}\)  is the largest value of \(k\)  such that the node \(u\)  belongs to a non-empty role-aware \(k\) -quark where its orbit is \(i\) .
In a role-aware \(k\) -quark, each \(M\)  instance participates in at least \(k\)  \(N\)  instances and the orbit of the \(M\)  instance in each of those participations is the same (note that different \(M\)  instances can have different orbits in the quark).
Role-aware quark numbers describe the extent of participation as a particular orbit while the quark number indicates the extent of participation as any orbit.
When \(M\)  is node and \(N\)  is cycle or reciprocal (in fig:dirmotifs), there is no role confusion since there is only one node orbit in each. For all the other directed triangles, there is a role confusion.
When \(M\)  is edge, we always consider the orbits of the two nodes in it.
In the context of directed triangles, one important point is the distinction between unidirectional and bidirectional edges.
In this work, we consider the bidirectional edge as an atomic entity; i.e., not combination of two unidirectional edges, due to the fact that a symmetrical relation has a different semantic than two asymmetrical ones—in a sense we only consider the induced edges.
For instance, in+ and out+ do not create any role confusion when \(M\)  is edge, because the unidirectional edge between the white and black nodes in in+ (or out+) cannot serve as a bidirectional edge (between two black nodes) in an adjacent in+ (or out+) motif (see fig:dirmotifs).
Example
fig:role illustrates an example on a toy graph.
We choose the vanilla edge as the motif \(M\)  and acyclic triangle as the motif \(N\) , shown in the top-left.
We denote the node orbits in acyclic with different colors; orange shows the node with two outgoing edges, blue is for the node with two incoming edges, and red denotes the node with one incoming and one outgoing edge.
Motif hypergraph, \(H\) , with respect to \(G, M, N\)  is shown next.
As described in def:motifhypergraph, we create a node for each vanilla edge (bottom set in \(H\) ) and a hyperedge for each acyclic (top set in \(H\) ).
Id of each acyclic and edge in \(H\)  is formed by the concatenation of the node ids in it, e.g., 12 denotes the edge from 1 to 2.
Each hyperedge is connected to three nodes since there are three edges in an acyclic—making \(H\)  a 3-uniform hypergraph.
The degree of each node in \(H\)  is called the motif degree, e.g., it is 2 for edge 4-5.
Quark numbers of the edges are denoted by gray (\(\mathcal {K}=1\) ) and black (\(\mathcal {K}=2\) ) in the bottom set of \(H\) ; e.g., quark number of edge 4-5 is 2.
Based on those quark numbers, we construct the quarks in the top-right.
Two quarks are created; a 1-quark, corresponding to the entire graph \(G\) , and a 2-quark with nodes \(1, 3, 4,\)  and 5.
We observe role confusions for the thick edges in those quarks, which in turn implies the role confusions on nodes.
Regarding the edges, 1-4, 3-4, and 3-5 have role confusion in both quarks; e.g., in 1-quark, 1-4 connects orange to blue in 1-4-6 acyclic but it links orange to red in 1-5-4 acyclic.
For the nodes, 3 and 4 in both quarks have role confusions, e.g., node 3 is red in the 1-3-5 acyclic (and in 1-3-4) while being orange in the 3-4-5 acyclic.
We give the role-aware quarks and quark numbers of the edges at the bottom.
If we construct the role-aware quarks by abiding the orbits, we get three role-aware 1-quarks.
Note that the only edges that have multiple non-zero \(\mathcal {K}_i\)  are the ones that have role confusion in the top-right.

Algorithms
Here we discuss our peeling algorithms, first for quark decomposition (def:quark) and then for role-aware quarks (def:RAquark).
Quark decomposition
Algorithm REF  outlines the quark decomposition. Here we assume the motif \(M\)  in def:quark to be node or edge for simplicity. Note that larger structures can be considered as well. Also, we avoid constructing the actual hypergraph of motifs since it requires enumerating all the \(N\) s which will have a significant space cost. Instead, we discover those motifs for each node/edge as needed, similar to the space-efficient approach in nucleus decomposition [1]}. There are three different phases in the quark decomposition; motif degree counting, peeling to find quark numbers, and constructing the subgraphs and the hierarchy.
Motif degree counting. Line REF  corresponds to counting the occurrences of \(N\)  instances per each node or edge.
There are some studies [8]}, [9]}, [10]} that leverage certain commonalities among motifs to avoid redundant computations.
Adapting those studies for per node/edge motif counting to improve runtime is possible but out of scope for this work.
Also, simultaneously counting the motif degrees for multiple motifs would speed up the workflow when the motif of interest is unknown to the user and multiple options need to be investigated.
Note that if the label set of the input motif \(N\)  is smaller than the label set of the input graph \(G\) , we can filter the graph to only keep the label set of \(N\) , e.g., if a triangle of female students is \(N\)  for an undirected graph where genders are the node labels, only the induced graph of female nodes can be considered.
Peeling to find quark numbers. Lines REF  to REF  assigns a quark number for each node/edge.
The classical core decomposition implementation [11]} makes use of the bucket data structure to keep track of the nodes with the minimum degree.
We also use this approach to watch the nodes/edges with the minimum motif degree.
Initially, all the nodes/edges are marked as unprocessed (line REF ), which will come handy to ensure each \(N\)  instance is processed only once.
In each iteration, an unprocessed node/edge with the minimum motif degree is chosen (line REF ).
The motif degree of the chosen node/edge is set to be its quark number (\(\mathcal {K}\) ) (line REF ).
Then, the \(N\)  instances that contain the chosen node/edge are found and processed in lines REF  to REF .
In each such instance of \(N\) , we make sure that the other nodes/edges (the neighbors of the chosen node/edge) are unprocessed (line REF ); this is done to ensure that each \(N\)  instance is examined only once.
Then, the neighbor nodes/edges in each \(N\)  instance are checked (line REF ) and their motif degree is decremented if larger than the motif degree of the chosen node/edge (lines REF  and REF ).
At the end of the iteration, the chosen node/edge is marked as processed (line REF ).
For any \(M, N\)  motif pair, two basic procedures are necessary and sufficient to instantiate the quark decomposition;
[\(\bullet \) ]
Finding the \(N\)  instances that contain a given \(M\)  instance (line REF ),

Finding the \(M\)  instances in a given \(N\)  instance (lines REF  and REF ).
Constructing the subgraphs and the hierarchy. It is also possible to construct the subgraphs and build hierarchy among \(k\) -quarks during the peeling operation, as noted in magenta lines after lines REF  and REF .
Subgraph and hierarchy construction during the peeling process is introduced in [12]} and can be adapted to the quark decomposition.
In line REF , the nodes/edges that are in the same \(N\)  instance with the chosen node/edge are checked.
If those nodes/edges are already processed (i.e., assigned a quark number), we can build non-maximal \(k\) -quarks during the peeling process.
At the end, those non-maximal \(k\) -quarks are converted to the real (maximal) \(k\) -quarks with a light-weight post-processing that uses the union-find data structure (following line REF ).
[!t]
Quark Decomposition (\(G\,(V,E)\) , motif \(N\) )

Compute \(d(u)\)  (motif deg.) \(\forall ~u \in V\)   blueor \(d(e)\)  \(\forall ~e\in E\) 
Mark every \(u\)  blue(or \(e\) ) as unprocessed
each unprocessed \(u\)  blue(or \(e\) ) with minimum degree \(d\) 
\(\mathcal {K}(u) \leftarrow d(u)\)  blueor \(\mathcal {K}(e) \leftarrow d(e)\) 
each motif \(N\)  s.t.  \(u \subset N\)  blue(or \(e \subset N\) )
any node \(v \in N\)  is processed blue(or edge)continue
magentacan also find subgraphs & hierarchy
each node \(v~(\ne u) \subset N\)  blue(or edge \(f~(\ne e)\) ) 
\(d(v) > d(u)\)  blue(or \(d(f) > d(e)\) )
\(d(v) \leftarrow d(v) - 1\)  blueor \(d(f) \leftarrow d(f) - 1\) 



Mark \(u\)  blue(or \(e\) ) as processed

magentaOptional post-processing to build the hierarchy
array \(\mathcal {K}(\cdot )\)  

Theorem 1 Given a graph \(G=(V,E)\)  and motif \(N\) , Algorithm REF  finds the quark numbers, \({\mathcal {K}({\cdot })}\) , of all \(u \in V\)  (or \(e \in E\) ).

We give the proof for the node case without loss of generality (i.e., it is similar for the edge).
As noted in sec:prelim, nodes \(u, v \in V\)  are neighbors if they participate in a common motif \(N\) .
\({\mathcal {K}({u})}=k\)  indicates that there are at least \(k\)  instances of \(N\)  which contain \(u\)  and in each such \(N\) , \(u\)  has a neighbor node \(v\)  s.t. \({\mathcal {K}({v})} \ge {\mathcal {K}({u})}\) .
This is enforced by the lines REF -REF , where the motif degree a neighbor node is decreased if it is larger than the quark number assigned at that step.
In other words, any neighbor node with a smaller quark number does not contribute to the quark number of the node of interest.
If Algorithm REF  finds \({\mathcal {K}({u})}=k\)  for a node \(u \in V\) , then by def:quark, we need to show that (i) \(\exists \)  a \(k\) -quark \(G^{\prime } \ni u\) , (ii) \(\nexists \)  a \(k^+\) -quark \(G^{\prime } \ni u\)  (\(k^+ > k\) ).
(i) Once \({\mathcal {K}({u})}=k\)  is found in Algorithm REF , we stop and construct an induced subgraph \(G^{\prime } \subset G\)  by traversal as follows.
Initially, \(G^{\prime }\)  has only \(u\) .
In each step, we visit a node \(v \in V\)  s.t. \(v\)  co-participates in some \(N\)  instance with a node from \(G^{\prime }\) .
If \({\mathcal {K}({v})}=k\)  or if it is unassigned but its current motif degree is equal to \(k\) , we add \(v\)  to \(G^{\prime }\) .
We continue the traversal until no such node \(v\)  can be found.
At the end, \(G^{\prime }\)  is a \(k\) -quark since (1) each node participates in \(\ge k\)  motifs, because the nodes are processed in the non-decreasing order of their motif degrees, (2) all the nodes are connected to each other with motifs due to the motif-based traversal, and (3) \(G^{\prime }\)  is maximal since it is the largest subgraph that can be found by the traversal.
(ii) \(u\)  cannot be in a \(k^+\) -quark. Assume it is. Then it should take part in at least \(k^+\)  motifs and each motif contains a neighbor node with motif degree of at least \(k^+\) . But, this implies that \({\mathcal {K}({u})}=k^+\)  (by def:quark), contradiction.
Time and space complexity. Algorithm REF  has \(O(\sum _{v\in V} d(v)^{|V_N|-1})\)  complexity when \(M\)  is node or edge (\(V_N\)  is the node set of \(N\) ).
The space complexity is \(O(|E|)\)  when \(M\)  is node/edge.
Instead of explicitly building the hypergraph of \(M\) s and \(N\) s in \(G\) , we only build the adjacency lists when required.
Since \(N\) s are not stored, space complexity is bounded by \(O(|E|)\) .
We find all motifs containing the node/edge of interest only when that node/edge is processed.
Each node/edge is processed at most once.
When \(M\)  is node, we can find all the \(N\) s containing a node by looking at all \((|V_N|-1)\) -tuples in each of the neighborhoods of the node.
This takes at most \(\sum _{v \in V} d(v)^{|V_N|-1}\) .
Likewise, when \(M\)  is edge, we consider \(|V_N|-2\)  tuples in each edge neighborhood and total time is \(\sum _{e \in E} \sum _{v \in e} d(v)^{|V_N|-2} \)  \(= \sum _{v \in V} \sum _{e \ni v} d(v)^{|V_N|-2} \)  \(= \sum _v d(v)^{|V_N|-1}\) .
[!t]
Role-aware Quark Dec. (\(G\,(V,E)\) , motif \(N\) )

Let \(B\)  be the set of orbits that a node/edge has in \(N\) 
Compute \(d_o(u)\)  (orbit deg.) \(\forall \)  orbits \(o\) =\(1,...,|B|\) , \(\forall \,u\)\(\in \)\(V\)  blueor \(d_o(e)\) 
Mark every tuple \((u, o)\)  as unprocessed for \(o\) =\(1,...,|B|\)  blueor \((e,o)\) 
each unprocessed \((u, a)\)  blue(or \((e,a)\) ) with min. orbit degree \(d_a\) 
\(\mathcal {K}_a(u) \leftarrow d_a(u)\)  blueor \(\mathcal {K}_a(e) \leftarrow d_a(e)\) 
each motif \(N\)  s.t.  \(u \subset N\)  blue(or \(e \subset N\) ) 
Let \(v\) (\(\ne \)\(u\) ) be a node in \(N\) , \(b\)  be its orbit blue(or \(f\) (\(\ne \,e\) ) is an edge)
any tuple \((v, b)\,\in \,N\)  is processed blue(or \((e,b)\) )cont.
each node \(v~(\ne u) \subset N\)  blue(or edge \(f~(\ne e)\) ) 
Let \(b\)  be the orbit of \(v\)  blue(or \(f\) ) in \(N\) 
\(d_b(v) > d_a(u)\)  blue(or \(d_b(f) > d_a(e)\) )
\(d_b(v) \leftarrow d_b(v) - 1\)  blueor \(d_b(f) \leftarrow d_b(f) - 1\) 



Mark \((u,a)\)  blue(or \((e,a)\) ) as processed

arrays \(\mathcal {K}_1(\cdot ), ..., \mathcal {K}_{|B|}(\cdot )\)  

Role-aware quark decomposition
Algorithm REF  outlines the role-aware quark decomposition; again, for simplicity, we assume the motif \(M\)  in def:RAquark is node or edge (larger \(M\)  can be considered as well).
The only difference with respect to Algorithm REF  is the way we compute and keep the degrees and process the node/edge in the inner loop.
We first find the set of orbits, \(B\) , that a node/edge has in \(N\)  (line REF ).
In line REF , we count the orbit degrees for each node/edge and for all orbits \(1,...,|B|\) .
Orbit degree \(d_o\)  of a node \(u\)  (or edge \(e\) ) is the number of \(N\)  instances that contain the node \(u\)  (edge \(e\) ) such that the orbit of \(u\)  (\(e\) ) is \(o\)  (def:RAquark).
Each orbit degree of a node/edge is processed separately.
We also keep \(|B|\)  arrays to keep track of the processed \((u, o)\)  (or \((e,o)\) ) tuples (\(o\)  is the orbit of node \(u\) , or edge \(e\) ) (line REF ).
In lines REF -REF , we process all the orbit degrees in non-decreasing order.
Role-aware quark number is assigned for the chosen node/edge (line REF ) and we find the neighbors of the node/edge in each \(N\)  to adjust their orbit degrees (lines REF  to REF ).
At the end, we return role-aware quark numbers for each node; \(\mathcal {K}_i(\cdot )\)  for \(1\le i \le |B|\) .
<TABLE>

Experiments
We evaluate our framework on three types of networks and motifs therein; directed (sec:expdirected), signed-directed (sec:expsigneddirected), and node-labeled (sec:expnodelabeled) networks.
We implement quark decompositions for various motifs in each type and evaluate the resulting subgraphs.
All experiments are performed on a Linux operating system (v. 4.12.14-150.52) running on a machine with Intel(R) Xeon(R) CPU E5-2698 v3 processor at 2.30GHz with 64 GB DDR3 1866 MHz memory.
Algorithms are implemented in C++ and compiled using gcc 6.1.0 at the -O2 level.
The code is available at http://sariyuce.com/quark_decomposition.tar.
For each network type, we discuss the set of motifs used and present the results.
We compare quark decomposition to the state-of-the-art methods and highlight anecdotal examples to stress the contrast between our method and others.
We also present the runtime performance of quark decompositions and other state-of-the-art methods.
Baselines. We consider three baselines in our comparisons.
[\(\bullet \) ]
Motif clustering (MC) [13]}. Set of higher-order clustering algorithms by Benson et al. (see sec:rel for details). We consider three versions; (1) MC-Single: Algorithm that gives a single subgraph with near-optimal motif conductance, (2) MC-Rec-Bisection: Recursive bisection algorithm that iteratively finds multiple clusters (starting with the optimal) until the cluster size gets too small (less than 10 nodes) or quality degrades too much (conductance goes above 0.5), (3) MC-k-means: k-means algorithm that is run on the motif adjacency matrix – number of clusters (k) must be specified for this version.

Takaguchi and Yoshida (TY) [14]}. Cycle-truss and flow-truss algorithms (see sec:rel for details).

(r,s) nucleus [1]}. Nucleus decomposition to find hierarchical dense subgraphs in undirected networks (see sec:rel).
Metrics. We consider three metrics to measure the quality of the subgraphs. We also show anecdotal examples when feasible.
[\(\bullet \) ]

Motif conductance. Edge conductance is adapted for motifs in [13]}. Motif conductance of a subgraph is defined as the ratio of the number of motif instances cut (i.e., motifs in the boundary) to the number of motif instance end points in the subgraph (i.e., nodes participating in the motifs). The lower values are better.

Average motif degree. Conductance metric is known to have a bias toward giving better results for smaller numbers of clusters [17]}, [18]}. As an alternative, we consider the average motif degree in each subgraph, as given in def:amd.
In edge-based clustering literature, the densest subgraph of a graph is defined as the one with the largest average degree [19]}, [20]}. Here we adapt this measure for the motif-based subgraphs and simply consider the number of motifs per node. The higher values are better.

Edge density. We also consider the ratio of edges over all possible in a subgraph (\(|E|/{|V| 2}\) ). We use this metric in sec:expnodelabeled for undirected networks. The higher values are better.

Directed networks
Datasets. We consider several directed networks from various domains in our experiments: Florida Bay food web (foodweb), word associations (EAT), emails (email-EuAll), citations (cit-HepPh), online social networks (slashdot, soc-pokec, livejournal,
wiki-Talk), web networks (web-ND, wiki-Talk), and product co-purchasing relations (amazon).
All networks (except EAT [21]}) are obtained from SNAP [22]}.
 tab:directeds gives several statistics, including the motif counts and maximum quark numbers.
<FIGURE>Motifs. We instantiate the quark decomposition for directed networks by considering the edge and triangle motifs (fig:dirmotifs), corresponding to the \(M\)  and \(N\)  in def:quark, respectively.
Note that considering edge as motif \(M\)  is more advantageous than node. Since the edges are assigned quark numbers, \(k\) -quarks can overlap with each other.
Also, role confusion does not happen for out+ and in+ as explained in sec:roleconf.
We also incorporate the reciprocity by considering the unidirectional and bidirectional edges separately, rather than treating each bidirectional edge as two unidirectional edges.
This is because directed networks often have a significant percentage of bidirectional edges (also observed in tab:directeds) and those need to be treated differently, as discussed in  [23]}, [24]}.
We use the vanilla edge as the motif \(M\)  and each of the seven directed triangles (fig:dirmotifs) as the motif \(N\) .
We first discuss the motif counts and quarks for directed triangles. Then we compare quarks with baselines using the EAT and foodweb networks. We finish by comparing the runtimes.
Motif counts and subgraphs
tab:directeds lists the motif counts and maximum quark numbers for each motif.
cycle is often the least common motif.
Networks with significant fraction of bidirectional edges tend to contain reciprocal motifs the most.
Note that the most frequent motif does not always yield the highest quark number.
In particular, reciprocals are often concentrated in a small region, thus yield highly-dense subgraphs.
For instance, en-wiki has 5.9M reciprocal and 163.3M acyclic motifs but the maximum quark numbers for those motifs are 29 and 26, respectively.
This is because the maximum \(k\) -quark has 465 edges in the reciprocal case but has 9461 edges in acyclic.
We also observe that the number of quarks are independent of the motif counts.
For example, the most prevalent motif in EAT network is, by far, acyclic.
However, acyclic yields only 447 \(k\) -quarks while the cycle+ locates 2826 subgraphs.
Overall, the abundance of a particular motif does not imply the existence of dense subgraphs containing that motif.

Comparison with previous methods
We compare quark decomposition against the three baselines listed above. We use EAT network, a collection of word association norms where the nodes are English words and an edge \((u, v)\)  implies that human subjects consider the word \(v\)  when they are shown the word \(u\)  as stimulus.
We first compare the quality of subgraphs given by the quark decomposition and MC algorithms [13]} using motif conductance and average motif degree metrics. For quark decomposition, we only consider the \(k\) -quarks with at least 10 nodes.
For MC algorithms, we consider MC-Single and MC-Rec-Bisection.
Note that we aim to compare the `best' clusters reported by the two algorithms and do not intend any comparison with respect to the number of clusters reported.
fig:EATcomp gives the comparison for reciprocal, out+, acyclic, and cycle++ motifs (other motifs show similar results and omitted).
For each subgraph, we report the size as well as the quality metric; number of motifs per node in the top row and the motif conductance in the bottom row.
MC variants often give large subgraphs, always with very low conductance, as expected. MC-Single (optimal cluster) has more than 1000 nodes for out+, in+, acyclic, and cycle++.
For cycle+, however, it has only five nodes.
Quarks are often small, most in the range of 10-100 nodes, and have higher conductance scores. For out+ and cycle++, some quarks yield comparable conductance scores with MC-Rec-Bisection.
We also observe that a quark for acylic has a better conductance than MC-Single (which is the near-optimal as shown in [13]}).
Regarding the average motif degrees (top row), quarks perform significantly better in all the motifs (note that y-axis is in log-scale).
By definition of the quark (the connectivity constraint in particular), if the size is \(n\) , the number of motifs is at least \(n-2\)  (for \(k=1\) , a single motif is a valid subgraph and can be extended by a new node that creates a new motif, keeping the motif count \(n-2\) ). This ensures a lower bound, \(\frac{n-2}{n}\)  (close to 1), for average motif degree in quarks.
In general, quarks tend to be smaller in size when compared to MC results, have consistently higher average motif degrees, and comparable conductance scores for some motifs.
Overall, the top-down partitioning approach in the motif clustering is likely to result in larger subgraphs in varying quality whereas the bottom-up computation in quark decomposition yields smaller subgraphs with larger average motif degrees.
Next we compare quark decomposition with TY  [14]}.
For EAT network, TY reports maximum cycle-truss number of 3 and maximum flow-truss number of 10. For each maximum truss subgraph, we checked the quarks that are the most similar.
fig:tycomp presents the results for cycle-truss, flow-truss, and their corresponding quarks with size and average motif degree information. For cycle- and flow-truss, we calculate the induced cycle and acyclic motif degrees (i.e., bidirectional edges are not included).
Next to each quark, we denote the size of its intersection with the truss.
Various types of quarks are able to obtain almost all the nodes in those trusses.
70 of 77 nodes in cycle-truss are obtained with 15 quarks and all of the 45 nodes in flow-truss are given in 15 other quarks.
This verifies the artificial over-representation of cycle- and flow-trusses due to the non-induced nature.
Overall, treating the bidirectional edges as atomic units enables finding diverse subgraphs while correctly capturing the semantics of pairwise relationships.
<FIGURE><FIGURE>Lastly, we compare quarks with \((2,3)\)  nucleus decomposition [1]}, which ignores edge directions.
We observe that incorporating the edge directions results in more diverse subgraphs.
The number of subgraphs (of any quality) obtained by each quark decomposition is significantly larger than what nucleus decomposition yields.
As an anecdotal example, we show a subgraph found by the nucleus decomposition in fig:EATexample.
The direction-oblivious subgraph contains words related to astronomy and space.
Quark decompositions capture several diverse contexts related to those words.
Thanks to the overlapping quarks, in+ finds two subgraphs that contain space and stars: one in astronomy theme (uranus, venus, ...) and another in the religious context (god, eternity, ...).
It also finds another subgraph in the vacation theme (sun, holiday, sand, ...).
Out+ yields a subgraph in the air-flight context (sky, aircraft, wing, ...).
We also recognize that multiple meanings of the homonym words are reflected in various \(k\) -quarks.
For instance, lie is reported in two subgraphs by cycle++: one is about incorrectness (falsehood, untruth, ...) and the other is about staying at rest in the horizontal position (couch, rest, ...).
Overall, quark decompositions by various motifs can locate diverse contexts for a given word thanks to the motif-aware approach and overlapping nature of quarks.

Analysis of Florida Bay food web
Here we analyze the structure of Florida Bay food web network (foodweb) where the nodes are the compartments (i.e., organisms, species) and the edges are the directed carbon exchanges (i.e., \(u\rightarrow v\)  if \(v\)  eats \(u\) ).
Benson et al. showed that high-quality clusters (i.e., with low conductance) by MC only exist for out+, which implies that the organization of compartments is better described with out+ (as opposed to the common belief that acyclic is the key motif) [13]}. They also show that the 4 clusters by MC-k-means for out+ reflect the ground-truth subgroup classifications better than the state-of-the-art clustering algorithms such as spectral edge clustering (with k-means and recursive bisection) [30]}, InfoMap [31]}, and Louvain method [32]}.
We first compare the quarks for out+ with MC-k-means.
We find 7 quarks for out+, so we consider MC-k-means with 7 clusters as well as with 4 clusters.
The nodes that appear in multiple quarks are only considered to be part of their largest quark (other choices give similar results).
tab:foodweb-comparison presents the results for two ground-truth classifications given in [33]}, [13]} by four metrics: Adjusted Rand Index (ARI), F1 score, Normalized Mutual Information (NMI), Purity [35]}.
Quarks clearly outperforms MC-k-means variants in both classifications by all the metrics.
One particular difference is that MC-k-means considers some macroinvertebrates like predatory crabs among the benthic predators of eels and toadfish whereas quark decomposition finds all macroinvertebrates in the same subgraph.
We believe the main reason is that MC-k-means considers motif counts from the node-perspective while quark decomposition is based on the edges and their motif counts.
<TABLE><TABLE>We also consider acyclic and use role-aware quark decomposition (Algorithm REF ) to determine the roles of the compartments in the resulting quarks.
For an acyclic formed by \(u\)\(\rightarrow \)\(v\) , \(u\)\(\rightarrow \)\(w\) , and \(v\)\(\rightarrow \)\(w\) , we define \(u\)  as the prey orbit, \(v\)  as the balancer orbit, and \(w\)  as the predator orbit.
The maximum quark obtained by QuarkDec (Algorithm REF ) and RA-QuarkDec (Algorithm REF ) is the same and contains 48 compartments.
RA-QuarkDec assigns three quark numbers for each edge, corresponding to the three edge orbits in acyclic (each is a union of its nodes' orbits).
We determine the role profile for each node based on the quark numbers of its outgoing and incoming edges.
The compartments that are dominantly predator are the birds including predatory ducks, big herons & egrets, greeb, and more.
Dominantly prey compartments include clown goby, four types of zooplankton microfauna, and seven macroinvertebrates (including pink and herbivorous shrimps).
Lastly, the ones that have the balancer role are the fishes, such as (bay) anchovy, sardines, and mojarra.
Note that it is not possible to understand the roles of the compartments by QuarkDec since each edge has a single quark number. For instance, the average quark numbers of incoming and outgoing edges for predatory ducks and code goby are very close, which tells nothing about their roles.

Runtime performance.
We measure the runtime for quark decomposition and MC-Single on all directed networks, tab:dirtimes lists the results for large networks.
MC-Single (denoted M) gives only one near-optimal cluster and quark decomposition (denoted Q) finds all the quark numbers.
Quark decomposition is faster than MC-Single for all motifs in web-ND, amazon, soc-pokec, and liveJournal.
For some configurations, such as in+ in liveJournal, we observe up to 10x speedup.
For en-wiki, however, MC-Single is faster for all motifs. Note that MC-Single runtime includes motif adjacency construction and spectral clustering to find one cluster. In order to find more clusters, spectral clustering needs to be run again. However, the spectral clustering takes 36% of the total time for en-wiki (on avg.), hence obtaining 10 clusters will increase the runtime by 4x.
All in all, although MC-Single finds only one cluster, quark decomposition is faster for most networks and motifs, and a better choice especially when multiple subgraphs are targeted.

Signed-directed networks
Datasets. We use signed-directed networks that have categorical labels on edges to denote one-sided positive/negative relationships (no bidirectional edges).
We have two Reddit hyperlink networks that have directed connections among the subreddits.
reddit-body and reddit-title consider the positive and negative interactions among users who belong to different subreddits [36]}.
We considered the last interactions in the datasets.
We also consider epinions, a who-trust-whom social network [37]},
and slashdot which contains the self-tagged friend/foe relationships [38]}.
All are obtained from SNAP [22]}.
tab:signeds gives the number of positive and negative edges, motif counts, and maximum quark numbers.
Motifs. We use edge and triangle motifs, corresponding to the \(M\)  and \(N\)  in def:quark, respectively.
This also ensures that quarks can overlap with each other.
There is no bidirectional edge and there are twelve possible triangle motifs in total, as shown in fig:signedmotifs; four cycle motifs since there is a single orbit and eight acyclic motifs where each ++- and +– appears in three different ways.
We use the vanilla edge as \(M\)  and each of the twelve triangles (fig:signedmotifs) as \(N\) .
<FIGURE><FIGURE>Motif counts and quark numbers
Acyclic variants are significantly more common than the cycles in all networks.
Among the cycle variants, +++ is the most prevalent in reddit networks and — is the least common in all.
This is also coherent with the structural balance theory [40]}, which states that the triangles with an odd number of negative links are rare.
However, cycle++- is more common than the other cycles in the epinions network.
This might be due to hierarchical status among the nodes; the lower status nodes are likely to trust the ones with higher status but the reverse is not true.
The ratio of balanced triangles is 0.8 for reddit networks but 0.42 for epinions.
Per the maximum quark numbers, we observe a correlation with the motif counts.
Among all, only acyclic+++ yields non-trivial subgraphs with large quark numbers.
Cycle variants fail to give significant quarks.
<TABLE>
Comparison with MC
We compare the \(k\) -quarks with the MC-Single and MC-Rec-Bisection for acyclic+++ motif in fig:rba.
Some quarks are able to obtain very low conductance scores, close to MC results.
For the average motif degrees, quarks significantly outperform MC-Rec-Bisection.
In particular, one quark has 284 nodes with average motif degree of 185.2.
One of the quarks by acyclic+++ has 21 subreddits about rappers/singers, such as kanye and kendricklamar.
The ones which praised the others but have not received much praise (the white node in acyclic in fig:dirmotifs) are boogalized, runthejewels, and  charlieputh. The last two are a young rapper duo and a new Canadian singer, respectively, with 6.6K and 279 members.
On the other hand, the subreddits that got praised by the others but have not reciprocated (the black node in acyclic) are theweeknd, frankocean, and kidcudi.
Those are experienced ones (active since 2010, 2005, and 2003) with tens of thousands of members in their subreddits.


Node-labeled networks
Datasets. Here we consider node-labeled undirected networks. We use the Facebok100 dataset that contains the complete Facebook networks of 100 American colleges from a single-day snapshot in September 2005 [41]}. Each node has multiple labels, here we only consider the genders of the nodes (there are only two available in the dataset; female and male) and use quark decomposition to find subgraphs that have balanced gender ratios, i.e., close number of females and males.
Excluding the female-only institutions, the overall average female ratio is \(\%48.5\)  and there are 57 networks with less than \(50\%\)  female.
We choose 18 networks with the lowest female ratio (all have \(<45\%\) ), tab:femaleratios gives a partial list.
<TABLE>Motifs. We instantiate the quark decomposition in five ways, where F/M denotes the female/male nodes:
(1) \(M\)  is vanilla edge and \(N\)  is triangle in the following two forms: FMM and FFM; and
(2) \(M\)  is vanilla triangle, \(N\)  is four-clique in the following three forms: FMMM, FFMM, and FFFM.
Also, there is no role confusion for any variant since the graph is undirected and node labels ensure that an edge cannot serve in different roles in its triangles in (1) (likewise for (2)).
Finding gender balanced subgraphs
Algorithmic fairness is one of the most important problems in today's automated world [42]}.
Algorithms can amplify the implicit bias in the data, particularly based on the protected attributes like gender, race, ethnicity, and this can lead to unwanted consequences in criminal justice system, hiring, credit scoring, and more [43]}.
The bias in the network data is more complicated; regarding the gender attribute, for example, the problem is not only the imbalanced gender distribution but also how each gender category is connected to the other categories.
There are a few studies that analyze the implications on information diffusion [44]}, [45]}.
In this context, the community structure in the network plays an important role and algorithms that do not actively consider the protected attributes are likely to fail getting fair results.
Algorithms that can find balanced communities even when there is an imbalance in the input network are essential.
Here we use quark decomposition to find subgraphs with balanced gender ratios.
As explained above, we set the input motif \(N\)  in ways to reflect the characteristics of gender balanced subgraphs.
 tab:femaleratios gives the female ratios in quarks in comparison to the label-oblivious nucleus decomposition algorithms [1]}.
For each network, we find the leaf quarks (def:hier) and nuclei with at least 10 nodes, calculate the female ratio in each quark or nucleus, and then take the average of those ratios.
We also show the average ratios across all the 18 datasets at the bottom.
The average female ratio of all the networks is \(40.3\%\) .
\((2,3)\) -nuclei have a bit better number, \(42.5\%\) .
Quarks for FMM get \(48.2\%\)  and the ratios are consistently good for all the networks, varying between \(45\%-51.3\%\) .
This significant jump from \((2,3)\) -nuclei is due to the fact that each edge has to participate in a number of FMM triangles.
Quarks for FFM give an even better ratio, \(51.5\%\) .
\((3,4)\) -nuclei are larger in number and also denser than \((2,3)\) .
Its average female ratio (\(44.1\%\) ) is also a bit better than \((2,3)\) -nuclei.
Quarks for FMMM are very close to \((3,4)\) -nuclei but more consistent.
FFMM achieves \(49.7\%\)  and FFFM gets the best: \(54.7\%\) .
Note that results get better for the motifs with larger female ratio: FMMM < FMM < FFMM < FFM < FFFM.
Quarks cannot provide a good theoretical lower bound for the female ratio since there is no size constraint in the quark definition. For instance, a 1-quark for FFM can possibly be formed by a pair of connected female nodes and \(n\)  male nodes that are connected to both females; the female ratio would be \(2/(n+2)\)  in this case.
But in practice, quarks with female-dominant motifs yield dense subgraphs with high female ratios. Even with FMM, which implies a 1/3 ratio (smaller than the average female ratio of the datasets), quarks can obtain better results than the label-oblivious (2,3)-nuclei.
<FIGURE>We also show all the subgraphs with size, edge density, and female ratio information obtained by quark and nucleus decompositions in UPenn7 network.
 fig:upenn gives \((3,4)\) -nuclei and quarks for FFFM on UPenn7 network.
Quarks are consistently gender balanced when compared to the nuclei; no quark with less than \(25\%\)  female ratio exists.
Note that there is a bit degradation in the number and density of the quarks for FFFM: 216 subgraphs with 0.88 avg. edge density, compared to the 230 \((3,4)\)  nuclei with avg. density 0.94.
Given the consistently high female ratios, we believe that this is an affordable loss in quality.

Discussion
Quark decomposition offers a principled approach for motif-driven dense subgraph discovery in heterogeneous networks by successfully regularizing the motif degrees to quark numbers.
Our evaluation shows that the \(k\) -quarks can find dense subgraphs according to a given motif.
Role-aware variant solves the role confusion problem by creating multiple quark numbers for each motif \(M\) .
Overall, quark decomposition is versatile, efficient, and extendible.
For future work, it would be interesting to investigate the other byproducts of the quark decomposition, such as hierarchy structure. Our initial results show limited success; detailed and meaningful hierarchies are rare for the most motifs. Theoretical and empirical analysis of the impact of the input motifs, \(M, N\) , on the hierarchy structure would be interesting .
Also, adapting the quark decomposition for numerical attributes on nodes/edges would be promising.


This research was supported by NSF-1910063 award, JP Morgan Chase and Company Faculty Research Award, and used resources of the Center for Computational Research at the University at Buffalo [47]} and the National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231.
