Part 1: Building a Sparse Cycle Graph

The edge list [(i, (i+1)%n) for i in range(n)] encodes a directed cycle: node 0 → 1 → 2 → 3 → 4 → 5 → 0. This is the simplest nontrivial sparse graph—each node has out-degree 1 and in-degree 1 (balanced). The adjacency matrix $A$ is a circulant matrix (each row is a cyclic shift of the previous row), with special structure: eigenvalues are $n$-th roots of unity $\lambda_k = e^{2\pi i k / n}$ for $k=0, \ldots, n-1$. For undirected cycles, symmetrize: A_sym = A + A.T (COO allows duplicate entries, which sum during conversion to CSR). The cycle graph is pedagogically minimal: $\text{nnz} = n$ (linear sparsity), diameter $n/2$ (maximal path length), and spectral gap $\lambda_1 - \lambda_0 = O(1/n^2)$ (slow mixing for random walks). Real-world analogs: ring topologies in distributed systems, circular dependencies in software, and polymer chains in chemistry.

Part 2: Sparse vs. Dense Matrix-Vector Multiplication

Sparse matvec (coo_matvec): Iterates over 6 stored nonzeros, performing 6 multiply-add operations. Algorithm: for (i, j, val) in zip(rows, cols, data): y[i] += val * x[j]. Cost: $O(\text{nnz})$ (6 ops). Memory access: sequential reads of rows, cols, data, random writes to y (cache-unfriendly but unavoidable for sparse). Dense matvec (@ operator): Computes all $n^2 = 36$ products $A_{ij} x_j$, including 30 zero products ($0 \times x_j = 0$, wasted computation). Cost: $O(n^2)$ (36 ops). Memory: $n^2 = 36$ floats stored. Speedup: $36/6 = 6\times$ for $n=6$. For real-world sparse matrices ($\text{nnz} \ll n^2$), speedup is $\sim n^2 / \text{nnz}$: e.g., web graph with $n=10^9$, average degree 10 yields $\text{nnz} \sim 10^{10}$, so speedup $\sim 10^{18} / 10^{10} = 10^8$ (hundred-million-fold). Numerical equivalence: Both methods compute identical results (within machine precision $\sim 10^{-16}$), confirming sparse storage is lossless—no approximation, just efficient exact arithmetic.

Part 3: Format Conversion and Computational Efficiency

COO is a storage format (easy to construct, append entries, convert from edge lists) but inefficient for repeated arithmetic. Each matvec scans all triples sequentially—no $O(1)$ access to row/column. CSR (Compressed Sparse Row) format stores indptr, indices, data arrays, enabling efficient row access: row $i$’s nonzeros are data[indptr[i]:indptr[i+1]] at columns indices[indptr[i]:indptr[i+1]]. Conversion: A_csr = A_coo.tocsr() (one-time $O(\text{nnz} \log \text{nnz})$ sort by row, then $O(\text{nnz})$ build). When to use each: (1) COO: constructing sparse matrices incrementally (FEM assembly, graph edge lists), allowing duplicates. (2) CSR: repeated row-wise operations (matvec, matrix-matrix multiply, left-multiply). (3) CSC: repeated column-wise operations (right-multiply, column access). (4) LIL (List of Lists): random access during construction (but convert to CSR/CSC for arithmetic). Production pattern: Build in COO/LIL, convert to CSR/CSC once, perform all arithmetic in CSR/CSC. SciPy default: csr_matrix for row-major, csc_matrix for column-major.

Why This Matters for ML

Graph neural networks (GNNs): Message passing layers compute $H^{(\ell+1)} = \sigma(\tilde{A} H^{(\ell)} W^{(\ell)})$, where $\tilde{A}$ is sparse normalized adjacency. For social networks ($n \sim 10^9$ users, $\text{nnz} \sim 10^{11}$ friendships), dense $\tilde{A}$ is $10^{18}$ entries (~4 exabytes)—infeasible. Sparse storage ($10^{11}$ entries, ~400 GB) enables billion-node GNNs (PyTorch Geometric, DGL). PageRank: Google’s web graph ($n \sim 10^{10}$ pages) has sparse transition matrix $P$ (average degree $\sim 10$). Sparse power iteration $r_{t+1} = \alpha P^\top r_t + (1-\alpha) \mathbf{1}$ converges in $\sim 50$ iterations at $O(\text{nnz})$ cost per iteration—dense would be $O(n^2) \sim 10^{20}$ ops (years of compute). Collaborative filtering: User-item matrices $R \in \mathbb{R}^{m \times n}$ are $< 1\%$ dense (Netflix: $10^8$ users, $10^4$ movies, $10^{10}$ ratings out of $10^{12}$ entries). Sparse storage enables matrix factorization $R \approx UV^\top$ via alternating least squares (ALS) or SGD on nonzeros only. Text embeddings: Document-term matrices $X \in \mathbb{R}^{d \times v}$ are $> 99\%$ sparse (most words absent from most documents). TF-IDF vectorization stores $\sim 10^{-4}$ of entries, enabling cosine similarity search on millions of documents. Attention masks: Block-sparse Transformers (Longformer, BigBird) use sparse attention patterns to reduce $O(L^2)$ to $O(L \log L)$ for sequence length $L$, enabling 16k-token contexts.

ML Examples and Patterns

GNN message passing (PyTorch Geometric):

from torch_geometric.nn import GCNConv
conv = GCNConv(in_channels=16, out_channels=32)
# edge_index: COO format (2, num_edges) tensor
# x: node features (num_nodes, in_channels)
x_new = conv(x, edge_index)  # Sparse neighbor aggregation

Sparse TF-IDF similarity (scikit-learn):

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
vectorizer = TfidfVectorizer()
X_sparse = vectorizer.fit_transform(documents)  # CSR matrix
similarities = cosine_similarity(X_sparse)  # Sparse @ Sparse.T

Sparse linear regression (Lasso on bag-of-words):

from scipy.sparse import csr_matrix
from sklearn.linear_model import Lasso
X_sparse = csr_matrix(X)  # (n_samples, n_features) sparse
model = Lasso(alpha=0.1)
model.fit(X_sparse, y)  # Exploits sparsity in X

PageRank via sparse power iteration:

from scipy.sparse import csr_matrix
import numpy as np
def pagerank(A, alpha=0.85, max_iter=100):
    n = A.shape[0]
    out_deg = np.array(A.sum(axis=0)).flatten()
    out_deg[out_deg == 0] = 1
    P = csr_matrix((A.data / out_deg[A.col], (A.row, A.col)), shape=A.shape).T
    r = np.ones(n) / n
    for _ in range(max_iter):
        r = alpha * (P @ r) + (1 - alpha) / n
    return r

Sparse gradient update (embedding lookup):

# Only update embeddings for tokens in batch
batch_token_ids = [42, 1337, 99999]
gradients = np.random.randn(len(batch_token_ids), embed_dim)
for idx, grad in zip(batch_token_ids, gradients):
    embeddings[idx] -= lr * grad  # Sparse update (0.003% of vocab)

Connection to Linear Algebra Theory

Graph Laplacian and sparsity: For undirected graph with adjacency $A$ and degree matrix $D = \text{diag}(\sum_j A_{ij})$, the graph Laplacian is $L = D - A$. For sparse $A$ ($\text{nnz}(A) = O(n)$), $L$ is also sparse ($\text{nnz}(L) = \text{nnz}(A) + n$). The Laplacian’s eigenvalues encode graph connectivity: $\lambda_0 = 0$ (trivial), $\lambda_1 > 0$ (Fiedler value, algebraic connectivity), and $\lambda_1$ small indicates slow mixing (bottleneck structure). Sparse eigenvalue solvers (Lanczos, ARPACK) compute top/bottom $k$ eigenpairs in $O(k \cdot \text{nnz}(L))$ time per iteration.

Sparse linear systems: For sparse $A$ with $\text{nnz}(A) = O(n)$ (tridiagonal, banded, graph Laplacian), direct solvers (sparse LU, Cholesky) have complexity $O(n^{3/2})$ to $O(n^2)$ depending on fill-in (new nonzeros created during factorization). Iterative solvers (conjugate gradient, GMRES, multigrid) achieve $O(n)$ cost per iteration when $\text{nnz}(A) = O(n)$, with convergence in $O(\sqrt{\kappa})$ to $O(\log n)$ iterations (preconditioned). For large systems ($n \sim 10^6$), iterative methods dominate.

Spectral graph theory: The eigenvectors of $L$ (or normalized Laplacian $\mathcal{L} = D^{-1/2} L D^{-1/2}$) define a Fourier basis for graph signals. Low-frequency eigenvectors (small $\lambda_k$) vary smoothly across edges (graph smoothness), while high-frequency eigenvectors oscillate. Spectral clustering: Project nodes onto the first $k$ eigenvectors of $\mathcal{L}$, then cluster via k-means. This partitions the graph to minimize cut size.

Matrix-vector product as linear combination: $y = Ax$ can be viewed as a linear combination of $A$’s columns: $y = \sum_{j=0}^{n-1} x_j A_{:,j}$. For sparse $A$, only columns with $x_j \neq 0$ contribute. This interpretation underlies sparse gradient descent: only weights corresponding to nonzero features receive updates.

Numerical and Implementation Notes

Shape discipline: $A \in \mathbb{R}^{n \times n}$ (sparse adjacency, $n=6$), $x \in \mathbb{R}^n$ (input vector), $y \in \mathbb{R}^n$ (output), $\text{nnz}(A) = 6$ (scalar). COO arrays: rows, cols $\in \mathbb{Z}^{\text{nnz}}$, data $\in \mathbb{R}^{\text{nnz}}$. Check dimensions before operations: A.shape = (n, n), x.shape = (n,), y.shape = (n,).

Gotcha 1: COO allows duplicates. Multiple (i, j, val) entries sum during conversion to CSR/CSC. Useful for FEM assembly (accumulate element contributions) but can cause bugs if unintended. Use A_coo.sum_duplicates() to merge before arithmetic.

Gotcha 2: Random access is slow. A_csr[i, j] requires binary search in row $i$’s indices ($O(\log \text{nnz})$). For sparse matrix construction with random access, use LIL format during building, then convert: A_lil[i, j] = val ($O(1)$), A_csr = A_lil.tocsr().

Gotcha 3: Sparse-dense operations. A_sparse @ x_dense is efficient ($O(\text{nnz})$), but A_dense @ x_sparse doesn’t exploit sparsity in $x$. SciPy converts sparse to dense if one operand is dense—avoid by ensuring both are sparse: A_csr @ B_csr.

Gotcha 4: Memory overhead. COO stores 3 arrays (rows, cols, data), so overhead is $3 \times \text{nnz}$ floats. For very dense matrices ($\text{nnz} > 0.3 \times n^2$), dense storage can be more efficient. CSR/CSC have lower overhead (2 arrays: indptr, indices+data), more compact for moderately sparse matrices.

Gotcha 5: Sparse linear solves. scipy.sparse.linalg.spsolve(A_csr, b) uses sparse LU factorization. For SPD matrices, use cholesky from CHOLMOD: from sksparse.cholmod import cholesky; factor = cholesky(A_csr); x = factor(b). For iterative solves: cg(A_csr, b) (conjugate gradient, requires SPD), gmres(A_csr, b) (general).

Numerical and Shape Notes

Verification checks: (1) Sparsity ratio: nnz(A) / (n * n) = 6 / 36 = 0.167 (16.7% nonzero). (2) Numerical equivalence: np.allclose(y_sparse, y_dense) should be True (exact match within tolerance $10^{-9}$). (3) Memory savings: sys.getsizeof(A_coo) < sys.getsizeof(A_dense) confirms space reduction. (4) Matvec correctness: Residual np.linalg.norm(A_dense @ x - y_sparse) < 1e-14 verifies implementation.

Cost analysis: COO matvec: $O(\text{nnz})$ operations (6 multiply-adds). Dense matvec: $O(n^2)$ operations (36 multiply-adds). Memory: COO stores $3 \times \text{nnz} = 18$ floats, dense stores $n^2 = 36$ floats. Break-even sparsity: For $\text{nnz} / n^2 > 1/3$, dense storage is more efficient (less overhead). For $\text{nnz} / n^2 < 0.1$, sparse is typically $10\times$ faster and $10\times$ more memory-efficient.

Tolerance: Sparse arithmetic is exact (no approximation), so y_sparse and y_dense should match to machine precision ($\sim 10^{-16}$ relative error). Any discrepancy indicates implementation bug. For iterative sparse solvers (CG, GMRES), residual tolerance $\|Ax - b\| / \|b\| < 10^{-6}$ is typical (converges in $\sim 10$-100 iterations for well-conditioned systems).

Pedagogical Significance

This example is the foundational entry point to sparse linear algebra for ML:

Key takeaways: (1) Sparse storage exploits structure: Store only $\text{nnz}$ nonzeros instead of $n^2$ total entries. (2) Sparse operations scale linearly: Matvec costs $O(\text{nnz})$ vs. $O(n^2)$ dense. (3) Graph adjacency matrices are naturally sparse: Bounded-degree graphs have $\text{nnz} = O(n)$. (4) Format matters: COO for construction, CSR/CSC for computation. (5) Numerical equivalence: Sparse and dense methods produce identical results (no approximation).

Common misconceptions addressed: (a) “Sparse matrices are approximate”—No, they store exact nonzeros (lossless). (b) “Sparse operations are always faster”—Only for sufficient sparsity ($\text{nnz} < 0.1 \times n^2$); overhead dominates otherwise. (c) “COO is efficient for arithmetic”—No, COO is for storage; use CSR/CSC for repeated operations. (d) “Sparse linear solves are always iterative”—No, sparse direct solvers (sparse LU, Cholesky) exist but have fill-in overhead. (e) “Sparsity only matters for massive graphs”—Sparsity benefits appear even for moderate $n \sim 10^3$ (e.g., text with $10^5$ vocabulary).

Connection to other examples: Example 71 (sparse dot products), Example 74 (sparse SVD), Example 76 (sparse least squares), Example 77 (sparse Cholesky), Example 78 (sparse preconditioning). This example provides the implementation foundation for understanding how ML scales to billion-parameter models (sparse attention), billion-node graphs (GNNs), and billion-document corpora (TF-IDF).

Why pedagogically powerful: The cycle graph is the simplest nontrivial sparse example—$\text{nnz} = n$ (linear), easy to visualize (ring topology), and transparently demonstrates the core pattern: store/iterate only nonzeros. Students see that sparsity is structure, not approximation, and that the $O(\text{nnz})$ complexity is exact arithmetic, not approximation. The $6\times$ speedup for $n=6$ is modest, but the pattern scales to $10^8\times$ for real-world problems. This is the gateway to web-scale ML—without sparse methods, GNNs on social networks, PageRank on web graphs, and Transformers on long sequences would be computationally infeasible.