Tarun Kumar
ABSTRACT
Many real-world systems involve higher-order interactions and thus demand complex models such as hypergraphs. For instance, a research article could have multiple collaborating authors, and therefore the co-authorship network is best represented as a hypergraph. In this work, we focus on the problem of hyperedge prediction. This problem has immense applications in multiple domains, such as predicting new collaborations in social networks, discovering new chemical reactions in metabolic networks, etc. Despite having significant importance, the problem of hyperedge prediction hasn’t received adequate attention, mainly because of its inherent complexity. In a graph with n nodes the number of potential edges is , whereas in a hypergraph, the number of potential hyperedges is . To avoid searching through the huge space of hyperedges, current methods restrain the original problem in the following two ways. One class of algorithms assume the hypergraphs to be k-uniform where each hyperedge can have exactly k nodes. However, many real-world systems are not confined only to have interactions involving k components. Thus, these algorithms are not suitable for many real-world applications. The second class of algorithms requires a candidate set of hyperedges from which the potential hyperedges are chosen. In the absence of domain knowledge, the candidate set can have possible hyperedges, which makes this problem intractable. More often than not, domain knowledge is not readily available, making these methods limited in applicability. We propose HPRA - Hyperedge Prediction using Resource Allocation, the first of its kind algorithm, which overcomes these issues and predicts hyperedges of any cardinality without using any candidate hyperedge set. HPRA is a similarity-based method working on the principles of the resource allocation process. In addition to recovering missing hyperedges, we demonstrate that HPRA can predict future hyperedges in a wide range of hypergraphs. Our extensive set of experiments shows that HPRA achieves statistically significant improvements over state-of-the-art methods.
Supplemental Material
- Austin R Benson. 2019. Three hypergraph eigenvector centralities. SIAM Journal on Mathematics of Data Science 1, 2 (2019), 293–312.Google Scholar
Cross Ref
- Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2016. Modeling user consumption sequences. In Proceedings of the 25th International Conference on World Wide Web. 519–529.Google ScholarDigital Library
- Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2018. Sequences of sets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1148–1157.Google ScholarDigital Library
- Klessius Berlt, Edleno Silva De Moura, André Luiz da Costa Carvalho, Marco Cristo, Nivio Ziviani, and Thierson Couto. 2007. A Hypergraph Model for Computing Page Reputation on Web Collections.. In SBBD. 35–49.Google Scholar
- Jiajun Bu, Shulong Tan, Chun Chen, Can Wang, Hao Wu, L. Zhang, and Xiaofei He. 2010. Music Recommendation by Unified Hypergraph: Combining Social Media Information and Music Content. In Proceedings of the 18th International Conference on Multimedia. ACM, 391–400. https://doi.org/10.1145/1873951.1874005Google ScholarDigital Library
- Mayukh Das, Devendra Singh Dhami, Gautam Kunapuli, Kristian Kersting, and Sriraam Natarajan. 2019. Fast relational probabilistic inference and learning: Approximate counting via hypergraphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 7816–7824.Google ScholarDigital Library
- Manlio De Domenico, Antonio Lima, Paul Mougel, and Mirco Musolesi. 2013. The anatomy of a scientific rumor. Scientific reports 3(2013), 2980.Google Scholar
- Fuli Feng, Xiangnan He, Yiqun Liu, Liqiang Nie, and Tat-Seng Chua. 2018. Learning on partial-order hypergraphs. In Proceedings of the 2018 WWW Conference. 1523–1532.Google ScholarDigital Library
- Agostino Funel. 2018. Analysis of the Web Graph Aggregated by Host and Pay-Level Domain. In International Conference on Complex Networks and their Applications. Springer, 16–27.Google Scholar
- Leonidas Georgiadis, Michael J Neely, Leandros Tassiulas, 2006. Resource allocation and cross-layer control in wireless networks. Foundations and Trends® in Networking 1, 1 (2006), 1–144.Google ScholarDigital Library
- Jin-Li Guo, Qi Suo, Ai-Zhong Shen, and J. Forrest. 2016. The evolution of hyperedge cardinalities and bose-Einstein condensation in hypernetworks. Scientific reports 6(2016), 33651.Google Scholar
- Jin-Li Guo, Xin-Yun Zhu, Qi Suo, and J. Forrest. 2016. Non-uniform evolving hypergraphs and weighted evolving hypergraphs. Scientific reports 6(2016), 36648.Google Scholar
- S. W. Hadley, B. L. Mark, and A. Vannelli. 1992. An efficient eigenvector approach for finding netlist partitions. In IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 885–892.Google Scholar
- Yi Han, Bin Zhou, Jian Pei, and Yan Jia. 2009. Understanding importance of collaborations in co-authorship networks: A supportiveness analysis approach. In Proceedings of the 2009 SIAM ICDM. SIAM, 1112–1123.Google ScholarCross Ref
- F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens Datasets: History and Context. ACM Trans. Interact. Intell. Syst. 5, 4, Article 19 (Dec. 2015), 19 pages. https://doi.org/10.1145/2827872Google ScholarDigital Library
- Ruining He and Julian McAuley. 2016. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In Proceedings of the 25th international conference on world wide web. 507–517.Google ScholarDigital Library
- Zan Huang and Dennis KJ Lin. 2009. The time-series link prediction problem with applications in communication surveillance. INFORMS Journal on Computing 21, 2 (2009), 286–303.Google ScholarDigital Library
- Leo Katz. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1 (01 Mar 1953), 39–43. https://doi.org/10.1007/BF02289026Google Scholar
- Yeonjoon Kim, Jin Woo Kim, Zeehyo Kim, and Woo Youn Kim. 2018. Efficient prediction of reaction paths through molecular graph and reaction network analysis. Chemical science 9, 4 (2018), 825–835.Google Scholar
- Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. 2009. Hypergraphs and cellular networks. PLoS computational biology 5, 5 (2009), e1000385.Google Scholar
- Tarun Kumar, Sankaran Vaidyanathan, Harini Ananthapadmanabhan, Srinivasan Parthasarathy, and Balaraman Ravindran. 2019. A New Measure of Modularity in Hypergraphs: Theoretical Insights and Implications for Effective Clustering. In International Conference on Complex Networks and Their Applications. Springer, 286–297.Google Scholar
- Jérôme Kunegis, Marcel Blattner, and Christine Moser. 2013. Preferential Attachment in Online Networks: Measurement and Explanations. In Proceedings of the 5th Annual ACM Web Science Conference (Paris, France) (WebSci ’13). ACM, New York, NY, USA, 205–214. https://doi.org/10.1145/2464464.2464514Google ScholarDigital Library
- Michael Ley. 2002. The DBLP computer science bibliography: Evolution, research issues, perspectives. In International symposium on string processing and information retrieval. Springer, 1–10.Google ScholarDigital Library
- Pan Li and Olgica Milenkovic. 2017. Inhomogeneous hypergraph clustering with applications. In Advances in Neural Information Processing Systems. 2308–2318.Google Scholar
- David Liben-Nowell and Jon Kleinberg. 2003. The Link-Prediction Problem for Social Networks. In CIKM’03. 556–559.Google Scholar
- Dekang Lin. 1998. An Information-Theoretic Definition of Similarity. In Proceedings of the Fifteenth ICML(ICML ’98). Morgan Kaufmann Publishers Inc., 296–304. http://dl.acm.org/citation.cfm?id=645527.657297Google Scholar
- Linyuan Lü and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications 390, 6(2011), 1150–1170.Google Scholar
- Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415–444.Google Scholar
- Giulia Menichetti, Daniel Remondini, Pietro Panzarasa, Raúl J Mondragón, and Ginestra Bianconi. 2014. Weighted multiplex networks. PloS one 9, 6 (2014).Google Scholar
- Mark EJ Newman. 2001. Clustering and preferential attachment in growing networks. Physical review E 64, 2 (2001), 025102.Google Scholar
- Prasanna Patil, Govind Sharma, and M Narasimha Murty. 2020. Negative Sampling for Hyperlink Prediction in Networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 607–619.Google Scholar
- Rizka Rahmaida, Asep Saefuddin, and Bagus Sartono. 2019. Predicting Potential Co-Authorship Using Random Forest: Case of Scientific Publications in Indonesian Institute of Sciences. STI Policy and Management Journal 4, 2 (2019).Google ScholarCross Ref
- N Roopashree and V Umadevi. 2014. Future Collaboration Prediction in Co-authorship Network. In 2014 3rd International Conference on Eco-friendly Computing and Communication Systems. IEEE, 183–188.Google Scholar
- Sanjukta Roy and Balaraman Ravindran. 2015. Measuring network centrality using hypergraphs. In IKDD CoDS. ACM, 59–68.Google Scholar
- Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W Moore. 2011. Theoretical justification of popular link prediction heuristics. In Twenty-Second International Joint Conference on Artificial Intelligence.Google Scholar
- Sai Nageswar Satchidanand, Siddharth Kumar Jain, Amit Maurya, and Balaraman Ravindran. 2014. Studying Indian railways network using hypergraphs. In 2014 Sixth International Conference on Communication Systems and Networks (COMSNETS). IEEE, 1–6.Google ScholarCross Ref
- Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93–93.Google Scholar
- Tie Shen, Zhengdong Zhang, Zhen Chen, Dagang Gu, Shen Liang, Yang Xu, Ruiyuan Li, Yimin Wei, Zhijie Liu, Yin Yi, 2018. A genome-scale metabolic network alignment method within a hypergraph-based framework using a rotational tensor-vector product. Scientific reports 8, 1 (2018), 1–16.Google Scholar
- Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. ArnetMiner: Extraction and Mining of Academic Social Networks. In KDD’08. 990–998.Google Scholar
- Daniel Valcarce, Javier Parapar, and Álvaro Barreiro. 2016. Additive smoothing for relevance-based language modelling of recommender systems. In Proceedings of the 4th CERI. 1–8.Google ScholarDigital Library
- Martijn P van den Heuvel and Olaf Sporns. 2013. Network hubs in the human brain. Trends in cognitive sciences 17, 12 (2013), 683–696.Google Scholar
- Chao Wang, Venu Satuluri, and Srinivasan Parthasarathy. 2007. Local Probabilistic Models for Link Prediction. In Proceedings of the 7th IEEE ICDM. IEEE Computer Society, 322–331.Google ScholarDigital Library
- Yu Wang, Aniket Chakrabarti, David Sivakoff, and Srinivasan Parthasarathy. 2017. Fast Change Point Detection on Dynamic Social Networks. In Proceedings of the 26th IJCAI(Melbourne, Australia) (IJCAI’17). AAAI Press, 2992–2998.Google ScholarCross Ref
- Ye Xu, Dan Rockmore, and Adam M Kleinbaum. 2013. Hyperlink prediction in hypernetworks using latent social features. In International Conference on Discovery Science. Springer, 324–339.Google ScholarCross Ref
- Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In Advances in Neural Information Processing Systems. 1509–1520.Google Scholar
- Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference on Web search and data mining. 587–596.Google ScholarDigital Library
- Jun Yu, Yong Rui, and Dacheng Tao. 2014. Click prediction for web image reranking using multimodal sparse coding. IEEE Transactions on Image Processing 23, 5 (2014), 2019–2032.Google ScholarCross Ref
- Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems. 5165–5175.Google Scholar
- Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018. Beyond link prediction: Predicting hyperlinks in adjacency space. In Thirty-Second AAAI Conference on Artificial Intelligence.Google ScholarCross Ref
- Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. 2007. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in neural information processing systems. 1601–1608.Google Scholar
- Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. 2009. Predicting missing links via local information. The European Physical Journal B 71, 4 (2009), 623–630.Google ScholarCross Ref
Recommendations
Covering Non-uniform Hypergraphs
A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...
Odd cycles and Θ-cycles in hypergraphs
A @Q-cycle of a hypergraph is a cycle including an edge that contains at least three base points of the cycle. We show that if a hypergraph H=(V,E) has no @Q-cycle, and |e|>=3, for every edge e@__ __E, then @__ __"e"@__ __"E(|e|-1)=<2|V|-2 with equality ...
Dominating sequences in graphs
A sequence of vertices in a graph G is called a legal dominating sequence if every vertex in the sequence dominates at least one vertex not dominated by those vertices that precede it, and at the end all vertices of G are dominated. While the length of ...
Comments