Top

Data Mining and Knowledge Discovery

Published in:

08-08-2023

Reciprocity in directed hypergraphs: measures, findings, and generators

Authors: Sunwoo Kim, Minyoung Choe, Jaemin Yoo, Kijung Shin

Published in: Data Mining and Knowledge Discovery | Issue 6/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Group interactions are prevalent in a variety of areas. Many of them, including email exchanges, chemical reactions, and bitcoin transactions, are directional, and thus they are naturally modeled as directed hypergraphs, where each hyperarc consists of the set of source nodes and the set of destination nodes. For directed graphs, which are a special case of directed hypergraphs, reciprocity has played a key role as a fundamental graph statistic in revealing organizing principles of graphs and in solving graph learning tasks. For general directed hypergraphs, however, even no systematic measure of reciprocity has been developed. In this work, we investigate the reciprocity of 11 real-world hypergraphs. To this end, we first introduce eight axioms that any reasonable measure of reciprocity should satisfy. Second, we propose HyperRec, a family of principled measures of hypergraph reciprocity that satisfy all the axioms. Third, we develop FastHyperRec, a fast and exact algorithm for computing the measures. Fourth, using them, we examine 11 real-world hypergraphs and discover patterns that distinguish them from random hypergraphs. Lastly, we propose ReDi, an intuitive generative model for directed hypergraphs exhibiting the patterns.

previous article trie-nlg: trie context augmentation to improve personalized query auto-completion for short and unseen prefixes

next article Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

This work is an extended version of Kim et al. (2022), which was presented at the 22nd IEEE International Conference on Data Mining (ICDM 2022). In the extended version, we introduce several theoretical extensions: (a) generalized versions of the axioms in Sect. :3.1 and a proof of Theorem 1 for the generalized versions (Appendix 1), (b) seven baseline hypergraph reciprocity measures (Sect. 3.3), (c) a proof that none of the baseline measures satisfies all the axioms (Appendix 2), and (d) proofs of Theorem 2 and Corollary 1 (Appendix 1). In addition, we conduct additional experiments regarding (a) the efficiency of FastHyperRec (Fig. 4 and Table 3 in Sect. 3.4), (b) the statistical significance of Observation 1 (Table 8 in Sect. 4.2), (c) the robustness of HyperRec with respect to the choice of \(\alpha\) (Tables 7 and 9 in Sect. 4.2), and (d) the verification of Observation 2 in 12 more real and synthetic hypergraphs (Fig. 5 in Sect. 4.2 and Fig. 7 in Sect. 5.2). At last, we provide one additional reciprocal pattern in real-world hypergraph (Observation 3: Fig. 6 in Sect. 4.2) and verify whether ReDi can reproduce this pattern.

Note that all arcs in \(R_{i}\) are used in computing the reciprocity of \(e_{i}\), and thus it does not correspond to a search space.

Note that, to improve legibility, we remove data points that lie outside the interquartile range (i.e., \([Q_{1} - 1.5(Q_{3} - Q_{1}), Q_{3} + 1.5(Q_{3} - Q_{1})]\), where \(Q_{3}\) and \(Q_{1}\) denote the third and first quantile of the corresponding distribution) from the box plots.

The search space of \(\beta _{1}\) is (a) \([0.05, 0.1, \ldots , 0.6]\) for the small datasets where \(|V \vert \le 10^{4}\), and (b) \([0.001, 0.0015, \ldots ,0.005]\) for the dense large datasets where \(|V \vert > 10^{4}\) and \({|E \vert }/{|V \vert } \ge 3\), and (c) \([0.01, 0.02, \ldots 0.15]\) for the other sparse large datasets. The search space of \(\beta _{2}\) is fixed to \(\in [0.1, 0.1, \ldots , 0.5]\) for all datasets.

As bitcoin transactions are made among randomly chosen accounts, the repetition of (partial) group interactions is rarely observed. Due to this intrinsic characteristic of the datasets, we use the degrees of individual nodes instead of the degrees of groups when ReDi and the baseline model are given the statistics from bitcoin datasets. The same strategy is also used for the baseline model when the input statistics are from the q &a server dataset. Without the strategy, the baseline model takes more than 12 hours.

Note that \((1+\frac{1}{x})^{x}\) is a well-known increasing function whose limit as \(x\rightarrow \infty\) is e. Thus, \(\log (1+\frac{1}{x})^{x}=x\log (1+\frac{1}{x})\) is also an increasing function, and since \(x'=1/x\) is decreasing at \(x>0\), \(x'\log (1+\frac{1}{x'})=\frac{1}{x}\log (1+x)\) is decreasing at \(x>0\).

We use the venues listed at Wikipedia (2022).

Akoglu L, Vaz de Melo PO, Faloutsos C (2012) Quantifying reciprocity in large weighted communication networks. In: Advances in knowledge discovery and data mining: 16th Pacific-Asia conference, PAKDD 2012, Kuala Lumpur, Malaysia, May 29–June 1, 2012, Proceedings, Part II 16. Springer, pp 85–96. https://doi.org/10.1007/978-3-642-30220-6_8

Albert R, Barabási AL (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47. https://doi.org/10.1103/RevModPhys.74.47MathSciNetCrossRefMATH

Archive I (2022) Stack exchange data dump question answering dataset of stack exchange inc. https://archive.org/details/stackexchange

Benson AR, Abebe R, Schaub MT et al (2018a) Simplicial closure and higher-order link prediction. Proc Natl Acad Sci 115(48):E11,221-E11,230. https://doi.org/10.1073/pnas.1800683115CrossRef

Benson AR, Kumar R, Tomkins A (2018b) Sequences of sets. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp 1148–1157. https://doi.org/10.1145/3219819.3220100

Bu F, Lee G, Shin K (2023) Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applications. arXiv preprint arXiv:2301.08440. https://doi.org/10.48550/arXiv.2301.08440

Chodrow P, Mellor A (2020) Annotated hypergraphs: models and applications. Appl Netw Sci 5:1–25. https://doi.org/10.1007/s41109-020-0252-yCrossRef

Choo H, Shin K (2022) On the persistence of higher-order interactions in real-world hypergraphs. In: Proceedings of the 2022 SIAM international conference on data mining (SDM). SIAM, pp 163–171. https://doi.org/10.1137/1.9781611977172.19

Cirkovic D, Wang T, Resnick S (2022) Preferential attachment with reciprocity: properties and estimation. arXiv preprint arXiv:2201.03769. https://doi.org/10.48550/arXiv.2201.03769

Comrie C, Kleinberg J (2021) Hypergraph ego-networks and their temporal evolution. In: 2021 IEEE international conference on data mining (ICDM). IEEE, pp 91–100. https://doi.org/10.1109/ICDM51629.2021.00019

Do MT, Yoon Se, Hooi B et al (2020) Structural patterns and generative models of real-world hypergraphs. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp 176–186. https://doi.org/10.1145/3394486.3403060

Dong Y, Sawin W, Bengio Y (2020) Hnhn: hypergraph networks with hyperedge neurons. arXiv preprint arXiv:2006.12278. https://doi.org/10.48550/arXiv.2006.12278

Garlaschelli D, Loffredo MI (2004) Fitness-dependent topological properties of the world trade web. Phys Rev Lett 93(18):188,701. https://doi.org/10.1103/PhysRevLett.93.188701CrossRef

Hidalgo CA, Rodríguez-Sickert C (2008) The dynamics of a mobile phone network. Phys A Stat Mech Appl 387(12):3017–3024. https://doi.org/10.1016/j.physa.2008.01.073CrossRef

Kim S, Choe M, Yoo J et al (2022) Reciprocity in directed hypergraphs: measures, findings, and generators. In: The 22nd IEEE international conference on data mining, ICDM 2022. IEEE Computer Society. https://doi.org/10.1109/ICDM54844.2022.00122

Kook Y, Ko J, Shin K (2020) Evolution of real-world hypergraphs: patterns and models without oracles. In: 2020 IEEE international conference on data mining (ICDM). IEEE, pp 272–281. https://doi.org/10.1109/ICDM50108.2020.00036

Lee G, Shin K (2021) Thyme+: temporal hypergraph motifs and fast algorithms for exact counting. In: 2021 IEEE international conference on data mining (ICDM). IEEE, pp 310–319. https://doi.org/10.1109/ICDM51629.2021.00042

Lee G, Ko J, Shin K (2020) Hypergraph motifs: concepts, algorithms, and discoveries. PVLDB 13(12):2256–2269. https://doi.org/10.14778/3407790.3407823CrossRef

Lee G, Choe M, Shin K (2021) How do hyperedges overlap in real-world hypergraphs? Patterns, measures, and generators. Proc Web Conf 2021:3396–3407. https://doi.org/10.1145/3442381.3450010CrossRef

Leskovec J (2008) Dynamics of large networks. Carnegie Mellon University, Pittsburgh

Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. http://snap.stanford.edu/data

Lin J (1991) Divergence measures based on the Shannon entropy. IEEE Trans Inf Theory 37(1):145–151. https://doi.org/10.1109/18.61115MathSciNetCrossRefMATH

Luo X, Peng J, Liang J (2022) Directed hypergraph attention network for traffic forecasting. IET Intell Transport Syst 16(1):85–98. https://doi.org/10.1049/itr2.12130CrossRef

Newman ME, Forrest S, Balthrop J (2002) Email networks and the spread of computer viruses. Phys Rev E 66(3):035,101. https://doi.org/10.1103/PhysRevE.66.035101CrossRef

Nguyen VA, Lim EP, Tan HH et al (2010) Do you trust to get trust? A study of trust reciprocity behaviors and reciprocal trust prediction. In: Proceedings of the 2010 SIAM international conference on data mining. SIAM, pp 72–83. https://doi.org/10.1137/1.9781611972801.7

Pearcy N, Crofts JJ, Chuzhanova N (2014) Hypergraph models of metabolism. Int J Biol Vet Agric Food Eng 8(8):752–756. https://doi.org/10.5281/zenodo.1094247CrossRef

Ranshous S, Joslyn CA, Kreyling S et al (2017) Exchange pattern mining in the bitcoin transaction directed hypergraph. In: Financial cryptography and data security: FC 2017 international workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, Malta, April 7, 2017, Revised Selected Papers 21. Springer, pp 248–263. https://doi.org/10.1007/978-3-319-70278-0_16

Savitzky A, Golay MJ (1964) Smoothing and differentiation of data by simplified least squares procedures. Anal Chem 36(8):1627–1639. https://doi.org/10.1021/ac60214a047CrossRef

Sinha A, Shen Z, Song Y et al (2015) An overview of microsoft academic service (mas) and applications. In: Proceedings of the 24th international conference on world wide web, pp 243–246. https://doi.org/10.1145/2740908.2742839

Squartini T, Picciolo F, Ruzzenenti F et al (2013) Reciprocity of weighted networks. Sci Rep 3(1):1–9. https://doi.org/10.1038/srep02729CrossRef

Wang T, Resnick SI (2022) Asymptotic dependence of in-and out-degrees in a preferential attachment model with reciprocity. Extremes. https://doi.org/10.1007/s10687-022-00439-5MathSciNetCrossRefMATH

Wikipedia (2022) Computer science conference Wikipedia. https://en.wikipedia.org/wiki/List_of_computer_science_conferences

Wu J, Liu J, Chen W et al (2021) Detecting mixing services via mining bitcoin transaction network with hybrid motifs. IEEE Trans Syst Man Cybern Syst 52(4):2237–2249. https://doi.org/10.1109/TSMC.2021.3049278CrossRef

Yadati N, Nitin V, Nimishakavi M et al (2020) Nhp: neural hypergraph link prediction. In: Proceedings of the 29th ACM international conference on information & knowledge management, pp 1705–1714. https://doi.org/10.1145/3340531.3411870

Yadati N, Gao T, Asoodeh S et al (2021) Graph neural networks for soft semi-supervised learning on hypergraphs. In: Advances in knowledge discovery and data mining: 25th Pacific-Asia conference, PAKDD 2021, Virtual Event, May 11–14, 2021, Proceedings, Part I. Springer, pp 447–458. https://doi.org/10.1007/978-3-030-75762-5_36

Yoon S, Song H, Shin K et al (2020) How much and when do we need higher-order information in hypergraphs? A case study on hyperedge prediction. Proc Web Conf 2020:2627–2633. https://doi.org/10.1145/3366423.3380016CrossRef

Title: Reciprocity in directed hypergraphs: measures, findings, and generators
Authors: Sunwoo Kim
Minyoung Choe
Jaemin Yoo
Kijung Shin
Publication date: 08-08-2023
Publisher: Springer US
Published in: Data Mining and Knowledge Discovery / Issue 6/2023
Print ISSN: 1384-5810
Electronic ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-023-00955-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2023

Datasets, tasks, and training methods for large-scale hypergraph learning

Explainable contextual anomaly detection using quantile regression forests

An alternative for data visualization using space-filling curve

Improving the core resilience of real-world hypergraphs

Fast block-wise partitioning for extreme multi-label classification

Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applications

Premium Partner