Graph Foundations | Graph Machine Learning

1. What Is a Graph?

A graph $G = (V, E)$ is a set of nodes (also called vertices) $V$ and edges $E$ that connect pairs of nodes.

Think of nodes as "things" and edges as "relationships between things."

Social network: nodes = people, edges = friendship
Citation network: nodes = papers, edges = "paper A cites paper B"
Molecule: nodes = atoms, edges = chemical bonds
Knowledge graph: nodes = entities (Paris, France), edges = relations (capital_of)

Directed vs undirected

Undirected: edge $(i,j)$ is the same as $(j,i)$. Friendship is usually undirected.
Directed: edge has a direction. Citations are directed: A cites B does not mean B cites A.

Weighted vs unweighted

Unweighted: edge exists (1) or does not (0).
Weighted: each edge has a number - distance, strength, probability, etc.

Attributed graphs

Real graphs almost always carry extra data:

Node features $\mathbf{x}_i \in \mathbb{R}^d$ - age, text embedding, atom type
Edge features $\mathbf{e}_{ij}$ - bond type, relation label, timestamp

Intuition: A graph is just a flexible way to store "who is connected to whom" plus optional attributes. Tables store rows independently; graphs store relationships explicitly.

Why not just use a table?

Suppose you have users and their friends. In a table, each row is one user. Where do you put "friend of friend" patterns? You would need hand-crafted columns or join many tables. In a graph, multi-hop relationships are natural - you follow edges.

When a table is enough: if rows are independent (no useful relationships), use regular ML. We cover this decision in When to Use GNNs.

2. Why Use Graphs for Machine Learning?

Standard neural nets assume a fixed input size and order:

MLP: fixed-length feature vector per sample
CNN: fixed grid (image)
RNN/Transformer: sequence with an order

Graphs break these assumptions: no fixed size, no canonical node order, and structure matters.

Relational inductive bias

An inductive bias is an assumption baked into a model. CNNs assume locality on a grid. RNNs assume sequential dependence. Graph neural networks (GNNs) assume:

Locality: useful information often comes from neighbors
Permutation invariance: shuffling node IDs should not change the graph's meaning
Compositional structure: patterns repeat across similar local neighborhoods

Intuition: If your problem is "predict this node's label, and similar nodes that are connected tend to share labels," a GNN is a natural fit. That is the homophily assumption (Section 6).

Refer: Hamilton et al. - Representation Learning on Graphs (survey) · Bronstein et al. - Geometric Deep Learning Grid

3. Notation and Vocabulary

Symbol	Meaning
$G = (V, E)$	Graph with nodes $V$, edges $E$
$n = \|V\|$	Number of nodes
$m = \|E\|$	Number of edges
$\mathcal{N}(i)$	Neighbors of node $i$
$\mathbf{A} \in \mathbb{R}^{n \times n}$	Adjacency matrix
$\mathbf{D}$	Degree matrix (diagonal)
$\mathbf{L}$	Graph Laplacian
$\mathbf{x}_i$	Feature vector of node $i$
$\mathbf{h}_i^{(l)}$	Hidden embedding of node $i$ at layer $l$
$k$-hop neighborhood	Nodes reachable in $k$ edge steps

4. Adjacency Matrix and Degree

The adjacency matrix $\mathbf{A}$ encodes connections. For an undirected unweighted graph:

$$A_{ij} = \begin{cases} 1 & \text{if } (i,j) \in E \\ 0 & \text{otherwise} \end{cases}$$

For directed graphs, $A_{ij}=1$ means an edge from $i$ to $j$. The matrix may be asymmetric.

Degree

The degree of node $i$ is how many edges touch it:

$$d_i = \sum_j A_{ij}$$

Store all degrees in a diagonal matrix:

$$\mathbf{D} = \text{diag}(d_1, d_2, \ldots, d_n)$$

Normalized adjacency (used in GCN)

Raw adjacency sums can explode for high-degree nodes. GCN uses a symmetric normalization:

$$\tilde{\mathbf{A}} = \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$$

Add self-loops ($\mathbf{A} + \mathbf{I}$) so a node can keep its own signal. We derive why in Classic Architectures (GCN).

Why normalize? Without $\mathbf{D}^{-1/2}$, multiplying $\mathbf{A}\mathbf{x}$ gives huge values for hub nodes (celebrities with millions of followers). Normalization balances influence so each neighbor contributes fairly relative to degree.

import torch

# 4-node cycle: 0-1-2-3-0
edge_index = torch.tensor([[0,1,1,2,2,3,3,0],
                           [1,0,2,1,3,2,0,3]], dtype=torch.long)
n = 4
A = torch.zeros(n, n)
A[edge_index[0], edge_index[1]] = 1

D = torch.diag(A.sum(dim=1))
D_inv_sqrt = torch.diag(1.0 / torch.sqrt(D.diag() + 1e-8))
A_norm = D_inv_sqrt @ A @ D_inv_sqrt

5. Graph Laplacian - Full Derivation

The graph Laplacian is the most important matrix in spectral graph theory. It appears in GCN derivations, graph signal processing, and positional encodings.

Definition

$$\mathbf{L} = \mathbf{D} - \mathbf{A}$$

Entry-wise: $L_{ii} = d_i$ (degree on diagonal), $L_{ij} = -1$ if $(i,j) \in E$, else $0$.

Equivalent form

$$\mathbf{L} = \mathbf{B}^T \mathbf{B}$$ where $\mathbf{B}$ is the signed incidence matrix (each edge row has $+1$ and $-1$ at endpoints). This shows $\mathbf{L}$ is positive semi-definite.

Quadratic form - smoothness measure

For signal $\mathbf{f} \in \mathbb{R}^n$ on nodes:

$$\mathbf{f}^T \mathbf{L} \mathbf{f} = \frac{1}{2} \sum_{(i,j) \in E} (f_i - f_j)^2$$

Derivation sketch: Expand $\mathbf{f}^T(\mathbf{D}-\mathbf{A})\mathbf{f} = \sum_i d_i f_i^2 - \sum_{(i,j)\in E} f_i f_j$. Pair each undirected edge once and complete the square: $(f_i - f_j)^2 = f_i^2 + f_j^2 - 2f_i f_j$. Summing over edges gives the result.

Intuition: $\mathbf{f}^T \mathbf{L} \mathbf{f}$ is small when connected nodes have similar values - a smooth signal on the graph. Large when neighbors disagree. GNN oversmoothing (later) pushes embeddings toward this smoothness too aggressively.

Normalized Laplacian

$$\mathcal{L}_{\text{sym}} = \mathbf{I} - \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$$ $$\mathcal{L}_{\text{rw}} = \mathbf{I} - \mathbf{D}^{-1}\mathbf{A}$$

Eigenvalues of $\mathcal{L}_{\text{sym}}$ lie in $[0, 2]$. The number of zero eigenvalues equals the number of connected components.

Why eigenvectors matter

Eigenvectors of $\mathbf{L}$ with small eigenvalues are smooth across the graph. They act like "Fourier bases" on non-grid data. Spectral GNNs use them as filters - see Spectral Methods.

6. Graph Machine Learning Tasks

Task	Input	Output	Example
Node classification	Graph + some labels	Label for each node	Categorize papers by topic
Node regression	Graph	Continuous value per node	Predict traffic at intersections
Link prediction	Graph (edges hidden)	Score for missing edges	Friend recommendation
Graph classification	Many graphs	One label per graph	Toxic vs non-toxic molecule
Graph regression	Many graphs	Scalar per graph	Predict molecular energy
Community detection	Graph	Cluster assignment	Find research subfields
Graph generation	Distribution	New graphs	Generate drug candidates

Transductive vs inductive

Transductive: test nodes are visible at training time (only labels hidden). Example: Cora citation network - all papers exist, classify unlabeled ones.
Inductive: test on completely new graphs or nodes not seen during training. Example: classify new molecules with a model trained on other molecules.

Common mistake: random train/test split on one graph without checking leakage across edges. We fix this in Data Preparation.

7. Homophily vs Heterophily

Homophily ("birds of a feather"): connected nodes tend to be similar. Social networks often show this - friends share interests.

Heterophily: connected nodes tend to be different. Example: protein interaction networks (different types interact), fraud detection (fraudsters connect to victims).

Homophily ratio (Zhu et al.)

$$h = \frac{|\{(u,v) : (u,v) \in E \land y_u = y_v\}|}{|E|}$$

$h \approx 1$ means strong homophily. $h \approx 0$ means strong heterophily.

Why this matters for GNNs: Classic GNNs aggregate neighbor features - they assume neighbors help predict your label. That works under homophily. Under heterophily, neighbors may mislead you; you need different architectures (H2GCN, GPR-GNN, etc. in Deep GNNs).

8. Graphs vs Grids vs Sequences

Structure	Neighbors per node	Order matters?	Typical model
Sequence	2 (prev, next)	Yes	RNN, Transformer
Grid (image)	4 or 8 fixed	Yes (position)	CNN
Graph	Varies (0 to millions)	No canonical order	GNN

Why not run a CNN on a graph? CNNs need a regular grid and fixed neighbor layout. Graph neighborhoods have arbitrary size and no left/right/up/down.

Why not sort nodes and use an RNN? Any sorting is arbitrary and destroys permutation invariance. Different orderings would give different outputs - wrong.

Solution: aggregate over neighbors in a symmetric way - message passing (next chapter).

9. Useful Graph Metrics

Clustering coefficient: how tightly a node's neighbors connect to each other (local triangle density)
Betweenness centrality: how often a node lies on shortest paths - bridge nodes
PageRank: importance based on incoming links from important nodes
Diameter: longest shortest path - graph "width"
Degree distribution: many real graphs are scale-free (few hubs, many low-degree nodes)

These can be used as input features or to understand whether a GNN can even reach distant nodes (over-squashing, later).

10. Key Papers and Further Reading

Hamilton, Ying, Leskovec - Representation Learning on Graphs: Methods and Applications - best survey to read after this page
Bronstein et al. - Geometric Deep Learning Grids, Groups, Graphs, Geodesics, and Gauges - theoretical blueprint
Zhu et al. - Beyond Homophily in GNNs - heterophily
Textbook: Graph Representation Learning by William L. Hamilton (free online)