Home Big Data Mining and Analytics Article
PDF (4.9 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

Census and Analysis of Higher-Order Interactions in Real-World Hypergraphs

School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
School of Science, Computing and Engineering Technologies, Swinburne University of Technology, Melbourne 3122, Australia
Show Author Information

Abstract

Complex systems can be more accurately described by higher-order interactions among multiple units. Hypergraphs excel at depicting these interactions, surpassing the binary limitations of traditional graphs. However, retrieving valuable information from hypergraphs is often challenging due to their intricate interconnections. To address this issue, we introduce a new category of structural patterns, hypermotifs, which are defined as statistically significant local structures formed by interconnected hyperedges. We propose a systematic framework for hypermotif extraction. This framework features the encoding, census, and evaluation of higher-order patterns, effectively overcoming their inherent complexity and diversity. Our experimental results demonstrate that hypermotifs can serve as higher-order fingerprints of real-world hypergraphs, helping to identify hypergraph classes based on network functions. These motifs potentially represent preferential attachments and key modules in real-world hypergraphs, arising from specific mechanisms or constraints. Our work validates the efficacy of hypermotifs in exploring hypergraphs, offering a powerful tool for revealing the design principles and underlying dynamics of interacting systems.

Keywords

complex systemshigher-order interactionshypergraphshigher-order motifshyperlink prediction

References

[1]

L. Hagen and A. B. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., vol. 11, no. 9, pp. 1074–1085, 1992.

Crossref Google Scholar
[2]

J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905, 2000.

Crossref Google Scholar
[3]

D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature, vol. 393, pp. 440–442, 1998.

Crossref Google Scholar
[4]

S. Milgram, The small world problem, Psychology today, vol. 2, no. 1, pp. 60–67, 1967.

Google Scholar
[5]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks, Science, vol. 298, no. 5594, pp. 824–827, 2002.

Google Scholar
[6]

S. Fortunato, Community detection in graphs, Phys. Rep., vol. 486, nos. 3–5, pp. 75–174, 2010.

Crossref Google Scholar
[7]

A. Galeotti, S. Goyal, M. O. Jackson, F. Vega-Redondo, and L. Yariv, Network games, Rev. Econ. Stud., vol. 77, no. 1, pp. 218–244, 2009.

Crossref Google Scholar
[8]

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, Complex networks: Structure and dynamics, Phys. Rep., vol. 424, nos. 4&5, pp. 175–308, 2006.

Crossref Google Scholar
[9]

A. R. Benson, D. F. Gleich, and J. Leskovec, Higher-order organization of complex networks, Science, vol. 353, no. 6295, pp. 163–166, 2016.

Crossref Google Scholar
[10]

J. Grilli, G. Barabás, M. J. Michalska-Smith, and S. Allesina, Higher-order interactions stabilize dynamics in competitive network models, Nature, vol. 548, no. 7666, pp. 210–213, 2017.

Crossref Google Scholar
[11]

A. E. Sizemore, C. Giusti, A. Kahn, J. M. Vettel, R. F. Betzel, and D. S. Bassett, Cliques and cavities in the human connectome, J. Comput. Neurosci., vol. 44, no. 1, pp. 115–145, 2018.

Crossref Google Scholar
[12]

F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. Ferraz de Arruda, B. Franceschiello, I. Iacopini, S. Kéfi, V. Latora, Y. Moreno, et al., The physics of higher-order interactions in complex systems, Nat. Phys., vol. 17, no. 10, pp. 1093–1098, 2021.

Google Scholar
[13]

K. A. Murgas, E. Saucan, and R. Sandhu, Hypergraph geometry reflects higher-order dynamics in protein interaction networks, Sci. Rep., vol. 12, no. 1, p. 20879, 2022.

Crossref Google Scholar
[14]
A. Bretto, Hypergraph theory, An introduction. Mathematical Engineering. Cham, Switzerland: Springer, 2013.
[15]
D. Yang, B. Qu, J. Yang, and P. Cudre-Mauroux, Revisiting user mobility and social relationships in LBSNs: A hypergraph embedding approach, in Proc. World Wide Web Conference, San Francisco, CA, USA, 2019, pp. 2147–2157.
[16]

F. Battiston, G. Cencetti, I. Iacopini, V. Latora, M. Lucas, A. Patania, J.-G. Young, and G. Petri, Networks beyond pairwise interactions: Structure and dynamics, Phys. Rep., vol. 874, pp. 1–92, 2020.

Google Scholar
[17]

S. G. Aksoy, C. Joslyn, C. Ortiz Marrero, B. Praggastis, and E. Purvine, Hypernetwork science via high-order hypergraph walks, EPJ Data Sci., vol. 9, no. 1, p. 16, 2020.

Crossref Google Scholar
[18]
S.-E. Yoon, H. Song, K. Shin, and Y. Yi, How much and when do we need higher-order information in hypergraphs? A case study on hyperedge prediction, in Proc. The Web Conf., Taipei, China, 2020, pp. 2627–2633.
[19]

A. Antelmi, G. Cordasco, M. Polato, V. Scarano, C. Spagnuolo, and D. Yang, A survey on hypergraph representation learning, ACM Comput. Surv., vol. 56, no. 1, pp. 1–38, 2024.

Google Scholar
[20]
D. Zhou, J. Huang, and B. Schölkopf, Learning with hypergraphs: Clustering, classification, and embedding, in Advances in Neural Information Processing Systems, Cambridge, MA, USA, The MIT Press, 2007. pp. 1601–1608.
[21]
C. Yang, R. Wang, S. Yao, and T. Abdelzaher, Semi-supervised hypergraph node classification on hypergraph line expansion, in Proc. 31st ACM Int. Conf. Information & Knowledge Management. Atlanta, GA, USA, 2022, pp. 2352–2361.
[22]
Y. Dong, W. Sawin, and Y. Bengio, HNHN: Hypergraph networks with hyperedge neurons, arXiv preprint arXiv:2006.12278, 2020.
[23]

A. P. Millán, J. J. Torres, and G. Bianconi, Explosive higher-order kuramoto dynamics on simplicial complexes, Phys. Rev. Lett., vol. 124, no. 21, p. 218301, 2020.

Crossref Google Scholar
[24]

L. Neuhäuser, A. Mellor, and R. Lambiotte, Multibody interactions and nonlinear consensus dynamics on networked systems, Phys. Rev. E, vol. 101, no. 3, p. 032310, 2020.

Google Scholar
[25]
S. Chowdhary, A. Kumar, G. Cencetti, I. Iacopini, and F. Battiston, Simplicial contagion in temporal higher-order networks, J. Phys. Complex., vol. 2, no. 3, p. 035019, 2021.
[26]

U. Alvarez-Rodriguez, F. Battiston, G. F. de Arruda, Y. Moreno, M. Perc, and V. Latora, Evolutionary dynamics of higher-order interactions in social networks, Nat. Hum. Behav., vol. 5, no. 5, pp. 586–595, 2021.

Google Scholar
[27]

N. Yuvaraj, K. Srihari, S. Chandragandhi, R. A. Raja, G. Dhiman, and A. Kaur, Analysis of protein-ligand interactions of SARS-Cov-2 against selective drug using deep neural networks, Big Data Mining and Analytics, vol. 4, no. 2, pp. 76–83, 2021.

Crossref Google Scholar
[28]

A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg, Simplicial closure and higher-order link prediction, Proc. Natl. Acad. Sci. U. S. A., vol. 115, no. 48, pp. E11221–E11230, 2018.

Google Scholar
[29]
Y. Feng, H. You, Z. Zhang, R. Ji, and Y. Gao, Hypergraph neural networks, in Proceedings of the 33rd AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 2019, pp. 3558–3565.
[30]

T. Carletti, F. Battiston, G. Cencetti, and D. Fanelli, Random walks on hypergraphs, Phys. Rev. E, vol. 101, no. 2, p. 022308, 2020.

Google Scholar
[31]

S. Bai, F. Zhang, and P. H. S. Torr, Hypergraph convolution and hypergraph attention, Pattern Recognit., vol. 110, p. 107637, 2021.

Google Scholar
[32]
J. Huang and J. Yang, UniGNN: A unified framework for graph and hypergraph neural networks, arXiv preprint arXiv:2105.00956, 2021.
[33]
L. Li, G. Lü, C. Zheng, R. Lin, and Y. Su, MHCLSyn: Multi-View Hypergraph Contrastive Learning for Synergistic Drug Combination Prediction, Big Data Mining and Analytics, vol. 7, no. 4, pp. 1273–1286, 2024.
[34]
M. T. Do, S.-E. Yoon, B. Hooi, and K. Shin, Structural patterns and generative models of real-world hypergraphs, in Proc. 26th ACM SIGKDD Int. Conf. Knowledge Discovery & Data Mining, Virtual Event, 2020, pp.176–186.
[35]
Y. Kook, J. Ko, and K. Shin, Evolution of real-world hypergraphs: Patterns and models without oracles, in Proc. IEEE Int. Conf. Data Mining, Sorrento, Italy, 2020, pp. 272–281.
[36]
G. Lee, M. Choe, and K. Shin, How do hyperedges overlap in real-world hypergraphs?—patterns, measures, and generators, in Proc. Web Conf., Ljubljana Slovenia, 2021 pp. 3396–3407.
[37]

R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon, Superfamilies of evolved and designed networks, Science, vol. 303, no. 5663, pp. 1538–1542, 2004.

Google Scholar
[38]

S. Maslov and K. Sneppen, Specificity and stability in topology of protein networks, Science, vol. 296, no. 5569, pp. 910–913, 2002.

Crossref Google Scholar
[39]
E. G. Allan Jr., and W. H. Turkett, E. W. Fulp, Using network motifs to identify application protocols, in Proc. IEEE Global Telecommunications Conference, Honolulu, HI, USA, 2009, pp. 1–7.
[40]

F. Saracco, R. Di Clemente, A. Gabrielli, and T. Squartini, Detecting early signs of the 2007–2008 crisis in the world trade, Sci. Rep., vol. 6, no. 1, p. 30286, 2016.

Crossref Google Scholar
[41]

L. Chen, X. Qu, M. Cao, Y. Zhou, W. Li, B. Liang, W. Li, W. He, C. Feng, X. Jia, et al., Identification of breast cancer patients based on human signaling network motifs, Sci. Rep., vol. 3, no. 1, p. 3368, 2013.

Crossref Google Scholar
[42]

S. R. McGee, C. Tibiche, M. Trifiro, and E. Wang, Network analysis reveals a signaling regulatory loop in the PIK3CA-mutated breast cancer predicting survival outcome, Genom. Proteom. Bioinform., vol. 15, no. 2, pp. 121–129, 2017.

Google Scholar
[43]

N. Pržulj, D. G. Corneil, and I. Jurisica, Modeling interactome: Scale-free or geometric, Bioinformatics, vol. 20, no. 18, pp. 3508–3515, 2004.

Google Scholar
[44]

I. Albert and R. Albert, Conserved network motifs allow protein-protein interaction prediction, Bioinformatics, vol. 20, no. 18, pp. 3346–3352, 2004.

Crossref Google Scholar
[45]

S. Mangan and U. Alon, Structure and function of the feed-forward loop network motif, Proc. Natl. Acad. Sci. U. S. A., vol. 100, no. 21, pp. 11980–11985, 2003.

Google Scholar
[46]

D. Zhu and Z. S. Qin, Structural comparison of metabolic networks in selected single cell organisms, BMC Bioinform., vol. 6, no. 1, p. 8, 2005.

Google Scholar
[47]

U. Alon, Network motifs: Theory and experimental approaches, Nat. Rev. Genet., vol. 8, no. 6, pp. 450–461, 2007.

Crossref Google Scholar
[48]
B. H. Junker and F. Schreiber, Analysis of biological networks. Hoboken, NJ, USA: Wiley Online Library, 2008.
[49]
M. Li, B. Zhao, Y. Li, P. Ding, R. Yin, S. Kan, and M. Zeng, SGCL-LncLoc: An interpretable deep learning model for improving incrna subcellular localization prediction with supervised graph contrastive learning, Big Data Mining and Analytics, vol. 7, no. 3, pp. 765–780, 2024.
[50]

N. Kashtan, S. Itzkovitz, R. Milo, and U. Alon, Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs, Bioinformatics, vol. 20, no. 11, pp. 1746–1758, 2004.

Crossref Google Scholar
[51]
F. Schreiber and H. Schwöbbermeyer, MAVisto: A tool for the exploration of network motifs, Bioinformatics, vol. 21, no. 17, pp. 3572–3574, 2005.
[52]

S. Wernicke, Efficient detection of network motifs, IEEE/ACM Trans. Comput. Biol. Bioinform., vol. 3, no. 4, pp. 347–359, 2006.

Crossref Google Scholar
[53]

Z. R. M. Kashani, H. Ahrabian, E. Elahi, A. Nowzari-Dalini, E. S. Ansari, S. Asadi, S. Mohammadi, F. Schreiber, and A. Masoudi-Nejad, Kavosh: A new algorithm for finding network motifs, BMC Bioinform., vol. 10, no. 1, p. 318, 2009.

Crossref Google Scholar
[54]
P. Ribeiro and F. Silva, G-tries: An efficient data structure for discovering network motifs, in Proc. ACM Symp. on Applied Computing, Sierre, Switzerland, 2010, pp. 1559–1566.
[55]
D. Marcus and Y. Shavitt, RAGE–A rapid graphlet enumerator for large networks, Comput. Netw., vol. 56, no. 2, pp. 810–819, 2012.
[56]

N. Shervashidze, S. V. N. Vishwanathan, T. H. Petri, K. Mehlhorn, and K. M. Borgwardt, Efficient graphlet kernels for large graph comparison, J. Mach. Learn. Res., vol. 5, pp. 488–495, 2009.

Google Scholar
[57]

B. MCKAY, Practical graph isomorphism, Congressus Numeranitum, vol. 30, pp. 45–87, 1981

Google Scholar
[58]
J. Jonsson, Simplicial Complexes of Graphs. Berlin, Germany: Springer, 2008.
[59]
C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F.Montufar, P. Lio, and M. Bronstein, Weisfeiler and lehman go topological: Message passing simplicial networks, in Proc. 38th Int. Conf. on Machine Learning, Virtual Event, 2021, pp. 1026–1037.
[60]
R. Yang, F. Sala, and P. Bogdan, Efficient representation learning for higher-order data with simplicial complexes, in Proc. the First Learning on Graphs Conf., Virtual Event, 2022, pp. 1–13.
[61]
A. Ramsay and R. D. Richtmyer, Introduction to hyperbolic geometry. Boulder, CO, USA: Springer Science & Business Media, 2013.
[62]
Q. Liu, M. Nickel, and D. Kiela, Hyperbolic graph neural networks, Advances in neural information processing systems, vol. 32, pp. 8230–8241, 2019.
[63]
P. Kyriakis, I. Fostiropoulos, and P. Bogdan, Learning hyperbolic representations of topological features, arXiv preprint arXiv:2103.09273, 2021.
[64]

Y. Xue and P. Bogdan, Reconstructing missing complex networks against adversarial interventions, Nat. Commun., vol. 10, no. 1, p. 1738, 2019.

Google Scholar
[65]

X. Xiao, H. Chen, and P. Bogdan, Deciphering the generating rules and functionalities of complex networks, Sci. Rep., vol. 11, no. 1, p. 22964, 2021.

Crossref Google Scholar
[66]

R. Yang and P. Bogdan, Controlling the multifractal generating measures of complex networks, Sci. Rep., vol. 10, no. 1, p. 5541, 2020.

Google Scholar
[67]

R. Yang, F. Sala, and P. Bogdan, Hidden network generating rules from partially observed complex networks, Commun. Phys., vol. 4, no. 1, p. 199, 2021.

Crossref Google Scholar
[68]

G. Lee, J. Ko, and K. Shin, Hypergraph motifs, Proc. VLDB Endow., vol. 13, no. 12, pp. 2256–2269, 2020.

Crossref Google Scholar
[69]

Q. F. Lotito, F. Musciotto, A. Montresor, and F. Battiston, Higher-order motif analysis in hypergraphs, Commun. Phys., vol. 5, no. 1, p. 79, 2022.

Google Scholar
[70]

Q. F. Lotito, F. Musciotto, F. Battiston, and A. Montresor, Exact and sampling methods for mining higher-order motifs in large hypergraphs, Computing, vol. 106, no. 2, pp. 475–494, 2024.

Crossref Google Scholar
[71]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., vol. 51, no. 3, pp. 455–500, 2009.

Crossref Google Scholar
[72]

G. Li, L. Qi, and G. Yu, The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory, Numer. Linear Algebra Appl., vol. 20, no. 6, pp. 1001–1029, 2013.

Crossref Google Scholar
[73]

K. J. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor, Graphs Comb., vol. 30, no. 5, pp. 1233–1248, 2014.

Crossref Google Scholar
[74]

A. M. Feist, D. C. Zielinski, J. D. Orth, J. Schellenberger, M. J. Herrgard, and B. Ø. Palsson, Model-driven evaluation of the production potential for growth-coupled products of Escherichia coli, Metab. Eng., vol. 12, no. 3, pp. 173–186, 2010.

Crossref Google Scholar
[75]

R. Mastrandrea, J. Fournet, and A. Barrat, Contact patterns in a high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys, PLoS One, vol. 10, no. 9, p. e0136497, 2015.

Crossref Google Scholar
[76]
Physical Review Journals, APS Datasets for research, https://journals.aps.org/datasets, 2021.
[77]

J. D. Orth, T. M. Conrad, J. Na, J. A. Lerman, H. Nam, A. M. Feist, and B. Ø. Palsson, A comprehensive genome-scale reconstruction of Escherichia coli metabolism—2011, Mol. Syst. Biol., vol. 7, no. 1, p. 535, 2011.

Google Scholar
[78]
A. Sinha, Z. Shen, Y. Song, H. Ma, D. Eide, B.-J P. Hsu, and K. Wang, An overview of microsoft academic service (MAS) and applications, in Proc. 24th Int. Conf. World Wide Web, Florence, Italy, 2015, pp. 243–246.
[79]
I. Amburg, N. Veldt, and A. Benson, Clustering in graphs and hypergraphs with categorical edge labels, in Proc. The Web Conf., Taipei, China, 2020, pp. 706–717.
[80]
C. J. Alpert, The ISPD98 circuit benchmark suite, in Proc. 1998 Int. Symp. on Physical design, Monterey, CA, USA, 1998, pp. 80–85.
[81]
S. Schlag, V. Henne, T. Heuer, H. Meyerhenke, P. Sanders, and C. Schulz, K-way hypergraph partitioning via n-level recursive bisection, in Proc. Eighteenth Workshop on Algorithm Engineering and Experiments, Arlington, VA, USA, 2016, pp. 53–67.
[82]

P. S. Chodrow, Configuration models of random hypergraphs, J. Complex Netw., vol. 8, no. 3, p. cnaa018, 2020.

Crossref Google Scholar
[83]

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al., Scikit-learn: Machine learning in python, the Journal of machine Learning research, vol. 12, pp. 2825–2830, 2011.

Google Scholar
[84]
N. Yadati, V. Nitin, M. Nimishakavi, P. Yadav, A. Louis, and P. Talukdar, NHP: Neural hypergraph link prediction, in Proc. 29th ACM Int. Conf. Information & Knowledge Management, Virtual Event, 2020, pp.1705–1714.
[85]
R. Zhang, Y. Zou, and J. Ma, Hyper-SAGNN: A self-attention based graph neural network for hypergraphs, arXiv preprint arXiv:1911.02613, 2019.
[86]
S. Maleki, D. Saless, D. P. Wall, and K. Pingali, HyperNetVec: Fast and scalable hierarchical embedding for hypergraphs, Porto, Portugal, 2022, pp. 169–183.
[87]

X.-J. Xu, C. Deng, and L.-J. Zhang, Hyperlink prediction via local random walks and Jensen–Shannon divergence, J. Stat. Mech., vol. 2023, no. 3, p. 033402, 2023.

Google Scholar
Big Data Mining and Analytics
Volume 8 Issue 2,
April 2025
Pages 383-406
DOI: 10.26599/BDMA.2024.9020091
Cite this article:
Meng X, Zhai X, Fei G, et al. Census and Analysis of Higher-Order Interactions in Real-World Hypergraphs. Big Data Mining and Analytics, 2025, 8(2): 383-406. https://doi.org/10.26599/BDMA.2024.9020091
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return