SAFRAN: An interpretable, rule-based link prediction method outperforming embedding models

• URL: http://arxiv.org/abs/2109.08002v1
• Date: Thu, 16 Sep 2021 14:18:29 GMT
• Title: SAFRAN: An interpretable, rule-based link prediction method outperforming embedding models
• Authors: Simon Ott, Christian Meilicke, Matthias Samwald
• Abstract summary: We introduce SAFRAN, which uses a novel aggregation approach called Non-redundant Noisy-OR that detects and clusters redundant rules prior to aggregation. SAFRAN yields new state-of-the-art results for fully interpretable link prediction on the established general-purpose benchmarks FB15K-237, WN18RR and YAGO3-10. It exceeds the results of multiple established embedding-based algorithms on FB15K-237 and WN18RR and narrows the gap between rule-based and embedding-based algorithms on YAGO3-10.
• Score: 5.52834593453565
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Neural embedding-based machine learning models have shown promise for predicting novel links in knowledge graphs. Unfortunately, their practical utility is diminished by their lack of interpretability. Recently, the fully interpretable, rule-based algorithm AnyBURL yielded highly competitive results on many general-purpose link prediction benchmarks. However, current approaches for aggregating predictions made by multiple rules are affected by redundancies. We improve upon AnyBURL by introducing the SAFRAN rule application framework, which uses a novel aggregation approach called Non-redundant Noisy-OR that detects and clusters redundant rules prior to aggregation. SAFRAN yields new state-of-the-art results for fully interpretable link prediction on the established general-purpose benchmarks FB15K-237, WN18RR and YAGO3-10. Furthermore, it exceeds the results of multiple established embedding-based algorithms on FB15K-237 and WN18RR and narrows the gap between rule-based and embedding-based algorithms on YAGO3-10.

Related papers

• PageRank Bandits for Link Prediction [72.61386754332776]
  Link prediction is a critical problem in graph learning with broad applications such as recommender systems and knowledge graph completion. This paper reformulates link prediction as a sequential decision-making process, where each link prediction interaction occurs sequentially. We propose a novel fusion algorithm, PRB (PageRank Bandits), which is the first to combine contextual bandits with PageRank for collaborative exploitation and exploration.
  arXiv  Detail & Related papers  (2024-11-03T02:39:28Z)
• Conformalized Link Prediction on Graph Neural Networks [8.807684750444626]
  Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications in high-stakes domains are often hampered by unreliable predictions. We introduce a distribution-free and model-agnostic uncertainty quantification approach to construct a predictive interval with a statistical guarantee for GNN-based link prediction.
  arXiv  Detail & Related papers  (2024-06-26T21:17:37Z)
• MANO: Exploiting Matrix Norm for Unsupervised Accuracy Estimation Under Distribution Shifts [25.643876327918544]
  Leveraging the models' outputs, specifically the logits, is a common approach to estimating the test accuracy of a pre-trained neural network on out-of-distribution samples. Despite their ease of implementation and computational efficiency, current logit-based methods are vulnerable to overconfidence issues, leading to prediction bias. We propose MaNo which applies a data-dependent normalization on the logits to reduce prediction bias and takes the $L_p$ norm of the matrix of normalized logits as the estimation score.
  arXiv  Detail & Related papers  (2024-05-29T10:45:06Z)
• Forest-ORE: Mining Optimal Rule Ensemble to interpret Random Forest models [0.0]
  We present Forest-ORE, a method that makes Random Forest (RF) interpretable via an optimized rule ensemble (ORE) for local and global interpretation. A comparative analysis of well-known methods shows that Forest-ORE provides an excellent trade-off between predictive performance, interpretability coverage, and model size.
  arXiv  Detail & Related papers  (2024-03-26T10:54:07Z)
• IBP Regularization for Verified Adversarial Robustness via Branch-and-Bound [85.6899802468343]
  We present IBP-R, a novel verified training algorithm that is both simple effective. We also present UPB, a novel robustness based on $beta$-CROWN, that reduces the cost state-of-the-art branching algorithms.
  arXiv  Detail & Related papers  (2022-06-29T17:13:25Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization [52.7137956951533]
  We argue that devising simpler methods for learning predictors on existing features is a promising direction for future research. We introduce Domain-Adjusted Regression (DARE), a convex objective for learning a linear predictor that is provably robust under a new model of distribution shift. Under a natural model, we prove that the DARE solution is the minimax-optimal predictor for a constrained set of test distributions.
  arXiv  Detail & Related papers  (2022-02-14T16:42:16Z)
• Better Short than Greedy: Interpretable Models through Optimal Rule Boosting [10.938624307941197]
  Rule ensembles are designed to provide a useful trade-off between predictive accuracy and model interpretability. We present a novel approach aiming to fit rule ensembles of maximal predictive power for a given ensemble size.
  arXiv  Detail & Related papers  (2021-01-21T01:03:48Z)
• Scalable and interpretable rule-based link prediction for large heterogeneous knowledge graphs [4.502717871564512]
  We introduce the SAFRAN rule application framework which aggregates rules through a scalable clustering algorithm. SAFRAN yields new state-of-the-art results for fully interpretable link prediction on the established general-purpose benchmark FB15K-237. It exceeds the results of multiple established embedding-based algorithms on FB15K-237 and narrows the gap between rule-based and embedding-based algorithms on OpenBioLink.
  arXiv  Detail & Related papers  (2020-12-10T15:36:47Z)
• CASTLE: Regularization via Auxiliary Causal Graph Discovery [89.74800176981842]
  We introduce Causal Structure Learning (CASTLE) regularization and propose to regularize a neural network by jointly learning the causal relationships between variables. CASTLE efficiently reconstructs only the features in the causal DAG that have a causal neighbor, whereas reconstruction-based regularizers suboptimally reconstruct all input features.
  arXiv  Detail & Related papers  (2020-09-28T09:49:38Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59: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.