EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Yuhang Su, Lin Wang, Shuo Zhao

Entropy · 29.10.2026 · 28 (11) · 1193

DOI: 10.3390/e28111193 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Entropy, online erschienen am 29.10.2026. Verfasst von Yuhang Su und 2 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Liaoning Province.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Natural Science Foundation of China
  • Natural Science Foundation of Liaoning Province

Zitieren

APA

Su, Y., Wang, L., & Zhao, S. (2026). Structure-Aware Approximate Hypergraph Motif Counting for Higher-Order Interaction Analysis. Entropy, 28(11), 1193. https://doi.org/10.3390/e28111193

Vancouver

Su Y, Wang L, Zhao S. Structure-Aware Approximate Hypergraph Motif Counting for Higher-Order Interaction Analysis. Entropy. 2026;28(11):1193. doi:10.3390/e28111193

BibTeX
@article{Su2026,
  author = {Su, Yuhang and Wang, Lin and Zhao, Shuo},
  title = {Structure-Aware Approximate Hypergraph Motif Counting for Higher-Order Interaction Analysis},
  journal = {Entropy},
  year = {2026},
  volume = {28},
  number = {11},
  pages = {1193},
  doi = {10.3390/e28111193}
}
Infokarte | EUVIMED

Artikeldaten derzeit nicht verfügbar.

Recherche