Edge Proposal Sets for Link Prediction

• URL: http://arxiv.org/abs/2106.15810v1
• Date: Wed, 30 Jun 2021 04:59:19 GMT
• Title: Edge Proposal Sets for Link Prediction
• Authors: Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, Austin R. Benson
• Abstract summary: Link prediction aims to predict future edges or infer missing edges in the graph, and has diverse applications in recommender systems, experimental design, and complex systems. Here, we demonstrate how simply adding a set of edges, which we call a emphproposal set, to the graph as a pre-processing step can improve the performance of several link prediction algorithms.
• Score: 39.33358136412426
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graphs are a common model for complex relational data such as social networks and protein interactions, and such data can evolve over time (e.g., new friendships) and be noisy (e.g., unmeasured interactions). Link prediction aims to predict future edges or infer missing edges in the graph, and has diverse applications in recommender systems, experimental design, and complex systems. Even though link prediction algorithms strongly depend on the set of edges in the graph, existing approaches typically do not modify the graph topology to improve performance. Here, we demonstrate how simply adding a set of edges, which we call a \emph{proposal set}, to the graph as a pre-processing step can improve the performance of several link prediction algorithms. The underlying idea is that if the edges in the proposal set generally align with the structure of the graph, link prediction algorithms are further guided towards predicting the right edges; in other words, adding a proposal set of edges is a signal-boosting pre-processing step. We show how to use existing link prediction algorithms to generate effective proposal sets and evaluate this approach on various synthetic and empirical datasets. We find that proposal sets meaningfully improve the accuracy of link prediction algorithms based on both neighborhood heuristics and graph neural networks. Code is available at \url{https://github.com/CUAI/Edge-Proposal-Sets}.

Related papers

• PULL: PU-Learning-based Accurate Link Prediction [12.8532740199204]
  Given an edge-incomplete graph, how can we accurately find the missing links? We propose PULL (PU-Learning-based Link predictor), an accurate link prediction method based on the positive-unlabeled (PU) learning. PULL consistently outperforms the baselines for predicting links in edge-incomplete graphs.
  arXiv  Detail & Related papers  (2024-05-20T09:47:22Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  We propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction. Design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps. We achieve promoted efficiency and leading performances on five large-scale benchmarks.
  arXiv  Detail & Related papers  (2024-03-15T12:00:12Z)
• 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)
• FakeEdge: Alleviate Dataset Shift in Link Prediction [16.161812856581676]
  In a link prediction task, links in the training set are always present while ones in the testing set are not yet formed, resulting in a discrepancy of the connectivity pattern and bias of the learned representation. We propose FakeEdge, a model-agnostic technique, to address the problem by mitigating the graph topological gap between training and testing sets.
  arXiv  Detail & Related papers  (2022-11-29T03:36:01Z)
• Line Graph Contrastive Learning for Link Prediction [4.876567687745239]
  We propose a Line Graph Contrastive Learning (LGCL) method to obtain multiview information. With experiments on six public datasets, LGCL outperforms current benchmarks on link prediction tasks.
  arXiv  Detail & Related papers  (2022-10-25T06:57:00Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Explaining GNN over Evolving Graphs using Information Flow [12.33508497537769]
  Graph neural networks (GNN) are the current state-of-the-art for these applications, and yet remain obscure to humans. We propose an axiomatic attribution method to uniquely decompose the change in a prediction to paths on computation graphs. We formulate a novel convex optimization problem to optimally select the paths that explain the prediction evolution.
  arXiv  Detail & Related papers  (2021-11-19T04:29:38Z)
• Simple Graph Convolutional Networks [72.92604941595019]
  We propose simple graph convolution operators, that can be implemented in single-layer graph convolutional networks. We show that our convolution operators are more theoretically grounded than many proposals in literature, and exhibit state-of-the-art predictive performance on the considered benchmark datasets.
  arXiv  Detail & Related papers  (2021-06-10T15:23:59Z)
• 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)
• ALPINE: Active Link Prediction using Network Embedding [20.976178936255927]
  We propose ALPINE (Active Link Prediction usIng Network Embedding) for link prediction based on network embedding. We show that ALPINE is scalable, and boosts link prediction accuracy with far fewer queries.
  arXiv  Detail & Related papers  (2020-02-04T11:09:03Z)

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.