Subgraph methods for link prediction were introduced as the Weisfeiler Leman Neural Machine (WLNM) in [1]}. As an MLP is used to learn from subgraphs instead of a GNN their model is not permutation-equivariant and uses a hashing-based WL algorithm [2]} to generate node indices for the MLP. Note that `hashing' here refers to injective neighbor aggregation functions, distinct from the data sketching methods employed in the current work. The MLP in WLNM was replaced by a GNN in the seminal SEAL [3]}, thus removing the need for a hashing scheme. Additional methodological improvements were made in [4]}, [5]} and subgraph generation was improved in [6]}. Applications to recommender systems were addressed in [7]} and [6]} use random walks to efficiently approximate subgraphs.
The DRNL labeling scheme was introduced in SEAL and further labeling schemes are developed in [9]}, [10]} and generalized with equivariant positional encodings [11]}.
Neural Bellman-Ford Networks [12]} takes a different approach. It is concerned with single source distances where each layer of the neural networks is equivalent to an iteration of the Bellman-Ford algorithm and can be regarded as using a partial labeling scheme. The same graph and augmentation can be shared among multiple destinations and so it is faster (amortized) than SGNNs. However, it suffers from poor space complexity and thus requires impractically high memory consumption.
Neo-GNN [13]} directly learns a heuristic function using an edgewise and a nodewise neural network. #GNN [14]} directly hashes node features, instead of graph structure, and is limited to node features that can be interpreted as set memberships.
Another paradigm for LP uses self-supervised node embeddings combined with an (often) approximate distance metric.
Amongst the best known models are TransE [15]}, DistMult [16]}, or complEx [17]}, which have been shown to scale to large LP systems in e.g. [18]}, [19]}.
Decoupling feature propagation and learning in GNNs was first implemented in SGC [20]} and then scalably in SIGN [21]}.
<TABLE>