Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methods

• URL: http://arxiv.org/abs/2411.14711v1
• Date: Fri, 22 Nov 2024 03:38:20 GMT
• Title: Can GNNs Learn Link Heuristics? A Concise Review and Evaluation of Link Prediction Methods
• Authors: Shuming Liang, Yu Ding, Zhidong Li, Bin Liang, Siqi Zhang, Yang Wang, Fang Chen,
• Abstract summary: This paper explores the ability of Graph Neural Networks (GNNs) in learning various forms of information for link prediction. Our analysis reveals that GNNs cannot effectively learn structural information related to the number of common neighbors between two nodes. Also, our extensive experiments indicate that trainable node embeddings can improve the performance of GNN-based link prediction models.
• Score: 16.428742189544955
• License:
• Abstract: This paper explores the ability of Graph Neural Networks (GNNs) in learning various forms of information for link prediction, alongside a brief review of existing link prediction methods. Our analysis reveals that GNNs cannot effectively learn structural information related to the number of common neighbors between two nodes, primarily due to the nature of set-based pooling of the neighborhood aggregation scheme. Also, our extensive experiments indicate that trainable node embeddings can improve the performance of GNN-based link prediction models. Importantly, we observe that the denser the graph, the greater such the improvement. We attribute this to the characteristics of node embeddings, where the link state of each link sample could be encoded into the embeddings of nodes that are involved in the neighborhood aggregation of the two nodes in that link sample. In denser graphs, every node could have more opportunities to attend the neighborhood aggregation of other nodes and encode states of more link samples to its embedding, thus learning better node embeddings for link prediction. Lastly, we demonstrate that the insights gained from our research carry important implications in identifying the limitations of existing link prediction methods, which could guide the future development of more robust algorithms.

Related papers

• PROXI: Challenging the GNNs for Link Prediction [3.8233569758620063]
  We introduce PROXI, which leverages proximity information of node pairs in both graph and attribute spaces. Standard machine learning (ML) models perform competitively, even outperforming cutting-edge GNN models. We show that augmenting traditional GNNs with PROXI significantly boosts their link prediction performance.
  arXiv  Detail & Related papers  (2024-10-02T17:57:38Z)
• Learning Scalable Structural Representations for Link Prediction with Bloom Signatures [39.63963077346406]
  Graph neural networks (GNNs) are known to perform sub-optimally on link prediction tasks. We propose to learn structural link representations by augmenting the message-passing framework of GNNs with Bloom signatures. Our proposed model achieves comparable or better performance than existing edge-wise GNN models.
  arXiv  Detail & Related papers  (2023-12-28T02:21:40Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• Self-Explainable Graph Neural Networks for Link Prediction [30.41648521030615]
  Graph Neural Networks (GNNs) have achieved state-of-the-art performance for link prediction. GNNs suffer from poor interpretability, which limits their adoptions in critical scenarios. We propose a new framework and it can find various $K$ important neighbors of one node to learn pair-specific representations for links from this node to other nodes.
  arXiv  Detail & Related papers  (2023-05-21T21:57:32Z)
• Robust Knowledge Adaptation for Dynamic Graph Neural Networks [61.8505228728726]
  We propose Ada-DyGNN: a robust knowledge Adaptation framework via reinforcement learning for Dynamic Graph Neural Networks. Our approach constitutes the first attempt to explore robust knowledge adaptation via reinforcement learning. Experiments on three benchmark datasets demonstrate that Ada-DyGNN achieves the state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-07-22T02:06:53Z)
• Structure Enhanced Graph Neural Networks for Link Prediction [6.872826041648584]
  We propose Structure Enhanced Graph neural network (SEG) for link prediction. SEG incorporates surrounding topological information of target nodes into an ordinary GNN model. Experiments on the OGB link prediction datasets demonstrate that SEG achieves state-of-the-art results.
  arXiv  Detail & Related papers  (2022-01-14T03:49:30Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• Interpretable Signed Link Prediction with Signed Infomax Hyperbolic Graph [54.03786611989613]
  signed link prediction in social networks aims to reveal the underlying relationships (i.e. links) among users (i.e. nodes) We develop a unified framework, termed as Signed Infomax Hyperbolic Graph (textbfSIHG) In order to model high-order user relations and complex hierarchies, the node embeddings are projected and measured in a hyperbolic space with a lower distortion.
  arXiv  Detail & Related papers  (2020-11-25T05:09:03Z)
• Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction [69.1473775184952]
  We introduce a realistic problem of few-shot out-of-graph link prediction. We tackle this problem with a novel transductive meta-learning framework. We validate our model on multiple benchmark datasets for knowledge graph completion and drug-drug interaction prediction.
  arXiv  Detail & Related papers  (2020-06-11T17:42:46Z)
• Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
  Graph Neural Network (GNN) is a powerful model to learn representations and make predictions on graph data. We propose a new graph convolution operator, which augments the weighted sum with pairwise interactions of the representations of neighbor nodes. We term this framework as Bilinear Graph Neural Network (BGNN), which improves GNN representation ability with bilinear interactions between neighbor nodes.
  arXiv  Detail & Related papers  (2020-02-10T06:43:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.