Lesson overview | Previous part | Next part

Random Graphs: Part 9: Applications in Machine Learning to Appendix K: Notation Reference

9. Applications in Machine Learning

9.1 GraphWorld: Benchmark Generation from SBM

Problem: GNN papers often report results on 3-4 standard benchmarks (Cora, Citeseer, OGBN-Arxiv). These benchmarks may not represent the diversity of graph structures encountered in practice.

GraphWorld (Palowitch et al., 2022): A benchmark generation framework that:

1. Parameterizes SBM space $(k, n, p, q, \text{features})$
2. Samples thousands of graph instances across this parameter space
3. Evaluates GNN architectures across the full parameter landscape

Key findings:

• No single GNN architecture dominates across all SBM parameters
• GCN is best on homophilic dense graphs; GIN is best near the detection threshold
• The Kesten-Stigum threshold accurately predicts when ALL GNNs fail
• Node feature quality (signal-to-noise ratio in features) often matters more than graph structure

For practitioners: When evaluating a GNN, generate benchmarks from an SBM sweep to characterize the algorithm's operating regime, rather than relying on a few fixed benchmarks.

9.2 Graph Generation: GRAN, GDSS, DiGress

Graph generation models learn to sample new graphs from a distribution. Framed probabilistically: learn a distribution $p_\theta(G)$ that matches a target distribution $p^*(G)$.

GRAN (Graph Recurrent Attention Networks, 2019): Generates graphs node-by-node, at each step attending to previously generated nodes. The attention mechanism implicitly models preferential attachment - recently added high-degree nodes attract more attention, reproducing scale-free structure.

GDSS (Jo et al., 2022): Score-based diffusion model for graphs. Joint diffusion over node features and edge features. Samples new graphs by reversing a diffusion process that gradually adds noise. The score function implicitly learns the SBM-like block structure of training graphs.

DiGress (Vignac et al., 2022): Discrete diffusion - adds/removes edges following a Markov process. Denoising model is a graph transformer that learns to predict the original edge from the noised version. DiGress can generate molecular graphs and large social networks by learning implicit graphon structure.

Random graph theory connection: Graph generation is essentially graphon estimation. Given samples from $p^*(G)$ (real graphs), estimate the underlying graphon $W^*$ such that sampling from $W^*$ approximates $p^*$. The approximation quality is measured by the cut metric $d_\square$.

9.3 LLM Attention as a Random Graph Process

Attention graph: In a transformer with $L$ layers and $H$ heads, the attention pattern at layer $\ell$, head $h$ defines a complete directed graph on tokens where edge weight $(i,j)$ is the attention score $\alpha^{(\ell,h)}_{ij}$.

Sparse attention = random graph: Sparse attention mechanisms (Longformer, BigBird, Reformer) explicitly sparsify the attention graph, keeping only $O(n)$ edges rather than $O(n^2)$. The sparsification pattern is often random or pseudo-random.

Random graph analysis of attention:

• Connectivity: Is the sparse attention graph connected? If not, information cannot flow between disconnected components. ER theory predicts connectivity iff expected degree $\ge \ln n$.
• Small-world: BigBird combines local window attention (ring lattice) with random global tokens (rewiring) and special tokens (hubs). This exactly matches the Watts-Strogatz construction!
• Expander properties: Expander graphs (high spectral gap) are the best sparse graphs for information flow. Ramanujan graphs achieve the optimal spectral gap - this motivates expander-based sparse attention.

Result: The random graph structure of sparse attention patterns determines the theoretical expressiveness of the transformer. An attention graph that is disconnected or has large diameter cannot capture long-range dependencies regardless of the weight values.

9.4 Lottery Ticket Hypothesis and Sparse Subgraphs

Lottery Ticket Hypothesis (Frankle & Carlin, 2019): A randomly initialized dense network contains sparse subnetworks ("winning tickets") that, when trained in isolation from the same initialization, achieve comparable accuracy to the dense network.

Random graph framing: Think of the neural network as a random graph where:

• Nodes = neurons
• Edges = weights (including the weight value)
• Sparsification = edge removal

The winning ticket is a sparse subgraph that retains the connectivity and flow properties of the dense graph. Random graph percolation theory describes when sparse subgraphs retain giant component connectivity.

Percolation interpretation: If we randomly retain each edge with probability $\rho$ (magnitude-based pruning approximation), the network retains its giant component iff $\rho > \rho_c$, where $\rho_c$ is the percolation threshold. For ER-like neural network graphs, $\rho_c \approx 1/(np_0)$ where $p_0$ is the original edge density.

Practical implication: Networks can be pruned to 90%+ sparsity (i.e., $\rho \approx 0.1$) while retaining performance, consistent with the existence of a giant percolating subgraph at such densities for typical neural network width/depth ratios.

9.5 Social Network Analysis at Scale

Community detection at scale: For billion-node graphs (Facebook, Twitter), exact SBM community detection is computationally infeasible. In practice:

• Louvain algorithm: Greedy modularity maximization, $O(n \log n)$
• Label propagation: Message-passing on the graph, converges in $O(\text{diam})$ steps
• GraphSAGE + semi-supervised: Use a few labeled nodes (community labels) to train GNN

Random graph models as null models: When analyzing a real social network, we ask: "Is the observed community structure more than what we'd expect by chance?" We compare to an ER null model with the same degree sequence (configuration model) and test whether the observed modularity exceeds the null expectation.

Link prediction: Predicting missing edges $(u,v)$ in a social graph using random graph models. Under ER: $\mathbb{P}[(u,v) \in E] = p$ (same for all pairs). Under SBM: $\mathbb{P}[(u,v) \in E] = B_{\sigma(u), \sigma(v)}$ - within-community edges are more likely. GNNs for link prediction learn to approximate this block-structured probability.

---

10. Common Mistakes

---

11. Exercises

Exercise 1 * - Phase Transition Simulation

Simulate the Erdos-Renyi phase transition computationally. For $n = 2000$ nodes and $p = c/n$ with $c \in [0.5, 3.0]$:

(a) Generate $G(n,p)$ for 20 values of $c$ linearly spaced in $[0.5, 3.0]$.

(b) For each graph, compute the size of the largest connected component $L_1$ and the second largest $L_2$.

(c) Plot $L_1/n$ and $L_2/n$ as functions of $c$. Identify the phase transition point visually.

(d) Overlay the theoretical prediction $\beta(c)$ satisfying $\beta = 1 - e^{-c\beta}$. Compute $\beta(c)$ numerically (Newton's method or bisection) for each $c$.

(e) Compute and plot $L_2/n$. What happens to the second-largest component at criticality? Explain from branching process theory.

---

Exercise 2 * - Degree Distribution Analysis

(a) Generate $G(n,p)$ with $n = 10000$ and $p = 5/n$. Compute the empirical degree distribution and overlay the theoretical $\text{Poisson}(5)$ PMF.

(b) Generate a BA graph with $n = 10000$ and $m = 3$. Compute the empirical degree distribution on a log-log scale and fit a power law using linear regression on the tail ($k \ge 10$). Report the estimated exponent $\hat{\gamma}$.

(c) Compare the two distributions using a Q-Q plot. What are the key structural differences?

(d) Compute the maximum degree in each model. Derive theoretically why $\max_v \deg(v) = \Theta(\log n / \log \log n)$ for ER and $\Theta(\sqrt{n})$ for BA.

---

Exercise 3 * - Small-World Analysis

Implement the Watts-Strogatz model from scratch.

(a) Build the ring lattice: $n = 500$ nodes, each connected to $k = 10$ nearest neighbors.

(b) For $\beta \in \{0, 0.001, 0.01, 0.05, 0.1, 0.3, 0.5, 1.0\}$, rewire each edge independently with probability $\beta$. Compute $C(\beta)$ and $L(\beta)$ for each value.

(c) Plot normalized clustering coefficient $C(\beta)/C(0)$ and normalized average path length $L(\beta)/L(0)$ on the same plot (both on log scale for $\beta$). Identify the small-world regime.

(d) Verify that $C(\beta) \approx C(0)(1-\beta)^3$ for small $\beta$. What does this formula say about how clustering degrades with rewiring?

---

Exercise 4 ** - Stochastic Block Model and Community Detection

(a) Sample an SBM with $n = 500$, $k = 2$ equal communities, $p = a/n$, $q = b/n$. Use $(a,b) = (20, 5)$ (above Kesten-Stigum threshold).

(b) Apply spectral clustering: compute the second eigenvector of the adjacency matrix, threshold at 0 (positive = community 1, negative = community 2), and compute accuracy (fraction of correctly classified nodes, up to community permutation).

(c) Repeat with $(a,b) = (10, 5)$ (near threshold) and $(a,b) = (6, 4)$ (below threshold). How does accuracy vary?

(d) The Kesten-Stigum threshold for 2-block SBM is $(a-b)^2 = 2(a+b)$. Verify your experimental results are consistent with this threshold.

(e) *** Implement the belief propagation algorithm (AMP / approximate message passing) for the 2-block SBM and compare accuracy to spectral clustering near the threshold.

---

Exercise 5 ** - Wigner's Semicircle Law

(a) Generate a Wigner matrix $W_n = (M + M^\top) / (2\sqrt{n})$ where $M$ has i.i.d. $\text{Normal}(0,1)$ entries, for $n \in \{50, 200, 500, 1000\}$.

(b) Plot the empirical spectral distribution (histogram of eigenvalues) for each $n$. Overlay the theoretical semicircle density $\frac{2}{\pi}\sqrt{4 - x^2}$ for $|x| \le 2$.

(c) Now set $W_n = A/\sqrt{np(1-p)}$ where $A$ is the centered adjacency matrix of $G(n,p)$ with $p = 0.3$, $n = 1000$. Plot the empirical spectral distribution. Identify the outlier eigenvalue corresponding to the average degree.

(d) For the SBM with 2 communities ($n = 1000$, $a = 15$, $b = 3$): plot the eigenvalue spectrum of $A$. Identify which eigenvalues encode community structure and which are bulk noise.

---

Exercise 6 ** - Graphon Estimation

(a) Generate a sequence of SBM graphs with $n \in \{100, 500, 2000\}$, $k = 3$ communities, and block matrix $B = \begin{pmatrix} 0.8 & 0.1 & 0.1 \\ 0.1 & 0.7 & 0.2 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}$.

(b) For each graph, sort vertices by community label (oracle information) and display the sorted adjacency matrix as a heatmap. Does it converge to the block graphon as $n$ grows?

(c) Without oracle labels: apply spectral clustering to estimate community labels, then display the sorted (estimated) adjacency matrix. Measure the cut distance $d_\square$ between the estimated and true graphon.

(d) Implement the "histogram graphon estimator": divide $[0,1]^2$ into $k^2$ bins and estimate $W$ by averaging edges within each bin. Compute the $L^2$ error $\|W_{\text{est}} - W^*\|_{L^2}$.

---

Exercise 7 *** - Giant Component Critical Window

This exercise studies the fine-grained behavior near the critical point $p = 1/n$.

(a) For $p = (1 + \lambda n^{-1/3})/n$ with $\lambda \in [-3, 3]$ and $n \in \{500, 2000, 8000\}$, compute $L_1 / n^{2/3}$ for 50 trials each. Plot the distribution of $L_1/n^{2/3}$ vs $\lambda$.

(b) Observe that the distribution has a universal shape (independent of $n$ for large $n$). This is the Brownian excursion limit - the critical window scaling is $n^{2/3}$ for the component size and $n^{1/3}$ for the window width.

(c) Compute the mean and standard deviation of $L_1 / n^{2/3}$ as functions of $\lambda$. Show that the mean crosses 0 near $\lambda = 0$ but the transition is smooth (not a jump) at finite $n$.

(d) Compare to the predicted infinite-$n$ limit: for $\lambda > 0$, $\mathbb{E}[L_1/n] \to \beta(1 + \lambda n^{-1/3}) \approx \lambda^2 n^{-1/3} \cdot C$ for some constant $C$. Verify this scaling.

---

Exercise 8 *** - Preferential Attachment Dynamics

(a) Implement the Barabasi-Albert preferential attachment model for $n = 5000$ nodes with $m = 2$ edges per new node. Use the efficient alias method or linear scan for sampling.

(b) After generation, fit the degree distribution tail to a power law $P(k) = C k^{-\gamma}$ using maximum likelihood estimation on $k \ge k_{\min}$ for suitable $k_{\min}$.

(c) Track the degree of each node over time as the network grows. Plot $k_i(t)$ for nodes added at times $t_i \in \{10, 100, 500, 1000\}$. Verify the mean-field prediction $k_i(t) \approx m\sqrt{t/t_i}$.

(d) Implement "fitness-based" preferential attachment: $\Pi(v) \propto \eta_v \deg(v)$ where $\eta_v \sim \text{Uniform}[0,1]$ is a fixed fitness. Compare the resulting degree distribution to standard BA. Does the power-law exponent change?

(e) Simulate a targeted attack: iteratively remove the highest-degree node. Plot the size of the giant component as a function of fraction of nodes removed. Compare to random removal. What fraction of nodes must be targeted to destroy the giant component?

---

12. Why This Matters for AI (2026 Perspective)

---

13. Conceptual Bridge

Backward: What This Builds On

Random graph theory synthesizes several branches of mathematics developed in earlier sections:

From Spectral Graph Theory (04): The Laplacian eigenvalues $\lambda_2, \ldots, \lambda_n$ studied there take on probabilistic meaning here - for random graphs, they become random variables following the Wigner semicircle law. The spectral gap $\lambda_2$ that controls mixing time in deterministic graphs now becomes a random quantity whose distribution determines community detectability.

From Probability Theory (07-Probability-Statistics): All threshold results (giant component, connectivity, community detection) use first and second moment methods, Chernoff bounds, and the Poisson limit theorem. Branching process theory is the probabilistic tool that gives the exact threshold equation $\beta = 1 - e^{-c\beta}$.

From Graph Neural Networks (05): The SBM community detection problem IS the node classification problem that GNNs solve in practice. The Kesten-Stigum threshold gives the hard limit on what any GNN can achieve, while Davis-Kahan shows why spectral GNNs succeed above this threshold.

Forward: What This Enables

Functional Analysis (12): The graphon operator $T_W h(x) = \int_0^1 W(x,y)h(y)\,dy$ is a Hilbert-Schmidt operator on $L^2[0,1]$. Its spectral theory - the Hilbert-Schmidt theorem giving a countable orthonormal eigenfunction expansion - is the infinite-dimensional generalization of the adjacency matrix eigendecomposition. This is the full treatment of graphon operators.

Graph Algorithms (07): Random graph models motivate efficient algorithms: spectral clustering (from SBM theory), Louvain community detection (from modularity theory), and link prediction (from random graph null models). The average-case complexity of graph problems is analyzed using random graph models.

Information Theory (09): The Kesten-Stigum threshold is an information-theoretic limit - it follows from a channel capacity argument. The mutual information between the community labels $\sigma$ and the observed graph $G$ is zero below the threshold, making recovery impossible regardless of computation. This connects random graphs to channel coding theory.

POSITION IN CURRICULUM
========================================================================

  04 Spectral Graph Theory
       |  Laplacians, eigenvalues, Cheeger inequality
       |
       +--> 05 Graph Neural Networks
       |         GCN, GAT, GIN, MPNN, expressiveness
       |
       +--> 06 Random Graphs  <=== YOU ARE HERE
                |
                +- Erdos-Renyi: phase transitions, thresholds
                +- Watts-Strogatz: small-world, navigation
                +- Barabasi-Albert: scale-free, preferential attachment
                +- SBM: communities, Kesten-Stigum threshold
                +- Spectral theory: semicircle law, Davis-Kahan
                +- Graphons: infinite limits, universality
                       |
                       v
                07 Graph Algorithms
                       |
                       v
                12 Functional Analysis <-- graphon operators T_W
                       Hilbert-Schmidt theory, L^2 spectral decomposition

========================================================================

The central insight of this section - that random graph models are not merely toy examples but rigorous frameworks for understanding real network behavior - carries forward into every domain where graphs appear. In machine learning, understanding when community structure is detectable, when information can flow across a sparse graph, and when a graph distribution can be learned from samples are fundamental questions with precise mathematical answers, and those answers come from random graph theory.

---

<- Back to Graph Theory | Next: Graph Algorithms ->

---

Appendix A: Branching Process Theory

A.1 Galton-Watson Branching Processes

A Galton-Watson process is a model of population growth where each individual independently produces offspring according to a fixed offspring distribution $\{p_k\}_{k \ge 0}$.

Formal definition: Let $Z_0 = 1$ (a single ancestor). At generation $t$, if $Z_t = z$, each of the $z$ individuals produces offspring independently according to $\{p_k\}$:

$$Z_{t+1} = \sum_{i=1}^{Z_t} \xi_i^{(t)}$$

where $\xi_i^{(t)} \sim \{p_k\}$ i.i.d.

Mean offspring: $\mu = \sum_k k p_k = \mathbb{E}[\xi]$.

Probability generating function (PGF): $\phi(s) = \sum_k p_k s^k = \mathbb{E}[s^\xi]$.

Extinction probability: The probability of ultimate extinction $q = \lim_{t \to \infty} \mathbb{P}[Z_t = 0]$ satisfies $q = \phi(q)$.

Theorem (Extinction):

• If $\mu \le 1$: $q = 1$ (certain extinction)
• If $\mu > 1$: $q < 1$ (positive survival probability $= 1 - q$)

Connection to ER: For $G(n,p)$ with $p = c/n$, exploring the component of a vertex proceeds like a branching process where each node has $\text{Binomial}(n-k, c/n) \approx \text{Poisson}(c)$ offspring (unexplored neighbors). The giant component probability $\beta$ satisfies:

$$1 - \beta = q = e^{-c\beta} = \phi_{\text{Poisson}(c)}(1 - \beta)$$

exactly the fixed-point equation $\beta = 1 - e^{-c\beta}$.

A.2 Multi-Type Branching Processes

For the SBM with $k$ communities, the local neighborhood exploration is a multi-type branching process where the type of an individual is its community label.

Offspring matrix: $M_{rs}$ = expected number of type-$s$ offspring from a type-$r$ parent.

For the symmetric 2-block SBM with $p = a/n$, $q = b/n$:

$$M = \frac{1}{2}\begin{pmatrix} a & b \\ b & a \end{pmatrix}$$

Survival theorem: The multi-type branching process survives iff $\rho(M) > 1$, where $\rho(M)$ is the spectral radius.

Eigenvalues of $M$: $\lambda_+ = (a+b)/2$, $\lambda_- = (a-b)/2$.

• Giant component exists iff $\lambda_+ > 1$, i.e., $a + b > 2$ (average degree condition).
• Community detection possible iff the "community eigenvalue" $\lambda_- = (a-b)/2 > 1$ ... but this is not quite right. The actual condition involves the non-backtracking matrix.

Non-backtracking operator: The correct spectral condition for SBM community detection uses the non-backtracking (Hashimoto) operator $B$ on directed edges. The eigenvalue of $B$ corresponding to community structure is $(a-b)/2$, and the bulk spectral radius is $\sqrt{(a+b)/2}$. Community detection is possible iff:

$$\frac{a-b}{2} > \sqrt{\frac{a+b}{2}}$$

i.e., $(a-b)^2 > 2(a+b)$ - precisely the Kesten-Stigum threshold.

A.3 Critical Branching Processes

At criticality $\mu = 1$ (Poisson offspring with $c = 1$), the branching process has a different behavior:

Yaglom's theorem: Conditioned on survival to generation $t$, the population $Z_t / t$ converges in distribution to an Exponential(1) random variable:

$$\mathbb{P}[Z_t / t > x \mid Z_t > 0] \to e^{-x}$$

For the ER critical window: At $p = 1/n$, the largest component has size $\Theta(n^{2/3})$ and there are $\Theta(n^{1/3})$ such components. The component size distribution follows Yaglom's theorem for the critical Poisson branching process, but rescaled by $n^{2/3}$.

---

Appendix B: Configuration Model

B.1 Definition

The configuration model generates a random graph with a prescribed degree sequence $(d_1, d_2, \ldots, d_n)$.

Construction:

1. Give vertex $v$ exactly $d_v$ "half-edges" (stubs)
2. Pair up all $2m = \sum_v d_v$ half-edges uniformly at random
3. Each pairing creates an edge

Result: A random multigraph (may have self-loops and multi-edges) with the given degree sequence.

Properties:

• For degree sequences with bounded maximum degree: the number of self-loops and multi-edges is $O(1)$ - a simple graph w.h.p.
• Conditioned on simplicity: uniform over all simple graphs with the given degree sequence

Why use it? The configuration model is the correct null model for testing graph hypotheses. Instead of comparing to ER (wrong degree distribution), compare to configuration model (same degree distribution, no other structure). If a property (e.g., high clustering) exceeds what configuration model predicts, it's genuinely structural, not just a degree artifact.

B.2 Giant Component in Configuration Model

For the configuration model with degree distribution $P(k)$:

Molloy-Reed criterion: A giant component exists iff:

$$\sum_k k(k-2) P(k) > 0 \iff \frac{\mathbb{E}[k^2]}{\mathbb{E}[k]} > 2$$

Interpretation: The excess degree distribution $q_k = (k+1)P(k+1)/\mathbb{E}[k]$ governs the branching factor of the exploration process. The process is supercritical (giant component exists) iff the mean of $q_k$ exceeds 1, which is $\mathbb{E}[k(k-1)]/\mathbb{E}[k] > 1$.

For scale-free networks: With $P(k) \propto k^{-\gamma}$, $\mathbb{E}[k^2]$ diverges when $\gamma \le 3$. Hence the Molloy-Reed criterion is always satisfied for BA-style scale-free networks - a giant component exists for arbitrarily sparse scale-free graphs.

For ER: $P(k) = e^{-c} c^k / k!$ (Poisson), so $\mathbb{E}[k^2] = c^2 + c$ and $\mathbb{E}[k] = c$. Molloy-Reed: $(c^2 + c)/c > 2 \Leftrightarrow c + 1 > 2 \Leftrightarrow c > 1$ - exactly the ER threshold.

B.3 Clustering in Configuration Model

For the configuration model:

$$C_{\text{conf}} = \frac{(\mathbb{E}[k^2] - \mathbb{E}[k])^2}{n \cdot \mathbb{E}[k]^3} \to 0$$

as $n \to \infty$ (for fixed degree distribution). The configuration model has vanishing clustering coefficient - it's locally tree-like.

Real networks vs. configuration model: Comparing observed clustering to $C_{\text{conf}} \approx 0$ tests for genuine clustering beyond degree effects. Small-world networks have $C \gg C_{\text{conf}}$ - they have clustering not explained by degree distribution alone.

---

Appendix C: Percolation Theory

C.1 Bond Percolation on Graphs

Bond percolation: Given a graph $G$ and probability $\rho \in [0,1]$, independently retain each edge with probability $\rho$. Let $G_\rho$ denote the resulting random subgraph.

Site percolation: Independently retain each vertex with probability $\rho$.

Critical probability: The percolation threshold $\rho_c$ is the infimum of $\rho$ for which $G_\rho$ has an infinite component (on infinite graphs) or a giant component of size $\Theta(n)$ (on finite graphs).

On the integer lattice $\mathbb{Z}^d$: Exact thresholds:

• $d = 1$: $\rho_c = 1$ (must keep all edges)
• $d = 2$ (square lattice): $\rho_c = 1/2$ exactly (by self-duality)
• $d \ge 2$: $\rho_c < 1$; harder to compute exactly

On ER graphs: Bond percolation on $G(n,p_0)$ with retention probability $\rho$ gives $G(n, \rho p_0)$. The percolation threshold is $\rho_c = 1/(np_0)$, so the giant component survives iff $\rho > 1/(np_0)$, i.e., $\rho np_0 > 1$.

C.2 Connection to Neural Network Pruning

Neural network weight pruning is isomorphic to bond percolation:

• Dense network graph $G$ (neurons = nodes, weights = edges)
• Pruning mask $m_{ij} \in \{0,1\}$ with $\mathbb{P}[m_{ij} = 1] = \rho$ (retention probability)
• Pruned network $G_\rho$ must retain computational connectivity

For the network to maintain its computational capacity, it must retain a giant component. The percolation threshold $\rho_c$ gives the minimum retention rate.

Structured pruning: Head pruning in transformers (removing entire attention heads) is site percolation on the attention head graph. Magnitude pruning selects edges by weight magnitude - approximately bond percolation with $\rho =$ fraction of weights retained.

Lottery ticket connection: A winning lottery ticket is precisely a giant percolating subgraph that retains the "signal paths" of the original network. The existence of such subgraphs at high sparsity ($\rho \approx 0.1$) is guaranteed by percolation theory for sufficiently wide networks.

C.3 Expanders and Optimal Percolation

Expander graph: A $d$-regular graph $G$ on $n$ nodes with spectral gap $\lambda(G) = d - \lambda_2(A_G)$. Large spectral gap means fast mixing and high robustness.

Percolation on expanders: For a $d$-regular expander, the percolation threshold is $\rho_c = 1/(d - \lambda(G)/d)^{-1} \approx 1/(d - 1)$ for bounded-degree expanders. The giant component after percolation at $\rho > \rho_c$ has size $\ge (1 - \epsilon)n$ for small $\epsilon$.

Implication for sparse attention: Expander-based sparse attention (using Ramanujan graphs with spectral gap $\approx d - 2\sqrt{d-1}$) achieves:

• $O(n)$ edges (efficient)
• $O(\log n)$ diameter (short paths)
• Maximum spectral gap (optimal information flow)
• Robust to random edge removal (good percolation threshold)

This is why expanders are theoretically optimal sparse attention patterns, even if not used in practice due to implementation complexity.

---

Appendix D: Threshold Functions - Complete Table

Sharp vs. coarse thresholds:

A threshold $p^*(n)$ is sharp if the transition from probability 0 to probability 1 occurs in a window of width $o(p^*)$. Connectivity and Hamiltonian cycles have sharp thresholds (window width $O(1/n) \ll \ln(n)/n$).

A threshold is coarse if the window is $\Theta(p^*)$. Most subgraph appearance thresholds are coarse - the probability transitions from $\epsilon$ to $1-\epsilon$ over a multiplicative constant change in $p$.

Friedgut's theorem (1999): Every monotone property has a sharp threshold OR can be reduced to a "small" property. Most natural properties (connectivity, $k$-colorability) have sharp thresholds. This is the technical statement of the Bollobas-Thomason heuristic.

---

Appendix E: Random Geometric Graphs

E.1 Definition

A random geometric graph $G(n, r)$ is constructed by:

1. Placing $n$ nodes uniformly at random in $[0,1]^2$ (or another metric space)
2. Connecting two nodes iff their Euclidean distance is $\le r$

Properties:

• Soft threshold for connectivity: $r^* = \sqrt{\ln n / (\pi n)}$ - same $\ln n / n$ scaling as ER
• High clustering: Nodes close to each other share many common neighbors (geometric constraint) - $C \to 1$ as $r \to 0$ with $nr^2$ fixed
• Bounded degree distribution: All degrees in $[0, \pi n r^2]$
• No long-range edges: Maximum edge length $= r$, giving large diameter for small $r$

For AI: Random geometric graphs model sensor networks, robotic swarms, and spatial point processes. They also model attention in vision transformers where tokens correspond to image patches at geometric positions - nearby patches should have high attention, distant patches low.

E.2 Comparison to Other Models

E.3 Connection to Kernel Methods

The random geometric graph adjacency matrix is a kernel matrix:

$$A_{ij} = \mathbf{1}[\|x_i - x_j\|_2 \le r] = k(x_i, x_j)$$

with kernel $k(x,y) = \mathbf{1}[\|x-y\| \le r]$ (indicator kernel).

More generally, kernel random graphs use $A_{ij} \sim \text{Bernoulli}(k(x_i, x_j))$ for a kernel function $k: \mathcal{X}^2 \to [0,1]$. This is a graphon with $W(x,y) = k(x,y)$ for node types $x,y \in \mathcal{X}$.

For attention: The softmax attention matrix $\text{softmax}(QK^\top/\sqrt{d})$ is a random kernel matrix where the "positions" are query/key vectors. Random graph theory for kernel random graphs directly applies to study information flow in attention layers.

---

Appendix F: Network Motifs and Subgraph Statistics

F.1 Network Motifs

Definition: A network motif is a subgraph pattern that occurs significantly more often in a real network than in random graphs with the same degree sequence (configuration model null).

Common motifs:

• Feedforward loop (3-node DAG): overrepresented in gene regulatory networks
• Bifan (2->2->2 bipartite): common in neural circuits
• Clique ($K_3$, $K_4$): overrepresented in social networks

Detection: For each candidate subgraph $H$, compare $t(H, G_{\text{real}})$ (density in real graph) to $\mathbb{E}[t(H, G_{\text{config}})]$ (expected density under null model). Z-score $> 2$: motif. Z-score $< -2$: anti-motif.

For GNNs: Motif counting is a proxy for what GNNs learn. Standard MPNNs (GCN, GraphSAGE) can count triangles but not 4-cycles. Higher-order GNNs (OSAN, subgraph GNNs) can count richer motif sets. The motif profile of a graph determines which GNN architecture is most suitable.

F.2 Triangle Counting at Scale

Exact triangle count: For dense graphs, $T = \frac{1}{6}\text{tr}(A^3)$ using matrix multiplication in $O(n^{2.37})$ (matrix multiplication exponent). For sparse graphs ($m = O(n)$), algorithms run in $O(m^{3/2})$.

Approximate counting: For massive graphs ($n = 10^9$), use streaming algorithms or random sampling:

• Wedge sampling: Count triangles by sampling paths of length 2 and checking closure
• DOULION: Sample edges independently with probability $\rho$; count triangles in subgraph; scale by $1/\rho^3$

Expected triangle count in $G(n,p)$: $\mathbb{E}[T] = \binom{n}{3} p^3 \approx n^3 p^3 / 6$.

Concentration: For $np^3 n^2 \to \infty$, by Azuma-Hoeffding (Lipschitz condition), $T$ concentrates around its mean with standard deviation $O(\text{mean}/\sqrt{n})$.

---

Appendix G: Information-Theoretic Limits

G.1 Mutual Information and Detection

The detection problem: Given $G \sim \text{SBM}(n, 2, \sigma, p, q)$, recover $\sigma$ (up to global flip).

Impossible regime: Below the Kesten-Stigum threshold, the mutual information $I(\sigma; G) = 0$ in the $n \to \infty$ limit. This means the graph $G$ contains literally no information about the community labels that could be extracted by any algorithm.

Formal statement: For $p = a/n$, $q = b/n$, $(a-b)^2 \le 2(a+b)$:

$$\lim_{n \to \infty} I(\sigma; G) / n = 0$$

The $/ n$ normalization is because both $\sigma$ and $G$ grow with $n$; the mutual information per node goes to 0.

Above threshold: For $(a-b)^2 > 2(a+b)$:

$$\lim_{n \to \infty} I(\sigma; G) / n = h_b\left(\frac{1+\alpha^*}{2}\right) - h_b\left(\frac{1}{2}\right) > 0$$

where $\alpha^*$ is the Bayes-optimal overlap and $h_b$ is binary entropy.

G.2 Exact Recovery Threshold

For the exact recovery problem (recover $\sigma$ exactly, not just correlate with it), the threshold is higher:

Theorem (Abbe-Sandon, 2015): For the 2-block SBM with $p = a \ln(n)/n$, $q = b \ln(n)/n$:

$$\text{Exact recovery is possible w.h.p.} \iff \left(\sqrt{a} - \sqrt{b}\right)^2 > 2$$

This is the CHI-squared divergence condition between the Poisson distributions with means $a$ and $b$.

The three thresholds:

1. Impossible: $(a-b)^2 \le 2(a+b)$ - no algorithm can detect communities
2. Weak recovery: $(a-b)^2 > 2(a+b)$ - algorithms exist to partially recover
3. Exact recovery: $(\sqrt{a} - \sqrt{b})^2 > 2$ - algorithms exist for exact recovery

These thresholds become relevant for GNN practitioners when designing tasks: is the community detection problem in your benchmark achievable at all? Which threshold regime does it fall in?

---

Appendix H: Practical Algorithms

H.1 Spectral Clustering Pipeline for SBM

INPUT: Adjacency matrix A of SBM graph with k communities
OUTPUT: Community assignments \sigma

1. REGULARIZE: Compute A_reg = A + \tau/n * 11^T (small ridge)
   (Prevents leading eigenvector being dominated by high-degree nodes)

2. NORMALIZE: Compute L_sym = D^{-1/2} A_reg D^{-1/2}

3. EIGENVECTORS: Compute top k eigenvectors U \in R^{n\timesk} of L_sym

4. NORMALIZE ROWS: Let U_row = U / ||u_i||_2 (spherical projection)

5. k-MEANS: Run k-means on rows of U_row, get cluster labels \sigma

6. RETURN: \sigma (up to global permutation)

COMPLEXITY: O(n*k/\epsilon^2) for sparse graphs (k power iterations)
ACCURACY: Achieves min error rate above Kesten-Stigum threshold

H.2 Louvain Community Detection

The Louvain algorithm maximizes modularity $Q$, a measure of community quality:

$$Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{d_i d_j}{2m} \right] \delta(\sigma_i, \sigma_j)$$

Phase 1 (local optimization): For each node $v$, move $v$ to the neighboring community that maximizes $\Delta Q$. Repeat until no improvement.

Phase 2 (aggregation): Collapse each community into a supernode. Edge weights between supernodes = total edges between original communities. Apply Phase 1 to the collapsed graph.

Repeat until no further improvement.

Complexity: $O(n \log n)$ empirically - the fastest practical community detection algorithm.

Limitation: Modularity has a resolution limit: communities smaller than $\sqrt{m}$ edges may not be detected. For fine-grained community structure, use alternatives (Infomap, hierarchical spectral methods).

H.3 Fast Giant Component Detection

def giant_component_fraction(A, n):
    """Compute giant component size via BFS."""
    visited = [False] * n
    max_component = 0
    
    for start in range(n):
        if visited[start]:
            continue
        # BFS from start
        queue = [start]
        visited[start] = True
        component_size = 0
        while queue:
            v = queue.pop(0)
            component_size += 1
            for u in range(n):
                if A[v][u] and not visited[u]:
                    visited[u] = True
                    queue.append(u)
        max_component = max(max_component, component_size)
    
    return max_component / n

For sparse adjacency lists (CSR format), BFS runs in $O(n + m)$ - linear in the graph size.

---

End of 06 Random Graphs notes.

---

Appendix I: Advanced Topics in Random Graphs

I.1 Local Weak Convergence (Benjamini-Schramm)

For sparse graph sequences where edge density $\to 0$, graphon theory breaks down. The correct limit theory uses local weak convergence.

Definition (Benjamini-Schramm limit): A sequence of graphs $G_n$ converges in the local weak sense to a random rooted graph $(G, \rho)$ if for every rooted graph $(H, v)$ and every $r \ge 0$:

$$\frac{1}{n} |\{u \in V(G_n) : B_r(G_n, u) \cong (H, v)\}| \to \mathbb{P}[B_r(G, \rho) \cong (H, v)]$$

where $B_r(G, u)$ is the ball of radius $r$ around $u$ in $G$.

For $G(n, c/n)$: The local weak limit is the Galton-Watson tree with Poisson($c$) offspring distribution - an infinite random tree. This confirms the "locally tree-like" structure of sparse ER graphs.

For BA networks: The local weak limit involves correlated degree distributions due to preferential attachment - the limiting tree is not a Galton-Watson tree but a Polya urn tree.

For SBM: The local weak limit is a multi-type Galton-Watson tree where the types are community labels. This is the probabilistic foundation of the belief propagation algorithm for community detection.

I.2 Random Regular Graphs

Definition: A $d$-regular random graph on $n$ vertices is a graph chosen uniformly at random among all $d$-regular simple graphs on $n$ vertices.

Construction (configuration model): Give each vertex $d$ stubs, pair uniformly at random, condition on simplicity.

Spectral properties: For $d$-regular random graphs, the eigenvalues are in $[-(2-\epsilon)\sqrt{d-1}, d]$ w.h.p. The Alon-Boppana bound says $\lambda_2 \ge 2\sqrt{d-1} - o(1)$ for any $d$-regular graph. A Ramanujan graph achieves equality: $\lambda_2 = 2\sqrt{d-1}$.

Alon conjecture (proved by Friedman, 2008): Almost all $d$-regular random graphs are Ramanujan:

$$\lambda_2(G) \le 2\sqrt{d-1} + \epsilon$$

for any fixed $\epsilon > 0$.

For AI: Expanders (near-Ramanujan regular graphs) provide the optimal sparse attention pattern:

• $d$ edges per node (linear total edges)
• Diameter $O(\log n)$ (short paths)
• Spectral gap $\approx d - 2\sqrt{d-1}$ (fast mixing)

I.3 Random Hypergraphs

Real-world networks often have higher-order interactions - a chemistry reaction involves multiple molecules simultaneously. Hypergraphs capture this.

Definition: A hypergraph $H = (V, E)$ where edges $e \in E$ can contain any number of vertices.

Random $k$-uniform hypergraph $G^k(n,p)$: Each $k$-subset of $V$ is an edge independently with probability $p$.

Phase transition: The giant component threshold for $G^k(n,p)$ occurs at $p = 1/\binom{n-1}{k-1}$ (average degree 1). The analysis uses a multi-type branching process.

For AI: Simplicial complex neural networks (SCNNs) and topological data analysis (TDA) use higher-order graph structure. Random simplicial complexes (random clique complexes of ER graphs) model the topological structure of neural network activation spaces.

I.4 Dynamic Random Graphs

Real networks evolve over time. Several models capture network dynamics:

Forest Fire model (Leskovec et al., 2007): A new node contacts a random "ambassador" and copies some of its links. Exhibits densification (average degree increases over time) and shrinking diameter - both observed in real growing networks.

Copying model: Each new node copies $m$ existing edges from a random source node. This generates power-law degree distributions similar to BA but with different exponent depending on copy probability.

Edge dynamics: Instead of just adding edges, allow edge rewiring, deletion, and creation. Models temporal networks (who talked to whom at time $t$). The temporal analog of clustering coefficient and path length requires time-respecting paths.

For AI: Training data graphs (social networks, citation graphs) evolve over time. Distribution shift in graph ML often comes from temporal evolution of the underlying random graph model. A GNN trained on a 2019 citation graph may fail on a 2024 citation graph if the graph generative process has changed.

---

Appendix J: Mathematical Proofs

J.1 Proof: Giant Component Threshold (Upper Bound)

We prove: for $c < 1$, all components have size $O(\log n)$ w.h.p.

Proof: Let $X_k$ = number of connected components of size exactly $k$ in $G(n,p)$ with $p = c/n$.

The probability that a specific set $S$ of $k$ vertices forms a component involves:

1. The internal graph on $S$ being connected: probability $\ge (1-p)^{k(k-1)/2} \cdot [\text{connectivity}]$
2. No edges from $S$ to $V \setminus S$: probability $(1-p)^{k(n-k)}$

By union bound:

$$\mathbb{E}[X_k] \le \binom{n}{k} \cdot k^{k-2} p^{k-1} \cdot (1-p)^{k(n-k)}$$

using Cayley's formula ($k^{k-2}$ labeled trees on $k$ vertices, each connected tree is a spanning tree of its component).

For $p = c/n$ and $k \le K \log n$:

$$\mathbb{E}[X_k] \le \frac{n^k}{k!} \cdot k^{k-2} \cdot (c/n)^{k-1} \cdot e^{-ck(n-k)/n}$$ $$\approx \frac{c^{k-1} k^{k-2}}{k! \cdot n} \cdot e^{-ck(1 - k/n)}$$ $$\lesssim \frac{1}{n} \cdot \frac{(ce^{1-c})^k}{k^{3/2}}$$

(using Stirling: $k! \approx k^k e^{-k} \sqrt{2\pi k}$, $k^{k-2}/k! \approx e^k k^{-2}/\sqrt{2\pi k}$)

For $c < 1$: $ce^{1-c} < 1$ (since $f(c) = ce^{1-c}$ has $f(1) = 1$, $f'(1) = 0$, $f''(1) = -1 < 0$ - it's a maximum at $c = 1$). Let $\alpha = ce^{1-c} < 1$.

Summing over $k = 2, 3, \ldots, \infty$:

$$\sum_k \mathbb{E}[X_k] \lesssim \frac{1}{n} \sum_k \alpha^k k^{-3/2} = \frac{C}{n} \to 0$$

By Markov's inequality, the total number of vertices in components of size $\ge 2$ is $O(1) = o(n)$, so the maximum component size is $O(\log n)$. $\square$

J.2 Proof: Poisson Degree Distribution

Claim: For $G(n,p)$ with $p = c/n$, $\deg(v) \xrightarrow{d} \text{Poisson}(c)$.

Proof via PGF: The degree $\deg(v) = \sum_{u \neq v} X_{uv}$ where $X_{uv} \sim \text{Bernoulli}(c/n)$ i.i.d.

PGF of $\deg(v)$:

$$G_{\deg}(s) = \mathbb{E}[s^{\deg(v)}] = \prod_{u \neq v} \mathbb{E}[s^{X_{uv}}] = \left(1 - \frac{c}{n} + \frac{cs}{n}\right)^{n-1}$$

Taking $n \to \infty$:

$$\left(1 + \frac{c(s-1)}{n}\right)^{n-1} \to e^{c(s-1)} = \sum_{k=0}^\infty \frac{e^{-c} c^k}{k!} s^k$$

which is the PGF of $\text{Poisson}(c)$.

Since PGF convergence (for $|s| \le 1$) implies distributional convergence (by continuity theorem for generating functions), $\deg(v) \xrightarrow{d} \text{Poisson}(c)$. $\square$

Multivariate extension: For distinct vertices $v_1, \ldots, v_m$, their degrees are jointly Poisson in the limit, with joint PGF:

$$\mathbb{E}\left[\prod_{i=1}^m s_i^{\deg(v_i)}\right] \to e^{\sum_i c_i(s_i - 1)}$$

where $c_i = c$ for all $i$. But the joint distribution is NOT independent Poisson (edges between $v_i$ and $v_j$ contribute to both $\deg(v_i)$ and $\deg(v_j)$). For fixed $m$, the correlation between degrees of $v_1$ and $v_2$ is $p = c/n \to 0$, so they are asymptotically independent.

J.3 Proof sketch: Davis-Kahan Theorem

Simplified version: Let $A = \bar{A} + W$ where $\bar{A}$ has eigenvalue $\bar{\lambda}$ and unit eigenvector $\bar{u}$. Let $\hat{u}$ be the unit eigenvector of $A$ corresponding to eigenvalue $\hat{\lambda}$ nearest to $\bar{\lambda}$. Let $\delta = \min_{\mu \in \sigma(\bar{A}) \setminus \{\bar{\lambda}\}} |\bar{\lambda} - \mu|$ (gap to other eigenvalues).

Claim: $\sin\angle(\hat{u}, \bar{u}) \le \|W\|_{op} / (\delta - \|W\|_{op})$ (assuming $\delta > \|W\|_{op}$).

Proof: Decompose $\hat{u} = \alpha \bar{u} + \beta v$ where $v \perp \bar{u}$, $|\alpha|^2 + |\beta|^2 = 1$, and $\sin\angle(\hat{u}, \bar{u}) = |\beta|$.

From $A\hat{u} = \hat{\lambda}\hat{u}$: $\bar{A}\hat{u} + W\hat{u} = \hat{\lambda}\hat{u}$.

Project onto $\bar{u}^\perp$: $P_{\bar{u}^\perp} \bar{A} P_{\bar{u}^\perp} (\beta v) + P_{\bar{u}^\perp} W \hat{u} = \hat{\lambda} \beta v$.

All eigenvalues of $P_{\bar{u}^\perp} \bar{A} P_{\bar{u}^\perp}$ are at distance $\ge \delta$ from $\hat{\lambda}$ (which is close to $\bar{\lambda}$):

$$\|(P_{\bar{u}^\perp} \bar{A} P_{\bar{u}^\perp} - \hat{\lambda} I)^{-1}\|_{op} \le \frac{1}{\delta - |\hat{\lambda} - \bar{\lambda}|}$$

Therefore:

$$|\beta| = \|P_{\bar{u}^\perp}(P_{\bar{u}^\perp} \bar{A} P_{\bar{u}^\perp} - \hat{\lambda} I)^{-1} P_{\bar{u}^\perp} W \hat{u}\| \le \frac{\|W\|_{op}}{\delta - \|W\|_{op}}$$

This gives the Davis-Kahan bound. $\square$

---

Appendix K: Notation Reference

---

<- Back to Graph Theory | Next: Graph Algorithms ->

---