Uncertainty quantification ≈ predicting magnitude/probability of error
Key ingredient for decision-making. For example:
Decisions are optimal with respect to the model:
the better its uncertainty, the better the decisions.
Default approach in deep learning
Lakshminarayanan et al. (NeurIPS 2017)
Epistemic: lack of data
Shows up as disagreement
Aleatoric: noise in the data
Shows up as predicted noise level
$$ \underbrace{\f{Var}\sbr{y \given x}}_{\text{total}} \;=\; \underbrace{\frac{1}{M}\sum_{m=1}^{M} \sigma_m^2(x)}_{\text{aleatoric}} \;+\; \underbrace{\frac{1}{M}\sum_{m=1}^{M} \del{\mu_m(x) - \bar{\mu}(x)}^2}_{\text{epistemic}} $$
Single model: aleatoric part only. Ensemble adds the epistemic part.
$$ f : V \to \text{distributions over } \R $$
$$ f\Big(\smash{\includegraphics[height=2.75em,width=1.5em]{figures/g3.svg}}\Big) = \f{N}(5, 0.7^2) $$
Also: graph-level and edge-level tasks (e.g. knowledge graph completion)
Deep ensembles: default in deep learning, strong in computer vision
On graphs, they are often assumed to work just as well.
Reported results are mixed: from hard to beat to worse than trivial baselines.
We study standard deep ensembles of message passing graph neural networks
(GCN, GAT, GIN, etc.)
Different tasks, scales, and structural properties
Node classification
Node regression
Graph-level tasks
Main metric: held-out negative log-likelihood (NLL)
Average of $-\log p(y \given x)$ over test points. Confident mistakes are penalized heavily.
How much more likelihood does the ensemble assign to test data?
Computer vision
Typical improvement: ~20%
Graphs
Improvement: below 1%
Graphs
Improvement: about 5%, at most 14%
Ensembles lead to some improvements on graphs,
but much less than in computer vision.
Why?
Uncertainty of GNN ensembles: aleatoric vs. epistemic parts
Epistemic part is close to zero: members barely disagree
(epistemic / aleatoric in regression: about 5 in computer vision, 0.02 to 0.1 here)
Ensembles add almost nothing beyond what a single model already captures
Each node is updated from its own features and those of its neighbors.
Path graph with 100 nodes. Training nodes (dots) are fitted by all members.
MLP
ignores the graph
GCN, 1 layer
smooths a bit
GCN, 4 layers
smooths more
Top: members' predictions, their average (black), target (dashed). Bottom: deviations from the average.
Deviations are ~ zero at training nodes and change little between neighbors
⇒ they stay small everywhere
The paper proves a bound on disagreement
in terms of how smooth the predictions are and how well nodes connect to training nodes
This smoothing is the homophily bias that makes message passing work
In excess: oversmoothing. A moderate amount of it already limits disagreement.
Heterophily: neighbors differ, so more room to disagree
Consistent with Chameleon showing the largest gains
Classification: softmax probabilities
Regression: variance head (predict mean and variance)
About the same quality as the ensemble, $M$ times cheaper to train and to run
But: no epistemic uncertainty
Better epistemic uncertainty with GNNs should be possible. How exactly is an open question.
Gaussian processes with graph-based kernels (e.g. graph Matérn)
Strengths
Principled epistemic uncertainty:
grows away from data
Very good when the signal
is smooth on the graph
Limitations
Computationally hard
to scale to large graphs
Not so smart at
processing node features
Fun fact: our research question came from a graph GP benchmark
Borovitskiy et al. (AISTATS 2021)
PeMS: traffic speed on San Jose highways. Color: predicted standard deviation. Black dots: training nodes.
GNN deep ensemble
Low almost everywhere,
peaks at some training nodes
Graph Gaussian process
Grows away
from training nodes
| Method | NLL |
|---|---|
| Trivial | 1.37 |
| GNN | 2.51 |
| GNN ensemble | 2.39 |
| Bayesian GNN | 1.32 |
| Graph GP | 0.98 |
GNN ensemble is worse than a trivial baseline (same Gaussian at every node)
No node features: GNNs get training labels as inputs. GNN = GCN.
Key takeaways
Future directions