FSM: Fast and scalable network motif discovery for exploring higher-order network organizations

Tao Wang, Jiajie Peng, Qidi Peng, Yadong Wang, Jin Chen

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Networks exhibit rich and diverse higher-order organizational structures. Network motifs, which are recurring significant patterns of inter-connections, are recognized as fundamental units to study the higher-order organizations of networks. However, the principle of selecting representative network motifs for local motif based clustering remains largely unexplored. We present a scalable algorithm called FSM for network motif discovery. FSM is advantageous in twofold. First, it accelerates the motif discovery process by effectively reducing the number of times for subgraph isomorphism labeling. Second, FSM adopts multiple heuristic optimizations for subgraph enumeration and classification to further improve its performance. Experimental results on biological networks show that, comparing with the existing network motif discovery algorithm, FSM is more efficient on computational efficiency and memory usage. Furthermore, with the large, frequent, and sparse network motifs discovered by FSM, the higher-order organizational structures of biological networks were successfully revealed, indicating that FSM is suitable to select network representative network motifs for exploring high-order network organizations.

Original languageEnglish
Pages (from-to)83-93
Number of pages11
StatePublished - Feb 15 2020

Bibliographical note

Funding Information:
This project is supported by US NSF ABI (grant nos. 1458556, 1716340), US DOE BES (grant no. DEFG0291ER20021), NSFC (grant nos. 61702421, 61332014), National Key Research and Development Program of China (Nos: 2017YFC0907503 and 2017YFC1201201). This manuscript is based on an earlier work presented at the IEEE International Conference on Bioinformatics and Biomedicine (BIBM-2018).

Publisher Copyright:
© 2019 Elsevier Inc.


  • Biological network
  • Higher-order organization
  • Network motif

ASJC Scopus subject areas

  • Molecular Biology
  • Biochemistry, Genetics and Molecular Biology (all)


Dive into the research topics of 'FSM: Fast and scalable network motif discovery for exploring higher-order network organizations'. Together they form a unique fingerprint.

Cite this