Graph Basics

Graph

A graph is a triple

$$G = (V,\mathcal{E},W)$$

where

• $V$ is an index set,
• $\mathcal{E} \subseteq V \times V$,
• $W : \mathcal{E} \to \mathbb{R}$.

The graph is unweighted if

$$W : \mathcal{E} \to \{0,1\}.$$

Undirected Graph

Undirected graphs can be defined similarly to the definition above. Keeping the same definition as a graph above, except changing the collection of edges,

$$\mathcal{E} \subseteq \{\{i,j\}: i,j \in V\}$$

However, every undirected graph can be embedded by a directed graph with the new set of edges,

$$\mathcal{E}_{\mathrm{dir}} = \{\, (i,j), (j,i) \mid \{i,j\} \in \mathcal{E} \,\}.$$

Note that this is still technically incompatible with the undirected graph definition above as $\mathcal{E}_{dir}$ is a set of ordered pairs, and not sets. For the rest of these notes I will treat undirected graphs as the directed graph embedding the same structure to avoid inconsistencies.

Graph Signal

For $|V|=n$, a graph signal is a function

$$x : V \to \mathbb{R}.$$

Here, the signals of the entire graph can be represented in one vector,

$$\mathbf{x} \in \mathbb{R^n}.$$

Each element in this vector corresponds to the signal in the respective node. So $x$ is the signal for the entire graph, not a single node. It's worth noting here that GNNs, going forward, can embed higher dimensional vector per node and will not be restricted to scalar values.

Neighbourhood

$$\mathcal{N}_a = \{\, j \in V \text{ s.t. } (a,j) \in \mathcal{E} \,\}$$

Or, in directed graphs,

$$\mathcal{N}_a^{out} = \{\, j \in V \text{ s.t. } (a,j) \in \mathcal{E} \,\}$$ $$\mathcal{N}_a^{in} = \{\, j \in V \text{ s.t. } (j,a) \in \mathcal{E} \,\}$$

Adjacency Matrix

For $|V|=n$, the adjacency matrix $A \in \mathbb{R}^{n \times n}$ has elements

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

Degree

For undirected graphs,

$$d(i) = \sum_{j \in V} A_{ij}.$$

For directed graphs,

$$d^{out}(i) = \sum_{j \in V} A_{ij}, \qquad d^{in}(i) = \sum_{j \in V} A_{ji}.$$