Learning Edge Representations via Low-Rank Asymmetric Projections

Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou

Prepared for ACM CIKM 2017, Singapore

1

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

2

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

3

Graph Embeddings -- What are they?

• Given graph G=(V, E):

​

​

• Embedding nodes == representing them in a continuous vector space:

4

v₁

v₂

v₃

v₅

v₄

v₆

v₁₁

v₉

• Nodes are “close” in vector space, if they are “neighbors” in the graph.
• Vector space should preserve structure of graph

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

5

Graph Embeddings -- Why are they needed?

• Graphs contain discrete relationships (e.g. adjacency list)
• Most Modern Machine Learning (ML) Methods accept continuous inputs
• Graph Embeddings is a way to represent it in continuous domain, such that it can be plugged into ML methods, examples include:
• Node Classification
• Edge Classification
• Link Prediction [this paper’s focus]

6

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

7

Graph Embedding -- How are they learned?

• Pre-deep learning era includes Laplacian Eigenmaps [1]:

​

​

Where:

• Y is embedding matrix (aka embedding dictionary)
• A is adjacency matrix.

8

[1] Belkin & Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. NIPS 2001

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

9

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

10

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

11

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Random Walk

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

12

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Random Walk

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

…

...

Random Walk Sequences

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

13

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Random Walk

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

…

...

Random Walk Sequences

word2vec algorithm

Graph Embedding -- How are they learned?

Deep learning era brought Deepwalk [2]: simulates random walks then uses word2vec-style [3] learning to learn embeddings.

14

[2] Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Random Walk

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

…

...

Random Walk Sequences

word2vec algorithm

Embeddings Y

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

15

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

16

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

​

Random Walk Sequences

Embeddings Y

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

17

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

​

Random Walk Sequences

Embeddings Y

anchor

node

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

18

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

​

Random Walk Sequences

Embeddings Y

anchor

node

context node

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

19

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

v₃ → v₅ → v₉ → v₁₁ → v₅ → ...

​

Random Walk Sequences

Embeddings Y

anchor

node

context node

Stochastic Update

Graph Embedding -- How are they learned?

• Word2vec [3] learns word embeddings by stochastically moving embedding of an anchor word closer to a neighboring context word.

E.g. increase

dot-product of embeddings

20

[3] Mikolov et al. Distributed Representations of Words and Phrases and their Compositionality. NIPS 2013

​

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

21

Weaknesses of existing methods

• Edge function is symmetric, with dist(u, v) = dist(v, u)
• This loses directed edge information
• They require large embedding dictionaries to preserve the graph structure. Sometimes larger than the original graph.

22

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

23

Our Method: TLDR

We extend existing methods in several ways:

• In addition to node embeddings, we learn an edge function, in the node embedding space.
• Our edge function is asymmetric: dist(u, v) ≠ dist(v, u)
• Better encodes directed graphs
• We propose novel objective: Graph Likelihood.
• Modelling an edge function, and training with our novel objective, we preserve the structure of the graph much better while using much smaller space.

24

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

25

Our Method: Model Architecture

26

v

Graph

u

Our Method: Model Architecture

27

v

Y_v

Y_u

u

Graph

Node

Embeddings

Our Method: Model Architecture

28

v

Y_v

f

f(Y_v)

Y_u

f

f(Y_u)

u

DNN

​

Node

Embeddings

Graph

Our Method: Model Architecture

29

v

Y_v

f

f(Y_v)

Y_u

f

f(Y_u)

u

DNN

​

Node

Embeddings

Graph

Our Method: Model Architecture

30

v

Y_v

f

f(Y_v)

^T

R

Y_u

f

f(Y_u)

^T

L^T

u

DNN

​

Node

Embeddings

Graph

Low-Rank Asymmetric Projection

​

Our Method: Model Architecture

31

v

Y_v

f

f(Y_v)

^T

R

Y_u

f

f(Y_u)

^T

L^T

u

DNN

​

Node

Embeddings

Low-Rank Asymmetric Projection

​

Dest

L^Tf(Y_u)

Graph

Edge Representation

​

Source

​

Rf(Y_v)

Our Method: Model Architecture

32

v

Y_v

f

f(Y_v)

^T

R

Y_u

f

f(Y_u)

^T

L^T

σ(g(u, v))

u

DNN

​

Node

Embeddings

Low-Rank Asymmetric Projection

​

Source

​

Dest

L^Tf(Y_u)

Rf(Y_v)

Graph

Edge Likelihood

​

Edge Representation

​

Our Method: Model Architecture

33

v

Y_v

f

f(Y_v)

^T

R

Y_u

f

f(Y_u)

^T

L^T

σ(g(u, v))

u

DNN

​

Node

Embeddings

Low-Rank Asymmetric Projection

​

Source

​

Dest

L^Tf(Y_u)

Rf(Y_v)

Graph

Edge Likelihood

​

Edge Representation

​

Left Embedding

(projection)

Right Embedding

(projection)

​

DeepWalk versus ours

DeepWalk [2]

Ours

34

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

35

Our Method: Graph Likelihood Derivation

• Assume that Q is an edge estimator.
• If Q is “perfect”, then likelihood below must equal to 1 when evaluated on E:

​

​

36

Our Method: Graph Likelihood Derivation

• Assume that Q is an edge estimator.
• If Q is “perfect”, then likelihood below must equal to 1 when evaluated on E:

​

​

• Equation above can be written as:

​

37

Our Method: Graph Likelihood Derivation

38

Our Method: Graph Likelihood Derivation

39

Graph Likelihood

Non exclusive!

is frequence of u and v are co-visited in random walks

Our Method: Graph Likelihood Derivation

40

Graph Likelihood

Our Method: Graph Likelihood Derivation

41

Graph Likelihood

Our Method: Training

• Our Graph Likelihood objective is quadratic:

​

​

• Instead, we optimize a linear objective. We simulate random walks for positives, and we use noise estimation for negatives. We optimize:

• We train using PercentDelta [7]

[7] Abu-El-Haija, Proportionate Gradient Updates with PercentDelta, 2017

42

where

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

43

Link Prediction Experiments

E

44

Link Prediction Experiments

E

E_train+

E_test+

45

Link Prediction Experiments

E

E_train+

E_train-

E_test+

46

Link Prediction Experiments

E

E_train+

E_train-

E_test-

E_test+

|E_train+| = |E_test+| = |E_train-| = |E_test-|

47

Why Link Prediction?

• We aim to produce structure-preserving embeddings.
• Embeddings that preserve the graph structure, should be able to reconstruct the input graph, generalizing to unseen edges.
• Application across many domains, including social and e-commerce.

48

Link Prediction Results

Sampled softmax

Graph Likelihood Objective

ca-AstroPh [5]

Protein-Protein Interaction [6]

49

[5] http://snap.stanford.edu/data

[6] Stark et al. BioGRID: A General Repository for Interaction Datasets. Nucleic Acids Research 2006.

Link Prediction Results

Datasets from [5, 6]

50

[5] http://snap.stanford.edu/data

[6] Stark et al. BioGRID: A General Repository for Interaction Datasets. Nucleic Acids Research 2006.

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

51

Our Method: Visualization of Learned Embeddings

Embedding Protein-Protein Interaction graph dataset [6] using asymmetric projection of 2 dimensions.

Right Projection

Left Projection

52

Our Method: Visualization of Learned Embeddings

Right & Left Projections

53

Our Method: Visualization of Learned Embeddings

Pick node and show is edges

54

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

55

Our Method: Implementation

Code will be at: sami.haija.org/graph/deep_embedding.html

# Create train/test positive/negatives and simulate random walks:

$ python create_dataset_arrays.py --input ~/data/mygraph.txt \

--output ~/data/mygraph_arrays

​

# Train node embeddings and edge representation

$ python deep_edge_trainer.py --dataset_dir ~/data/mygraph_arrays

​

56

Outline

• Background: Graph Embeddings
• What are they?
• Why are they needed?
• How are they learned?
• Weaknesses of existing methods
• Our Method
• Model Architecture
• Objective Function & Training
• Linked Prediction Experiments
• Visualization of Learned Embeddings
• Implementation
• Conclusion

57

Conclusion

• We train node embeddings jointly with an edge function.
• Our edge function is a (deep) asymmetric projection in the node embedding space.
• We train using our novel objective (Graph Likelihood).
• Training with an edge function and using our objective show relative error reductions of up to 63% (directed) and 15% (undirected), while using 16x smaller representations.
• Our code and data-splits will be available on github, accessible thru sami.haija.org/graph/deep_embedding.html

58

Thank you!

Any Questions?

59

Backup Slides

60

Link Prediction Results

Note: We ran node2vec using their default context window size (C=10).

Datasets from [5, 6]

61

[5] http://snap.stanford.edu/data

[6] Stark et al. BioGRID: A General Repository for Interaction Datasets. Nucleic Acids Research 2006.

Model Discussion: Can we skip f() ?

?

?

Skipping f() will hurt the generalization performance of the model, since:

1. Overfitting without f()
2. f() is a regularizer.

Tables on next slide!

62

Model Discussion: Can we skip f() ?

Shallow = without f()

Deep = with f()

63

Visualization: soc-facebook [5] dataset (spherical constraints)

64

[5] http://snap.stanford.edu/data

65