Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors

• URL: http://arxiv.org/abs/2402.00053v1
• Date: Thu, 25 Jan 2024 15:44:46 GMT
• Title: Are We Wasting Time? A Fast, Accurate Performance Evaluation Framework for Knowledge Graph Link Predictors
• Authors: Filip Cornell, Yifei Jin, Jussi Karlgren, Sarunas Girdzijauskas
• Abstract summary: In Knowledge Graphs on a larger scale, the ranking process rapidly becomes heavy. Previous approaches used random sampling of entities to assess the quality of links predicted or suggested by a method. We show that this approach has serious limitations since the ranking metrics produced do not properly reflect true outcomes. We propose a framework that uses relational recommenders to guide the selection of candidates for evaluation.
• Score: 4.31947784387967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The standard evaluation protocol for measuring the quality of Knowledge Graph Completion methods - the task of inferring new links to be added to a graph - typically involves a step which ranks every entity of a Knowledge Graph to assess their fit as a head or tail of a candidate link to be added. In Knowledge Graphs on a larger scale, this task rapidly becomes prohibitively heavy. Previous approaches mitigate this problem by using random sampling of entities to assess the quality of links predicted or suggested by a method. However, we show that this approach has serious limitations since the ranking metrics produced do not properly reflect true outcomes. In this paper, we present a thorough analysis of these effects along with the following findings. First, we empirically find and theoretically motivate why sampling uniformly at random vastly overestimates the ranking performance of a method. We show that this can be attributed to the effect of easy versus hard negative candidates. Second, we propose a framework that uses relational recommenders to guide the selection of candidates for evaluation. We provide both theoretical and empirical justification of our methodology, and find that simple and fast methods can work extremely well, and that they match advanced neural approaches. Even when a large portion of true candidates for a property are missed, the estimation barely deteriorates. With our proposed framework, we can reduce the time and computation needed similar to random sampling strategies while vastly improving the estimation; on ogbl-wikikg2, we show that accurate estimations of the full, filtered ranking can be obtained in 20 seconds instead of 30 minutes. We conclude that considerable computational effort can be saved by effective preprocessing and sampling methods and still reliably predict performance accurately of the true performance for the entire ranking procedure.

Related papers

• Graspness Discovery in Clutters for Fast and Accurate Grasp Detection [57.81325062171676]
  "graspness" is a quality based on geometry cues that distinguishes graspable areas in cluttered scenes. We develop a neural network named cascaded graspness model to approximate the searching process. Experiments on a large-scale benchmark, GraspNet-1Billion, show that our method outperforms previous arts by a large margin.
  arXiv  Detail & Related papers  (2024-06-17T02:06:47Z)
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms [14.82820088479196]
  Dynamic Link Prediction (DLP) addresses the prediction of future links in evolving networks. In this work, we contribute tools to perform such a comprehensive evaluation. We describe an exhaustive taxonomy of negative sampling methods that can be used at evaluation time.
  arXiv  Detail & Related papers  (2024-05-27T14:03:28Z)
• 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)
• Modeling of learning curves with applications to pos tagging [0.27624021966289597]
  We introduce an algorithm to estimate the evolution of learning curves on the whole of a training data base. We approximate iteratively the sought value at the desired time, independently of the learning technique used. The proposal proves to be formally correct with respect to our working hypotheses and includes a reliable proximity condition.
  arXiv  Detail & Related papers  (2024-02-04T15:00:52Z)
• Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking [66.83273589348758]
  Link prediction attempts to predict whether an unseen edge exists based on only a portion of edges of a graph. A flurry of methods have been introduced in recent years that attempt to make use of graph neural networks (GNNs) for this task. New and diverse datasets have also been created to better evaluate the effectiveness of these new models.
  arXiv  Detail & Related papers  (2023-06-18T01:58:59Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  Active learning frameworks aim to reduce the cost of data annotation by actively requesting the labeling for the most informative data points. Some proposed approaches include uncertainty-based techniques, geometric methods, implicit combination of uncertainty-based and geometric approaches. We present an innovative integration of recent progress in both uncertainty-based and geometric frameworks to enable an efficient exploration/exploitation trade-off in sample selection strategy. Our framework provides two advantages: (1) accurate posterior estimation, and (2) tune-able trade-off between computational overhead and higher accuracy.
  arXiv  Detail & Related papers  (2022-10-11T20:20:20Z)
• Topology-Guided Sampling for Fast and Accurate Community Detection [1.0609815608017064]
  We present an approach based on topology-guided sampling for accelerating block partitioning. We also introduce a degree-based thresholding scheme that improves the efficacy of our approach at the expense of speedup. Our results show that our approach can lead to a speedup of up to 15X over block partitioning without sampling.
  arXiv  Detail & Related papers  (2021-08-15T03:20:10Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise. First-order guarantees are relatively well understood in statistical and online learning. We show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees.
  arXiv  Detail & Related papers  (2021-07-05T19:20:34Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• SIMPLE: SIngle-network with Mimicking and Point Learning for Bottom-up Human Pose Estimation [81.03485688525133]
  We propose a novel multi-person pose estimation framework, SIngle-network with Mimicking and Point Learning for Bottom-up Human Pose Estimation (SIMPLE) Specifically, in the training process, we enable SIMPLE to mimic the pose knowledge from the high-performance top-down pipeline. Besides, SIMPLE formulates human detection and pose estimation as a unified point learning framework to complement each other in single-network.
  arXiv  Detail & Related papers  (2021-04-06T13:12:51Z)

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.