Link Prediction with Untrained Message Passing Layers

Abstract Message passing neural networks (MPNNs) operate on graphs by exchanging information between neigbouring nodes.MPNNs have been successfully applied to various node-, edge-, and graph-level tasks in areas like molecular science, computer vision, natural language processing, and combinatorial optimization. However, most MPNNs require training on large amounts of labeled data, which can be costly and time-consuming.In this work, we explore the use of various untrained message passing layers in graph neural networks, i.e. variants of popular message passing architecture where we remove all trainable parameters that are used to transform node features in the message passing step.Focusing on link prediction, we find that untrained message passing layers can lead to competitive and even superior performance compared to fully trained MPNNs, especially in the presence of high-dimensional features.We provide a theoretical analysis of untrained message passing by relating the inner products of features implicitly produced by untrained message passing layers to path-based topological node similarity measures.As such, untrained message passing architectures can be viewed as a highly efficient and interpretable approach to link prediction. Directory Structure The repository is organized into two directories:- `AttributedNetworks`: Contains code for link prediction on attributed graphs.- `NonAttributedNetworks`: Contains code for link prediction on non-attributed graphs. Replicating the ResultsTo replicate the results presented in the paper, follow these steps:1. Navigate to the respective directory (`AttributedNetworks` or `NonAttributedNetworks`).2. Run the `run_experiments_link_prediction.py` file to execute the experiments.3. LL stands for the UT layers, it can be used for UTMP or SMPNNs Viewing the ResultsAfter running the experiments, you can view the results by opening the `results.ipynb` notebook in the respective directory (`attributed_graphs` or `non_attributed_graphs`).