With the rapid development of Web 2.0 technology, online social media have become increasingly popular and influential. In online social media, such as Reddit, Digg, Twitter and Weibo, users can post, vote and comment posted stories and other users’ comments. Users, together with story and corresponding feedbacks, form a heterogeneous information diffusion network. To analyze how information diffuses among different users, we need to better understand a few key factors, including (1) frequent appearing sub-structures, called motifs, in the network and (2) evolution of a motif. In this paper, we explore the MOtif-based Sequential Pattern (MOSP) to facilitate the understanding of motif evolution along the time. Furthermore, we propose Topological MOSP (T-MOSP) and Propagative MOSP (P-MOSP) to observe frequent sequence of motifs in different angles. Facing a large volume of graph data, Motif mining is time-consuming. Therefore, we devise efficient mining algorithms, namely, Motif-Mine and Lattice-based Temporal Sequential Pattern Mine (LTSP-Mine), to discover motifs and sequences of motifs, respectively. Extensive experimental evaluation on Digg demonstrates that T-MOSP and P-MOSP discovered by the proposed algorithms can efficiently and effectively capture and summarize the information diffusion patterns in online social media.