On Matching Web-scale
Entity Graphs
Seung-won Hwang
Associate Professor
Department of Computer Science andEngineering
POSTECH, Korea

My Research Mantra•

Web is overloaded with human intelligence trails•

We can mimic social human intelligence by mining such trails•

This talk focuses on trails represented in a form of entity graphs(finer-granularity)– e.g., search logs, clicks– e.g., autoComplete

Motivation

EnglishEntityCube
7/27/2011

ChineseEntityCube(a.k.a, Renlifang)3

Mining Name Translation[CIKM11,EMNLP10]
Joint work with Gae-won You1, Jinhan Kim1
Ming Zhou2, Young-In Song2, Long Jiang2, Zaiqing Nie2
1Pohang University of Science and Technology (POSTECH), Korea
2Microsoft Research Asia (MSRA), China

7/27/20114

(turns out) A novel approach for MT•Name translation: Hard problem in machine translation (MT)– Transliteration-based: low accuracy, 100% coveragee.g., arbitrary mapping, e.g., “Jackie Chan” to “成龙(chénglóng)”– Corpus-based: low coverage, high accuracye.g.:… Bill Gates ….

… 比尔·盖茨 …

… Bill Gates ….

… 比尔·盖茨 …

… 比尔·盖茨 (Bill Gates) ….
7/27/20115Basic Insight• We combine the strength of the two approachesPhonetic similarity
If two names are phonetically similar, they are likely to bea name translation pair
- E.g., “Bill Gates” vs. “比尔·盖茨 ”

Relational similarity
If two names in source language are related, their corres
ponding names are also likely to be related in target language- E.g.,g ((“Jackie Chan”, “Bill Gates” ) vs. (“成龙”,( 龙 “比尔·盖茨 ”))

7/27/2011

6Basic Insights• Relax using bilingual co-occurrence tomonolingual co-occurrence based on relationa
l similarity
Steve Ballmer

Phonetically similar史蒂夫·鲍尔默

Co-occur with

Co-occur with雷·奥兹

Ray Ozzie
Co-occur withBill Gates

7/27/2011

Co-occur with
Phonetically similar比尔·盖茨Neighbors of two entities are similar!
- Relationally similar

7

Step 1: Initialization of Similarity
Matrix• Denote– Ne : Word sequence of given English name,– PYc : Pinyin sequence of Chinese name Nc,• Transliteration similarity can be defined as the edit-distan
ce to measure their spelling similarity:

7/27/20118

Step 2: Reinforcement• Update translation similarity between two entiti
es leveraging the relational similarities

2.
Null
problem:
evennoif twonodes
aretrue translationstranslation, ther
1.
How
Necessity
toalignment
estimate
to align
similarity
neighbors:
betweennameneighbors
has multipleof “RayOzzie” and pair
“雷·奥兹
”?
Align
neighbors neighborof two nodes
e can -benon-matchedpairswith similarity scores- Consider only the neighbor alignment pairs whose similarity > Θ

Craig M
undie

Steve B
allmerRay Ozzi
eBrad S
mith史蒂夫·鲍尔默雷·奥兹比尔·盖茨Bill Gates
7/27/20119

Results – Head/Tail Entities[EMNLP10]• Divide head and tail entities according to # hits in Google; head (top-100 popular) and tail (remaining)

7/27/201110

Missing Quadrant
EntityRelationship

Using names

贝拉克·奥巴马~
Barack Obama(贝拉克·奥巴马, 米歇尔奥巴马)~(Barack Obama,Michelle Obama)

Using context(surrounding words)

总统~president

配偶~spouseA Holistic Approach [CIKM11]

Mining Social Network Accounts[EDBT11, SIGKDD09]
Joint work with Jongwuk Lee1, Gae-won You1
Ji-rong Wen2, Zaiqing Nie2
1Pohang University of Science and Technology (POSTECH), Korea
2Microsoft Research Asia (MSRA), China

7/27/201113

EntityCube and Twitter Network[EDBT11b]

EntityCube and Feature Graph[SIGKDD09]

EntityCube(human perception)

124Clustering results

Feature-based (value locality)
15356

A Big Challenge Under the Rug
EntityCubeProbase
US Presidents such as Bill Clintonand George W. BushUS Presidents
Bill Clinton
William J Clinton
George W. Bush
George H.W. BushDubya

Web-scale Cleansing[VLDB11]
Joint work with Taesung Lee1
Zhongyuan Wang2, Haixun Wang2
1Pohang University of Science and Technology (POSTECH), Korea
2Microsoft Research Asia (MSRA), China

7/27/201117

Positive Evidence••

String similarity
To handle nickname case– Ex) George W. Bush – Dubya– Synonym pairs from known sources – [Silviu Cucerzan, EMNLP-CoNLL
2007, …]
• Wikipedia Redirects• Wikipedia Internal Links – [[ George W. Bush | Dubya ]]• Wikipedia Disambiguation Page
• Patterns such as ‘whose nickname is’, ‘alsoknown as’What If Just Positive Evidence?
• George W. Bush = President Bush+ President Bush = George H. W. Bush=?
Entity Similarity
GraphDubya
George W.
BushBush
Bush Sr.

PresidentBushGeorge H. W.
BushNegative Evidence• What if we know they are different?
It is possible to…
– stop transitivity at the right place– safely utilize string similarity Bush– remove false positive evidenceSr.

Dubya
George W. BushBush• ‘Clean data has no duplicates’ Principle

Different!

PresidentBushGeorge H. W.
Bush– The same entity would not be mentioned in a list ofinstances several times in different forms– We assume these are clean:• ‘List of ***’, ‘Table of ***’• such as …
• Freebase

Two Types of Evidence in Action
Instance Pair Space

Correct Matching Pairs[Evidence]
Wikipedia
Redirect Page
[Evidence]
Wikilinks[Evidence]
Wikipedia
Disambiguation
Page

Negative
Evidence[Evidence]

String Similarity
Negative
EvidenceOur Approach
Dubya

0.9

• Building a graph of entities

George W. Bush

0.6
– Quantifying positive evidence for edge weight
0.6– Noisy-or modelBush•• Using All kinds of positive evidence
including string similarity

0.90.30.6

President BillClinton

0.8

President Bush0.4Hillary Clinton

George H. W. Bush

• Multi-Multiway Cut problem on a graph of entities– A variant of s-t cut– No vertices with the same label may belong to one connectedcomponent (cluster) with a cost function; the sum of removed edge
weights• {George W. Bush, President Bill Clinton, George H. W. Bush},{George W. Bush, Bill Clinton, Hillary Clinton}, …

– Some instance may belong to any of several possible clusters• Bush to George W. Bush, or George H. W. BushBill Clinton

Our method• Checking violation with each ‘monte-carlo’
insertion– Randomly insert one edge at a time withprobability proportional to the weight of edge
– Skip the edge that makes violation• We repeat the random process for a fixed
number of times, and then choose the best
one that minimize the cost; sum of dropped
edge weights

Dubya0.9
George W. Bush

0.9

0.6

0.6
0.6

Bush

0.5

President Bill Clinton

0.3

President Bush

0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6

0.6
0.6

Bush

0.5

President Bill Clinton

0.3

President Bush0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6

0.6
0.6

Bush

0.5

President Bill Clinton

0.3

President Bush

0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6

0.6
0.6

Bush

0.5

President Bill Clinton

0.3

President Bush

0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6
0.6
Bush

0.5

0.3

President Bill Clinton

President Bush

0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6
0.6Bush

0.50.3President Bill Clinton

President Bush

0.4

George H. W. Bush
Bush Sr.

1.0

Dubya0.9
George W. Bush

0.9

0.6
0.6

President Bill Clinton

President BushBush

George H. W. Bush
Bush Sr.

1.0

Experimental Setting• Probase: 16M instances / 2M concepts• Freebase (2010-10-14 dump): 13M instances / 12.7K
concepts• Positive Evidence– String similarity: Weighted Jaccard Similarity– Wikipedia Links: 12,662,226– Wikipedia Redirect: 4,260,412– Disambiguation Pages: 223,171• Negative Evidence (# name bags)– Wikipedia List: 122,615– Wikipedia Table: 102,731– Freebase

Experimental Setting• Baseline #1– Positive evidence (without string similarity) based method.
– Maps two instances with the strongest positive evidence.
If there is no evidence, not mapped.

• Baseline #2– String similarity based method.
– Maps two instances if the string similarity, here Jaro-Winkler
distance, is above a threshold (0.9 to get comparable
precision).

• Baseline #3– Markov Clustering with our similarity graphs– The best method among the scalable clustering methods forentity resolution introduced in [Hassanzadeh, VLDB2009]Some Examples of Mapped
Probase Instances
Freebase
Instance

Baseline #1

Baseline #2

Baseline #3

Our Method

George W. Bush

George W. Bush,
President George
W. Bush, Dubya

George W. Bush

George W. Bush,
President George
W. Bush, George
H. W. Bush,
George Bush Sr.,
Dubya

George W. Bush,
President George
W. Bush, Dubya,
Former President
George W. Bush

American Airlines

American Airlines,
American Airline,
AA, Hawaiian
Airlines

American Airlines,
American Airline

American Airlines,
American Airline,
AA, North
American Airlines

American Airlines,
American Airline,
AAJohn KerryJohn Kerry, Sen.
John Kerry,Senator KerryJohn KerryJohn Kerry,
Senator KerryJohn Kerry, Sen.
John Kerry,Senator Kerry,
Massachusetts
Sen. John Kerry,Sen. John Kerryof Massachusetts

Some Examples of Mapped
Probase Instances• Baseline #1 cannot deal with misspelledinstances and variations  low recall– Massachusetts Sen. John Kerry– Sen. John Kerry of Massachusetts• Baseline #2 produces false positives & shows
weakness on large length variations– George W. Bush ~ George H. W. Bush– Hillary Clinton ~ Bill Clinton• Baseline #3 produces false positives by wrong
transitivity– George W. Bush ~ George H. W. Bush
– American Airlines ~ North American Airlines

Precision / Recall
ProbaseClassPoliticians

Foramts

Systems

AirlineFreebase
Type/government/politician/computer/file_format/computer/operating_system/aviation/airline

Precision

RecallPrecision

RecallPrecision

RecallPrecision

RecallBaseline #1

0.99

0.66

0.90

0.25

0.90

0.37

0.92

0.63

Baseline #2

0.97

0.31

0.79

0.27

0.59

0.26

0.96

0.47

Baseline #3

0.88

0.63

0.82

0.48

0.88

0.52

0.96

0.54

Our method

0.98

0.84

0.93

0.86

0.91

0.59

1.00

0.70

Scalability• Our method (in C#) is compared with
Baseline #3 (Markov Clustering, in C)

Category|V||E|

Companies

662,029

110,313

Locations964,665

118,405

Persons

1,847,907

81,464Books

2,443,573

205,513

Thanks• http://www.postech.ac.kr/~swhwang