Structure-Aware Approximate Hypergraph Motif Counting for Higher-Order Interaction Analysis

Hypergraph motifs characterize recurring local interaction patterns among hyperedges and provide structural signatures for higher-order network analysis. Exact motif counting is computationally expensive on large hypergraphs because it requires examining numerous connected hyperedge triples. Existing hyperwedge-based estimators reduce this cost while preserving unbiased estimation. However, they typically sample hyperwedges uniformly, assigning the same sampling probability to structurally different hyperwedges. Since hyperwedges may vary in their overlap patterns, local connectivity, and contributions to motif counts, uniform sampling can be inefficient when such structural heterogeneity is substantial. To address this limitation, we propose a structure-aware stratified hyperwedge sampling framework (SASH) for approximate motif counting. SASH stratifies hyperwedges by pairwise overlap size and endpoint projected-degree characteristics, capturing complementary aspects of overlap structure and local connectivity, and samples without replacement within strata. Stratum-specific inverse inclusion-probability weighting with motif-specific multiplicity correction preserves unbiased estimation. We prove estimator unbiasedness under feasible sampling budgets, derive its variance, and analyze the expected time complexity. Experiments on eight real-world hypergraphs show that, compared with the state-of-the-art MoCHy-A+, SASH achieves a mean relative-error reduction of 23.13% across datasets, with a maximum reduction of 41.06%, while attaining lower average end-to-end running time on all eight datasets. Ablation results show that structure-aware stratification and within-stratum sampling without replacement provide complementary benefits for estimation accuracy.