Link Prediction Schemes Contra Weisfeiler-Leman Models

Link prediction is of particular interest to the data mining and machine learning communities. Until recently all approaches to the problem used embedding-based methods which leverage either node similarities or latent group memberships towards link prediction. Chen and Zhang recently developed a class of non-embedding approaches called Weisfeiler-Leman (WL) Models. WL-Models extract subgraphs around links and then encode subgraph patterns via adjacency matrices using the so-called Palette-WL algorithm. A training stage then learns nonlinear graph topological features for link prediction. Chen and Zhang compared two WL-Models – a linear regression model (“WLLR”) and a neural networks model (“WLNM”) – against 12 different common link prediction schemes. In this paper, all author claims are validated for WLLR. Additionally, WLLR is tested against 22 additional embedding-based link prediction techniques arising from common neighbor-, path- and random walk-based schemes. WLLR is shown not to be superior when calculable. In fact, in 80% of the datasets where comparisons were possible, one of our added implementations proved superior.

@article{Brodhead2018,
  title     = {Link Prediction Schemes Contra Weisfeiler-Leman Models},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {9},
  number    = {6},
  year      = {2018},
  publisher = {The Science and Information Organization},
  author    = {Katie Brodhead},
  doi       = {10.14569/IJACSA.2018.090603},
  url       = {https://doi.org/10.14569/IJACSA.2018.090603}
}