Shallow Representation Learning

Node Embedding

Unit Objectives

• Introducing node embedding problem
• Embedding in simple graphs
• Embedding in complex graphs

Node Embedding

• Node Embedding
• Low dimensional vector representation of a node
• Preserves some properties of the node in original graph
• Node in two domains
• Graph domain: nodes and their connections
• Embedding domain: node as a continuous vector
• Node embedding as mapping
• Mapping a node from the graph domain to the embedding domain

Embedding Methods: Intuition

A good node representation should be able to reconstruct information that is desired to be preserved

mapping

Extractor

Reconstructor

Objective: Reconstruction Loss

Node Embedding: Visual Example

Input

Output

Zachary’s Karate Club Graph

Graph Embedding

Simple Graphs

Node Co-occurrence

Structural Role

Node status

Community Structure

Complex Graphs

Heterogeneous Graphs

Bipartite Graphs

Multi-dimensional Graphs

Signed Graphs

Hypergraphs

Dynamic Graphs

Embedding Simple Graphs

Node Co-occurrence Methods

Notions of Co-occurrence

… if the degree distribution of a connected graph follows a power law, we observe that the frequency which vertices appear in the short random walks will also follow a power-law distribution …

Language

Co-occurrence is the basis of fundamental representations in NLP: Vector representation of words or neural language models

Notion of Co-Occurrence

Source: School of Information, Pratt Institute

Co-Authorship Network

An author is connected to limited set of authors

This can be used as a notion of Co-occurrence

Can we use learn node representations that preserves the co-occurrence relations in the network?

Language Models

Word Frequency in Natural Language

Word frequency in natural language follows a power law

Slide from Bryan Perozzi et al.

The second most used word appears half as often as the most used word.

The third most used word appears one-third the number of times the most used word appears, and so on

Connection: Language and Graphs

Scale Free Graph

Artificial Language: Short truncated random walks as sentences

Random Walk on Graph

Short random walks

Vertex frequency in random walks on

scale free graphs also follows a power

law.

Connection: Language and Graph

• Learning Word Representation
• Learn a dense representation of words so that the word co-occurrence information is preserved
• Learning Node Representation
• Learn dense representation of the nodes in the graph such that node neighborhood information (community structure) in the graph is preserved

Language Model in Concrete Terms

The Problems

The Hope

• Solving the optimization problem builds representations that capture the shared similarities in local graph structure between vertices
• Vertices which have similar neighborhoods will acquire similar representations (encoding co-citation similarity)

DeepWalk

DeepWalk: Online Learning of Social Representations, Perozzi et al., KDD’14

DeepWalk Method

1) Input graph

3) Representation Mapping

4) Hierarchical Softmax

5) Output: Representation

2) Random Walks

SkipGram: Details

Random Walks

Otherwise

https://towardsdatascience.com/node2vec-explained-graphically-749e49b7eb6b

Learning the Parameters

Learning Objective

Learning Objective (Cntd..)

Learning Objective (Cntd …)

SkipGram Architecture

• Two approximation techniques to speed-up
• Hierarchical Softmax
• Negative Sampling

Hierarchical Softmax

Hierarchical Softmax

Hierarchical Softmax

Algorithm

Negative Sampling

Negative Sampling

Negative sampling

Supervised Learning: Logistic Regression Model

Objective Function

Sampling Distribution

Selecting Negative Samples

Increases the probability of choosing low degree nodes

Empirical frequency

Social and Structural Aspect

node2vec

node2vec: Scalable Feature Learning for Networks, Grover and Leskovec, SIGKDD’16

Node2vec Objective

• The Goal: Embed nodes with similar neighborhoods are also close in the feature space
• Nodes belonging to the same community
• Nodes having similar neighborhood profile
• Unsupervised: Maximum likelihood estimation
• Require redefining neighborhood function that is flexible to cover both the aspects

Biased Random Walk

Local microscopic view

Global macroscopic view

BFS - DFS Tradeoff with Interpolation

Biased (2^nd Order) Random Walk

First order random walk probability:

Second order biased random walk probability:

Simulating BFS vs DFS

DFS

BFS

Performance Comparison

Performance Comparison

Multi-Label Node Classification (Macro-F1 scores)

Performance Comparison

(a)

(b)

(c)

(d)

Link Prediction(AUC scores)

struc2vec

struc2vec: Learning Node Representations from Structural Identity, Ribeiro et al., KDD’17

Representation Context

Similar degree values – 5 and 4

Connected to similar no of triangles – 3 and 2

Connected to the rest of the network by two nodes

struc2vec: Core Ideas

• Model structural similarity independent of edge and node attributes and position in the network
• Two nodes having similar local structure
• Notion of similarity is hierarchical
• At bottom, depends only on node degree
• At top, entire network from the viewpoint of a node
• Generate contexts using random walks on multilayer graph
• Two nodes appearing in similar contexts will likely have similar structure

struc2vec: Steps

• Step-1: Determine structural similarity between a node pair
• Hierarchical measure for structural similarity
• Assess structural similarity at each level of hierarchy
• Step-2: Construct a weighted multi-layer graph
• Each node is present in every layer
• Each level corresponds to a level in similarity measure hierarchy
• Edge weight between every node pair within each layer is inversely proportional to their structural distance

struc2vec: Steps

• Step-3: Generate context for each node from multi-layer graph
• Biased random walk on the multi-layer graph to generate node seq
• A sequence is likely to include structurally similar nodes
• Step-4: Learning node representation
• Learn latent representation from context (random walk) using techniques like Skipgram

Hierarchical Structural Similarity

• Automorphism: Strong Structural Equivalence

​

​

​

​

• Notion of hierarchy
• Two nodes that have same degree are structurally similar (Level 1)
• If their neighbors also have same degree, they are even more structurally similar (Level 2)

RED, GREEN 🡪 Automorphism

PURPLE, BROWN 🡪 Structurally Similar

Hierarchical Structural Similarity

Hierarchical Structural Similarity

Hierarchical Structural Similarity

Dynamic Time Warping (DWT)

DWT computes element-wise match such that the distance between matched elements are minimized

Hierarchical Structural Similarity

Constructing Multi-Layer Graph (M)

Layer 1

Layer 2

Generate Context from M

Performance

DeepWalk

Node2vec

Struc2vec

Barbell Graph (10,10)

Mirrored Karate Network

DeepWalk

Node2vec

Struc2vec

Classification Performance

Graph Embedding

Simple Graphs

Node Co-occurrence

Structural Role

Node status

Community Structure

Complex Graphs

Heterogeneous Graphs

Bipartite Graphs

Multi-dimensional Graphs

Signed Graphs

Hypergraphs

Dynamic Graphs