454. Graph Neural Network
| Node Embedding: |
|
||||
| Edge Embedding: |
|
||||
| Adjacency Matrix: |
|
- Node-level predictions
- Edge-level predictions
- Graph-level predictions
Graph Data
- Size variant
- Isomorphism: permutation invariance
- Grid structure: non-euclidian
454.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 ()
- : set of edges
- : feature (embedding) of node at iteration
- : set of neighbors of node
Step 1: Message computation
Each node receives messages from its neighbors . A message function defines how information is sent:
- : source (neighbor)
- : target (receiver)
- : Optional edge features
Step 2: Aggregation
Aggregation combines incoming messages. This is often already done by the summation, mean, or max:
Step 3: Update
Each node updates its state with an update function :
Common choce:
Where:
- : vector concatenation
- : non-linearity (ReLU, tanh)
- : learnable weights
Example
454.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
454.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
Adjacency matrix:
Node feature matrix:
Permutation matrix (swaps node 0 and node 1):
Equivariance
Let’s define a very simple equivariant function:
Message passing: sum over neighbors’ features
Step 1: Compute output without permutation
Step 2: Compute permuted inputs
- Permute
- Permute
This is now node 1 pointing to node 0
Step 3: Apply function to permuted inputs
Step 4: Compare with
So this function is equivariant:
Invariance
Let’s define a simple invariant function:
Step 1: Compute
Sum over rows:
Step 2: Compute permuted inputs
- Permute
- Permute
Step 3: Compute new output
Step 4: Apply function to permuted inputs
Result:
So the function is invariant under node permutation: