DM9 - Graph Embeddings Flashcards

Question 1

What is the fundamental purpose of a graph embedding?

Accepted Answer

To project nodes from a non-Euclidean graph structure into a low-dimensional Euclidean space (like $\mathbb{R}^d$) where geometric distances reflect graph similarities.

Question 2

Why are standard machine learning models difficult to apply directly to raw graph data?

Accepted Answer

Because graphs lack a predefined node ordering or fixed grid structure (unlike images or text), making them invariant to permutations.

Question 3

In a linear graph embedding framework, how is the similarity between two nodes usually computed mathematically?

Accepted Answer

By calculating the dot product ($z_i^{	op} z_j$) of their respective embedding vectors.

Question 4

What is shallow encoding in the context of graph representations?

Accepted Answer

A method where a node's embedding is retrieved via a simple dictionary lookup from a learned embedding matrix $Z$, rather than passing features through a deep neural network.

Question 5

What does an adjacency-based similarity loss function try to optimize?

Accepted Answer

It attempts to minimize the squared difference between the dot product of the embeddings and the actual values in the graph's adjacency matrix.

Question 6

What is the primary computational drawback of naive adjacency-based embeddings?

Accepted Answer

They require computing pairwise similarities for all node pairs, resulting in an $\mathcal{O}(n^2)$ runtime that scales poorly on large graphs.

Question 7

How do multi-hop similarity methods improve upon simple adjacency embeddings?

Accepted Answer

They capture broader structural contexts by analyzing connections at distance $k$, often using the $k$-th power of the adjacency matrix ($A^k$).

Question 8

In graph theory, what does the value at entry $(i, j)$ in the matrix $A^k$ specifically represent?

Accepted Answer

The exact number of distinct paths of length exactly $k$ that exist between node $i$ and node $j$.

Question 9

How does the Adamic-Adar score calculate similarity between two nodes?

Accepted Answer

It measures the overlap of their neighborhoods, specifically assigning higher weight to shared neighbors that have a low overall degree.

Question 10

How do Random Walk embeddings define the similarity between two nodes?

Accepted Answer

Similarity is defined by the probability that the two nodes will co-occur within a short random walk simulated on the graph.

Question 11

Why is the Softmax function commonly used in random walk embedding loss functions?

Accepted Answer

It normalizes the unbounded dot products of the embedding vectors into a valid probability distribution over all other nodes in the network.

Question 12

What major computational bottleneck does Negative Sampling solve in neural embeddings?

Accepted Answer

It approximates the expensive Softmax denominator (which sums over all $V$ nodes) by framing the task as binary classification against a small handful of random negative nodes.

Question 13

In Negative Sampling, how are the negative noise nodes typically selected?

Accepted Answer

They are usually sampled proportionally to their degree, forcing the model to learn to distinguish true connections from highly connected hubs.

Question 14

What specific similarity metric does the VERSE embedding algorithm aim to preserve?

Accepted Answer

The Personalized PageRank (PPR) distributions between nodes.

Question 15

What mathematical metric does the VERSE algorithm minimize to align the learned embeddings with the target similarity distribution?

Accepted Answer

The Kullback-Leibler (KL) divergence.

Question 16

Why is Personalized PageRank (PPR) considered a highly expressive similarity measure for embeddings?

Accepted Answer

It successfully captures both local neighborhood structures and global network topology by evaluating random walks with a restart probability.

DM9 - Graph Embeddings

Card Preview

Related Flashcard Sets

Classical Mechanics - Newtonian Laws & Energy Conservation

General Pharmacology - Pharmacodynamics & Pharmacokinetics

Neuroscience Fundamentals - Brain Anatomy & Neurotransmitters

Cell Biology - Cellular Structure & Function