Link Prediction Based on Graph Neural Networks
Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a "heuristic" that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel -decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the -decaying theory, we propose a new method to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.
Quality:   From the technical point of view, the paper seems to be well-prepared. In particular, the authors propose $\gamma-heuristic theory$ for link prediction and show that many common heuristics can be expressed in a general formulation.  They build their framework based on this theory and on the previous work  (WLNM). However,  I would like to touch on some points here: - In Line 115, there is no clear definition of the \textbf{h-order heuristic} although it is mentioned between lines 26 and 31. If \textbf{h-order heuristic} is defined as, for example, "a heuristic requiring to know up to h-hop neighborhood of the target nodes", then do we really need Theorem 1? - In lines 274 and 275, it is stated that "We run all experiments for 5 times and report the average". It would be better if more runs are performed. - Lines 278-283: The training set size consists of the 90\% of all edges. I think it could be better to see the performance of the framework over different training/test set ratios. (In Appendix, there is another experiment similar to the one in Node2Vec paper in which 50\% of the edges are chosen as training set). - The standard deviation of experiments can also be included in the tables of the paper, as it is done in the Appendix. - The explicit features are not used in Table 2. I think it could be better to perform an experiment including explicit features. - The $\gamma$-heuristic theory is only used to show that small $h$ values can be sufficient to approximate some heuristics. It could be interesting that if the authors could develop a method that is able to learn the parameters within the general formulation.  Clarity:   I think that the structure and readability of the paper is quite good. The authors clearly define the \textbf{h-order heuristic} theory, with several examples. Then, they shortly mention about the methods that have been used in their framework. Here, I would like to indicate some mistakes in the notation: - In Lines 143 and 172, two different walk and length representations $|(w_1,...,w_n)|$ and $len()$ are used. - In Line 143, $d(i,x)$ and $d(i,y)$ should be $d(v_i,x)$ and $d(v_i,y)$ since $i$ is index. - In Line 143, the expression $l=|\{x,v_1,...,v_{i-1}\}| + |\{v_{i+1},...,v_{l-1},y\}|$ should be $l=|\{x,v_1,...,v_{i-1},v_{i}\}| + |\{v_{i}, v_{i+1},...,v_{l-1},y\}|$ - In Line 264, "This" should be changed with "These"  Originality: The authors give a nice general formulation (\gamma-heuristic theory) for link prediction heuristics and show that many heuristics can be approximated with small $h$ values and appropriate parameters. Although it seems that the rest of the paper is similar to the WLNM method, they have managed to enhance it, outperforming previous state-of-the-art methods by changing the methodologies used at the different steps. Unlike WLNM, it also enables the use of explicit and latent features of nodes.  Significance: As it was stated above, one of the major contributions of this work is the development of the $\gamma$-decaying heuristic theory which stems from the natural design of many heuristics. The proposed framework also allows us to benefit from the latent and explicit node features with the favor of GNN model in link prediction tasks and the experiments performed over many datasets also support its significance.