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 [1]}) are obtained from SNAP [2]}.
 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  [3]}, [4]}.
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 [5]} 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 [5]}).
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  [7]}.
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 [8]}, 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) [5]}. 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) [10]}, InfoMap [11]}, and Louvain method [12]}.
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 [13]}, [5]} by four metrics: Adjusted Rand Index (ARI), F1 score, Normalized Mutual Information (NMI), Purity [15]}.
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 [16]}.
We considered the last interactions in the datasets.
We also consider epinions, a who-trust-whom social network [17]},
and slashdot which contains the self-tagged friend/foe relationships [18]}.
All are obtained from SNAP [2]}.
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 [20]}, 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 [21]}. 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 [22]}.
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 [23]}.
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 [24]}, [25]}.
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 [8]}.
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 [27]} 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.
