Expressive Higher-Order Link Prediction through Hypergraph Symmetry
  Breaking
Simon Zhang Cheng Xin Tamal K. Dey
A hypergraph consists of a set of nodes along with a collection of subsets of
the nodes called hyperedges. Higher-order link prediction is the task of
predicting the existence of a missing hyperedge in a hypergraph. A hyperedge
representation learned for higher order link prediction is fully expressive
when it does not lose distinguishing power up to an isomorphism. Many existing
hypergraph representation learners, are bounded in expressive power by the
Generalized Weisfeiler Lehman-1 (GWL-1) algorithm, a generalization of the
Weisfeiler Lehman-1 algorithm. However, GWL-1 has limited expressive power. In
fact, induced subhypergraphs with identical GWL-1 valued nodes are
indistinguishable. Furthermore, message passing on hypergraphs can already be
computationally expensive, especially on GPU memory. To address these
limitations, we devise a preprocessing algorithm that can identify certain
regular subhypergraphs exhibiting symmetry. Our preprocessing algorithm runs
once with complexity the size of the input hypergraph. During training, we
randomly replace subhypergraphs identified by the algorithm with covering
hyperedges to break symmetry. We show that our method improves the expressivity
of GWL-1. Our extensive experiments also demonstrate the effectiveness of our
approach for higher-order link prediction on both graph and hypergraph datasets
with negligible change in computation.