Link Prediction with Untrained Message Passing Layers

## Abstract

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.

## 1 Introduction

Graph neural networks (GNNs) are a powerful class of machine learning models that can learn from graph-structured data, such as social networks, molecular graphs, and knowledge graphs.
GNNs have emerged as an important tool in the machine learning landscape, due to their ability to model complex relationships and dependencies within data with applications in a variety of fields where data exhibits a complex topology that can be captured in a graph.
This is shown by a multitude of studies, including Basu et al. (); Wang et al. (); Fu et al. (); Jaini et al. (); Puny et al. (), which highlight the versatility and adaptability of GNNs for machine learning tasks across a range of fields.

One of the key concepts underlying GNNs is message passing (MP) Gilmer et al. (), which operates by propagating and aggregating information between nodes in the graph, using message and update functions possibly with learnable parameters.
However, designing and training effective GNNs can be challenging, as they may suffer from issues such as over-smoothing or over-parameterization, and since training can be computationally demanding.

In order to address these shortcomings recent efforts have concentrated on finding simplified architectures that are both more interpretable and easier to optimize.
Approaches to simplify GNNs have almost exclusively taken the point of view of node and graph classification.
With our work, we aim to complement existing works by analysing simplified and untrained architectures from the perspective of link prediction Zhang and Chen ().
Link prediction is an important task for graph learning algorithms with applications such as recommender systems, spam mail detection, drug repurposing, and many more Zhang and Chen ().
Moreover, we show that link prediction can also provide a complementary perspective for the theoretical analysis of GNNs Zhou et al. (); Chamberlain et al. ().

In this work, we explore the use of untrained message passing layers for link prediction in data on unlabelled graphs with high dimensional features.
By formulating Untrained Message Passing (UTMP) layers, we follow an approach similar to that of *Simplified Graph Convolutional Networks* introduced by Wu et al.Wu et al. ().
This approach simplifies GNN architectures by removing trainable parameters and nonlinearities resulting in an architecture that can be clearly separated into two components: an untrained message passing/feature propagation steps followed by a linear classifier. In addition to these we also consider fully untrained architectures based on simple inner products of features obtained after $l$ iterations of UTMP layers as a baseline and find that these features produced by UTMP layers are already highly informative leading to surprisingly high link prediction performances.

We base our analysis on untrained versions of four widely used MP architectures, namely Graph Convolutional Networks (GCN)Kipf and Welling (), SAGE Hamilton et al. (), GraphConv Morris et al. () and GIN Xu et al. ().
We test these untrained message passing layers on a variety of datasets that cover a wide range of sizes, node features, and topological characteristics ensuring a comprehensive evaluation of the models.
Interestingly, for the large majority of datasets, we find that untrained message passing layers actually perform better than their fully trained counterparts while being highly interpretable and much easier to optimize.

In our theoretical analysis we establish a direct connection between untrained message passing layers and path based measures. Path based methods and measures can capture the indirect connection strength between node pairs nodes in the absence of a direct link connecting the nodes. Consequently, path based measures and methods have been widely used in traditional link prediction methods Martínez et al. (); Kumar et al. () and also play a key role in the state of the art methods Zhu et al. (); Zhang and Chen (). Our theoretical analysis is based on the assumption that initial node features are orthonormal which covers widely used initialization schemes such as as one-hot encodings and high dimensional random features, and also holds approximately for many empirical data sets with high dimensional features. Hence, our theoretical findings also provide new insights into the effectiveness of the widely used initialization schemes of one-hot encodings and high dimensional random features in graph representation learning. Our results show that untrained versions of message passing layers are highly amenable to theoretical analysis and hence could potentially serve as an general ansatz for the theoretical analysis of GNNs in settings beyond link prediction.

We have structured the remainder of the paper as follows:
In Section 2, we summarize related works on untrained and simplified GNNs.
Section 3 introduces the untrained message passing architectures that form the basis of our investigation.
Here, we further provide a theoretical analysis of these layers from the perspective of node similarity measures that account both for node features and the graph topology.
Section 4 details the experimental setup and results.
Finally, in Section 5 we present our conclusions and highlight the potential for future work.

To ensure replicability of our results, we make our code available online (^1^11[https://zenodo.org/records/11237762](https://zenodo.org/records/11237762)).

## 2 Related Work

Our work is motivated by recent works that investigate simplified and untrained GNNs from different perspectives. We follow an approach that is closely related to Wu et al. () which simplifies GNNs by successively removing trainable parameters from layers and nonlinearities between consecutive layers. This results in an architecture that can be separated into two components. The first component consists of feature propagation in untrained message passing layers of which the output is then fed into a linear layer resulting in models that scale to larger data sets while being naturally interpretable. Wu et al. also provide a theoretical analysis of simplified models in the context of node classification reducing the model to a fixed low-pass filter followed by a linear classifier. The paper also empirically evaluates the simplified architectures on various downstream applications and shows that simplified architectures do not negatively impact accuracy while being computationally more efficient than their more complex counterparts.

Other works have focused on finding untrained subnetworks. For instance Huang et al. () explores the existence of untrained subnetworks in GNNs that can match the performance of fully trained dense networks at initialization, without any optimization of the weights. The paper leverages sparsity as the core tool to find such subnetworks and shows that they can substantially mitigate the over-smoothing problem, hence enabling deeper GNNs without bells and whistles. The paper also shows that the sparse untrained subnetworks have appealing performance in out-of-distribution detection and robustness to input perturbations. Similarly, in Böker et al. () the authors demonstrate that GNNs with randomly initialized weights, without training, can achieve competitive performance compared to their trained counterparts focusing on the problem of graph classification. Other more recent works on untrained GNNs include Dong et al. () where the authors propose a training free linear GNN model for semi supervised node classification in text attributed graphs and Sato () that defines training free GNNs for transductive node classification based on using training labels as features.

Link prediction is widely studied problem with a multitude of methods. Our method is related to a both GNN based methods where the prevalent approach is the use of Variational Graph Autoencoders (V-GAE) Kipf and Welling () and more traditional methods that are rely on path and random walk based measures for link prediction Kumar et al. (). Indeed, one of our main results is to establish a link between GNN based approaches and traditional path based measures. Some more recent methods such as SEAL Zhang and Chen () and WalkPool Pan et al. () rely on extracting local subgraphs around target links and frame link prediction as a graph classification problem. Although subgraph extraction based methods can out perform GNN based methods in link prediction tasks the subgraph extraction process can be very resource intensive for large networks negatively affecting the scalability of these methods. NBFNet Zhu et al. () is another state-of-the-art method that is motivated by the Bellman-Ford algorithm. NBFNet is based on learning representations of paths between target nodes and aggregation functions for these representations. While NBFNet scales more favorably compared to subgraph extraction based methods it still needs to compute representations for large numbers of paths to predict links and hence has worse scaling behavior compared to purely GNN based link prediction methods Zhu et al. ().

From a theoretical perspective, our results also relate to recent works on the effectiveness of random node initializations and one-hot encodings. For instance Sato et al. () and Abboud et al. () focus on the effect of random node initializations of the expressivity of GNNs in the context of graph classification while Cui et al. () explore various encodings for the task including node and graph classification. Our analysis complements these works from the point of view of link classification and establishes a link between features derived from random and one hot initializations and, path based topological features.

## 3 Message Passing Architectures

Prior to introducing the message passing architectures investigated in our work, we first clarify the notation used throughout the paper.
Let $G(V,E)$ be an undirected graph with vertex set $V=\{v_{1},v_{2}\ldots v_{N}\}$, edges $E\subseteq V\times V$ and no self-loops, i.e. $(v,v)\notin E\quad\forall v\in V$.
We denote the adjacency matrix of the graph as $A$ and define $\tilde{\mathbf{A}}:=\mathbf{A}+\mathbf{I}$, where $\mathbf{I}$ is the identity matrix, i.e. $\tilde{\mathbf{A}}$ denotes the adjacency matrix of the graph $G$ that explicitly includes all self-loops.
We use $\mathcal{N}(v)$ to denote the neighborhood of a node $v$, i.e. the set $\{w\in V:(v,w)\in E\}$, and use $\tilde{\mathcal{N}}(v):=\mathcal{N}(v)\cup\{v\}$ to denote the neighborhood of $v$ in the graph with self-loops.
Similarly, we denote the degree of a node $v$ as $d(v)$ and $\tilde{d}(v)=d(v)+1$.
The initial feature vector of node $v$ is denoted as $h_{v}^{(0)}$ and we use $h_{v}^{(l)}$ to denote the updated feature vector of node $v$ after $l$ rounds of message passing. Although we restrict our discussion to undirected and unweighted graphs the generalization of our definitions and results to weighted graphs is straightforward.

Prior to defining untrained versions, we first introduce the message passing rules of the four GNN architectures considered in our work, using the unified notation above.

#### Graph Convolutional Networks Kipf and Welling ( 2016a )

GCNs were introduced as a scalable approach for semi-supervised learning on graph-structured data. GCNs are based on an efficient variant of convolutional neural networks which operate directly on graphs. The MP layer of GCN is given by:

$$ $h_{v}^{(l)}=W^{(l),\top}\sum_{u\in\tilde{\mathcal{N}}(v)}\frac{1}{\sqrt{\tilde {d}_{u}\tilde{d}_{v}}}h_{u}^{(l-1)}$ $$

where $W^{(l),\top}$ is the transposed weight matrix for this layer.

#### GraphSAGE Hamilton et al. ( 2017 )

GraphSAGE is a type of Graph Neural Network that uses different types of aggregators such as mean, gcn, pool, and lstm to aggregate information from neighboring nodes.
The MP layer in GraphSAGE uses the following formula:

$$ $h_{v}^{(l)}=W^{(l)}_{1}h_{v}^{(l-1)}+W^{(l)}_{2}\cdot\text{AGG}_{u\in\mathcal{ N}(v)}h_{u}^{(l-1)},$ $$

where $W^{(l)}_{\{1,2\}}$ are learned weight matrices at layer $l$, $AGG$ is an aggregation function (such as mean, sum, max).

Throughout this paper use the following slightly modified version of the SAGE layer :

$$ $h_{v}^{(l)}=W_{1}^{(l)}\cdot\frac{1}{\tilde{d}_{v}}\sum_{u\in\tilde{\mathcal{N }}(v)}h_{u}^{(l-1)},$ $$

which we found to produce superior results for link prediction.

#### GIN Xu et al. ( 2018 )

The Graph Isomorphism Network Convolution (GIN) is a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test.
It is designed to capture the local structure of a graph by aggregating feature information from a node’s neighborhood.
The mathematical formula for GIN is as follows:

$$ $h_{v}^{(l)}=\Theta\big{(}(1+\epsilon)\cdot h_{v}^{(l-1)}+\sum_{u\in\mathcal{N} (v)}h_{u}^{(l-1)}\big{)},$ $$

where $\Theta$ denotes a Multilayer Perceptron after each message passing layer, which in our implementation includes two Linear layers and a Rectified Linear Unit (ReLU) activation function following each Linear layer (code adapted from Böker et al. (); Morris and Ningyuan Huang ()).

#### GraphConv Morris et al. ( 2019 )

GraphConv is a generalization of GNNs, which can take higher-order graph structures at multiple scales into account. The mathematical formulation of this is as follows:

$$ $h_{v}^{(l)}=W_{1}^{(l)}h_{v}^{(l-1)}+W_{2}^{(l)}\sum_{u\in\mathcal{N}(v)}h_{u} ^{(l-1)}$ $$

where $W^{(l)}_{\{1,2\}}$ are learned weight matrices.

### 3.1 Untrained MP Architectures

For the purpose of our theoretical and experimental evaluation, we now define the untrained counterparts of the four Message Passing Neural Network (MPNN) architectures introduced in the previous section.
We specifically eliminate all learnable components and replace them with identity matrices.
Our objective is to obtain the simplest form for the update function that retains the general message passing strategy, which includes the predefined update message passing functions and aggregation methods while removing all learnable parameters and non-linearities.
We obtain the following functions that capture the aggregation and update step in the untrained versions of the message passing layers:

- UTGCN: $h_{v}^{(l)}=\sum_{u\in\tilde{\mathcal{N}}(v)}\frac{1}{\sqrt{\tilde{d}_{u}
\tilde{d}_{v}}}h_{u}^{(l-1)}$
- UTSAGE: $h_{v}^{(l)}=\frac{1}{\tilde{d}_{v}}\sum_{u\in\tilde{\mathcal{N}}(v)}h_{u}^{(l-
1)}$
- UTGIN: $h_{v}^{(l)}=(1+\epsilon)\cdot h_{v}^{(l-1)}+\sum_{u\in\mathcal{N}(v)}h_{u}^{(l
-1)}$
- UTGraphConv: $h_{v}^{(l)}=\sum_{u\in\tilde{\mathcal{N}}(v)}h_{u}^{(l-1)}$

In general, we consider the case where all nodes have self-loops, i.e. the feature of a node itself is used in the aggregation step.
The modified architectures, now simplified, serve as the layers for our untrained experiments.
To maintain simplicity and fairness across all methods, we refrain from using edge weights in our models.
Further setting $\epsilon=0$ for GINs results in a uniform formula across both models: $h_{v}^{(l)}=\sum_{u\in\tilde{\mathcal{N}}(v)}h_{u}^{(l-1)}$.
Henceforth we will refer to both models as UTGIN.

The simplified message passing layers can also be expressed in matrix form:

$$ $\mathbf{H}^{(l)}=\mathbf{S}\mathbf{H}^{(l-1)}=\mathbf{S}^{l}\mathbf{H}^{(0)},$ $$

where $\mathbf{H}^{(0)}\in\mathbb{R}^{n\times d}$ is the initial feature matrix, and $\mathbf{H}^{(l)}$ the feature matrix after $l$ iterations of message passing. Following, the definitions of UTMP layers above we have $\mathbf{S}=\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}$ for UTGCN and $\mathbf{S}=\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}$ for UTSAGE, where $\tilde{\mathbf{D}}$ is the degree matrix with diagonal entries $\tilde{\mathbf{D}}_{uu}=\sum_{v}\tilde{\mathbf{A}}_{uv}$. Similarly, for UTGIN $\mathbf{S}=\tilde{\mathbf{A}}$. The generalization of UTMP layers to undirected weighted graphs can be obtianed by simply replacing the adjacency matrix and related quantities with their weighted counterparts in the formulation of $\mathbf{S}$.

### 3.2 Simplified architectures

Following the construction of Wu et al. for the case of node classification we add a final trained linear layer before the final dot product. We refer to such architectures that include a final trained linear layer after the UTMP layers as ’simplified’ in accordance with Wu et al. () and include an ’S’ in the abbreviations of these models, e.g. SGCN. This results in an architecture where the final node features are given by:

$$ $\mathbf{H}^{(l)}=\Theta\mathbf{S}^{l}\mathbf{H}^{(0)},$ $$

where $\Theta$ is the learned weight matrix of the linear layer. In the case of simplified GNN architectures, the trained linear layer can also be interpreted as a modified positive semi-definite inner product in the form of $<\Theta h_{v}^{l},\Theta h_{u}^{l}>$ where $\Theta$ is the weight matrix of the linear layer.

In the case of link prediction features produced by UTMP layers can actually be used to construct fully untrained architectures that only consist of feature propagation steps followed by an inner product. In practice we found that such architectures based solely on UTMP layers do work well showing that UTMP layers produce highly informative features for link prediction.

### 3.3 UTMP layers and path based measures

Building on the formulations of the untrained layers above, in the following we provide a theoretical analysis that relates the inner products of features resulting from untrained message passing layers to pair-wise measures of node similarity that are based on characteristics of *paths* in the underlying graph. Such path based measures quantify the indirect connection strength between node pairs in the absence of a direct link connecting the nodes. In order to relate path based measures and untrained MP layers we will assume that initial feature vectors are pairwise orthonormal i.e. $<h_{v}^{(0)},h_{u}^{(0)}>=\delta_{u,v}$.

A path of length $l$ is defined as a sequence of $l+1$ vertices $(v_{0},v_{1}\ldots v_{l})$ such that $(v_{i},v_{i+1})\in E$ for all $0\leq i<l$. We denote the space of a set of all paths of length $l$ between $u$ and $v$ as $P^{l}_{uv}$. The number of paths of length $l$ between any $u$ and $v$ is given by the $l^{th}$ power of the adjacency matrix i.e. $|P^{l}_{uv}|=\tilde{\mathbf{A}}^{l}_{uv}$. Note that since we assume self-loops on all vertices $P^{l}_{uv}$ implicitly also includes shorter paths between $u$ and $v$. Similarly, paths of length $l$ between vertices $u$ and $v$ also determine to the probability of a random walk starting at $u$ reaching $v$ which is given by $P(u\xrightarrow{l}v)=\sum_{p\in P^{l}_{uv}}\prod_{i\in p-[v]}\frac{1}{\tilde{d
}_{i}}$, where $p-[v]$ denotes that the last vertex ($v$) is not included in the product. The random walk probability can also be expressed in matrix form $P(u\xrightarrow{l}v)=(\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}})^{l}_{uv}$.

Now we consider inner products of features after $l$ iterations of message passing which is given by $<h_{u}^{(l)},h_{v}^{(l)}>=(\mathbf{S}^{l}\mathbf{H}^{(0)}\mathbf{H}^{(0)\top}(
\mathbf{S}^{l})^{\top})_{uv}$. For
orthonormal features the inner products of features reduces to $\mathbf{H}^{(0)}\mathbf{H}^{(0)\top}=\mathbf{I}$ and we obtain the following expression for the inner product of the features after $l$ iterations of UTMP layers:

$$ $<h_{u}^{(l)},h_{v}^{(l)}>=(\mathbf{S}^{l}(\mathbf{S}^{l})^{\top})_{uv}.$ $$

For UTGCN we have $\mathbf{S}=\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}$ and the inner product after $l$ layers can be expressed in terms of paths of length $2l$ between $u$ and $v$ as:

$$ $<h_{u}^{(l)},h_{v}^{(l)}>=\frac{1}{\sqrt{\tilde{d}(u)\tilde{d}(v)}}\sum_{p\in P ^{2l}_{uv}}\prod_{i\in[p]}\frac{1}{\tilde{d}_{i}},$ $$

where $[p]$ denotes the path $p$ with the first and last vertices removed. The above expression is equivalent to $\sqrt{P(u\xrightarrow{2l}v)P(v\xrightarrow{2l}u)}$ i.e. the geometric mean of the probabilities that a random walk starting at either $u$ or $v$ to reaches the other in $2l$ steps. Similarly, for UTSAGE we have $\mathbf{S}=\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}$ and the inner product can be expressed in terms of paths in $P^{2l}_{uv}$ as:

$$ $<h_{u}^{(l)},h_{v}^{(l)}>=\sum_{p\in P^{2l}_{uv}}\prod_{i\in p-m(p)}\frac{1}{ \tilde{d}_{i}},$ $$

where $m(p)$ is the midpoint of the path $p$. The above epression is equivalent to $<h_{u}^{(l)},h_{v}^{(l)}>=\sum_{i}P(u\xrightarrow{l}i)P(v\xrightarrow{l}i)$ and hence corresponds to the probability that two simulatenous random walks starting at $u$ and $v$, respectively, meet after $l$ steps at some midpoint. Finally, for UTGIN we have $\mathbf{S}=\tilde{\mathbf{A}}$ and hence:

$$ $<h_{u}^{(l)},h_{v}^{(l)}>=|P^{2l}_{uv}|.$ $$

Although the condition of orthonormality might seem quite restrictive at first glance it applies in many practical settings, though in some cases only approximately. Moreover, orthogonality only needs to be satisfied in the common $l$-neighbourhood of the nodes. One hot encodings are just one example of orthonormal features used in practice. Orthonormality also applies in the case of high dimensional random feature vectors as for sufficiently large dimensions any set of $k$ independent random vectors is almost orthogonal Eaton (). Similar results also hold for random high dimensional binary features that are sparsely populated for which the expected value of the inner product of two vectors scales as $O(1/k)$ for dimension $k$.

High dimensional features of empirical data sets also show similar characteristics to their random counterparts. For instance, empirical feature vectors of randomly selected node pairs tend to be approximately orthogonal, notwithstanding the fact that features of connected node pairs can be highly correlated Nt and Maehara (), as can be verified experimentally (see Sec.C).

As mentioned before in the case of simplified GNN architectures, the final trained linear layer can be interpreted as a modified positive semi-definite inner product and the orthogonality results for high dimensional random features also apply to such more general inner products. However, note that normality is no longer guaranteed i.e. $<\Theta h_{v},\Theta h_{u}>\sim\delta_{u,v}|h_{u}|^{2}_{\Theta}$.

### 3.4 Triadic closure and other path based measures

Triadic closure, also known as transitivity, refers to the tendency for nodes in real-world networks to form connections if they share (many) common neighbors. As such triadic closure has been widely studied as a mechanism that drives link formation in complex real-world networks Rapoport (); Holland and Leinhardt ().
Moreover, node similarity measures that build on triadic closure in social networks have been used for similarity-based link prediction algorithms Lü and Zhou ().

Given a pair of nodes $(u,v)$, the tendency of them to be connected due to triadic closure can be quantified by simply counting the number of common neighbours between the two vertices i.e. $T(u,v)=|N(u)\cap N(v)|$ which corresponds to $l=1$ for UTGIN, assuming that $u$ and $v$ are not connected in the graph as is customary in a link prediction scenario. In practice, one might further want to account for the fact that in general nodes with higher degrees also have a larger probability of having common neighbours, for instance by normalizing by the degrees, i.e.: $T_{d}(u,v)=|N(u)\cap N(v)|/\tilde{d}(u)\tilde{d}(v)$, which corresponds to $l=1$ for UTSAGE. One can go one step further and also take into account the degrees of the common neighbours themselves since high degree nodes are by definition common neighbours of more node pairs, for instance by weighing common neighbours according to their degree $T_{n}(u,v)=\frac{1}{\sqrt{\tilde{d}(u)\tilde{d}(v)}}\sum_{i\in N(u)\cap N(v)}
\frac{1}{\tilde{d}_{i}}$ which in our case corresponds to UTGCN with $l=1$.

Our results also link UTMP layers to other topological similarity measures that are widely used in link prediction heuristics such as the Adamic-Adar (AA) index Adamic and Adar (), Resource Allocation (RA) Zhou et al. (), the Katz index Katz (), rooted PageRank Brin and Page () and SimRank Jeh and Widom (). For instance the AA index, given by $AA(u,v)=\sum_{i\in N(u)\cap N(v)}\frac{1}{\log\tilde{d}_{i}}$, and $RA(u,v)=\sum_{i\in N(u)\cap N(v)}\frac{1}{\tilde{d}_{i}}$ differ only slightly from the triadic closure measures we obtained for UTMP layers. Similar results also hold for other path based measures such as rooted PageRank, the Katz index and SimRank which can be defined in terms of power series over paths of different lengths. For instance, SimRank similarity between nodes $u$ and $v$ is defined as $s(x,y)=\sum_{l}P_{uv}(l)\gamma^{l}$ where $P_{uv}(l)$ is the probability that two random walks starting at $u$ and $v$ meet after $l$ steps and $0<\gamma<1$ is a free parameter. Similarly the Katz index is defined as $Katz(u,v)=\sum_{l}\mathbf{A}^{l}_{uv}\gamma^{l}$ and rooted PageRank is defined as $PR(u,v)=(1-\gamma)\sum_{l}\frac{P(u\xrightarrow{l}v)+P(v\xrightarrow{l}u)}{2}
\gamma^{l}$ again with $0<\gamma<1$ being a free parameter. Hence, the Katz index is closely realted to UTGIN and rooted PageRank is closely related to UTGCN, the main difference being that these measures also include paths of odd length which UTGIN and UTGCN include only indirectly through the inclusion of self loops in their formulation.

## 4 Experiments and Results

In the following, we provide details on our experimental setup.
We evaluate GNN architectures on a variety data sets summarized in Table 3.
The data sets cover both attributed graphs where nodes have additional high-dimensional features (Cora small, CiteSeer small, Cora, CoraML, PubMed, CiteSeer, DBLP) and non-attributed graphs that do not contain any node features. Data sources and summary statistics of the data sets can be found in Table 3. We use the area under the Receiver Operator Characteristic curve (ROC-AUC) to link prediction performance for all data sets.

### 4.1 Experimental Setup

To ensure a fair comparison among models we maintain the same overall architectures across all experiments where each trainable message passing layer is followed by an Exponential Linear Unit (ELU) and the optimal number of layers for models is determined via hyperparameter search. Upon completion of the message passing layers, we introduce a final linear layer for both trained and simplified models. We also consider untrained (UT) models that do not include this final linear layer and directly take the inner product between the propagated features of the source and target nodes resulting in a parameter-free and hence fully untrained model.

For each model, the optimal values of the learning rate, the number of layers, and hidden dimensions are determined through an exhaustive search over the values given in Table 4). The optimal hyperparameters values for attributed and non-attributed datasets are given in Table 5 and Table 6, respectively. We implement a three-fold cross-validation procedure to select the optimal hyperparameter values.

We use Adam Kingma and Ba () as an optimization function and employ binary cross entropy with logits as our loss function. All datasets are transformed by normalizing the node features and randomly splitting the dataset, with $10\%$ allocated to the test set, $5\%$ to the validation set, and the remainder to the training set. Each model configuration is run $10$ times, with the results averaged over these runs.
Our training and testing procedures are based on the methodology outlined in pyg (), where we perform a new round of negative edge sampling for each training epoch. We limit the maximum number of epochs to 10,000 and also incorporate an early stopping mechanism in our training process by terminating training whenever there is no improvement in the validation set results over a span of $250$ epochs.

For the simplified models we pre-compute node features corresponding to the untrained message passing layers as these do not change during training. We use one-hot encoding as initial node features for the non-attributed datasets.

**Table 1: Link Prediction accuracy for attributed networks as measured by ROC-AUC. Red values correspond to the overall best model for each dataset, and blue values indicate the best-performing model within the same category of message passing layers.**
| Models | Cora (small) | CiteSeer (small) | Cora | Cora ML | PubMed | CiteSeer | DBLP |
| --- | --- | --- | --- | --- | --- | --- | --- |
| GCN | 92.82 ± 0.83 | 91.67 ± 1.14 | 97.87 ± 0.18 | 94.67 ± 0.51 | 97.54 ± 0.09 | 94.22 ± 0.77 | 96.63 ± 0.12 |
| SGCN | 95.3 ± 0.68 | 96.22 ± 0.4 | 98.6 ± 0.07 | 96.82 ± 0.43 | 97.94 ± 0.16 | 95.9 ± 0.77 | 97.1 ± 0.14 |
| UTGCN | 93.82 ± 0.68 | 96.0 ± 0.24 | 95.72 ± 0.12 | 93.93 ± 0.45 | 94.29 ± 0.24 | 92.74 ± 0.81 | 94.91 ± 0.32 |
| SAGE | 91.41 ± 0.38 | 90.78 ± 1.79 | 97.7 ± 0.08 | 94.38 ± 0.58 | 95.6 ± 0.18 | 93.58 ± 0.87 | 96.16 ± 0.25 |
| SSAGE | 94.47 ± 0.64 | 95.75 ± 0.29 | 98.23 ± 0.1 | 95.74 ± 0.6 | 95.88 ± 0.22 | 95.14 ± 0.9 | 96.29 ± 0.12 |
| UTSAGE | 92.77 ± 0.5 | 96.07 ± 0.43 | 96.85 ± 0.13 | 93.45 ± 0.81 | 88.12 ± 0.29 | 91.78 ± 0.85 | 93.36 ± 0.31 |
| GIN | 91.65 ± 0.73 | 90.62 ± 1.17 | 97.69 ± 0.13 | 94.54 ± 0.32 | 96.27 ± 0.13 | 92.88 ± 0.87 | 96.11 ± 0.25 |
| GraphConv | 92.06 ± 0.67 | 91.24 ± 0.32 | 97.94 ± 0.11 | 95.34 ± 0.25 | 96.39 ± 0.15 | 92.7 ± 0.73 | 96.09 ± 0.23 |
| \hdashlineSGIN | 92.87 ± 0.37 | 93.6 ± 0.48 | 97.82 ± 0.11 | 95.26 ± 0.41 | 96.37 ± 0.23 | 94.13 ± 0.4 | 95.85 ± 0.11 |
| UTGIN | 85.45 ± 1.28 | 85.7 ± 0.82 | 88.93 ± 0.35 | 86.86 ± 0.98 | 88.76 ± 0.25 | 91.11 ± 0.93 | 92.25 ± 0.29 |

### 4.2 Experimental Results

In the following section, we discuss the results of our experiments for link prediction in graphs with node attributes (i.e. in graphs where nodes have additional features) and non-attributed graphs separately.
This diverse selection of data sets allows us to thoroughly evaluate the capabilities of the models for graphs from different application scenarios, with different sizes, and different topological characteristics.

Results for attributed graphs are given in Table 1 where we find that the simplified model SGCN performs best on all attributed datasets, with performance comparable to more sophisticated state-of-the-art models Pan et al. (); Zhang and Chen (); Zhu et al. () (See Table 9 in the Appendix) . Moreover, we find that in general simplified models perform better than or on par with their fully trained counterparts on almost all datasets, with the single exception of GIN on DBLP. We also find that the fully untrained (UT) architectures already provide a very good baseline and some cases even outperform fully trained versions. This demonstrates that the raw features produced by UTMP layers, which the simplified models are trained on, are already highly informative for link prediction in accordance with our theoretical results. Note that, the fully untrained (UT) models can be computed very efficiently via sparse matrix multiplication.

In the case of non-attributed graphs (Table 10) we observe that models based on UTMP layers achieve the highest score on 6 out of 8 datasets, with the exceptions being NS and Router datasets. Moreover, we find that the fully untrained UTGCN model outperforms all other models on the ’Celegans’, ’PB’, ’USAir’, ’E-coli’ which can be attributed to the reduced dimension of the learned features that come with the linear layers present in the simplified and fully trained models. In contrast to the trained variants UTGCN maintains the higher initial dimensionality of the features and hence can more efficiently discriminate between local neighborhoods by maintaining orthogonality. Furthermore, as we used one hot encodings as initial node features for the unattributed datasets orthonormality is satisfied exactly and therefore there is a one-to-one correspondence between node similarities produced by UTGCN and path based topological measures.

**Table 2: Link Prediction accuracy for non-attributed networks as measured by ROC-AUC. Red values correspond to the overall best model for each dataset, and blue values indicate the best-performing model within the same category of message passing layers.**
| Models | NS | Celegans | PB | Power | Router | USAir | Yeast | E-coli |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GCN | 95.22 ± 1.8 | 87.98 ± 1.45 | 92.91 ± 0.3 | 74.68 ± 2.67 | 91.42 ± 0.44 | 93.56 ± 1.53 | 94.49 ± 0.61 | 98.48 ± 0.22 |
| SGCN | 95.17 ± 0.96 | 89.38 ± 1.42 | 93.86 ± 0.42 | 81.08 ± 1.2 | 77.51 ± 1.85 | 94.08 ± 1.43 | 95.74 ± 0.33 | 98.32 ± 0.2 |
| UTGCN | 94.76 ± 1.03 | 91.47 ± 1.4 | 94.49 ± 0.38 | 72.97 ± 1.27 | 61.68 ± 1.01 | 94.81 ± 1.1 | 94.0 ± 0.43 | 99.37 ± 0.1 |
| SAGE | 95.9 ± 0.86 | 87.32 ± 1.61 | 92.94 ± 0.57 | 74.17 ± 2.03 | 62.6 ± 3.3 | 93.37 ± 1.2 | 94.43 ± 0.67 | 98.22 ± 0.13 |
| SSAGE | 95.21 ± 1.09 | 88.05 ± 1.8 | 91.66 ± 0.43 | 81.84 ± 1.49 | 70.1 ± 1.3 | 92.25 ± 1.45 | 95.72 ± 0.31 | 93.59 ± 0.14 |
| UTSAGE | 94.72 ± 1.07 | 84.48 ± 1.87 | 86.46 ± 0.64 | 72.96 ± 1.26 | 61.47 ± 0.99 | 87.94 ± 1.58 | 93.45 ± 0.45 | 85.56 ± 0.37 |
| GIN | 95.24 ± 1.22 | 86.74 ± 2.3 | 93.04 ± 0.99 | 71.97 ± 2.3 | 87.84 ± 3.05 | 92.14 ± 0.98 | 94.7 ± 0.45 | 98.43 ± 0.24 |
| GraphConv | 95.73 ± 1.4 | 86.64 ± 2.31 | 92.99 ± 0.87 | 74.31 ± 1.93 | 80.84 ± 1.28 | 91.16 ± 1.76 | 94.94 ± 0.38 | 98.32 ± 0.22 |
| \hdashlineSGIN | 95.48 ± 0.88 | 88.31 ± 1.3 | 93.72 ± 0.48 | 73.73 ± 1.69 | 72.83 ± 1.28 | 93.02 ± 1.37 | 95.63 ± 0.49 | 97.68 ± 0.2 |
| UTGIN | 94.62 ± 1.05 | 86.48 ± 1.29 | 92.77 ± 0.51 | 72.93 ± 1.27 | 61.67 ± 1.02 | 93.44 ± 0.84 | 92.94 ± 0.41 | 95.81 ± 0.22 |

Finally, we also examine the effect of increasing the number of UTMP layers using fully untrained (UT) models.
Our results in Fig.1 indicate that, in general, UTGCN and UTSAGE maintain their performance as the number of layers is increased whereas the performance of UTGIN decreases sharply with more layers. This behavior can be attributed to the lack of degree based normalization in the formulation of GIN (see Sec.3.3) which leads UTGIN to be dominated by longer paths, and hence longer distance correlations, as the number of layers increases.

Figure: Figure 1: The effect of increased layer size for fully untrained models.
Refer to caption: x1.png

## 5 Conclusion

In this work, we explored the application of graph neural networks with untrained message passing layers for link prediction.
Interestingly, our experimental evaluation of twelve data sets shows that simplifying GNNs architectures by eliminating trainable parameters and non-linearities not only enhances the link prediction performance of GNNs, but also improves their interpretability and training efficiency.
As such untrained message passing layers offer a computationally efficient alternative to their fully trained counterparts that naturally scales to large graphs and in many cases produces state-of-the-art results.
To complement our experimental results, we offered a theoretical perspective on untrained message passing, analytically establishing links between features generated by untrained message passing layers and path-based topological measures.
We found that the link prediction offers a complementary perspective for analysing MPNNs and provides insights into the topological features captured by widely used initialization schemes such as random features and one-hot encodings.

In future work, we hope to extend our study to other classes of graphs, such as directed, signed, weighted, and temporal networks.
The conceptual simplicity of untrained message passing layers might also be a useful guide in designing new graph neural network architectures or adapting existing architectures to directed or temporal networks.
We thus believe that our work is of interest both for the community of researchers developing new machine learning methods, as well as for practitioners seeking to deploy efficient and resource-saving models in real-world scenarios.

## Acknowledgement

Lisi Qarkaxhija and Ingo Scholtes acknowledge funding from the German Federal Ministry of Education and Research (BMBF) via the Project "Software Campus 3.0", Grant No. (FKZ) 01IS24030, which is running from 01.04.2024 to 31.03.2026. Ingo Scholtes acknowledges funding through the Swiss National Science Foundation (SNF), Grant No. 176938.

## Appendix A Dataset details

**Table 3: Overview of the datasets, sources, and node features for attributed graphs (top group) used in our experimental evaluation.**
| Dataset | $|$V$|$ | $|$E$|$ | Features | Metric |
| --- | --- | --- | --- | --- |
| Cora small Yang et al. [] | 2,708 | 10,556 | 1,433 | ROC-AUC |
| CiteSeer small Yang et al. [] | 3,327 | 9,104 | 3,703 | ROC-AUC |
| Cora Bojchevski and Günnemann [] | 19,793 | 126,842 | 8,710 | ROC-AUC |
| Cora ML Bojchevski and Günnemann [] | 2,995 | 16,316 | 2,879 | ROC-AUC |
| PubMed Bojchevski and Günnemann [] | 19,717 | 88,648 | 500 | ROC-AUC |
| CiteSeer Bojchevski and Günnemann [] | 4,230 | 10,674 | 602 | ROC-AUC |
| DBLP Bojchevski and Günnemann [] | 17,716 | 105,734 | 1,639 | ROC-AUC |
| NS Newman [] | 1,461 | 2,742 | - | ROC-AUC |
| Celegans Watts and Strogatz [] | 297 | 2,148 | - | ROC-AUC |
| PB Ackland et al. [] | 1,222 | 16,714 | - | ROC-AUC |
| Power Watts and Strogatz [] | 4,941 | 6,594 | - | ROC-AUC |
| Router Spring et al. [] | 5,022 | 6,258 | - | ROC-AUC |
| USAir Batagelj and Mrvar [] | 332 | 2,126 | - | ROC-AUC |
| Yeast Von Mering et al. [] | 2,375 | 11,693 | - | ROC-AUC |
| E-coli Zhang et al. [] | 1,805 | 15,660 | - | ROC-AUC |

## Appendix B Hyperparameter choices

All hyperparameter searches and experiments were conducted on a workstation with AMD Ryzen Threadripper PRO 5965WX 24-Cores with 256 GB of memory and two Nvidia GeForce RTX 3090 Super GPU, and also AMD Ryzen 9 7900X 12-Cores with 64 GB of memory and an Nvidia GeForce RTX 4080 GPU.

**Table 4: The hyperparameter space for our experiments. It is worth noting that only the number of MPNN layers applies to the untrained models.**
| Hyperparameter | Values |
| --- | --- |
| Number of MPNN layers | 1,2,3 |
| Learning Rate | 0.2, 0.1,0.01, 0.001, 0.0001 |
| Hidden Dimensions | 16, 64, 128 |

**Table 5: Optimal hyperparameter values for attributed datasets (MaxEpochs=10,000).**
|  | Cora small | CiteSeer small | Cora | Cora ML | PubMed | CiteSeer | DBLP |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. |  |
| GCN | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 64 | 1 | 0.001 | 64 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 | 0.001 | 128 | 1 |
| SGCN | 0.001 | 64 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 2 | 0.001 | 128 | 1 | 0.001 | 128 | 2 | 0.2 | 128 | 2 |
| UTGCN |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 3 |  |  | 2 |
| SAGE | 0.01 | 128 | 1 | 0.01 | 16 | 1 | 0.01 | 128 | 1 | 0.001 | 128 | 1 | 0.01 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 64 | 1 |
| SSAGE | 0.0001 | 128 | 1 | 0.0001 | 128 | 2 | 0.1 | 64 | 1 | 0.001 | 64 | 1 | 0.001 | 128 | 2 | 0.01 | 128 | 3 | 0.01 | 64 | 2 |
| UTSAGE |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |
| GIN | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 |
| GraphConv | 0.0001 | 64 | 1 | 0.0001 | 128 | 1 | 0.001 | 64 | 1 | 0.0001 | 128 | 1 | 0.0001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 |
| \hdashlineSGIN | 0.001 | 64 | 1 | 0.0001 | 128 | 2 | 0.0001 | 128 | 1 | 0.001 | 64 | 1 | 0.01 | 128 | 1 | 0.0001 | 128 | 1 | 0.001 | 128 | 1 |
| UTGIN |  |  | 1 |  |  | 1 |  |  | 1 |  |  | 1 |  |  | 1 |  |  | 1 |  |  | 1 |

**Table 6: Hyperparameter choices for each model in each of the non-attributed dataset.**
|  | NS | Celegans | PB | Power | Router | USAir | Yeast | E-coli |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. |  |
| GCN | 0.01 | 64 | 3 | 0.001 | 128 | 1 | 0.01 | 128 | 2 | 0.001 | 64 | 3 | 0.2 | 128 | 3 | 0.001 | 128 | 2 | 0.01 | 64 | 3 | 0.1 | 128 | 1 |
| SGCN | 0.1 | 128 | 3 | 0.01 | 128 | 2 | 0.1 | 128 | 2 | 0.001 | 128 | 3 | 0.2 | 64 | 3 | 0.1 | 64 | 2 | 0.01 | 128 | 2 | 0.01 | 16 | 1 |
| UTGCN |  |  | 3 |  |  | 2 |  |  | 2 |  |  | 3 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |
| SAGE | 0.01 | 64 | 2 | 0.01 | 128 | 2 | 0.01 | 128 | 2 | 0.01 | 64 | 3 | 0.2 | 16 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 2 | 0.01 | 128 | 1 |
| SSAGE | 0.01 | 128 | 1 | 0.01 | 16 | 2 | 0.01 | 128 | 1 | 0.001 | 128 | 3 | 0.001 | 64 | 3 | 0.1 | 64 | 2 | 0.001 | 128 | 1 | 0.01 | 128 | 1 |
| UTSAGE |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 3 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 2 |
| GIN | 0.001 | 128 | 3 | 0.001 | 64 | 1 | 0.001 | 128 | 1 | 0.01 | 128 | 3 | 0.1 | 128 | 2 | 0.0001 | 128 | 2 | 0.001 | 128 | 1 | 0.01 | 128 | 1 |
| GraphConv | 0.001 | 128 | 1 | 0.0001 | 128 | 1 | 0.0001 | 64 | 1 | 0.0001 | 128 | 3 | 0.001 | 16 | 1 | 0.01 | 64 | 2 | 0.0001 | 64 | 1 | 0.01 | 64 | 1 |
| \hdashlineSGIN | 0.0001 | 128 | 2 | 0.01 | 128 | 1 | 0.2 | 64 | 1 | 0.0001 | 128 | 2 | 0.0001 | 128 | 1 | 0.1 | 64 | 1 | 0.001 | 128 | 1 | 0.001 | 64 | 1 |
| UTGIN |  |  | 2 |  |  | 1 |  |  | 1 |  |  | 3 |  |  | 2 |  |  | 2 |  |  | 2 |  |  | 1 |

## Appendix C Orthogonality of node features in empirical data sets

The distribution of inner products of initial node features for attributed datasets is given in Figure 2. We find that the inner products of feature vectors of randomly selected node pairs are in general close to zero. Note that, the feature vectors of all datasets are non-negative as they represent word occurrences. As expected, for connected nodes the inner products of feature vectors tend to be higher reflecting the increased feature similarity.

Figure: Figure 2: The distribution of feature dot products for pairs of connected and random node pairs for the attributed datasets.
Refer to caption: x2.png

## Appendix D Runtime Analysis and Training Efficency

#### Efficiency of SMPNNs

While we allocated a very generous limit of 10,000 epochs for training models in the main paper to ensure models can reach their best possible performance in order to compare the computational efficiency of the simplified models to their fully trained counterparts we also consider an experimental setting where we restrict the maximum number of training epochs to 100. We find that simplified models achieved convergence even for larger learning rates and considerably faster than their fully trained models. Even when constrained to 100 training epochs simplified models maintain scores that are almost identical to those presented in Table 8, while fully trained architectures suffer from the increased learning rates and require in general more epochs to converge. This leads to training efficiency gains similar to those reported by Wu et al. [] in the case of node classification.

In Table 8, it is evident that the simplified models consistently outperform the fully trained models across all datasets by a considerable margin. Furthermore, as demonstrated in Table 1, the fully trained models nearly achieve their peak accuracy within just 100 epochs, indicating that extended training offers minimal additional benefit. This also implies that the Simplified models are more efficient in terms of both time and resources required for training.

The hyperpameter space used for the computational efficiency experiments is the same as in Table5, except that we only use 100 epochs.

#### Efficiency of UTMP

In Figure 3, we presented the training times for both simplified and fully trained models.
The prediction times for UT models are excluded, as they require only a single "epoch" for making the predictions, unlike other methods that necessitate prolonged training periods. This characteristic of UT models leads to a substantial reduction in both time consumption and electricity costs.

Despite a minor trade-off in accuracy on attributed graphs, UT models frequently outperform in terms of accuracy on unattributed graphs across numerous datasets.
In practical applications, the efficiency of UTMP models could translate to significant savings in energy consumption and hence environmental footprint which can outweigh marginal improvements in accuracy in settings where either computational resources are limited or reducing energy consumption/cost and environmental impact of models take priority.
This makes UT models particularly appealing for large-scale applications where operational efficiency and cost reduction are critical. Additionally, the societal impact of using UT models includes a lower environmental footprint due to reduced energy consumption, aligning with sustainable and environmentally friendly practices.

**Table 7: Optimal hyperparameter values for attributed datasets for MaxEpochs=100.**
|  | Cora small | CiteSeer small | Cora | Cora ML | PubMed | CiteSeer | DBLP |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. | lr. | hd. | nl. |  |
| GCN | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 | 0.01 | 128 | 1 |
| SGCN | 0.1 | 128 | 1 | 0.1 | 128 | 2 | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 64 | 2 | 0.1 | 128 | 2 |
| SAGE | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 128 | 1 |
| SSAGE | 0.2 | 128 | 2 | 0.1 | 128 | 2 | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 128 | 1 | 0.01 | 64 | 1 | 0.1 | 128 | 2 |
| GIN | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.01 | 64 | 1 | 0.01 | 64 | 1 |
| GraphConv | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.01 | 128 | 1 | 0.001 | 128 | 1 |
| \hdashlineSGIN | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 | 0.001 | 128 | 1 |

**Table 8: Link Prediction accuracy for attributed networks as measured by ROC-AUC. Red values correspond to the overall best model for each dataset, and blue values indicate the best-performing model within the same category of message passing layers. The models are trained only for MaxEpochs = 100.**
| Models | Cora small | CiteSeer small | Cora | Cora ML | PubMed | CiteSeer | DBLP |
| --- | --- | --- | --- | --- | --- | --- | --- |
| GCN | 91.44 ± 1.31 | 91.48 ± 0.67 | 96.45 ± 0.29 | 93.95 ± 0.54 | 96.56 ± 0.22 | 93.48 ± 0.81 | 95.57 ± 0.18 |
| SGCN | 94.58 ± 1.27 | 96.4 ± 0.97 | 97.99 ± 0.06 | 96.75 ± 0.3 | 97.1 ± 0.17 | 95.41 ± 0.76 | 96.95 ± 0.1 |
| SAGE | 90.2 ± 1.67 | 90.34 ± 1.87 | 95.42 ± 0.22 | 92.53 ± 0.69 | 92.68 ± 0.5 | 91.29 ± 1.32 | 94.36 ± 0.32 |
| SSAGE | 93.98 ± 1.08 | 95.77 ± 1.02 | 97.72 ± 0.08 | 95.61 ± 0.38 | 94.52 ± 0.18 | 94.48 ± 0.96 | 96.34 ± 0.12 |
| GIN | 90.39 ± 0.6 | 88.27 ± 0.61 | 95.38 ± 0.29 | 93.75 ± 0.24 | 94.84 ± 0.28 | 90.94 ± 0.72 | 94.71 ± 0.26 |
| GraphConv | 91.57 ± 1.33 | 90.79 ± 0.91 | 96.68 ± 0.16 | 94.56 ± 0.48 | 95.17 ± 0.3 | 92.04 ± 0.96 | 94.94 ± 0.11 |
| SGIN | 92.72 ± 1.23 | 93.11 ± 0.25 | 97.29 ± 0.08 | 95.43 ± 0.27 | 95.95 ± 0.21 | 93.18 ± 0.56 | 95.84 ± 0.15 |

Figure 3 illustrates that the simplified models, when trained for extended periods, generally achieve higher accuracy and converge faster to their optimal values compared to fully trained models.
Notably, when trained for a shorter duration (100 epochs), the simplified models not only outperform the fully trained counterparts by a larger margin but also require considerably fewer epochs to reach relatively high accuracies. Additionally, the accuracy gap between shorter and longer training durations is smaller for simplified models than for fully trained models.

Figure: Figure 3: Average runtimes (in seconds) for training and inference for attributed data sets.
Refer to caption: x3.png

## Appendix E Comparison to state-of-the-art

In Table 9 we compare UTMP architectures to three state-of-the-art link prediction methods, namely SEAL Zhang and Chen [], WalkPool Pan et al. [] and NBFNet Zhu et al. [] on attributed datasets. Compared to SEAL SGCN achieves higher scores on all 3 datasets. While NBFNet outperforms SGCN on Cora and PubMed by a small margin SGCN achieves a significantly higher score on CiteSeer. For WalkPoll the results on Cora and Citeseer are within one standard deviation of each other while WalkPool does better on PubMed.

For the unattributed datasets (see Table 10) we find that UTGCN has the highest overall score for E-coli while being within a standard deviation of the other methods on Celegans with WalkPool performing best on the remaining datasets. Note that WalkPool can be set up with different base methods as can be seen in Table 9 and hence using SGCN or UTGCN as a base method for WalkPool could potentially lead to performance improvements, which however is beyond the scope of this paper. It should also be noted that SGCN is considerably more efficient than all three methods, which rely either on subgraph extraction (SEAL and WalkPool) or learning explicit path representations (NBFNet).

**Table 9: Link Prediction accuracy for attributed networks as measured by ROC-AUC compared to state-of-the-art models SEAL and NBFNet. ROC-AUC values for NBFNet and SEAL are from Zhu et al. [] (no standard deviations reported) and results for WalkPool from Pan et al. [].**
| Models | Cora (small) | CiteSeer (small) | PubMed |
| --- | --- | --- | --- |
| SEAL | 93.3 | 90.5 | 97.8 |
| NBFNet | 95.6 | 92.3 | 98.3 |
| WalkPool (VGAE) | 94.64 ± 0.55 | 94.32 ± 0.90 | 98.49 ± 0.13 |
| WalkPool (ARGVA) | 94.71 ± 0.85 | 94.53 ± 1.77 | 98.52 ± 0.14 |
| WalkPool (GIC) | 95.90 ± 0.50 | 95.94 ± 0.59 | 98.72 ± 0.10 |
| GCN | 92.82 ± 0.83 | 91.67 ± 1.14 | 97.54 ± 0.09 |
| SGCN | 95.3 ± 0.68 | 96.22 ± 0.4 | 97.94 ± 0.16 |
| UTGCN | 93.82 ± 0.68 | 96.0 ± 0.24 | 94.29 ± 0.24 |

**Table 10: Link Prediction accuracy for non-attributed networks as measured by ROC-AUC compared to state-of-the-art models SEAL and WalkPool. ROC-AUC values SEAL are taken from Zhang and Chen [] and for WalkPool from Pan et al. [].**
| Models | NS | Celegans | PB | Power | Router | USAir | Yeast | E-coli |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| SEAL | 97.71±0.93 | 89.54±2.04 | 95.01±0.34 | 84.18±1.82 | 95.68±1.22 | 97.09±0.70 | 97.20±0.64 | 97.22±0.28 |
| WalkPool | 98.95±0.41 | 92.79±1.09 | 95.60±0.37 | 92.56±0.60 | 97.27±0.28 | 98.68±0.48 | 98.37±0.25 | 98.58±0.19 |
| GCN | 95.22 ± 1.8 | 87.98 ± 1.45 | 92.91 ± 0.3 | 74.68 ± 2.67 | 91.42 ± 0.44 | 93.56 ± 1.53 | 94.49 ± 0.61 | 98.48 ± 0.22 |
| SGCN | 95.17 ± 0.96 | 89.38 ± 1.42 | 93.86 ± 0.42 | 81.08 ± 1.2 | 77.51 ± 1.85 | 94.08 ± 1.43 | 95.74 ± 0.33 | 98.32 ± 0.2 |
| UTGCN | 94.76 ± 1.03 | 91.47 ± 1.4 | 94.49 ± 0.38 | 72.97 ± 1.27 | 61.68 ± 1.01 | 94.81 ± 1.1 | 94.0 ± 0.43 | 99.37 ± 0.1 |
| SAGE | 95.9 ± 0.86 | 87.32 ± 1.61 | 92.94 ± 0.57 | 74.17 ± 2.03 | 62.6 ± 3.3 | 93.37 ± 1.2 | 94.43 ± 0.67 | 98.22 ± 0.13 |
| SSAGE | 95.21 ± 1.09 | 88.05 ± 1.8 | 91.66 ± 0.43 | 81.84 ± 1.49 | 70.1 ± 1.3 | 92.25 ± 1.45 | 95.72 ± 0.31 | 93.59 ± 0.14 |
| UTSAGE | 94.72 ± 1.07 | 84.48 ± 1.87 | 86.46 ± 0.64 | 72.96 ± 1.26 | 61.47 ± 0.99 | 87.94 ± 1.58 | 93.45 ± 0.45 | 85.56 ± 0.37 |
| GIN | 95.24 ± 1.22 | 86.74 ± 2.3 | 93.04 ± 0.99 | 71.97 ± 2.3 | 87.84 ± 3.05 | 92.14 ± 0.98 | 94.7 ± 0.45 | 98.43 ± 0.24 |
| GraphConv | 95.73 ± 1.4 | 86.64 ± 2.31 | 92.99 ± 0.87 | 74.31 ± 1.93 | 80.84 ± 1.28 | 91.16 ± 1.76 | 94.94 ± 0.38 | 98.32 ± 0.22 |
| \hdashlineSGIN | 95.48 ± 0.88 | 88.31 ± 1.3 | 93.72 ± 0.48 | 73.73 ± 1.69 | 72.83 ± 1.28 | 93.02 ± 1.37 | 95.63 ± 0.49 | 97.68 ± 0.2 |
| UTGIN | 94.62 ± 1.05 | 86.48 ± 1.29 | 92.77 ± 0.51 | 72.93 ± 1.27 | 61.67 ± 1.02 | 93.44 ± 0.84 | 92.94 ± 0.41 | 95.81 ± 0.22 |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: NA
soundness: 2
strengths: Using untrained message passing layers for GNN can be a computationally efficient approach, which is an important topic in the community.
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.
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?

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: Can you comment on why orthogonality would be expected in homophilic networks?
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
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.
soundness: 2
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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: See weakness.
soundness: 3
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.
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.
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?

Meta-review: 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.

Decision: Reject