Hyunjin Hwang
ABSTRACT
Hypergraphs (i.e., sets of hyperedges) naturally represent group relations (e.g., researchers co-authoring a paper and ingredients used together in a recipe), each of which corresponds to a hyperedge (i.e., a subset of nodes). Predicting future or missing hyperedges bears significant implications for many applications (e.g., collaboration and recipe recommendation). What makes hyperedge prediction particularly challenging is the vast number of non-hyperedge subsets, which grows exponentially with the number of nodes. Since it is prohibitive to use all of them as negative examples for model training, it is inevitable to sample a very small portion of them, and to this end, heuristic sampling schemes have been employed. However, trained models suffer from poor generalization capability for examples of different natures. In this paper, we propose AHP, an adversarial training-based hyperedge-prediction method. It learns to sample negative examples without relying on any heuristic schemes. Using six real hypergraphs, we show that AHP generalizes better to negative examples of various natures. It yields up to 28.2% higher AUROC than the best existing methods and often even outperforms its variants with sampling schemes tailored to test sets.
Supplemental Material
- Ilya Amburg, Nate Veldt, and Austin Benson. 2020. Clustering in graphs and hypergraphs with categorical edge labels. In WWW.Google Scholar
- Martin Arjovsky and Léon Bottou. 2017. Towards principled methods for training generative adversarial networks. In ICLR.Google Scholar
- Martin Arjovsky, Soumith Chintala, and Léon Bottou. 2017. Wasserstein generative adversarial networks. In ICML.Google Scholar
- Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018. Simplicial closure and higher-order link prediction. PNAS 115, 48 (2018), E11221--E11230.Google ScholarCross Ref
- Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2018. Sequences of sets. In KDD.Google Scholar
- Minyoung Choe, Jaemin Yoo, Geon Lee, Woonsung Baek, U Kang, and Kijung Shin. 2022. MiDaS: Representative Sampling from Real-world Hypergraphs. In WWW.Google Scholar
- Hyunjin Choo and Kijung Shin. 2022. On the Persistence of Higher-Order Interactions in Real-World Hypergraphs. In SDM.Google Scholar
- Cazamere Comrie and Jon Kleinberg. 2021. Hypergraph Ego-networks and Their Temporal Evolution. In ICDM.Google Scholar
- Manh Tuan Do, Se-eun Yoon, Bryan Hooi, and Kijung Shin. 2020. Structural patterns and generative models of real-world hypergraphs. In KDD.Google Scholar
- Yihe Dong, Will Sawin, and Yoshua Bengio. 2020. HNHN: Hypergraph networks with hyperedge neurons. arXiv preprint arXiv:2006.12278 (2020).Google Scholar
- Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2019. Hypergraph neural networks. In AAAI.Google Scholar
- Li He, Hongxu Chen, Dingxian Wang, Shoaib Jameel, Philip Yu, and Guandong Xu. 2021. Click-Through Rate Prediction with Multi-Modal Hypergraphs. In CIKM.Google Scholar
- Ming Hou, Brahim Chaib-draa, Chao Li, and Qibin Zhao. 2018. Generative Adversarial Positive-Unlabelled Learning. In IJCAI.Google Scholar
- Wenpeng Hu, Ran Le, Bing Liu, Feng Ji, Jinwen Ma, Dongyan Zhao, and Rui Yan. 2021. Predictive Adversarial Learning from Positive and Unlabeled Data. In AAAI.Google Scholar
- Leo Katz. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1 (1953), 39--43.Google ScholarCross Ref
- Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR.Google Scholar
- Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. 2017. Positive-unlabeled learning with non-negative risk estimator. In NIPS.Google Scholar
- Yunbum Kook, Jihoon Ko, and Kijung Shin. 2020. Evolution of Real-world Hypergraphs: Patterns and Models without Oracles. In ICDM.Google Scholar
- Geon Lee, Minyoung Choe, and Kijung Shin. 2021. How Do Hyperedges Overlap in Real-World Hypergraphs? - Patterns, Measures, and Generators. In WWW.Google Scholar
- Geon Lee, Jihoon Ko, and Kijung Shin. 2020. Hypergraph Motifs: Concepts, Algorithms, and Discoveries. PVLDB 13, 11 (2020).Google ScholarDigital Library
- Geon Lee and Kijung Shin. 2021. THyMe+: Temporal Hypergraph Motifs and Fast Algorithms for Exact Counting. In ICDM.Google Scholar
- Yicong Li, Hongxu Chen, Xiangguo Sun, Zhenchao Sun, Lin Li, Lizhen Cui, Philip S Yu, and Guandong Xu. 2021. Hyperbolic hypergraphs for sequential recommendation. In CIKM.Google Scholar
- David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. JASIST 58, 7 (2007), 1019--1031.Google ScholarDigital Library
- Zheng Liu, Xing Xie, and Lei Chen. 2018. Context-aware academic collaborator recommendation. In KDD.Google Scholar
- Byeonghu Na, Hyemi Kim, Kyungwoo Song, Weonyoung Joo, Yoon-Yeong Kim, and Il-Chul Moon. 2020. Deep generative positive-unlabeled learning under selection bias. In CIKM.Google Scholar
- Duc Anh Nguyen, Canh Hao Nguyen, and Hiroshi Mamitsuka. 2021. CentSmoothie: Central-Smoothing Hypergraph Neural Networks for Predicting Drug-Drug Interactions. arXiv preprint arXiv:2112.07837 (2021).Google Scholar
- Prasanna Patil, Govind Sharma, and M Narasimha Murty. 2020. Negative sampling for hyperlink prediction in networks. In PAKDD.Google Scholar
- Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, and Thomas Hofmann. 2017. Stabilizing training of Generative Adversarial Networks through regularization. In NIPS.Google Scholar
- Hoang Thanh-Tung, Svetha Venkatesh, and Truyen Tran. 2019. Improving generalization and stability of generative adversarial networks. In ICLR.Google Scholar
- Thonet Thibaut, Renders Jean-Michel, Choi Mario, and Kim Jinho. 2022. Joint Personalized Search and Recommendation with Hypergraph Convolutional Networks. In ECIR.Google Scholar
- Leo Torres, Ann S Blevins, Danielle Bassett, and Tina Eliassi-Rad. 2021. The why, how, and when of representations for complex systems. SIAM Rev. 63, 3 (2021), 435--485.Google ScholarDigital Library
- Ke Tu, Peng Cui, Xiao Wang, Fei Wang, and Wenwu Zhu. 2018. Structural deep embedding for hyper-networks. In AAAI.Google Scholar
- Maria Vaida and Kevin Purcell. 2019. Hypergraph link prediction: learning drug interaction networks embeddings. In ICMLA.Google Scholar
- Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In NIPS.Google Scholar
- Jianling Wang, Kaize Ding, Liangjie Hong, Huan Liu, and James Caverlee. 2020. Next-item recommendation with sequential hypergraphs. In SIGIR.Google Scholar
- Man Wu, Shirui Pan, Lan Du, Ivor Tsang, Xingquan Zhu, and Bo Du. 2019. Longshort distance aggregation networks for positive unlabeled graph learning. In CIKM.Google Scholar
- 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 NeurIPS.Google Scholar
- Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. 2020. NHP: Neural Hypergraph Link Prediction. In CIKM.Google Scholar
- Se-eun Yoon, Hyungseok Song, Kijung Shin, and Yung Yi. 2020. How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction. In WWW.Google Scholar
- Chia-An Yu, Ching-Lun Tai, Tak-Shing Chan, and Yi-Hsuan Yang. 2018. Modeling multi-way relations with hypergraph embedding. In CIKM.Google Scholar
- Junwei Zhang, Min Gao, Junliang Yu, Lei Guo, Jundong Li, and Hongzhi Yin. 2021. Double-Scale Self-Supervised Hypergraph Learning for Group Recommendation. In CIKM.Google Scholar
- Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018. Beyond link prediction: Predicting hyperlinks in adjacency space. In AAAI.Google Scholar
- Ruochi Zhang, Yuesong Zou, and Jian Ma. 2020. Hyper-SAGNN: a self-attention based graph neural network for hypergraphs. In ICLR.Google Scholar
- Yao Zhou, Jianpeng Xu, Jun Wu, Zeinab Taghavi, Evren Korpeoglu, Kannan Achan, and Jingrui He. 2021. PURE: Positive-Unlabeled Recommendation with Generative Adversarial Network. In KDD.Google ScholarDigital Library
Index Terms
- AHP: Learning to Negative Sample for Hyperedge Prediction
Recommendations
HPRA: Hyperedge Prediction using Resource Allocation
WebSci '20: Proceedings of the 12th ACM Conference on Web ScienceMany 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 ...
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 ...
Comments