UoE/Huawei Joint Lab Workshop

On Uncertainty Quantification
in Graph Machine Learning

Viacheslav (Slava) Borovitskiy

https://vab.im

Why do uncertainty quantification?

Why do uncertainty quantification?

Uncertainty quantification ≈ predicting magnitude/probability of error

Key ingredient for decision-making. For example:

  • Which nodes to label next? [Active learning]
  • Which molecule to synthesize next? [Bayesian optimization]
  • Answer or say “I don’t know”? [Knowledge Graph QA]

Decisions are optimal with respect to the model:
the better its uncertainty, the better the decisions.

Deep ensembles

Default approach in deep learning

  • Train one architecture $M$ times from different random initializations
  • Prediction: average of the $M$ models
  • Uncertainty: disagreement + each model's noise level (shaded)

Lakshminarayanan et al. (NeurIPS 2017)

Two kinds of uncertainty

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.

Graph machine learning

Example setting: Probabilistic node regression

$$ 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)

Do Deep Ensembles Capture Uncertainty in Graph Neural Networks?

Do Deep Ensembles Capture Uncertainty in Graph Neural Networks?

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.)

Benchmark

Different tasks, scales, and structural properties

Node classification

  • Citeseer
    (classic)
  • Tolokers2
    (modern, larger)

Node regression

  • Artnetviews
    (modern, larger)
  • Chameleon
    (heterophilic)

Graph-level tasks

  • MolHIV
    (classification)
  • QM9-5%
    (regression, little data)

Main metric: held-out negative log-likelihood (NLL)

Average of $-\log p(y \given x)$ over test points. Confident mistakes are penalized heavily.

Deep ensembles: Graphs vs. computer vision

How much more likelihood does the ensemble assign to test data?

Classification. Likelihood ratios $\exp(\mathrm{NLL}_{\mathrm{GNN}}-\mathrm{NLL}_{\mathrm{DE}})$, $N$ = ensemble size.
Regression. Likelihood ratios $\exp(\mathrm{NLL}_{\mathrm{GNN}}-\mathrm{NLL}_{\mathrm{DE}})$, $N$ = ensemble size.

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?

The root cause: Epistemic collapse

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

Why do ensemble members agree?

How graph neural networks work: Message passing

Each node is updated from its own features and those of its neighbors.

  • GCN: same MLP at every node
  • Then average over neighbors
  • Network is a stack of such layers
  • Result: repeated local averaging
  • Neighbors get similar predictions

Smoothing limits disagreement: Toy example

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

Smoothing limits disagreement: General picture

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

What to use instead?

In practice: Just use a single model

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.

When they fit the problem: Graph Gaussian processes

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)

Graph GPs vs. GNN ensembles: PeMS benchmark

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

MethodNLL
Trivial1.37
GNN2.51
GNN ensemble2.39
Bayesian GNN1.32
Graph GP0.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.

Summary and future work

Key takeaways

  • Deep ensembles of message passing GNNs add little over a single model: epistemic collapse.
  • Theory: smoothing, the inductive bias that makes message passing work, also limits disagreement.
  • In practice: use a single model. When they fit the problem, graph GPs work very well.

Future directions

  • How to get better epistemic uncertainty with GNNs?
  • Graph transformers and other architectures.
  • Link prediction and knowledge graphs?
Main author
Pedro C. Vieira
Paper Info
Do Deep Ensembles Actually Capture Uncertainty in Graph Neural Networks?
P. C. Vieira, P. Ribeiro, V. Borovitskiy
(arXiv:2605.22593)

Thank you!