Se-eun Yoon
ABSTRACT
Hypergraphs provide a natural way of representing group relations, whose complexity motivates an extensive array of prior work to adopt some form of abstraction and simplification of higher-order interactions. However, the following question has yet to be addressed: How much abstraction of group interactions is sufficient in solving a hypergraph task, and how different such results become across datasets? This question, if properly answered, provides a useful engineering guideline on how to trade off between complexity and accuracy of solving a downstream task. To this end, we propose a method of incrementally representing group interactions using a notion of n-projected graph whose accumulation contains information on up to n-way interactions, and quantify the accuracy of solving a task as n grows for various datasets. As a downstream task, we consider hyperedge prediction, an extension of link prediction, which is a canonical task for evaluating graph models. Through experiments on 15 real-world datasets, we draw the following messages: (a) Diminishing returns: small n is enough to achieve accuracy comparable with near-perfect approximations, (b) Troubleshooter: as the task becomes more challenging, larger n brings more benefit, and (c) Irreducibility: datasets whose pairwise interactions do not tell much about higher-order interactions lose much accuracy when reduced to pairwise abstractions.
- 2020. Supplementary Document. Available online: https://github.com/granelle/www20-higher-order.Google Scholar
- Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks 25, 3 (2003), 211–230.Google Scholar
- Sameer Agarwal, Kristin Branson, and Serge Belongie. 2006. Higher order learning with graphs. In ICML.Google Scholar
- Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman, and Serge Belongie. 2005. Beyond pairwise clustering. In CVPR.Google Scholar
- Devanshu Arya and Marcel Worring. 2018. Exploiting Relational Information in Social Networks using Geometric Deep Learning on Hypergraphs. In ACM Multimedia.Google Scholar
- AR Benson, R Abebe, MT Schaub, A Jadbabaie, and J Kleinberg. 2018. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences of the United States of America 115, 48 (2018).Google ScholarCross Ref
- Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2018. Sequences of sets. In KDD.Google Scholar
- Jiajun Bu, Shulong Tan, Chun Chen, Can Wang, Hao Wu, Lijun Zhang, and Xiaofei He. 2010. Music recommendation by unified hypergraph: combining social media information and music content. In ACM Multimedia.Google Scholar
- Samuel R Bulò and Marcello Pelillo. 2009. A game-theoretic approach to hypergraph clustering. In NeurIPS.Google Scholar
- Gang Chen, Jianwen Zhang, Fei Wang, Changshui Zhang, and Yuli Gao. 2009. Efficient multi-label classification with hypergraph regularization. In CVPR.Google Scholar
- Jesse Davis and Mark Goadrich. 2006. The relationship between Precision-Recall and ROC curves. In ICML.Google Scholar
- Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. 2019. Knowledge Hypergraphs: Extending Knowledge Graphs Beyond Binary Relations. arXiv:1906.00137 (2019).Google Scholar
- Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. 2019. Hypergraph neural networks. In AAAI.Google Scholar
- James H. Fowler. 2006. Connecting the Congress: A Study of Cosponsorship Networks. Political Analysis 14, 04 (2006), 456–487.Google ScholarCross Ref
- James H. Fowler. 2006. Legislative cosponsorship networks in the US House and Senate. Social Networks 28, 4 (2006), 454–465.Google ScholarCross Ref
- Debarghya Ghoshdastidar and Ambedkar Dukkipati. 2017. Uniform hypergraph partitioning: Provable tensor methods and sampling techniques. The Journal of Machine Learning Research 18, 1 (2017), 1638–1678.Google ScholarDigital Library
- Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In KDD.Google Scholar
- Aditya Grover, Aaron Zweig, and Stefano Ermon. 2019. Graphite: Iterative Generative Modeling of Graphs. In ICML.Google Scholar
- Tianming Hu, Hui Xiong, Wenjun Zhou, Sam Yuan Sung, and Hangzai Luo. 2008. Hypergraph partitioning for document clustering: A unified clique perspective. In SIGIR.Google Scholar
- Jin Huang, Rui Zhang, and Jeffrey Xu Yu. 2015. Scalable hypergraph learning and processing. In ICDM.Google Scholar
- Sheng Huang, Mohamed Elhoseiny, Ahmed Elgammal, and Dan Yang. 2015. Learning hypergraph-regularized attribute predictors. In CVPR.Google Scholar
- TaeHyun Hwang, Ze Tian, Rui Kuangy, and Jean-Pierre Kocher. 2008. Learning on weighted hypergraphs to integrate protein interactions and gene expressions for cancer outcome prediction. In ICDM.Google Scholar
- George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. 1999. Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Transactions on Very Large Scale Integration Systems 7, 1(1999), 69–79.Google ScholarDigital Library
- George Karypis and Vipin Kumar. 2000. Multilevel k-way hypergraph partitioning. VLSI design 11, 3 (2000), 285–300.Google Scholar
- Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. 2009. Hypergraphs and cellular networks. PLoS computational biology 5, 5 (2009), e1000385.Google Scholar
- Bryan Klimt and Yiming Yang. 2004. The enron corpus: A new dataset for email classification research. In ECML PKDD.Google Scholar
- Tamara G Kolda and Brett W Bader. 2009. Tensor decompositions and applications. SIAM review 51, 3 (2009), 455–500.Google ScholarDigital Library
- Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data 1, 1 (2007).Google ScholarDigital Library
- Dong Li, Zhiming Xu, Sheng Li, and Xin Sun. 2013. Link prediction in social networks based on hypergraph. In WWW.Google Scholar
- Jianbo Li, Jingrui He, and Yada Zhu. 2018. E-tail product return prediction via hypergraph-based local graph cut. In KDD.Google Scholar
- David Liben-Nowell and Jon Kleinberg. 2007. The link prediction problem for social networks. Journal of the American society for information science and technology 58, 7 (2007), 1019–1031.Google ScholarCross Ref
- Yu-Ru Lin, Jimeng Sun, Paul Castro, Ravi Konuru, Hari Sundaram, and Aisling Kelliher. 2009. Metafac: community discovery via relational hypergraph factorization. In KDD.Google 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
- Rossana Mastrandrea, Julie Fournet, and Alain Barrat. 2015. Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PloS one 10, 9 (2015), e0136497.Google ScholarCross Ref
- Saket Navlakha and Carl Kingsford. 2010. The power of protein interaction networks for associating genes with diseases. Bioinformatics 26, 8 (2010), 1057–1063.Google ScholarDigital Library
- Mark EJ Newman. 2001. Clustering and preferential attachment in growing networks. Physical review E 64, 2 (2001), 025102.Google Scholar
- Ferda Ofli, Yusuf Aytar, Ingmar Weber, Raggi Al Hammouri, and Antonio Torralba. 2017. Is saki# delicious?: The food perception gap on instagram and its relation to health. In WWW.Google Scholar
- Min Ouyang, Michel Toulouse, Krishnaiyan Thulasiraman, Fred Glover, and Jitender S Deogun. 2002. Multilevel cooperative search for the circuit/hypergraph partitioning problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21, 6(2002), 685–693.Google ScholarDigital Library
- Gerard Salton and Michael J McGill. 1983. Introduction to modern information retrieval. mcgraw-hill.Google Scholar
- Marc Santolini and Albert-László Barabási. 2018. Predicting perturbation patterns from the topology of biological networks. Proceedings of the National Academy of Sciences 115, 27(2018), E6375–E6383.Google ScholarCross Ref
- Ankit Sharma, Jaideep Srivastava, and Abhishek Chandra. 2014. Predicting multi-actor collaborations using hypergraphs. arXiv:1401.6404 (2014).Google Scholar
- Amnon Shashua, Ron Zass, and Tamir Hazan. 2006. Multi-way clustering using super-symmetric non-negative tensor factorization. In ECCV.Google Scholar
- Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June (Paul) Hsu, and Kuansan Wang. 2015. An Overview of Microsoft Academic Service (MAS) and Applications. In WWW.Google Scholar
- Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, 2011. High-resolution measurements of face-to-face contact patterns in a primary school. PloS one 6, 8 (2011), e23176.Google ScholarCross Ref
- Shulong Tan, Ziyu Guan, Deng Cai, Xuzhen Qin, Jiajun Bu, and Chun Chen. 2014. Mapping users across networks by manifold alignment on hypergraph. In AAAI.Google Scholar
- Ye Xu, Dan Rockmore, and Adam M Kleinbaum. 2013. Hyperlink prediction in hypernetworks using latent social features. In DS.Google Scholar
- Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. 2018. Hypergcn: Hypergraph convolutional networks for semi-supervised classification. arXiv:1809.02589 (2018).Google Scholar
- Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. 2018. Link Prediction in Hypergraphs using Graph Convolutional Networks. openreview.net (2018).Google Scholar
- Dingqi Yang, Bingqing Qu, Jie Yang, and Philippe Cudre-Mauroux. 2019. Revisiting user mobility and social relationships in lbsns: a hypergraph embedding approach. In WWW.Google Scholar
- Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. 2017. Local higher-order graph clustering. In KDD.Google Scholar
- Jiaxuan You, Rex Ying, and Jure Leskovec. 2019. Position-aware Graph Neural Networks. In ICML.Google Scholar
- Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. 2018. Beyond link prediction: Predicting hyperlinks in adjacency space. In AAAI.Google Scholar
- Yang Zhang. 2019. Language in Our Time: An Empirical Analysis of Hashtags. In WWW.Google Scholar
- Chang Zhou, Yuqiong Liu, Xiaofei Liu, Zhongyi Liu, and Jun Gao. 2017. Scalable graph embedding for asymmetric proximity. In AAAI.Google Scholar
- Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. 2007. Learning with hypergraphs: Clustering, classification, and embedding. In NeurIPS.Google Scholar
- Yu Zhu, Ziyu Guan, Shulong Tan, Haifeng Liu, Deng Cai, and Xiaofei He. 2016. Heterogeneous hypergraph embedding for document recommendation. Neurocomputing 216(2016), 150–162.Google ScholarCross Ref
Index Terms
- How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction
Index terms have been assigned to the content through auto-classification.
Recommendations
Erdős-Hajnal-type theorems in hypergraphs
The Erdos-Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n^@d^(^H^), where @d(H)>0 depends only on the ...
On 2-Colorings of Hypergraphs
In this article, we continue the study of 2-colorings in hypergraphs. A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let Hk denote the class of all k-uniform k-regular hypergraphs. It is known see ...
Regular subgraphs of uniform hypergraphs
We prove that for every integer r 2 , an n-vertex k-uniform hypergraph H containing no r-regular subgraphs has at most ( 1 + o ( 1 ) ) ( n - 1 k - 1 ) edges if k r + 1 and n is sufficiently large. Moreover, if r { 3 , 4 } , r | k and k, n are both ...
Comments