Motif-based densest subgraph and clique finding. There are a few works in the literature that studies the motif-driven densest subgraph problem. For constant size cliques, which can be thought of as motifs in simple undirected graphs, Tsourakakis introduced the \(k\) -clique densest subgraph problem [1]} to generalize the classical densest subgraph discovery [2]} for \(k\) -cliques (\(k>2\) ). Analogous to finding the subgraph with the maximum average degree, Tsourakakis proposed to find the subgraphs that have a maximum average triangle (or \(k\) -clique) count per node.
More recently, Fang et al. proposed exact and approximate algorithms for the same problem [3]} and Hu et al. considered heterogeneous information networks with specific schemas to find maximal motif-cliques [4]}.
Note that our problem setup is more general and we aim to find multiple subgraphs that are not necessarily perfect cliques but always significantly dense.
