1 of 38

Graph Representation Learning

January 31st, 2026

CS60078

2 of 38

Features from Graphs

3 of 38

Traditional ML for Graphs

4 of 38

Graph Representation Learning

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

5 of 38

Graph Representation Learning

Goal: Efficient task-independent feature learning for machine learning with graphs!

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

6 of 38

Why Embedding?

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

7 of 38

Example Node Embedding

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

8 of 38

Setup

Assume we have an (undirected) graph G:

V is the vertex set.
A is the adjacency matrix (assume binary).
For simplicity: No node features or extra information is used

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

9 of 38

Embedding Nodes

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

10 of 38

Connection with Language Modeling

11 of 38

Connection with Language Modeling

12 of 38

Let’s look at representation learning for words

13 of 38

One-hot-encoding

In traditional NLP / IR, words are treated as discrete symbols.

Vector dimension = number of words in vocabulary (e.g., 500,000)

14 of 38

Problems with words as discrete symbols

Example: In web search, if user searches for “Baltimore motel”, we would like

to match documents containing “Baltimore hotel”. But

The vectors are orthogonal, and there is no natural notion of similarity between

one-hot vectors!

Solution: Can we learn to encode similarity in the vectors themselves?

15 of 38

Word Vectors - One-hot Encoding

Suppose our vocabulary has only five words: King, Queen, Man, Woman, and Child.

We could encode the word ‘Queen’ as:

16 of 38

Word2Vec – A distributed representation

17 of 38

Distributional Representation

Take a vector with several hundred dimensions (say 1000).
Each word is represented by a distribution of weights across those

elements.

So instead of a one-to-one mapping between an element in the vector

and a word, the representation of a word is spread across all of the

elements in the vector, and

Each element in the vector contributes to the definition of many words.

18 of 38

Distributional Representation: Illustration

If we label the dimensions in a hypothetical word vector (there are no such

pre-assigned labels in the algorithm of course), it might look a bit like this:

Such a vector comes to represent in some abstract way the ‘meaning’ of a word

19 of 38

Learning Word Vectors: Overview

20 of 38

Two Variations: CBOW and Skip-grams

21 of 38

Word2Vec (Skip-gram) Overview

Example windows and process for computing P(w_t+j|w_t)

22 of 38

Word2Vec (Skip-gram) Overview

Example windows and process for computing P(w_t+j|w_t)

23 of 38

Word2Vec: objective function

24 of 38

Understanding P(o|c) further

25 of 38

Try this problem

26 of 38

Issues with word2Vec

e.g., negative sampling

27 of 38

Node Embeddings: Shallow Encoding

Slide Courtesy: Jure Leskovec, Stanford CS224W

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

28 of 38

Node Embeddings: Two Key Components

Slide Courtesy: Jure Leskovec, Stanford CS224W

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

29 of 38

“Shallow” Encoding

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

30 of 38

“Shallow” Encoding

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

31 of 38

Shallow Encoding

Simplest encoding approach: Encoder is just an embedding-lookup

Each node is assigned a unique

embedding vector

(i.e., we directly optimize

the embedding of each node)

Many methods: DeepWalk, node2vec

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

32 of 38

Node Embeddings: Random Walk-Based

Slide Courtesy: Jure Leskovec, Stanford CS224W

Given a graph and a starting

point, we select a neighbor of it at random, and move to this neighbor; then we select a neighbor of this point at

random, and move to it, etc.

The (random) sequence of

points visited this way is a

random walk on the graph.

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

33 of 38

Random Walk Embeddings

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

34 of 38

Unsupervised Feature Learning

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

35 of 38

Feature Learning as Optimization

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

36 of 38

Random Walk Optimization

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

37 of 38

Random Walk Optimization

Lecture 4: Complex Networks, IIT KGP, Somak Aditya

38 of 38

Node Embeddings: Random Walk-Based

Slide Courtesy: Jure Leskovec, Stanford CS224W

Lecture 4: Complex Networks, IIT KGP, Somak Aditya