Efficient Link Prediction via GNN Layers Induced by Negative Sampling

• URL: http://arxiv.org/abs/2310.09516v2
• Date: Mon, 30 Dec 2024 13:53:16 GMT
• Title: Efficient Link Prediction via GNN Layers Induced by Negative Sampling
• Authors: Yuxin Wang, Xiannian Hu, Quan Gan, Xuanjing Huang, Xipeng Qiu, David Wipf,
• Abstract summary: 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.
• Score: 86.87385758192566
• License:
• Abstract: Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories. First, \emph{node-wise} architectures pre-compute individual embeddings for each node that are later combined by a simple decoder to make predictions. While extremely efficient at inference time, model expressiveness is limited such that isomorphic nodes contributing to candidate edges may not be distinguishable, compromising accuracy. In contrast, \emph{edge-wise} methods rely on the formation of edge-specific subgraph embeddings to enrich the representation of pair-wise relationships, disambiguating isomorphic nodes to improve accuracy, but with increased model complexity. To better navigate this trade-off, we propose a novel GNN architecture whereby the \emph{forward pass} explicitly depends on \emph{both} positive (as is typical) and negative (unique to our approach) edges to inform more flexible, yet still cheap node-wise embeddings. 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. Notably, this energy is distinct from the actual training loss shared by most existing link prediction models, where contrastive pairs only influence the \textit{backward pass}. As demonstrated by extensive empirical evaluations, the resulting architecture retains the inference speed of node-wise models, while producing competitive accuracy with edge-wise alternatives. We released our code at https://github.com/yxzwang/SubmissionverOfYinYanGNN.

Related papers

• 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)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• 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)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)
• Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection [57.34881616131377]
  We introduce a Personalized Subgraph Selector (PS2) as a plug-and-play framework to automatically, personally, and inductively identify optimal subgraphs for different edges. PS2 is instantiated as a bi-level optimization problem that can be efficiently solved differently. We suggest a brand-new angle towards GNNLP training: by first identifying the optimal subgraphs for edges; and then focusing on training the inference model by using the sampled subgraphs.
  arXiv  Detail & Related papers  (2022-12-23T17:30:19Z)
• Adversarial Permutation Guided Node Representations for Link Prediction [27.31800918961859]
  Link prediction (LP) algorithm identifies node pairs between which new edges will likely materialize in future. Most LP algorithms estimate a score for currently non-neighboring node pairs, and rank them by this score. We propose PermGNN, which aggregates neighbor features using a recurrent, order-sensitive aggregator and directly minimizes an LP loss while it is attacked' by adversarial generator of neighbor permutations.
  arXiv  Detail & Related papers  (2020-12-13T03:52:25Z)
• Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking [63.49779304362376]
  Graph neural networks (GNNs) have become a popular approach to integrating structural inductive biases into NLP models. We introduce a post-hoc method for interpreting the predictions of GNNs which identifies unnecessary edges. We show that we can drop a large proportion of edges without deteriorating the performance of the model.
  arXiv  Detail & Related papers  (2020-10-01T17:51:19Z)
• Learning Node Representations against Perturbations [21.66982904572156]
  Recent graph neural networks (GNN) has achieved remarkable performance in node representation learning. We study how to learn node representations against perturbations in GNN. We propose Stability-Identifiability GNN Against Perturbations (SIGNNAP) that learns reliable node representations in an unsupervised manner.
  arXiv  Detail & Related papers  (2020-08-26T07:11:01Z)
• PushNet: Efficient and Adaptive Neural Message Passing [1.9121961872220468]
  Message passing neural networks have recently evolved into a state-of-the-art approach to representation learning on graphs. Existing methods perform synchronous message passing along all edges in multiple subsequent rounds. We consider a novel asynchronous message passing approach where information is pushed only along the most relevant edges until convergence.
  arXiv  Detail & Related papers  (2020-03-04T18:15:30Z)

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.