Line Graph Neural Networks for Link Weight Prediction
Link weight prediction is of great practical importance, since real-world
networks are often weighted networks. Previous studies have mainly used shallow
graph features for link weight prediction, which limits the prediction
performance. In this paper, we propose a new link weight prediction algorithm,
namely Line Graph Neural Networks for Link Weight Prediction (LGLWP), which
learns deeper graph features through deep learning. In our algorithm, we first
extract the enclosing subgraph around a target link, and then employ a weighted
graph labeling algorithm to label the subgraph nodes. Next, we transform the
subgraph into a line graph and apply the graph convolution neural networks to
learn the node embedding in the line graph, which can represent the links in
the original subgraph. Finally, the link feature vectors are put into a
fully-connected neural network to predict the weight of the target link. Our
algorithm directly obtain the feature vectors of the target links in the
original graph, which is better than the previous methods that splice the node
feature vectors for link weight prediction. Experiments results on six real
datasets of various network sizes and types show that our algorithm has better
prediction performance than the state-of-art methods, while it has fewer
parameters and high training efficiency.
Jinbi Liang, Cunlai Pu
# Line Graph Neural Networks for Link Weight Prediction

###### Abstract.

Link weight prediction is of great practical importance, since real-world networks are often weighted networks. Previous studies have mainly used shallow graph features for link weight prediction, which limits the prediction performance. In this paper, we propose a new link weight prediction algorithm, namely Line Graph Neural Networks for Link Weight Prediction (LGLWP), which learns deeper graph features through deep learning. In our algorithm, we first extract the enclosing subgraph around a target link, and then employ a weighted graph labeling algorithm to label the subgraph nodes. Next, we transform the subgraph into a line graph and apply the graph convolution neural networks to learn the node embedding in the line graph, which can represent the links in the original subgraph. Finally, the link feature vectors are put into a fully-connected neural network to predict the weight of the target link. Our algorithm directly obtain the feature vectors of the target links in the original graph, which is better than the previous methods that splice the node feature vectors for link weight prediction. Experiments results on six real datasets of various network sizes and types show that our algorithm has better prediction performance than the state-of-art methods, while it has fewer parameters and high training efficiency.

Link weight prediction, line graph, graph neural network, graph mining +
Footnote †: journal: Computer graphics & Machine learning

+
Footnote †: journal: Computer graphics & Machine learning
Link weight prediction represents a burgeoning field of research in network science, aiming to forecast the strength of connections between nodes in a network. Unlike traditional graph classification tasks such as node classification or link prediction, link weight prediction poses a more intricate regression task that has received comparably less attention and exploration. Previous studies have attempted to address this problem through simplified approaches, primarily utilizing shallow topological features of the network to estimate connection weights (Wang et al., 2018; Wang et al., 2019; Wang et al., 2020; Wang et al., 2020). For instance, methods like WCN, WAA, and WRA (Wang et al., 2019) rely solely on basic statistical characteristics of the local graph structure to infer connection weights.However, it has been empirically and practically observed that connection weights often embody intricate interdependencies, exemplified by the strength of interactions between neurons in brain networks. These complex relationships elude facile capture by shallow feature-based methodologies (Wang et al., 2019). As a result, the challenge of link weight prediction resides in the necessity to devise advanced techniques and methodologies capable of accurately capturing and predicting the multifaceted strengths of connections between nodes. Accomplishing this goal necessitates thorough research and exploration to tackle the inherent challenges presented by this regression task.

Inspired by LGLP (Liang et al., 2019), we propose line graph neural network for link weight model LGLWP.We first extract the enclosing subgraphs of the target links for node labeling.Since the node labeling algorithm in LGLP is for unweighted graphs, here we introduce the node labeling algorithm for weighted graphs in (Wang et al., 2019), and then we transform the subgraphs into corresponding line graphs, and then through the graphs Convolutional Neural Network GCN to learn the node features and get the feature vector corresponding to the target link, and finally regression prediction by two fully connected layers.The framework is depicted in Figure 1. In fact by transforming the original graph into a line graph, the feature vectors of the original two destination nodes are transformed into the feature vectors of the corresponding points in the line graph, and this feature vectors are fed into the neural network for regression prediction. On the one hand, the neural network can require fewer parameters, and on the other hand, it can accelerate the training speed of the model.

The contributions of our research can be summarized as follows:

1. Based on LGLP, unlike LGLP for link existence prediction, we propose link weight regression prediction with line graphs. Thus, we open up a new idea for link weight prediction.
2. Since the subgraph node labeling algorithms in LGLP are mainly for undirected unweighted graphs, these works focus on simple link prediction, i.e., they are not suitable for weight prediction. Their node labeling algorithms are not able to handle weighted graph nodes and hence are not applicable to the tasks of this work. Here we introduce algorithms suitable for weighted graph node labeling.
3. On six real datasets, six datasets involving different network sizes and containing both large and small graphs, we have achieved good results. We also conducted ablation experiments to demonstrate the effectiveness of this weighted graph node labeling algorithm for link weight prediction by comparing the random labeling of subgraph nodes with the weighted graph node labeling algorithm.

## 2. Related Work

Link weight prediction is a relatively new research area within network science. Lv et al. (Lv et al., 2019) pioneered this field by exploring the role of weak connectivity in weighted networks. They introduced weighted local similarity metrics, which included Weighted Common Neighbors (WCN) metrics, Weighted Adamic-Adar (WAA) metrics, and Weighted Resource Allocation (WRA) metrics to estimate link weights. Zhao et al. (Zhao et al., 2019) extended unweighted local similarity metrics to weighted local similarity metrics through a method called the "Reliable Routing Method."These weighted local similarity metrics are invaluable for predicting the presence of links and their respective weights. (Li et al., 2019)In this approach, a link weight matrix is generated by perturbing the observed weighted network structure. Subsequently, the link weight matrix is reconstructed by utilizing the factorized latent factors derived from the observed network. Finally, these two matrices are combined to yield predictions for missing link weights.In another approach, (Li et al., 2019) expanded the eigenvector space of connected edges by incorporating node similarity metrics from the original network and node centrality metrics from the line graph to perform link weight regression prediction.Additionally, (Li et al., 2019) introduced a novel computational framework called Neighborhood Estimation Weights NEW. This method relies solely on the fundamental structural information of the network and offers flexibility to adapt to various types of networks. However, it's important to note that these methods often remain at the level of basic structural network information and may have limitations when dealing with more complex network features.

Thus graph representation learning was proposed, where the goal of graph representation learning is to encode nodes into low-dimensional vectors that contain the nodes' positions in the graph as well as their local graph structure. In other words, graph representation learning is the projection of nodes into a potential Euclidean space, where the geometric relations in this potential space correspond to the relations in the original graph or network. The obtained embedding vectors can be used for downstream tasks such as node embedding and link prediction. The main technical tools are Graph Embedding (GE) and Graph Neural Networks (GNNs) (Goh et al., 2019; Li et al., 2019). The graph embedding models are deepwalk (Wang et al., 2019), node2vec (Wang et al., 2019), SDNE (Wang et al., 2019), etc., and the graph deep learning models are GCN (Goh et al., 2019),GAE (Goh et al., 2019), VGAE (Goh et al., 2019), etc., but the link weight prediction task has never been addressed. Therefore, it would be interesting to investigate how well these deep graph learning models perform on this task (Wang et al., 2019).

In addition, there is recent literature demonstrating promising results using enclosing subgraph extraction. There are methods for link prediction through enclosing subgraph extraction in recent years, representative of which are WLNM (Wang et al., 2019), SEAL (Wang et al., 2019) and LGLP (Liang et al., 2019). They have achieved very good results in this task. Thus, the correct representation of the target links has been shown to be sufficient to predict the links and their weights, avoiding the need to process the whole graph. However, node labeling techniques must be provided to use enclosing subgraph extraction methods. By
consistently labeling nodes to learn predictions, further models can be generalized to different subgraphs. In addition, node labeling techniques must preserve topological directionality towards the target link for optimal performance, thus providing a mechanism for the model to focus on specific nodes (Wang et al., 2017).Weisfeiler-Lehman (2017), proposed an algorithm based on the original WL algorithm for labeling unweighted graphs. The SEAL framework (Kumar et al., 2017) also proposes a novel node labeling method based on the radius of each node to the target linkLGLP (Beng et al., 2017) applies a line graph based on SEAL while also retaining the node labeling algorithm of the SEAL model. These works focus on simple link prediction, i.e., they are not suitable for weights. Their node labeling algorithms are unable to handle weighted nodes and hence are not suitable for tasks related to weighted graph node labeling (Wang et al., 2017). Therefore, in this paper, we introduce a node labeling technique suitable for weighted graphs based on the LGLP (Beng et al., 2017) model, while retaining the enclosing subgraph extraction method, and finally perform link weight prediction with good results on several datasets.

## 3. Proposed Method

In this section, we will begin by providing an overview of the problem of link weight prediction. Subsequently, we will introduce our novel link weight prediction method, LGLWP, which encompasses the following key steps:

1. Enclosing subgraph extraction
2. Subgraph node ordering
3. Feature learning and link weight prediction via line graph neural networks

A summary figure of the whole approach is shown in Figure 1.

### Problem description

Let \(G(V,E,W)\) represent an undirected weighted network, where V denotes the network's nodes and E denotes its edges. The weight matrix, denoted as W, describes the network's adjacency, where the weight value \(w\) of a link \((i,j)\in E\) is assigned as \(W_{i,j}=w\), and \(W_{i,j}=0\) otherwise. The set of weights, W, can be divided randomly into two subsets: \(W_{train}\) and \(W_{test}\), where \(W_{train}\cup W_{test}=W\), and \(W_{train}\cap W_{test}=\emptyset\). The objective of network link weight prediction is to predict the weights of the test set \(W_{test}\) with maximum accuracy, using the graph \(G(V,E,W_{train})\)(Beng et al., 2017).To avoid the effect of different weight ranges on the results, we first preprocess the weights. Here we employ we use the exponential transformation method to normalize all the contiguous edge weights \(w\) to the interval \((0,1)\), i.e.:

\[w^{*}=e^{-\frac{1}{w}} \tag{1}\]

### Enclosing subgraph extraction

The first step of the method is to extract the enclosing subgraph of the target connection.

The link weights between two nodes can be predicted based on the subgraph of the target link. In general, the larger the subgraph, the more information can be learned. However, this will bring more computational cost. In order to find a balance between performance and computational cost, we only extract 1-hop subgraphs, and one-hop subgraphs are defined as follows:

\[G^{1}(i,j)=\{w\mid\min(d(v,i),d(v,j))\leq 1\}, \tag{2}\]

Where \(d(v,i)\) and \(d(v,j)\) denote the shortest path between \(v\) and i, and \(v\) and j, respectively, i.e., the path that connects two nodes with the least number of edges on the path.

Figure 1. Summary of the steps for the LGLWP link weight prediction framework.
Since the number of nodes contained in different enclosing subgraphs is inconsistent, considering the time complexity and performance, we select 10 nodes in the first-order enclosing subgraphs of all the target links, and randomly select 10 nodes in the enclosing subgraphs with the number of nodes greater than 10 nodes, and leave them unprocessed if they are less than 10 nodes. This avoids the variability in the number of nodes in different graphs. With the same subgraph extraction strategy, we can obtain similar contextual representations of target node pairs and the model can be generalized across different graphs, nodes, and links.

### Subgraph node ordering

The second step of the approach is to order the extracted enclosing subgraph.

The purpose of the ordering is to provide a consistent way of labeling nodes such that those nodes with similar topological characteristics to the subgraphs are similarly labeled, e.g. if the relative positions and structural roles of the vertices in their respective subgraphs are similar, then they receive a similar ordering.

Now, let's provide a brief introduction to the Weisfeiler-Lehman (WL) algorithm (Zhou et al., 2017). The WL algorithm addresses the graph isomorphism problem, which involves determining whether two graphs share the same number of nodes connected in the same manner. WL operates through iterative updates of node labels, utilizing the labels of neighboring nodes and compacting them into new labels until convergence.Initially, all nodes are assigned the same color, typically denoted as 1. For each node, a signature string is generated by concatenating its color with the sorted colors of its neighboring nodes. Subsequently, nodes are sorted based on their signature strings in ascending order, and new colors are assigned. Nodes with identical signature strings are assigned the same color.A crucial aspect of the WL algorithm is its ability to encode the structural roles of vertices within the graph. Moreover, it defines a relative order for these vertices, considering their structural roles; vertices with similar roles receive similar labels. Importantly, the relative ordering of vertices remains consistent across different graphs.

Literature (Zhou et al., 2017) proposed a new node labeling ranking method suitable for unweighted graphs based on Weisfeiler-Lehman ( WL ) algorithm. Literature (Zhou et al., 2017) introduces another node labeling sorting algorithm based on weighted graph based on literature (Zhou et al., 2017), which has the following requirements for graph labeling algorithm:

1. The graph labeling algorithm must provide similar labels for nodes with similar topological characteristics in a enclosing subgraph.
2. It must maintain topological directionality to the target link, i.e., the order of the nodes must be constrained by the target node and the distance to the target node must be reflected in the ordering.

Since the WL algorithm does not satisfy the second requirement and the node ordering is crucial for model learning, we adopt here the graph labeling approach proposed in (Zhou et al., 2017) by applying the one-dimensional Weisfeiler - Lehman ( WL ) algorithm to a weighted graph. The goal of this algorithm is to rank the set of nodes from the extracted subgraphs. However, since we want to maintain topological directionality with respect to the target edges, the target edges will always be assigned the order 1 and 2. First, initial labels are assigned to the nodes based on the sum of the shortest paths (shortest paths are computed by computing the weights of the edges) from the nodes to the target nodes, \(o_{x}\) and \(o_{y}\). Next, we use the Weisfeiler-Lehman algorithm to assign a label string to each node. This process consists of arranging the initial labels of each node with the initial labels of its neighboring nodes in order from smallest to largest, and in this way, we generate a unique label string. Then, the lowest dictionary-ordered string signature corresponds to the next node in the ordered list. Next, we iterate this process until each node is assigned a number. The process is defined in Algorithm 1.The schematic of the process is shown in Figure 2.

```
Input:\(h\)-hop enclosing subgraph \(G^{h}_{(o_{1},o_{2})}\) centered on two target nodes \(o_{1}\) and \(o_{2}\), which is extracted by Equation (2) Output: ordered set of nodes from \(o\in G^{h}_{(o_{1},o_{2})}\)\(o_{1}=\)x \(o_{2}=\)y  calculate \(d(o):=d(o,x)+d(o,y)\) for all \(o\in G^{h}_{(o_{1},o_{2})}\) get initial labels \(l(o)=f(d(o))\)\(l(o_{1})=0\)\(l(o_{2})=0\)while\(|orderList|<|V|\)do  generate label string \(Agg(l(o))\) for all \(o\in G^{h}_{(o_{1},o_{2})}\) sorted \(Agg(l(o))\) add lowest \((Agg(l(o)))\) to orderList endwhile returnorderList
```

**Algorithm 1** Subgraph node ordering algorithm

Once the node sorting process is complete and the ordered set is obtained, we extract the adjacency matrix of the subgraph with rows and columns of the matrix corresponding to the ordered set. Each row vector of this adjacency matrix is then used as a feature vector for each node. Before feeding into the line graph network model for prediction, we ensure that the values \(W_{1,2}\) and \(W_{2,1}\) in the matrix representing the link weights are not visible to the model and are set to -1 here, respectively (Zhou et al., 2017).

### Line graph transformation

To predict the weights of links from a given enclosing subgraph \(G^{h}_{(o_{1},o_{2})}\), where \(G^{h}_{(o_{1},o_{2})}\) is an \(h\)-hop enclosing subgraph centered on two target nodes v1 and v2, each node in the enclosing subgraph corresponds to an ordered feature vector, and nodes with similar topological features to the subgraph are similarly labeled. Since the edges corresponding to pairs of nodes in the original graph correspond to vertices in the line graph. Therefore directly processing the nodes in the line graph is processing the edges in the original graph. This will not only not increase the time complexity, but will also require fewer model parameters. Therefore we propose to convert the enclosing subgraph into a line graph, which represents the adjacencies between the edges of the original graph (Beng et al., 2019). Moreover, the features of the links to be predicted can be learned directly from
the line graph representation using graph convolutional neural networks for weight prediction.

In graph theory, the graph G corresponding to a line graph is a graph that reflects the adjacency of the edges in the graph, denoted as \(L(G)\). Briefly, \(L(G)\) abstracts each edge in G into a vertex each; if two edges in the original graph are adjacent, then an edge is connected to the corresponding vertex in the line graph. Because a line graph reduces the edges of the original graph to vertices, it can also be thought of as a dual of the original graph. An example of the line graph transformation process is given in Figure 3.

In order to transform the attributes of the node pairs in the original graph into the attributes of the nodes in the line graph, (Bang et al., 2017) proposed a function:

\[l_{(v_{1},v_{2})}=\text{concate}(\min(f_{l}(v_{1}),f_{l}(v_{2})),\max(f_{l}(v_ {1}),f_{l}(v_{2}))), \tag{3}\]

where: \(f_{l}(\cdot)\) is the node labeling function, \(v_{1}\) and \(v_{2}\) are the two endpoints of the edge, and concate \(\text{concate}(\cdot)\) denotes the cascade operation on the two inputs. Since only the link weight prediction of the undirected weighted graph is considered in this paper, the attributes \((v1,v2)\) and \((v2,v1)\) of the introduced edges should be the same. The above formulation ensures that the generated edge attributes (i.e., node attributes in the line graph) are consistent when switching the end nodes. In addition, the structural importance information of the nodes can be well preserved in the function (Bang et al., 2017).

Since the nodes in the original graph are represented by the row vectors of the ordered adjacency matrix, here we take the node pairs in the original graph and splice the row vectors of the two nodes according to the above transformation method as the feature vectors of the nodes in the line graph.

### Feature Learning by Graph Neural Networks

Deep learning methods have been successfully applied in many fields such as image processing, speech recognition, etc., but the data in these fields are in Euclidean space. However, the data present in real world networks are in non-Euclidean space, so traditional deep learning methods do not work well to extract features from graphs.Kipf et al. (Kipf et al., 2017) proposed a multilayer graph convolutional neural network that can be used directly on graph data, which aggregates the node information of its neighbors and generates new node embeddings that contain rich neighborhood information.

In this work, we use a graph convolutional neural network to learn node embeddings in a line graph, where a node in the line graph can represent an edge in the original graph. The graph convolutional neural network can aggregate the information of neighboring nodes to generate a new node embedding that contains rich neighbor information. Therefore, the node embeddings in the line graph can be used to predict the target edge connection weights in the network.

Given a line graph representation of the enclosing subgraph \(L\left(G_{01,02}^{h}\right)\), the node embedding of \((v_{i},v_{j})\) in the kth layer of the graph convolutional neural network is denoted as \(Z_{(v_{i},v_{j})}^{(k)}\). The node embedding of \((v_{i},v_{j})\) in the \((k+1)\)th layer is:

\[Z_{(v_{i},v_{j})}^{(k+1)}=\sigma(\widetilde{D}^{-\frac{1}{2}}\widetilde{A} \widetilde{D}^{-\frac{1}{2}}Z_{(v_{i},v_{j})}^{(k)})W^{(k)}), \tag{4}\]

Where \(\widetilde{A}=A+I_{N}\) is the adjacency matrix of the line graph \(L\left(G_{01,02}^{h}\right)\) of the enclosing subgraphs where each node in the graph

Figure 3. Line graph transformation procedure.

Figure 2. Subgraph node ordering algorithm. We want to predict the weight (w, coloured in red) of the link for the target nodes (dashed and coloured in yellow).
is connected to itself, \(\widetilde{D}_{ii}=\sum_{j}\widetilde{A}_{ij}\) is the degree of the line graph \(L\left(G_{o1,02}^{h}\right)\) of the enclosing subgraphs where each node in the graph is connected to itself, and \(W(k)\) is the trainable weight matrix of the kth layer. \(\sigma(\cdot)\) is the activation function in each layer. The input for the first layer of graph convolution neural network is set to node attribute in the line graph as \(Z_{(u_{i},u_{j})}^{0}=l_{(o1,02)}\)(Gendran et al., 2017).We then treat the link weight prediction task as a regression problem and train the neural network by minimizing the root-mean-square error loss for all all link weights to be predicted.

## 4. Experiments

### Datasets description

We test the effect of our proposed algorithm in the following in six weighted networks, respectively. The six datasets cover different network sizes and network types. The specific topological characteristics are shown in Table 1.

* Neural network (Kang et al., 2017): The neural network of C. elegans exhibits connections between neurons, which can occur through synapses or gap junctions. The weights assigned to the edges in this network signify the quantity of interactions that transpire between the neurons.
* C. elegans (Kang et al., 2017): The network describing the interactions between metabolites in the roundworm Caenorhabditis elegans is an undirected graph. In this graph, the links represent the connections between pairwise metabolites. The weights assigned to the edges reflect the occurrence of multiple interactions between these metabolites.
* Coauthorships in network science (Kang et al., 2017): The largest component of a co-authorship network collected by M. Newman consists of scientists collaborating on studies in the field of network science. M. Newman calculated the weights of edges in this network based on information from co-authored papers and co-authors.
* Political blogs (Newman, 2017): Adamic and Glance collected a network that depicts the directed hyperlinks between political web blogs during the 2004 US Election. In this study, we simplified the directed links as undirected ones and assigned weights to represent the volume of multiple hyperlinks between blogs.
* UC-social (Newman, 2017): The network consists of sent messages exchanged between users within an online student community at the University of California, Irvine. Users are represented as nodes, while directed edges indicate the flow of sent messages. The weight assigned to each edge reflects the occurrence of multiple messages. In this analysis, the network was treated as undirected but with weighted edges.
* Condmat (Candand, 2017): This network represents collaborations among scientists who have posted preprints on the condensed matter archive at www.arxiv.org between 1995 and 1999. The compilation of this network was conducted by M. Newman. The weights assigned to the network follow the methodology outlined in the original paper.

### Evaluation metrics

When performing link weight prediction, many literatures propose to use Pearson's correlation coefficient and root-mean-square error as evaluation metrics, however, according to the idea proposed in (Newman, 2017), they have practically equal evaluative power, and in order to save the paper's length, we choose only RMSE to measure the model's prediction performance.

The definition of RMSE is:

\[RMSE=\sqrt{\frac{\sum_{i=1}^{n}(y_{i}-\hat{y}_{i})^{2}}{n}} \tag{5}\]

where y is the predicted value and \(\hat{y}\) is the actual value. Obviously, the smaller the RMSE is, the smaller the difference between predicted and actual values is, and the more accurate the algorithm is in its prediction. The smaller the RMSE is, the more accurate the algorithm's prediction is.

### Parameter settings

The model parameters used in this paper are similar to the original paper (Gendran et al., 2017). Three graph convolution layers are used to compute the node embeddings, and the output feature dimensions of the three graph convolution layers are set to 32. Finally, the link weight regression prediction is performed through two more fully connected layers. The number of training iterations is set differently depending on the specific dataset. Specifically, 5 training epochs are used on some graphs with larger network sizes, such as Condmat, P.blog, and UC-social, and 15 training epochs are used on the rest of the datasets.

### Baselines

In order to evaluate the predictive ability of the LGLWP model, we selected the same baseline models as in (Newman, 2017). These include seven well-known graph representation models such as Deepwalk (Wang et al., 2018), Node2vec (Chen et al., 2018), Grarep (Chen et al., 2018), SDNE (Kang et al., 2017), LINE (Kang et al., 2017), GAE (Gendran et al., 2017), VGAE (Gendran et al., 2017), etc. proposed in recent years. Since the above seven graph learning models cannot be directly applied to link weight prediction, the obtained node embedding vectors are concatenated as edge feature vectors to further train the linear regression model and evaluate its performance for link weight prediction (Newman, 2017). In addition to the mentioned baseline model, we also compared the GCN (Gendran et al., 2017) model. Since GCN model also performs very well in graph representation, it is often used for node classification, graph classification and other related tasks. GCN learns node embeddings by graph convolution. For this purpose, they use message passing framework in which node embeddings are updated by aggregating the embeddings of their neighbors. Our proposed model performs graph convolution on the line graph, whereas GCN performs graph convolution in the full graph. With the embedding vectors obtained

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Dataset & \(|V|\) & \(E\) & Range of weights & categories \\ \hline Neural & 296 & 2137 & \([1,72]\) & biology \\ C.elegans & 453 & 2025 & \([1,114]\) & biology \\ Netscience & 575 & 1,028 & [0.0526, 2.5] &authorship \\ P.blog & 1224 & 16,715 & \([1,3]\) & social \\ UC-social & 1899 & 13,838 & \([1,184]\) & social \\ Condmat & 16264 & 47,594 & \([0.058824,22.3333]\) & coauthorship \\ \hline \hline \end{tabular}
\end{table}
Table 1. Basic topological features of weighted networks
by GCN, we follow the method proposed by (Kumar et al., 2017) and use the inner product of the node vectors to measure the weights between nodes. In addition, seven shallow feature-based link weight prediction methods are selected for comparison, including three reliable routing-based methods (Wang et al., 2018), three line graph-based methods (Wang et al., 2018), and NEW methods (Kumar et al., 2018). SEA (Kumar et al., 2018), a self-attention-enhanced graph self-encoder SEA, which improves weight prediction by learning deep graph features, is a very novel model that achieves state-of-the-art performance in link weight prediction, and is presented in the paper we also compare it. Here all the parameters of the baseline are set according to the original literature.

### Results and Analysis

In this paper, we follow the setup of (Wang et al., 2018; Kumar et al., 2018), where we choose 90% of the link weights in the original network as the training set and 10% of the link weights as the test set. Also, to avoid errors from a single experiment, each model is run on 10 independent sets of training and test sets, and their means and standard deviations are calculated. All data were preprocessed according to the methodology proposed in the (Kumar et al., 2018), e.g., all weights were normalized to intervals (0,1) using the exponential transformation method. The machine used for the experiments is a laptop computer configured with i9-12900H 2.50 GHz processor, 16G RAM and Nvidia 3070 GPU.

Since GAE and VGAE are designed for attriubte networks. In order to make GAE and VGAE work on ordinary weighted graphs, the i-th column vector of the weighted adjacency matrix is used as the initial eigenvector of node i. The GAE\({}^{*}\) and VGAE\({}^{*}\) methods are modified versions of the original implementations. Especially when it comes to line-graph-based techniques such as LG-RF, LG-GBDT, and LG-SVM, the computation of centrality-based metrics can be quite resource-intensive. Consequently, these methods encountered difficulties in producing conclusive results for large graphs, including Condmat.

As can be seen from Table 2, comparing seven link weight prediction models based on shallow graph features and eight graph representation models, our model achieves the best results. the SEA model has comparable performance with ours. SEA model is based on graph attention mechanism using graph self-encoder for link weight prediction, which opens the way to weight prediction based on attention mechanism, and the result also proves that the attention mechanism in weight prediction has a lot of room for development. However, SEA models are limited by the size of the graph, and their computation needs to consider the global information of the whole graph, which often requires more computational resources. On some large graphs, SEA proposes an effective graph compression algorithm, which first compresses the graph to a smaller size and then performs link weight prediction, and the algorithm also achieves good results. Contrary to graph compression, we only extract the neighbor information around the target links, and an effective node labeling algorithm can achieve the model to generalize between different subgraphs, thus avoiding processing the whole graph. In addition, our node labeling technique maintains the topological directionality of the target links for optimal performance, providing a mechanism for the model to focus on specific nodes. Our proposed method can learn the features of target links directly in the line graph. To analyze the convergence speed of the two models, we run the models on different datasets and collect the loss of each epoch. The results are shown in Figure 4. The losses in this paper's method are marked with green lines, and the losses in the SEA model are marked with blue lines. As can be seen from the results, our proposed model is able to converge faster than SEA. For our proposed method, we only need about 15 epochs to achieve the best performance on Neural, C.elegans, and Netscience datasets, and about 5 epochs on P.blog, UC-social, and Condmat datasets. while SEA has not converged after 50 epochs. According to (Kumar et al., 2018), specifically, SEA needs to be trained for 100 epochs on the Condmat dataset for optimal performance and 800 epochs on the P. blog dataset requires 800 epochs of training, 500 epochs in the UC - social dataset, and 300 epochs in the rest of the datasets.Thus, our proposed method saves training time and requires fewer model parameters.

As can be seen from the Table 2, our model LGLWP outperforms SEA on the Neural and Netscience datasets.To test the robustness of LGLWP, we dynamically take 30, 40, 50, 60, 70, and 80 percent of all the links and weights in G as the training set and the rest as the test set, respectively. Our purpose is to determine whether the model consistently outperforms SEA with different proportions of weights missing.The results are shown in Figure 5. The experimental results show that the RMSE of LGLWP is lower than that of SEA for different proportions of the training set, indicating that LGLWP is robust.

### Ablation study

We conducted ablation experiments with the aim of understanding the extent to which the graph labeling algorithm affects the models The introduction of a weighted graph labeling algorithm in LGLWP is one of the main contributions of this paper. It provides consistency to the model by labeling roles with similar structural roles and similar labels. We compare this algorithm with random labeling of nodes.

We conducted experiments on all six data with the same experimental setup. The experimental results are shown in the Table 3. The results clearly demonstrate the effectiveness of the weighted graph labeling algorithm, as it indeed achieves significantly better performance than the subgraph random labeling algorithm. Due to the search for a balance between performance and computational cost, we only extract 1-hop subgraphs while controlling the number of subgraph nodes to be around 10. It is believed that this gap will become more obvious with the expansion of subgraph size. The use of enclosing subgraph extraction is a promising approach for link prediction and link weight prediction. A proper representation for the target links has been shown to be sufficient to predict the links and their weights, thus avoiding the entire processing graph. However, a node labeling technique must be provided to pair with the enclosing subgraph extraction method. By consistently labeling nodes algorithmically, the model can generalize the conversation over different subgraphs and thus make predictions. In addition, the node labeling technique must remain topologically oriented to the target links for optimal performance, thus providing a mechanism for the model to focus on specific nodes (Wang et al., 2018).
Figure 4. Training loss comparison between our proposed LGLWP and SEA method. The training loss on Neural, C.elegans, Netscience, P.blog, UC-social and Condmat dataset.

Figure 5. RMSE comparison on Neural, Netscience for SEA, LGLP using different percent of training set. On each dataset, we take 30, 40, 50, 60, 70, and 80 percent of all the links and weights in G as the training set.
### Discussion

Since the P.blog, UC-social and Condmat networks are larger and therefore contain more samples, we trained only 5 epochs and the other datasets 15 epochs.The main problem when using graph-based methods for prediction is how to make them independent of the size of the graph. The subgraph extraction method solves this problem by making LWLWP independent of the number of nodes in the graph, i.e., to predict the link weights, we only need a small portion of the graph. However, being unaffected by the number of nodes in the graph comes at the cost of computational complexity and time complexity of the weighted graph labeling algorithm. Nevertheless, the time required to compute the weighted graph labeling algorithm for a given subgraph will always remain the same, while the model for processing the entire graph will scale linearly according to the number of nodes in the graph. It is worth noting that Deepwalk, Node2vec, Grarep, SDNE, Line, GCN, GAE and VGAE are all techniques based on graph representation learning. They all learn the representation of nodes in the graph to perform the link weight prediction task. We conclude that the model that generates the best representation for the nodes in the graph is the most successful. As (Kang et al., 2019) points out, good node embeddings should yield good prediction accuracy, because eventually some other machine learning system should use these embeddings to make valuable predictions. For this purpose, aggregating information from the most important neighbors and nodes is crucial. Meanwhile LGLP (Kang et al., 2019) points out that learning node embeddings by graph convolution in a line graph is more effective than performing neighbor embedding aggregation in the original graph. Therefore we introduce the line graph mechanism. For these graph representation learning methods, simply converting node vectors to connected edge vectors may not accurately characterize the structure of connected edges. Directly mapping connected edges to low-dimensional vectors can better preserve the structural features of incoming connected edges and is more suitable for network analysis tasks where connected edges are the object of study.

## 5. Conclusion and Future Work

Inspired by LGLP, we propose a new link weight model, LGLWP.This model applies subgraph extraction and node labeling techniques that are currently widely used in link prediction and link weight prediction. To overcome the limitations of the unweighted graph node labeling technique in LGLP, we introduce a new weighted graph node labeling technique while retaining the line graph and graph convolutional neural network architectures. Our model achieved the best results on each of the tested datasets.

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline Model & Neural & C.elegans & Netscience & P.blog & UC-social & Condmat \\ \hline rWCN & 5.78\(\pm\)0.74 & 1.79\(\pm\)0.76 & 0.43\(\pm\)0.05 & 3.02\(\pm\)0.03 & 2.4527\(\pm\)0.0942 & 0.1992\(\pm\)0.0029 \\ rWAA & 6.3\(\pm\)0.75 & 2.36\(\pm\)0.84 & 0.42\(\pm\)0.05 & 0.89\(\pm\)0.02 & 0.6617\(\pm\)0.0292 & 0.1816\(\pm\)0.0031 \\ rWRA & 6.7\(\pm\)0.76 & 2.93\(\pm\)0.91 & 0.42\(\pm\)0.05 & 1.09\(\pm\)0.01 & 0.5852\(\pm\)0.0067 & 0.1932\(\pm\)0.0027 \\ LG-RF & 0.235\(\pm\)0.006 & 0.183\(\pm\)0.003 & 0.213\(\pm\)0.005 & 0.099 \(\pm\)0.003 & 0.223\(\pm\)0.002 & - \\ LG-GBDT & 0.383\(\pm\)0.004 & 0.276\(\pm\)0.005 & 0.181\(\pm\)0.006 & 0.239\(\pm\)0.003 & 0.369\(\pm\)0.003 & - \\ LG-SVM & 0.236\(\pm\)0.006 & 0.152\(\pm\)0.004 & 0.212\(\pm\)0.004 & 0.171\(\pm\)0.004 & 0.225\(\pm\)0.003 & - \\ NEW & 0.2056\(\pm\)0.0064 & 0.1421\(\pm\)0.0081 & 0.0891\(\pm\)0.0115 & 0.0797\(\pm\)0.0024 & 0.2076\(\pm\)0.0017 & 0.1953\(\pm\)0.0016 \\ \hline Deepwalk & 0.2211\(\pm\)0.0043 & 0.1421\(\pm\)0.0045 & 0.1214\(\pm\)0.0151 & 0.0816\(\pm\)0.0023 & 0.2124\(\pm\)0.0026 & 0.1943\(\pm\)0.0008 \\ Node2vec & 0.2153\(\pm\)0.0054 & 0.1413\(\pm\)0.0052 & 0.1199\(\pm\)0.0126 & 0.0817\(\pm\)0.0021 & 0.2088\(\pm\)0.0022 & 0.2032\(\pm\)0.0011 \\ Grarep & 0.2254\(\pm\)0.0092 & 0.1424\(\pm\)0.0053 & 0.1484\(\pm\)0.0378 & 0.0798\(\pm\)0.0021 & 0.2098\(\pm\)0.0012 & 0.1945\(\pm\)0.0016 \\ SDNE & 0.2060\(\pm\)0.0058 & 0.1380\(\pm\)0.0167 & 0.1386\(\pm\)0.0263 & 0.0771\(\pm\)0.0029 & 0.2056\(\pm\)0.0029 & 0.1808\(\pm\)0.0014 \\ LINE & 0.2222\(\pm\)0.0079 & 0.1390\(\pm\)0.0052 & 0.1377\(\pm\)0.0112 & 0.0809\(\pm\)0.0021 & 0.2102\(\pm\)0.0016 & 0.1927\(\pm\)0.0016 \\ GAE\({}^{*}\) & 0.2161\(\pm\)0.0082 & 0.1508\(\pm\)0.0058 & 0.4452\(\pm\)0.0052 & 0.1466\(\pm\)0.0142 & 0.2360\(\pm\)0.0041 & 0.4112\(\pm\)0.0017 \\ VGAE\({}^{*}\) & 0.2332\(\pm\)0.0089 & 0.1496\(\pm\)0.0054 & 0.4458\(\pm\)0.0052 & 0.1340\(\pm\)0.0008 & 0.2318\(\pm\)0.0043 & 0.4127\(\pm\)0.0017 \\ GCN & 0.2216\(\pm\)0.0098 & 0.1583\(\pm\)0.0139 & 0.1232\(\pm\)0.0146 & 0.2720\(\pm\)0.0770 & 0.2540\(\pm\)0.0614 & 0.2117\(\pm\)0.0036 \\ SEA & 0.2015\(\pm\)0.0052 & **0.11134\(\pm\)0.0055** & 0.0823\(\pm\)0.0094 & **0.0754\(\pm\)0.002** & **0.19764\(\pm\)0.0028** & 0.1694\(\pm\)0.0018 \\ \hline LGLPW & **0.1915\(\pm\)0.0086** & 0.1299\(\pm\)0.0061 & **0.0624\(\pm\)0.0137** & 0.0759\(\pm\)0.0019 & 0.2007\(\pm\)0.0029 & **0.1556\(\pm\)0.0024** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Root Mean Squared Errors, standard deviation on all of the datasets, In addition to LGLWP, GCN, other experimental data were obtained from (Kang et al., 2019). The best experimental results have been bolded. The second-best results are indicated with underlining.

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline Method & Neural & C.elegans & Netscience & P.blog & UC-social & Condmat \\ \hline Random labeling & 0.2115 \(\pm\)0.0066 & 0.1466\(\pm\)0.0068 & 0.0762\(\pm\)0.0154 & 0.0833\(\pm\)0.0013 & 0.2096\(\pm\)0.0025 & 0.1745\(\pm\)0.0034 \\ weighted graph labeling & 0.1915\(\pm\)0.0086 & 0.1309\(\pm\)0.0072 & 0.0698\(\pm\)0.0134 & 0.0766\(\pm\)0.0012 & 0.2017\(\pm\)0.0022 & 0.1556\(\pm\)0.0024 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Results for each version of the algorithm applied to all datasets. We report the Mean Squared errors with the Standard Deviation for 10 trials on each version.
In network analysis tasks where connected edges are the object of study, simply transforming node vectors into connected edge vectors may not accurately characterize the structural features of connected edges. Directly mapping the connected edges into low-dimensional vectors can better characterize the structural features of the connected edges, and the line graph is certainly a very good solution. In our future research, we will focus on the application of line graphs in the network analysis task with connected edges as the object of study. A good subgraph node labeling algorithm is also crucial for the final prediction. A good subgraph extraction strategy and node labeling algorithm are both worthy future work.
