Evaluating Robustness and Uncertainty of Graph Models Under Structural Distributional Shifts
Authors: Gleb Bazhenov
Denis Kuznedelev
Andrey Malinin
Artem Babenko
Liudmila Prokhorenkova
Venue: NeurIPS 2023 poster (2023)
Keywords: graph
distributional shift
structural shift
uncertainty
robustness
graph neural networks
TL;DR: We propose a general approach for inducing structural distributional shifts that can be applied to any graph dataset and allows for evaluating robustness and uncertainty of graph models in node-level problems.

Abstract: In reliable decision-making systems based on machine learning, models have to be robust to distributional shifts or provide the uncertainty of their predictions. In node-level problems of graph learning, distributional shifts can be especially complex since the samples are interdependent. To evaluate the performance of graph models, it is important to test them on diverse and meaningful distributional shifts. However, most graph benchmarks considering distributional shifts for node-level problems focus mainly on node features, while structural properties are also essential for graph problems. In this work, we propose a general approach for inducing diverse distributional shifts based on graph structure. We use this approach to create data splits according to several structural node properties: popularity, locality, and density. In our experiments, we thoroughly evaluate the proposed distributional shifts and show that they can be quite challenging for existing graph models. We also reveal that simple models often outperform more sophisticated methods on the considered structural shifts. Finally, our experiments provide evidence that there is a trade-off between the quality of learned representations for the base classification task under structural distributional shift and the ability to separate the nodes from different distributions using these representations.

Evaluating Robustness and Uncertainty of Graph Models Under Structural Distributional Shifts
Gleb Bazhenov*
Denis Kuznedelev Yandex Research, Skoltech
HSE University, Yandex Research
Andrey Malinin Isomorphic Labs
Artem Babenko Yandex Research, HSE University
Liudmila Prokhorenkova
Yandex Research
Abstract
In reliable decision-makine systems based on machine learning, models have to be robust to distributional shifts or provide the uncertainty of their predictions. In node- level problems graph learning, distributional shifts can be especially complex since the samples interdependent. To evaluate the performance of graph models, it important to test them on diverse and meaningful distributional shifts. However, most graph benchmarks considering distributional shifts for node-level problems focus mainly on node features, while structural properties are also essential for graph problems. In this work, propose a general approach for inducing diverse distributional shifts based on graph structure. We use this approach to create data splits according several structural node properties: popularity, locality, and density. In our experiments, we thoroughly evaluate the proposed distributional shifts and show that they can be quite challenging for existing graph models. We also reveal that simple models often outperform more sophisticated methods on the considered structural shifts. Finally, our experiments provide evidence that there is trade-off between the quality of learned representations for the base classification task under structural distributional shift and the ability to separate the nodes from different distributions using these representations.
Introduction
Recently, much effort has been put into creating decision makionn systems based on machine learning for various high-risk applications, such financial operations, medical diagnosties, autonomous driving, etc. These systems should comprise several important properties that allow users to rely on their predictions. One such property robustness, the ability of an underlying model cope with distributional shiftss when the features of test inputs become different from those encountered in the training phase. the same time, if a model is unable maintain high performance on shifted input, it should signal the potential problems by providing some measure of uncertainty. These properties are especially difficult to satisfy in the node-level prediction tasks on graph data since the elements are interdependent, and thus the distributional shifts may be even more complex than for the classic setup with i.i.d. samples.
To evaluate graph models in the node-level problems, it is important to test them under diverse, complex, and meaningful distributional shifts. Unfortunately, most existing graph datasets split the nodes into train and test parts uniformly at random. Rare exceptions include the Open Graph Benchmark (OGB) [12 that creates more challenging non-random data splits by dividing the nodes
"Correspondence to gr-bazhenovdyandee- teazz.teem..e.
Work done while at Yandex Research
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

according to some Domain--specife property. For instance, in the OGB-Arxiv dataset, the papers are divided according to their publication date, which is a realistic setup. Unfortunately, not many datasets contain such mnta-information that can be used to split the data. To overcome this issue, Gui et al. [0] propose the Graph OO1) Benchmark (GOOD) designed specifically for evaluating graph models under distributional shifts. The authors distinguish between two types of shifts: concept and covariate. However, creating such shifts is non-trivial, while both types of shifts are typically present simultaneously in practical applications. Also, the splitting strategies in GOOD are mainly based on the node features and do not take into account the graph structure 3
In our work, we fill this gap and propose universal method for inducing structural distributional shifts in graph data. Our approach allows for creating diverse, complex, and meaningful node-level shifts that can be applied to any graph dataset. In particular, we introduce the split strategies that focus on such node properties as popularity, locality, and densiry. Our framework is flexible and allows one to easily extend it with other structural shifts or vary the fraction of nodes available for training and testing. We empirically show that the proposed distributional shifts are quite challenging for existing graph methods. In particular, the locality-based shift appears to be the most difficult in terms of the predictive performance for most considered OOD robustness methods, while the density-based shift is extremely hard for OOD detection by uncertainty estimation methods. Our experiments also reveal that simple models often outperform more sophisticated approaches on structural distributional shifts. In addition, investigate some modifications of graph model architectures that may improve their OOD robustness or help in OOD detection on the proposed structural shifts. Our experiments provide evidence that there trade-off between the quality of learned representations for base classification task under structural distributional shift and the ability to separate the nodes from different distributions using these representations.
Background
2.1 Graph problems with distributional shifts
Several research areas in graph machine learning investigate methods for solving node-level prediction tasks under distributional shifts, and they primarily different in what problem they seek to overcome. One such area is adversarial robustness, which requires one to construct a method that can handle artificial distributional shifts that are induced as adversarial attacks for graph models in the form of perturbed and contaminated inputs. The related approaches often focus on designing
various data augmentations via introducing random learnable noise (30 42 40
35
22
Another research area is out-of--isttibbttin generalization. The main task is to design a method that can handle real-world distributional shifts on graphs and maintain high predictive performance across different OOD environments. Several invariant learning and risk minimization techniques have been proposed to improve the robustness of graph models to such real-world shifts [1] 19 20 38).
There is also an area of uncertainty estimation, which covers various problems. In ervor detection, a model needs to provide the uncertainty estimates that are consistent with prediction errors, i.e., assign higher values to potential misclassifications In the presence of distributional shifts, the uncertainty estimates can also be used for out-of distriiibttion detection, where model is required to distinguish the shifted OOD data from the ID data (2 36 27
The structural distributional shifts proposed in our paper can be used for evaluating OOD generaliza- tion, OOD detection, and error detection since they designed replicate the properties of realistic graph data.
2.2 Uncertainty estimation methods
Depending on the source of uncertainty, it usually divided into data uncertainty, which describes the inherent noise in data due to the labeling mistakes or class overlap, and knowledge uncertainty, which accounts for the insufficient amount of information for accurate predictions when the distribution of the test data is different from the training one 5 24 23
In Appendix C we provide detailed discussion of the GOOD benchmark.

---

General-purper methods The most simple approaches are standard classification models that predict the parameters of softmax distribution. For these methods, we can define the measure of uncertainty as the entropy of the predictive categorical distribution. This approach, however, does not allow us distinguish between data and knowledge uncertainties, so it usually inferior to other methods discussed below.
Ensembling techniques are powerful but expensive approaches that providing decent predictive performance and uncertainty estimation. The most common example is Deep Ensemble [21] which can be formulated as an empirical distribution of model parameters obtained after training several instances of the model with different random seeds for initialization. Another way to construct an ensemble is Monte Carlo Dropout (6), which is usually considered as the baseline uncertainty estimation literature. However, it has been shown that this technique is commonly inferior to deep ensembles, as the obtained predictions are dependent and thus lack diversity. Importantly, ensembles allow for natural decomposition of total uncertainty in data and knowledge uncertainty (3
There also family of Dirichlet-based methods. Their core idea is to model the point-wise Dirichlet distribution by predicting its parameters for each input individually using some model. To get the parameters of the categorical distribution, one can normalize the parameters of the Dirichlet distribution by their sum. This normalization constant is called evidence and can be used to express the general confidence of a Dirichlet- model. Similarly to ensembles, these methods are able to distinguish between data and knowledge uncertainty. There are numerous examples of Dirichlet- methods, one of the first being Prior Network (24] that induces the behavior of Dirichlet distribution by contrastive learning against the OOD samples. Although this method is theoretically sound, it requires knowing the OOD samples in the training stage, which is significant limitation. Another approach is Posterior Network 22. where the behavior of the Dirichlet distribution is controlled by Normalizing Flows [13 [3), which estimate the density in latent space and reduce the Dirichlet evidence in the regions of low density without using any OOD samples.
Graph-specific methods Recently, several uncertainty estimation methods have been designed specifically for node-level problems. For example, Graph Posterior Network [33 is extension of the Posterior Network framework discussed above. To model the Dirichlet distribution, it first
encodes the node features into latent representations with graph-agnostic model and then uses one flow per class for density estimation. Then, the Personalized Propagation scheme [17] is applied to the Dirichlet parameters to incorporate the network effects. Another Dirichlet-based method is Graph- Graph-Kernel Dirichlet Estimation [4]]. In contrast to Posterior Networks, its main property is a compound training objective, which focused on optimizing the node classification performance and inducing the behavior of the Dirichlet distribution. The former is achieved via knowledge distillation from a teacher GNN, while the latter is performed as a regularisation against the prior Dirichlet distribution computed via graph kernel estimation. However, as shown by Stadler et al. [33, this approach is inferior to Graph Posterior Network while having a more complex training procedure and larger computational complexity.
2.3 Methods for improving robustness
Improving OOD robustness can be approached from different perspectives, which, however, share the same idea of learning the representations that are invariant to undesirable changes of the input distribution. For instance, the main claim in domain adaptation is that to achieve an effective domain transfer and improve the robustness to distributional shift, the predictions should depend on the features that can not discriminate between the source and target domains. Regarding the branch of invariant learning, these methods decompose the input space into different environments and focus on constructing robust representations that are insensitive their change.
General- purrose methods A classic approach for domain adaptation is Domain-Adversart Neural Network 77] that promotes the emergence of features that are diseriminative for the main learning task on the source domain but do not allow to detect the distributional shift on other domains. This achieved by jointly optimizing the underlying representations as well as two predictors operating on them: the main label predictor that solves the base classification task and the domain classifier that discriminates between the source and the target domains during training. Another simple technique in the class of unsupervised domain adaptation methods is Deep Correlation Alignment
3

---

34 which trains to align the second-order statistics of the source and target distributions that are produced by the activation layers of a deep neural model that solves the base classification task.
representative approach in invariant learning is Invariant Risk Minimization [. which searches for data representations providing decent performance across all environments, while the optimal classifier on top of these representations matches for all environments. Another method is Risk Extrapolation [20], which targets both robustness to covariate shifts and invariant predictions. In particular, it targets the forms of distributional shifts having the largest impact on performance in training domains.
Graph-specific methods More recently, several graph-specific methods for improving OOD robust- ness have been proposed. One of them is invariant learning technique Applore-to-Extrapolee Risk Minimization [38]. which leverages multiple context explorers that are specified by graph structure editors and adversarially trained to maximize the variance of risks across different created environ- ments. There is also a simple data augmentation technique Mixup [39] that trains neural models on convex combinations of pairs of samples and their corresponding labels. However, devising such method for solving the node-level problems is not straightforward, as the inputs are connected to each other. Based on this technique, Wang et al. 37 have designed its adaptation for graph data: instead of training on combinations of the initial node features, this method exploits the intermediate representations of nodes and their neighbors that are produced by graph convolutions.
Structural distributional shifts
3.1 General approach
As discussed above, existing datasets for evaluating the robustness and uncertainty of node-level problems mainly focus on feature-based distributional shifts. Here, we propose a universal approach that produces non-trivial yet reasonable structural distributional shifts. For this purpose, we introduce a node-level graph characteristic o; and compute it for every node i E V. We sort all nodes in ascending order of a; those with the smallest values of a; are considered be ID, while the remaining ones are OOD. As result, we obtain a graph- based distributional shift where ID and OOD nodes have different structural properties. The type of shift depends on the choice of og and several possible options are described in Section 3.2 below.
We further split the ID nodes uniformly random into the following parts:
Train contains nodes Virain that are used for regular training of models and represent the only observations that take part in gradient computation.
Valid-IN In enables us to monitor the best model during the training stage by computing the validation loss for nodes Vvalid-in and choose the best checkpoint.
Test-In used for testing on the remaining ID nodes Viestin and represents the simplest setup that requires model reproduce in-distribution dependencies.
The remaining OOD nodes are split into Valid-Out and Test-Out subsets based on their oy;
Test-Out is used to evaluate the robustness of models to distributional shifts. It consists of nodes with the largest values of o; and thus represents the most shifted part Viest-out-
Valid-Out contains OOD nodes with smaller values of a; and thus is less shifted than Test-Out. This subset Vvalid-out can be used for monitoring the model performance on a shifted distribution. Our experiments assume more challenging setup when such shifted data is unavailable during training. However, the presence of this subset allows us to further separate V Viest-out from V the larger Vvalid-out consider, the more significant distributional shift is created between the train and OOD test nodes.
Our general framework is quite flexible and allows one to easily vary the size of the training part and the type of distributional shift. Let us now discuss some particular shifts that propose in this paper.

---

(a) Popularity
(b) Locality
(c) Density
Figure 1: Visualization of structural shifts for AmazonPhoto dataset: ID is blue, OOD is red.
3.2 Proposed distributional shifts
To define our data splits, we need to choose node property o; splitting factor. We consider diverse graph characteristics covering various distributional shifts that may occur in practice. In standard non-graph ML setup, shifts typically happen only in the feature space (or, more generally, the joint distribution of features and targets may shift). However, in graph learning tasks, there can be shifts specifically related the graph structure. We discuss some representative examples below.
Popularity-baser The first strategy represents possible bias towards popularity. In some appli- cations, is natural to expect the training set to consist of more popular items. For instance, in the web search, the importance of pages in the internet graph can be measured via PageRank [29]. For this application, the labeling of pages should start with important ones since they are visited more often. Similar situations may happen for social networks, where it is natural start labeling with the most influential users, or citation networks, where the most cited papers should be labeled first. However, when applying graph model, is essential make accurate predictions less popular items. Motivated by that, we introduce popularity- -based split based on PageRank. The vector of PageRank values πं describes the stationary distribution of random walk with restarts, for which the transition matrix is defined as the normalized adjacency matrix AD- and the probability of restart a:
π (1 a ADD + aap.
(1)
The vector of restart probabilities p is called personalization vector, and p; 1/n by default, which describes the uniform distribution
nodes.
To construct popularity-based split, we use PageRank (PR) as a measure node importance. Thus, we compute PR for every node i and set a; -T, which means that the nodes with smaller PR values (i.e., less important ones) belong to the OOD subsets. Note that instead PR, one can potentially use any other measure of node importance, e.g., node degree, or betweenness centrality.
Figure Ta illustrates that the proposed shift separates the most important nodes that belong to the cores of large clusters and the structural periphery, which consists of less important nodes in terms of their PR values. We also observe that such popularity-
split agrees well with some natural distributional shifts. For instance, Figure 11a in Appendix shows the distribution of PageRank in train and test parts of the OGB-Arxiv dataset [1]] Here, the papers are split according to their publication date. Thus, older papers naturally have more citations and, therefore, larger PageRank. Our proposed split allows one to mimic this behavior for datasets without timestamps available. We refer to Appendix A for more details and additional analysis.
Locality-based Our next strategy is focused on a potential bias towards locality, which may happen when labeling is performed by exploring the graph starting from some node. For instance, in web search applications, crawler has to explore the web graph following the links. Similarly, the information about the users of a social network can usually be obtained via an API, and new users are discovered following the friends of known users. To model such situation, one could divide nodes based on the shortest path distance to given node. However, graph distances are discrete, and the number of nodes at certain distance may grow exponentially with distance. Thus, such approach
5

---

does not provide us with the desired flexibility in varying the size of the train part. Instead, we use the concept of Personalized PageRank (PPR) (29 to define local neighborhood of a node. PPR is the stationary distribution of a random walk that always restarts from some fixed node j. Thus, the
personalization vector p ① is set to the one-hot-encoding of j. The associated distributional shift naturally captures locality since a random walk always restarts from the same node.
For our experiments, we select the node j with the highest PR score as a restarting one. Then, we compute the PPR values Tú for every node i and define the measure o; = -Tç, The nodes with high PPR, which belong the ID part, are expected to close to the restarting node, while far away nodes go to the OOD subset. Figure [egureIIbcore confirms that the locality is indeed preserved, as the ID part consists of one compact region around the restarting node. Thus, the OOD subset includes periphery nodes as well as some nodes that were previously marked as important in the PR-based split but are far away from the restarting node. Our analysis in Appendix A also provides evidence for this behavior: the PPR-based split strongly affects the distribution of pairwise distances within the ID/OOD parts as the locality bias of the ID) part makes the OOD nodes more distant from each other.
While Aocality-based distributional shifts are natural, we are unaware of publicly available benchmarks focusing on such shifts. We believe that our approach will be helpful for evaluating the robustness of GNNs under such shifts. Our empirical results in Section A demonstrate that locality-based splits are the most challenging for graph models and thus may require special attention.
The next distributional shift we propose is based on density. One of the most simple node characteristics that describe the local density in graph is the local clustering coefficient. Con- sidering some node i, let d; be its degree and "/ be the number of edges connecting the neighbors of i, Then, the local clustering coefficient is defined as the edge density within the one-hop neighborhood:
Density-based
27
C: d(d-11
For experiments, we consider nodes with the highest clustering coefficient to be ID, which implies that 0g = -cy.
This structural property might be particularly interesting for inducing distributional shifts since it is defined through the number of triangles, the substructures that most standard
graph neural networks are unable to distinguish and count [4) Thus, it is interesting to know how changes in the clustering coefficient affect the predictive performance and uncertainty estimation.
Figure IC visualizes the density-based split. We see that the OOD part includes both the high-degree central nodes and the periphery nodes of degree one. Indeed, the nodes of degree one naturally have zero clustering coefficient. On the other hand, for the high-degree nodes, the number of edges between their neighbors usually grows slower than quadratically. Thus, such nodes tend to have a vanishing clustering coefficient.
Finally, we note that the existing datasets with realistic splits may often have the local clustering coefficient shifted between the train and test parts. Figures and [3c Appendix show this for two OGB datasets. Depending on the dataset, the train subset may be biased towards the nodes with either larger (Figure [3c) or smaller (Figure 12c) clustering. In our experiments, we focus on the former scenario.
4 Experimental setup
While our approach can potentially be applied to any node prediction dataset, for our experiments, pick the following seven homophilous datasets that commonly used in the literature: three citation networks, including CoraML, CiteSeer [26] 9 g BT, and PubMed (28). two co-authorship graphs- CoauthorPhysics and CoauthorCS (32. and two co-purchase datasets
Datasets
Amazon and AmazonComputer 25 32 Moreover, we consider DGB-Products, a large- scale dataset from the OGB benchnark. Some of the methods considered in our work are not able to process such a large dataset, so we provide only the analysis of structural shifts on this dataset and do not use it for comparing different methods.
For any distributional shift, we split each graph dataset as follows. The half of nodes with the smallest values of o; are considered to be ID and split into Train, Valid- In, and Test- In uniformly at

---

random in proportion 30%: 10%: 10%. The second half contains the remaining OOD nodes and is split into Valid-Ouu Out and Test-Our the ascending order o; proportion 10% 40%. Thus, in our base setup, the IID to OOD split ratio is 50%: 50%. We have also conducted experiments with other split ratios that involve smaller sizes of OOD subsets, see Appendix B for the details.
Models In our experiments, we apply the proposed benchmark to evaluate the OOD robustness and uncertainty of various graph models. In particular, we consider the following methods for improving the OOD generalisation in the node classification task:
ERM the Empirical Risk Minimization technique that trains simple GNN model by optimizing a standard classification loss;
DANN is an instance of Domain Adversurial Network 7 that trains regular and a domain
classifiers to make features indistinguishable across different domains;
CORAL is the Deep Correlation Alignment 34 technique that encourages the representations
of nodes in different domains be similar;
EERM is the Explore-to Ssplore-to-Extrapolie Extrapolate Risk Minimization 38 method based on graph structure
editors that creates virtual environments during training;
Mixup is an implementation of Mixup from [37 and represents simple data augmentation technique adapted for the graph learning problems;
DE represents a Deep Ensemble [2 of graph models, a strong but expensive method for improving the predictive performance;
context OOD detection, we consider the following uncertainty estimation methods:
SE represents a simple GNN model that is used in the ERM method. for which the measure of uncertainty Softmax Entropy (i.e., the entropy of predictive distribution);
GPN an implementation of the Graph Posterior Network uncertainty estimation;
33
method for the node-level
NatPN is instance of Natural Posterior Network 3 in which the encoder has the same
architecture as in the SE method;
DE represents a Deep Ensemble (21 of graph models, which allows to separate the knowledge uncertainty that used for OOD detection;
GPE and NatPE represent the Bayesian Combinations of GPN and NatPN, an approach to construct ensemble of Dirichlet models 3
The training details are described in Appendix For experiments with the considered OOD robustness methods, including DANN, CORAL, EERM, and Mixup, we use the experimental framework from the GOOD benchmark|" framework and can be found in our repository
(5) whereas the remaining methods are implemented in our custom experimental
Prediction tasks & evaluation metries To evaluate OOD robustness in the node classification problem, we exploit standard Accuracy. Further, to assess the quality of uncertainty estimates, we treat the OOD detection problem as binary classification with positive events corresponding the observations from the OOD subset and use AUROC to measure performance.
5 Empirical study
In this section, we show how the proposed approach to creating distributional shifts can be used for evaluating the robustness and uncertainty of graph models. In particular, we compare the types of distributional shifts introduced above and discuss which of them are more challenging, We also discuss how they affect the predictive performance of OOD robustness methods as well the ability for OOD detection of uncertainty estimation methods.
Link to GOOD benchmark repository
Link to GitHub repository

---

Table I: Comparison of structural distributional shifts terms OOD robustness and OOD detection. We report the drop in predictive performance of the ERM method measured by Accuracy (left) and the quality of uncertainty estimates of the SE method measured by AUROC (right).
Popularity
Locality
Density
Popularity
Locality
Density
AmazonComputer
110.01 %
221.95 %
-7.91 %
AmazonComputer
88.52
86.48
44.24
AmazonPhoto
-8.44% %
-30.93% %
33,58 %
AmazonPhoto
92.05
93.29
41.08
CoauthorCSS
-3.13%
-.222%
4.86 %
CoauthorCS
83 25
85.74
50.91
CouuthorPhysics
3.42% %
4.75%
1.41 %
ComuthorPysscss
86.60
87.73
37.50
CoraMI.
-3.94%
14.61 %
- -17.09 %
CoraMI.
75.67
87.13
81.55
CiteSecr
-0.02 %
26.51 %
-.39 %
CiteScer
68.01
89.89
66.90
PubMed
3.23%
5.71
0.78 %
PubMed
68 60
66.34
58.60
OGB-Prodduct
-2.86% %
-2.83 %
-0.12%
OGB- PiB-Prroducts
88.50
88.56
36.00
Average
-4.39% %
- -13.56 %
-5.52 %
Average
81.40
85.65
52.10
5.1
Analysis of structural distributional shifts
In this section, we analyze and compare the proposed structural distributional shifts.
OOD robustness To investigate how the proposed shifts affect the predictive performance of graph models, we take the most simple ERM method and report the drop in Accuracy between the ID and OOD test subsets in Table (left). It can be seen that the node classification results the considered datasets are consistently lower when measured on the OOD part, and this drop can reach tens of percent in some cases. The most significant decrease in performance is observed on the locality-based splits, where it reaches 14% on average and more than 30% in the worst case. This fact matches our intuition about how training on local regions of graphs may prevent OOD generalization and create a great challenge for improving OOD robustness. Although the density-based shift does not appear to be as difficult, it is still more challenging than the popularity- based shift, leading to performance drops of 5.5% on average and 17% in the worst case.
OOD detection To analyze the ability of graph models to detect distributional shifts by providing higher uncertainty on the shifted inputs, report the performance of the most simple SE method for each proposed distributional shift and graph dataset in Table (right). It can be seen that the popularity-based and locality-based shifts can be effectively detected by this method, which is proved by the average performance metrics. In particular, the AUROC values may vary from 68 to 92 points on the aapularity-based splits and approximately in the same range for the locality-based splits. Regarding the density-based shifts, one can see that the OOD detection performance is almost the same as for random predictions on average. Only for the citation networks the AUROC exceeds 58 points, reaching a peak of 81 points. This is consistent with the previous works showing that standard graph neural networks are unable to count substructures such as triangles. In our case, this leads to graph models failing to detect changes in density measured as the number of triangles around the central node.
Thus, the popularity- shift appears to be the simplest for OOD detection, while the density-based the most difficult. This elearly shows how our approach to creating data splits allows one to vary the complexity of distributional shifts using different structural properties as splitting factors.
5.2 Comparison of existing methods
In this section, we compare several existing methods for improving OOD robustness and detecting OOD inputs the proposed structural shifts. To concisely illustrate the overall performance of the models, we first rank them according to a given performance measure on a particular dataset and then average the results over the datasets. For detailed results of experiments on each graph dataset separately, please refer to Appendix
OOD robustness For each model, we measure both the absolute values of Accuracy and the drop in this metric between the ID and OOD subsets in Table (left). It can be seen that simple data augmentation technique Mixup often shows the best performance. Only on the density-based shift, expensive DE outperforms it average when tested on the OOD subset. This proves that data
8

---

Table 2: Comparison of several graph methods for improving the OOD robustness (left) and detecting the OOD inputs by means of uncertainty estimation (right). For each task, we report the method ranks averaged across different graph datasets (lower better).
Popularity
Locality
Density
Popularity
Locality
Density
ID
OOD
ID
OOD
ID
OOD
ERM
4.0
4.0
3.3
4.1
3.9
4.0
SE
1.4
2.1
4.0
Mixup
1.4
2.1
1.4
2.4
1.9
3.3
GPN
3.3
3.9
4.3
EERM
3.6
3.9
5.0
4.3
NaiPN
5.3
2.9
DANN
4.3
4.3
5.0
4.1
3.0
3.6
DE
2.1
2.7
CORAL
4.7
4.1
4.3
4.7
4.1
3.9
GPE
3.1
4.3
3.4
DE
3.0
2.6
2.6
2.3
3.1
2.0
NaPPR
5.7
5.4
3.7
Table 3: Comparison of the proposed architecture modifications that are used in the ERM method for OOD robustness (left) and SE method for OOD detection (right). For each task, we report the win/tie/loss counts across graph datasets for the modified GNN architecture against the base one.
Popularity
Locality
Density
Popularity
Locality
Density
OOD
TD
OOD
OOD
ERM + mod| 4/2/1 5/2/0
4/2/1
3/2/2
4/2/1
5/2/0 SE + mod 0/0/77 0/1/6
4/0/3
augmentation techniques are beneficial in practice, as they prevent overfitting to the structural patterns and improve the OOD robustness. Regarding other OOD robustness methods, graph- specific method EERM outperforms DANN and CORAL on the popularity-basee shifts. However, these domain adaptation methods are superior to EERM on the density-based shifts, providing better predictive performance on average for both ID and OOD subsets.
and locality- -aased
In conclusion, we reveal that the most sophisticated methods that generate virtual environments and predict the underlying domains for improving the OOD robustness may often be outperformed by simpler methods, such data augmentation.
OOD detection Comparing the quality of uncertainty estimates in Table (right), one can observe that the methods based the entropy of predictive distribution usually outperform Dirichlet methods. In particular, natural distinction knowledge uncertainty in DE enables it to produce uncertainty estimates that are the most consistent with OOD inputs average, especially when applied to the locality-basee and density-based shifts. In general, GPN and the combination of its instances GPE provide higher OOD detection performance than their counterparts based on NatPN when tested on the popularity- based and locality-baac based splits.
Trigh)(rrggt)),
5.3 Influence of graph architecture improvements
In this section, consider several adjustments for the base GNN architecture of such methods as ERM, which is used to evaluate OOD robustness, and SE, which provides the uncertainty estimates for OOD detection. In particular, replacing the first one with a pre-processing step based on MLP, apply the skip-connections between graph convolutional layers, and replace the GCN [16] graph convolution with SAGE (IT).
reduce the number of graph convolutional layers from 3 to 2,
These changes are aimed at relaxing the restrictions on the information exchange between a central node and its neighbors and providing more independence in processing the node representations across neural layers. Such a modification is expected to help the GNN model to learn structural patterns that could be transferred to the shifted OOD subset more successfully. Further, changes in the model architecture affect the predictive performance and the quality uncertainty estimates of the corresponding methods when tested on the proposed structural distributional shifts.
investigate how these
For this, we use the win/tie/loss counts that reflect how many times the modified architecture has outperformed, got a statistically insignificant difference, or lost to the corresponding method, respectively. As can seen from Table 3 (left), the ERM method supplied with the proposed modifications usually outperforms the baseline architecture both on ID and OOD, which is proved by high win counts. However, as can be seen from Table 3 (right), the same modification in the corresponding SE method leads to consistent performance drops, which is reflected in high loss

---

counts, It means that, when higher predictive performance is reached on the shifted subset, it becomes more difficult detect the imputs from this subset as OOD since they appear to be less distinguishable by a GNN model in the context of the base node classification problem. Our observation is very similar to what is required from Invariant Learning techniques, which try to produce node representations invariant to different domains or environments. This may serve evidence that there is trade-off between the quality of learned representations for solving the target node classification task under structural distributional shift and the ability to separate the nodes from different distributions based on these representations.
Conclusion
In this work, we propose and analyze structural distributional shifts for evaluating robustness and uncertainty in node-level graph problems. Our approach allows one to create realistic, challenging, and diverse distributional shifts for an arbitrary graph dataset. In our experiments, we evaluate the proposed structural shifts and show that they can be quite challenging for existing graph models. We also find that simple models often outperform more sophisticated methods on these challenging shifts. Moreover, by applying various modifications for graph model architectures, we show that there is a trade-off between the quality of learned representations for the target classification task under structural distributional shift and the ability to detect the shift using these representations.
Limitations While our methods of creating structural shifts are motivated by real distributional shifts that arise in practice. they are synthetically generated, whereas, for particular applications, natural distributional shifts would be preferable. However, our goal is address the situations when such natural shifts are unavailable. Thus, we have chosen an approach universally applied to any dataset. Importantly, graph structure is the only common modality of different graph datasets that can be exploited in the same manner to model diverse and complex distributional shifts.
Broader impact Considering the broader implications of our work, we assume that the proposed approach for evaluating robustness and uncertainty of graph models will support the development of more reliable systems based on machine learning. By testing on the presented structural shifts, should be easier to detect various biases against under-represented groups that may have a negative impact on the resulting performance and interfere with fair decision -acision-mmaing....
Future work In the future, two key areas can be explored based on our work. Firstly, there is need to develop principled solutions for improving robustness and uncertainty estimation on the proposed structural shifts. Our new approach can assist in achieving this objective by providing an instrument for testing and evaluating such solutions. Additionally, there is a need create new graph benchmarks that accurately reflect the properties of data observed in real-world applications. This should involve replacing synthetic shifts with realistic ones. By doing so, we may capture the challenges and complexities that might be faced in practice, thereby enabling the development of more effective and applicable graph models.
References
[1] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz. Invariant risk minimization. arXiv preprint 19Xiv:1907.02899 2019.
[2] B. Charpentier; D. Zügner, and S. Güinnemann. Posterior network: Uncertainty estimation with- ood samples via density-hased pseudo-counts. Advances in Neural Information Processing Systems, 33:1356-1367, 2020.
[3] B. Charpentier, O. Borchert, D. Zügner, S. Geisler, and S. Günnemann. Natural posterior net- work: Deep bayesian predictive uncertainty for exponential family distributions. In International Conference on Learning Representations, 2022.
[4] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, 33:10383-10395 2020.
[5] Y. Gal. Uncertainty in deep learning. University of Cambridge, Cambridge, 2016.
10

---

[6] Y. Gal and Z. Ghahramani. Dropout bayesian approximation: Representing model uncer- tainty in deep learning. In International Conference on Machine Learning, pages 1050-1059. PMLR, 2016.
[7] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and Lempitsky. Domain-adversare adversarial training of neural networks. The journal of machine learning research, 17(1):2096-2033 2016.
[8] L. Getoor. Link-based classification. In Advanced methods for knowledge discovery from complex data, pages 189-207. Springer, 2005.
[9] C. L. Giles, K. D. Bollacker, and S. Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[10] S. Gui, X. Li, L. Wang, and S. Ji. GOOD: A Graph Out-of-Distribution Benchmark. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[11] W. Hamilton, 7. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances Neural Information Processing Systems, 30, 2017.
[12] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning graphs Advances in Neural Information Processing Systems, 33:221 18-22133, 2020.
[13] C.-W. Huang, D. Krueger, A. Lacoste, and A. Courville. Neural autoregressive flows. In International Conference on Machine Learning. pages
PMLR, 2018.
[14] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 2015.
[15] D. P. Kingma, T. Salimans, R. Jozefowiez, X. Chen, I. Sutskever, and M. Welling. Improved vari- ational inference with inverse autoregressive flow. Advances in Neural Information Processing Systems, 29, 2016
[16] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[17] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
[18) N. Kotelevskii, A. Artemenkov, K. Fedyanin, F. Noskov, A. Fishkov, A. Petiushko, and M. Panov. Nonparametric Uncertainty Quantification for Deterministic Neural Networks. Advances in Neural Information Processing Systems, 35, 2022.
[19] M. Koyama and S. Yamaguchi. When is invariance useful in out-of-distribation generrlizaionnn problem? arXiv preprint wxXii:2008.0/886 2020.
[20] D. Krueger, E. Caballero, J.-H. Jacobsen, A. Zhang, J. Binas, D. Zhang, R. Le Priol, and A. Courville. Out-of-Distribution Generalization via Risk Extrapolation (REx). In International Conference on Machine Learning, pages 5815 5815-5826. PMLR, 2021.
[21] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 30, 2017.
[22] J. Ma, S. Ding, and Q. Mei. Towards more practical adversarial attacks on graph neural networks. Advances in Neural Information Processing Systems, 33:4756-4766, 2020.
[23] A. Malinin. Uncertainty estimation in deep learning with application to spoken language assessment. PhD thesis, University of Cambridge, 2019.
[24] A. Malinin and M. Gales. Predictive uncertainty estimation via prior networks. Advances in Neural Information Processing Systems, 31, 2018

---

[25] J. McAuley, C. Targett, Q. Shi, and A. Van Den Hengel. Image-based based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pages 43-52, 2015.
[26] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
[27] J. Mukhoti, A. Kirsch, J. van Amersfoort, H. Torr, and Y. Gal. Deep deterministic uncertainty: A simple baseline. arXiv e-prints, pages arXiv-2102, 2021.
[28] G. Namata, B. London, L. Getoor, Huang, and U. Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012.
[29] I.. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Infolab, 1999.
[30] Y. Rong, W. Huang. T. Xu, and J. Huang. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In International Conference on Learning Representations. 2020.
[31] Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classifica- tion in network data. Al magazine, 29(3):93-93, 2008.
[32] O. Shchur, M. Mumme, A. Bojchevski, and S. Günneeann. Pitfalls of graph neural network evaluation, Relational Representation Learning Workshop, NeurIPS 2018, 2018.
[33] M. Stadler, Charpentier, Geisler, Zügner, and S. Günnemann. Graph posterior net- work: Bayesian predictive uncertainty for node classification. Advances in Neural Information Processing Systems, 34: 1803-18008, 2021.
[34] B. Sun and K. Saenko. Deep coral: Correlation alignment for deep domain adaptation. In Computer Vision-ECCY 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016, Proceedings, Part III 14, pages 443-450. Springer, 2016.
[35] Y. Sun, S. Wang, X. Tang, T.-Y. Hsieh, and V. Honavar. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the Web Conference 2020, pages 673-683, 2020.
[36] B. Wang, J. Lu, Z. Yan, H. Luo. T. Li, Y. Zheng. and G. Zhang. Deep uncertainty quantification: machine learning approach for weather forecasting. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2087-2095, 2019.
[37] Y. Wang, W. Wang, Y. Liang, Y. Cai, and B. Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pages 3663-3674, 2021.
[38] Q. Wu, H. Zhang, J. Yan, and D. Wipf. Handling Distribution Shifts on Graphs: An Invariance Perspective. In International Conference Learning Representations, 2022.
[39] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk mini- mization. In International Conference on Learning Representations, 2018.
[40] X. Zhang and M. Zitnik. GNNGuard: Defending Graph Neural Networks Against Adversarial Attacks. Advances Neural Information Processing Systems, 03:9263-9275. 2020.
[41] X. Zhao, F. Chen, S. Hu, and J.-H. Cho. Uncertainty Aware Semi-Supervised Learning on Graph Data. Advances in Neural Information Processing Systems, 33: 13:1727--2283. 2020.
[42] D. Zügner and S. Günnemann. Adversarial attacks graph neural networks via meta learning. In International Conference on Learning Representations, 2019.
12

---

A Properties of distributional shifts
This section provides a detailed analysis and comparison of the proposed distributional shifts. For this purpose, we consider three representative real- world datasets Amazon Computer, CoauthorCS, and CoraML, and discuss how different distributional shifts affect the basic properties of data: class bulance, degree distribution, and graph distances between nodes within and OOD subsets.
8.00
3,00
63
0.00
66
80
(a) Popularity
(b) Locality
(c) Density
Figure 2: Class balance for AmazonComputer dataset across different types of shifts.
600
4.55
6.3
6:33
6.15
0.10
6:18
6.5
00C
613
(a) Popularity
(b) Locality
(c) Density
Figure Class balance for CoauthorCS dataset across different types of shifts.
OUD
000
0.20
6:5
2115
620
6.33
or5
(a) Popularity
(b) Locality
(c) Density
Figure 4: Class balance for CoraML dataset across different types of shifts.
Class balance Class balance directly affects the amount of evidence acquired by the graph process- ing model and used for estimating uncertainty and making predictions. It is especially important for evaluating Dirichlet-based models which exploit normalizing flows, as their density estimates can become irrelevant due to significant change in class balance.
In Figures 4 one can see that the popularity- split does not create a notable difference class balance between the ID and OOD subsets (for the datasets under consideration). Thus, the more important and less important nodes have, on average, the same probability of belonging to a particular class. More noticeable differences leads to the most significant changes for some classes. This shows that the split strategies based on the structural locality in graph can be very challenging as they also affect such erucial statistics as class balance.
induced by the density- based split. The locality-basee -bssd split
Degree distribution graph that describes the local importance of nodes. Degrees are especially important for such graph
The node degree distribution is one of the basic structural characteristics of
13

---

W
130
Oogres
degins
Cegres
(a) Popularity
(b) Locality
Density
Figure 5: The distribution of node degrees for AmazonComputer dataset across different shifts.
19
127
107
10
107
10P
12
14
(a) Popularity
(b) Locality
(c) Density
Figure 6: The distribution of node degrees for CoauthorCS dataset across different shifts.
OCD
000
000
102
CHEL
Cegree
Segios
Cegres
(a) Popularity
(b) Locality
(c) Density
Figure 7: The distribution of node degrees for CoraML dataset across different shifts.
processing methods GNNs since they describe how many channels around the considered node are used for message passing and aggregation.
In Figures 7 one can see that the most significant change in the degree distribution appears when the ID and OOD subsets are separated based on PageRank: the ID part contains more high-degree nodes. This is expected since PageRank is graph characteristic measuring node importance (a.k.a centrality), and node degree the simplest centrality measure known to correlated with PageRank. For the locality-basee -bsed splits, the difference in degree distribution is smaller but still significant since PPR selects nodes by their relative importance for a particular node, so some high-degree nodes can be less important. Finally, for the density-based splits, the degree distribution also changes, but the extent of shift is usually less significant, and for some datasets (e.g., CoauthorCS), the higher-degree nodes are in the OOD subset.
Graph distance distribution The distance between two nodes in a graph is defined the length of the shortest path between them. Here, we compute such distances between the nodes in the ID or OOD subset within the original graph, i.e., we consider the whole graph when searching for the shortest path. The distribution of distances illustrates which parts of the datasets are more locally concentrated.
In Figures 10 one can observe that the locality-based split leads to the most significant changes in distances, making the OOD nodes nearly twice as far from each other as the ID ones. At the same time, the popularity-bast based split does not lead to such difference, revealing almost the same distributions on ID and OOD subsets. This means that the popularity bias in graph does not prevent one from
14

---

147
100
100
101
10P
10
100
(a) Popularity
(b) Locality
Density
Figure 8: The distribution of graph distances for AmazonComputer dataset across different shifts.
100
000
COD
107
OC0
180
14
10
10
16
15
29
35
(a) Popularity
(b) Locality
(c) Density
Figure 9: The distribution of graph distances for CoauthorCS dataset across different shifts.
000
on0
10P
139
100
(a) Popularity
(b) Locality
(c) Density
Figure 10: The distribution of graph distances for CoraML dataset across different shifts.
covering the less popular periphery nodes since the most popular nodes may be widespread. Similarly, the density-based split does not induce a significant difference pairwise distances.
15

---

B Results on other split ratios
The main part of our empirical study focused on a 50% 50% split ratio. this section, we extend our discussion with varying ID to OOD ratios and consider two setups where the fraction of OOD samples is smaller - 70% : 30% and 90% 10%.
Let us first revisit our analysis of the proposed structural shifts on a 70% 30% ratio. As can be seen in Table 4 the results both OOD robustness, which is evaluated in the node classification task, and OOD detection, which is done by means of uncertainty estimation, have not changed much compared to our base setup discussed in the main text the considered graph models show the average drop in performance of 3% on the popularity-basee shift and 6% on the density- shift, while the OOD detection performance remains at nearly 81 and 54 points, respectively. Despite the fact that the graph models now have access to more diverse structures in terms of popularity and local density, making decisions about unimportant and sparsely surrounded nodes remains as difficult as before.
Further, the drop in predictive performance on the locality-based shift appears to be less significant compared the original setup and reaches only 5% on average instead of the previous 14%. At the same time, the OOD detection performance on this structural shift drops to 79 points, whereas it was 85 points in the original setup. These results also match our intuition as the distance between the ID and OOD nodes decreases, the OOD samples become less distinguishable from the ID ones. This makes the OOD detection performance drop on average, while the gap between ID and OOD metries in standard node classification disappears.
We also may compare the existing graph models based the results in Table As be seen, the ranking of methods remains almost the same as in the original setup. Specifically, the most simple data augmentation technique Míxup often shows the best performance in OOD robustness, while DE provides the second best results on most structural shifts. As for OOD detection, the methods based on the entropy of predictive distribution again outperform the Dirichlet ones, and the uncertainty estimates produced by DE are best correlated with the OOD examples. Thus, our observations regarding the performance of graph models are consistent with those reported in the paper.
Table 4: Comparison of structural distributional shifts terms OOD robustness and OOD detection. We report the drop in predictive performance of the ERM method measured by Accuracy (left) and the quality of uncertainty estimates of the SE method measured by AUROC (right). The ID to OOD ratio in these experiments is 70% 30% instead of 50% 50% in the main text.
Popularity
Locality
Density
Popularity
Locality
Density
AmazonComputt
3.80 %
12.66 %
14.04 %
Amazon CompterC
87.83
85.77
50.46
AmazonPhoto
-7.19 %
-3.03 %
-6.79 %
AmazonPhotn
91 .1.80
85.78
47.27
CoauthorC'S
-6.51 %
-1.89%
6.64
CiteSeer
70.56
64.55
58.04
CoauthorPhysics
2.58 %
5.50
2.47 %
CoauthorCS
83.68
81.13
63.24
CoraML
-7.56 %
-13.63%
-9.49
CoauthorPhysics
86.70
82.06
39.68
CiteSeer
+3.24 %
+2.00%
4.13%
CoraML
82.06
84.63
76.82
PubMed
+0.46%
-0.67% %
-1.76 %
PubMed
66.64
63.34
55.79
2.35 %
2.36%
4.02 %
CGB-Products
82.35
82.44
43.50
Average
-3.28 %
-4.65 %
-6.17%
Average
81.45
78.71
54.35
Table 5: Comparison of several graph methods for improving the OOD robustness (left) and detecting the OOD inputs by means of uncertainty estimation (right). For each task, we report the method ranks averaged across different graph datasets (lower is better). The ID to OOD ratio in these experiments 70% 30% instead of 50%: 50% as in the main text.
Popularity
Locality
Density
Popularity
Locality
Density
ID
OOD
ID
OOD
ID
OOD
ERM
3.0
3.4
2.9
3.1
4.3
4.3
SE
1.3
2.3
3.7
Mixup
1.9
2.6
1.4
2.7
1.4
3.3
GPN
3.3
3.9
3.9
BERM
4.9
3.9
4.4
NaIPN
5.4
DANN
4.1
4.4
4.3
3.7
2.6
DE
3.0
1.9
CORAL
4.1
4.0
4.4
4.9
4.1
3.7
GPE
3.1
3.9
3.4
DE
3.0
2.7
3.0
2.0
3.0
3.0
NaPP
4.9
5.3
4.4
16

---

Now let us discuss the setup based on more extreme 90% 10% ratio. According to Table the drop predictive performance under the popularity- based and locality-based shifts reaches more than 6% instead of 3% in the previous setup and almost 1 11% instead of 6%, respectively. This was expected and can explained by the fact that graph models are now tested on the nodes with the most extreme structural properties (i.e., nodes with the lowest PageRank or clustering coefficient), and their inaccurate predictions are no longer compensated by the more accurate ones, which were made on the nodes with far less anomalous properties.
At the same time, the performance drop on the locality- based shift appears to be nearly 1% on average. This result is quite reasonable since now graph models have access to the whole variety of graph substructures and node features, which allows them to predict equally well for any graph region regardless of its distance to some particular node. The observed effects are interesting and also important to consider when using our approach for evaluating graph models.
Regarding the OOD detection performance, we observe that results on the locality- -bated shift keep decreasing and reach 73 points, in contrast to 79 points in the previous setup (and this might happen for the same reason as we discussed before). At the same time, the detection metrics on the remaining structural shifts appear be nearly the same (79 points instead of the previous 81 the popularity- based shift) or even better on average (63 points instead of 54 on the density- baasd shift), which is consistent with the changes in predictive performance discussed above.
As for the ranking of different models in Table 7 it remains almost the same, with the most simple methods providing top performance on the majority of prediction tasks.
Table 6: Comparison of structural distributional shifts terms OOD robustness and OOD detection. We report the drop in predictive performance of the ERM method measured by Accuracy (left) and quality of uncertainty estimates of the method measured by AUROC (right). The to OOD 10% instead of 50% 50% as in the main text.
ratio in these experiments is 90%
Popularity
Locality
Density
Popularity
Locality
Density
AmazonComputer
8..45
-7.79 %
-0.98 %
AmazonComputer
83.42
76.53
68.97
AmazonPhoto
+0.12 %
16.35 %
AmazonPhoto
89.01
82.57
64.41
CoauthorCSS
9.79
4.42 %
7.76 %
CiteSeer
75.90
65.11
55.48
CoauthorPhysics
-3.77
-4.91 %
-3.32 %
CoauthorCS
83.22
76.02
70.63
CoraML
16.10%
+5.52 %
8,03 %
ConuthorPhysics
84.68
78.60
52.97
CiteSeer
-5.14% %
+1.35 %
+1.86 %
CoraMI.
79.36
69.64
69.78
PubMed
+3.33 %
+4.70 %
-2.63 %
PubMed
61.05
57.14
55.11
OGB-Products
2.92 %
2.75 %
15.61 %
77.92
78.02
68.33
Average
-1.02 %
10.60
Average
79.32
72.95
63.21
Table 7: Comparison of several graph methods for improving the OOD robustness (left) and detecting the OOD inputs by means of uncertainty estimation (right). For each task, we report the method ranks averaged across different graph datasets (lower is better). The ID to OOD ratio in these experiments 90%: 10% instead of 50%: 50% as in the main text.
Popularity OOD
Locality
Density
Popularity
Locality
Density
ID
OOD
ID
OOD
ERM
3.3
3.7
3.4
3.0
3.3
4.4
SE
1.6
2.6
3.3
Mixup
1.7
2.4
1.7
2.9
1.7
3.0
GPN
3.1
3.0
3.9
BERM
5.0
4.1
5.0
3.7
4.9
3.9
NalPN
5.0
4.4
3.7
DANN
4.3
4.0
4.0
4.3
3.4
3.0
DE
2.6
1.6
CORAL
3.9
3.6
5.1
4.3
3.4
GPE
3.6
4.3
DE
2.9
3.4
3.3
NalPE
4.3
17

---

C Comparison with the GOOD benchmark from Gui et al. [10]
Our work complements and extends the GOOD benchmark recently proposed by Gui et al. 10 However, there are several important differences that we discuss in this section.
One of the main properties of the GOOD benchmark is theoretical distinction between two types of distributional shifts, which are represented through graphical model. In particular, the authors consider covariate shifts, which the distribution of features changes while the conditional distribution of targets given features remains the same, and concept shifts, where the opposite situation occurs, i.e., the conditional target distribution changes, while the feature distribution is the same. Although this distinction might be very helpful for understanding the properties of particular GNN models, such exclusively covariate or concept shifts rarely happen in practice where both types of shifts are present at the same time.
To create pure covariate or concept shifts, Gui et al. [TO] introduce different subsets of variables that either fully determine the target, create confounding associations with the target, or are completely independent of the target. This has to be properly handled and makes non-trivial to create distributional shifts new datasets with this approach. Indeed, the distributional shifts in the GOOD benchmark can be properly implemented only for synthetic graph datasets or via appending synthetic features that either describe various domains completely independent variables or create the necessary concepts by inducing some spurious correlation with the target. Moreover, the authors claim that, in the case of real-world datasets, one has perform screening over the available node features to create the required setup of domain or concept shift. This fact implies numerous restrictions on how the data splits can be prepared.
In contrast, our method does not distinguish between covariate and concept shifts and thus can be universally applied to any dataset and does not require any dataset modifications. Importantly, the type of distributional shift and the sizes of all split parts are easily controllable. This flexibility is the main advantage of our approach.
Finally, Gui al. [10] confirm the importance of using both node features and graph structure. Still, their node-level distributional shifts are mainly based node features such as the number of words or the year of publication in citation network, the language of users in social network, the name of organizations in a webpage network. As for the graph properties, only node degrees are used in some citation networks. In contrast, we focus on graph structure and propose diverse structural shifts together with a framework allowing one to easily create splits based on other structural properties.
18

---

D Structural properties of the OGB data splits proposed by Hu et al. [2]
In Figures 13 we present how the distribution of structural node characteristics, including PageRank, Personalized PageRank, and clustering coefficient, may change across the train and test parts in some OGB datasets, where the distributional shifts are constructed using some domain- specific node feature. This shows that our approach creating data splits using structural graph properties can be similar to realistic distributional shifts.
tnb
371
381
(610006 valuos
prepe-ty Kdlie
preperty AdRAS
(a) PageRank
(b) Personalized PageRank
(c) Clustering coefficient
Figure 11: Structural properties across train and test parts in time-beee based split of OGB-Arxiv.
1D
30
valuo
prepecty sdars
8.6
10
(a) PageRank
(b) Personalized PageRank
(c) Clustering coefficient
Figure 12: Structural properties across train and test parts in rank-based split of OGB-Produce
tnh
10
324
18 53 He
10
10
10
20
preperty
(a) PageRank
(b) Personalized PageRank
(c) Clustering coefficient
Figure 13: Structural properties across train and test parts in species based split of
19

---

E
Dataset characteristics
Characteristics of the datasets used this paper are listed in Table
Table 8: Description of the considered graph datasets for node classification task.
Dataset
Nodes
# Edges
# Classes
Features
AmazonComputer
13,381
259,159
10
767
AmazonPholo
7,484
126,530
8
745
CoauthorCS
18,333
163,788
15
6,805
CoauthorPhysics
34,493
495,924
5
8,415
CoraML
2,995
16,316
7
2,879
CiteSeer
3,327
4,732
3,703
PubMed
19,717
44,338
8,415
OGB-Products
2,449,029
61,859,110
47
100
F
Method configurations
consider graph For our main series of experiments with graph models in Sections 5.1 and 5.2 encoder based on three GCN convolutional layers [16]. On top of this graph encoder, we use a single linear layer the task-specific head, which is used predict the parameters of categorical distribution in classification tasks, the parameters of Dirichlet distribution for modeling uncertainty, The hidden dimension of baseline architecture is 256, and the dropout between hidden layers is = 0.2. We exploit a standard Adam optimizer decay of 0.00001. For additional series of experiments with improved GNN architecture, which is discussed in Section 5.3 we reduce the number of graph convolutional layers from 3 to 2, replacing the first one with pre-processing step based on linear layer, apply the skip-connections between graph convolutional layers, and replace the GCN graph convolution with SAGE [.].
14] with a learning rate of 0.0003 and a weight
Some of the considered methods for improving the OOD robustness, such DANN and CORAL, exploit the notion of domains and require the knowledge about which nodes in the training set belong to which domain. Therefore, need to define domains, which is not straightforward since node properties are real-valued, not discrete. Thus, we discretize the values into k = 10 non-intersecting domains. After that, we assign domain index each node. These indices treated labels and used by DANN and CORAL during their training.
20

---

G
Detailed experimental results
In this section, we provide detailed experimental results.
Tables 15 show the predictive performance of various OOD robustness methods on the proposed structural distributional shifts;
show the OOD detection performance of various uncertainty estimation methods the proposed structural distributional shifts.
Tables T6
Table 9: Comparison of several graph methods for improving the OOD robustness in terms of their predictive performance across structural shifts CoraML dataset.
popularity
locality
density
ID
OOD
ID
OOD
ID
0OD
ERM
85.80 1.10
82.42
0.79
84.47
72.13 1.74
93.27 0.28
77.33
1.07
Mixup
89.27 + 0.57
83.65
0.67
86.27
0.57
78.42 = 0.84
88.20
+ 0.44
78.98 2.100
BERM
88.40 1: 1.22
83.07
0.76
88.80
0.73
69.96 1 6.62
86.87 1 0.45
79.07
0.32
DANN
86.00 + 1.10
79.01
+ 0.77
81.45 + 0.65
65.03 = 2.51
91.33 + 0.76
78.37 = 2.07
CORAL
85,00 + 1.11
77.65
0.62
82.33
0.25
66.83 2.24
80.55 1 0.54
73.34 :: 2.28
DR
87.00 + 0.00
82.74
:: 0.00
84.67
+ 0.00
75.40 + 0.00
93.00
+ 0.00
78.90 + 0.00
ERM mod
85.33 + 0.62
82.55
0.56
84.87 + 0.61
72.59 = 0.96
94.13 = 0.69
79.33 0.37
Table 10: Comparison of several graph methods for improving the OOD robustness in terms of their predictive performance across structural shifts on CiteSeer dataset.
popularity
locality
density
OOD
OOD
OOD
ERM
72.43 + 1.33
72.42 + 0.37
77.60 + 0.66
57.03 = 1.16
73.75 + 0.96
67.57 = 0.49
Mixup
72.79 1 0.74
72.13
1 0.69
76.82
0.59
56.45
1 4.53
76.88 1 1.47
68.59 1 2.12
FERM
71.47
1.01
70.48
+ 0.66
75.31
0.80
61.95
+ 3.30
76.46 + 0.92
0.71
DANN
67.57 + 0.96
67.84
0.65
71.17 + 71.87
0.33 0.33
54.90 = 2.49
75.07 + 1.48
61.13 2.82
CORAL
67.87 1.19
67.77100.38 0.38
0.62
57.16 1 1.84
73.47 1 1.22
58.53
2.02
DE
73.27
0.00
72.37
0.00
78.38
0.00
64.71 0.00
74.17
+ 0.00
70.35
0.00
ERM mod
73.75 0.62
71.73
1.02
76.70
4 1.14
= 2.23
75.80
+ 0.96
68.32
1.01
Table 11: Comparison of several graph methods for improving the OOD robustness in terms of their predictive performance across structural shifts on PubMed dataset.
popularity
locality
density
ID
0OD
ID
OOD
ID
0OD
ERM
86,85 + 0.12
84.04
0.33
86.75 + 0.48
81.80 - 1.07
85.96 + 0.27
85.29 2.19
Mixup
89.32 1 0.24
88.21
1 0.21
87.94
0.37
86.20
1 0.75
88.72
1 0.25
88.23
EERM
86.83 + 0.12
83.39
+ 0.10
85.67
0.24
84.79 0.18
86.43 + 0.22
84.10
DANN
86.26 + 0.48
$4.49.1..19
86.04 0.30
85.41 1.04
87.07 0.24
8.17
CORAL
86.31 + 0.48
0.32
1.63
87.24 0.15
84.86
DE
87.17 + 0.00
84.72
87.07 0.00
0.00
86.61 0.00
85.97
ERM mod
88.83 1 0.24
87.39 0.22
88.32 0.511
87.5810.
1.5610.43
87.71 1.222
21

---

Table 12: Comparison of several graph methods for improving the OOD robustness in terms their
predictive performance across structural shifts AmazonComputer dataset.
popularity
locality
density
ID
OOD
ID
0OD
ID
OOD
92.43 1 0.24
83.18
93.04
72.62 0.52
93.10
0.27
85.73
0.60
Mixup
92.27 + 0.19
66.80
2.84
66.94 + 2.00
92.46
0.44
74.72
EERM
89.49 + 1.55
0.61 82.08
92.22 0.37
88.09
0.55
79.98
1.28
DANN
91.25 + 0.37
1.87 83.39
92.30
+ 0.77
68.84 2.53
91.84 0.79 0.79
83.89 = 1.37
CORAL
91.25 1 0.54
84.77
92.47 0.18
62.36 1.87
91.40 0.91
85.35 1: 1.58
DR
92.51 + 0.00
84.17
0.00
93.31
+ 0.00
73.93
93.24 + 0.00
86.93
+ 0.00
ERM mod
90.99 + 0.16
85.72 #
91.74 + 0.24
63.67 = 0.35
92.40 = 0.34
86.17 = 0.20
Table 13: Comparison of several graph methods for improving the OOD robustness in terms of their predictive performance across structural shifts on AmazonPhoto dataset.
popularity
locality
density
ID
OOD
ID
OOD
ID
OOD
FRM
95.82
0.24
87.63
0.65
93.73
64.73
3.80
94.64
0.38
0.16
Mixup
97.99
0.36
87.73
95.55 + 0.30
75.36
95.50
0.41
90.71
2.13
BERM
95.90
0.40
86.84
1.02
91.95 1 0.21
54.06
0.81
90.46
1 0.38
88,91
0.31
DANN
95.25 + 0.26
85.23
0.78
91.81 + 0.39
48.79 = 5.04
93.99 + 0.66
91.87 0.46
CORAL
95.34 + 0.27
85.91
+ 0.67
91.85
+ 0.51
45.70 = 3.34
93.64 0.80
0.43
DB
95.82
1 0.00
88.82 1 0.00
93.59
1 0.00
69.15 1 0.00
94.38 1 0.00
92.09
0.00
ERM mod
97.07
+ 0.35
89.95 + 0.20
95.01 + 0.43
57.41 = 1.79
95.22 + 0.33
91.97
0.33
Table 14: Comparison of several graph methods for improving the OOD robustness in terms their predictive performance across structural shifts Coauthor dataset.
popularity
locality
density
ID
0OD
ID
OOD
ID
OOD
ERM
93.60
0.18
0.20
91.22
0.35
94.30
0.17
Mixup
94.97 + 0.33
94.05
94.05
91.48 = 0.16
94.97
0.29
92.11
0.15
BERM
93,82 1 0.08
91.01
0.15
91.22
0.27
91.95
93.64 0.23
88.42 1.15
DANN
93.89 + 0.26
90.59
1.:9::0.11 0.12
91.66
+ 0.37 0.37
1.29 91.65
94.60 0.16
89.92 1.92-:0.99
CORAL
93.80 1 0.14
90.78
0.13
91.69
0.23
91.37
1 0.48
94.42
0.07
89.7210.22
DE
93.68
+ 0.00
90.93
+.93:00 0.00
92.64
+ 0.00
91.76
0.00
94.55 + 0.00
90.05 -
0.00 0.00
ERM mod
95.35 + 0.15
95.00
94.77
+ 0.09
94.06 1.06
96.67 0.11
93.64 0.16
Table 15: Comparison of several graph methods for improving the OOD robustness in terms their predictive performance across structural shifts CoauthorPhysic. dataset.
popularity
locality
density
ID
OOD
ID
OOD
ID
OOD
ERM
93.60
0.18
90.67
0.20
0.14
91.25
0.35
94.30 0.17
89.71 =
Mixup
96.96 + 0.11
94.05 0.74
97.27
0.11
93.39
0.95
96.80 1 0.08
84.57 0.88
FERM
95.93 + 0.10
93.37
1: 0.08
94.01
0.16
92.32
0.11
95.26 + 0.03
93.98
0.06
DANN
96.56 + 0.14
93.73 0.25
96.64
0.23
11.55111
96.08 0.17
95.05
CORAL
96,51
1 0.10
93.58
1 0.29
96,93
0.08
86.21
0.86
95.97 95.00 0.09
DR
93.68
+ 0.00
90.93
+ 0.00
92.64 +
91.76 0.00
94.55 0.00
90.05
ERM mod
95.35 + 0.15
95.00
94.77 + 0.09
96.67 0.11
93.61
22

---

Table 16: Comparison of several graph methods for uncertainty estimation terms of their OOD detection performance across structural shifts on CoraML dataset.
Popularity
Locality
Density
SE
0.85
87.13 0.74
81.55
NarPN
47.31
9.44
81.66 + 3.05
69.05
GPN
66.95 + 1.15
73.09 + 2:21
70.95
1.58
DE
70.55 0.00
93.32 1: 0.00
84.46 1: 0.00
NaPPE
37.59 0.00
78.48 0.00
65.83 0.00
GPE
65.67 0.00
74,23 1 0.00
71.07 0.00
SF + mod
55.66 0.25
72.97 + 0.71
68.27 + 0.58
Table 17: Comparison of several graph methods for uncertainty estimation in terms of their OOD detection performance across structural shifts on CiteSeer dataset.
Popularity
Locality
Density
SE
68.01 + 1.23
89.89 i 0.56
66.90 0.41
NatPN
31.18 = 1.54
91.96 = 3.14
59.77 = 1.54
GPN
61.99 1: 1.74
69.53 1 5.10
57.41 :: 1.72
DE
56.22 + 0.00
98.18 + 0.00
70.48 + 0.00
NalPE
28.07 1 0.00
89.02 1 0.00
58.10
GPE
63.01 = 0.00
73.89 + 0.00
5.004
mod
54.36 + 0.56
1..74
61.03 0.73
Table 18: Comparison of several graph methods for uncertainty estimation terms of their OOD detection performance across structural shifts PubMed dataset.
Popularity
Locality
Density
SE
68.60 + 0.34
66.34 + 1.03
58.60 0.39
NaPNN
49.61 3.17
58.91 1 2.89
51.00 1.45
GPN
72.30 = 0.29
69.63 - 4.84
62.04 - 0.68
DE
74.31 0.00
72.19 1 0.00
63.04 1 0.00
NaIPR
46.94
56.41 0.00
49.54 0.00
GPE
72.62 = 0.00
66.07
= 0.00
62.58 0.00
SE mod
53.68 0.11
54.86 1 0.72
52.25 0.133
23

---

Table 19: Comparison of several graph methods for uncertainty estimation terms of their OOD detection performance across structural shifts on AmazonComputer dataset.
Popularity
Locality
Density
SE
88.52 + 0.37
86.48
0.80
44.24 + 0.57
NatPN
53.83
15.71
59.92
6.59
44.42 3.44
GPN
82.84
2.56
DE
82.53 = 0.00
83.54
50.88 0.00
NatPE
41.33
42,09 0.00
GPF
81.35 + 0.00
81.97 0.00
43.81 + 0.00
SE mod
6..44
74.09 0.64
59.27 0.44
Table 20: Comparison of several graph methods uncertainty estimation terms of their OOD detection performance across structural shifts on AmazonPhoto dataset.
Popularity
Locality
Density
92.05 + 0.27
93.29 + 0.60
41.08 + 1.89
NatPN
79.72 + 7.29
65.66 11.98
54.88
17.40
80.85 2.64
90.90
2.82
49.97 2.24
90.72 0.00
96.66 0.00
51.33 0.00
NaPP
80.43 + 0.00
59.74 - 0.00
64.69 + 0.00
GPE
82.95 1 0.00
91.61 1 0.00
SE mod
66.93 + 0.47
83.09 = 1.57
51.36 + 0.94
Table Comparison of several graph methods for uncertainty estimation terms of their OOD detection performance across structural shifts CoauthorCS dataset.
Popularity
Locality
Density
SE
83.25
0.40
85.74 1 1.06
50.91 i 0.26
NatPN
59.99 = 5.57
64.53 = 12.82
58.47 = 8.22
GPN
63.43
64.84 1.57
56.81 0.54
DE
82.50
0.00
87.54 0.00
54.47 = 0.00
NatPE
61.00 1 0.00
60.55 1 0.00
62.63 0.00 0.00
GPE
62.12 = 0.00
63.76 + 0.00
57.15 0.00
SE mod
58.05 + 0.71
64.43 + 1.40
56.99 + 0.26
Table Comparison of several graph methods for uncertainty estimation terms of their OOD detection performance across structural shifts on Coauthor dataset.
Popularity
Locality
Density
86.60
0.29
87.73 + 0.51
37.50 + 0.32
NatPN
56.74 3.68
59.54 + 23.75
58.81 + 5.96
GPN
67.48 0.45
74.05 2.67
0.53
DE
85.94 0.00
91.93 0.00
36.15
NatPE
56.11 0.00
46.14 0.00
56.94 0.00
GPF
66.29
0.00
72.16 0.00
SE mod
61.84 0.73
88.02 + 0.31
44.13 0.31
24

---

H Visualization of distributional shifts in graph domain
In Figures 14 20 we provide the visualizations of different structural shifts in graph domain for all the considered graph datasets: ID is blue, OOD is red. Some graphs have multiple connected components - in that case, we keep only the largest one.
(a) Popularity
(b) Locality
(c) Density
Figure 14: Visualization of structural shifts in graph domain for CoraMI dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 15: Visualization of structural shifts in graph domain for CiteSeer dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 16: Visualization of structural shifts in graph domain for PubMed dataset.
25

---

(a) Popularity
(b) Locality
(c) Density
Figure 17: Visualization of structural shifts in graph domain for AmazonPhoto dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 18: Visualization of structural shifts in graph domain for AmazonComputer dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 19: Visualization of structural shifts in graph domain for CoauthorCS dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 20: Visualization of structural shifts in graph domain for CoauthorPhysics dataset.
26

---

Visualization of distributional shifts in node feature space
In Figures 27 we provide the visualizations of different structural shifts in node feature space for all the considered graph datasets: ID is blue, OOD is red. The pictures are obtained by reducing the original node feature space into the 2D space of t-SNE representations.
STHE
(a) Popularity
(b) Locality
(c) Density
Figure 21: Visualization of structural shifts in node feature space for CoraML dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 22: Visualization of structural shifts in node feature space for CiteSeer dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 23: Visualization of structural shifts in node feature space for PubMed dataset.
27

---

(a) Popularity
(b) Locality
(c) Density
Figure 24: Visualization of structural shifts in node feature space for AmazonPhoto dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 25: Visualization of structural shifts in node feature space for AmazonComputer dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 26: Visualization of structural shifts node feature space for CoauthorCS dataset.
(a) Popularity
(b) Locality
(c) Density
Figure 27: Visualization of structural shifts in node feature space for CoauthorPhysies dataset.
28


Reviews:
[{"review_id": "t0zrc3tIWF", "reviewer": "Reviewer_AZW5", "summary": "This paper proposes a general approach for inducing diverse distributional shifts based on graph structure and evaluates the robustness and uncertainty of graph models under these shifts. The authors define several types of distributional shifts based on graph characteristics, such as popularity and locality, and show that these shifts can be quite challenging for existing graph models. They also find that simple models often outperform more sophisticated methods on these challenging shifts. Additionally, the authors explore the trade-offs between the quality of learned representations for the base classification task and the ability to separate nodes under structural distributional shift. Overall, the paper's contributions include a novel approach for creating diverse and challenging distributional shifts for graph datasets, a thorough evaluation of the proposed shifts, and insights into the trade-offs between representation quality and shift detection.", "questions": "Here are some questions and suggestions for the authors:\n\nCan the proposed approach be extended to other types of graph problems, such as link prediction or graph classification? If so, how might the approach need to be modified to accommodate these different types of problems?\n\nHow might the proposed approach be adapted to handle real-world distributional shifts, rather than synthetically generated shifts? Are there any limitations to the proposed approach that might make it less effective in handling real-world shifts?\n\nHow does the proposed approach compare to other existing methods for evaluating graph models under distributional shifts? Are there any specific strengths or weaknesses of the proposed approach compared to other approaches?\n\nThe paper notes that there is a trade-off between the quality of learned representations for the target classification task and the ability to detect distributional shifts using these representations. Can the authors provide more details on this trade-off and how it might impact the effectiveness of the proposed approach in different scenarios?\n\nThe paper proposes several different types of distributional shifts based on graph structure. Can the authors provide more details on how these shifts were chosen and whether there are other types of shifts that might be relevant for evaluating graph models?\n\nThe paper focuses on evaluating graph models under distributional shifts, but does not provide any guidance on how to modify existing models to improve their robustness to these shifts. Can the authors provide any suggestions or guidelines for modifying existing models to improve their performance under distributional shifts?\n\nThe paper notes that the proposed approach can be applied to any dataset, but does not provide any guidance on how to choose the appropriate node property to use as a splitting factor. Can the authors provide any suggestions or guidelines for choosing an appropriate node property for a given dataset?\n\nOverall, the paper presents an interesting and novel approach for evaluating graph models under distributional shifts. However, there are several areas where the authors could provide more details or guidance to help readers better understand and apply the proposed approach.", "limitations": "The paper briefly acknowledges some of the limitations of the proposed approach, such as the fact that the synthetic shifts may not fully reflect the complexity of real-world distributional shifts. However, the paper does not provide a detailed discussion of the potential negative societal impact of the work.\n\nGiven the technical nature of the paper, it is possible that the authors did not see a direct connection between their work and potential negative societal impacts. However, it is always important for authors to consider the broader implications of their work, especially in fields like machine learning where there is a growing awareness of the potential risks and harms associated with these technologies.\n\nIn future work, the authors could consider providing a more detailed discussion of the potential societal impacts of their work, including any ethical or social considerations that may arise from the use of their approach. This could help to ensure that the work is being developed and applied in a responsible and ethical manner.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper's approach for inducing diverse distributional shifts based on graph structure is novel and fills a gap in the existing literature, which has mainly focused on node features. The authors' proposed shifts are also motivated by real-world scenarios and are synthetically generated, making them a valuable resource for evaluating the robustness and uncertainty of graph models.\n\nQuality: The paper's methodology is rigorous and well-designed, with clear explanations of the proposed shifts and the evaluation metrics used. The authors also provide extensive experimental results that demonstrate the effectiveness of their approach and highlight the challenges that arise when evaluating graph models under distributional shifts.\n\nClarity: The paper is well-written and easy to follow, with clear explanations of the proposed shifts and the evaluation methodology. The authors also provide helpful visualizations and examples to illustrate their points.\n\nSignificance: The paper's contributions are significant and have implications for the development of more robust and reliable decision-making systems based on machine learning. The authors' approach for inducing diverse distributional shifts based on graph structure can be applied to any dataset, making it a valuable resource for researchers and practitioners working on graph learning problems. The insights into the trade-offs between representation quality and shift detection are also important for understanding the limitations of existing graph models and developing more effective ones. Overall, the paper's contributions have the potential to advance the field of graph learning and improve the reliability of machine learning systems.", "weaknesses": "Limited scope: The paper focuses solely on node-level problems of graph learning and does not consider other types of graph problems, such as link prediction or graph classification. This limited scope may restrict the generalizability of the proposed approach and its applicability to other types of graph problems.\n\nSynthetic shifts: While the authors' proposed shifts are motivated by real-world scenarios, they are synthetically generated, which may limit their ability to capture the full complexity of real distributional shifts. The paper acknowledges this limitation, but it is still worth noting that the proposed shifts may not fully reflect the challenges that arise in real-world scenarios.\n\nLimited comparison to existing methods: While the paper provides extensive experimental results that demonstrate the effectiveness of the proposed approach, it does not compare the proposed approach to other existing methods for evaluating graph models under distributional shifts. This limits the ability to assess the relative strengths and weaknesses of the proposed approach compared to other approaches.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review! We appreciate your support and address your comments below (the order of questions is preserved).\n\nQ1. In graph-level problems, the notion of structural distributional shift might be significantly different and depend on particular applications. On the contrary, many node-level and edge-level problems have a lot in common in terms of what a plausible structural shift may look like. For instance, in link prediction problems, one may have to train their model on the edges that connect very popular nodes to unpopular ones, which is a very common and meaningful situation in real-world scenarios, and then test on the edges between mostly unpopular nodes. The same sort of reasoning can be done for the structural shifts based on locality, where one has access only to some local region of a graph and need to predict edges between the nodes of a distant region. Thus, our proposed structural shifts can be easily transferred for evaluating the robustness and uncertainty of graph models in edge-level problems.\n\nQ2. Our approach is designed specifically for situations when real-world distributional shifts are not available. In such cases, synthetically generated shifts can serve as a reasonable approximation. In Appendix C, we show that the proposed structural shifts enable us to catch some properties of real-world ones.\n\nQ3. Please refer to Appendix B, where we discuss how our method for creating data splits with structural shifts extends the GOOD benchmark, and how it allows us to overcome some of their practical limitations. Moreover, in Appendix C, we show that the proposed structural shifts enable us to catch some properties of the distributional shifts between train and test subsets in realistic data splits of the OGB benchmark. If these sections do not cover some important aspects of comparison, please let us know.\n\nQ4. We note that our approach for generating distributional shifts is orthogonal to the problem of developing models capable of dealing with them. We hope that our diverse and complex structural shifts will help researchers in investigating this trade-off and developing models that are both robust to distributional shifts and able to detect them.\n\nQ5. This question is covered in Section 3.2, where we discuss the motivation behind our proposed structural shifts and how they can arise in real-world applications. In addition, we mention there some other examples of node-level characteristics that can be used to describe the chosen structural properties, such as node degree as the measure of popularity and graph distance as the measure of locality. The structural shifts considered in our paper are intuitive and practically motivated. However, any node characteristic can be used for splitting, and also different characteristics can potentially be combined to create more complicated shifts.\n\nQ6. In Section 5.3, we partially cover this question and demonstrate that it is possible to make several modifications to the GNN model which help it to deal with distributional shifts. However, a more principled solution to this question is non-trivial and requires further investigation. We hope that our proposed method for creating distributional shifts will support studies in this area.\n\nQ7. In fact, the choice of some structural node property as a splitting factor might depend significantly on a particular application. In our paper, we consider quite diverse node characteristics that have different motivations behind them and impact on the performance of graph models, so we recommend using all of them to conduct experiments and aggregate the obtained results for making final decisions."}, {"review_id": "rTdaqzeYYx", "reviewer": "Reviewer_gSyv", "summary": "This paper provides a benchmark solution for producing diverse and meaningful distributional shifts from existing graph datasets. The experiments conducted demonstrate that the proposed distributional shifts can be difficult for existing graph models, and surprisingly, simpler models often outperform more sophisticated ones. The experiments also reveal a trade-off between the quality of learned representations for the base classification task and the ability to distinguish nodes from different distributions using these representations.", "questions": "Please refer to the Weakness section. ", "limitations": " I am not seeing limitations of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed data-splitting approach is quite interesting. The overall presentation is quite easy to follow.  \nBased on the provided data-splitting strategy, most graph/node classification methods may not achieve a good classification performance and uncertainty quantification quality. It is also nice to see the authors conduct many empirical studies to validate the idea and compare the difference between various baselines. ", "weaknesses": "1. The technical novelty is somewhat limited. It seems like the technical contribution is based on existing techniques (PageRank, PPR, ...). I would like to see more discussions of the rationale/motivation for choosing the specific metric. For example, the PageRank is selected because of the need to quantify the node popularity, but other node centrality-based metrics can also be used to quantify the node popularity.   \n2. The dataset size is also quite small. It's not promising the experience learned from these small networks can be extended to million-scale networks.\n3. Some important baselines (e.g., GOOD: A Graph Out-of-Distribution Benchmark) are not included in the main context. \n\nI feel like this paper should be more suitable for the dataset and benchmark track.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review! We appreciate that you find our approach to create data splits interesting and the presentation easy to follow. Below, we reply to your comments.\n\nW1. Our main contribution is an approach for creating data splits with distributional shifts based on various structural properties. For our experiments, we consider some particular examples of node characteristics (specifically, PageRank, PPR, and clustering coefficient) as they are quite diverse, widely adopted in the community, and related to situations that may arise in practice. However, as mentioned in Section 3.2, other node characteristics can also be used instead of the chosen ones (e.g., node degree as the measure of popularity or graph distance as the measure of locality). As for PageRank, we choose this metric because it is less discrete than node degree and also widely used in the literature.\n\nW2. We conduct our experiments on several graph datasets that have been used in most previous works and adopted in established graph benchmarks. They come from various domains and applications, while having different structure and number of node features. Although these datasets do not fall under the category of large-scale datasets, they still enable us to conduct the necessary experiments and support our claims about the performance of graph models under structural distributional shifts.\n\nHowever, if you feel that our discussion can remain incomplete without some large-scale graph datasets, please let us know which of them we should include, and we will do our best to conduct additional experiments on them and include our results into the revised version.\n\nW3. Could you please explain what you mean by such baselines? \n* If you would like to see the evaluation of other methods for improving OOD that have been considered in the GOOD benchmark and have some particular recommendations, please let us know the names of these methods so that we could test them on the proposed structural shifts and include the results into the revised version;\n* If your comment refers to the lack of comparison between our distributional shifts and those proposed in the GOOD benchmark, we can extend the main text with the content of Appendix B, which describes how our approach to create structural shifts extends GOOD and allows us to overcome some of their practical limitations.\n\n> I feel like this paper should be more suitable for the dataset and benchmark track.\n\nPlease refer to our [general response](https://openreview.net/forum?id=nJFJcgjnGo&noteId=EvXe6dwLzG)."}, {"review_id": "zwiK9lWSR2", "reviewer": "Reviewer_E4Gb", "summary": "The authors propose three domain selections, namely, popularity, locality, and density to equip node prediction datasets with structural distribution shifts. Extensive experiments are conducted to compare present OOD generalization methods and OOD detection methods.", "questions": "Q1: Can you find a way to compare your proposed shifts with the real shifts?\n\nQ2: I would suggest submitting benchmark works to the Datasets and Benchmarks track, which offers more transparent evaluations to your benchmark.", "limitations": "Broader impacts are expected to be discussed.\nThe licenses of the datasets and the code (GOOD) are expected to be mentioned.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1: The proposed distribution shifts are novel.\n\nS2: The paper is well written and easy-to-follow.\n\nS3: The evaluations are clear and sufficient.", "weaknesses": "W1: The title is misleading. Since this benchmark only focuses on node prediction tasks, the title should reflect it. As we know, structural distribution shifts are different in graph-level and node-level tasks.\n\nW2: The chosen shifts are somehow limited because they are not extracted from real-world scenarios.\n\nW3: Line 39: \"Also, the splitting strategies in GOOD are mainly based on the node features and do not take into account the graph structure\" is somehow misleading. I suggest the authors to clarify that \"GOOD mainly focuses on node feature shifts in **node-level tasks**\".\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review! We appreciate your encouraging feedback about our work and address your comments below.\n\nW1. Thanks for this remark. Indeed, the notion of structural distributional shift might be significantly different in graph-level problems, so it is important to emphasize that our approach to induce structural shifts is primarily intended for node-level problems. We will change the title accordingly.\n\nW2. This concern is reasonable. Because of that, we devote a significant part of the text to the discussion of this limitation. In Section 3.2, we provide the motivation behind the proposed structural shifts — specifically, we describe how they can arise in real-world applications and how they can be modeled by our split strategies based on various structural node properties. Of course, having real distribution shifts for a particular application would be preferable, but our goal was to address the situations when such natural splits are unavailable. Moreover, in Appendix C, we show that the proposed structural shifts enable us to catch some properties of the distributional shifts between train and test subsets in realistic data splits of the OGB benchmark. Note that we outline our limitations in a separate paragraph of conclusion.\n\nW3. Thanks for this comment, we will make the necessary clarification in the revised version of our paper.\n\nQ1. Yes, this is done to some extent in Appendix C, where we discuss how the chosen node-level characteristics that describe particular structural properties, including PageRank, PPR and clustering coefficient, correlate with the distributional shifts induced by the split strategies of the OGB benchmark. Unfortunately, there are not many examples of real distributional shifts in known graph benchmarks. Otherwise, we would not need such an approach that allows us to create data splits with synthetic structural shifts that replicate the properties of the real ones.\n\nQ2. Please refer to our [general response](https://openreview.net/forum?id=nJFJcgjnGo&noteId=EvXe6dwLzG)."}, {"review_id": "1Vitgw3ksI", "reviewer": "Reviewer_2ynW", "summary": "This paper proposes a benchmark for evaluating model robustness against structural distributional shifts. The authors propose three different metrics to split the datasets for the evaluation. In the experiments, the authors evaluate different models under the proposed distributional shifts and show that they can be quite challenging for existing graph models.", "questions": "In addition to the above weaknesses, another question is (line 290-292), the authors\"... including DANN, CORAL, EERM, and Mixup, we use the experimental framework from the GOOD benchmark, whereas the remaining methods are implemented in our custom experimental\nframework ...\", what does it mean? Why not just use the same experimental framework?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper targets an understudied problem of evaluating model robustness and uncertainty estimation under structural distribution shift.\n\n2. It presents a novel idea of using different evaluation metrics to create data splits for structural distribution shifts.\n\n3. The authors evaluate different methods based on the proposed metrics and show some empirical findings.", "weaknesses": "1. The authors consider less important nodes are OOD nodes. However, real-world graphs follow the power-law distribution and only have a small number of nodes that have a high degree/node importance. So the proposed metric is kind of counterintuitive to me.\n\n2. The experimental setup, particularly the equal splitting of in-distribution (ID) and out-of-distribution (OOD) data, raises concerns about the generalizability of the findings. Real-world scenarios typically involve a smaller proportion of OOD data, and investigating varying ratios of ID to OOD data would enhance the practical relevance of the evaluation.\n\n3. Since the authors argue the existing methods only focus on feature distribution shift, while this paper only focuses on the structural distribution shift. It would be better to consider them together rather than separately evaluate them, as they often occur simultaneously and have interdependencies.\n\n4. While the proposed metrics for creating data splits are new, the authors could provide more detailed justification and analysis for their choices. It would be beneficial to explore the sensitivity of the evaluation results to different metric configurations.\n\n5. I have a concern that should this paper be submitted to the datasets and benchmark datasets since this paper doesn't focus on technical contribution. \n\nTo strengthen the paper, it would be beneficial to address these additional points and provide more comprehensive justifications, analyses, and experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review! We appreciate that you also consider the problem of evaluating robustness and uncertainty of graph models under structural distributional shift to be understudied, and that you find our idea to use structural node properties for inducing distributional shifts novel. Below, we address your concerns and questions.\n\nW1. If we understand correctly, you consider here another notion of OOD that is based on how many objects in the given dataset have a particular structural property and suggest that the observations with the rarest values of a structural property should be treated as OOD (for instance, as you mentioned, the nodes with high degree in the power-law distribution should belong to OOD). At the same time, rather than focusing on which proportions of nodes share some specific structural property, we try to construct OOD based on how labels might be assigned to the nodes in real-world applications (and in what order they become available for a graph model to extract knowledge from them). Even if there are much more unimportant nodes in the network, they can easily appear to be OOD for a graph model that has learned the structural patterns of the most important nodes that had been investigated first. So, your remark about the power-law distribution of node degrees in real-world networks is true, but it does not contradict our approach to model structural shifts.\n\nW2. Thank you for pointing this out. We believe that in most real-world scenarios, the presence of a large amount of labeled data is rather an exception. In our empirical study, we try to simulate such a situation when the lack of a sufficient amount of labeled data is combined with the presence of structural distributional shift. \n\nNevertheless, we agree with the importance of investigating other ratios of ID and OOD data to understand whether our findings can be transferred to other cases. Because of that, we have conducted an additional series of experiments where we change the proportion of ID and OOD data, and we discuss them in our [general response](https://openreview.net/forum?id=nJFJcgjnGo&noteId=EvXe6dwLzG).\n\nW3. As you have mentioned, the problem of evaluating model robustness and uncertainty estimation under structural distribution shift is under-explored. In this work, we focus on this aspect and isolate ourselves from the task of simulating complex distributional shifts that are explicitly based on both the structural properties and the node features. It facilitates our study of existing graph models and investigation of various effects in their performance associated with the changes of graph structure. Please also note that graph structure is the only common modality of different graph datasets that can be explored in the same manner, whereas node features may vary significantly across different domains and applications. \n\nHowever, we have conducted additional analysis to show that our proposed structural shifts also induce the distributional shift in feature space of the considered graph datasets. Several figures demonstrating this effect can be found in our [general response](https://openreview.net/forum?id=nJFJcgjnGo&noteId=EvXe6dwLzG). As future research, it would be interesting to consider some techniques for inducing distributional shifts in graph data where the changes in graph structure and node features could be controlled simultaneously.\n\nW4. Our main idea is that data splits can be created based on various structural properties. Thus, one can potentially use any other node characteristics within our split strategy. In our experiments, we have chosen three particular options that are diverse and reasonable: please, refer to Section 3.2 for a detailed motivation of our choices. In Section 5.1, we investigate how challenging the proposed structural shifts are for some existing graph models in terms of their robustness and uncertainty estimation. Moreover, Appendix A demonstrates how these shifts affect other important graph properties, such as class balance, degree distribution, and pairwise node distances. Finally, in Appendices B and C, we discuss how our approach to create distributional shifts, along with three particular choices of structural node properties, allow us to create a more challenging setting for evaluating the performance of graph models, while complementing and extending the existing techniques. We hope that these sections make the analysis of the proposed structural properties fairly detailed and complete. However, if you have any ideas on how we can further improve this part of our study, could you please share your thoughts so we can adjust the paper accordingly?\n\nW5. Please refer to our [general response](https://openreview.net/forum?id=nJFJcgjnGo&noteId=EvXe6dwLzG).\n\nQ1. In this sentence, we clarify that the experiments with the methods for improving OOD robustness, where we measure the predictive performance in standard node classification, are conducted using the GOOD framework, as it provides all necessary functions. However, the experiments with uncertainty estimation methods, which are evaluated in OOD detection, required a substantially different set of functions (e.g., basic routines for predictions, architecture design, evaluation procedure, metrics, etc.), so we found it much easier to develop a custom experimental framework rather than extending that of GOOD benchmark."}]

Author rebuttal:
**General response**

We would like to thank all the reviewers for their valuable feedback and suggestions! In this general response, we address questions raised by several reviewers and describe additional experiments we conducted.

**Additional experiments**

As requested by Reviewer 2ynW, we extend our empirical study with greater ID to OOD ratio (70% to 30% instead of 50% to 50% as in the paper) and provide the results in the attached PDF.

Let us revisit our analysis of the proposed structural shifts. As can be seen in Table 1, the results in both OOD robustness, which is evaluated in node classification task, and OOD detection, which is done by means of uncertainty estimation, have not changed much compared to the previous setup — the considered graph models show the average drop in performance of 3% on the popularity-based shift and 6% on the density-based shift, while the OOD detection performance remains at nearly 81 and 56 points, respectively. Despite the fact that the graph models now have access to more diverse structures in terms of popularity and local density, making decisions about unimportant and sparsely surrounded nodes remains to be as difficult as before.

Interestingly, the drop in predictive performance on the locality-based shift appears to be less significant compared to the original setup and reaches only 5% on average instead of the previous 15%. At the same time, the OOD detection performance on this structural shift drops to 78 points, whereas it was 85 points in the original setup. These results also match our intuition — as the distance between the ID and OOD nodes decreases, the OOD samples become less distinguishable from the ID ones. This makes the OOD detection performance drop on average, while the gap between ID and OOD metrics in standard node classification disappears.

Now we may compare the existing graph models based on the results in Table 2. As can be seen, the ranking of methods remains almost the same as in the original setup. Specifically, the most simple data augmentation technique Mixup often shows the best performance in OOD robustness, while DE provides the second best results on most structural shifts. As for OOD detection, the methods based on the entropy of predictive distribution again outperform the Dirichlet ones, and the uncertainty estimates produced by DE are best correlated with the OOD examples. Thus, our observations regarding the performance of graph models are consistent with those reported in the paper.

**Additional analysis**

As a response to Reviewer 2ynW, we have also conducted a brief analysis of distributional shift in feature space induced by the proposed structural shift. In particular, we used t-SNE to embed the original feature space of the considered graph datasets into 2D representation space. In Figure 1 of the attached PDF, one can see the examples of such a visualization for the locality-based structural shift that also creates a notable distributional shift in node features. It supports our reasoning in Appendix B that a realistic shift most commonly impacts both node features and graph structure. In the revised version of our paper, we will include the figures for other graph datasets and shifts.

**On submission track**

Several reviewers expressed their doubts about whether our work should be at the main conference track or at the Datasets and Benchmarks (DB) track. Let us explain our choice.

According to the DB track description, its main purpose is to present new datasets to the community, with a special focus on their maintenance and accessibility via a properly designed API. Among other things, a submission to the DB track requires the information about how the data is collected and organized, what kind of information it contains, how it should be used ethically and responsibly, etc. 

On the contrary, our work is about a new approach to induce structural distributional shifts that can be applied to any graph dataset. In other words, our work presents a way of looking at and dealing with data, rather than a new source of data. Further, according to the call for papers, our work fits the scope of the main track. It is written in the conference FAQ that if a paper fits both tracks, it remains the authors' choice where to submit it. Taking into account the above arguments, we decided to submit to the main track. 

**Broader impact**

As requested by the reviewers, we will add a discussion of broader impact to our paper. In particular, we assume that the proposed approach for evaluating robustness and uncertainty of graph models will support the development of more reliable systems based on machine learning. By testing on the presented structural shifts, it should be easier to detect various biases against under-represented groups that may have a negative impact on the resulting performance and interfere with fair decision-making.

Meta-review: This paper proposes a method for inducing structural distributional shifts that can be applied to graph datasets and help to explore robustness of various algorithms with respect to such shifts. The reviewers found the paper to be novel and interesting, with potential implications for research  studying the robustness of node prediction algorithms. While there were also some concerns such as the size of the graphs used in the experiments, the overall consensus was that the paper has sufficient value and should be accepted to the conference.
Decision: Accept (poster)