Detecting Critical Nodes in Hypergraphs via Hypergraph Convolutional Network

In many real-world networks, such as co-authorship, etc., relationships are complex and go beyond pairwise associations. Hypergraphs provide a flexible and natural modeling tool to model such complex relationships. Detecting the set of critical nodes that keeps the hypergraph structure cohesive and tremendous has great significance. At present, all the researches in detecting critical nodes area focus on traditional pairwise graphs, and how to extend these researches to hypergraphs is an urgent problem. In this paper, we propose a novel framework, called Hypercore Hypergraph Convolutional Network (H²GCN) to detect the critical nodes. Specifically, we first transform the raw hypergraph into a k-hypercore, and then generate training samples using biased sampling. Furthermore, we adopt the hypergraph convolutional network to capture the complex hypergraph topological structure information for generating node embedding, and then generate a hypergraph embedding by aggregating node embedding using a self-attention mechanism. Finally, by feeding the hypergraph embedding to MLP, H²GCN has the ability to predict the probability that the remaining nodes will be selected as critical nodes under the condition of existing partial solutions. Our experiments on many real-world hypergraphs show that H²GCN significantly improves the quality of the detected critical nodes compared to existing traditional algorithms extended to hypergraphs.