Link Prediction with Untrained Message Passing Layers

Author response

We thank the reviewer for their insightful comments. Individual concerns are addressed below. ## Reply to weaknesses: 1- In the paper we focus on comparing trained MP layers with their untrained counterparts. This also motivates our choice of using GAEs as an experimental setting as their simplicity allows for an objective comparison between layers. LP performance of path based measures is widely reported in the literature, however as expected such purely topological measures that do not make use of node features are usually outperformed significantly by methods that make use of features information. Some path based methods (CN, AA, RA) are already included in Table 9 in the appendix and Table 10 will also be updated to include these measures, in the updated version of the manuscript. We have now also updated the manuscript to include experiments that use NCNC [2] with trained and untrained GCN layers. 2-Due to the large size of the ogb-datasets performing systematic large scale experiments, which in our case would have to include fully trained models, is not feasible with reasonable computational resources. For instance in [1] the authors report multiple OOM (>50 GB) errors on ogb-datasets for GAEs even for rather restricted ranges of hyperparameters. This is not to say that UTMP layers can’t be used in conjunction with ogb-datasets, it is just that performing the type of systematic experiments we do in the paper are extremely time and resource intensive for these data sets. 3- The results do not change significantly when performed with random features as the use of random features can be seen as a simple change of basis in feature space. Moreover the use of one-hot encodings is not realistic for the larger attributed data sets as some of these have almost 20k nodes and there is limited value in transforming attributed data sets into unattributed ones. [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] Wang et al. Neural common neighbor with completion for link prediction.arXiv:2302.00890, 2023.

Author response

We thank the reviewer for their detailed and insightful comments. Individual points raised by the reviewer are addressed below. ## Replies to weaknesses 1- We clearly attribute the introduction of UTMP to Wu et al. and follow their formulation. Consequently some similarities in terms of training efficiency improvements with the ones reported by Wu et al. are to be expected. Our goal is to analyse UTMP layers and their surprising performance from the perspective of LP. Although the simplicity of UTMP certainly plays a factor in them being more interpretable, the claim of interpretability stems from the theoretical analysis which shows how features produced by UTMP layers encode paths, and hence also neighbourhood structures, which are essential for LP tasks. We further relate these to topological similarity measures that are widely studied in the literature and are also used as subcomponents of state of the art LP methods. 2- Our theoretical results show how features resulting from UTMP can capture essential topological characteristics, namely paths between nodes, by leveraging orthogonality. As paths capture essential topological information that is also relevant in tasks other than LP this explains why orthogonal initialisation schemes work well in practice. This does not imply, and we do not claim, that OHE or random initialisations will be more effective than other initialisation schemes that do not warrant orthogonality, under all circumstances. However, some degree of orthogonality should be expected for any initialisation scheme that uses high dimensional features as orthogonality is a typical property of collections of high dimensional vectors. The theoretical results provide an explanation as to why UTMP layers perform well in LP tasks (often better than then their trained counterparts) and hence is directly relevant to the central claim of the paper. Once UTMP layers are formulated in matrix form the results follow from simple matrix algebra hence in our opinion there is no need to formalise these in terms of theorems and proofs. 3- - We follow a standard benchmarking procedure that is widely used across the LP literature including all recent papers that introduce sota LP methods e.g [3-5]. - Random sampling of negative edges is standard in the field, in the absence of predetermined data splits. There is no reason for this to lead to a suboptimal training procedure, moreover the results we report for fully trained architectures are in agreement with those reported in the literature. - The difference in the split settings is due to the fact that UT models do not require any form of training and hence there is no need to create a validation set for UT models. Otherwise, we use the same split settings for all models with trainable parameters i.e. fully trained models and simplified (S) models. - [1] introduces a benchmarking procedure for LP, however is not widely adopted and hence using it would have distracted from the main results of the paper. In [2] the authors consider the effects of including target links while training, however this simply does apply in our case. Incidentally, the benchmarking procedure of [1] seems to include target links during training. Although, we agree that [1] is an interesting benchmarking framework, it does not imply that the standard benchmarking procedure we use in the paper is flawed in any way. - Due to the large size of the ogb-datasets performing systematic large scale experiments, which in our case would have to include fully trained models, is not feasible with reasonable computational resources. For instance in [1] the authors report multiple OOM (>50 GB) errors on ogb datasets for GAEs even for rather small ranges of hyperparameters. - The fact that for some of the attributed datasets the fully untrained architectures (UT) perform best can be explained by the fact that the inclusion of the linear layer significantly reduces the dimensionality of the feature vector which might impede the ability of the features to effectively encode neighbourhood information. Moreover, the unattributed datasets are in general smaller which inevitably limits the amount of training data putting trained methods at a disadvantage. ## Replies to questions - This is due to the pre-computation of features for UT models on the CPU to increase training efficiency, however this is an optional step that can omitted for larger dataset. - The simplified models consist of two components UTMP followed by a a trained linear layer. Hence removing the linear layer is the only possible ablation which results in the UT models. - see above. [3] Yun et al. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Neurips, 2021. [4] Wang et al. Neural common neighbor with completion for link prediction.arXiv:2302.00890, 2023. [5] Chamberlain et al. Graph neural networks for link prediction with subgraph sketching.arXiv:2209.15486, 2022.

Author response

We thank the reviewer for the review. Individual concerns are addressed below. ## Reply to weaknesses: - ‘the idea has limited novelty.’: We clearly attribute the formulation of UTMP layers to Wu et al. our goal is to provide a complementary analysis of UTMP layers from the perspective of LP where we find that they can lead to significant gains in terms of performance and training efficiency, as was observed by Wu et al. in the case of node classification. Our theoretical analysis provides additional insights on the type of information captures by UTMP layers which not only explains why UTMP works well in practical settings but also provides a theoretical interpretation of LP algorithms that use UTMP. Moreover, the theoretical analysis provides a direct link between MPGNNs and path based measures, both of which are essential components of state-of-the art LP methods. - Orthonormality is a mathematical assumption that we use to establish the connection between path based measures and features produced by UTMP layers. Although we do not expect this assumption to hold exactly in real world datasets, orthogonality is a typical/expected property for collections of high dimensional vectors/features. In the homophilic case where connected nodes tend to have similar features, as is the case for the attributed datasets we consider (see Figure 2), the deviation from orthogonality actually improves the link prediction performance as homophily leads to larger inner products/scores for positive node pairs/links. - ‘Link prediction has been studied in many works and the impact of another paper is limited.’ - LP is one of the core tasks in graph ML. Furthermore, the main motivation of the paper is not to propose another LP method but to study UTMP in the context of LP. Our findings indicate that in many instances replacing trained MP layers with their untrained counterparts leads to better performing methods. In order to further support this finding we have now included additional experiments that uses the state-of-the-art LP method NCNC [1] instead of GAEs, where again we study the effects of replacing the trained GCN layers in NCNC with untrained UTGCN layers and observe that this consistently improves LP performance. Answer to questions: - By definition orthogonality is not satisfied in homophilic graphs. However, in homophilic graphs this deviation improves LP performance as it leads to higher inner products/scores for node pairs that are connected compared to the case of orthogonal features where the inner product would be based purely on the path structure of the graph. Moreover, for sparse graphs where only a small fraction of all possible links are present, pairwise orthogonality can still hold to a high degree of accuracy even if the graph is homophilic as disconnected node pairs form the overwhelming majority of all possible node pairs. This can also be confirmed empirically for the datasets we consider (see Figure 2). [1] Wang et al. arXiv:2302.00890, 2023.

Author Response

We thank the reviewer for the concise review. Individual points raised by the reviewer are addressed below: 1- - ‘it is very challenging to judge its correctness’ : the theoretical results follow directly from the definitions provided in the paper and simple matrix algebra. We would be happy to provide further clarification if the reviewer could be more specific about the parts they believe are unclear. - ‘there is no clear distinction between the authors’ contributions and existing results.’:It would be helpful if the reviewer could provide specific references to the existing results they are referring to. Needless to say in the case we missed any such results we would be happy to acknowledge and discuss them. - ‘ To be honest, I am not very sure what is the theoretical contributions provided by the authors’ : as clearly stated multiple times in the paper the main theoretical result of the paper is to establish a direct correspondence between the features produced by UTMP layers and path based measures which are widely used as link prediction heuristics on their own as well as subcomponents in state-of-the-art LP methods. Path based measures have been widely studied in the literature in the context of LP and our results demonstrate how MPGNNs can capture and leverage the path structure of graphs in LP tasks. - ‘The results rely on oversimplified assumptions (e.g., orthonormality line 304)’ : From a mathematical standpoint we simply select an assumption that allows us to derive meaningful results. Whether the assumption of orthonormality applies to practically relevant settings is discussed at length in the paper. Just to reiterate the main points: orthonormality applies both for OHE and high dimensional features which are widely used in practice. Some degree of orthogonality is a typical/expected and a well known feature of high dimensional features spaces as can be verified experimentally (See Figure 2 in the appendix). As discussed in the paper orthogonality is not necessary for UTMP layers to perform in LP tasks and indeed deviations from orthogonality can in certain cases even increase the LP performance for instance when connected nodes tend to have more similar/non-orthogonal features as is the case in many real world data sets ( see Figure 2). - ‘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.’ : PageRank and the other measures discussed in the paper are defined in terms of path structures in graphs and are widely used and studied in the context of LP and hence clearly relate to both UTMP layers and LP. 2-As stated in the paper the fully untrained (UT) models should be considered as a baseline for how informative the features produced by UTMP layers are for LP tasks. Note that in the paper we focus on MP layers and not specific LP methods consequently in our experiments we are comparing ‘MP layers’ and not methods. For the sake of simplicity we choose a GAE setting where we consider various MP layers and replace trained layers by their untrained (UT) counterparts resulting in what is termed 'simplified' models and observe a general improvement in LP performance when UT layers are used. We have now updated the manuscript to include experiments based on NCNC [1], where we replace trained GCN layers with untrained UTGCN layers and again observe that replacing trained layers with untrained layers improves performance. 3- - ‘Lack of ablation experiments’: because the GAE architecture we consider consists of only two components: MP layers followed by a linear layer the only possible ablation is the removal of the linear layer which is results in the UT models. - ‘intuitive results on synthetic datasets’: to the best of our knowledge there are no widely used synthetic benchmarks for LP and none of the recent papers on LP methods use synthetic data sets. The underlying reason for this might be that synthetic datasets usually consist of either random graphs where the prospects of LP are fundamentally limited or highly regular graphs such as grids where LP is trivial. - ‘example results/visualizations on representative datasets’: we would be happy to include such additional examples and visualisations if the reviewer could elaborate these further. 4- - ‘The presented figure 1 is of low quality.’: The figure shows how LP performance changes as the number of UTMP layers is increased. We checked the figure again and there does not seem to be any issues regarding the resolution or readability of the figure. - ‘Maybe at least show the standard deviation across different runs?’: the typical standard deviations can be found in Table 1 which in many cases would be smaller than the symbols. Moreover it is unclear how the inclusion of std deviations would improve the figure/add any information that is relevant to what the figure is trying to convey. [1] Wang et al. arXiv:2302.00890, 2023.