Foundations of Graph Representation and Signal Processing

Graphs serve as a universal language for modeling relational data across domains as diverse as social networks, molecular chemistry, transportation systems, and knowledge graphs. At their core, graphs encode pairwise relationships between entities, capturing structural dependencies that traditional Euclidean data representations—such as grids or sequences—cannot naturally express. This structural richness introduces both opportunities and challenges: while graphs can represent complex interactions, they lack a canonical coordinate system, making the adaptation of classical signal processing techniques non-trivial. The field of Graph Neural Networks (GNNs) emerges at this intersection, seeking to generalize deep learning to non-Euclidean domains by developing operations that respect graph structure. Before constructing neural architectures, however, we must establish a rigorous mathematical foundation for representing and processing signals on graphs. This chapter builds that foundation from first principles, bridging discrete graph theory with continuous signal processing concepts. We will begin with formal graph definitions and matrix representations, progress to spectral graph theory and graph Fourier analysis, derive the theoretical basis for graph convolution, and conclude with a critical examination of the two dominant paradigms—spectral and spatial approaches—that have shaped GNN design. Throughout, we emphasize not just *what* the equations are, but *why* they are structured as they are, providing intuition through small-scale examples and computational exercises that solidify abstract concepts.

Graphs and Their Matrix Representations

A graph $G = (\mathcal{V}, \mathcal{E})$ is a fundamental combinatorial structure consisting of a set of nodes (or vertices) $\mathcal{V} = \{v_1, v_2, \dots, v_n\}$ and a set of edges $\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ that connect pairs of nodes. The cardinality $|\mathcal{V}| = n$ defines the graph's size. Graphs can be classified along several axes that determine their mathematical properties and the suitability of different processing techniques.

Directed vs. Undirected Graphs. In an *undirected* graph, edges are unordered pairs: $(v_i, v_j) \in \mathcal{E} \implies (v_j, v_i) \in \mathcal{E}$. This symmetry implies that relationships are reciprocal. In a *directed* graph (or digraph), edges are ordered pairs $(v_i, v_j)$, indicating a directional relationship from $v_i$ to $v_j$ without implying the reverse. Many real-world systems—such as citation networks (paper A cites paper B) or web link graphs—are inherently directed. The distinction affects the symmetry of matrix representations, as we shall see.

Weighted vs. Unweighted Graphs. An *unweighted* graph assigns a binary presence/absence to edges, typically represented with $A_{ij} = 1$ if $(v_i, v_j) \in \mathcal{E}$ and $0$ otherwise. A *weighted* graph associates a real-valued weight $w_{ij} > 0$ with each edge, capturing relationship strength, distance, or capacity. For instance, in a road network, edge weights might represent travel time; in a co-authorship network, they might reflect the number of joint publications. Weighted graphs are essential for modeling nuanced interactions.

Simple Graphs vs. Multigraphs vs. Hypergraphs. A *simple graph* contains no self-loops (edges from a node to itself) and at most one edge between any pair of nodes. *Multigraphs* allow multiple edges between the same node pair, useful for representing multiple relationship types. *Hypergraphs* generalize further by allowing edges (hyperedges) to connect more than two nodes, suitable for modeling group interactions (e.g., a research collaboration involving three or more authors). This chapter focuses primarily on simple, undirected, weighted graphs, as they form the basis for most GNN literature, though we will note extensions where relevant.

The Adjacency Matrix

The most common matrix representation of a graph is the adjacency matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$, defined element-wise as:

$$ A_{ij} = \begin{cases} w_{ij} & \text{if } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$

For undirected graphs, $\mathbf{A}$ is symmetric ($A_{ij} = A_{ji}$). For directed graphs, $\mathbf{A}$ is generally asymmetric. The adjacency matrix compactly encodes the graph's connectivity pattern. Its entries directly indicate edge existence and weight. Several important graph properties are immediately readable from $\mathbf{A}$:

• The *degree* of node $i$, denoted $d_i$, is the sum of weights of edges incident to $i$. For undirected graphs: $d_i = \sum_{j=1}^n A_{ij}$. For directed graphs, we distinguish *out-degree* $d_i^{out} = \sum_j A_{ij}$ and *in-degree* $d_i^{in} = \sum_j A_{ji}$.
• The number of edges $|\mathcal{E}|$ equals $\frac{1}{2}\sum_{i,j} A_{ij}$ for undirected graphs (accounting for symmetry) or $\sum_{i,j} A_{ij}$ for directed graphs.
• The *neighborhood* of node $i$, denoted $\mathcal{N}(i)$, is the set of nodes connected to $i$: $\mathcal{N}(i) = \{j \mid (v_i, v_j) \in \mathcal{E}\}$.

```mermaid graph LR A[Graph G] --> B[Adjacency Matrix A] B --> C[Symmetric for undirected graphs] B --> D[Asymmetric for directed graphs] A --> E[Node degrees from row/column sums] ```

Example 1.1: Adjacency Matrix of a Small Graph. Consider a graph with 4 nodes and edges: $(1,2)$ with weight 1, $(1,3)$ with weight 2, $(2,3)$ with weight 1, $(3,4)$ with weight 3. Assuming undirected connections, the adjacency matrix is:

$$ \mathbf{A} = \begin{bmatrix} 0 & 1 & 2 & 0 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 3 \\ 0 & 0 & 3 & 0 \end{bmatrix} $$

Node 1 has degree $d_1 = 1 + 2 = 3$; node 3 has degree $d_3 = 2 + 1 + 3 = 6$. The matrix is symmetric.

While $\mathbf{A}$ directly encodes adjacency, it does not inherently capture higher-order structural information like cycles or connectivity patterns. For many graph algorithms and spectral methods, we need alternative matrix representations that reveal global properties.

The Degree Matrix and Graph Laplacian

The degree matrix $\mathbf{D} \in \mathbb{R}^{n \times n}$ is a diagonal matrix where each diagonal entry $D_{ii} = d_i$ is the degree of node $i$, and off-diagonal entries are zero:

$$ \mathbf{D} = \begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_n \end{bmatrix} $$

The degree matrix is always positive semidefinite for non-negative degree sequences. It arises naturally when normalizing the adjacency matrix or defining operators that measure smoothness over the graph.

The most fundamental operator in spectral graph theory is the graph Laplacian (or combinatorial Laplacian), defined as:

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

Element-wise, $L_{ij} = \begin{cases} d_i & \text{if } i = j \\ -A_{ij} & \text{if } i \neq j \text{ and } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases}$

The Laplacian matrix possesses several crucial properties that make it the cornerstone of graph-based signal processing:

1. Symmetry: For undirected graphs, $\mathbf{L}$ is symmetric because both $\mathbf{D}$ and $\mathbf{A}$ are symmetric. 2. Zero row sum: For any row $i$, $\sum_{j=1}^n L_{ij} = d_i - \sum_{j \neq i} A_{ij} = d_i - d_i = 0$. This implies that the vector $\mathbf{1} = [1, 1, \dots, 1]^\top$ is an eigenvector of $\mathbf{L}$ with eigenvalue $0$, since $\mathbf{L}\mathbf{1} = \mathbf{0}$. 3. Positive semidefiniteness: $\mathbf{L}$ is positive semidefinite (PSD), meaning all its eigenvalues are non-negative. This follows from the quadratic form $\mathbf{x}^\top \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2 \geq 0$ for any $\mathbf{x} \in \mathbb{R}^n$. 4. Connectivity indicator: The multiplicity of the eigenvalue $0$ equals the number of connected components in the graph. A connected graph has exactly one zero