PaperlayerView exact revision on arXiv

Source-linked AI summary

Discriminative Predicate Path Mining for Fact Checking in Knowledge Graphs

Baoxu Shi, Tim Weninger

arXiv:1510.05911v2cs.DBcs.AIcs.IRcs.SI

TL;DR

Fact checking needs scalable ways to distinguish true from false statements in incomplete, heterogeneous knowledge graphs. The paper mines discriminative paths that capture connectivity, type information, and predicate interactions, then uses them to evaluate claims; experiments report strong performance and interpretable explanations.

  • Problem

    Fact checking requires scalable computational assessment because misinformation and incomplete knowledge graphs make reliable validation difficult.

  • Method

    The method mines discriminative paths that generalize subject-object types, capture predicate context, and support link-prediction-based fact checking.

  • Results

    The framework was the all around best in fact-checking performance across 8 tasks on DBpedia and SemMedDB, with running time similar to existing models.

  • Takeaways & Limitations

    The framework produces interpretable and informative discriminative paths that can provide reasons for fact-checking determinations.

Abstract

from arXiv · show

Traditional fact checking by experts and analysts cannot keep pace with the volume of newly created information. It is important and necessary, therefore, to enhance our ability to computationally determine whether some statement of fact is true or false. We view this problem as a link-prediction task in a knowledge graph, and present a discriminative path-based method for fact checking in knowledge graphs that incorporates connectivity, type information, and predicate interactions. Given a statement S of the form (subject, predicate, object), for example, (Chicago, capitalOf, Illinois), our approach mines discriminative paths that alternatively define the generalized statement (U.S. city, predicate, U.S. state) and uses the mined rules to evaluate the veracity of statement S. We evaluate our approach by examining thousands of claims related to history, geography, biology, and politics using a public, million node knowledge graph extracted from Wikipedia and PubMedDB. Not only does our approach significantly outperform related models, we also find that the discriminative predicate path model is easily interpretable and provides sensible reasons for the final determination.

I. INTRODUCTION

The paper frames automated fact checking as necessary for separating true from false claims in increasingly unreliable information environments. It proposes interpretable discriminative paths that capture context-dependent predicate meanings and uses them to validate factual statements in large knowledge graphs.

  • Misinformation and unreliable web information motivate computational methods for assessing factual claims and source credibility.
  • The proposed method mines discriminative paths that incorporate connectivity, entity types, and predicate interactions to define generalized statements and evaluate specific claims.
  • The framework aims to generalize beyond known predicate types, adapt definitions to context, and support interpretable fact checking.
  • Existing association-mining and link-prediction methods often rely on global rules, synonyms, or topology that poorly capture context-dependent predicates in heterogeneous knowledge graphs.
  • The authors report superior performance to alternative approaches, similar execution time, and informative reasons for its determinations across DBpedia and SemMedDB.

II. PROBLEM DEFINITION

The paper formalizes knowledge graphs as typed directed multigraphs and fact checking as supervised link prediction. Because topology alone cannot reliably distinguish true from false edges, it selects discriminative typed paths that characterize predicate-specific relationships.

  • A knowledge graph is a directed multigraph whose entities have ontology labels and whose edges have predicate types.
  • Meta paths encode typed sequences of vertices and predicates, while anchored predicate paths retain typed endpoints and predicate-labeled edges.
  • Fact checking uses a learned relationship definition to determine whether a proposed subject-predicate-object edge is implied by the graph.
  • Traditional topology-only methods perform poorly because network structure does not sufficiently distinguish true and false candidate edges.
  • The model automatically discovers paths that test both type generality and context dependence, selecting those that uniquely define the predicate.

III. DISCRIMINATIVE PATH ANALYSIS

Discriminative path analysis extracts typed endpoint paths, selects those that distinguish predicate-linked pairs from comparable unlinked pairs, and validates statements with a model built from the selected paths.

  • Discriminative paths represent a predicate between entities whose endpoint types match those of the proposed statement.
  • The extraction phase collects anchored predicate paths connecting a statement’s subject and object, while selection retains the most discriminating paths.
  • The validation phase compares the actual statement connection with a statistical model constructed from the selected discriminative paths.

A. Path Extraction

The method extracts anchored predicate paths by constrained traversal between type-compatible subject and object entities, then assesses their usefulness for fact checking.

  • Path selection: The procedure retains only a small subset of helpful paths because most graph paths are irrelevant or nondiscriminative for a given predicate.Extracted paths are later ranked for inclusion in a regression model.
  • Path extraction: The algorithm traverses from a proposed statement’s subject to object, collecting anchored predicate paths up to length k instead of enumerating all graph paths.It focuses on paths connecting entities of the relevant endpoint types.
  • Path extraction: Positive and negative anchor pairs provide predicate-path sets whose contrasting paths can discriminate the predicate of interest.These paths serve as alternate descriptions of the original predicate.
  • Traversal: Depth-first traversal uses a closure function to follow a predicate or its inverse and a transition function to generate unvisited next nodes.The implementation records both edge directions when possible.

B. Meta Path versus Predicate Path

The paper uses anchored predicate paths rather than more tightly specified meta paths because noisy or inconsistent entity types can reduce discriminative power without improving performance.

  • Predicate paths: Anchored predicate paths are used as features because entity types may be redundant or inconsistently assigned in complex knowledge graphs.Multiple type labels can make otherwise related paths appear different.
  • Meta paths: Jaccard similarity between entity-label sets is used to reduce redundant meta paths when endpoint types are sufficiently similar.The method relaxes type matching for non-endpoint entities while retaining stricter endpoint matching.
  • Empirical comparison: Meta paths increased the number of model variables without noticeable performance improvement and reduced important-path occurrence through noisy entity types.These effects lowered the discriminative power of the resulting path set.
  • Predicate paths: The extracted positive and negative predicate paths provide alternate descriptions used as evidence to define the original predicate.Their usefulness is assessed in the fact-checking model.

C. Path Selection

Path selection converts anchored-path counts into a reduced feature matrix by retaining paths with the greatest ability to distinguish positive from negative predicate instances.

  • Feature representation: The training matrix X records anchored-path counts for subject–object pairs, with labels indicating whether each pair has the predicate of interest.Feature selection produces a reduced matrix X′ containing m′ selected paths.
  • Feature selection: The feature-selection function uses a path-importance vector w and threshold δ to retain only sufficiently important path features.The selected paths are those with the greatest discriminative power.
  • Feature selection: Path importance is measured by the information gain between each path-count feature and the corresponding class labels.The feature matrix columns and label vector provide the inputs to this measurement.
  • Fact checking: A standard logistic regression model uses the pruned discriminative-path representation to validate the original fact statement.The model is trained after path extraction and feature pruning.

D. Fact Interpretation

The framework ranks discriminative paths to isolate predicate-defining patterns, while acknowledging that some accurate paths may support fact checking without clearly defining the predicate.

  • Interpretation: Table I lists the top discriminative paths for capitalOf in descending importance order.The listed paths include location, deathPlace, and headquarter relations with endpoint type labels.
  • Interpretation: Some extracted paths are spurious as definitions: they may be accurate for an instance yet weakly describe what the predicate means.Examples include location−1, location and deathPlace−1, deathPlace paths.
  • Interpretation: Supportive but non-defining paths can still help identify false statements through their learned regression weights, even when excluded from human-interpretable definitions.The paper distinguishes predictive utility from semantic definition.
  • Path ranking: The model ranks extracted predicate paths by importance w and removes unnecessary or verbose paths using an empirically chosen threshold θ.The resulting set D∗ is intended to contain specific predicate definers.

IV. EXPERIMENTS

The experiments evaluate fact checking on DBpedia and SemMedDB using multiple test cases, comparison methods, and cross-validation. The study also documents dataset construction, missing-predicate evaluation, and practical constraints affecting baseline comparisons.

  • Experimental scope: The evaluation covers fact checking and definition interpretation across eight test cases on DBpedia and SemMedDB.The experiments use thousands of fact statements from two large real-world knowledge graphs.
  • Datasets: DBpedia and SemMedDB are converted into heterogeneous multigraphs from RDF triples, with entities sharing names or identifiers merged.DBpedia uses infobox facts and article ontology, while SemMedDB retains duplicate edges.
  • Evaluation design: The fact-checking task removes all edges labeled by the target predicate before evaluating missing facts and unseen relations.The modified graph is G′ = G −p.
  • Baselines: All experiments use 10-fold cross validation and compare the proposed method with nine alternative approaches, including graph, path, rule, and embedding models.The comparison includes Adamic/Adar, Preferential Attachment, Katz, Semantic Proximity, PPR, SimRank, PCRW, AMIE, and TransE.
  • Practical constraints: PathSim and other symmetric-only algorithms cannot be compared because AMIE-mined rules are rarely symmetric when endpoint entity types differ.AMIE also required 2,690 CPU hours on DBpedia and 1,190 CPU hours on SemMedDB, while publicly available RESCAL and NTN implementations were impractical or produced incomprehensible results.

C. Test Cases

The test suite constructs difficult true and false statements across geography, history, business, politics, and biomedicine. The default design uses a 20/80 true-to-false split, with additional experiments varying label proportions.

  • Test-case scope: Eight test cases span capital-city, civil-war commander, company CEO, bestseller author, vice-president, disease, and cell-function relations.The cases cover DBpedia and SemMedDB entity types across geography, history, business, politics, and biology.
  • Geography: CapitalOf #2 contains 250 statements: 50 true capital-city relations and 200 false random capital-state matchings.The construction tests examples such as Springfield paired with states other than Illinois.
  • History: The US Civil War case contains 710 commander-battle statements, including 126 true relations and 584 incorrect random matchings.The true statements concern Union and Confederate commanders of decisive US Civil War battles.
  • Business: The Company CEO case contains true statements about 205 notable companies and 1,025 incorrect CEO-company matchings.The task checks whether a person is the CEO of a company.

D. Predicate Path Analysis

Predicate-path analysis compares anchored predicate paths with meta paths and examines their feature sizes, interpretability, and performance. Anchored paths achieve comparable performance with smaller feature sets, while some meta-path analyses become impractical.

  • Path design: Meta paths require type labels for every entity in a path, whereas anchored predicate paths require labels only at path endpoints.This makes anchored paths less restrictive than meta paths.
  • Performance comparison: Anchored predicate paths perform comparably to meta paths across six DBpedia tasks despite using a much smaller feature set.The comparison includes original and information-gain-selected path subsets.
  • Feature size: Even after selecting the most informative paths, meta-path feature sets are typically larger while producing similar performance.For (gngm, causes, celf), 165,331 unique meta paths were extracted, compared with 1,066 unique anchored predicate paths.
  • Interpretability: The study presents anchored paths as more intuitive in an example but leaves complete testing of path understandability for future work.The authors identify intuitive interpretation as difficult to test fully.
  • Evaluation metrics: The reported fact-checking score is AUROC from logistic regression with 10-fold cross validation, while feature-generation time is reported separately by algorithm.A missing table value marked with an asterisk reflects an excessively large feature set.

E. Fact Checking

The proposed fact-checking method is evaluated against nine competing algorithms across DBpedia and SemMedDB, with strong performance in discriminating true statements from carefully chosen false ones. Its runtime is comparable to existing models, while its performance varies with negative-example construction and graph structure.

  • The proposed method is compared with nine link prediction, knowledge base completion, and data mining algorithms on DBpedia and SemMedDB.
  • In CapitalOf #1, the method significantly outperforms alternatives when true capitalOf statements are mixed with false largestCity statements.
  • Only 17 U.S. capital cities are also their state’s largest city, limiting purely topographical models that strongly connect largest cities with states.
  • Randomly generated negatives make tasks easier for topological models, while SimRank slightly outperforms the proposed model on Company CEO and NYT Bestseller.
  • TransE performs poorly on these tasks, potentially because of the large graph or its handling of duplicated edges, which may help identify factual relations in SemMedDB.
  • The experiments use a 20/80 true/false ratio and additionally test robustness across different class ratios; mean execution times are combined across eight tasks.

F. Statement Interpretation

The paper frames discriminative predicate paths as interpretable representations of entity relationships and evaluates them as alternatives to manually specified or globally mined paths. Across several tasks, the framework combines broad fact-checking performance with interpretable explanations while leaving extensions for future work.

  • Statement Interpretation: The model’s main contribution is explaining relationship meaning through commonsense predicate paths rather than only producing fact-checking predictions.
  • Statement Interpretation: Its predicate paths are presented as generally intuitive and as describing at least one key property of the fact being evaluated.
  • Statement Interpretation: One discovered path encodes that a vice president can succeed another vice president and later become president; eight U.S. presidents fit this pattern.
  • Discriminative Path Generation: Unlike approaches requiring human-annotated paths or global association rules, the framework extracts context-dependent paths directly for given endpoints.
  • Conclusions and Future Work: Across several thousand statements and eight tasks on DBpedia and SemMedDB, the framework is reported as the all-around best performer with runtime similar to existing models.
  • Conclusions and Future Work: The framework is generally invariant to the true/false class ratio and discovers interpretable paths missed by other methods.
  • Conclusions and Future Work: Future work includes predicate identification, enhanced entity representation, and fact qualification.
Loading 1510.05911v2…