Generative Graph Neural Networks for Link Prediction
Inferring missing links or detecting spurious ones based on observed graphs,
known as link prediction, is a long-standing challenge in graph data analysis.
With the recent advances in deep learning, graph neural networks have been used
for link prediction and have achieved state-of-the-art performance.
Nevertheless, existing methods developed for this purpose are typically
discriminative, computing features of local subgraphs around two neighboring
nodes and predicting potential links between them from the perspective of
subgraph classification. In this formalism, the selection of enclosing
subgraphs and heuristic structural features for subgraph classification
significantly affects the performance of the methods. To overcome this
limitation, this paper proposes a novel and radically different link prediction
algorithm based on the network reconstruction theory, called GraphLP. Instead
of sampling positive and negative links and heuristically computing the
features of their enclosing subgraphs, GraphLP utilizes the feature learning
ability of deep-learning models to automatically extract the structural
patterns of graphs for link prediction under the assumption that real-world
graphs are not locally isolated. Moreover, GraphLP explores high-order
connectivity patterns to utilize the hierarchical organizational structures of
graphs for link prediction. Our experimental results on all common benchmark
datasets from different applications demonstrate that the proposed method
consistently outperforms other state-of-the-art methods. Unlike the
discriminative neural network models used for link prediction, GraphLP is
generative, which provides a new paradigm for neural-network-based link
prediction.
Xingping Xian, Tao Wu, Xiaoke Ma, Shaojie Qiao, Yabin Shao, Chao Wang, Lin Yuan, Yu Wu
# Generative Graph Neural Networks for Link Prediction

###### Abstract

Inferring missing links or detecting spurious ones based on observed graphs, known as link prediction, is a long-standing challenge in graph data analysis. With the recent advances in deep learning, graph neural networks have been used for link prediction and have achieved state-of-the-art performance. Nevertheless, existing methods developed for this purpose are typically discriminative, computing features of local subgraphs around two neighboring nodes and predicting potential links between them from the perspective of subgraph classification. In this formalism, the selection of enclosing subgraphs and heuristic structural features for subgraph classification significantly affects the performance of the methods. To overcome this limitation, this paper proposes a novel and radically different link prediction algorithm based on the network reconstruction theory, called GraphLP. Instead of sampling positive and negative links and heuristically computing the features of their enclosing subgraphs, GraphLP utilizes the feature learning ability of deep-learning models to automatically extract the structural patterns of graphs for link prediction under the assumption that real-world graphs are not locally isolated. Moreover, GraphLP explores high-order connectivity patterns to utilize the hierarchical organizational structures of graphs for link prediction. Our experimental results on all common benchmark datasets from different applications demonstrate that the proposed method consistently outperforms other state-of-the-art methods. Unlike the discriminative neural network models used for link prediction, GraphLP is generative, which provides a new paradigm for neural-network-based link prediction. The code is available at [https://github.com/star4455/GraphLP](https://github.com/star4455/GraphLP).

keywords: Graph Machine Learning, Graph Neural Networks, Link Prediction, Structural Patterns, Network Reconstruction. +
Footnote †: journal: Journal of LaTeX Templates

## 1 Introduction

Graphs provide an elegant representation for characterizing entities and their interrelations in complex systems. Given that real-world graphs can usually only be partially observed and are often noisy, link prediction aimed at inferring missing and spurious links based on observed graphs is a paradigmatic and fundamental problem across many scientific domains, including knowledge graph completion [52], experimental design in biological networks [6], fake account detection in online social networks [24], and product recommendation on e-commerce websites [31].

To address the link prediction problem, numerous heuristic methods have been proposed, including local indices such as Common Neighbors (CN) [2], and Resource Allocation (RA) [61], global indices such as Katz [25], and SimRank [23], and quasi-local indices such as the Local Path Index (LP) [61]. However, heuristic methods have a strong assumption on when two nodes are likely to be linked in real-world graphs and lack universal applicability to diverse areas [8]. Subsequently, statistical learning-based algorithms have been proposed to obtain ground-breaking results, such as maximum likelihood-based hierarchical structure model [13], stochastic block model [21], matrix factorization-based link prediction method [37], Linear Optimization (LO) link prediction [38], and Low Frobenius norm-based Link Prediction (LFLP) method [53]. With the proposal of network representation learning, various network embedding algorithms have been put forth so that the likelihood of a non-observed links can be estimated based on the proximity of nodes in low-dimensional vector space, including LINE [44], Node2Vec [20], and DNGR [10].

Recently, driven by the dramatic advances in deep learning techniques, neural networks have gradually been used to solve the link prediction problem. [56] trained a fully-connected neural network on the enclosing subgraphs of target links for link prediction, wherein a Weisfeiler-Lehman (WL) algorithm-based graph labeling mechanism was proposed to encode subgraphs. Based on the enclosing subgraphs extracted around links, [57] trained a Graph Neural Network (GNN) for link prediction to achieve a performance comparable to that of heuristic methods. Along this line of research, [36] encoded subgraphs into random-walk transition probabilities and then computed features using these probabilities to classify positive and negative links. Although these subgraph classification-based methods have achieved state-of-the-art link prediction performance, the prediction results are found to be considerably affected by the extraction process of the _k_-hop enclosing subgraphs and the graph structure features for them. For example, in representation learning on graphs [55], the range of enclosing subgraphs strongly depends on the graph structure, and the effective range should be different for subgraphs with varying properties.

Typically, from the perspective of subgraph classification, link prediction methods treat subgraphs in real-world graphs independently and equivalently. That is, the global structural information of real-world graphs is totally neglected during this process. However, extensive empirical analyses indicate that real-world graphs are not locally isolated but globally relevant
[35; 51]; here, nodes and edges naturally portray different structural roles and contribute differently to the global organization of real-world graphs [53; 54]. Moreover, subgraph classification-based link prediction methods assume that real-world graphs exhibit low-order connectivity patterns and can be captured at the level of individual nodes and edges. However, empirical studies have discovered that real-world graphs exhibit high-order organizations at the level of small subgraphs, which are recursively grouped into a hierarchical structure [7; 3]. An illustrative example of the global and high-order organization in real-world graphs is depicted in Figure 1. Hence, two challenges need to be addressed for link prediction: (i) how to learn good representation preserving both local and global graph structural features? and (ii) how to characterize and utilize hierarchical structure patterns?

To address these challenges, instead of predicting potential links through subgraph classification, this study designs a novel generative and multi-order GNN for link prediction, called GraphLP. Evidently, real-world graphs share some global properties, such as low-rank and sparsity, that can be used to provide guidance for graph learning. Hence, motivated by the network reconstruction theory [21], GraphLP defines a self-representation model-based collaborative inference operation to refine the observed graphs globally, which assumes that the original graph can be reconstructed utilizing the correlation between subgraph patterns. Assuming that the paths between a pair of nodes provide evidence for the existence of potential links, GraphLP extracts the local structural information via a high-order connectivity operation on the observed graphs. Thus, every neural network layer obtains the connectivity of node pairs within two-hop neighborhood, and a neural network with multiple connectivity layers captures the degree of connectivity between node pairs with various path lengths. Meanwhile, the weighted adjacency matrices generated by the connectivity operation in every neural network layer reflect the multi-order connectivity pattern in the graphs. Further, the hierarchical organizational structure of real-world graphs is explored by applying a collaborative inference operation. The contributions of this study can be summarized as follows:

* **Generative framework.** Rather than subgraph classification based discriminative schemes, a novel network reconstruction-based generative GNN is proposed for link prediction, which provides a new paradigm for the application of neural networks in link prediction problem.
* **End-to-end learning.** Instead of designing heuristic graph structural features for subgraph representation, local and global structural patterns are extracted and fused in an end-to-end fashion for link prediction.
* **Algorithm.** A novel collaborative inference operation and high-order connectivity computation mechanism are developed to characterize the structural patterns in real-world graphs at different scales.
* **Experiment.** Extensive experiments on real-world datasets from different areas reveal that the proposed method, GraphLP, achieves promising performance and consistently outperforms other state-of-the-art methods.

**Paper Organization.** The rest of this work is organized as follows. Section 2 discusses related studies. Section 3 presents the problem definitions and describes the preliminaries. Section 4 describes the proposed method. Section 5 presents the experimental results, and finally, Section 6 presents the conclusion and discussion.

## 2 Related Work

GNNs and link prediction task have been extensively investigated in recent years. A brief review of related studies is provided in this section.

### Graph Neural Networks

Owing to their potential in modeling the complex structures of non-Euclidean graphs, GNNs have achieved state-of-the-art performance on almost all graph-based tasks, such as node classification, graph classification, link prediction. Based on different theories and perspectives, a plethora of different GNNs have

Figure 1: An illustrative example depicting the global and high-order organizations of real-world graphs. (a) Gene network for C. elegans [12]. (b) Representative hierarchical star-like structure [45]. (c) Representative hierarchical modular organization [39]. (b) and (c) depict the representative structural patterns of real-world graphs such as (a).
been proposed over the years. Generally, GNNs can be divided into two categories: spectral-based and spatial-based methods. Of these, spectral-based GNNs are types of GNNs that design graph convolution operators in the spectral domain using Fourier transform. The involved convolution operation is defined as follows:

\[f_{1}*f_{2}=\mathbf{U}[(\mathbf{U}^{\mathrm{T}}f_{1})\odot(\mathbf{U}^{\mathrm{ T}}f_{2})], \tag{1}\]

where \(\odot\) denotes an element-wise product. The spectral filter is defined as \(\mathbf{g}=\mathbf{U}^{\mathrm{T}}f_{1}\), and the node signal \(\mathbf{X}\) can be processed as follows:

\[\mathbf{Z}=\mathbf{U}[\mathbf{g}(\Lambda)\odot(\mathbf{U}^{\mathrm{T}}\mathbf{ X})]=\mathbf{U}\mathbf{g}(\Lambda)\mathbf{U}^{\mathrm{T}}\mathbf{X}. \tag{2}\]

where \(\mathbf{U}\) denotes a matrix of eigenvectors of the normalized Laplacian graph \(\mathbf{L}=\mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1} {2}}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{\mathrm{T}}\)[11]. Assuming that feature representation of node should be affected only by its \(k\)-hop neighborhood, [16] proposed a Chebyshev polynomial based \(k\)-localized convolution and developed a convolutional neural network, ChebNet, which eliminated the need to compute the eigenvectors of the Laplacian. Subsequently, [50] simplified the Chebshev polynomial filter using its first-order approximation and proposed the popular spectral-based method called Graph Convolutional Networks (GCNs). Notably, spatial-based GNNs define graph convolution operator based on graph topology wherein the feature vectors of node's neighbors are aggregated via a permutation-invariant function. Specifically, [22] proposed a GraphSAGE approach that sampled fixed size neighborhood nodes and used max pooling, mean pooling, and LSTM pooling scheme to aggregate neighbor information. Considering the different weights of node's neighbors, [46] proposed a Graph Attention Network (GAT) algorithm to calculate attention coefficient and then aggregated the neighborhood information. Other related models include PATCHY-SAN [34], DCNN [4], and further details on GNNs can be found in the review [60].

### Neural Networks based Link Prediction

Following heuristic methods, matrix completion-based methods and network embedding-based methods, neural networks have been gradually applied to link prediction problem and have achieved state-of-the-art results. Specifically, [56] proposed a link prediction method called Weisfeiler-Lehman Neural Machine (WLNM), which labeled nodes using the Weisfeiler-Lehman algorithm and encoded subgraphs to construct a feedforward neural network-based classification model. Next, from the perspective of subgraph classification, [57] proposed a novel GNN-based link prediction framework, SEAL, to learn subgraph structures and node features from local enclosing subgraphs. Along this line, to directly leverage the topology features of local subgraphs, [36] proposed a new random-walk-based pooling scheme, WalkPool, and built features for subgraph classification. Moreover, [18] proposed a neural network-based link prediction method with only one-hop neighborhood information, which demonstrated almost equivalent performance to the WLNM and SEAL. Instead of subgraph classification, [8] converted the original graph into a corresponding line graph and solved the node classification problem for link prediction. To perform link prediction for general directed or undirected complex networks, [48] represented the adjacency matrices of networks as binary images and developed a generative adversarial networks (GANs)-based method. In addition, because existing GNN-based methods do not scale appropriately to large graphs, [30] extracted sparse enclosing subgraphs based on multiple random walks and presented a scalable link prediction solution, called ScaLed. To reduce the time required to determine the distances between two nodes, [27] defined an anchor-based distance and proposed a new distance-enhanced GNN method for link prediction.

Among all existing methods for link prediction, the work closest to the one considered in this study is the GANs-based method [48]. However, this method predicts potential links via image processing within the GANs framework, whereas the proposed method conducts link prediction via GNNs-based network reconstruction.

### Network Structure Analysis

Real-world graphs, also known as complex networks, are abstract representation of complex systems and have been extensively studied in the field of network science. Consequently, numerous studies have revealed that complex networks exhibit rich and diverse connectivity patterns. [32] augmented that the organization of real networks usually embodies both regularities and irregularities, where the former can be modeled and decides the extent to which the formation of a network can be explained. Notably, link predictability reflects the structural regularities in real-world networks and denotes the inherent difficulty of link prediction. [53] proposed a self-representation network model-based method, called NetSER, for measuring and regulating link predictability of networks. [54] proposed a deep linear coding-based link prediction adversarial attack method by disturbing the underlying structural pattern of networks, which proved that links play global structural roles in network organization. Moreover, [7] suggested that high-order connectivity patterns are essential for understanding the fundamental structures of networks and developed a framework that identified clusters of network motifs. [41] claimed that hierarchical structure plays an important role in complex systems. To prove the existence of hierarchical organization, an unsupervised method for extracting the hierarchical organization of complex networks was introduced and validated.

Although real-world graphs exhibit various structural patterns, most existing neural networks-based link prediction methods simply assume that they are flattened and locally isolated, and these methods judge the existence of links explicitly based only on local enclosing subgraphs. With the exception of local structural features, this study focuses on integrating global and hierarchical structural patterns into neural networks for link prediction.

## 3 Problem Definition and Preliminaries

### Problem Definition

NotationsLet \(\mathcal{G}=(V,\mathcal{E})\) denote an undirected and unweighted graph, where \(V=\{v_{1},\cdots,v_{N}\}\) denotes the set of nodes and \(\mathcal{E}=\{e_{1},\cdots,e_{M}\}\) denotes the set of edges. The adjacency matrix of graph \(\mathcal{G}\) is denoted as \(\mathbf{A}\in\{0,1\}^{N\times N}\), where \(\mathbf{A}_{ij}=1\) if nodes \(i\) and \(j\) are connected and \(\mathbf{A}_{ij}=0\) otherwise. Each edge \(e\) can be represented as a node pair \((\mathbf{u},\mathbf{v},)\), where \(\mathbf{u},\mathbf{v}\in\mathcal{V}\). Let \(\mathcal{N}(u)\) denote the neighbors of node \(u\), \(\mathcal{N}(u)=\{v|(\mathbf{u},\mathbf{v})\in\mathcal{E}\}\).

**Link Prediction**. Given an observed graph \(\mathcal{G}_{o}=(V,\mathcal{E}_{o})\) that corresponds to the original graph \(\mathcal{G}=(V,\mathcal{E})\), link prediction aims to infer the presence or absence of an edge between a pair of target nodes based on \(\mathcal{G}_{o}\), thereby generating a recovered graph \(\mathcal{G}^{*}\) to approximate the original graph \(\mathcal{G}\). In particular, the prediction problem involves identifying a function that generates
a likelihood score for a pair of nodes \((\mathbf{u},\mathbf{v})\notin\mathbf{\xi}\) to infer the missing link \((\mathbf{u},\mathbf{v})\), or to produce a likelihood score for an existing edge \((\mathbf{u},\mathbf{v})\in\mathbf{\xi}\) to identify spurious links. Thus, the link prediction problem can be formulated as \(s_{\mathbf{u}\pi}=f(\mathbf{u},\mathbf{v},\mathbf{\Lambda}|\mathbf{\theta})\), where \(\mathbf{\theta}\) denotes the parameter of link prediction model. In this work, \(\mathbf{\xi}_{m}\) and \(\mathbf{\xi}_{s}\) denote the identified missing and spurious links, respectively.

Note that data augmentation is a set of techniques that increases the amount and diversity of data by creating reasonable virtual data points from existing data, such that better machine learning models can be constructed based on them. According to [59], this study considers graph data augmentation and adopts a random mapping mechanism to produce augmented graph set \(\mathcal{D}\) based on the observed graph \(\mathbf{\xi}_{o}=(\mathcal{V},\mathbf{\xi}_{o})\). Specifically, the set of all possible edges in the graph \(\mathbf{\xi}_{o}\) is denoted as \(\Omega\), the existing edge set is denoted as \(\mathbf{\xi}_{o}\), and the non-existing edge set is denoted as \(\mathbf{\xi}_{nom}=\Omega-\mathbf{\xi}_{o}\). Thus, the candidate sets for random mapping are defined as follows:

\[\mathbf{\xi}_{dd}^{c}=\mathbf{\xi}_{o},\quad\mathbf{\xi}_{add}^{c}=\mathbf{\xi}_{nom}. \tag{3}\]

Thereafter, samples are randomly produced from the candidate sets to obtain the edge sets \(\mathbf{\xi}_{dd}\) and \(\mathbf{\xi}_{add}\). Finally, a new augmented graph is generated by modifying the graph \(\mathbf{\xi}_{o}\) based on \(\mathbf{\xi}_{del}\) and \(\mathbf{\xi}_{add}\):

\[\mathbf{\xi}^{\prime}=(\mathcal{V},(\mathcal{B}\cup\mathbf{\xi}_{add})\backslash\mathbf{ \xi}_{del}). \tag{4}\]

Each input graph can be viewed as an instance for link prediction, owing to the generative learning scheme of the models considered in this work. Thus, the dataset containing a series of augmented graphs can be denoted as \(\mathcal{D}=\{\mathbf{\xi}_{0}|i=1,...,l\}\) and split to yield disjoint training and validation sets. These can be denoted as \(\mathcal{D}_{train}\) and \(\mathcal{D}_{val}\) respectively, wherein the missing and spurious links of the validation set are guaranteed not to appear in the training set. The observed graph \(\mathbf{\xi}_{o}\) used to generate the augmented graphs is defined as test set \(\mathcal{D}_{test}\).

### Graph Convolutional Networks

GCNs are a class of neural networks designed to generalize traditional convolution operator for non-euclidean graph-structured data. In essence, GCNs aim to learn new feature representations of nodes in graphs by exploiting their structural information. Let adjacency matrix \(\mathbf{\Lambda}\in\{0,1\}^{\forall\mathcal{N}\mathcal{N}}\) denote the structural information of the graph \(\mathbf{\xi}\), and \(\mathbf{\mathbf{X}}\in\mathbb{R}^{N\times F}\) denote the feature matrix of all graph nodes. Mathematically, using the output of the \(l\)-th layer as the input for the next layer, each neural network layer can be formulated as a nonlinear function:

\[\mathbf{\mathbf{H}}^{(l+1)}=f(\mathbf{\mathbf{H}}^{(l)},\mathbf{\mathbf{A}}) \tag{5}\]

where \(\mathbf{\mathbf{H}}^{(l)}\) corresponds to the feature matrix of the \(l\)-th layer, and \(\mathbf{\mathbf{H}}^{(l)}=\mathbf{\mathbf{X}}\) is the input feature matrix of the first layer. Specific GCNs models differ only in the manner in which the nonlinear function \(f(\cdot)\) is instantiated. A simple example of \(f(\cdot)\) is as follows:

\[f(\mathbf{\mathbf{H}}^{(l)},\mathbf{\mathbf{A}})=\sigma(\mathbf{\mathbf{A}}\mathbf{\mathbf{H} }^{(l)}\mathbf{\mathbf{W}}^{(l)}) \tag{6}\]

where \(\sigma(\cdot)\) denotes a nonlinear activation function, such as a Rectified Linear Unit (ReLU), and \(\mathbf{\mathbf{W}}^{(l)}\) denotes a trainable weight matrix for the \(l\)-th layer. With this propagation rule, the neighbour's features are aggregated to represent each node at every layer, and the features become increasingly abstract by stacking layers on top of each other. However, there exist two limitations: the propagation rule simply aggregates the features of neighboring nodes but not the node itself, and the multiplication with \(\mathbf{\mathbf{A}}\) expected to change the scale of the feature vectors. That is, the nodes with a high degree will have a larger value, and the nodes with a low degree may have smaller values. To address the problems, a new propagation function, \(f(\cdot)\), is presented as follows:

\[f(\mathbf{\mathbf{H}}^{(l)},\mathbf{\mathbf{A}})=\sigma(\hat{\mathbf{\mathbf{D}}}^{-\frac{ 1}{2}}\hat{\mathbf{\mathbf{A}}}\hat{\mathbf{\mathbf{D}}}^{-\frac{1}{2}}\mathbf{\mathbf{H} }^{(l)}\mathbf{\mathbf{W}}^{(l)}) \tag{7}\]

where \(\hat{\mathbf{\mathbf{A}}}\) is obtained by adding an identity matrix \(\mathbf{\mathbf{I}}\) to the adjacency matrix \(\hat{\mathbf{\mathbf{A}}}=\mathbf{\mathbf{A}}+\mathbf{\mathbf{I}}\), \(\mathbf{\mathbf{D}}\) denotes the diagonal node degree matrix of \(\hat{\mathbf{\mathbf{A}}}\), and \(\hat{\mathbf{\mathbf{D}}}^{-\frac{1}{2}}\hat{\mathbf{\mathbf{A}}}\hat{\mathbf{\mathbf{D}}}^ {-\frac{1}{2}}\) denotes symmetric normalization.

### Low-rank and Sparse Modeling

Traditionally, Principal component analysis (PCA) was proposed to determine a low-dimensional representation of data while retaining as much information as possible. However, the PCA is particularly effective when dealing with Gaussian noise, which is independent and identically distributed with respect to the original data. Hence, the Robust Principal Component Analysis (RPCA) [9] has been proposed to eliminate the effect of erratic noise (outliers). PCA and RPCA methods implicitly assume that the underlying data structure is a single low-rank subspace; however, real-world data may be drawn from a union of multiple subspaces, and therefore, modeling may be inaccurate. To this end, Low-Rank Representation (LRR) [28] has been proposed.

Considering the correlation between the connectivity patterns of nodes in real-world graphs, the adjacency matrix of the graphs should be low-rank. In other words, the rows or columns of the adjacency matrix must not be linearly independent. Thus, assuming that hidden non-zero entries representing missing links can be recovered according to the adjacency matrix, [37] proposed an RPCA-based link prediction method, which is formulated as the following optimization problem:

\[\min_{\mathbf{\mathbf{X}}\cdot\mathbf{\mathbf{E}}}\text{rank}(\mathbf{\mathbf{X}}^{*})+ \gamma\|\mathbf{\mathbf{E}}\|_{0}\text{ }s.t.,\ \mathbf{\mathbf{A}}=\mathbf{\mathbf{X}}^{*}+\mathbf{\mathbf{E}} \tag{8}\]

where \(\text{rank}(\mathbf{\mathbf{X}}^{*})\) denotes the rank of matrix \(\mathbf{\mathbf{X}}^{*}\), \(\|\cdot\|_{0}\) is the \(\ell_{0}-\)norm, and \(\gamma\) denotes the balancing parameter. The method searches for \(\mathbf{\mathbf{X}}^{*}\) with a low rank as low as possible and \(\mathbf{\mathbf{E}}\) as sparse as possible from \(\mathbf{\mathbf{A}}\). Moreover, by representing a network structure with as few representative subgraphs as possible, [53] proposed an LRR-based link prediction method, wherein networks could be modeled via a low-rank and sparse represen

\begin{table}
\begin{tabular}{|c|l|} \hline Notations & Descriptions \\ \hline \(\mathbf{\mathbf{\xi}}\) & Original graph \\ \hline \(\mathbf{\mathbf{\xi}}_{o}\) & Observed graph \\ \hline \(\mathbf{\mathbf{A}}\) & Adjacency matrix of graph \\ \hline \(\mathbf{\mathbf{\xi}}_{m}\) & Missing links \\ \hline \(\mathbf{\mathbf{\xi}}_{s}\) & Spurious links \\ \hline \(\mathbf{\mathbf{\Omega}}\) & Dataset that contains augmented graphs \\ \hline \(\mathbf{\mathbf{H}}^{(l)}\) & Feature matrix of \(l\)-th neural network layer \\ \hline \(\mathbf{\mathbf{W}}^{(l)}\) & Trainable weight matrix for the \(l\)-th layer \\ \hline \(\|\cdot\|_{0}\) & \(\ell_{0}-\)norm \\ \hline \(\|\cdot\|_{2,1}\) & \(\ell_{2,1}-\)norm \\ \hline \end{tabular}
\end{table}
Table 1: Notations and meanings.
tation, as follows:

\[\min_{\mathbf{Z},\mathbf{E}}\text{rank}(\mathbf{Z})+\alpha\|\mathbf{Z}\|_{0}+ \beta\|\mathbf{E}\|_{2,1}\ s.t.,\ \mathbf{A}=\mathbf{A}\mathbf{Z}+\mathbf{E} \tag{9}\]

where \(\mathbf{Z}\) denotes the representation matrix reflecting the organization principle of the network, and \(\|\cdot\|_{2,1}\) is the \(\ell_{2,1}-\)norm.

The notations used in this study are listed in Table 1.

## 4 The Proposed Method

This section presents the proposed link prediction method, GraphLP. As depicted in Figure 2, the framework of GraphLP consists of three main components:

* Collaborative inference operation. There exist certain similarities between the connection patterns of individuals in a complex system such that the perturbed structure of real-world graphs can be recovered globally based on the correlation between subgraph patterns (Section 4.1).
* High-order connectivity computation. The existence of a link between any two target nodes is intended to be primarily determined by the connectivity degree between nodes, i.e., the number of paths and their length. Thus, the likelihood of a link can be estimated locally by computing the connectivity (Section 4.2).
* Pattern fusion operation. In addition to the first-order adjacency matrix, the connection patterns of nodes in the high-order adjacency matrix are also considered to be correlated, and the high-order connectivity can be reconstructed based on the collaborative inference. Thus, the graph topology can be estimated by fusing the k-order (\(k\geq 1\)) adjacency matrix (Section 4.3).

### Collaborative Inference Operation

[32] suggested that link formation in real-world graphs is usually driven by both regular and irregular factors, and the former can be explained based on the mixture of multiple mechanisms, such as homophily, triadic closure, preferential attachment. Meanwhile, assuming that high-dimensional data are a mixture of simple data and are drawn from a union of multiple low-dimensional linear subspaces, the LRR has been proposed to represent the data \(\mathbf{A}=[a_{1},a_{2},...,a_{N}]\) as a linear combination of the basis in a "dictionary" \(\mathbf{D}=[d_{1},d_{2},...,d_{M}]\):

\[\min_{\mathbf{Z}}\text{rank}(\mathbf{Z})\ s.t.,\ \mathbf{A}=\mathbf{D} \mathbf{Z}, \tag{10}\]

Figure 2: Demonstration of our link prediction method, GraphLP. (a) Link prediction method, GraphLP. The original graph is perturbed using a random mapping mechanism to obtain the observed graph; after this, the observed graph is further perturbed to generate augmented graphs. These augmented graphs are fed into GraphLP to learn the model using the observed graph as the label. Subsequently, the learned model is used to infer the original graph based on the observed graph. (b) Self-representation-based collaborative inference. Based on the structural regularity of graphs, the original graph can be reconstructed by utilizing the correlation between subgraph patterns. (c) Example of high-order connectivity. In addition to the 1-hop neighborhood, multi-hop connectivity influences the existence of links. The right graph represents the two-hop connectivity of the graph on the left, and the red dotted lines in the left graph provide an example of the two-hop connectivity path of node 2.
Thus, the optimal representation matrix \(\mathbf{Z}^{*}\) uncovers the underlying subspaces in the data. By using each subspace to model a homogeneous subset of the data, multiple subspaces in LRR can capture heterogeneous structures within the data. Therefore, considering the above ideas, the regular structure of real-world graphs can be described appropriately by the LRR model, wherein the generation mechanisms of graph organization essentially corresponds to subspaces and the low rankness constraint captures the global correlation in graphs. Meanwhile, based on the generation mechanisms of graph organization, individual nodes may have similar connection patterns, and substructures that follow the same generation mechanism can be represented by each other, as depicted in Figure 2(b). Therefore, by using the adjacency matrix \(\mathbf{A}\) as the dictionary, the real-world graph can be represented by itself, as follows:

\[\min_{\mathbf{Z}}\text{rank}(\mathbf{Z})\text{ \emph{s.t.}, }\mathbf{A}=\mathbf{A}\mathbf{Z}. \tag{11}\]

In addition to their regular structure, real-world graphs also contain irregular components. Thus, we let matrix \(\mathbf{E}\) denote such irregular connections; then, the proposed self-representation model can be modified as \(\mathbf{A}=\mathbf{A}\mathbf{Z}+\mathbf{E}\). According to the LRR, data are considered to be "sample specific", and the \(\ell_{21}-\)norm is adopted to constrain the matrix \(\mathbf{E}\), i.e., \(||\mathbf{E}||_{2,1}\). However, although the proposed method can be used to model real-world graphs, the low-rank model and \(\ell_{21}-\)norm constraints are usually solved using Alternating direction method (ADM), which requires a large number of iterations and has high complexity. Therefore, a reasonable strategy is to relax the constraints with Frobenius norm:

\[\min_{\mathbf{Z}}||\mathbf{Z}||_{\mathcal{G}}^{2}+\lambda||\mathbf{A}- \mathbf{A}\mathbf{Z}||_{\mathcal{G}}^{2}\text{ \emph{s.t.}, }\mathbf{A}=\mathbf{A}\mathbf{Z}+\mathbf{E} \tag{12}\]

Let \(\mathcal{L}=||\mathbf{Z}||_{\mathcal{G}}^{2}+\lambda||\mathbf{A}-\mathbf{A} \mathbf{Z}||_{\mathcal{G}}^{2}\) denote the partial derivative of \(\mathcal{L}\) with respect to \(\mathbf{Z}\) is \(\partial\mathcal{L}/\partial\mathbf{Z}=\mathbf{Z}\mathbf{Z}+\lambda(-2 \mathbf{A}^{\mathsf{T}}\mathbf{A}+2\mathbf{A}^{\mathsf{T}}\mathbf{A}\mathbf{Z})\). By setting \(\partial\mathcal{L}/\partial\mathbf{Z}=0\), the optimal representation \(\mathbf{Z}^{*}\) can be obtained as follows:

\[\mathbf{Z}^{*}=\lambda(\lambda\mathbf{A}^{\mathsf{T}}\mathbf{A}+\mathbf{I})^{- 1}\mathbf{A}^{\mathsf{T}}\mathbf{A}. \tag{13}\]

where \(\mathbf{I}\) denotes the identity matrix. Thus, in the case that the clean data is sufficient enough to represent the graph's structural patterns and the irregular connections are properly characterized, the structure perturbations can be inferred using \(\mathbf{A}\mathbf{Z}^{*}\). Hence, the collaborative inference operation is defined as follows:

\[\mathcal{C}\mathcal{B}(\mathbf{A})=\lambda\mathbf{A}(\lambda\mathbf{A}^{ \mathsf{T}}\mathbf{A}+\mathbf{I})^{-1}\mathbf{A}^{\mathsf{T}}\mathbf{A} \tag{14}\]

### High-order Connectivity Computation

According to local similarity indices for link prediction, the more the number of paths two nodes possess, the greater the similarity between them. Specifically, two nodes with a high mutual connectivity are more likely to generate a link between them. Thus, n-hop-based (\(n\geq 2\)) paths must be explored to characterize the local structural features for link prediction. Using a deep learning framework, the \(n\)-hop computation can be decomposed into two-hop operations on each neural layer. Hence, a high-order connectivity computation calculates the two hop connectivity of graph nodes in each layer, and the mutual connectivity of two nodes can be estimated by stacking the high-order connectivity computation mechanism. Assuming that the integer powers of the adjacency matrix characterizes the mutual connectivity of graph nodes, that is, \([\mathbf{A}^{\mathsf{n}}]_{ij}\) denotes the number of paths with length \(n\) connecting nodes \(i\) and \(j\), the high-order connectivity computation in each neural layer can be defined based on the idea of the second power of adjacency matrix \(\mathbf{A}\). From the perspective of graph convolution networks, high-order connectivity computation can be defined as

\[\mathcal{HCCA}(\mathbf{A})=\hat{\mathbf{D}}^{-\frac{1}{2}}\hat{\mathbf{A}} \hat{\mathbf{D}}^{-\frac{1}{2}}\mathcal{C}\mathcal{G}(\mathbf{A}), \tag{15}\]

where the weighted adjacency matrix generated by the proposed collaborative inference operation is viewed as the features of graph nodes. Figure 3 illustrates a high-order connectivity computation. As presented in Equation (15), the global and local structural features can be captured for link prediction at the level of individual nodes and edges. Thus, the nonlinear propagation function can be defined as follows:

\[\mathbf{H}^{(l+1)}=\hat{\mathbf{D}}^{-1}\hat{\mathbf{A}}\hat{\mathbf{D}}^{- \frac{1}{2}}\mathcal{C}\mathcal{G}(\mathbf{H}^{(l)})\mathbf{W}^{(l)}. \tag{16}\]

Thus, the hierarchical structure of real-world graphs can be characterized by executing the nonlinear propagation function iteratively, in which \(\mathcal{HCCA}(\mathbf{H}^{(l)})=\hat{\mathbf{D}}^{-\frac{1}{2}}\hat{\mathbf{A}} \hat{\mathbf{D}}^{-\frac{1}{2}}\mathcal{C}\mathcal{G}(\mathbf{H}^{(l)})\) represents the high-order connectivity of graph nodes, as depicted in Figure 2(c), and \(\mathcal{C}\mathcal{G}(\mathbf{H}^{(l+1)})\) denotes the collaborative inference.

### Pattern Fusion Operation

To estimate the likelihood of potential links, the output of the \((l-1)\)-th layer, i.e., \(\mathbf{H}^{(l)}\), is fed as the input of the \(l\)-th layer. Based on \(\mathcal{C}\mathcal{G}(\mathbf{H}^{(l)})\) and \(\mathcal{HCCA}(\mathbf{H}^{(l)})\), the shallow layers extract the low-order global and local structure features, while the deep layers extract the high-order global and local structure features. Meanwhile, the effective range that the local structure features drawn from increases as the model depth increases. Therefore, the structure features in different range at various order, i.e., \(\mathcal{HCCA}(\mathbf{H}^{(l)})\) and \(\mathcal{C}\mathcal{G}(\mathbf{H}^{(l)})\), \(0\leq l\leq L\), all contribute to the inference of potential links, although the exact extent of their contribution depends on the graph data.

To overcome the issues mentioned above, in addition to being used as the inputs of the next layer, the outputs of neural network layers are mapped to skip a block of several layers based on residual connections, as illustrated in Figure 2(a). Next, all outputs are concatenated and used as the input of a two-layer Multi-layer Perceptron (MLP), which is defined as:

\[\mathbf{O}\mathbf{=}\text{MLP}(\text{concat}(\mathcal{C}\mathcal{G}(\mathbf{H} ^{(l)}),\mathcal{HCCA}(\mathbf{H}^{(l)}))),0\leq l\leq L. \tag{17}\]

where \(\mathbf{O}\) is a vector containing the probabilities of links between all possible node pairs, and missing and spurious links can be inferred based on it.

Figure 3: Illustration of high-order connectivity computation.
### Model Training

To train the proposed model, augmented graphs generated based on the observed graph are used as training data, and the adjacency matrix of the observed graph is flatten as its labels \(\mathbf{Y}\), where \(\mathbf{Y}_{i:N*,j}\) denotes the existence of the link between nodes \(i\) and \(j\). Correspondingly, \(\mathbf{O}\) represents the prediction results obtained by the proposed model for all possible links. Here, the Binary Cross-Entropy (BCE) is used as the loss function:

\[\mathcal{L}=-\frac{1}{N^{2}}\sum_{i=1}^{N^{2}}\mathbf{Y}_{i}\log(\mathbf{O}_{i })+(1-\mathbf{Y}_{i})\log(1-\mathbf{O}_{i}). \tag{18}\]

The learned model is then deployed on the observed graph to reconstruct the original graph. The training process of GraphLP is outlined in Algorithm 1.

```
0: Training set \(\mathcal{D}_{train}\), validation set \(\mathcal{D}_{val}\), and test set \(\mathcal{D}_{test}\), number of neural network layers \(L\).
0: The well-trained model GraphLP.
1:while not convergence do
2:for\(0\leq l\leq L\)do
3: Conduct collaborative inference operation using (14);
4: Compute high-order connectivity using (16);
5:endfor
6: Fuse the outputs based on MLP using (17);
7: Update the model by minimizing the loss function (18);
8:endwhile
```

**Algorithm 1** Training Process of GraphLP

### Model Analysis

(1) Generalized local similarity indices. The high-order connectivity computation \(\mathcal{HCCAT}(\mathbf{H}^{(l)})\) in every neural network layer is essentially the second power of the adjacency matrix, and it obtains the connectivity of node pairs within two-hop neighborhood. As the model depth increases, the connectivity of node pairs in a wider range is considered. Thus, GraphLP can degenerate to \(S_{ij}=\mathbf{A}^{2}+\alpha\mathbf{A}^{3}+\beta\mathbf{A}^{4}+\cdots\) when collaborative inference and deep learning mechanism are abolished.

(2) Connection to WalkPool. WalkPool [36] first generates node representations based on GNN and encodes them into edge weights of the extracted enclosing subgraphs; following this, it uses the edge weights to compute the transition probabilities of random walk. Next, the method calculates a list of features based on the transition probabilities to classify the subgraphs. However, for an enclosing subgraph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), its variants \(\mathcal{G}^{*}=(\mathcal{V},\mathcal{E}\cup\{i,j\})\) and \(\mathcal{G}^{*}=(\mathcal{V},\mathcal{E}\backslash\{i,j\})\) are used as positive and negative samples, respectively. In essence, this method discriminates only those subgraphs that differ by a single edge and is not suitable for practical link prediction scenarios. In contrast, GraphLP can predict any potential links based on graph structure features.

(3) Connection to LFLP. The LFLP [53] constructs an adjacency matrix based on a self-representation model and then combines it with the observed network to identify missing and spurious links. The collaborative inference operation \(\mathcal{CG}(\mathbf{H}^{(l)})\) of our work is similar to that in the LFLP with respect to modeling the global structure of graphs; however, the difference is that only low-order global structural features are considered in LFLP, whereas multi-order global and local structural features are characterized based on the deep-learning framework in GraphLP.

## 5 Experiments

Further, extensive experiments are conducted on real-world graphs to evaluate the performance of the proposed method GraphLP: (1) Compare GraphLP with state-of-the-art methods; (2) Compare GraphLP with traditional baseline methods; (3) Model architecture analysis; (4) Model sensitivity analysis. Here, Area Under Curve (AUC) and Average Precision (AP) are adopted to evaluate the performance of the methods. Furthermore, Precision is used to verify the superiority of GraphLP over traditional link prediction methods. Based on the link prediction results \(\mathbf{O}\), the scores are sorted in descending and ascending orders, and following this, their top-L links are taken as the predicted missing and spurious links. Note that Precision is defined by calculating the ratio of accurately discovered links to the total number of links in the probe set:

\[\text{Precision}=\mathcal{T}/\mathcal{R} \tag{19}\]

where \(\mathcal{T}\) is the number of accurately identified links, and \(\mathcal{R}\) is the total number of links in the probe set.

### Experimental Settings

#### 5.1.1 Experimental Datasets

Herein, seven widely used graph datasets are used for link prediction. (1) USAir [40]. This is the transportation network of the United States, including 332 airports as nodes and 2,126 airlines as edges, connecting the United States worldwide. The average node degree is 12.81. (2) C.ele [49]. This is a neural network of C. elegans, with 297 neurons representing nodes and 2,148 synaptic connections representing edges. The average node degree is 14.46. (3) PB [1]. This dataset is a network of hyperlinks between weblogs on US political blogs, with 1,222 blogs on US politics as nodes and 16,714 hyperlinks between blogs as edges. The average node degree is 27.36. (4) NS [33]. This is an undirected co-authorship network with 1,589 nodes and 2,742 edges, where the nodes denote the scientists engaged in network science research, and the edges denote two scientists have co-authored a publication. The average node degree is 3.45. (5) Yeast [47]. This represents a protein-protein interaction network formed in yeast with 2,375 proteins as nodes and 11,693 protein-protein interactions as edges. The average node degree is 9.85. (6) E.coli [58]. This is a pairwise reaction network of metabolites with 1,805 nodes and 14,660 edges. The average node degree is 12.55. (7) Router [43]. It is a snapshot of the Internet structure at the level of autonomous systems, with 5,022 nodes and 6,258 edges, in which the nodes represent routers and the edges represent the data transmission between routers. The average node degree is 2.49. The properties of the datasets are listed in Table 2.

To extensively validate the performance of the proposed method, 90% and 50% of the links of the original graph are selected randomly to first construct the observed graphs. Thereafter, based on the observed graph \(\mathcal{G}_{o}\), 10% nonexing links are add randomly as spurious links, and 10% existing links are removed randomly as missing links, denoted as \(\mathcal{E}_{del}\) and \(\mathcal{E}_{add}\) respectively, to generate the augmented graph set \(\mathcal{D}=\{\mathcal{G}_{i}\|i=1,...,l\}\). Following this, 90% and 10% graphs are randomly select from \(\mathcal{D}\) as the training and validation set, respectively, and the observed graph \(\mathcal{G}_{o}\) is used as the test set.
#### 5.1.2 Comparison Methods

The proposed method was compared with six state-of-the-art deep learning-based link prediction methods, including:

(1) Weisfeiler-Lehman graph kernel (WLK) [42] is a fast feature extraction scheme based on the WL test for graph isomorphism, which maps the original graph to a graph sequence and adds the pair-wise similarities between the graphs.

(2) Weisfeiler-Lehman Neural Machine (WLNM) [56] is a subgraph classification-based link prediction method that leverage deep learning to automatically learn topological features from enclosing subgraphs.

(3) Node2Vec [20] is a network embedding method that encodes proximity information into low-dimensional vectors. The node features and low-dimensional vectors are then fed into the MLP for link prediction.

(4) LINE [44] learns network embeddings that preserve the first-order and second-order proximity, and the resulting low-dimensional vectors are used for link prediction.

(5) SEAL [57] extracts the enclosing subgraphs of positive and negative links and marks different roles of their nodes. The method then trains a GNN based on the node information matrix to classify subgraphs for link prediction.

(6) WalkPool (WP) [36] is a subgraph classification-based link prediction method. It encodes node feature and graph topology into the transition probabilities of random walk, and following this, a list of features is computed to classify subgraphs.

#### 5.1.3 Parameter Settings

GraphLP is implemented on a Pytorch platform with a NVIDIA GeForce RTX GPU and optimized using Adam optimizer. All models are implemented using Python 3.6. The learning rate is set to 0.0012 for the NS dataset and 0.0005 for the other graphs. For all the datasets, the weight decay is set to 0.0. The number of epochs on the E.coli and Yeast dataset is 300, whereas it was 200 on the other datasets. Dropout is applied to the MLP, and the dropout rate is set to 0.5 on Router and 0.2 on the others. The trade-off parameter \(\lambda\) is set to 0.13, and the number of neural network layers in the GraphLP is set to three. The detailed hyperparameter settings for the model are listed in Table 3.
\begin{table}
\begin{tabular}{c|c c c c c c c} \hline Data & USAir & NS & PB & Yeast & C.ele & Router & E.coli \\ \hline WLK & 96.82 \(\pm\) 0.84 & 98.79 \(\pm\) 0.40 & 93.34 \(\pm\) 0.89 & 96.82 \(\pm\) 0.35 & 88.96 \(\pm\) 2.06 & 86.59 \(\pm\) 2.23 & 97.25 \(\pm\) 0.42 \\ \hline WLNM & 95.95 \(\pm\) 1.13 & 98.81 \(\pm\) 0.49 & 92.69 \(\pm\) 0.64 & 96.40 \(\pm\) 0.38 & 85.08 \(\pm\) 2.05 & 93.53 \(\pm\) 1.09 & 97.50 \(\pm\) 0.23 \\ \hline Node2Vec & 89.71 \(\pm\) 2.97 & 94.28 \(\pm\) 0.91 & 84.79 \(\pm\) 1.03 & 94.90 \(\pm\) 0.38 & 83.12 \(\pm\) 1.90 & 68.66 \(\pm\) 1.49 & 90.87 \(\pm\) 1.48 \\ \hline LINE & 97.70 \(\pm\) 11.76 & 85.17 \(\pm\) 1.65 & 78.82 \(\pm\) 2.71 & 90.55 \(\pm\) 2.39 & 67.51 \(\pm\) 2.72 & 71.92 \(\pm\) 1.53 & 86.45 \(\pm\) 1.82 \\ \hline SEAL & 97.13 \(\pm\) 0.80 & 99.06 \(\pm\) 0.37 & 94.55 \(\pm\) 0.43 & 98.33 \(\pm\) 0.37 & 89.48 \(\pm\) 1.85 & 96.23 \(\pm\) 1.71 & 98.03 \(\pm\) 0.20 \\ \hline WP & 98.66 \(\pm\) 0.55 & **99.09 \(\pm\) 0.29** & 95.28 \(\pm\) 0.41 & 98.64 \(\pm\) 0.28 & 91.53 \(\pm\) 1.33 & **97.20 \(\pm\) 0.38** & 98.79 \(\pm\) 0.21 \\ \hline GraphLP & **99.91 \(\pm\) 1.03** & 98.94 \(\pm\) 0.96 & **98.32 \(\pm\) 1.43** & **98.74 \(\pm\) 0.16** & **99.41 \(\pm\) 0.42** & 79.30 \(\pm\) 0.19 & **98.96 \(\pm\) 0.19** \\ \hline \end{tabular}
\end{table}
Table 6: Prediction measured by AUC ( 50% observed links). **Bold** numbers are the best results of all methods.

\begin{table}
\begin{tabular}{c|c c c c c c c} \hline Data & USAir & NS & PB & Yeast & C.ele & Router & E.coli \\ \hline WLK & 93.34 \(\pm\) 0.51 & 89.97 \(\pm\) 1.02 & 92.34 \(\pm\) 0.34 & 93.55 \(\pm\) 0.46 & 83.20 \(\pm\) 0.90 & 75.49 \(\pm\) 3.43 & 94.51 \(\pm\) 0.32 \\ \hline WLNM & 92.54 \(\pm\) 0.81 & 90.10 \(\pm\) 1.11 & 91.01 \(\pm\) 0.20 & 93.93 \(\pm\) 0.20 & 76.12 \(\pm\) 1.08 & 86.12 \(\pm\) 0.68 & 94.47 \(\pm\) 0.21 \\ \hline Node2Vec & 82.51 \(\pm\) 2.08 & 86.01 \(\pm\) 0.87 & 77.21 \(\pm\) 0.97 & 92.45 \(\pm\) 0.23 & 72.91 \(\pm\) 1.74 & 66.77 \(\pm\) 0.57 & 85.41 \(\pm\) 0.94 \\ \hline LINE & 71.75 \(\pm\) 11.85 & 71.53 \(\pm\) 0.97 & 78.72 \(\pm\) 1.24 & 83.06 \(\pm\) 9.70 & 60.71 \(\pm\) 6.26 & 64.87 \(\pm\) 6.76 & 75.98 \(\pm\) 14.45 \\ \hline SEAL & 94.15 \(\pm\) 0.54 & 92.21 \(\pm\) 0.97 & 93.42 \(\pm\) 0.19 & 95.32 \(\pm\) 0.38 & 81.99 \(\pm\) 2.18 & 87.79 \(\pm\) 1.71 & 95.67 \(\pm\) 0.24 \\ \hline WP & 95.87 \(\pm\) 0.74 & 92.33 \(\pm\) 0.76 & 94.22 \(\pm\) 0.27 & 96.15 \(\pm\) 0.13 & 86.25 \(\pm\) 1.42 & **89.17 \(\pm\) 0.55** & 96.36 \(\pm\) 0.34 \\ \hline GraphLP & **97.96 \(\pm\) 0.09** & **93.08 \(\pm\) 0.08** & **96.27 \(\pm\) 0.10** & **97.27 \(\pm\) 0.09** & **95.89 \(\pm\) 0.11** & 79.23 \(\pm\) 0.14 & **96.48 \(\pm\) 0.13** \\ \hline \end{tabular}
\end{table}
Table 7: Prediction measured by AP ( 50% observed links). **Bold** numbers are the best results of all methods.

\begin{table}
\begin{tabular}{c|c c c c c c c c} \hline Data & USAir & NS & PB & Yeast & C.ele & Router & E.coli \\ \hline WLK & 96.63 \(\pm\) 0.73 & 98.57 \(\pm\) 0.51 & 93.83 \(\pm\) 0.59 & 95.86 \(\pm\) 0.54 & 89.72 \(\pm\) 1.67 & 87.42 \(\pm\) 2.08 & 96.94 \(\pm\) 0.29 \\ \hline WLNM & 95.95 \(\pm\) 1.10 & 98.61 \(\pm\) 0.49 & 93.49 \(\pm\) 0.47 & 95.62 \(\pm\) 0.52 & 86.18 \(\pm\) 1.72 & 94.41 \(\pm\) 0.88 & 97.21 \(\pm\) 0.27 \\ \hline Node2Vec & 91.44 \(\pm\) 1.78 & 91.52 \(\pm\) 1.28 & 85.79 \(\pm\) 0.78 & 93.67 \(\pm\) 0.46 & 84.11 \(\pm\) 1.27 & 65.46 \(\pm\) 0.86 & 90.82 \(\pm\) 1.49 \\ \hline LINE & 81.47 \(\pm\) 10.71 & 80.63 \(\pm\) 1.90 & 76.95 \(\pm\) 2.76 & 87.45 \(\pm\) 3.33 & 69.21 \(\pm\) 3.14 & 67.15 \(\pm\) 2.10 & 82.38 \(\pm\) 2.19 \\ \hline SEAL & 97.09 \(\pm\) 0.7 & 98.85 \(\pm\) 0.41 & 95.01 \(\pm\) 0.34 & 97.91 \(\pm\) 0.52 & 90.30 \(\pm\) 1.35 & 96.38 \(\pm\) 1.45 & 97.64 \(\pm\) 0.22 \\ \hline WP & 98.68 \(\pm\) 0.48 & 98.95 \(\pm\) 0.41 & 95.60 \(\pm\) 0.37 & 98.37 \(\pm\) 0.25 & 95.79 \(\pm\) 1.09 & 97.27 \(\pm\) 0.28 & 98.58 \(\pm\) 0.19 \\ \hline GraphLP & **99.26 \(\pm\) 1.01** & **99.64 \(\pm\) 0.98** & **99.73 \(\pm\) 0.25** & **99.41 \(\pm\) 0.15** & **99.90 \(\pm\) 0.14** & **99.02 \(\pm\) 0.19** & **99.23 \(\pm\) 0.23** \\ \hline \end{tabular}
\end{table}
Table 4: Prediction measured by AUC (90% observed links). **Bold** numbers are the best results of all methods.

\begin{table}
\begin{tabular}{c|c c c c c c c} \hline Data & USAir & NS & PB & Yeast & C.ele & Router & E.coli \\ \hline WLK & 96.82 \(\pm\) 0.84 & 98.79 \(\pm\) 0.40 & 93.34 \(\pm\) 0.89 & 96.82 \(\pm\
in the corresponding column indicates the highest accuracy. The results presented in Table 8 demonstrate that the proposed model GraphLP model performs the best among the methods. Furthermore, the link prediction accuracy of the proposed model is far higher than that of the other methods, which can be at least three times higher than that of the best-performing method. For spurious links prediction, the results measured by Precision are listed in Table 9. For all networks, GraphLP performs the best among the methods and is remarkably better than the second best algorithm. The results presented in Table 8 and 9 demonstrate that GraphLP has stronger ability to learn structural features, and can recover the structure of the original network more accurately. Based on Table 2, it can be observed that the Precision of our proposed model performs best, despite the large differences between the ACC and AD across all the datasets; thus indicates that the proposed model performs well for heterogeneous graph structures.

### Recovered Graph Visualization

To verify the effectiveness of the proposed model of missing and spurious links inference, the topology of the recovered graphs in the model training process on Club dataset is visually compared, as depicted in Figure 4 and 5. The top half depicts the topology of the graphs, wherein the red links denote the missing

Figure 4: The topology visualization of Club dataset. The experiment performs 10% link perturbation, i.e. 10% spurious links are added and 10% missing links are deleted.

Figure 5: The topology visualization of Club dataset. The experiment performs 20% link perturbation, i.e. 20% spurious links are added and 20% missing links are deleted.

\begin{table}
\begin{tabular}{c|c c c c c c c c} \hline Data & Macaque & Mangwet & Jazz & Metabolic & USAir & C.ele & E.coli & Yeast \\ \hline RA & 0.5490 & 0.1380 & 0.5410 & 0.140 & 0.2650 & 0.2790 & 0.4171 & 0.1110 \\ \hline CN & 0.5710 & 0.2880 & 0.5690 & 0.1670 & 0.2480 & 0.2458 & 0.3222 & 0.073 \\ \hline LP & 0.5939 & 0.3280 & 0.7016 & 0.6911 & 0.6271 & 0.4780 & 0.6089 & 0.4585 \\ \hline NMF & 0.8090 & 0.5660 & 0.6510 & 0.2430 & 0.4820 & 0.4333 & 0.4662 & 0.2330 \\ \hline RPCA & 0.810 & 0.5180 & 0.5920 & 0.074 & 0.443 & 0.2609 & 0.3795 & 0.4250 \\ \hline LFLP & 0.818 & 0.583 & 0.663 & 0.2210 & 0.5970 & 0.4390 & 0.4246 & 0.5680 \\ \hline GraphLP & **0.9073** & **0.8750** & **0.9197** & **0.8812** & **0.9057** & **0.9533** & **0.8452** & **0.6210** \\ \hline \end{tabular}
\end{table}
Table 9: The precision (90% observed links) of spurious links prediction. **Bold** numbers are the best results of all methods.
links, the blue links denote the spurious links, and the gray links denote the original links. The bottom half depicts the likelihood scores of missing and spurious links. Based on the results, it can be concluded that with an increase in epoch times, the likelihood scores of missing links increases gradually, and the likelihood scores of spurious links decline gradually. The widths of the lines indicate the following process: when the number of epochs reaches 100, the likelihood scores of missing links approach 1.0, and the likelihood scores of spurious links approach 0.0. This proves that the proposed GraphLP model can distinguish between missing links and spurious links and infer them effectively. Moreover, to further prove the effectiveness of the proposed model, the topology of the recovered graphs in the model training process is visualized when 20% of the links of Club are perturbed, as depicted in Figure 5. Compared to Figure 4, we determined that the likelihood of missing and spurious links is weakened with an increase in the structure perturbation ratio. However, with an increase in the training epochs, the model is still able to distinguish and infer the missing and spurious links according to the structural patterns. For instance, when the training epoch reaches 140, the likelihood scores of missing links are greater than 0.5, and those of spurious links

Figure 8: Visualization of model convergence. (a) Convergence of USAir dataset. (b) Convergence of C.ele dataset.

Figure 6: The performance of link prediction under various model depth. (a) AUC of link prediction method GraphLP with different layer number. (b) AP of link prediction method GraphLP with different layer number.

Figure 7: The performance of link prediction under different values of \(\lambda\). (a) AUC of link prediction method GraphLP under different values of \(\lambda\). (b) AP of link prediction method GraphLP under different values of \(\lambda\).
are less than 0.3, indicating that the proposed model can still predict missing and spurious links with high accuracy.

### Impact of Model Depth

Next, the performance of GraphLP is explored at various model depths. As depicted in Figure 6, the performance of the model in terms of the AUC and AP trained with one-layer neural network is poor; however, its performance improves significantly with an increase in the number of layers. In particular, when the model depth is equal to two, a significant performance improvement is noted. The primary reason for this is that the model with two-layers multi-order global and local structural features is integrated adaptively based on the MLP component, which considerably improves the performance of the model. Subsequently, as the layer number increases, a slight improvement in model performance is still noted. When the number of layers is four, the accuracy of GraphLP declines significantly on NS and fluctuates on other datasets. A possible reason for this is that the model with four layers becomes more complex, thereby requiring more training iterations or an appropriate learning rate [14]. In general, the performance of the proposed model is optimal when the depth is three, and a deep architecture is necessary.

### Impact of Trade-off Parameter

To examine the sensitivity of the proposed model to the trade-off parameter, the AUC and AP values of link prediction methods with different \(\lambda\) are presented in Figure 7. Based on the results, it can be concluded that the performance of the proposed model is not sensitive to \(\lambda\) for most datasets. In Figure 7(a), for the USAir and NS datsets, the AUC value varies significantly under different \(\lambda\), but the performance is still better than other of the other algorithms. In Figure 7(b), the AP value remains stable for different \(\lambda\) values, indicating that the proposed model is insensitive to different \(\lambda\). Overall, our proposed algorithm exhibited satisfactory performance on most datasets with various \(\lambda\).

### The Convergence Analysis

Generally, GraphLP converges to optimal values after approximately 200 epochs on most datasets. In particular, Figure 8 plots the learning curves of GraphLP on the USAir and C.ele datasets, including the training loss, validation AUC, validation AP, and validation loss. The results indicate that the AUC and AP values increase rapidly with the decrease in training loss and validation loss, and these values converge to the optimal value when the validation loss approaches a minimum value. Additionally, we discover that validation loss is lower than training loss, and the difference between them remains relatively stable. A possible reason for this is that the dropout manipulation is only applied to the training process.

## 6 Conclusion

This paper aims to reconstruct graph structure to improve the performance of link prediction. In particular, unlike existing subgraph-classification-based discriminative methods, this work achieves the aforementioned objective by developing a generative GNN, namely GraphLP, which considered both global and local structure features and hierarchical structural patterns. Concurrently, a novel collaborative inference operation and high-order connectivity computation mechanism are developed. We also present an analysis about the relation between GraphLP and other classical link prediction methods. Extensive experimental results demonstrate the superiority of the proposed method over other state-of-the-art models and traditional baseline methods. This could be a fruitful avenue for future research aimed at addressing graph learning tasks.

## Acknowledgment

This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 62106030, 61802039, 62272066; Chongqing Municipal Postdoctoral Science Foundation under Grant No. cstc2021jcyj-bsb0176; Chongqing Municipal Natural Science Foundation under Grant No. cstc2020jcyj-msxmX0804; the Chonging Research Program of Basic Research and Frontier Technology under Grant No. cstc2021jcyj-msxmX0530.
