Prior art based on common neighbors and Katz index for likelihood of links.
Learning the heuristic from the network instead of using predefined ones should be better.
Developed a novel gamma-decaying heuristic theory.
Local subgraphs are proven to have rich information for link existence.
Introduction
Heuristics like common neighbors and preferential attachment are first-order heuristics: they involve 1-hop.
Heuristics like Adamic-Adar (AA), Resource Allocation (RA) are 2nd order heuristics.
h-order heuristics go to the h-hop neighborhood.
Illustration of h-order heuristics showing 1-hop and multi-hop neighborhoods.
These heuristics belong to a more generic class: graph structural features.
Such are any features which can be computed directly from the graph.
Weisfeiler-Lehman Neural Machine (WLNM) studied this problem and provided features specific for link prediction.
Higher order heuristics like PageRank and Katz have better performance than first and second order ones.
We don't need a huge h number for h-heuristics.
SEAL is an improvement on WLNM.
Preliminaries
Latent features: factorize a matrix representation to learn a low-dimensional representation for each node. Node2vec, DeepWalk, matrix factorization...
Explicit features: usually node attributes.
Combining both usually brings out the best performance.
Supervised heuristic learning: WLNM trained FCNN on the subgraphs adjacency matrices.
Diagram of WLNM supervised heuristic learning architecture.