Graph Theory Foundations for Machine Learning

Graph Theory Foundations for Machine Learning

Why does a model that achieves 99% accuracy on ImageNet stumble when we feed it a molecule? The answer is structural. Images live on a regular grid where every pixel has a fixed location relative to its neighbors. Molecules, citation networks, transaction ledgers, and social platforms do not. Their elements are connected by relationships that are themselves part of the signal. A learning algorithm that ignores those relationships throws away the most informative part of the data, and a learning algorithm that processes them naively, by enumerating all possible orderings, explodes combinatorially before it sees its first training example. This chapter builds the mathematical vocabulary needed to reason about relational data rigorously. We will define what a graph is, enumerate the variants practitioners actually encounter, translate those definitions into matrices that linear algebra can chew on, identify the symmetries that any competent graph-aware architecture must respect, and close with a small lab that grounds every abstract definition in a runnable script. By the end you will be able to look at a relational dataset, formalize it as an object $G = (V, E, X)$, and predict which architectural choices are forced on you by the structure you have observed.

1.1 Why Graphs Refuse to Sit Still: The Topology Problem

A standard supervised learning pipeline assumes that the input is a fixed-size feature vector $x \in \mathbb{R}^d$. The model applies a sequence of linear maps and elementwise nonlinearities, and out comes a prediction $\hat{y}$. This contract is wildly successful when the data naturally arrives in vector form: pixels, audio frames, embeddings of pre-tokenized text. The moment the data has internal connectivity, however, the contract starts to strain, and the strain is not a minor implementation detail but a foundational mismatch between what the data carries and what the model can read.

Four data modalities illustrate the point. Molecules are graphs in which atoms are vertices and bonds are edges. The hydrogen count of a carbon, the electronegativity of an attached substituent, and the aromatic status of

the aromatic status of the ring it sits on are not local properties of that single carbon alone — they are properties of the carbon *together with* the specific set of neighbors the molecule happens to pose around it. Citation networks such as the Cora or DBLP datasets arrange papers as vertices and citations as directed edges; classifying a paper requires knowing not just its abstract but how the citation topology clusters it with disciplinary neighbors. Social platforms turn users into vertices and friendship or follow relations into edges; recommendation, fraud detection, and information cascade prediction all hinge on multi-hop neighborhood structure rather than on any single user's profile vector. Transaction ledgers, the kind that auditors and anti-money-laundering teams sift through every day, link accounts by payment flows, and a $\$40$ transfer that looks innocuous in isolation becomes a smoking gun when it is the fourth hop of an unwitting money-mule chain.

The unifying theme is that the *edges are half the data*. A vanilla multilayer perceptron cannot consume them because an MLP expects a fixed-length $x \in \mathbb{R}^d$, and a graph with $n$ vertices has no canonical ordering. If you feed the MLP the raw feature matrix $X \in \mathbb{R}^{n \times d}$ after arbitrarily permuting the rows, the MLP's predictions change, even though the graph you meant to feed it is mathematically identical. This is not a bug we can patch by sorting. It is a symmetry: every graph is equivalent to any of its vertex-relabeled copies, and a competent learning architecture must respect that symmetry or pay an unnecessary $n!$-fold sample-complexity tax.

The remainder of this chapter builds the vocabulary that lets us, and ultimately our models, talk about that symmetry precisely.

1.2 The Object Itself: Formal Definition and Variants

A graph is an ordered pair $G = (V, E)$ where $V$ is a finite set of vertices (we will write $|V| = n$) and $E \subseteq V \times V$ is a set of edges. When $E$ is a relation rather than a subset (because we want to allow edges between any ordered pair, including self-loops), we will write the more general $G = (V, E, X)$ where $X \in \mathbb{R}^{n \times d}$ attaches a $d$-dimensional feature vector to each vertex.

The simplest variant is the undirected simple graph: $E$ is a set of unordered pairs $\{u, v\}$ with $u \neq v$, so that $\{u, v\} = \{v, u\}$ and there is at most one edge between any two vertices. Most organic molecules are well described this way once we collapse double and triple bonds to single edges and ignore stereochemistry. The next variant is the directed graph (digraph), in which $E \subseteq V \times V$ is a set of ordered pairs $(u, v)$, so that $(u, v) \neq (v, u)$ and both can coexist. Web pages with hyperlinks, citations, and Twitter followers are all digraphs. Multigraphs permit multiple parallel edges between the same vertex pair, which is the natural model for transaction networks where Alice may pay Bob nine times in a single afternoon. We will mark multigraphs with the qualifier "multigraph" throughout and use the unadorned term "graph" for simple graphs unless the distinction is load-bearing.

Two further adjectives appear so often that we should fix them now. A graph is weighted if every edge carries a scalar $w_{uv} \in \mathbb{R}$, and attributed if vertex features $X$ (and sometimes edge features $E_{\text{feat}}$) are available. The familiar molecular dataset ZINC stores both: atomic numbers as vertex attributes and bond orders as edge attributes. We will use $G = (V, E, W, X)$ when both weights and features matter, and drop the letters that do not.

A graph with no edges is empty; a graph with every possible edge is complete, written $K_n$; a graph whose vertices can be split into two cliques with no internal edges is bipartite. These three classes are the workhorses of the toy problems that benchmark new architectures.

Two scalars summarize local structure. The degree $\deg(v) = |\{u \in V : \{u, v\} \in E\}|$ counts $v$'s neighbors in an undirected graph; in a digraph, in-degree $\deg^-(v)$ counts incoming arcs and out-degree $\deg^+(v)$ counts outgoing ones. The degree sequence is the multiset $(\deg(v_1), \ldots, \deg(v_n))$ sorted in non-increasing order, and graphs with the same degree sequence are called degree-isomorphic — a weak notion of equivalence that we will use only as a sanity check on graph generators.

> Definition 1.1 (Degree Matrix). The degree matrix of an undirected graph $G = (V, E)$ is the diagonal matrix $D \in \mathbb{R}^{n \times n}$ with $D_{ii} = \deg(v_i)$ and $D_{ij} = 0$ for $i \neq j$.

$D$ records who is locally popular. For weighted graphs we generalize to $D_{ii} = \sum_j W_{ij}$, where $W$ is the weight matrix we introduce next. For a digraph the convention is to use the out-degree unless we say otherwise.

1.3 Three Matrices That See the Same Graph Differently

Linear algebra can only digest matrix-shaped objects, so we encode a graph three ways: through its adjacency matrix, its incidence matrix, and its Laplacian. The three encodings are isomorphic in information content but differ wildly in what properties they expose cheaply.

The adjacency matrix $A \in \mathbb{R}^{n \times n}$ of an undirected simple graph is

$$ A_{ij} = \begin{cases} 1 & \text{if } \{v_i, v_j\} \in E, \\ 0 & \text{otherwise.} \end{cases} $$

For a weighted graph we replace the $1$ with the weight $w_{ij}$. For a digraph we use the convention $A_{ij} = 1 \iff (v_i, v_j) \in E$, so that $A$ is in general *not* symmetric. Symmetric adjacency matrices are exactly the undirected case, and that symmetry is wh