Fact Checking: Theory and Practice

Xin Luna Dong, Christos Faloutsos

Xian Li, Subhabrata Mukherjee, Prashant Shiralkar

​

Slides

http://bit.ly/factcheck-kdd2018

What is Fact Checking?

Determine the correctness of a factual statement by

• searching evidence from external sources of data, and
• evaluating and aggregating the evidence

​

​

Why Fact Checking?

• “Rapid spread of misinformation online" – one of the top 10 challenges as per The World Economic Forum

​

​

¹ http://www.washingtonstarnews.com/proof-obamacare-requires-all-americans-to-be-chipped/

² http://theracketreport.com/several-injured-in-zombie-like-attack-at-tennessee-walmart-as-man-tries-to-eat-his-victims/

³https://www.forbes.com/sites/tonybradley/2017/07/31/facebook-ai-creates-its-own-language-in-creepy-preview-of-our-potential-future/

Why Fact Checking?

• Fake news--Stories that were fabrications (2016)
• Trump used the term 153 times in 2017

​

​

¹https://www.washingtonpost.com/news/fact-checker/wp/2018/02/06/president-trump-cries-fake-news-and-the-world-follows/?utm_term=.ae7dcf5247c7

² https://www.vox.com/policy-and-politics/2018/5/9/17335306/trump-tweet-twitter-latest-fake-news-credentials

Why Fact Checking?

• Misleading video taken out of context posted on Blog

​

​

¹ https://www.youtube.com/watch?v=BLWeMyGpTfI

² https://www.nytimes.com/2010/07/22/us/politics/22sherrod.html

Why Fact Checking?

• Erroneous information because of data entry errors

​

​

Why Fact Checking?

• Erroneous information because of out-of-date information

​

​

Why Fact Checking?

Why is Fact Checking Hard?--Sparsity

• To verify 90% retail phone# from >=3 sources, we need > 1000 sources

10-coverage

1-coverage

Nilesh Dalvi, Ashwin Machanavajjhala, Bo Pang:

An Analysis of Structured Data on the Web. VLDB 2012.

​

.

#Sources

Why is Fact Checking Hard?--Conflicts

• Inconsistency on 70% data items with tolerance of 1% difference

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, Divesh Srivastava

Truth Finding on the Deep Web: Is the Problem Solved? PVLDB 2012.

​

.

Why is Fact Checking Hard?--Trustworthiness

• Even authoritative sources may not have very high accuracy of data

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, Divesh Srivastava

Truth Finding on the Deep Web: Is the Problem Solved? PVLDB 2012.

​

.

Why is Fact Checking Hard?--Trustworthiness

• Knowledge-Based Trust (KBT) computed for 5.6M websites

X. Dong, E. Gabrilovich, K. Murphy, et al. Knowledge-Based Trust: Estimating the Trustworthiness of Web Sources? PVLDB 2015.

​

.

Why is Fact Checking Hard?--Semantic Ambiguity

• 46% inconsistency in Stock and 33% inconsistency in Flight are caused by semantic ambiguity

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, Divesh Srivastava

Truth Finding on the Deep Web: Is the Problem Solved? PVLDB 2012.

​

.

Why is Fact Checking Hard?--Instance Ambiguity

• 87 Wei Zhang authors in DBLP 8/2018

Why is Fact Checking Hard?--Changes over Time

• Over half European patent inventors changed their address in 5 years

Pei Li, Xin Luna Dong, Andrea Maurino, Divesh Srivastava:

Linking Temporal Records. VLDB 2011.

​

.

Why is Fact Checking Hard?--Rumor/Copying

Why is Fact Checking Hard?--Rumor/Copying

• Copying or data sharing happens not only on correct data

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, Divesh Srivastava

Truth Finding on the Deep Web: Is the Problem Solved? PVLDB 2012.

​

.

Why is Fact Checking Hard?--Text Understanding

Does solar panels really drain the sun of energy?

Why is Fact Checking Hard?--Inference

Recap: What is Fact Checking?

Determine the correctness of a factual statement by

• searching evidence from external sources of data, and
• evaluating and aggregating the evidence

​

​

What to Check?

• Different formats
• Structured triples: (Obama, born_in, Kenya)
• Textual claims: “solar panel drains the sun of energy”
• Entire articles: e.g., fake reviews
• Different types
• Atomic: string, categorical, numerical �E.g., “The height of Mt Everest is 29K”
• Correlated: “Tom Cruise plays Pete in Top Gun”
• Aggregated: “Tom Cruise is the actor in all Top Gun series”

Where to Check?

• Graph data
• Curated knowledge graph: e.g., Freebase, WikiData
• Extracted KG: ClosedIE--Knowledge Vault, OpenIE--ReVerb

Where to Check?

• Structured data
• Semi-structured websites: e.g., IMDb
• Web tables, lists
• RDB, XML, etc.

Where to Check?

• Text data
• Web texts: e.g., Wikipedia
• Social network posts/blogs
• Query logs

How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Objective evidence?

Up-to-date evidence?

Related evidence?

​

How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Trustworthy source ?

Correlation of sources?

Joint interaction between statement, evidence and its source!

Objective evidence?

Up-to-date evidence?

Related evidence?

​

How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Trustworthy source ?

Correlation of sources?

Credible statement ?

Objective evidence?

Up-to-date evidence?

Related evidence?

​

Goals of a Fact Checker

• Accuracy

Fact checker’s prediction should mimic truth

• Scalability

Reduce human burden by scaling to vast volume of data

• Interpretability

Provide explanation for the prediction

Outline

Part I: Fact Checking from Structured Data

Part II: Fact Checking from Graphs, Anomaly Detection

Part III: Fact Checking from Texts

Recipe

• Characteristics of sources
• High-level intuitions
• Technique details
• Summary w. a short answer

Questions We Answer Throughout the Tutorial

• How do we leverage evidence that is non-trustworthy?
• How do we infer using indirect evidence?
• How do we handle complex statements and ambiguous evidence?

The FEVER Dataset (fever.ai)

Fact Checking on Structured Data

Xin Luna Dong, Christos Faloutsos

Xian Li, Subhabrata Mukherjee, Prashant Shiralkar

​

Fact Checking on Structured Data

Our Focus

Fact Checking on Structured Data

Input

Structured data + provenance

A given fact f

Output

Prob(f is true)

​

f: Obama’s birthplace is Kenya

Prob(f) = ?

Source Characteristics

Data are redundant, well structured with schema alignment.

Atomic values: categorical, numerical, date etc

It may be single truth or multiple truths

Source Characteristics

Source trustworthiness varies

Source Characteristics

Source may be correlated and errors spread easily

Intuitions

• Trustworthy sources usually provide truthful data

Source Trustworthiness is the Key

Majority voting and correctly identify similar values. Accuracy = 0.6

Source Trustworthiness is the Key

Accurate source, Accuracy = 1.0

Intuitions

• Trustworthy sources provide more truthful data
• Correlated sources spread erroneous data and may dominate in voting

Correlated Sources Spread Erroneous Data

Majority voting, Accuracy = 0.4

Intuitions

• Trustworthy sources provide more truthful data
• Correlated sources spread erroneous data and may dominate the voting
• Learn source quality from labeled data & domain specific features

Learn Source Quality from Features

Characteristics, Challenges and Opportunities

Methods

EM-Like Model

Graphical Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2012

PrecRecCorr Pochampally et al. 2014

FACTY Li et al. 2017

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

...

LTM Zhao et al. 2012

GTM Zhao et al. 2014

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

...

​

​

​

Query Perturbation Wu et al. 2017

​

​

Methods Covered In This Talk

EM-Like Model

Graphical Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2013

PrecRecCorr Pochampally et al. 2014

FACTY Li et al. 2017

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

...

LTM Zhao et al. 2012

GTM Zhao et al. 2014

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

​

​

​

Query Perturbation Wu et al. 2017

​

Recap: Apply Fact Checking Recipe

Given a fact for validation:

• Gather evidence from different sources
• Evaluate evidence
• Model joint interaction
• Aggregate evidence and predict

Roadmap

EM-Like Model

Graphical Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2013

PrecRecCorr Pochampally et al. 2014

FACTY Li et al. 2017

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

...

​

...

LTM Zhao et al. 2012

GTM Zhao et al. 2014

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

​

​

​

Query Perturbation Wu et al. 2017

​

EM-Like Models

• Data sources are of different quality and we trust data from accurate sources more

​

​

Model source quality for accurate results

Recap: Source Accuracy is the Key

Accurate source, Accuracy = 1.0

Boost the vote from trustworthy sources

ACCU: Gather/Evaluate Evidence

• Recipe 1/4: Gather evidence
• Given a data item D (e.g. Obama’s birthplace),
• Dom(D) = {v₀, v₁, …, v_n}
• Ф: s₁ provides v₀ for D, s₂ does not provide any value for D
• Recipe 2/4: Evaluate evidence
• Objective evidence
• Value distribution, similarity and formatting

​

Xin Luna Dong, Laure Berti-Equille, and Divesh Srivastava:

Integrating conflicting data: the role of source dependence. In VLDB, 2009

ACCU: Gather/Evaluate Evidence

• Recipe 1/4: Gather evidence
• Given a data item D (e.g. Obama’s birthplace),
• Dom(D) = {v₀, v₁, …, v_n}
• Ф: s₁ provides v₀ for D, s₂ does not provide any value for D
• Recipe 2/4: Evaluate evidence
• Objective evidence
• Value distribution, similarity and formatting

​

Similar Step 1 and 2 for all the other methods, we will skip these two steps for the rest of the talk.

ACCU: Joint Modeling and Predict

​

• Recipe 3-4 /4: Prediction

Continue until source accuracy converges

ACCU Series: More Features in Joint Modeling

• False value distribution
• Value similarity
• Value format
• Trustworthiness on attribute level

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, and Divesh Srivastava:

Truth finding on the Deep Web: Is the problem solved? In VLDB, 2013

ACCU Series: Main Results

​

Leverage source trustworthiness significantly improve the fact checking accuracy

EM-Like Models

• Data sources are of different quality and we trust data from accurate sources more

​

• Data sources can copy from each other and errors can be propagated quickly

Model source quality for accurate results

Model the source dependence

Recap: Correlated Sources Spreads Erroneous Data

Majority voting, Accuracy = 0.4

Downweight the vote from dependent sources

DEPEN: Model Copying Relationship

How to detect source copying?

Xin Luna Dong, Laure Berti-Equille, and Divesh Srivastava:

Integrating conflicting data: the role of source dependence. In VLDB, 2009

DEPEN: Model Copying Relationship

If two sources share a lot of false values, they are more likely to be dependent.

DEPEN: Model Copying Relationship

Who is the copier?

DEPEN: Model Copying Relationship

S1 is more likely to copy from S2, if the accuracy of the common data is highly different from the accuracy of S1.

DEPEN: Model Copying Relationship

​

• Recipe 4/4: Prediction

DEPEN: Main Results

Modeling source dependence further improves the fact checking accuracy significantly

DEPEN: Bookstore Copiers

Low quality source may have many copiers

Source Copying is not rare

EM-Like Models

• Data sources are of different quality and we trust data from accurate sources more

​

• Data sources can copy from each other and errors can be propagated quickly

Model source quality for accurate results

Model the source dependence

Is source accuracy good enough to model source quality?

Is source copying the only type of source correlation?

Source Correlation can be Positive or Negative

Correlation in Web Extraction

Correlation in Web Sources

Negative correlation

Positive correlations

5 pairs of extractor positively correlate

40% pairs of extractor negatively correlate

PrecRec: Model Positive/Negative Correlation

• Use Precision and Recall to model the source quality

​

High recall

High precision

Med prec/rec

Ravali Pochampally, Anish Das Sarma, Xin Luna Dong, Alexandra Meliou, and Divesh Srivastava:

Fusing data with correlations. In Sigmod, 2014

PrecRec: Model Positive/Negative Correlation

• Use Precision and Recall to model the source quality

​

High recall

High precision

Med prec/rec

More likely to be correct if extracted by high-precision source

More likely to be wrong if not extracted by high-recall source

PrecRec: Model Positive/Negative Correlation

• Model two types of correlations
• Positive correlation: e.g. data copying
• The fact provided by two dependent sources should not significantly increase our belief that it is true
• Negative correlation: e.g. complimentary sources
• The fact provided by one source but not the other should not significantly reduce our belief that it is true

PrecRec: Main Results

PrecRecCorr achieved the best F1 score, and handle well of both single value truth and multi-value truth.

PrecRecCorr achieved the best AUC-PR

Roadmap

Statistical Model

Graphical Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2013

PrecRec Pochampally et al. 2014

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

FACTY Li et al. 2017

...

​

...

LTM Zhao et al. 2012

​

GTM Zhao et al. 2014

​

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

​

​

​

Query Perturbation Wu et al. 2017

​

Probability Graphical Models

• Data sources are of different quality and we trust data from accurate sources more

​

• Data sources can copy from each other and errors can be propagated quickly

​

• More principled models

Model source quality for accurate results

Model the source correlation

Graphical Models

LTM: Latent Truth Model

• Use Bayesian Network to model the source trustworthiness, fact truthfulness and claims from sources

​

Each node is a random variable (observed value, latent value or unknown parameter)

Directed edge (a->b) models the conditional dependence between a and b.

B Zhao, BIP Rubinstein, J Gemmell, J Han:

A Bayesian approach to discovering truth from conflicting sources for data integration, In VLDB 2012

LTM: Latent Truth Model

Prior truth probability

Observation of claim

Specificity ~ false positive

Sensitivity(recall) ~ false negative

𝞱: Beta(𝞫)

t : Bernoulli(𝞱)

f is true: sensitivity->Bernoulli(𝝓¹_sc)

f is false: specificity ->Bernoulli(𝝓⁰_sc)

​

LTM: Main Results

Both accuracy and F1 score are significantly higher than other methods on both datasets

Both accuracy and F1 score are significantly higher than other methods on both datasets

Not compared with ACCU method

GTM: Gaussian Truth Model

• Focus on estimating real-valued truth from conflicting data sources.

​

• Consider the distance between real values. Values closer to the mean parameter have higher probability than values that are farther.

B Zhao, J Han:

A Probabilistic Model for Estimating Real-valued Truth from Conflicting Sources, In QDB 2012

GTM: Gaussian Truth Model

​

Use Gaussian to model the prior truth probability of real value

GTM: Gaussian Truth Model

GTM outperformed all other methods in estimating the truth values of numerical attributes.

KBT: Knowledge-based Trust

• Distinguish the source quality and extractor accuracy
• Use graphical model to predict four things at the same time
• fact correctness
• source accuracy
• extraction correctness
• extractor precision/recall

Xin Luna Dong, Evgeniy Gabrilovich, Kevin Murphy, Van Dang, Wilko Horn, Camillo Lugaresi, Shaohua Sun, and Wei Zhang:

Knowledge-based trust: estimating the trustworthiness of web sources. In VLDB, 2015

KBT: Knowledge-based Trust

• Recipe 3/4: Joint Modeling

Source accuracy

Precision/Recall of extractor

Correct values of data item d

source w provides value v for d

Whether extractor e extracts from source w the (d, v) item-value pair.

KBT: Knowledge-based Trust

Model source and extractor separately improved the accuracy of fact checking

Model source and extractor separately improved the estimation of source accuracy

KBT: Knowledge-based Trust

​

KBT scores of 5.6MM websites based on 119M+ web pages

52% websites have a KBT over 0.8

Roadmap

Statistical Model

Graphical Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2013

PrecRec Pochampally et al. 2014

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

FACTY Li et al. 2017

...

​

...

LTM Zhao et al. 2012

​

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

​

​

​

Query Perturbation Wu et al. 2017

​

SLimFast: Unsupervised vs Supervised Model

• Unsupervised method leveraging data conflicts and source quality estimation
• Supervised method leveraging domain-specific features and small amount of labeled data
• When to use unsupervised method and when to use supervised method

Unsupervised Method

Supervised Method

Optimizer between unsupervised and supervised

Theodoros Rekatsinas, Manas Joglekar, Hector Garcia-Molina, Aditya G. Parameswaran, Christopher Ré:

SLiMFast: Guaranteed Results for Data Fusion and Source Reliability. SIGMOD Conference 2017

SLiMFast: Discriminative Data Fusion

• Supervised data fusion (EMR algorithm)

Challenge: limited labeled data

Sources have domain-specific features that are indicative of their accuracy

Reduce the required training data

SLiMFast: Discriminative Data Fusion

​

Perform well only when there are many observations per fact and when sources have an avg. accuracy p > 0.5

Need number of labeled examples proportional to the number of Sources

Original slides from Theodoros Rekatsinas

SLiMFast: Discriminative Data Fusion

Goal: maximize accuracy of estimated true values of facts

• If sufficient labeled data, use supervised learning
• If source accuracy is high and observation density is high, use unsupervised learning
• otherwise instance based decision

SLiMFast: Discriminative Data Fusion

SLiMFast is more effective with small volume of training data due to the reduced dimension of the model

Roadmap

Statistical Model

Probability Graphical & Optimization Model

Supervised Model

Computational Fact Checking

ACCU, DEPEN Dong et al. 2009

ACCU Series Li et al. 2013

PrecRec Pochampally et al. 2014

TruthFinder Yin et al. 2008

Scale up Copy Li et al. 2015

FACTY Li et al. 2017

...

​

LTM Zhao et al. 2012

​

KBT Dong et al. 2015

GLAD Whitehill et al. 2009

CRH Li et al. 2014

Minimax Entropy Zhou et al. 2012

...

SLiMFast Rekatsinas et al. 2016

​

​

​

Query Perturbation Wu et al. 2017

​

​

​

Fact Checking by Query Perturbation

Ideally ...

• Data is rich, cleaned, conflict resolved, well-structured, …
• Are all the claims drawn from the data reliable?

Total number of adoptions during 1996-2001 increased by 66.5% compared with 1990-1995

Giuliani was in office from 1994-2001

You Wu, PankaJK.Agarwal, Chengkai Li, Jun Yang, Cong Yu: Computational Fact Checking through Query Perturbations. TODS 2017

Fact Checking by Query Perturbation

Claim: Total number of adoptions during 1996-2001 increased by 66.5% compared with 1990-1995

Counterargument: Comparing the first and last years of Giuliani’s tenure, adoptions increased by only 17%

Giuliani was in office from 1994-2001

Fact Checking by Query Perturbation

​

• Beyond correctness, what measures the “quality” of claims?
• How do we unravel vague claims?
• How do we counter claims?

​

Original slides from Jun Yang

Fact Checking by Query Perturbation

• Claim = a parameterized query q
• Has a specific setting p₀ of parameters
• Returns a specific answer q(p₀)
• Perturb a claim: try different p from the parameter space and see how r = q(p) compares with r₀ = q(p₀)

+ Strengthens the claim

- Weakens the claim

Let SR(r; r₀) measure the strength of result r relative to r₀

Fact Checking by Query Perturbation

Let SP(p; p₀) measure the sensibility of parameter setting p given p₀

• Think of it as defining a weight on each possible parameter setting, or a pdf/pmf over P
• Higher sensibility means p is more relevant to checking the claim

​

​

It may be irrelevant to consider perturbations this far

Original slides from Jun Yang

Fact Checking by Query Perturbation

Finding counterarguments

• To counter a claim, find parameter setting p that optimizes:
• SR(q(p); r₀): Strength ~ the more negative the better
• SP(p; p₀): Sensibility ~ the higher the better

FACTY: Combine Structured, Graph and Text Evidence

• FACTY presents fact checking by considering evidence from
• Knowledge graph
• Text data
• Search log

Furong Li, Xin Luna Dong, Anno Largen, and Yang Li. Knowledge verification for long tail verticals. In VLDB, 2017

Solution:

​

Convert all evidence into structured data and apply EM-like models.

FACTY: Combine Structured, Graph and Text Evidence

In 4 long tail verticals, FACTY effectively filtered false triples.

Summary

• Fact checking in structured data is based on three intuitions:
• Trustworthy sources provide truthful data
• Data sources are of different quality and we trust data from accurate sources more
• Correlated sources spread erroneous data
• Data sources can copy from each other and errors can be propagated quickly
• Learn from labeled data and domain-specific features

Summary

​

• How do we leverage evidence that is non-trustworthy?
• Model source accuracy
• Model source correlation
• How do we infer using indirect evidence?
• How do we handle complex statements and ambiguous evidence?

References

Xin Luna Dong, Laure Berti-Equille, and Divesh Srivastava. Integrating conflicting data: the role of source dependence. In VLDB, 2009

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, and Divesh Srivastava. Truth finding on the Deep Web: Is the problem solved? In VLDB, 2013

Ravali Pochampally, Anish Das Sarma, Xin Luna Dong, Alexandra Meliou, and Divesh Srivastava. Fusing data with correlations. In Sigmod, 2014

Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng, and Divesh Srivastava. Scaling up Copy Detection. In ICDE, 2015

Furong Li, Xin Luna Dong, Anno Largen, and Yang Li. Knowledge verification for long tail verticals. In VLDB, 2017

B Zhao, BIP Rubinstein, J Gemmell, J Han: A Bayesian approach to discovering truth from conflicting sources for data integration, In VLDB 2012

B Zhao, J Han: A Probabilistic Model for Estimating Real-valued Truth from Conflicting Sources, In QDB 2012

Xin Luna Dong, Evgeniy Gabrilovich, Kevin Murphy, Van Dang, Wilko Horn, Camillo Lugaresi, Shaohua Sun, and Wei Zhang. Knowledge-based trust: estimating the trustworthiness of web sources. In VLDB, 2015

Theodoros Rekatsinas, Manas Joglekar, Hector Garcia-Molina, Aditya G. Parameswaran, Christopher Ré: SLiMFast: Guaranteed Results for Data Fusion and Source Reliability. SIGMOD Conference 2017

You Wu, PankaJK.Agarwal, Chengkai Li, Jun Yang, Cong Yu: Computational Fact Checking through Query Perturbations. TODS 2017

​

​

​

Fact Checking from Graph

Xin Luna Dong, Christos Faloutsos

Xian Li, Subhabrata Mukherjee, Prashant Shiralkar

​

Where Do We Find Knowledge For Fact Checking?

Source: Barack Obama was born on April 8, 1961 in Honolulu which is the capital of Hawaii

(non-trivial processing)

https://en.wikipedia.org/wiki/Barack_Obama

@BarackObama

The Web

Linked Data

Knowledge Graph: A Rich Source For Fact Checking

ex:birthDate

ex:bornIn

ex:capitalOf

Instance Data (RDF)

ex:Barack_Obama

Characteristics of Knowledge Graphs

Knowledge is ..

• Structured
• Accurate
• Trustworthy
• Unambiguous

But ..

• Incomplete

Nevertheless, a rich source for fact checking!

Size of Publicly Available Knowledge Graphs

H Paulheim. Knowledge graph refinement: A survey of approaches and evaluation methods. Semantic Web, 2017.

​

This Talk: Fact Checking Using KGs

Input

a Knowledge Graph

a claim triple

Output

compute a truth value

​

​

Fact checking can be posed as a Triple Verification problem

Number in parenthesis indicates node degree in DBpedia 2016

Recap: Goals of a Fact Checker

• Accuracy

Fact checker’s prediction should mimic truth.

• Scalability

Reduce human burden by scaling to vast volume of data.

• Interpretability

Provide explanation for the prediction.

Key Differences with Structured Data

Methods

x

Methods

Intuition: Use KG structure to explain Similarity(S, O).

No use of node & edge types → Sub-optimal perf.

Methods

Intuition: Model the joint distribution of KG facts as a dependency graph using input logical formulate. Fact checking = inference for (S, P, O).

Input: KG + logical formulae

Scalability is a serious issue.

KG

Dependency Graph

Example from

Nickel et al. (2016)

​

Red: marriedTo

Blue: parentOf

Methods--Earlier Tutorial Today (T01)!

Intuition: Predicate embedding captures the relation (+/x) between subject and object embeddings

Accurate, but low interpretability

Table from Wang et al. (AAAI 2014)

Refer: Graph & Tensor Mining for Fun and Profit

Methods: Focus today

x

Not only accurate and scalable,

But also interpretable

Methods--This Talk

Intuition: A (S, P, O) triple can be reasoned upon based on chains of related facts (paths) in the KG.

Washington

Olympia, WA

Capital ?

Washington State Liquor and Cannabis Board

jurisdictionOf

headquarter

Accurate, Scalable and Interpretable!

Path Ranking Algorithm (PRA)

Intuition: Common path types around +ve node pairs of a relation discriminate them from -ve node pairs.

N Lao and WW Cohen. Relational retrieval using a combination of path-constrained random walks. Machine Learning, 2010.

Path Ranking Algorithm (PRA)

Recipe:

1. Generate paths of length <k as features

​

Path Ranking Algorithm (PRA)

Recipe:

• Generate paths of length <k as features
• Select informative features
• Use precision and recall of feature

​

Path Ranking Algorithm (PRA)

Recipe:

• Generate paths of length <k as features
• Select informative features
• Learn a discriminative model for relation

​

Paths as features

Node pairs

Feature matrix

Path Ranking Algorithm (PRA)

Recipe:

• Generate paths of length <k
• Select informative features
• Learn a discriminative model for relation
• Generate feature for a claim triple and predict

​

PRA - Top Ranked Paths

Simple, intuitive explanation

N Lao, T Mitchell, WW Cohen. Random walk inference and learning in a large scale knowledge base. EMNLP 2011.

Path Ranking Algorithm (PRA)

Applied for inference in:

• NELL (Lao et al. - EMNLP 2011)
• Knowledge Vault (Dong et al. - KDD 2014)

Results still far from perfect

N Lao, T Mitchell, WW Cohen. Random walk inference and learning in a large scale knowledge base. EMNLP 2011.

Discriminative Predicate Path Mining (PredPath)

B Shi, T Weninger. Discriminative predicate path mining for fact checking in knowledge graphs. Knowledge-Based Systems, 2016.

Discriminative Predicate Path Mining (PredPath)

Idea: Same as PRA, but instead mine anchored predicate paths and use them as features.

​

Example:

​

for

B Shi, T Weninger. Discriminative predicate path mining for fact checking in knowledge graphs. Knowledge-Based Systems, 2016.

Similar Recipe, Different Ingredients

Similarities

1. Paths as “experts” or features
2. Feature selection using supervision
3. Learn supervised learning model for fact checking

Differences

Top Discriminative Paths by PredPath

Intuitive definition of target predicate as explanation

Performance of PredPath

• Performs better than PRA
• Lower performance on some datasets

PRA

B Shi, T Weninger. Discriminative predicate path mining for fact checking in knowledge graphs. Knowledge-Based Systems, 2016.

Knowledge Linker (KL)

Intuition: A short path involving specific nodes may be predictive of the truth.

GL Ciampaglia, P Shiralkar, LM Rocha, J Bollen, F Menczer, A Flammini. Computational fact checking from knowledge networks. PLoS ONE, 2015.

Specificity of a Path

How do we identify a short, specific path?

Specificity inversely proportional to generality of a path

KL scores true relations along the diagonal higher than false ones

GL Ciampaglia, P Shiralkar, LM Rocha, J Bollen, F Menczer, A Flammini. Computational fact checking from knowledge networks. PLoS ONE, 2015.

Performance of KL

Ignores semantics of target predicate!

(B. Obama, spouse, M. Obama) True

(B. Obama, sibling, M. Obama) True!

Mixed results: Good performance on some datasets, but poor on others

Relational Knowledge Linker (KL-REL)

• Same intuition as Knowledge Linker (KL)
• Short, specific paths are informative
• But find paths with edge types similar to target predicate

Relational Similarity

How do we measure similarity between edge type and target predicate?

​

Top Similar Relations

Performance of KL-REL

By using edge types, KL-REL performs better than KL

P Shiralkar, A Flammini, F Menczer, GL Ciampaglia. Finding streams in knowledge graphs to support fact checking. ICDM, 2017.

Knowledge Stream (KS)

Capacity proportional to similarity between edge type and target predicate

Intuition: Short, specific paths connecting subject and object can explain triple’s truthfulness based on their ability to carry flow!

​

Fact Checking As Min-Cost Max-Flow Problem

1. Capacity of an edge proportional to similarity between the edge type and target predicate.
• We already know how to measure relational similarity!
2. Short, specific paths preferred over long paths.

Fact checking a claim triple = maximum flow from S to O along least cost (specific) paths.

​

KS Discovers Paths for Fact Checking

KS assigns large flow to relevant paths

Width of an edge is proportional to its flow

P Shiralkar, A Flammini, F Menczer, GL Ciampaglia. Finding streams in knowledge graphs to support fact checking. ICDM, 2017.

Knowledge Stream

Top 2 (max-flow) paths lead to optimal performance

Are all paths in the flow useful?

KS Discovers Relational Patterns

Performance Comparison of the State of the Art

​

No clear winner!

​

Rule Mining and Vector Space Approaches deliver better overall performance

P Shiralkar, A Flammini, F Menczer, GL Ciampaglia. Finding streams in knowledge graphs to support fact checking. ICDM, 2017.

Part 2 - Summary

• Knowledge Graphs - trustworthy, accurate repositories
• Rule-mining methods:
• Supervised models - PRA, PredPath
• Unsupervised - KL, KL-REL, KS
• Useful because of their ability to ..
• Learn / discover relational path patterns
• Combine multiple evidence
• Offer explanation for claims

Code and Datasets

http://bit.ly/factcheck-code-datasets

References

• N. Lao and W. W. Cohen. Relational retrieval using a combination of path- constrained random walks. Machine learning, 81(1):53–67, 2010.
• Ni Lao, Tom Mitchell, and William W. Cohen. 2011. Random walk inference and learning in a large scale knowledge base. EMNLP 2011.
• Landwehr, Niels et al. nFOIL: Integrating Naïve Bayes and FOIL. AAAI (2005).
• B. Shi and T. Weninger. Discriminative predicate path mining for fact checking in knowledge graphs. Knowledge-Based Sys., 104:123–133, 2016.
• G. L. Ciampaglia, P. Shiralkar, L. M. Rocha, J. Bollen, F. Menczer, and A. Flammini. Computational fact checking from knowledge networks. PLoS ONE, 10(6):1–13, 2015.

​

References

• P.Shiralkar,A.Flammini,F.Menczer, and G.L.Ciampaglia. Finding streams in knowledge graphs to support fact checking. In 2017 IEEE ICDM 2017, pp 859–864, 2017.
• Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014. Knowledge vault: a web-scale approach to probabilistic knowledge fusion. In SIGKDD 2014. ACM, New York, NY, USA, 601-610.
• Galárraga, Luis et al. AMIE: association rule mining under incomplete evidence in ontological knowledge bases. WWW (2013).
• W. Xiong, T. Hoang, and W. Y. Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. arXiv preprint arXiv:1707.06690, 2017.

References

• Simas, Tiago and Luis Mateus Rocha. Distance closures on complex networks. Network Science 3 (2015): 227-268.
• Adamic, Lada A. and Eytan Adar. Friends and neighbors on the Web. Social Networks 25 (2003): 211-230.
• Jeh, Glen and Jennifer Widom. SimRank: a measure of structural-context similarity. KDD (2002).
• Lü, L., Jin, C., & Zhou, T. (2009). Similarity index based on local paths for link prediction of complex networks. Physical review. E, Statistical, nonlinear, and soft matter physics, 80 4 Pt 2, 046122.
• Xu, Z., Pu, C., & Yang, J. (2015). Link prediction based on path entropy. CoRR, abs/1512.06348.

References

• Maguitman, A.G., Menczer, F., Erdinc, F., Roinestad, H., & Vespignani, A. (2006). Algorithmic Computation and Approximation of Semantic Similarity. World Wide Web, 9, 431-456.
• Nickel, M., Tresp, V., & Kriegel, H. (2011). A Three-Way Model for Collective Learning on Multi-Relational Data. ICML.
• Bordes, A., Usunier, N., García-Durán, A., Weston, J., & Yakhnenko, O. (2013). Translating Embeddings for Modeling Multi-relational Data. NIPS.
• Lin, Y., Liu, Z., Sun, M., Liu, Y., & Zhu, X. (2015). Learning Entity and Relation Embeddings for Knowledge Graph Completion. AAAI.
• Shi, B., & Weninger, T. (2017). ProjE: Embedding Projection for Knowledge Graph Completion. AAAI.

References

• Wang, Z., Zhang, J., Feng, J., & Chen, Z. (2014). Knowledge Graph Embedding by Translating on Hyperplanes. AAAI.
• Yang, B., Yih, W., He, X., Gao, J., & Deng, L. (2014). Embedding Entities and Relations for Learning and Inference in Knowledge Bases. CoRR, abs/1412.6575.
• Richardson, M., & Domingos, P.M. (2006). Markov logic networks. Machine Learning, 62, 107-136.
• Lao, N., Zhu, J., Liu, X., Liu, Y., & Cohen, W.W. (2010). Efficient Relational Learning with Hidden Variable Detection. NIPS.
• Khot, T., Balasubramanian, N., Gribkoff, E., Sabharwal, A., Clark, P., & Etzioni, O. (2015). Exploring Markov Logic Networks for Question Answering. EMNLP.

Bonus Slides

Knowledge Graph Construction (Out of Scope)

• Manual curation

​

• Collaborative construction
• Freebase (Bollacker et al. 2008), Wikipedia

​

• Semi-automatic extraction from semi-structured data
• DBpedia (Auer et al. 2007), YAGO (Suchanek et al. 2007)

​

• Automatic extraction from unstructured text
• NELL (Carlson et al. 2010), Knowledge Vault (Dong et al. 2014)

Fact Checking As Min-Cost Max-Flow Problem

Based on relational similarity

Specificity as defined in Knowledge Linker

Anomaly Detection - Graphs

Xin Luna Dong, Christos Faloutsos

Xian Li, Subhabrata Mukherjee, Prashant Shiralkar

​

Trust <-> Anomalies <-> Patterns - example1

161

Trust <-> Anomalies <-> Patterns - example2

162

Same 300 people, re-tweeting the same 500 messages

...

...

P1

P2

P300

T-500

T-1

T-2

Trust <-> Anomalies <-> Patterns

Dong +

163

Roadmap

• Single-node anomalies -> ‘oddball’ ++
• Group anomalies -> ‘copyCatch’ ++

Dong +

164

Single-node anomalies - Problem sketch

Dong +

165

Single-node anomalies - Problem sketch

Dong +

166

Leman Akoglu, Mary McGlohon, Christos Faloutsos:

Oddball: Spotting Anomalies in Weighted Graphs. PAKDD 2010.

​

.

OddBall: approach

1) from each node, extract ‘ego-net’

1.1) extract features

2) Detect patterns:

→ regularities

3) Detect anomalies:

→“distance” to patterns

Dong +

167

ego

ego-net

What is odd?

168

Which features to compute?

169

• N_i: number of neighbors (degree) of ego i
• E_i: number of edges in egonet i

​

​

​

• W_i: total weight of egonet i
• λ_w,i: principal eigenvalue of the weighted adjacency matrix of egonet i

​

Weighted principle eigenvalue

170

λ_w,i = √N = √E = √W

λ_w,i > √N

~ √E, √W

λ_w,i = N ≈ √W

λ_w,i = W

λ_w,i ≈ W

λ_w,i √W

N: #neighbors, W: total weight

details

OddBall: pattern#1

171

slope=2

slope=1

slope=1.35

telemarketer, spammer,

port scanner, “popularity

contests”, etc.

discussion group,

“rank boosting”, etc.

#neighbors N

#edges E

OddBall: pattern#2

172

slope=1

slope=1.08

uniform, robot-like

behavior

high $ vs. #accounts, high $ vs. #donors, etc.

#edges E

total weight W

OddBall: pattern#3

173

slope=1

slope=0.5

slope=0.64

total weight W

largest eigenvalue λ_1,w

OddBall: anomaly detection

174

• can tell what type

of anomaly a node

belongs to

• can quantify “anomalous-ness”

of nodes using score

score_dist = distance to fitting line

score_outl = outlier-ness score

score = func ( score_dist , score_outl )

OddBall: datasets

175

Bipartite graphs: |V| |E|

1. FEC Don2Com 1.6M 2M

2. FEC Com2Cand 6K 125K

3. DBLP Auth2Conf 21K 1M

​

​

Unipartite graphs: |V| |E|

4. BlogNet 27K 126K

5. PostNet 223K 217K

6. Enron 36K 183K

7. AS peering 11K 8K

OddBall at work (Posts)

Dong +

176

#citations

#cross-citations

223K posts

217K citations

POSTS

OddBall at work (FEC)

177

6K candidates

125K checks

OddBall at work (DBLP)

178

#publications

Conclusions - Anomaly detection in graphs

1. Single-node: OddBall (and many more…)

179

NUMEROUS extensions: #1- node-attributes

Nodes have attributes (age, gender, $income, …)

• Leman Akoglu, HanghangTong, Brendan Meeder, Christos Faloutsos: PICS: Parameter-free Identification of Cohesive Subgroups in Large Attributed Graphs. SDM 2012

​

180

NUMEROUS extensions: #2 – time evolving

Time-evolving graphs (who-calls-whom-when)

• EvangelosE. Papalexakis, Christos Faloutsos, Tom M. Mitchell, ParthaPratimTalukdar, Nicholas D. Sidiropoulos, Brian Murphy: Turbo-SMT: Accelerating Coupled Sparse Matrix-Tensor Factorizations by 200x.SDM 2014:
• Miguel Ramos de Araujo, Pedro Manuel Pinto Ribeiro, and Christos Faloutsos, TensorCast: Forecasting with Context using Coupled Tensors, IEEE ICDM 2017 (Best Paper Award)

​

181

NUMEROUS extensions: #3 – w/ labels

Some labels (‘fraud’/’honest’), exist

• Dhivya Eswaran, Stephan Günnemann, Christos Faloutsos, Disha Makhija, Mohit Kumar: ZooBP: Belief Propagation for Heterogeneous Networks. PVLDB 10(5): 625-636 (2017)
• Dhivya Eswaran, Stephan Günnemann, Christos Faloutsos: The Power of Certainty: A Dirichlet-Multinomial Model for Belief Propagation. SDM 2017: 144-152
• Danai Koutra, Tai-You Ke, U. Kang, DuenHorngChau, Hsing-KuoKenneth Pao, Christos Faloutsos: Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms. ECML/PKDD (2) 2011: 245-260

​

182

Roadmap

• Single-node anomalies -> ‘oddball’ ++
• Group anomalies -> ‘copyCatch’ ++

183

Fraud

• Given
• Who ‘likes’ what page, and when
• Find
• Suspicious users and suspicious products

184

CopyCatch: Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks, Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos WWW, 2013.

Fraud

• Given
• Who ‘likes’ what page, and when
• Find
• Suspicious users and suspicious products

185

CopyCatch: Stopping Group Attacks by Spotting Lockstep Behavior in Social Networks, Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos WWW, 2013.

Graph Patterns and Lockstep Behavior

186

Our intuition

• Lockstep behavior: Same Likes, same time

Graph Patterns and Lockstep Behavior

187

Our intuition

• Lockstep behavior: Same Likes, same time

Likes

Graph Patterns and Lockstep Behavior

188

Our intuition

• Lockstep behavior: Same Likes, same time

Suspicious Lockstep Behavior

Likes

MapReduce Overview

189

• Use Hadoop to search for many clusters in parallel:
1. Start with randomly seed
2. Update set of Pages and center Like times for each cluster
3. Repeat until convergence

Likes

Deployment at Facebook

190

​

• CopyCatch runs regularly (along with many other security mechanisms, and a large Site Integrity team)

3 months of CopyCatch @ Facebook

#users

caught

time

Deployment at Facebook

191

Manually labeled 22 randomly selected

clusters from February 2013

Most clusters (77%) come from

real but compromised users

Fake acct

Roadmap

• Single-node anomalies -> ‘oddball’ ++
• Group anomalies -> ‘copyCatch’ ++
• Stealthy attackers?

192

Problem: Social Network Link Fraud�

193

Target: find “stealthy” attackers missed by other algorithms

Clique

Bipartite

core

41.7M nodes

1.5B edges

Problem: Social Network Link Fraud�

Dong +

194

Neil Shah, Alex Beutel, Brian Gallagher and Christos Faloutsos. Spotting Suspicious Link Behavior with fBox: An Adversarial Perspective. ICDM 2014, Shenzhen, China.

Target: find “stealthy” attackers missed by other algorithms

Takeaway: use reconstruction error between true/latent representation!

Numerous extensions - #1: SVD-based

• B. Aditya Prakash, Ashwin Sridharan, Mukund Seshadri, Sridhar Machiraju, Christos Faloutsos: EigenSpokes: Surprising Patterns and Scalable Community Chipping in Large Graphs. PAKDD (2) 2010: 435-448
• Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, ShiqiangYang: Inferring Strange Behavior from Connectivity Pattern in Social Networks. PAKDD (1) 2014: 126-138

​

195

Numerous extensions - #2: dense-blocks

Camouflage

• Bryan Hooi, Hyun Ah Song, Alex Beutel, Neil Shah, KijungShin, Christos Faloutsos: FRAUDAR: Bounding Graph Fraud in the Face of Camouflage. KDD 2016: 895-904
• Kijung Shin, Bryan Hooi, Christos Faloutsos: M-Zoom: Fast Dense-Block Detection in Tensors with Quality Guarantees. ECML/PKDD (1) 2016: 264-280

​

196

Conclusions - graph anomaly detection

• Single-node anomalies -> ‘oddball’ (PICS, ++)

​

• Group anomalies -> ‘copyCatch’ (SVD, Fraudar, ++)

Dong +

197

Fact Checking from Text

Xin Luna Dong, Christos Faloutsos

Xian Li, Subhabrata Mukherjee, Prashant Shiralkar

​

Fact Checking from Text: Outline

• Motivation
• Models
• Graph Algorithms
• Probabilistic Graphical Models
• Neural Networks
• Automated Fact-Checker

Fact Checking:

Textual Statements

​

Does solar panels really drain the sun of energy?

Where can we find textual statements?

Misinformation and Fake news impact policies, regulations, induce polarization, etc.

Recap: How to Check?

Statement

(Obama, born_in, Hawaii) True / False ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Trustworthy source ?

Correlation of sources?

Objective evidence?

Related evidence?

Up-to-date evidence?

Joint interaction between statement, evidence and its source!

Obama, born_in, Hawaii True / False ?

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Trustworthy source ?

Objective piece of evidence ?

Trustworthy sources generate credible statements

Credible statements are obtained from trustworthy sources

Credible statements are objective

Credible statement ?

Joint interaction between statement, evidence and its source!

Key Intuitions

Data Format

Key Difference with Structured Data and Graph

Desiderata: Leverage Text

• Explore rich semantics and context of statements and evidence
• Analyze subjectivity / objectivity of evidence
• Explore topics, topic - specific reliabilities of sources, stance, ...
• Deep text understanding
• ...

Methods Covered in this Talk

x

Statements as Triples

A statement is a triple of the form <S, V, O>: where S is the subject, V is a verbal phrase, and O is the object.

For example, <Obama, born_in, Hawaii> and <Obama, graduated_from, Harvard> are True statements. However, the triple <Obama, president_of, India> is not.

​

Problem Statement: Given a set of triples from different sources, identify which ones are True or False

Methods Covered in this Talk

x

Recipe 1/4: Gather Evidence

1. What could be alternative fact candidates ?
1. Given a triple <Obama, Born_In, Kenya> alternative candidates are:
1. < Obama, BornIn, * > perturb Obj
2. < * , BornIn, Kenya > perturb Subj
2. Search for answers in other resources using the above patterns

Ndapa Nakashole and Tom Mitchell:

Language-Aware Truth Assessment of Fact Candidates. In ACL, 2015.

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Recipe 2/4: Evaluate Evidence

Objective sources are more trustworthy than subjective sources.

Alternative statements in objective sources are more likely to be true than those stated in subjective sources.

​

​

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Recipe 2/4: Evaluate Evidence

2. Find “objectivity score” of a statement as aggregation over “objective score” of the documents mentioning the fact.

​

1. Learn an objectivity classifier using features

Recipe 3/4: Model Joint Interaction

Alternative statements mentioned in similar sources have similar credibility

f_i : Statement

D_i : Document mentioning f_i

O(.) : Objectivity score

w_ij : avg. objectivity scores of documents mentioning statements

​

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

f_i

f_j

w_ij

Recipe 3/4: Model Joint Interaction

Alternative statements mentioned in similar sources have similar credibility captured by w_ij

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

f_i

f_j

w_ij

Pagerank-style iteration till convergence

Main Results: Accuracy of KB Fact Candidates

• FactChecker obtains 70% - 88% accuracy
• Outperforms other methods by 8% - 10% (except comp. acquisitions)

Drawbacks

Does not model source

​

Statement

Variation 1:Two-layer Framework

Obama, born_in, Hawaii True / False ?

Wikipedia

Trustworthy source ?

Credible statement ?

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

VGV Vydiswaran, ChengXiang Zhai, Dan Roth:

Content-driven Trust Propagation Framework. In KDD, 2011.

Variation 2: Three-layer Framework

Obama, born_in, Hawaii True / False ?

Wikipedia

"Certificate of Live Birth: Barack Hussein Obama II, August 4, 1961, 7:24 pm, Honolulu"

Trustworthy source ?

Objective piece of evidence ?

Credible statement ?

Source-Evidence (Trustworthiness of source for evidence)

Evidence-Claim (Relevance of evidence for a claim)

​

VGV Vydiswaran, ChengXiang Zhai, Dan Roth:

Content-driven Trust Propagation Framework. In KDD, 2011.

Variation 2 (contd.): Capturing Evidence Text

• difference with fact-checking in structured data

Incorporate various text-based scores in edge weights like:

• Similarity in evidence (e.g., duplicates or near duplicates)
• Cosine similarity between text documents
• Topic-based similarity etc.

​

Evidence-Evidence (Content Equivalence)

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Graph Propagation

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

score(claim_i) = Aggr(score(evidence_j))

score(source_i) = Aggr(score(claim_j))

score(evidence_i) = Aggr(score(evidence_j))

Main Results

NDCG values for ten topics in Politics from NewsTrust.net

Three layer model with evidence-evidence interplay better than two layer models

Drawbacks

Does not model subjectivity / emotionality in text

• Common in posts in social media in user-contributed content

Does not exploit supervision information

Drawbacks

Does not model subjectivity / emotionality in text

• Common in posts in social media in user-contributed content

Does not exploit supervision information

Focus of next work!

Methods Covered in this Talk

x

Use-case: Identifying rare or unobserved side-effects of drugs from user posts in online health forums

​

226

Problem: Given a set of posts from different users, extract credible statements (DrugX_HasSideEffect_Y) from trustworthy users

Subhabrata Mukherjee, Gerhard Weikum, Cristian Danescu-Niculescu-Mizil:

People on Drugs: Credibility of User Statements in Health Communities. In KDD, 2014

Recipe 1/4: Gather evidence

​

227

• Statements are triples of the form: DrugX-HasSideEffect_Y e.g., Xanax_causes_Hallucination
• Evidence comes from multiple users reporting the statements in different (writing) styles

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Recipe 3/4: Joint Interaction by Probabilistic Graphical Models

Credible statements appear in objective posts

Trustworthy users corroborate on credible statements in objective language

​

• Each user, post, and statement is a random variable with edges depicting interactions

User post

Post statement

User statement in post

​

• Variables have observable features (e.g, authority, emotionality, subjectivity)

​

How to complement expert knowledge with large-scale non-expert data?

1. Estimate user trustworthiness

2. Estimate label of unknown statements by Gibbs Sampling

3. Maximize log-likelihood to estimate feature weights

4. Apply E-Step and M-Step till convergence

Subhabrata Mukherjee, Gerhard Weikum, Cristian Danescu: KDD 2014

Partial Supervision: Expert stated (top 20%) side-effects of drugs as training labels

Model predicts labels of unobserved statements.

What constitutes objective language?

230

determiner (this, that,..)

negation (not, never, ..)

second person (you, ..)

conjunction (therefore, consequently, ..)

contrast (despite, though, ..)

question (what, why, ..)

conditional (if)

adverb (maybe, probably, ..)

modality (might, could, ..)

Discourse and Modalities

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

What constitutes objective language?

231

Affective Emotions from WordNet-Affect

confidence

sympathy

self-esteem

eagerness

coolness

compunction

anxiety

embarrassment

misery

distress

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Finding drug side-effects from users’ posts

CRF captures joint interactions via cliques as opposed to SVM

Drawbacks

Does not model Topics of discussion

• Topic-specific expertise of users and sources

Conditional Random Fields cannot be used for numeric output / Regression

Next Work

1. Model Topics of discussion
1. Topic-specific expertise of users and sources

2. Extend Conditional Random Fields for numeric output / Regression

3. Extend techniques to deal with short documents

Credibility Rating of Articles in News Communities (e.g. Digg, Reddit)

235

Topics

​

Climate Change

​

Sources

trunews.com

​

Articles

Global warming is a hoax ?

​

Sources / Users

Scientificamerican.com

snopes.com

user-donald

Reviews & Ratings

scientific analysis, 1.5/ 5,

conspiratory theory

​

Subhabrata Mukherjee and Gerhard Weikum:

Leveraging Joint Interactions for Credibility Analysis in News Comm. In CIKM, 2015

Credibility Rating of Articles in News Communities (e.g. Digg, Reddit)

236

Topics

​

Climate Change

​

Sources

trunews.com

​

Articles

Global warming is a hoax ?

​

Sources / Users

Scientificamerican.com

snopes.com

user-donald

Reviews & Ratings

scientific analysis, 1.5/ 5,

conspiratory theory

​

Subhabrata Mukherjee and Gerhard Weikum:

Leveraging Joint Interactions for Credibility Analysis in News Comm. In CIKM, 2015

Problem Statement: Given articles from various sources and feedback from different users: predict credibility rating of articles

Online Communities: Factors

Related to Ensemble Learning, Learning to Rank

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Online Communities: Factors

All models trained on user-assigned ratings to articles and sources

Related to Ensemble Learning, Learning to Rank

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

How to incorporate continuous ratings instead of discrete labels in CRF ?

• We show that a certain energy function for clique potential --- geared for reducing mean-squared-error --- results in multivariate gaussian p.d.f. !!!

​

​

• Constrained Gradient Ascent for inference

239

239

Subhabrata Mukherjee and Gerhard Weikum:

Leveraging Joint Interactions for Credibility Analysis in News Comm.. In CIKM, 2015

Predicting Article Credibility Ratings in Newstrust.net

Progressive decrease in mean squared error with more network interactions, context

Dataset statistics.

Discussions

• What if there is no training label?
• May not be available for all domains
• Unsupervised graph propagation models (discussed earlier)?
• Yes. But they do not model topics
• Cannot capture topic-specific expertise of sources and users

​

Discussions

• What if there is no training label?
• May not be available for all domains
• Unsupervised graph propagation models (discussed earlier)?
• Yes. But they do not model topics
• Cannot capture topic-specific expertise of sources and users

​

Focus of next work!

Fact-checking for Question-Answering

Given a (text) question and a set of (text) answers from different users: find out which answers are true or false

Application Domains:

• Question - Answering communities like Stackoverflow, Reddit, Quora etc.

Generative (Topic) Models for Fact-Checking in QA

​

​

244

Topic

​

Question+ Content

​

Answers +

Content

Users + Expertise

F. Ma, Y. Li, Q. Li, M. Qiu, J. Gao, S. Zhi, L. Su, B. Zhao, H. Ji, and J. Han:

Faitcrowd: Fine-grained Truth Discovery for Crowdsourced Data Aggr. In KDD, 2015

Joint Interactions: Generative Model

• Jointly modeling question content and users’ answers by latent topics.
• Modeling question content help estimate user reliability; modeling answers leads to discovering meaningful topics.
• Learning topic-level user expertise, truths and topics simultaneously

Slide taken from: http://www.acsu.buffalo.edu/~fenglong/files/2015/kdd15_FaitCrowd_slides.pptx

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

Modeling Question Content

Modeling Answers

• Word Generation
• Draw a topic for the question
• Draw a word from the topic of question or a background word

​

​

​

​

​

​

​

• Answer Generation
• Correctness of user’s answer depends on question’s topic, user’s expertise on the topic and question’s bias
• Draw user’s expertise
• Draw the truth
• Draw the bias
• Draw a user’s answer

​

​

​

​

​

​

​

Slide taken from: http://www.acsu.buffalo.edu/~fenglong/files/2015/kdd15_FaitCrowd_slides.pptx

Inference Method

• Gibbs-EM
• Gibbs sampling to learn the hidden variables
• Gradient descent to learn hidden factors

​

​

​

​

​

​

Slide taken from: http://www.acsu.buffalo.edu/~fenglong/files/2015/kdd15_FaitCrowd_slides.pptx

Main Results

FaitCrowd has 11.36% error rate for the most difficult questions compared to 20.45% error rate for baselines

​

Key strength: Modeling topic expertise, question bias,

background word

Statements as Textual Claims

Problem Statement: Given a claim as a sequence of tokens, classify it as True or False

Fact Checking Claims: Datasets with Ground Labels

• Snopes (http://snopes.com/)
• Verifies Internet rumors, hoaxes, and other claims
• Labels (true/fake) along with explanation provided by moderators (editors, journalists, etc.)
• Politifact (http://politifact.com/)
• Similar
• Fact check political statements

Fact Checking Claims: Off-the-shelf Models

Hannah Rashkin, Eunsol Choi, Jin Yea Jang, Svitlana Volkova, Yejin Choi:

Truth of varying shades: Analyzing language in fake news and political fact-checking. In EMNLP, 2017

EMNLP 2017

Drawbacks

Classification using only claim context (as sequence of tokens)

Does not consider interactions between:

• Claim
• Source
• External Evidence

Claim Text

Fact Checking Claims: Neural Networks

E.g., party affiliations, current job, home state, historical counts of lies etc.

​

​

William Yang Wang: liar, liar pants on fire”: A new benchmark dataset for fake news detection. In ACL, 2017

Fact Checking Claims: Neural Networks

Drawbacks

Classification using claim context and source meta-data

Does not consider interactions between:

• Claim -- External Evidence
• Source -- External Evidence

Claim Text

Towards an Automated fact-checker

• Problem statement: Given a claim and (optional) its source: classify the claim as true or false with evidence from the Web

​

Textual Claim

Credibility Assessment

False

True

Evidence

World Wide Web

Source

Key Contributors

• How is the claim reported? – Language style
• Objective v/s subjective, sensationalism
• Does the article support the claim? – Determining stance
• Article can refer to the claim in negated form

“. . . is a mere rumor. . . ”

• Who is reporting the claim? – Web source reliability
• Credible sources provide credible information; BBC v/s The Onion
• Temporal footprint of the claim
• Belief about various claims and how they are discussed keep changing over the time

257

Automated Fact Checker

Kashyap Popat, Subhabrata Mukherjee, Jannik Stroetgen, Gerhard Weikum: Where the Truth Lies: Explaining the Credibility of Emerging Claims on the Web and Social Media.In WWW 2017, WWW 2018 (demo)

Claim Classification Results: Snopes

LG: Language, ST: Stance, SR: Source Reliability

Best model incorporates all the factors!

Does Trend Help?

Trend helps in early detection (as few as 5 days from origin of the claim)

Impact of Evidence on Performance

Automated Fact-Checker with Evidence

Kashyap Popat, Subhabrata Mukherjee, Jannik Stroetgen, Gerhard Weikum: Where the Truth Lies: Explaining the Credibility of Emerging Claims on the Web and Social Media.In WWW 2017, WWW 2018 (demo)

Drawbacks

Does not model:

• Semantics of claim context and evidence
• Relevance of evidence with claim i.e. claim -- evidence interactions

Dependent on rich lexicons and feature engineering

Drawbacks

Does not model:

• Semantics of claim context and evidence
• Relevance of evidence with claim i.e. claim -- evidence interactions

Dependent on rich lexicons and feature engineering

Focus of next work!

DeClarE: Evidence-aware Deep Learning

Kashyap Popat, Subhabrata Mukherjee, Andrew Yates, Gerhard Weikum:

DeClarE: Debunking Fake News and False Claims with Evidence-aware Deep Learning. In EMNLP, 2018

Key Idea is to model the following jointly:

• Learn separate embeddings for
• (i) Claim Text, (ii) Claim Source, (iii) Evidence (Article) Text, (iv) Evidence (Article) Source
• Bidirectional LSTM to model contextual information
• Attention to focus on relevant parts of the evidence (article) w.r.t claim context
• Aggregate and predict

Collect Evidence

Evaluate Evidence

Joint Modeling

Predict Correctness

DeClarE: Framework

Claim Text

Evidence Text

Claim Source

Evidence Source

Credibility Classification on Snopes and PolitiFact

Credibility Classification on Snopes and PolitiFact

Rich lexicons + feature engineering (Distant Supervision) outperforms Declare in Snopes

Source embedding and Attention improves AUC by 2% - 3%

Credibility Regression in NewsTrust

• Declare incurs the least mean squared error (MSE) for rating prediction

Clear Separation between True and Fake Claims

TRUE

FAKE

Clear Separation between Fake and Authentic News Sources

Fake Sources

Authentic Sources

Clusters politicians (speakers of claims) of similar ideologies close to each other in semantic space

Republicans

Democrats

Using Attention to Generate Evidence

[Source] nytimes.com [Evidence] “glimmer of truth, sketchy evidence, hasn’t said, barely true claims”

Summary: Features

• How to evaluate credibility of evidence?
• Content, Writing Style
• Topics
• Linguistic Markers
• How to evaluate trustworthiness of source?
• Topic-specific expertise
• Temporal Trend
• Stance

Summary: Models

• Joint interaction between several factors lead to the best model
• Graphical models capture interplay between several factors
• Generative models capture interplay between latent and observed factors
• (Partial) Supervision helps ground the models
• Evidence generation for interpretable explanation

Resources

Papers, Datasets, Slides, etc available from:

• http://bit.do/credibility-analysis
• https://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/impact/

Upcoming workshop FEVER

The First Workshop on Fact Extraction and Verification, EMNLP 2018, Brussels

Consider submitting your work!

References covered:

• F. Ma, Y. Li, Q. Li, M. Qiu, J. Gao, S. Zhi, L. Su, B. Zhao, H. Ji, and J. Han. Faitcrowd: Fine grained truth discovery for crowdsourced data aggregation. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 745–754, New York, NY, USA, 2015. ACM.
• S. Mukherjee and G. Weikum. Leveraging joint interactions for credibility analysis in news communities. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management (CIKM 2015), 2015.
• S. Mukherjee, G. Weikum, and C. Danescu-Niculescu-Mizil. People on drugs: Credibility of user statements in health communities. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, pages 65–74, New York, NY, USA, 2014. ACM.
• N.Nakashole and T.M. Mitchell. Language-Aware Truth Assessment of Fact Candidates. Acl, pages 1009–1019, 2014.
• J. Pasternack and D. Roth. Latent credibility analysis. In 22nd International World Wide Web Conference, WWW ’13, Rio de Janeiro, Brazil, May 13-17, 2013, pages 1009–1020, 2013.
• K. Popat, S. Mukherjee, J. Stroetgen, and G. Weikum. Where the Truth Lies: Explaining the Credibility of Emerging Claims on the Web and Social Media. WWW (Companion Volume), pages 1003–1012, 2017.
• K. Popat, S. Mukherjee, A. Yates, G. Weikum: DeClarE: Debunking Fake News and False Claims with Evidence-aware Deep Learning. EMNLP, 2018
• H. Rashkin, E. Choi, J. Y. Jang, S. Volkova, and Y. Choi. Truth of varying shades: Analyzing language in fake news and political fact-checking. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2921–2927. Association for Computational Linguistics, 2017.
• V. V. Vydiswaran, C. Zhai, and D. Roth. Content-driven trust propagation framework. In Proceedings of the 17th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining, KDD ’11, pages 974–982, New York, NY, USA, 2011. ACM.
• W. Y. Wang. ”liar, liar pants on fire”: A new benchmark dataset for fake news detection. In ACL (2), pages 422–426. Association for Computational Linguistics, 2017.