Introducing new node prediction in graph mining: Predicting all links from isolated nodes with Graph Neural Networks

This paper introduces new node prediction, , a fresh problem in the field of graph mining and social network analysis. This task can be categorized as zero-shot out-of-graph all-links prediction, , and aims to predict all links coming from or going to a new, isolated, and unobserved node that was previously disconnected from the graph. In comparison with classic approaches to link prediction (including few-shot out-of-graph link prediction), this problem bears two key differences: (1) the new node has no existing links from which to extract patterns for new predictions; and (2) the goal is to predict not just one, but all the links of this new node, or, at least, a significant part of them. Experiments used an architecture based on Deep Graph Neural Networks, and were carried out on two datasets: a bibliographic citation graph and a drug-drug interaction graph. Results demonstrate that this challenging problem can be solved satisfactorily by using state-of-the-art Deep Learning techniques.