Hypergraph Motifs:
Concepts, Algorithms, and Discoveries

Overview

We propose Hypergraph Motifs (h-motifs), whose occurrences capture local structural patterns of real-world hypergraphs.
H-motifs describe connectivity patterns of three connected hyperedges with the following properties:

• Exhaustive: h-motifs capture connectivity patterns of all possible three connected hyperedges
• Unique: connectivity pattern of any three connected hyperedges is captured by exactly one h-motif
• Size independent: h-motifs capture connectivity patterns independently of the sizes of hyperedges

MoCHy (Motif Counting in Hypergraphs) is a family of parallel algorithms for counting h-motifs' occurrences in a hypergraph.

• MoCHy-E (MoCHy Exact) exactly counts the instances of each h-motif.
• MoCHy-A (MoCHy Approximate) approximately counts the instances of each h-motif.
• The advanced approximate version MoCHy-A⁺ is up to 25X more accurate than MoCHy-A, and it is up to 32X faster than MoCHy-E.

Paper

• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
  Geon Lee, Jihoon Ko, and Kijung Shin
  VLDB 2020.
  [arXiv] [BIBTEX]
  
  

Code

The source code used in the paper is available. [Code]

Datasets

We use the following 11 real-world hypergraphs from 5 different domains after removing duplicated hyperedges: