Node Embeddings

Slide 7 recaps the traditional ML pipeline on graphs: given an input graph, a human designs structured features (node-level, edge-level and graph-level features such as degree, centrality or graphlet counts), and then a learning algorithm (SVM, neural network, etc.) maps these features to labels for the downstream prediction task. The weak point is the feature-engineering step: it must be redone, by hand, for every new task and domain.

Slide 8 shows the alternative. Graph representation learning removes the need to do feature engineering every single time: the "feature engineering" box is crossed out and replaced by representation learning, which learns the features automatically.

Slide 9 states the goal: efficient, task-independent feature learning for machine learning with graphs. We want a map

that sends each node \(u\) to a \(d\)-dimensional vector, its feature representation or embedding.

Slide 10 says what a good embedding should do:

• Similarity of embeddings indicates similarity in the network. For example, two nodes connected by an edge should get nearby vectors.
• Encode network information in the vector.
• Be usable for many downstream predictions: node classification, link prediction, graph classification, anomalous node detection, clustering, and more. The same vectors feed all these tasks.

Slide 11 shows an example from the DeepWalk paper (Perozzi et al., KDD 2014): Zachary's Karate Club network (left, nodes coloured by community) and its 2D embedding (right). Nodes of the same colour land close together in the plane, and the four communities become four visible clusters. So the embedding, learned only from the graph structure, has recovered the community structure.

Slide 13 fixes the setup. We have an undirected graph \(G\) with vertex set \(V\) and binary adjacency matrix \(A\). For simplicity, no node features or extra information are used; only the structure. The example graph has \(V = \{1, 2, 3, 4\}\) and edges 1–2, 1–4, 2–4, 3–4, so

Slide 14 states the goal: encode nodes so that similarity in the embedding space (e.g., dot product) approximates similarity in the graph. The figure shows an encoder ENC mapping node \(u\) to \(z_u\) and node \(v\) to \(z_v\) in the embedding space. Slide 15 writes the goal as

where the left side is similarity in the original network (which we still need to define) and the right side is similarity of the embeddings.

Slide 16 lists the four steps of learning node embeddings:

1. An encoder maps nodes to embeddings.
2. Define a node similarity function, i.e., a measure of similarity in the original network.
3. A decoder DEC maps a pair of embeddings to a similarity score.
4. Optimize the encoder's parameters so that \(\text{DEC}(z_v^\top z_u) \approx \text{similarity}(u, v)\).

Slide 17 names the two key components. The encoder maps each node to a low-dimensional vector: \(\text{ENC}(v) = z_v\), a \(d\)-dimensional embedding of node \(v\). The similarity function says how relations in vector space map to relations in the network. Here the decoder is simply the dot product between node embeddings.

Slides 18–20 give the simplest encoder: the encoder is just an embedding lookup.

• \(Z\) is a matrix with one column per node; each column is that node's embedding. This matrix is what we learn and optimize.
• \(v\) is an indicator (one-hot) vector: all zeros except a one in the position of node \(v\). Multiplying \(Z\) by it simply picks out column \(v\).
• The number of rows \(d\) is the dimension (size) of the embeddings (slide 19's picture: a \(d \times |V|\) box with one highlighted column).

Slide 20 summarises: each node is assigned a unique embedding vector, i.e., we directly optimize the embedding of each node. Many methods work this way, including DeepWalk and node2vec.

Slide 21 summarises the whole framework:

• Shallow encoder: embedding lookup. Parameters to optimize: \(Z\), which contains the embeddings \(z_u\) for all \(u \in V\). Deep encoders (GNNs) come in later lectures.
• Decoder: based on node similarity.
• Objective: maximize \(z_v^\top z_u\) for node pairs \((u, v)\) that are similar.

"Shallow" means there is no function that computes an embedding from inputs; there is just a table. The number of parameters is \(d \cdot |V|\), which grows with the graph, and nothing is shared between nodes. This is the root of the limitations at the end of the lecture.

Slide 22: the key choice that distinguishes methods is how they define node similarity. Should two nodes have similar embeddings if they

• are linked?
• share neighbours?
• have similar "structural roles" (e.g., both are hubs, or both are bridges)?

These are genuinely different notions. Two hubs at opposite ends of a network are similar by role but far apart by distance. The lecture now builds a similarity defined by random walks, and shows how to optimize embeddings for it.

Slide 23 stresses the nature of this learning:

• It is an unsupervised / self-supervised way of learning node embeddings. We use no node labels and no node features.
• The goal is to directly estimate a set of coordinates (the embedding) for each node so that some aspect of the network structure, the one captured by DEC, is preserved.
• The embeddings are task independent: they are not trained for a specific task, but can be used for any task.

Slide 25 fixes notation used in the rest of the lecture:

• \(z_u\): the embedding of node \(u\), which we want to find.
• \(P(v \mid z_u)\): the model's predicted probability of visiting node \(v\) on random walks starting from node \(u\).
• Softmax turns a vector of \(K\) real numbers into \(K\) probabilities that sum to 1: \[ S(z)[i] = \frac{e^{z[i]}}{\sum_{j=1}^{K} e^{z[j]}}. \]
• Sigmoid is an S-shaped function that maps a real number into \((0, 1)\): \[ \sigma(x) = \frac{1}{1 + e^{-x}}. \]

Slide 26 defines a random walk: given a graph and a starting point, select a neighbour at random and move to it; then select a neighbour of this point at random and move to it; and so on. The random sequence of nodes visited is a random walk on the graph. The figure shows a 5-step walk on a 12-node graph, starting at the highlighted (smiley-face) node and moving to 5, then 8, 9, back to 8, and 11 (steps 1–5 marked by red arrows). Note that a walk may revisit nodes.

Slide 27 states the core idea in one line:

This is the similarity function we were missing on slide 15. It is defined by a random process, not by a fixed formula.

Slide 28 gives the two-step recipe:

1. Estimate the probability of visiting node \(v\) on a random walk starting from node \(u\), using some random walk strategy \(R\). Call it \(P_R(v \mid u)\).
2. Optimize embeddings to encode these random-walk statistics. The figure shows two vectors \(z_i, z_j\) with angle \(\theta\) between them: similarity in the embedding space (here the dot product, which equals \(\cos\theta\) for unit vectors) should be proportional to \(P_R(v \mid u)\).

Slide 29 explains why random walks:

1. Expressivity. They give a flexible, stochastic definition of node similarity that includes both local and higher-order (multi-hop) neighbourhood information. Idea: if a random walk from \(u\) visits \(v\) with high probability, then \(u\) and \(v\) are similar.
2. Efficiency. Training does not need all \(|V|^2\) node pairs; it only needs the pairs that co-occur on random walks.

Slide 30 restates the setting as unsupervised feature learning. Intuition: find embeddings in \(d\)-dimensional space that preserve similarity. Idea: learn embeddings so that nodes that are nearby in the network are close together in embedding space. How do we define "nearby"? With \(N_R(u)\), the neighbourhood of \(u\) obtained by some random walk strategy \(R\).

This is the analogy that DeepWalk took from word2vec: a random walk is a "sentence" of nodes, and nodes that appear in the same context should get similar vectors, just as words that appear in similar contexts do.

Slide 31: given \(G = (V, E)\), we want a mapping \(f: u \to \mathbb{R}^d\), \(f(u) = z_u\). The log-likelihood objective is

where \(N_R(u)\) is the neighbourhood of \(u\) under strategy \(R\). In words: given node \(u\), learn a representation that is predictive of the nodes in its random-walk neighbourhood.

Slide 32 gives the procedure:

1. Run short fixed-length random walks from each node \(u\) using strategy \(R\).
2. For each \(u\), collect \(N_R(u)\), the multiset of nodes visited on walks from \(u\). It is a multiset because a node can be visited many times, and repeated visits should count more.
3. Optimize embeddings by maximum likelihood: given node \(u\), predict its neighbours \(N_R(u)\).

Slide 33 writes the equivalent minimization, assuming the neighbours are predicted independently given \(z_u\):

Intuition: minimize the negative log-likelihood of the random-walk neighbourhoods. The probability is parameterized with a softmax:

Why softmax? We want node \(v\) to be the most similar to \(u\) out of all nodes \(n\); since \(\sum_i \exp(x_i) \approx \max_i \exp(x_i)\), the softmax is a smooth version of picking the maximum.

Slide 34 puts it together:

The outer sum runs over all nodes \(u\); the inner sum over nodes \(v\) seen on walks from \(u\); the fraction is the predicted probability that \(u\) and \(v\) co-occur. Optimizing random-walk embeddings = finding embeddings \(z_u\) that minimize \(\mathcal{L}\).

Slides 35–36: doing this naively is too expensive. The outer sum over \(u \in V\) and the softmax denominator's sum over \(n \in V\) are nested, giving \(O(|V|^2)\) complexity. The culprit is the normalization term of the softmax. Can we approximate it?

Slide 37 gives the solution, negative sampling:

• \(\sigma\) is the sigmoid; it makes each term a "probability" between 0 and 1.
• Instead of normalizing against all nodes, we only compare against \(k\) random "negative samples" \(n_i\), drawn from a background distribution \(P_V\) over nodes.
• Why is this valid? Technically it is a different objective. But negative sampling is a form of Noise Contrastive Estimation (NCE), which approximately maximizes the log-probability of the softmax. The new form is a logistic regression that distinguishes the true target \(v\) from the noise nodes \(n_i\). (Reference on the slide: arXiv 1402.3722.)
• Negative sampling makes the likelihood quick to compute: \(k+1\) dot products instead of \(|V|\).

Slide 38 adds practical details. Sample the \(k\) negative nodes with probability proportional to their degree. Two considerations for \(k\): (1) higher \(k\) gives more robust estimates; (2) higher \(k\) puts more bias on negative events. In practice \(k = 5\)–\(20\). Can a negative sample be any node, or only nodes not on the walk? People often sample any node, for efficiency.

Slide 39: once we have the objective \(\mathcal{L} = \sum_{u}\sum_{v \in N_R(u)} -\log P(v \mid z_u)\), how do we minimize it? Gradient descent:

• Initialize \(z_u\) at random for all nodes \(u\).
• Iterate until convergence: for all \(u\), compute the derivative \(\partial\mathcal{L}/\partial z_u\); then for all \(u\), step in the reverse direction: \(z_u \leftarrow z_u - \eta\, \partial\mathcal{L}/\partial z_u\), where \(\eta\) is the learning rate.

Slide 40: stochastic gradient descent (SGD) evaluates the gradient on individual training examples instead of all of them. Define the per-node loss

• Initialize \(z_u\) at random for all \(u\).
• Iterate until convergence: sample a node \(u\); for all \(v\), compute \(\partial\mathcal{L}^{(u)}/\partial z_v\) and update \(z_v \leftarrow z_v - \eta\, \partial\mathcal{L}^{(u)}/\partial z_v\).

Each step is cheap and noisy, but on average it moves in the right direction; this is what makes training on millions of nodes possible.

Slide 41 summarises random-walk embeddings in three steps:

1. Run short fixed-length random walks from each node.
2. For each node \(u\), collect \(N_R(u)\), the multiset of nodes visited on walks from \(u\).
3. Optimize the embeddings \(Z\) with SGD on \(\mathcal{L} = \sum_u \sum_{v \in N_R(u)} -\log P(v \mid z_u)\), approximated efficiently with negative sampling.

Slide 42: so far we optimized embeddings for a given walk strategy \(R\). Which strategy should we use? The simplest idea is to run fixed-length, unbiased random walks from each node. This is DeepWalk (Perozzi et al., KDD 2014). The issue: this notion of similarity is too constrained. How can we generalize it?

Slide 43 gives the overview of node2vec (Grover & Leskovec, KDD 2016):

• Goal: embed nodes with similar network neighbourhoods close together in feature space.
• Framed as maximum-likelihood optimization, independent of the downstream task.
• Key observation: a flexible notion of network neighbourhood \(N_R(u)\) leads to richer node embeddings.
• Method: a biased 2nd-order random walk \(R\) to generate \(N_R(u)\). "2nd-order" means the next step depends on the current node and the previous one.

Slide 44: the idea is to use flexible, biased walks that can trade off between local and global views of the network.

Slide 45 shows the two classic strategies on a graph where \(u\) has neighbours \(s_1, s_2, s_3, s_4\), and a path \(u \to s_4 \to s_5 \to s_6\) leads into a second cluster (\(s_6\)–\(s_9\)). With a neighbourhood of size 3:

Slide 46 summarises with two pictures: BFS stays among the immediate neighbours and gives a micro-view of the neighbourhood; DFS runs away along a path and gives a macro-view.

Intuition: BFS-like neighbourhoods describe a node's immediate surroundings (good for detecting structural roles, e.g., hub vs. periphery); DFS-like neighbourhoods describe which region of the graph a node lives in (good for communities, i.e., homophily).

Slide 47 defines the biased fixed-length walk \(R\) that generates \(N_R(u)\). It has two parameters:

• Return parameter \(p\): controls returning back to the previous node.
• In-out parameter \(q\): controls moving outwards (DFS) versus inwards (BFS). Intuitively, \(q\) is the "ratio" of BFS vs. DFS.

We specify one step of the walk; a walk is just a sequence of such steps.

Slide 48: the walk has just traversed edge \((t, w)\) and is now at \(w\). We set transition probabilities on the edges out of \(w\). Insight: every neighbour of \(w\) is at distance 0, 1 or 2 from \(t\): it is \(t\) itself (distance 0), a common neighbour of \(t\) and \(w\) (distance 1), or a node farther from \(t\) (distance 2). In the figure, \(s_1\) is at distance 1 from \(t\) and \(s_2\) is at distance 2.

Slides 49–50 assign the unnormalized transition probabilities:

Normalize by the sum to get probabilities. A BFS-like walk uses a low \(p\) (it keeps returning to \(t\), so it stays close to the start). A DFS-like walk uses a low \(q\) (moving outward is cheap). \(N_R(u)\) is the multiset of nodes visited by this biased walk. With \(p = q = 1\) all weights are 1 and we get DeepWalk's uniform walk.

Worked example (our numbers, for practice): with \(p = 0.5, q = 2\) the weights are \(2, 1, 0.5, 0.5\), sum 4, so the probabilities are \(0.5, 0.25, 0.125, 0.125\): a strongly local, BFS-like walk.

Slide 50's heading says the walker "came over edge \((s_1, w)\)", but its figure and table treat \(t\) as the previous node. Read it as edge \((t, w)\), as on slides 48–49.

Slide 51 gives the node2vec algorithm:

1. Compute edge transition probabilities: for each edge \((t, w)\), compute the walk probabilities (from \(p, q\)) of the edges \((w, \cdot)\).
2. Simulate \(r\) random walks of length \(l\) starting from each node \(u\).
3. Optimize the node2vec objective with stochastic gradient descent (the same objective as before, with negative sampling).

It has linear-time complexity, and all three steps are individually parallelizable.

Slide 52 lists other random-walk ideas:

• Other kinds of biased walks: based on node attributes (Dong et al.) or on learned weights (Abu-El-Haija et al.).
• Alternative optimization: directly optimize based on 1-hop and 2-hop random-walk probabilities (LINE, Tang et al.).
• Network preprocessing: run random walks on modified versions of the network (Ribeiro et al., struc2vec; Chen et al., HARP).

Slide 53 summarises so far. Core idea: embed nodes so that distances in embedding space reflect node similarities in the original network. Different notions of similarity: naïve (similar if connected), and random-walk approaches (today).

Slide 54: which method should you use? No method wins in all cases. For example, node2vec does better on node classification while other methods do better on link prediction (Goyal and Ferrara, survey). Random-walk approaches are generally more efficient. In general: choose the definition of node similarity that matches your application.

Slide 56: sometimes we want to embed a subgraph or an entire graph \(G\) as a vector \(z_G\). Tasks: classifying toxic vs. non-toxic molecules, identifying anomalous graphs.

Slide 57, approach 1 (simple but effective): run a standard node-embedding technique on the (sub)graph \(G\), then sum (or average) the node embeddings:

Duvenaud et al. used this to classify molecules by their graph structure.

Slide 58, approach 2: introduce a "virtual node" that represents the (sub)graph, connect it to the nodes of the (sub)graph, and run a standard node-embedding technique. The virtual node's embedding is \(z_G\). Proposed by Li et al. as a general technique for subgraph embedding.

Slide 59 recaps the two ideas: (1) embed nodes and sum/average them; (2) create a super-node that spans the (sub)graph and embed that node.

Slide 60 previews hierarchical embeddings with DiffPool: hierarchically cluster the nodes, sum/average the node embeddings within clusters, and repeat. The figure shows the original network pooled into a smaller network at level 1, then level 2, then a single node at level 3, which feeds a graph classifier.

Slide 62 recalls that the encoder is an embedding lookup into \(Z\) (one column per node), with the objective "maximize \(z_v^\top z_u\) for similar pairs".

Slide 63 takes the simplest similarity: \(u\) and \(v\) are similar if they are connected by an edge. Then we want

the \((u, v)\) entry of the adjacency matrix. Stacking all pairs: \(Z^\top Z = A\). The figure shows the 4-node graph from slide 13, its matrix \(A\), and \(A\) written as the product \(Z^\top Z\): entry \((u,v)\) is the dot product of columns \(z_u\) and \(z_v\).

Slide 64: the dimension \(d\) (rows of \(Z\)) is much smaller than the number of nodes \(n\), so an exact factorization \(A = Z^\top Z\) is generally impossible (the rank of \(Z^\top Z\) is at most \(d\)). We learn \(Z\) approximately:

minimizing the L2 (Frobenius) norm. Today's random-walk methods used softmax instead of L2, but the goal of approximating a similarity matrix with \(Z^\top Z\) is the same. Conclusion: an inner-product decoder with edge-connectivity similarity is equivalent to matrix factorization of \(A\).

Slides 65–66: DeepWalk and node2vec use a more complex, random-walk-based similarity, but they too are matrix factorizations. DeepWalk is equivalent to factorizing

where (slide 66):

• \(\mathrm{vol}(G) = \sum_i \sum_j A_{i,j}\) is the volume of the graph (twice the number of edges);
• \(D\) is the diagonal degree matrix, \(D_{u,u} = \deg(u)\);
• \((D^{-1}A)^r\) is the \(r\)-th power of the normalized adjacency matrix;
• \(T = |N_R(u)|\) is the context window size;
• \(b\) is the number of negative samples.

node2vec can also be written as a matrix factorization, of a more complex matrix. Reference: Qiu et al., "Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec" (WSDM 2018).

Slide 67: how to use the embeddings \(z_i\):

• Clustering / community detection: cluster the points \(z_i\).
• Node classification: predict the label of node \(i\) from \(z_i\).
• Link prediction: predict edge \((i, j)\) from \((z_i, z_j)\). Combine the two vectors with a function \(f\) and feed it to a classifier \(g\):
  • Concatenate: \(f(z_i, z_j) = g([z_i, z_j])\)
  • Hadamard (per-coordinate product): \(f(z_i, z_j) = g(z_i * z_j)\)
  • Sum/average: \(f(z_i, z_j) = g(z_i + z_j)\)
  • Distance: \(f(z_i, z_j) = g(\lVert z_i - z_j \rVert_2)\)
• Graph classification: get a graph embedding \(z_G\) by aggregating node embeddings or with a virtual node, then predict the label from \(z_G\).

For an undirected edge, sum, Hadamard and distance are symmetric in \(i, j\); concatenation is not, so it suits directed links.

Slide 68 summarises the lecture: graph representation learning learns node and graph embeddings for downstream tasks without feature engineering. The encoder–decoder framework: encoder = embedding lookup; decoder = a score from the embeddings that matches node similarity. Node similarity measure: (biased) random walks, e.g., DeepWalk and node2vec. Extension to graph embedding: aggregate node embeddings.

Slides 69–71 list the limitations of node embeddings via matrix factorization and random walks.

1. Transductive, not inductive (slide 69).

• We cannot obtain embeddings for nodes not in the training set. The figure adds a new node 5 at test time (e.g., a new user in a social network) attached to node 2; DeepWalk/node2vec cannot compute its embedding, and all node embeddings must be recomputed.
• We cannot apply the model to new graphs.
• If you run DeepWalk on the same graph several times, you get a different embedding each time. Why? The walks and the initialization are random, and the objective only depends on dot products \(z_u^\top z_v\), which do not change under any rotation of all embeddings. So the solution is defined only up to such transformations.

2. No structural similarity (slide 70). In the figure, nodes 1 and 11 are structurally similar: each is in a triangle (1–2–3 and 11–12–13) with degree 2, and the two triangles are joined by a long path 3–4–5–…–10–13. Yet they get very different embeddings, because a random walk from node 1 is unlikely to reach node 11. DeepWalk and node2vec do not capture structural similarity; they capture proximity.

3. No features (slide 71). They cannot use node, edge or graph features, e.g., protein properties in a protein–protein interaction graph (the green bars in the figure). The embeddings ignore them.

The solution to all three: deep representation learning and graph neural networks, covered next. A GNN computes an embedding as a function of a node's features and neighbourhood, so it works for new nodes, sees local structure and uses features.