Finding Streams in Knowledge Graphs to Support Fact Checking

I. INTRODUCTION

• Content-based reasoning is needed beyond rumor-context signals, while a desirable system should combine accuracy, interpretability, simplicity, scalability, and broader claim context.The introduction also identifies near-real-time operation as a fact-checking need.Source: §I · pp. 1–2
• Knowledge Stream treats a knowledge graph as a flow network, using multiple paths whose shared edges are reused subject to capacity constraints.It seeks maximum knowledge flow at minimum cost.Source: §I · p. 2
• For the Gladwell book claim, the What the Dog Saw route receives more flow than the Tipping Point route, reflecting stronger evidence.The figure depicts the best paths, with edge width roughly proportional to knowledge flow.Source: Figure 1 · p. 1, §I · p. 2
• The paper introduces relation similarity and uses it in Relational Knowledge Linker to bias a single shortest-path search toward predicates related to the claim.Relational Knowledge Linker scores a claim using one shortest, semantically related path.Source: §I · p. 2
• Knowledge Stream is presented as a novel flow-network method for fact checking with large knowledge graphs, and, to the authors’ knowledge, the first such application to soft reasoning.The paper gives DBpedia as an example knowledge graph.Source: §I · p. 2
• Knowledge Stream and Relational Knowledge Linker offer high interpretability and performance comparable to state-of-the-art methods.Knowledge Stream also produces more meaningful explanations than methods such as PredPath.Source: §I · p. 2

II. METHODS

• The knowledge graph is represented as a directed graph whose edges are labeled with semantic relations, but the methods discard edge directionality in practice.The formal graph includes node, edge, and relation sets, with a function labeling each edge by a predicate.Source: §II · pp. 2–3
• The figure contrasts a line graph with its contracted form, whose edge weights count how often relations co-occur with neighboring relations in the knowledge graph.The example uses four relations and five nodes.Source: Figure 2 · p. 3
• Both proposed methods depend on gauging similarity or relevance between pairs of relations.The authors begin the methods section by describing a data-driven approach to relational similarity.Source: §II · p. 3

A. Relational Similarity via the Line Graph of a KG

• The contracted line graph merges nodes with duplicate relation labels into one node per relation, with edge weights recording merged edges.It is built from the KG’s line graph, whose nodes represent KG edges and whose adjacencies reflect incident edges.Source: A. Relational Similarity via the Line… · p. 3
• TF-IDF weighting addresses raw co-occurrence counts being dominated by common relations, and cosine similarity between weighted rows defines relation similarity.The co-occurrence matrix is the adjacency matrix of the contracted line graph.Source: A. Relational Similarity via the Line… · p. 3
• Fig. 3 shows the top 20 most similar relations for selected DBpedia predicates, with font size proportional to relational similarity.Compare font sizes within each predicate’s displayed list.Source: Figure 3 · p. 3

B. Fact checking as a Minimum Cost Maximum Flow Problem

• Knowledge Stream assigns edge capacities from predicate similarity and incident-node specificity, while edge costs are the logarithm of the degree of the node in the path direction.The specificity assumption treats higher-degree nodes as more general.Source: B. Fact checking as a Minimum Cost… · pp. 3–4
• The minimum-cost maximum-flow solution sends knowledge from subject to object along paths, with each path’s maximum contribution set by its bottleneck capacity.The total maximum flow is the sum of the bottlenecks of paths in the stream.Source: B. Fact checking as a Minimum Cost… · pp. 3–4
• The truth score sums path net flows, combining each path’s bottleneck with specificity that favors paths involving few specific entities.Path specificity is inversely proportional to the sum of logarithms of intermediate-node degrees.Source: B. Fact checking as a Minimum Cost… · p. 4

C. Computing the Knowledge Stream

• Successive Shortest Path iteratively finds a shortest path in the residual network and pushes flow up to that path’s bottleneck.Residual networks include forward edges with leftover capacity and backward edges that can undo previously allocated flow.Source: C. Computing the Knowledge Stream · p. 4
• Node potentials track reduced edge costs for efficient successive path-finding and contribute to optimality conditions for maximum flow.The passage cites these optimality conditions as ensuring maximum flow upon termination.Source: C. Computing the Knowledge Stream · p. 4
• For integer maximum flow γ, the stated complexity is O(γ|E| log |V|); in practice, the algorithm is pseudo-polynomial because γ is computed and need not be an integer.The complexity bound assumes integral edge weights; the passage says rational capacities can be converted to integers.Source: C. Computing the Knowledge Stream · p. 4
• On DBpedia, the implementation takes an average of 356 seconds per triple on a laptop.The passage characterizes this performance as acceptable.Source: C. Computing the Knowledge Stream · p. 4

D. Relational Knowledge Linker

• Knowledge Linker ignores the target predicate’s semantics, so KL-REL biases its search for specific paths toward edges semantically related to that predicate.The revised path measure also accounts for intermediate-node specificity and considers the last edge without penalizing the object’s generality.Source: D. Relational Knowledge Linker · p. 5
• KL-REL scores a triple by the maximum revised path-specificity value, computed efficiently with Dijkstra’s algorithm.The method’s truth score is the maximum over paths connecting the subject and object.Source: D. Relational Knowledge Linker · p. 5

III. EVALUATION

• The evaluation examines Knowledge Stream and Relational Knowledge Linker on a range of datasets.The passage introduces the evaluation but does not report its results in the supplied text.Source: §III · p. 5
• The comparison includes existing computational fact-checking, knowledge-base construction, and link-prediction approaches.The passage says the experimental setup is described next.Source: §III · p. 5

1) Knowledge Graph:

• DBpedia is filtered to remove transitive-closure subsumption triples and RDF-literal objects, yielding an undirected graph with 6M nodes, 24M triples, and 663 relations.Source: 1) Knowledge Graph · p. 5

2) Labeled Datasets:

• The evaluation combines synthetic facts from several domains with real-world triples from GREC and WSDM Cup corpora.GREC covers birthplace, death place, alma mater, and educational degree; WSDM Cup datasets cover professions and nationalities.Source: 2) Labeled Datasets · p. 5
• GREC triples are retained only when five raters unanimously label them true or false, while WSDM Cup contributes unanimously rated true triples.Source: 2) Labeled Datasets · p. 5

3) Benchmark & Metric:

• Methods are compared using AUROC, the probability that a true triple receives a higher score than a false one.The benchmark includes fact-checking, knowledge-graph-completion, and link-prediction algorithms.Source: 3) Benchmark & Metric · p. 6

4) Implementation & Configuration:

• The implementation uses Python 2.7 and Cython 0.22; Katz, PRA, and PredPath use up to 200 paths at lengths 1–3, while TransE uses 100-dimensional embeddings for 1,000 epochs.Source: 4) Implementation & Configuration · p. 6

1) Fact checking:

• The average optimum for Knowledge Stream uses exactly two paths; too many paths can hinder performance, so stream length should be tuned.Fig. 4 reports average performance across datasets as a function of the number of paths.Source: 1) Fact checking · p. 6, Figure 4 · p. 6
• KS-AVG fixes the stream at two paths and KS-CV tunes path count per dataset; both improve average performance over KS and exceed KL-REL on synthetic datasets.KS-CV uses cross-validation and is therefore supervised.Source: 1) Fact checking · p. 6

2) Discovery of relational patterns:

• KS discovers frequent path patterns that distinguish paths from true triples from those found with false triples, and the reported patterns are highly relevant.The paper notes that these patterns could seed information-extraction rules or serve as features for learning other concepts.Source: 2) Discovery of relational patterns · p. 6, Table IV · p. 8

1) Fact checking:

• KL-REL outperforms KL, TransE, and link-prediction algorithms, leads on real-world datasets, and is comparable to PredPath on synthetic data.The tables compare fact-checking performance on synthetic and real datasets; statistical tests do not identify a clear overall winner.Source: 1) Fact checking · p. 6, Table III · p. 7, Table II · p. 7

3) Surfacing facts relevant to a target claim:

• Knowledge Stream automatically surfaces relevant ground facts for a target claim, with wider edges indicating paths carrying greater net flow.The illustrated Berkshire Hathaway–Warren Buffett claim shows diverse facts supporting the triple.Source: 3) Surfacing facts relevant to a… · p. 8

• Truthy, Rumorlens, TweetCred, and Claim-Buster track contextual indicators, while Hoaxy studies claims and fact checks without analyzing claim content.Source: §IV · p. 8
• Logical approaches such as ILP and AMIE are interpretable, whereas embedding models including RESCAL and TransE handle uncertainty and global regularities but can be difficult to interpret.The passage also identifies scalability concerns for both classes.Source: §IV · p. 8
• Knowledge Linker uses a single short, specific path, but does not account for the target predicate's semantics.Source: §IV · p. 8
• PRA and PredPath use labeled examples for path-feature selection and training; the paper says its methods offer comparable or better performance with greater interpretability and expressiveness, without training except for learning edge capacities.Source: §IV · pp. 8–9
• Link-prediction methods rely mainly on elementary structural cues and perform poorly on many fact-checking test sets [7].Source: §IV · p. 9

• The paper presents unsupervised KS using multiple short paths and KL-REL using a single shortest path, alongside relation similarity measured from KG co-occurrence.Source: §V · p. 9
• Across diverse real-world and synthetic test cases, both approaches performed on par with the state of the art; KS also surfaced useful path patterns and relevant facts.Source: §V · p. 9
• KS remains preliminary for complex test cases, and its success depends on appropriate edge capacities; effective relational-similarity metrics remain future work.Source: §V · p. 9
• Current stream paths are ranked by flow, while novelty-, diversity-, or serendipity-aware ranking remains future research.Source: §V · p. 9
• Temporal or location-specific facts remain a challenge; a proposed extension would bias search toward KG regions valid in the relevant interval or place.Source: §V · pp. 9–10
• Successive path-finding can be slow for subjects with large search spaces; DBpedia checks take a few minutes per triple, and network simplex is suggested for better behavior.Source: §V · p. 10