On the Prediction Instability of Graph Neural Networks

# On the Prediction Instability of Graph Neural Networks

## Max Klabunde and Florian Lemmerich

### Jacob Danovitch

### October 26, 2022

#### McGill University

<br/>
<pre style="font-size: small">
@article{Klabunde2022OnTP,
  title={On the Prediction Instability of Graph Neural Networks},
  author={Max Klabunde and Florian Lemmerich},
  journal={ArXiv},
  year={2022},
  volume={abs/2205.10070}
}
</pre>

---

# Introduction

---

# Motivation

In general, we expect a given node embedding model to produce relatively similar outputs each time we train it. However, there are many factors which can determine if this is actually the case:

* Model hyperparameters
* Random initialization
  * Seeding & method
* GPU floating point (im)precision
* Different versions of software libraries
  * E.g., PyG has a nondeterministic scatter operation on CUDA

These are all sources of _instability_.

---

# Motivation

This is problematic in two particular areas:

1. Reproducability; it may not be possible to reliably reproduce the results of published works

2. Real-world applicability 
   * Applications where models are re-trained regularly may lead to inconsistent & confusing outputs (e.g. recommendations) to the user
   * Unstable models part of larger ML pipelines may affect downstream services 
   * Models in high-stakes domains (healthcare, law, insurance) will not be reliable enough for practical use

---

# Goals

The authors make three contributions:

1. Show that popular GNNs (GCN, GAT) demonstrate high levels of prediction instability when trained multiple times on the same data
  * While aggregate performance is consistent, example-level predictions vary wildly

2. Examine what example (node), graph, and model properties contribute to (in)stability

3. Identifying the tendency of multi-layer GNNs to be more unstable at the deepest layers in particular

---

# Problem Setup

---

# Task Definition

The authors investigate the _(in)stability_ of GNNs' predictions on multi-label classification tasks. Given a graph `$G=(V, E)$` where  `$F \in \mathbb{R}^{|V|\times D}$, $Y \in \{0,1\}^{|V|\times C}$` are the features and labels for each node and `$C$` is the number of class labels, we wish to train a GNN on a subset of `$Y$` such that the model can predict the remainder of the labels.

The models are trained _transductively_, meaning that all nodes, node features, and edges are known during training and testing.

---

# Methodology

* The authors train two-layer, 64-dimensional GCN and GAT models 
  * GCN uses degree-based normalization and ReLU activation
  * GAT uses sum pooling with dropout (`$p=0.6$`) + ELU activation on final layer
* Each model is trained for up to 500 epochs with early stopping of 40
  * Adam (`$lr=0.01$`) used for optimzation
* Identical seeds, initialization, GPU hardware, etc.
* Models are evaluated on:
  *  CiteSeer
  *  Pubmed
  *  Coauthor (CS & Physics)
  *  Amazon (Photo & Computers)
  *  WikiCS

---

# Prediction Instability

We define _prediction instability_ as the expected disagreement between the predictions of two instances `$f_1, f_2$` of a given model:

$$
d^{(x)} = \mathbb{E}_{x, f_1, f_2} 𝟙(\mathrm{argmax}f_1(x) \neq \mathrm{argmax}f_2(x))
$$

This value is bounded by the performance of the model:
* When two models perform at 95%, minimal disagreement is zero (identical predictions)
* When two models perform at 90%, maximal disagreement occurs with 90% identical predictions and `$f_1$` succeeds on 5% of `$f_2$`'s failures

The authors also provide `$d_\mathrm{norm} = \mathbb{E}_{f_1, f_2}[\frac{d_{f_1, f_2} - \min d_{f_1, f_2}}{\max d_{f_1, f_2} - \min d_{f_1, f_2}}]$` as the normalized disagreement relative to the minimum and maximum possible values, as well as `$d_\mathrm{true}, d_\mathrm{false}$` as the disagreements conditioned on the success of the prediction.

---

# Prediction Instability

???

* Disagreement is 3-4% on all datasets except for CiteSeer and Computers (>10%)
* Disagreement is seemingly inversely correlated with accuracy
  * That is, lower disagreement => higher accuracy
* d_norm is low => disagreement is close to minimum that performance allows
* False disagreement almost always one magnitude larger than true disagreement
  * Partially explained by strong performance
* MAE suggests predicted class probabilities are similar between models

---

# Node Properties

???

* Fig. 2: Prediction disagreement for PageRank septiles on selected datasets
  * Nodes with higher centrality demonstrate higher stability
  * Low clustering coefficient leads to higher instability, but high value does not suggest higher stability
  * A higher k-core number reduces instability
* Fig. 3: Relation between subgroup accuracy and prediction disagreement for GAT with respect to the node classes (left) and PageRank septiles (right). The higher the accuracy, the lower the disagreement. The correlation between accuracy and disagreement suggests that central nodes are stably predicted due to high model performance on that subgroup of the data. Results for the other properties and GCN are similar.

---

# Influence of Methodology

.left[
* The authors vary each hyperparameter - one at a time - to examine their effects on stability
* Also vary the ratio of withheld labels between 1 and 60%
* Disagreement and error clearly decrease with more training data
]

]

---

# Other Notable Findings

* No clear effect of optimizer on stability 
* L2 regularization can somewhat help decrease disagreement
* Dropout often leads to higher disagreement
* Wider (higher dim) models have lower disagreement, while deeper (more layers) have higher
* Layer-wise evaluation
  * Compared outputs of each layer instead of final model output
  * Found that first layers are very stable, while final layers are where instability is introduced

---

# Conclusions

* Overall, certain GNNs exhibit fairly clear instability in their node-level predictions, even when their aggregated performance is the same
* This is more likely to happen in certain nodes than others, as a function of their structural properties (primarily centrality)
* A variety of other factors can promote stability such as more training data, L2 regularization, and higher model dimensionality
* Certain factors can also decrease stability including dropout and additional model layers

---

# Thank you