Ambiguities in neural-network-based hyperedge prediction

A hypergraph is a generalization of a graph that depicts higher-order relations. Predicting higher-order relations, i.e. hyperedges, is a fundamental problem in hypergraph studies, and has immense applications in multiple domains. Recent development of graph neural network (GNN) advanced the prediction of pair-wise relations in graphs. However, existing methods can hardly be extended to hypergraphs due to the lack of higher-order dependency in their graph embedding. In this paper, we mathematically formulate the ambiguity challenges of GNN-based representation of higher-order relations, namely node-level and hyperedge-level ambiguities. We further present HIGNN (Hyperedge Isomorphism Graph Neural Network) that utilizes bipartite graph neural network with hyperedge structural features to collectively tackle the two ambiguity issues in the hyperedge prediction problem. HIGNN achieves constant performance improvement compared with recent GNN-based models. In addition, we apply HIGNN to a new task, predicting genetic higher-order interactions on 3D genome organization data. HIGNN shows consistently higher prediction accuracy across different chromosomes, and generates novel findings on 4-way gene interactions, which is further validated by existing literature.