Aggregation Functions in GNNs
Giovanni Pellegrini1,2,3
SML1 Lab, University of Trento, Italy
TIM2
EIT DIGITAL3
1
01 Recap
COMPUTATION GRAPH
The neighbour of a node defines its computation graph
INPUT GRAPH
2
01 Recap
COMPUTATION GRAPH
The neighbour of a node defines its computation graph
INPUT GRAPH COMPUTATION GRAPH
3
01 Recap
COMPUTATION GRAPH
The neighbour of a node defines its computation graph
INPUT GRAPH COMPUTATION GRAPH
4
01 Recap
COMPUTATION GRAPH
The neighbour of a node defines its computation graph
INPUT GRAPH COMPUTATION GRAPH
5
01 Recap
xA
xB
xE
Neural Networks
Permutation invariant
Aggregation
Sum
Average
Max
6
01 Recap
GCN mean
GraphSage max, mean, LSTM
GAT sum
7
Recap 01
WL Isomorphism test
02
TABLE OF 04 Sum Decomposition
03
Graph Isomorphism
Network (GIN) CONTENTS
05
Principal Neighborhood
Aggregation (PNA)
06 Learning Aggregation
Functions (LAF)
07 Aggregation in PyG
8
02 WL Isomorphism Test
?
≌
Solution: Weisfeiler-Lehman isomorphism test1
1
Weisfeiler and Lehman. A reduction of a graph to a canonical form and an algebra
arising during this reduction. Nauchno-Technicheskaya Informatsia, 1968.
9
02 WL Isomorphism Test
Step 0 10
02 WL Isomorphism Test
Step 1 11
02 WL Isomorphism Test
Step 1 12
02 WL Isomorphism Test
Step 1 13
02 WL Isomorphism Test
Step 2 14
02 WL Isomorphism Test
Step 2 15
02 WL Isomorphism Test
Step 2 16
02 WL Isomorphism Test
17
02 WL Isomorphism Test
Observed node Neighbours’ color
18
02 WL Isomorphism Test
Injective function Observed node Neighbours’ color
19
02 WL Isomorphism Test
Injective function Observed node Neighbours’ color
● Efficient heuristic
● Isomorphic graphs -> same labels
● Nodes are uniquely coloured
● Distinguish most graphs
But… limited use in practice
20
03 Graph Isomorphism Network (GIN)
Can we construct a GNNs as powerful as the WL isomorphism test?
21
03 Graph Isomorphism Network (GIN)
Can we construct a GNNs as powerful as the WL isomorphism test?
GIN - Graph Isomorphism Network2
2
Xu et al., How powerful are graph neural networks?, International Conference on
Learning Representations, 2019
22
03 Graph Isomorphism Network (GIN)
two non-isomorphic graphs
a GNN
23
03 Graph Isomorphism Network (GIN)
two non-isomorphic graphs
a GNN
Construct s.t. and differ
WL test decides they are non-isomorphic
24
03 Graph Isomorphism Network (GIN)
two non-isomorphic graphs
a GNN
Construct s.t. and differ
WL test decides they are non-isomorphic
Injective
25
03 Graph Isomorphism Network (GIN)
two non-isomorphic graphs
a GNN
Construct s.t. and differ
WL test decides they are non-isomorphic
Injective
Sum-decomposition
26
04 Sum-decomposition3
Any injective function on multisets can be decomposed as
3
Zaheer et al., Deep sets, Advances in Neural Information
Processing Systems 30, 2017
27
04 Sum-decomposition3
Any injective function on multisets can be decomposed as
3
Zaheer et al., Deep sets, Advances in Neural Information
Processing Systems 30, 2017
28
04 Back to GIN
Use an MLP for representing
29
04 Back to GIN
Use an MLP for representing
Cons of sum-decomposition:
● Highly discontinuous functions
● For uncountable domains, latent dimension of should be
higher than the number of elements in the set4
● No guarantee to find the right function
4
Wagstaff et al., On the limitations of representing functions on sets, Proceedings
of the 36th International Conference on Machine Learning, 2019
30
05 Principal Neighborhood Aggregation5
Select the best combination of aggregators and scalers
31
05 Principal Neighborhood Aggregation5
Select the best combination of aggregators and scalers
Image taken from the arXiv version of the paper.
5
Corso et al., Principal Neighbourhood Aggregation for Graph Nets, Advances in
Neural Information Processing Systems 33 (NeurIPS 2020), 2020
32
05 Principal Neighborhood Aggregation5
Select the best combination of aggregators and scalers
Image taken from the arXiv version of the paper.
Library of aggregators
5
Corso et al., Principal Neighbourhood Aggregation for Graph Nets, Advances in
Neural Information Processing Systems 33 (NeurIPS 2020), 2020
33
05 Principal Neighborhood Aggregation5
Select the best combination of aggregators and scalers
Image taken from the arXiv version of the paper.
Library of aggregators Logarithmic scalers
5
Corso et al., Principal Neighbourhood Aggregation for Graph Nets, Advances in
Neural Information Processing Systems 33 (NeurIPS 2020), 2020
34
05 Principal Neighborhood Aggregation5
06 Learning Aggregation Functions6
Don’t choose the aggregation function(s) - learn it!
5
Pellegrini et al., Learning Aggregation Functions, under revision, 2020
36
06 Learning Aggregation Functions6
Don’t choose the aggregation function(s) - learn it!
5
Pellegrini et al., Learning Aggregation Functions, under revision, 2020
37
06 Learning Aggregation Functions6
Don’t choose the aggregation function(s) - learn it!
5
Pellegrini et al., Learning Aggregation Functions, under revision, 2020
38
06 Learning Aggregation Functions6
Don’t choose the aggregation function(s) - learn it!
Learnable parameters
MAX, MIN, SUM, MEAN, MOMENTS, MIN/MAX, COUNT ...
5
Pellegrini et al., Learning Aggregation Functions, under revision, 2020
39
06 Learning Aggregation Functions
40
07 Aggregation in Pytorch Geometric
PyTorch Geometric provides the MessagePassing base class.
METHODS
Aggregates messages from
neighbors (sum, mean, max)
Constructs messages from node j
to node i in analogy to ϕΘ
Propagate messages
Updates node embeddings in
analogy to γΘ
41
07 Aggregation in Pytorch Geometric
PyTorch Geometric provides the MessagePassing base class.
METHODS
Aggregates messages from
neighbors (sum, mean, max)
Constructs messages from node j
to node i in analogy to ϕΘ
Propagate messages
Updates node embeddings in
analogy to γΘ
42