  Finding dense subnetworks, with density based on edges or more complex
structures, such as subgraphs or $k$-cliques, is a fundamental algorithmic
problem with many applications. While the problem has been studied extensively
in static networks, much remains to be explored for temporal networks.
  In this work we introduce the novel problem of identifying the temporal motif
densest subnetwork, i.e., the densest subnetwork with respect to temporal
motifs, which are high-order patterns characterizing temporal networks. This
problem significantly differs from analogous formulations for dense temporal
(or static) subnetworks as these do not account for temporal motifs.
Identifying temporal motifs is an extremely challenging task, and thus,
efficient methods are required. To this end, we design two novel randomized
approximation algorithms with rigorous probabilistic guarantees that provide
high-quality solutions. We perform extensive experiments showing that our
methods outperform baselines. Furthermore, our algorithms scale on networks
with up to billions of temporal edges, while baselines cannot handle such large
networks. We use our techniques to analyze a financial network and show that
our formulation reveals important network structures, such as bursty temporal
events and communities of users with similar interests.
