SEAL

Link prediction had long been the domain of hand-designed heuristics: count common neighbors, weight by Adamic-Adar, run Katz. SEAL reframed the task as graph classification. For each candidate link it extracts the h-hop enclosing subgraph around the two endpoints, labels the nodes by their structural role (a double-radius node labeling that marks the target nodes and their distances), and trains a GNN to classify the whole subgraph as link or no-link. The key theoretical claim is that the learned model can capture heuristics of any order, including ones no human has designed, because the labeling lets the GNN see exactly where each node sits relative to the candidate link.\n\nThe NeurIPS 2018 paper evaluates on eight networks (USAir, NS, PB, Yeast, C.ele, Power, Router, E.coli) and SEAL beats every latent-feature and heuristic baseline on seven of them, with AUCs like 97.09 on USAir and 97.71 on NS. Most strikingly, on Power and Router, where classic heuristics are barely better than random guessing, SEAL still reaches 84.18 and 95.68 AUC. The enclosing-subgraph idea became a standard recipe for link prediction and influenced later subgraph-based GNNs.

Paper-reported AUC: USAir 97.09, NS 97.71, PB 95.01, Yeast 97.20, C.ele 89.54, Power 84.18, Router 95.68, E.coli 97.22 - best among all methods compared on 7 of 8 networks (Zhang & Chen, NeurIPS 2018).