Link Prediction based on Social Networks - SEAL

Key ideas

Prior art based on common neighbors and Katz index for likelihood of links.
Learning the heuristic from the network instead of using predfined 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.
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.