  A motif is a frequently occurring subgraph of a given directed or undirected
graph $G$. Motifs capture higher order organizational structure of $G$ beyond
edge relationships, and, therefore, have found wide applications such as in
graph clustering, community detection, and analysis of biological and physical
networks to name a few. In these applications, the cut structure of motifs
plays a crucial role as vertices are partitioned into clusters by cuts whose
conductance is based on the number of instances of a particular motif, as
opposed to just the number of edges, crossing the cuts.
  In this paper, we introduce the concept of a motif cut sparsifier. We show
that one can compute in polynomial time a sparse weighted subgraph $G'$ with
only $\widetilde{O}(n/\epsilon^2)$ edges such that for every cut, the weighted
number of copies of $M$ crossing the cut in $G'$ is within a $1+\epsilon$
factor of the number of copies of $M$ crossing the cut in $G$, for every
constant size motif $M$.
  Our work carefully combines the viewpoints of both graph sparsification and
hypergraph sparsification. We sample edges which requires us to extend and
strengthen the concept of cut sparsifiers introduced in the seminal work of to
the motif setting. We adapt the importance sampling framework through the
viewpoint of hypergraph sparsification by deriving the edge sampling
probabilities from the strong connectivity values of a hypergraph whose
hyperedges represent motif instances. Finally, an iterative sparsification
primitive inspired by both viewpoints is used to reduce the number of edges in
$G$ to nearly linear.
  In addition, we present a strong lower bound ruling out a similar result for
sparsification with respect to induced occurrences of motifs.
