Core ML

Graph Representation Learning

Machine learning models only understand matrices of numbers. Graph representation learning is the math used to compress a messy web of relationships into a clean, flat matrix of vectors, without losing the network structure.

Random walks (like DeepWalk) translate a 2D graph structure into 1D sequences of nodes. We can then train standard embedding models (like Word2Vec) on these sequences to generate node embeddings.

Why Does This Exist?

You have a massive Knowledge Graph or a social network. You want to train a machine learning model to predict:

Node Classification: Is this user a bot?
Link Prediction: Should we recommend that User A be friends with User B?

Standard ML models (like XGBoost or a Multi-Layer Perceptron) expect flat, tabular data. They expect User A to be a row with 10 fixed columns. But a graph is not flat. User A might have 5 friends, User B might have 5,000 friends.

Graph Representation Learning is the process of generating Embeddings for a graph. It takes nodes and edges and squashes them down into fixed-length, dense mathematical vectors (e.g., an array of 128 floats). Once every node is a vector, you can feed them into standard ML models, calculate cosine similarity, and run clustering algorithms.

Think of It Like This

Imagine trying to describe the layout of the London Underground (a graph) to someone who can only understand lists of numbers (an ML model).

If you just give them a list of stations, they lose the structure. Instead, you simulate a tourist wandering randomly through the tube network. You record the stations they pass: [Waterloo, Embankment, Charing Cross, Piccadilly Circus]. By simulating millions of these Random Walks, you turn the 2D map into 1D sentences. You can now use text-based AI (like Word2Vec) to learn that "Waterloo" and "Embankment" are highly related because they frequently appear next to each other in the random walks.

How It Actually Works

The goal of graph representation learning is simple: If two nodes are structurally close in the graph, their resulting embedding vectors should be close in the vector space.

1. Matrix Factorization (The Old Way)

A graph can be represented as an Adjacency Matrix (a massive grid of 0s and 1s where a 1 means two nodes are connected). We can use algorithms like Singular Value Decomposition (SVD) to factorize this matrix into a smaller, dense matrix. This works well for small graphs, but it requires $O(N^2)$ memory, making it impossible to run on a graph with millions of nodes.

2. Random Walks (DeepWalk & Node2Vec)

To solve the memory problem, researchers borrowed the math from Natural Language Processing (word2vec).

DeepWalk (2014): Start at a random node. Pick a random edge. Walk to the next node. Repeat 10 times. This generates a "sentence" of nodes. Do this for every node in the graph, then train Word2Vec on the resulting text.
Node2Vec (2016): An improvement over DeepWalk. It adds two hyperparameters ( $p$ and $q$ ) that control the random walk. You can force the walker to stay local (Breadth-First Search, capturing the immediate community) or explore deep into the graph (Depth-First Search, capturing the structural role of the node).

3. Graph Neural Networks (The Modern Way)

Random walks generate static embeddings (a lookup table). If a new user joins the network tomorrow, you have to re-run Node2Vec from scratch. Graph Neural Networks (GNNs) solve this by learning a function that generates embeddings dynamically. GNNs use "Message Passing," where a node updates its own embedding by aggregating the embeddings of its immediate neighbors. This allows the model to handle dynamic graphs and incorporate node features (like the user's age or bio).

Show Me the Code

You can use the nodevectors library to quickly generate Node2Vec embeddings for a graph using a standard networkx object.

1import networkx as nx2from nodevectors import Node2Vec3
4# 1. Create a dummy graph (e.g., a social network)5G = nx.karate_club_graph()6
7# 2. Initialize the Node2Vec algorithm8# walklen: How many steps the random walker takes9# epochs: How many walks to simulate per node10# return_weight (p) and neighbor_weight (q): Control BFS vs DFS exploration11n2v = Node2Vec(12    walklen=10, 13    epochs=20, 14    n_components=64, # Output embedding dimension15    return_weight=1.0, 16    neighbor_weight=1.017)18
19# 3. Fit the model to generate the embeddings20n2v.fit(G)21
22# 4. Extract the embedding for a specific node (e.g., Node 0)23node_0_embedding = n2v.predict(0)24print(f"Node 0 Embedding Shape: {node_0_embedding.shape}") 25# Output: (64,)26
27# Now you can pass these 64-dimensional vectors into XGBoost or a similarity search!

Watch Out For

The Homophily vs. Structural Equivalence Trap. When you generate embeddings, what does "similar" actually mean?

Homophily (Community): Node A and Node B are in the same friend group.
Structural Equivalence (Role): Node A and Node B are both CEOs of different companies; they don't know each other, but they have the same "hub" structure in the graph. If you use standard DeepWalk, your embeddings will capture Homophily. If you need to predict roles (e.g., "Is this node a bot?"), you must tune Node2Vec to favor Structural Equivalence, or use specialized role-based algorithms like struc2vec.

The Quick Version

Standard ML models cannot read graphs natively; they need flat vectors.
Graph Representation Learning translates nodes and edges into dense mathematical embeddings.
DeepWalk and Node2Vec achieve this by simulating random walks across the graph to generate "sentences", which are then fed into Word2Vec.
Modern pipelines use Graph Neural Networks (GNNs), which generate dynamic embeddings by aggregating information from neighboring nodes.

Related concepts

Graph Neural Networks