Source-linked AI summary
Post-Pruning vs. Early Stopping: Which Works Better for Link Prediction with AnyBurl?
Thomas Eiter, Davide Soldà, Hai Xia
TL;DR
Rule-based link prediction can produce very large rule sets, burdening query answering, inspection, and LLM pipelines. This study compares pruning AnyBurl’s rules after generation with stopping rule generation earlier, and reports that support-based pruning can outperform early stopping when the target rule set is small.
Problem
Rule-based link prediction systems can generate very large rule sets, compromising query responsiveness, inspectability, and usability as input to LLM-based pipelines.
Source: §1 · pp. 1–2Method
The study prunes AnyBurl’s generated rules using support, confidence, PCA confidence, or relation-balanced support, and compares the results with the original rules and a similarly sized set from an earlier stopping time.
Source: §1 · p. 2Results
For a very small target rule set, support or balanced pruning can outperform AnyBurl’s simple earlier-stopping approach.
Source: §4 · p. 9Takeaways & Limitations
The preliminary study motivates exploring more sophisticated Horn-clause pruning and combining rule-quality measures such as PCA confidence with relevance measures such as support.
Source: §5 · p. 10Hetionet and Nations have far fewer test queries, so their results are treated as exploratory and excluded from across-benchmark statements.
Source: §4 · p. 8
Abstract
from arXiv · showhide
Rule-based link prediction combines symbolic and statistical artificial intelligence methods by inductively learning a set of rules from a knowledge graph (KG), with the aim of completing the graph when a query cannot be answered from the KG alone. Several systems have been proposed, and while they perform well on classical benchmarks, even compared with embedding-based systems, many of them produce a large number of rules. This compromises scalability in the query-answering phase, especially under strong hardware constraints. In this work, we investigate the behavior of AnyBurl, a state-of-the-art rule learner for link prediction, to determine whether running it for a given time and then pruning the learned rules yields better query-answering performance at test time than a simpler approach that stops rule generation earlier.
1 Introduction
Rule learners can generate millions of rules, burdening query answering, human inspection, and LLM pipelines. This work tests whether post-generation pruning AnyBurl’s rules performs better than stopping rule generation earlier.
1 Introduction
- Large rule sets compromise query responsiveness, inspectability, and usability as input to LLM-based pipelines.The introduction notes that rule learners can produce millions of rules, while an overloaded LLM context window can impair performance.Source: §1 · pp. 1–2
- Post-generation pruning selects among AnyBurl’s learned rules using support, confidence, PCA confidence, or relation-balanced support, and is compared with early stopping at a similar rule-set size.The study tests whether pruning after a longer run is more beneficial than shortening AnyBurl’s time budget.Source: §1 · p. 2
1.1 Related Works
- Earlier work applies the same metrics during mining to restrict the search space, where unrestricted exploration can be computationally infeasible and generate redundant rules.That work’s refinement operators are complete with respect to its chosen language bias.Source: §1.1 · p. 2
- Post-training rule pruning is presented as a symbolic counterpart to neural-network magnitude pruning, retaining a small fraction of interpretable rules while aiming to preserve predictive performance.The distinction is the unit being pruned: logical rules rather than weights.Source: §1.1 · p. 2
2 Background
The background defines link prediction as inferring missing knowledge-graph facts and describes its ranking-based evaluation. It then introduces rule-based link prediction systems, including AnyBurl and AMiE.
2.1 Link Prediction in Knowledge Graphs
- A knowledge graph is a set of subject-relation-object facts, and link prediction seeks to infer missing triplets by answering head or tail queries.Candidates are entities that complete a query triplet as a valid fact, even when it is absent from the graph.Source: §2.1 · pp. 2–3
- In filtered evaluation, other known correct answers are removed before ranking, and model quality is measured with MRR and Hits@k over head and tail queries.Hits@k rewards placing the correct entity within the cutoff; MRR is sensitive to its exact rank and favors answers near the top.Source: §2.1 · p. 3
2.2 ILP Systems for KG Link Prediction
- Rule-based link prediction inductively generates rules, matches their bodies against graph facts, and scores each answer using the highest score among rules that derive it.Rules require head variables to occur in the body, and derivation requires the body atoms to hold in the graph.Source: §2.2 · p. 4
- AnyBurl generates rules by generalizing paths from random walks, using reinforcement learning to allocate CPU across rule-type and path-length profiles.It uses an object identity assumption, and its rules include binary and unary forms; Uc rules are later pruned if they do not generalize on training data.Source: §2.2 · p. 5
- AMiE learns only closed rules, unlike AnyBurl’s Ud rule schema, and does not impose the path constraint followed by AnyBurl’s B, Uc, and Ud schemas.Its rule-generation operators extend rule bodies with new atoms using variables already present, new variables, or entity constants.Source: §2.2 · p. 6
- PCA confidence addresses standard confidence’s treatment of absent facts under the open-world assumption by counting counterexamples only when a subject-relation pair has an observed object.Under the partial completeness assumption, an observed object implies that all true objects for that subject and relation are assumed present.Source: §2.2 · pp. 6–7
3 Pruning Method
The method selects a specified fraction of AnyBurl rules using four criteria, including a relation-aware balanced selector that allocates the rule budget across head relations.
3 Pruning Method
- For retained fraction p, each selection criterion returns floor(p · |R|) rules from the Horn clauses produced by AnyBurl.The criteria use the training graph G_train.Source: §3 · p. 7
- The four criteria are support, confidence, balanced support, and PCA confidence, with the latter counted on the training graph.Support is estimated by AnyBurl; confidence is support divided by body support; balanced uses recounted exact support with a relation-split budget.Source: §3 · p. 7
- Balanced selection allocates rules independently by head relation, using validation-triple counts as D’Hondt votes and training support to fill each relation’s rule seats.Rules with different head relations serve disjoint query sets.Source: §3 · p. 7
4 Experimental Evaluation
The evaluation compares pruning AnyBurl’s rule set with early stopping and assesses selectors across link-prediction benchmarks. Support and balanced pruning can outperform early stopping for very small target sets, while PCA confidence has weaker ranking results.
4 Experimental Evaluation
- Hetionet and Nations are exploratory and excluded from cross-benchmark statements because their test sets are small; a single query shifts Hits@1 by 0.33 and 0.25 percentage points, respectively.They contain 151 and 201 test triples, respectively.Source: §4 · pp. 8–9
- In filtering rules produced by AnyBurl, support and its weighted version, balanced, are effective pruning metrics; retaining 10% of rules yields better performance than retaining only 1%.The reported results appear in Tables 3 and 4.Source: §4 · p. 8
- Most benchmark rule sets’ quality rises and then flattens before one hour, while Hetionet and Nations instead decline after an early peak.Figure 1 tracks four quality measures as AnyBurl’s runtime increases from one second to one hour on a logarithmic scale.Source: Figure 1 · p. 8, §4 · p. 9
- At very small target rule sets, support or balanced pruning can outperform AnyBurl’s early-stop snapshot; Table 3 compares equal-size sets at 0.1%, 0.25%, and 0.5%.Its Δ is MRRpruned − MRRearly stop, with positive values favoring pruning.Source: Table 3 · p. 9, §4 · p. 9
- PCA confidence does not score highly on MRR or Hits@1, Hits@3, and Hits@10 because it can favor rules that trigger only a handful of times.The authors distinguish rule quality when triggered from the rule’s relevance.Source: §4 · p. 9
- MRR@100 averages reciprocal ranks over the top 100 ranked elements, underestimates actual MRR, and is reported to differ negligibly.The authors use it to simplify MRR computation.Source: §4 · p. 9
5 Conclusions
The conclusion identifies several directions for further work: more sophisticated rule pruning, hybrid optimization, and applying pruning to temporal rule learners.
5 Conclusions
- Future pruning work could combine PCA confidence, which measures rule quality when triggered, with support as an indicator of a rule’s relevance to the knowledge graph.The authors characterize the work as preliminary.Source: §5 · p. 10
- The authors plan to investigate hybrid pruning and reranking that combine heuristics with MaxSAT and integer linear programming.Source: §5 · p. 10
- Post-processing pruning may also be explored for temporal rule learners, including TLogic, and for temporal forecasting and interpolation approaches.Forecasting uses only earlier timestamps; interpolation can use past and future information around the query timestamp.Source: §5 · p. 10