Love tHy Neighbour: Remeasuring Local Structural Node Similarity in Hypergraph-Derived Networks
This work addresses the challenge of exploiting hypergraph structure for node similarity, which is important for applications like link prediction in complex networks, though it appears incremental as it extends existing graph-based methods.
The authors tackled the problem of measuring node similarity in hypergraphs, where traditional graph-based measures fail to capture higher-order relations, and proposed novel hypergraph-oriented similarity scores that significantly improve link prediction performance when combined with existing graph-based scores.
The problem of node-similarity in networks has motivated a plethora of such measures between node-pairs, which make use of the underlying graph structure. However, higher-order relations cannot be losslessly captured by mere graphs and hence, extensions thereof viz. hypergraphs are used instead. Measuring proximity between node pairs in such a setting calls for a revision in the topological measures of similarity, lest the hypergraph structure remains under-exploited. We, in this work, propose a multitude of hypergraph-oriented similarity scores between node-pairs, thereby providing novel solutions to the link prediction problem. As a part of our proposition, we provide theoretical formulations to extend graph-topology based scores to hypergraphs. We compare our scores with graph-based scores (over clique-expansions of hypergraphs into graphs) from the state-of-the-art. Using a combination of the existing graph-based and the proposed hypergraph-based similarity scores as features for a classifier predicts links much better than using the former solely. Experiments on several real-world datasets and both quantitative as well as qualitative analyses on the same exhibit the superiority of the proposed similarity scores over the existing ones.