Graph Neural Network

458. Graph Neural Network

Node Embedding:

𝑥_{1}

𝑥_{2}

\dots

𝑥_{𝑛}

Edge Embedding:

𝑥_{1}

𝑥_{2}

\dots

𝑥_{𝑛}

Adjacency Matrix:

[\begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}]

Node-level predictions
Edge-level predictions
Graph-level predictions

Graph Data

Size variant
Isomorphism: permutation invariance
Grid structure: non-euclidian

458.0.1. Message Passing

Allows nodes in a graph to exchange information and update their representations (embeddings) based on their local neighborhood

𝐺 = (𝑉, 𝐸)

Where:

$𝑉$ : set of nodes ( $| 𝑉 | = 𝑛$ )
$𝐸 \subseteq 𝑉 \times 𝑉$ : set of edges
$ℎ_{𝑣}^{𝑘} \in ℝ^{𝑑}$ : feature (embedding) of node $𝑣$ at iteration $𝑘$
$𝒩︀ (𝑣)$ : set of neighbors of node $𝑣$

Step 1: Message computation

Each node $𝑣$ receives messages from its neighbors $𝑢 \in 𝒩︀ (𝑣)$ . A message function $𝑀$ defines how information is sent:

𝐦_{𝑣}^{𝑘} = \sum_{𝑢 \in 𝒩︀ (𝑣)} 𝑀 (𝐡_{𝑣}^{𝑘 - 1}, 𝐡_{𝑢}^{𝑘 - 1}, 𝑒_{𝑢 𝑣})

$𝐡_{𝑢}^{𝑘 - 1}$ : source (neighbor)
$𝐡_{𝑣}^{𝑘 - 1}$ : target (receiver)
$𝑒_{𝑢 𝑣}$ : Optional edge features

Step 2: Aggregation

Aggregation combines incoming messages. This is often already done by the summation, mean, or max:

𝐦_{𝑣}^{𝑘} = AGGREGATE ({𝐡_{𝑢}^{𝑘 - 1} : 𝑢 \in 𝒩︀ (𝑣)})

Step 3: Update

Each node updates its state with an update function $𝑈$ :

𝐡_{𝑣}^{𝑘} = 𝑈 (𝐡_{𝑣}^{𝑘 - 1}, 𝐦_{𝑣}^{𝑘})

Common choce:

𝐡_{𝑣}^{𝑘} = 𝜎 (𝑊 \cdot [𝐡_{𝑣}^{𝑘 - 1} ‖ 𝐦_{𝑣}^{𝑘}])

Where:

$‖$ : vector concatenation
$𝜎$ : non-linearity (ReLU, tanh)
$𝑊$ : learnable weights

Example

458.0.2. Invariance

A function is invariant to node permutations if its output stays the same no matter how the nodes are reordered (i.e., relabeled)

𝑓 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇}) = 𝑓 (𝑋, 𝐴)

If you shuffle the node labels, the graph is still the same — just redrawn

If you reorder the rows of $𝑋$ (node features) and both rows and columns of $𝐴$ (adjacency matrix) using the same permutation matrix $𝑃$ , the output does not change

458.0.3. Equivariance

A function is equivariant to node permutations if permuting the input nodes results in the output being permuted in the same way

𝑓 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇}) = 𝑃 𝑓 (𝑋, 𝐴)

If you shuffle the nodes in the input graph, the output values (e.g., node embeddings or predictions) shuffle in the same way

If you reorder the rows of $𝑋$ (node features) and both rows and columns of $𝐴$ (adjacency matrix) using the same permutation matrix $𝑃$ , the output is reordered in the same way — i.e., its rows are permuted by $𝑃$ too

Example

Let $𝐺 = (𝑉, 𝐸)$ be a directed graph where

\begin{aligned} 𝑉 & = {0, 1} \\ 𝐸 & = {(0, 1)} \end{aligned}

Adjacency matrix:

𝐴 = [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}]

Node feature matrix:

𝑋 = [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}]

Permutation matrix (swaps node 0 and node 1):

𝑃 = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]

Equivariance

Let’s define a very simple equivariant function:

𝑓 (𝑋, 𝐴) = 𝐴 𝑋

Message passing: sum over neighbors’ features

Step 1: Compute output without permutation

𝑓 (𝑋, 𝐴) = 𝐴 𝑋 = [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}] [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] = [\begin{matrix} 3 & 4 \\ 0 & 0 \end{matrix}]

Step 2: Compute permuted inputs

Permute $𝑋$

𝑃 𝑋 = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] = [\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix}]

Permute $𝐴$

𝑃 𝐴 𝑃^{𝑇} = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}] [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] = [\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}]

This is now node 1 pointing to node 0

Step 3: Apply function to permuted inputs

𝑓 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇}) = (𝑃 𝐴 𝑃^{𝑇}) (𝑃 𝑋) = [\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}] [\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix}] = [\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}]

Step 4: Compare with $𝑃 𝑓 (𝑋, 𝐴)$

𝑓 (𝑋, 𝐴) = [\begin{matrix} 3 & 4 \\ 0 & 0 \end{matrix}] ⟹ 𝑃 𝑓 (𝑋, 𝐴) = [\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}]

So this function is equivariant:

𝑓 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇}) = 𝑃 𝑓 (𝑋, 𝐴)

Invariance

Let’s define a simple invariant function:

𝑔 (𝑋, 𝐴) = 𝟏^{𝑇} 𝐴 𝑋

Step 1: Compute $𝑔 (𝑋, 𝐴)$

𝐴 𝑋 = [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}] [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] = [\begin{matrix} 3 & 4 \\ 0 & 0 \end{matrix}]

Sum over rows:

𝟏^{𝑇} 𝐴 𝑋 = [\begin{matrix} 3 + 0 & 4 + 0 \end{matrix}] = [\begin{matrix} 3 & 4 \end{matrix}]

Step 2: Compute permuted inputs

Permute $𝑋$

𝑃 𝑋 = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] = [\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix}]

Permute $𝐴$

𝑃 𝐴 𝑃^{𝑇} = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} 0 & 1 \\ 0 & 0 \end{matrix}] [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] = [\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}]

Step 3: Compute new output

𝑃 𝐴 𝑃^{𝑇} \cdot 𝑃 𝑋 = [\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}] [\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix}] = [\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}]

Step 4: Apply function to permuted inputs

𝟏^{𝑇} (𝑃 𝐴 𝑃^{𝑇}) (𝑃 𝑋) = [\begin{matrix} 1 & 1 \end{matrix}] [\begin{matrix} 0 & 0 \\ 3 & 4 \end{matrix}] = [\begin{matrix} 3 & 4 \end{matrix}]

Result:

𝑔 (𝑋, 𝐴) = [\begin{matrix} 3 & 4 \end{matrix}] = 𝑔 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇})

So the function is invariant under node permutation:

𝑓 (𝑃 𝑋, 𝑃 𝐴 𝑃^{𝑇}) = 𝑓 (𝑋, 𝐴)