A Topological Perspective on Demystifying GNN-Based Link Prediction Performance

• URL: http://arxiv.org/abs/2310.04612v1
• Date: Fri, 6 Oct 2023 22:07:49 GMT
• Title: A Topological Perspective on Demystifying GNN-Based Link Prediction Performance
• Authors: Yu Wang, Tong Zhao, Yuying Zhao, Yunchao Liu, Xueqi Cheng, Neil Shah, Tyler Derr
• Abstract summary: Topological Concentration (TC) is based on the intersection of the local subgraph of each node with the ones of its neighbors. We show that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density. We propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the complexity.
• Score: 72.06314265776683
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have shown great promise in learning node embeddings for link prediction (LP). While numerous studies aim to improve the overall LP performance of GNNs, none have explored its varying performance across different nodes and its underlying reasons. To this end, we aim to demystify which nodes will perform better from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit poorer LP performance, our empirical findings provide nuances to this viewpoint and prompt us to propose a better metric, Topological Concentration (TC), based on the intersection of the local subgraph of each node with the ones of its neighbors. We empirically demonstrate that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density, offering a better way to identify low-performing nodes than using cold-start. With TC, we discover a novel topological distribution shift issue in which newly joined neighbors of a node tend to become less interactive with that node's existing neighbors, compromising the generalizability of node embeddings for LP at testing time. To make the computation of TC scalable, We further propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the computation complexity. Given the positive correlation between node TC and its LP performance, we explore the potential of boosting LP performance via enhancing TC by re-weighting edges in the message-passing and discuss its effectiveness with limitations. Our code is publicly available at https://github.com/YuWVandy/Topo_LP_GNN.

Related papers

• Conditional Local Feature Encoding for Graph Neural Networks [14.983942698240293]
  Graph neural networks (GNNs) have shown great success in learning from graph-based data. The key mechanism of current GNNs is message passing, where a node's feature is updated based on the information passing from its local neighbourhood. We propose conditional local feature encoding (CLFE) to help prevent the problem of node features being dominated by information from local neighbourhood.
  arXiv  Detail & Related papers  (2024-05-08T01:51:19Z)
• Node Duplication Improves Cold-start Link Prediction [52.917775253887264]
  Graph Neural Networks (GNNs) are prominent in graph machine learning. Recent studies show that GNNs struggle to produce good results on low-degree nodes. We propose a simple yet surprisingly effective augmentation technique called NodeDup.
  arXiv  Detail & Related papers  (2024-02-15T05:07:39Z)
• How Expressive are Graph Neural Networks in Recommendation? [17.31401354442106]
  Graph Neural Networks (GNNs) have demonstrated superior performance on various graph learning tasks, including recommendation. Recent research has explored the expressiveness of GNNs in general, demonstrating that message passing GNNs are at most as powerful as the Weisfeiler-Lehman test. We propose the topological closeness metric to evaluate GNNs' ability to capture the structural distance between nodes.
  arXiv  Detail & Related papers  (2023-08-22T02:17:34Z)
• LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity [59.41119013018377]
  We propose to use the local similarity (LocalSim) to learn node-level weighted fusion, which can also serve as a plug-and-play module. For better fusion, we propose a novel and efficient Initial Residual Difference Connection (IRDC) to extract more informative multi-hop information. Our proposed method, namely Local Similarity Graph Neural Network (LSGNN), can offer comparable or superior state-of-the-art performance on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-07T09:06:11Z)
• When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability [92.8279562472538]
  Homophily principle has been believed to be the main reason for the performance superiority of Graph Networks (GNNs) over Neural Networks on node classification tasks. Recent research suggests that, even in the absence of homophily, the advantage of GNNs still exists as long as nodes from the same class share similar neighborhood patterns.
  arXiv  Detail & Related papers  (2023-04-25T09:40:47Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  We aim at improving the computational efficiency of graph convolutional networks (GCNs) for learning on point clouds. A series of experiments show that optimized networks have reduced computational complexity, decreased memory consumption, and accelerated inference speed.
  arXiv  Detail & Related papers  (2021-04-12T17:59:16Z)
• NCGNN: Node-level Capsule Graph Neural Network [45.23653314235767]
  Node-level Capsule Graph Neural Network (NCGNN) represents nodes as groups of capsules. novel dynamic routing procedure is developed to adaptively select appropriate capsules for aggregation. NCGNN can well address the over-smoothing issue and outperforms the state of the arts by producing better node embeddings for classification.
  arXiv  Detail & Related papers  (2020-12-07T06:46:17Z)

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.