My Key Takeaways After Reading "Deep Learning on Graphs": Graph Embedding

Graph embedding is simply how we map a graph's nodes into vector in a continuous coordinate space.

From a linear algebra perspective, an adjacency matrix A represents the graph's connections and edge weights. Our goal is to transform each node into a d-dimensional vector in a lower-dimensional coordinate system. The edges represent relationships between vectors, which we measure using the dot product. If two vectors point in the same direction (dot product close to 1), they are highly similar or strongly connected.

Random Walk & DeepWalk
A random walk is a graph traversal algorithm, similar in spirit to BFS and DFS, but without strict deterministic rules.

To visualize a Random Walk, imagine placing an ant on a node. The ant walks randomly from node to node, recording its travel path. By analyzing these paths, we discover which nodes frequently show up together (co-occurrence). We then update out vector space to pull these co-occurring nodes closer so their vectors point in similar directions. This entire process forms the foundation of DeepWalk.

Why use Random Walks instead of traditional DFS or BFS?

• Parallel Processing: DFS and BFS are linear and constraint-heavy, you can only process one path at time with a single "ant". Random Walks, however, allow us to release 1,000 ants simultaneously to explore different parts of the graph in parallel, making training significantly faster.

• Capturing Community: Random walks better reveal structural contexts and local communities.

Since an ant could theoretically walk endlessly across the entire graph, we use a context window restricts the ant's view to just 1 or 2 steps ahead, focusing specifically on highly localized node relationships.

After each walk, a reconstruction function updates the relations among nodes. Updating incrementally after each walk, rather than waiting to process the while graph at once, keeps the coordinate system stable and prevents vectors from over-fitting to just a few neighbors. However, calculating dot product between one node and billions of other is computationally impossible. To solve this, we rely on divide-and-conquer strategies and tree structures to accelerate the learning process.

Hierarchical Softmax
Hierarchical Softmax uses a binary tree structure to group similar nodes on the same branch. The closer a node is to the root, the boarder its category.

Think of it like a university: the root represents the university itself, the next layer branches into specific majors (e.g., Computer Science), and deeper layers descend into specialized courses for that major. By using this divine-and-conquer tree structure, the model can inherit prior node decisions and dramatically speed up vector calculations from $O(N)$ to $O(\log N)$ .

Negative Sampling
Negative Sampling works like a gacha game with a clever cheat.

When updating a target node, calculating its relationship against all other nodes in a massive graph is unrealistic. Instead of evaluating everything, the algorithm picks the 1 actual neighbor (the rare "5-star" positive pull) to draw closer, and randomly samples a few unrelated nodes (the common "1-star" negative pulls) to push far away in the vector space.

Node2Vec
Technology is never stop evolving, and Node2Vec is the upgrade version of DeepWalk.

While Deepwalk relies on purely uniform random walks, Node2Vec introduces two parameters, p and q, to control the ant's walking behavior:

• Return Parameter (p): A small p encourages the ant to stay close to the starting node (like a localized BFS search), capturing tight-knit communities.

• In-out Parameter (q): A small q encourages the ants to explore outward into new regions (like a deep DFS search), capturing structural roles.

LINE
Rather than relying solely on linear paths, LINE explicity models two structural perspective:

1. First order Proximity: Direct connections between nodes.

2. Second-order Proximity: Shared neighborhood contexts. Even if two nodes do not have a direct adge between them, if they share almost identical context vectors (similar neighbors), LINE pulls their embeddings closer together.

Struct2Vec
Struct2Vec builds upon LINE's ideas, Relying only on immediate neighbors can lead to mistakes when identifying global roles. Struc2vec expands this scope by recursively evaluating the neighborhood structure of a node's neighbors. Nodes with similar structural roles (e.g., "hubs" or "leaf nodes") are mapped close together in the vector space, even if they are located on opposite sides of the graph.