Attribute-Enhanced Similarity Ranking for Sparse Link Prediction

• URL: http://arxiv.org/abs/2412.00261v1
• Date: Fri, 29 Nov 2024 21:22:35 GMT
• Title: Attribute-Enhanced Similarity Ranking for Sparse Link Prediction
• Authors: João Mattos, Zexi Huang, Mert Kosan, Ambuj Singh, Arlei Silva,
• Abstract summary: Graph Neural Networks (GNNs) have become the predominant framework for link prediction. We show that the reported performance of GNNs for link prediction in the balanced setting does not translate to the more realistic imbalanced setting. Experiments show that Gelato, a similarity-based link-prediction method, outperforms existing GNN-based alternatives.
• Score: 6.774952925054741
• License:
• Abstract: Link prediction is a fundamental problem in graph data. In its most realistic setting, the problem consists of predicting missing or future links between random pairs of nodes from the set of disconnected pairs. Graph Neural Networks (GNNs) have become the predominant framework for link prediction. GNN-based methods treat link prediction as a binary classification problem and handle the extreme class imbalance -- real graphs are very sparse -- by sampling (uniformly at random) a balanced number of disconnected pairs not only for training but also for evaluation. However, we show that the reported performance of GNNs for link prediction in the balanced setting does not translate to the more realistic imbalanced setting and that simpler topology-based approaches are often better at handling sparsity. These findings motivate Gelato, a similarity-based link-prediction method that applies (1) graph learning based on node attributes to enhance a topological heuristic, (2) a ranking loss for addressing class imbalance, and (3) a negative sampling scheme that efficiently selects hard training pairs via graph partitioning. Experiments show that Gelato outperforms existing GNN-based alternatives.

Related papers

• RoCP-GNN: Robust Conformal Prediction for Graph Neural Networks in Node-Classification [0.0]
  Graph Neural Networks (GNNs) have emerged as powerful tools for predicting outcomes in graph-structured data. One way to address this issue is by providing prediction sets that contain the true label with a predefined probability margin. We propose a novel approach termed Robust Conformal Prediction for GNNs (RoCP-GNN) Our approach robustly predicts outcomes with any predictive GNN model while quantifying the uncertainty in predictions within the realm of graph-based semi-supervised learning (SSL)
  arXiv  Detail & Related papers  (2024-08-25T12:51:19Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. We propose a novel GNN architecture whereby the emphforward pass explicitly depends on emphboth positive (as is typical) and negative (unique to our approach) edges. This is achieved by recasting the embeddings themselves as minimizers of a forward-pass-specific energy function that favors separation of positive and negative samples.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• Heterophily-Based Graph Neural Network for Imbalanced Classification [19.51668009720269]
  We introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We propose Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs. Our experiments on real-world graphs demonstrate our model's superiority in classification performance and efficiency for node classification tasks.
  arXiv  Detail & Related papers  (2023-10-12T21:19:47Z)
• Link Prediction without Graph Neural Networks [7.436429318051601]
  Link prediction is a fundamental task in many graph applications. Graph Neural Networks (GNNs) have become the predominant framework for link prediction. We propose Gelato, a novel framework that applies a topological-centric framework to a graph enhanced by attribute information via graph learning.
  arXiv  Detail & Related papers  (2023-05-23T03:59:21Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)
• Neural Link Prediction with Walk Pooling [31.12613408446031]
  We propose a link prediction based on a new pooling scheme called WalkPool. It combines the expressivity of topological algorithms with the feature-learning ability of neural networks. It outperforms state-of-the-art methods on all common link prediction benchmarks.
  arXiv  Detail & Related papers  (2021-10-08T20:52:12Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)

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.