1 of 87

GNN Applications-I

Knowledge Graphs

2 of 87

https://kge-tutorial-ecai2020.github.io/

Knowledge Graph Embedding: A Survey of Approaches and Applications, Wang et al. IEEE TKDE, 2021

https://www.youtube.com/watch?v=xop5tC9T5xM

Prof. Jure Leskovec Lectures

https://www.youtube.com/watch?v=Xm5VrxZYhu4

https://www.youtube.com/watch?v=X9yl0pTP9fY

https://www.youtube.com/watch?v=qaRIBNE-4Ho

https://www.youtube.com/watch?v=Nt66M2OsbCw

3 of 87

Resources

  • Knowledge Graph Embedding: A Survey of Approaches and Applications, Wang et al. IEEE TKDE, 2021

4 of 87

Knowledge Graphs

 

Wikidata

DbPedia

Microsoft Satori

LinkedIn KG

Freebase

5 of 87

Knowledge Graph Embedding

Typical Embedding Steps:

1) Representing entities and relations [Vector, Matrices, Gaussian Distribution, complex space]

 

3) Learning entity and relation representations [maximize the total probability of the observed facts]

6 of 87

Relationships as translations in the embedding space

7 of 87

Translational Distance Models: TransE

Relationships as translations in the embedding space

 

 

 

 

 

Sundar Pichai + CEOof

 

Alphabet_Inc.

Satya_Nadella + CEOof

 

Microsoft

 

 

8 of 87

TransE Training

  •  

https://gombru.github.io/2019/04/03/ranking_loss/

9 of 87

TransE Training

  •  

10 of 87

TransE Training

  •  

11 of 87

TransE Limitations

  •  

12 of 87

Relation Types in KGs

  •  

13 of 87

Relation Types in KGs

  •  

14 of 87

TransE and Relation Types

Antisymmetric

Symmetric

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15 of 87

TransE and Relation Types

1-to-N

N-to-1

 

 

 

Cannot model 1-to-N

 

Cannot model N-to-1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

16 of 87

TransE and Relation Type

 

 

 

 

 

Can model inverse relation

 

 

 

 

 

 

 

 

 

 

Can model relation composition

17 of 87

Separate out Entity Space and Relation Space

 

 

 

 

 

 

 

 

 

 

18 of 87

TransR: Translation in Relation Space

  •  

19 of 87

TransR

 

 

 

 

 

 

 

 

 

 

 

20 of 87

TransR: Symmetric Property

 

 

 

 

 

 

 

 

 

 

 

 

TransR can model symmetric property

21 of 87

TransR: Asymmetric Property

 

 

 

 

 

 

 

 

 

 

 

TransR can model asymmetric property

22 of 87

TransR: 1-to-N Property

 

 

 

 

 

 

 

 

 

TransR can model 1-to-N property

 

23 of 87

TransR: Inverse Property

 

 

 

 

 

 

 

 

 

TransR can model inverse property

 

 

 

24 of 87

TransR: Relation Composition

  •  

25 of 87

Similarity-based scoring function of a triple

26 of 87

Semantic Matching Energy (SME)

27 of 87

Semantic Matching Energy (SME)

  •  

28 of 87

Neural Tensor Network (NTN)

29 of 87

Neural Tensor Network (NTN)

  •  

30 of 87

Neural Tensor Network (NTN)

 

 

 

 

 

 

 

 

 

 

 

31 of 87

Neural Tensor Network (NTN)

Scoring Function

 

Combined representation

head representation

tail representation

32 of 87

Multi Layer Perceptron (MLP)

 

 

 

33 of 87

Neural Association Model (NAM)

 

 

 

 

 

Deep Architecture

34 of 87

KG Completion Task and KG Embedding

Source: Jure Leskovec

35 of 87

Most of the slides are adopted from Jure Leskovec

36 of 87

Reasoning over Knowledge Graphs

  • Goal
    • How to perform multi-hop reasoning over KGs?
  • Reasoning over knowledge graphs
    • Answer multi-hop queries
      • Path queries
      • Conjunctive queries
    • Query2box

​

37 of 87

Example KG: Biomedicine

38 of 87

Queries on KG

  • One-hop query
    • What adverse event is caused by Fulvestrant?
    • (e:Fulvestrant, (r:Causes))
  • Path Query
    • What protein is associated with the adverse event caused by Fulvestrant?
    • (e:Fulvestrant, (r:Causes, r:Assoc))
  • Conjunctive Query
    • What is the drug that treats breast cancer and caused headache?
    • ((e:BreastCancer, (r:TreatedBy)), (e:Migraine, (r:CausedBy))

39 of 87

Answering One-hop Queries

  • We can formulate knowledge graph completion problems as answering one-hop queries.

 

 

 

 

 

What side effects are caused by drug Fulvestrant?

40 of 87

Answering Path Queries

  •  

41 of 87

Answering Path Queries

  •  

42 of 87

Answering Path Queries

  • Query: (e:Fulvestrant, (r:Causes, r:Assoc))

Fulvestrant

Headache

Brain Bleeding

Short of

Breath

Kidney

Infection

Start from the anchor node “Fulvestrant” and

traverse the KG by the relation “Causes”, we

reach entities {“Brain Bleeding”, “Short of

Breath”, “Kidney Infection”, “Headache”}.

Causes

43 of 87

Answering Path Queries

  • Query: (e:Fulvestrant, (r:Causes, r:Assoc))

Fulvestrant

Headache

Brain Bleeding

Short of

Breath

Kidney

Infection

CASP8

BIRC2

PIM1

Start from the nodes {“Brain Bleeding”, “Short of Breath”, “Kidney Infection”, “Headache”} and traverse the KG by the

relation “Assoc”, we reach entities {“CASP8”, “BIRC2”, “PIM1”}. These are the answers.

Answers

44 of 87

KGs are Incomplete ☹

  • KGs are incomplete and unknown
  • Many relations between entities are missing or are incomplete
    • For example, we lack all the biomedical knowledge
    • Enumerating all the facts takes non-trivial time and cost, we cannot hope that KGs will ever be fully complete
  • Due to KG incompleteness, one is not able to identify all the answer entities

45 of 87

KGs are Incomplete ☹

  • Query: (e:Fulvestrant, (r:Causes, r:Assoc))

​

46 of 87

KG Completion to Fill up the Gap?

  •  

47 of 87

Predictive Query

  • Strategy to answer path-based queries over an incomplete knowledge graph.
    • Implicitly impute and account for the incomplete KG.
  • Predictive Queries
    • Want to be able to answer arbitrary queries while implicitly imputing for the missing information
    • Generalization of the link prediction task

48 of 87

General Intuition

  • Map queries into embedding space. Learn to reason in that space
    • Embed query into a single point in the Euclidean space: answer nodes are close to the query.
    • Query2Box: Embed query into a hyper-rectangle (box) in the Euclidean space: answer nodes are enclosed in the box.

49 of 87

Traversing KG in Vector Space

  •  

50 of 87

Traversing KG in Vector Space

51 of 87

Traversing KG in Vector Space

  •  

52 of 87

Traversing KG in Vector Space

  • Query: (e:Fulvestrant, (r:Causes, r:Assoc))

​

​

​

53 of 87

Conjunctive Queries

  • Can we answer more complex queries with logic conjunction operation?
  • Conjunctive Queries:
    • What are drugs that cause Short of Breath and treat diseases associated with protein ESR2?
    • ((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))

54 of 87

Conjunctive Queries

((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))

​

55 of 87

Conjunctive Queries

 

Existential Positive First-order (EPFO) logical queries

56 of 87

Traversing KGs for Conjunctive Queries

What are drugs that cause Short of Breath and treat diseases associated with protein ESR2?”

​

((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))

57 of 87

Traversing KGs for Conjunctive Queries

What are drugs that cause Short of Breath and treat diseases associated with protein ESR2?”

​

((e:ESR2, (r:Assoc, r:TreatedBy)), (e:Short of Breath, (r:CausedBy))

58 of 87

Traversing KGs for Conjunctive Queries

How can we use embeddings to implicitly impute the missing (ESR2, Assoc, Breast Cancer)?

Intuition: ESR2 interacts with both BRCA1 and ESR1. Both proteins are associated with breast cancer.

59 of 87

Traversing KGs for Conjunctive Queries

Each transformation gives us a set of entities. How to represent these sets?

How do we define the intersection operation in the latent space?

60 of 87

Set Representation: Box Embedding

  •  

61 of 87

Representation with Box Embedding

  •  

62 of 87

Projection Operator for Traversal

  •  

 

 

63 of 87

Projection Operator for Traversal

  • Use projection operator again following the query plan.

64 of 87

Perform Intersection

65 of 87

 

  •  

66 of 87

 

  •  

 

 

 

 

Element-wise product or

Hadamard product

67 of 87

 

  •  

 

Sigmoid function: squashes output in (0,1)

 

68 of 87

After Applying Intersection Operator

69 of 87

The Score Function

 

 

 

 

 

 

 

 

70 of 87

Answering Disjunctive Queries

  • Disjunctive queries
    • What drug can treat breast cancer or lung cancer?
  • AND-OR Queries [EPFO Queries]
    • Conjunctive + Disjunctive Queries
  • Can we design disjunction operator (Union) and embed AND-OR queries in low-dimension space?

71 of 87

Answering Disjunctive Queries

  •  

72 of 87

Answering Disjunctive Queries

  •  

 

 

73 of 87

Answering Disjunctive Queries

  • We cannot embed AND-OR queries in low dimension space
    • But we will be able to handle them

Algo in Query2Box paper

74 of 87

Answering Disjunctive Queries

  •  

75 of 87

Answering Disjunctive Queries

  •  

76 of 87

Training Query2Box

  •  

77 of 87

Training Algorithm

  •  

78 of 87

How to Generate Training Data?

Generate training data from multiple query templates

79 of 87

Query Template to Query

80 of 87

Generation with Backward Inference

81 of 87

Generation with Backward Inference

82 of 87

Generation with Backward Inference

83 of 87

Generation with Backward Inference

84 of 87

Generation with Backward Inference

85 of 87

Generation with Backward Inference

86 of 87

Generation with Backward Inference

87 of 87

Generation with Backward Inference