Link Prediction with Untrained Message Passing Layers

Authors: Lisi Qarkaxhija, Anatol Eugen Wegner, Ingo Scholtes
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, untrained message passing layers, link prediction, path-based similarity measures

Abstract:
In this work, we explore the use of untrained message passing layers in graph neural networks for link prediction. The untrained message passing layers we consider are derived from widely used graph neural network architectures by removing trainable parameters and nonlinearities in their respective message passing layers. Experimentally we find that untrained message passing layers can lead to competitive and even superior link prediction performance compared to fully trained message passing layers while being more efficient and naturally interpretable, especially in the presence of high-dimensional features. We also provide a theoretical analysis of untrained message passing layers in the context of link prediction and show that the inner product of features produced by untrained message passing layers relate to common neighbour and path-based topological measures which are widely used for link prediction. As such, untrained message passing layers offer a more efficient and interpretable alternative to trained message passing layers in link prediction tasks.

Decision: reject
Reviewer scores: 3, 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1729995985183

thread_type:
official_review

<thread_object>
creator: reviewer_dplb

<content>
summary:
The paper explores the use of untrained message-passing layers (UTMP) for link prediction tasks in graph neural networks (GNNs). The authors propose simplifying GNN architectures by removing trainable parameters and nonlinear components, resulting in interpretable and computationally efficient models. Their research finds that these simplified architectures can often outperform or match the performance of fully trained GNNs in link prediction tasks.

strengths:
1. The paper introduces untrained message-passing architectures, extending existing research from node classification to link prediction. This perspective is relatively novel and addresses the computational limitations of GNNs. The untrained models, by eliminating learnable parameters, are shown to be faster and more resource-efficient, making them suitable for large-scale applications.


2. Theoretical results provide a deeper understanding of how UTMP layers approximate traditional path-based link prediction metrics (e.g., random walks and common neighbors), making the models highly interpretable.

weaknesses:
1. Limited baselines are compared. Path-based methods and edge-wise methods should be compared. This doesn't mean the authors should change them into untrained models and do comparison. The author discuss the theoretical relationship with path-based methods, so the emperical comparison is needed to validate the theory.

2. Limited datasets are included. Large datasets like OGB datasets are not included so the application is limited. 

3. For non-attributed graphs the results of original GNNs are much better than on the attributed graphs, compared to S-models and UT-models. Can the authors do some ablations to discuss this observation? Maybe it's because of the one-hot encoding? Can the authors show the results of one-hot encoding in attributed graphs?

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730457023279

thread_type:
official_review

<thread_object>
creator: reviewer_nhjd

<content>
summary:
The paper investigates the use of untrained message-passing layers for link prediction tasks. Both a completely untrained model and a model with a trainable layer after the message passing layers are compared to standard trained message-passing layers. The authors provide theoretical observations to support their empirical analysis.

strengths:
* To the best of my knowledge, this is the first application of untrained message-passing layers to link prediction.
* The empirical results show that untrained layers perform reasonably well.
* Some theoretical observations are included to complement the empirical analysis.

weaknesses:
* Lack of novelty: Most of the work builds directly on top of Wu et al. and mirrors many parts of it. The architecture and setup are almost exactly the same, and even some claims, like the benefit of efficiency and interpretability, are taken straight from there. This is not to say that they are not true, but for example in the case of interpretability, there is not much evidence provided beyond the fact that the architecture is simpler. 

* The theoretical contribution in the paper feels somewhat limited, with unclear takeaways. Although the authors aim to support their work with theory, the analysis falls short of substantiating the core claims. For instance, the authors state that “Our theoretical analysis further provides insights into the effectiveness of widely used node initialization schemes such as one-hot encodings and random features.” However, as this theoretical analysis is restricted to feature vectors that are pairwise orthonormal - often true for one-hot encodings and random features - it doesn’t convincingly explain why these should be more effective than other potential initializations that lack this precondition. Additionally, this analysis seems somewhat peripheral to the main focus of the paper: comparing untrained and trained MPNNs. To strengthen this aspect, I suggest clearly outlining the theoretical contributions by structuring them into theorems with proofs and more directly linking them to the paper’s central claim.

* The main point of the paper is the fact that untrained message-passing layers perform very well in comparison to their trained counterparts. To evaluate this properly, a good benchmarking framework is necessary that guarantees that the difference in predictive performance is coming from what the authors claim it’s coming from, and especially that the comparison is fair. This is where I have my main problem with this paper. No established benchmarking framework is used, and almost no attention is paid to the fact that link prediction tasks are notoriously hard to evaluate. I would recommend the authors to consult recent works like [1] and [2], which go into more detail on various problems, but let me name some important ones here: Looking at the provided code, it looks like negative sampling of edges is done randomly, which is likely to cause bad performance on these tasks. This is problematic because it’s not clear if untrained layers really perform that well in comparison or if the training procedure was just not good. From Table 2, I can tell that in several cases, the final trained linear layer (which was also trained with random negative sampling) performs worse than the untrained one. This is really surprising to me and could be due to the negative samples that were not chosen well. While looking at the code, I also noticed that the test dataset for the untrained variants is not the same as for the trained ones because the random link split in the dataset transform is initialized with `num_val=0.00, num_test=0.1` in contrast to `num_val=0.05, num_test=0.1` for the trained counterpart. While I don’t expect this one to make a huge difference, it just goes to show that the benchmarking is not done thoroughly enough to warrant the claims made in the paper. Getting link prediction right is actually quite hard, considerably more so than for node and graph-level prediction tasks, and a paper that builds on top of these results that much should put more scrutiny into it. My proposal is this: Use an existing benchmarking framework. This also makes it possible to compare the results to other papers and to run with more recent datasets from ogb, which are completely missing from this analysis. On a side note, I think that these would be quite important as they are bigger and could demonstrate the claimed scalability advantage of untrained layers.

[1] Li, Juanhui, et al. "Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking." Advances in Neural Information Processing Systems 36 (2024). 

[2] Zhu, Jing, et al. "Pitfalls in link prediction with graph neural networks: Understanding the impact of target-link inclusion & better practices." Proceedings of the 17th ACM International Conference on Web Search and Data Mining. 2024.

questions:
* While running the code I noticed that the inference for the untrained layers uses considerably more memory than even training the full GNN. So much so that I ran out of memory on my laptop. I’m wondering, could your code actually be used for much larger graphs?
* The meaning of this sentence was a bit unclear to me: “ Since the simplified architectures consist of UTMP layers followed by a trainable linear layer, the consideration of UT models which do not include the linear layer also covers all possible ablation studies” Could you clarify?
* Some other suggestions for improvements were already described together with the weaknesses. 

In light of the weaknesses I mentioned, I tend towards a reject. Especially the empirical analysis has to be improved considerably.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730673334670

thread_type:
official_review

<thread_object>
creator: reviewer_vkud

<content>
summary:
The paper proposes untrained and linear message passing layers for graph neural networks for the task of link prediction. Theoretical analysis relates the values computed at the intermediate layers to path-based and random walk based connectivity measures. An assumption is made regarding the orthogonality of the initial node features. Experimentally, the method is shown to be comparable to trained and non-linear layers in a GNN.

strengths:
The paper is written well and the presentation is good.

The analysis of the inter layer values to path-based measures is nice, though not unexpected.

Experimental results have been carried out on the usual link prediction benchmarks.

weaknesses:
The idea of untrained and linear layers (as acknowledged by the authors) has previously appeared for node classification in Wu et al, ICML 2019. So, the idea has limited novelty.

The assumption of orthogonality may not always hold especially under conditions of homophily where neighboring nodes have similar features.

Link prediction has been studied in many works and the impact of another paper is limited.

questions:
Can you comment on why orthogonality would be expected in homophilic networks?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730686470285

thread_type:
official_review

<thread_object>
creator: reviewer_jhbm

<content>
summary:
This work explores the use of untrained message passing layers in GNN for link prediction tasks. The authors showed that, experimentally, untrained message passing layers provides competitive performance when compared against fully trained layers for link prediction. The authors also provided a simple theoretical analysis to justify their claims.

strengths:
Using untrained message passing layers for GNN can be a computationally efficient approach, which is an important topic in the community.

weaknesses:
Weakness:

Overall, the presented work gives the impression of an early draft, and I find it challenging to fully assess its contributions in its current form. Below are some clear issues:

1. The presented “theoretical results” are poorly organized, and it is very challenging to judge its correctness given there is no clear distinction between the authors’ contributions and existing results. To be honest, I am not very sure what is the theoretical contributions provided by the authors. The results rely on oversimplified assumptions (e.g., orthonormality line 304); and the authors were linking random things together (e.g., PageRank line 348). It is very challenging for me to decipher what the authors what to convey here.

2. It does not seem like the experimental results support the authors’ claim. In many cases, the untrained variant of the network performs very poorly, especially in Hits@100 dataset. If the authors want to claim the simplified network performs very well, the paper should be written as such.

3. Lack of ablation experiments, intuitive results on synthetic datasets, or example results/visualizations on representative datasets.

4. The presented figure 1 is of low quality. Maybe at least show the standard deviation across different runs?

questions:
NA
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces an approach for link prediction in graphs with untrained message passing layers. The authors show that untrained MP layers can outperform fully trained models while offering better efficiency.

The reviewers appreciated the idea that untrained MP layers could improve efficiency, there were a number of issues raised about the contributions of the work, whether the approach could be used on large graphs, and the high amount of overlap with previous work from Wu in 2019. Additionally, there was a major concern raised about the benchmarking procedure utilized in this work and how it may lead to inconclusive claims about what leads to the benefits of their approach.