GraphDE: A Generative Framework for Debiased Learning and Out-of-Distribution Detection on Graphs
Authors: Zenan Li
Qitian Wu
Fan Nie
Junchi Yan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Data
Debiased Learning
OOD Detection.

Abstract: Despite the remarkable success of graph neural networks (GNNs) for graph representation learning, they are generally built on the (unreliable) i.i.d. assumption across training and testing data. However, real-world graph data are universally comprised of outliers in training set and out-of-distribution (OOD) testing samples from unseen domains, which solicits effective models for i) debiased learning and ii) OOD detection, towards general trustworthy purpose. In this paper, we first mathematically formulate the two challenging problems for graph data and take an initiative on tackling them under a unified probabilistic model. Specifically, we model the graph generative process to characterize the distribution shifts of graph data together with an additionally introduced latent environment variable as an indicator. We then define a variational distribution, i.e., a recognition model, to infer the environment during training of GNN. By instantiating the generative models as two-component mixtures, we derive a tractable learning objective and theoretically justify that the model can i) automatically identify and down-weight outliers in the training procedure, and ii) induce an effective OOD detector simultaneously. Experiments on diverse datasets with different types of OOD data prove that our model consistently outperforms strong baselines for both debiasing and OOD detection tasks. The source code has been made publicly available at https://github.com/Emiyalzn/GraphDE.

GraphDE: A Generative Framework for Debiased Learning and Out-of-Distribution Detection on Graphs
Zenan Li, Qitian Wu, Fan Nie, Junchi Yan'
Department of Computer Science and Engineering and MoE Key Lab of Artificial Intelligence
Shanghai Jiao Tong University {emiyali, echo740, youluo2001, yanjunchi edu.
Abstract
Despite the remarkable success graph neural networks (GNNs) for graph rep- resentation learning, they generally built on the (unreliable) i.id. assumption across training and testing data. However, real-world graph data are universally comprised of outliers in training and out-of-distribution (OOD) testing samples from unseen domains, which solicits effective models for i) debiased learning and ii) OOD detection, towards general trustworthy purpose. In this paper, first mathematically formulate the two challenging problems for graph data and take initiative on tackling them under unified probabilistic model. Specifically, we model the graph generative process to characterize the distribution shifts of graph data together with additionally introduced latent environment variable an indicator. We then define a variational distribution, i.e., recognition model, infer the environment during training of GNN. By instantiating the generative models as two-component mixtures, we derive tractable learning objective and theoretically justify that the model can automatically identify and doighteight outliers in the training procedure, and ii) induce an effective OOD detector si- multaneously. Experiments on diverse datasets with different types of OOD data prove that our model consistently outperforms strong baselines for both debiasing and OOD detection tasks. The source code has been made publicly available btttps://gttaie thub..ubbccc com
Introduction
For processing ubiquitous graph data, graph neural networks (GNNs) 17 43 have emerged as effective approaches for graph representation learning [12), which in turn has spanned wide range of applications, from drug discovery (3 to image classification 4
Despite their success, existing GNNs are generally built on the assumption that both training and testing data are independently sampled from the identical distribution (i.i.d.), which often does not hold [45] 22 49 [4].. Real-world training data is often shown universally mixed with outliers [30 7 which specifically may incur large gradient steps in the wrong direction (38), or be overfitted by the model (3. thereby hurting models' performance. Besides, testing samples from unseen domains are also unavoidable when the model is deployed in the wild 19), which may easily be classified into wrong class with high probability [3] Inevitably, graph data also involve these two common problems. As illustrated in Fig. []] we indeed find that vanilla GNNs perform poorly when encountering large portion of outliers and nut-oo-distributiin (OOD) testing samples, which solicits effective models for i) debiased learning and ii) OOD detection, towards general trustworthy purpose.
'Junchi Yan is the corresponding author who is also with Shanghai Al Laboratory.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Max Softmax Score
Variiiioaal Inferred Score
Accuracy (%)
30
Frenusncyy
Frecuency
70
0.05
GOD Score.]
000 Soore.
Biased
Ratio
(a) Debiasing results on SPMotif
(b) Detection results on MNIST-75sp
Figure I: Vanilla GNNs' performance degenerates drastically with a larger number of outliers in the training dataset. They also assign high softmax scores to OOD data, which may raise trustworthy concerns. In comparison, our proposed framework can boost performance for both tasks notably. In (a), GraphDE-a is plugged in the backbone; In (b), the variational inferred score is derived from GraphDE's is recognition model. We plot MNIST images at corresponding OOD scores for intuition.
However, these two problems still remain less explored for graph data. Generally, identifying graph outliers (or OOD samples) is inherently hard as the Euclidean graph data can own large number of node features and additional structural knowledge. The bias may exist in certain node features, local and global graph structures (29). as well as the underlying relations between features, structures, and labels (38], preventing trivial applications of traditional machine learning methods [25 from identifying outliers on graph data.
We argue that training outliers and OOD testing samples can be conceptually unified as they both represent data drawn from distributions other than the major in-distribution (ID) part of training data. However, they inherently different as the training outliers also catch label-related distribution shifts, e.g. noisy labels M. while OOD testing samples are solely determined by their features [14] since we cannot access their ground- -trtthhh labels. This difference also explains why many existing works tend to tackle the two problems independently.
In light of the intrinsic connection between these types of data, we present GraphDE, prob- abilistic generative framework for Graph DEbiased learning and OOD DEtection. Specifically, model the generative process to characterize the distribution shifts of graph data, along with an environment variable as an indicator. Utilizing variational inference [51] we propose to infer the environment variable during the training procedure of GNN. Our framework consists of three modules: the recognition model that infers the environment variable based on the input graph data; the structure estimation model by which extract OOD detector on testing dataset; the classification model which is our target GNN. Following the idea of data resampling [38 37), we model the latter two modules by two-component mixtures, with one component for ID data, and the other component robustifying the model by isolating outliers. Based on this, we derive tractable learning objective for our model and theoretically justify its effectiveness for the target tasks. The contributions are:
We focus on two critical but largely unexplored problems for graph data: debiased learning and OOD detection, find their fundamental correlations and define them under probabilistic framework.
We propose GraphDE with a novel learning objective and theoretically justify that: 1) it can identify and down-weight outliers during training; 2) it can provide OOD detector the testing set; 3) its constituent modules are optimized a
manner.
We evaluate GraphDE with different GNN backbones on diverse datasets of different OOD types, where GraphDE achieves consistent performance improvements over the baselines. Specifically, as shown in Fig. for the debiasing task, it yields up to 14.6% accuracy improvement on SPMotif; for the OOD detection task, outperforms the strongest baseline by 9.31 3.31% % on MNIST-75sp.
Problem Formulation and Related Works
In typical graph learning problems, given set of labeled graphs D [(Gr, N
need to train a model fo G -> ý to predict the labels on the testing dataset Die = [G. 1 Specifically, the input graph G (A, X) is composed of an adjacency matrix A {avalv, E VJ and node features

---

= f V), where V is the node set. Define G as random variable of the input graph and y as a random variable of the graph label, the data-generating process can then be characterized as p yle) = p(G (()))((( G, e) where we introduce an environment variable as a potential unknown indicator for data from particular distributions.
The biased data (we use the form interchangeable to outliers) in the training set and out-of- -istriibuitt (OOD) data in the testing set can both be treated as data drawn from different distributions to the distribution generating the majority of the training set and testing data of our interests, i.e., the in-distribution (ID) data so-called. Hence, we can model them by a binary environment variable e, with e = 1 denoting the ID portion and e = 0 for the biased/OOD portion. Then the training and testing datasets can be split into D'r D U Duut and D D U Dout accordingly. Note that i) the partitions of training/testinng data are only for illustration purpose and are strictly unknown in practice; ii) the testing data and distribution are also strietly unknown during the training process; iii) here e is mainly used for distinguishing the ID part with the OOD counterpart of datasets. In fact, the OOD part (e = 0) may consist of data from multiple distributions
Denote the loss on sample (G, y) by Ly, fo(G)), e.g., cross-entropy loss for classification problems. Then the standard empirical risk minimization (ERM) objective can be written
min Ens((e)
Ly. (L..
This objective works based on the i.i.d. assumption across training and testing data. As we aim at promoting the ID test aceuracy (i.e. the performance on D(s), however, the updating gradient by training data drawn from p( yle = 0) will hurt model performance drastically [3] On the other hand, for testing data from unseen distributions Dég the model would incline to produce imprecise results as (c) & Pout (e), which is undesired and should be avoided for the trustworthy purpose. We next formulate the two problems of our interests.
Task I: Debiased learning for training data. The target is to mitigate outliers' negative effects during training, thereby enhancing the performance ID testing data. We modify the ERM objective:
min Bewn(a)
I4 fa [C]))e)).
(2)
L(y. (G)), Lo.
e =
1,
where Lyy, fo(G))e)
where the loss function for biased training data fixed as Lo. so the debiasing objective is equivalent to minimize B(G.)))(GG.yle=)
[o(G) i.e., the training loss for the II) portion Dir
Task I: OOD detection for testing data. We aim to obtain an OOD detector g composed of trained model fe G - J. a scoring function s and a threshold T:
0 (OOD), if fo) ST. T, {
(3)
(ID). if: >T.
As we are willing to induce an OOD detector during the training procedure of GraphDE, we leverage the trained model fe from task I and what need is to find the optimal score function s" that can best separate out ID and OOD data (c.g. maximize the AUROC).
Related works on debiased learning. A series of strategies have been proposed to debias the training dataset in general machine learning [88 5 and computer vision 30 77. Many works propose to preprocess the dataset by filtering out the outliers
[5] 25). However, these methods cannot capture label-related distribution variations such as noisy labels II and also cannot be easily adapted to deal with graph data. Another popular strategy is data resampling [38 37), which relies on the training loss to identify and down-weight outliers in the training set. However, these methods only capture bias in the mapping from features to labels, but ignore the variation in feature space. For the first time to our best knowledge, we formally define and deal with the graph debiased learning problem.
Related works on OOD detection. A trustworthy learning system should not only produce accurate predictions for ID data, but also distinguish and reject OOD examples without further prediction.
2 "Since we are not interested in the specific OOD distributions. we model them by a unified distribution y/e yle 0). which is enough to identify the OOD samples we will justify later.
3

---

Pin
Training Stage
Testing Stage
Der x.
Becognition Model
muturally
Recognition Model (e A.le),A,.yy y,y)
Dee (A.X)
(o y.
boust
1) D
inferred
computed
De
Glasttication Model
Structure Estimation
Ulestiication Model Pe(y X. n) ID: Doly A, X)
Stracture Extination Ps e,
Poly/A, A, X,o)
Generative Models
(A e)
ID: (plyyl,,X) X) 00D:ooyVAA.X)
Po(A
Generative Models
ID: Po(A
OOD: PA(A
00D:
OOD: p=(A
infer pa(yl4,
infor (e A)
Cota
+
Cki
Freg C
During the training stage, the training data is fed into the recognition model to infer the environment variable, then fed into the generative models to compute the total loss for training (we omit the source of Lu in the figure for simplicity). Right: In the testing stage, the testing data is fed into the structure estimation model for OOD detection, then fed into the classification model to compute the class probabilities.
Figure 2: The proposed GraphDE framework. Left:
Deep learning based OOD detection has achieved promising progress in vision 127 13 Besides, node and edge-level anomaly detection on graphs are also widely studied, some of which are based
on classical network science (26), while others utilize the power of GNNs [36] 9 In comparison,
only limited works [52 (29 attempt solve graph-level OOD detection. Specifically, OCGIN (52)
designs one-class GNN objective to distinguish between ID and OOD data. GLocalKD 22 utilizes joint random distillation of graph and node representations to learn rich global and local pattern information of graph-structured data. However, both of them need to be trained individually for the detection task. In this paper, we extract an OOD detector during the training procedure of the target GNN, while outperforming all the baselines on 7 out of 9 benchmarks. Appendix B gives more comprehensive description on related works on GNNs and Trustworthy GNNs.
Methodology
3.1 Probabilistic Generative Learning for Debiased Learning and OOD Detection
To improve the ID test accuracy, we want to make the model more robust by automatically identifying potential outliers during training. Thus, we take generative perspective on the graph data and adopt variational inference to infer the environment variable during training.
Generative Process. We model the joint distribution p(X, y, A, e) to capture graph-level distribution shifts. line with the homophily principle from random graph theory B33, i.e., linking probability depends on some inherent properties of nodes, we assume that the graph structure is generated based on the node features and the environment variable. The graph labels are then generated based on the graph structure, node features, and the environment. We also assume p(e) and p(X) to be
independent distributions for environments and node features, respectively. We do not specify the
form of p( (X), since everything will be conditioned on X in this paper, similar to 28 44
We have:
(, e) = p(e)p(X) (X)))(X))(AA ((A/X, e)p(y
(4)
where the generative models p(A e) and p(y X A, e) could be modeled by some flexible para- metric distributions Po (A|X, e) and pe ( A, e) with parameter 6. These two distributions will later be instantiated as the structure estimation model and classification model, respectively. We define the generative models with two-component mixtures. For example, pe (A())) | e) composed of an ID component po A)), and an OOD component po (A|X) (the subscript Ó implies a fixed distribution). The environment variable e {0. 1} indicates whether the graph should be modeled by the ID (e = 1) or the OOD (e = 0) component. Specifically, these two terms are decomposed as:
Po (A c) = po X (A 1-c
(5)
pa ( A, e) = Pe ( X, A) A) X, 1

---

Recognition Model. As the variables X, A and y are all observed during training, what we need is infer the sample-wise environment variable e conditional on these observed variables. Thus, we resort to variational inference [51] and introduce recognition model go(e|A, A, x, parameterized with & to approximate the true posterior po y
Learning Objective. We train the model parameters 0 and @ by optimizing the Evidence Lower BOund (ELBO) of the observed data tuple (A, X,,x,))) y):
log (A,, x|x) 2 log po (A, y XX-
(e|A, y)]
= -Bng (e)A,
-xx (e x. v)llp(e]] LELBO
Eq. 6 shows that by maximizing the ELBO, we are maximizing the log- oogliikelhoood of observed data log Po A. yl X) while minimizing the KL divergence between the recognition model and the true posterior Po (, X,y) y). Finally, the learning objective for the training dataset can be written as:
Ndr
B gole (...). (e, lo X,, A.) + e1) log A.)
Classification Loss Ceta
N
E (e, log + (Ag
Ntr
Structure Regularization Loss Erey
N
DKL A, U.Ull(((()
Ntr
KL Loss Cei
Justification of GraphDE. We provide theoretical analysis here to reveal the rationale of GraphDE. Without loss of generality, do not take account into the KI. loss here for simplicity. The proofs of the propositions are postponed to Appendix A
Proposition 1. 1) The learning objective for GraphDE is in a re-weighted form when go (elA,, X, y) instantiated as a Bernoulli distribution, with go 1| X1, 3k) acting as weight for the i-th sample; 2) Given the ideal recognition model os that gives g (e = 1I(A, X, y) E Dnn) 1 and (e 11(A, E Dowt) = 0, the generative models can learn to best fit the ID data.
Prop. T reveals how the inferred posterior takes effect on the learning objective. Typically, if as (e) A, X. y) can assign a higher probability ID data, our model can thereby learn ignore the negative effects of biased training data and better fit the target distribution (i.e. ID).
Proposition 2. 1) Assuming the generative models fit to the ID data, i.e. Pe(A[X E Din) > Po(A|X Dont) and po(y) (A, X) E Din) 2 Po (A X) D Dont), the recognition model will Doutt;; ; 2) Given optimal generative models that best fit the ID data and perform randomly on outliers, there exists recognition model 9 which yields the minimal objective while ideally predict the environment variable.
learn to predict ç = 1|( X, E Din) lo (A,
Prop. proves GraphDE's effectiveness from the recognition model's perspective. To summarize, the above two propositions show that go(e) A, X, yo A,X) and po [A|X) can mutually promote each other during training. As deep networks tend to learn simple shared (i.e. ID) patterns first (3) this positive feedback can guide GraphDE to identify outliers in early epochs and thereby learn better representations of ID data. Besides, the propositions also suggest that given either of the recognition model or the generative model optimal, the other can be trained to be optimal, which suggests the existence of the global optimum. Based on these, we can further understand the implications of the three loss terms in Eq. 7 i) Cats is the re- re-whighted version of the original classification loss; ii) Lreg acts graph regularization and will impact the gradient of qa (c A, X. y), weighting ID data higher than the outliers; iii) the third term Lx is the KL divergence between the learned posterior and the fixed prior distribution, ensuring the posterior not go too complex.
Inference on Testing Dataset. For new data, we need to infer the posterior conditional distribution of e and y given (A, X), i.c. po(e) A, X) and pe (y) J,, X), respectively. To compute pe pe(e) A, X) is
5

---

just to do OOD detection. For binary e, we can compute its posterior analytically:
A, (e,
ple) (A e)
(8)
E. po e)
The posterior can be used as the score function s for the OOD detector, once we have the well-trained (A e). Subsequently, we can calculate pe(y (y Ly|A,, X) by the total probability theorem:
pa pa Epo(ylA,.,eeppoeelll
(9)
where (y A, e) can also be obtained after training.
3.2
GraphDE Instantiations
We proceed to specify the distributions po (A e). p A, e). p(e) and go x,y) We assume p(e) Bernoulli(a) where E [0, 1] represents our prior belief about the cleanliness of the dataset. higher a implies a larger portion of ID data in D'r, It is fixed as a scalar during training.
3.2.1 Instantiations of the Recognition Model
We propose two variants for the recognition model 4s X,, In the first way, directly assign a learnable scalar for each sample in the training dataset, i.c., 96 (e, X,, y4) = Bernoulli(a;)) where a; E [0, 1] is trainable parameter jointly optimized with generative models through the ELBO in 7 7 We call this variant GraphDEE-varriaionna) as we optimize directly over og, In the second way, notice that is binary variable by definition, we can compute the posterior analytically by
po Px y. A, e)
go(elA, = po(elA.
E.po X e) (A) P.
(10)
e)
c)
We call this variant GraphDE-a(nallticaa) and the optimization procedure in this setting is essentially an EM algorithm [1]: in the E-step, we evaluate the posterior distribution of the latent variable by Eq. TO in the M-step, optimize the model parameters using gradient descent w.r.t. the objective in Eq. In comparison, GraphDE-v runs more efficiently as it does not need to calculate the posterior, while GraphDE-a can give tight approximation log po x LELBO. We compare the space/time complexity of the algorithms in Appendix F33
3.2.2 Instantiations of the Structure Estimation Model
Recall that (a(A XX, is defined by two-component mixture (Eq. 5), we need specify po (A X) and po (A|A separately for the structure estimation model. We follow the common practice and assume that the edges are conditionally independent (28.. Then the conditional probability of A can be further factorized as (A) = II Pa (a.a X).
We next consider two versions for pa(a.u) X). First, we adopt the latent space models (LSM) 15 where the probability of a only depends the representations of nodes and w:
(a 1 x,, x..) (((Ux.))
(Ux..) [w)
(11)
Eq. 11 can be viewed as logistic regression model where o(-) denotes the Sigmoid function, Us linear transformation matrix, and w is learnable vector.
Second, we propose variant of LSM referred as CosLSM which utilizes the cosine similarity function to measure the similarity between the node representation pair (x,, x.):
m cos (U,x,, U.x.) +1
Po (ava 1/x,, X.
(12)
m
where we harness meati-head linear transformations {U.),, for better capacity. Note that if we train the structure estimation model completely based on the observed edges, the model will yield

---

trivial solutions which predict all edges' probabilities as 1. To avoid this issue, we randomly sample one disconnected node pair labeled as avu = for each existing edge during training.
Finally, for (a we simply fix it as po = 1 = 1/2. Although more complex distributions be used for improving the capacity, our experiment results empirically show that this simple distribution is enough for wide range of debiasing and detection tasks on graphs.
3.2.3 Instantiations of the Classification Model
We next specify (y A, X) and (y)A X) for the classification model. Similar to the structure where K denotes the total number of classes. Typically,
estimation model, we fix (o A X) = =
GNN takes (A, X) as input and outputs the probability of y. So for pe (y|A,X) we adopt two types of GNN models: the global pooling models [37.3] and hierarchical pooling models [21 18]
Denote node v's neighborhoods by Ny: specifically, common GNN convolutional layers execute
recursive feature propagation along G:
x!) =
x =X,
(13)
where (()) denotes weight matrix in the I-th layer and AGG is wewputatioonnnne invarrinn function that aggregates node representations. hierarchical pooling GNNs, each convolutional layer is followed by pooling layer to filter out nodes for the next convolution operation:
(14)
ids,
where idx is the selected node indices obtained by operations such as selecting the top-k score (calculated by a learnable function) nodes. Finally, for both types of GNNs, global pooling layer (e.g. max or mean operation over node features) is adopted to extract graph-level representation h to be fed into the classifier whose probability obtained by an output softmax layer:
pe ( A, X) = Softmax(*(h)) h GlobalPool(X("))
(15)
where n denotes the total number of convolutional layers.
4 Experiments
In this section, we conduct extensive experiments to answer the following questions:
Q1: How effective is GraphDE in debiased learning and OOD detection?
Q2: How do the composed modules and hyperparameters impact GraphDE's performance? Besides, how does GraphDE take effect during the training procedure?
4.1 Experiment Setup
Datasets. One synthetic and three real-world datasets of different OOD types are used for debiasing and OOD detection tasks. Here we briefly introduce them, leaving details of statisties to Appendix E
Spurious-Motif [50 (SPMotif) is synthetic dataset in which each graph is composed of one base (denoted by S) and one motif (denoted by C). The graph label y is solely determined by the motif C. To simulate distribution shifts, we manually construct spurious correlations between S' and y. We use datasets with different spurious correlations to represent ID and OOD data, respectively. This dataset is unsuitable for typical OOD detection task, as the distribution shift is dominated by label information, opposed to that the OOD detectors focus on detecting input graphs with abnormal structures or node features.
MNIST-75sp
[8] converts the MNIST images into super-pixel graphs with at most 75 nodes. For OOD data, we add Gaussian noise to node features to simulate distribution shift.
Collab 47 is social network derived from 3 public collaboration datasets. We use the graph size to simulate distribution shift, with graphs of no more than 45 nodes denoted as ID data. DrugOOD [6] aims to benchmark the OOD generalization performance in the field of Al-aided drug discovery. We use the provided dataset curator to generate a dataset with different scaffolds, and treat the largest 6000 molecules ID data.
7

---

6CN
GAT
TopkPPol
SAGPool
Dropedge
Grand
GraphDE-v
GraphDC-a
MNIST-75sp
Collab
Drugood
80
Teat Accuracy
Test Accuracy
Test AUROC
70
65
75
60
50
65
0.2 Blased Ratio
0.1
0.3
0.0
0.1
0.1
0.2
0.3
Blased Ratio
Blased Ratio
Figure 3: Debiasing results on real-world datasets. The test mean accuracy (or AUROC for DrugOOD)
on the ID dataset is plotted. GAT is adopted as the backbone.
Table 1: Debiasing results SPMotif. It records the test mean accuracy and standard deviation on the ID dataset. The biased ratio is fixed as 10% for fair comparison. Best results are in bold.
Model
Backbone
DropEdge
GRAND
GraphDE-v
GraphDE-a
GCN
17
68.67:15.04
65.5943.116
73.92+3.37
75.10:33.36
7..59:
GAT
43
65.02+33.1
62.81
65.27+3.90
66.88+1.38
6.85
Topk 18
78.43+44.93 8..32+3.85
83.25+3.89
85.11+4.42
18,54+1.772
SAGPool
21
83.57+4.15
85.72+3.15
86.71+3.49
28696+22.66
89.41+22.77
Note that during the debiased training stage of GraphDE, we need to mixed a certain number of OOD data into the training dataset. To prevent potential data leakage [14] during the evaluation of OOD detection, the OOD testing dataset should be drawn from different distribution w.r.t. the OOD data mixed into the training dataset. We denote these two sources of OOD data as the OOD testing dataset and the OOD mixed dataset, respectively. We leave more details of dataset splits to Appendix B
GNN backbones. We adopt two types of GNN backbones for debiasing and OOD detection tasks.
To extract the global graph representation for graph classification, we use global mean pooling or global max pooling layer after the GNNs to summarize the node representations.
Global pooling backbones. We adopt two popular GNNs: GCN 17 and GAT 4%
Hierarchical pooling backbones. This architecture is comprised of blocks each of which consists of graph convolutional layer and pooling layer. Typically, TopKPool [18] selects local parts of input graph for propagation by a learnable score function; SAGPool [2]] uses the self-attention mechanism to calculate attention scores, and retain important nodes for propagation.
Debiasing settings. For the debiasing task, we mix the training set with certain ratio of outliers and compare models' performance on ID testing data. We evaluate GraphDE's debiasing performance on the four datasets. Besides, As far as we know, there are little existing works concerning debiased learning on graph data. For demonstrating the empirical superiority of our approach, we adopt two recently proposed methods that claim to enhance the general-purposs robustness of GNNs as competitors: DropFige (39] randomly removes number of edges from the input graph in each training epoch, and GRAND 11 uses random propagation strategy to perform graph augmentation. We study the negative effect of outliers by varying the biased ratio (DD / (DD")) |) of training data.
OOD detection settings. We evaluate GraphDE's OOD detection performance on three real-world datasets (with equal number of ID and OOD testing samples), using three widely used metrics [14] area under the receiver operating characteristic curve (AUROC), area under the precision- recall curve (AUPR), and the false positive rate at 95% true positive rate (FPR95). Besides, we consider three types of baselines: first, we use the backbones' max softmax score (MSP) [ as vanilla baseline; second, we adopt two-stage graph kernel baselines in [52] (specifically, we adopt WI. [4) and PK [34
kernels, LOF 5S) and OCSVM (6) detectors); finally, we use OCGIN 52 and GLocclII
29 as two
deep learning based detection baselines.
Notably, they can also be integrated with GraphDE to achieve even better debiasing performance.
8

---

Table 2: Detection results on real-world datasets. The biased ratio is fixed as 30% for fair comparison. We report the mean and standard deviation for all the detectors, except the two-stage models, which are invariant to different random seeds. We use the GraphDE-a variant as the OOD detector.
OOD Detector
AUROCT
MNIST-75<p AUPRI
[PR951
AUROCT
Collab AUPR
FPR95]
AUROCT
DrugOOD AUPR1
FPR9E1
MSP B
62.3742.96
60.71
88.6042.71
51,3744.24
53.1943.68
91,0042.41
54.5749.18
52.43=6.85
90.76=4..55
-OCSVM
75.35
32.75
60.39
64.80
6684
57.22
67.72
81.40
56.21
49.31
PK
HOCSVM 6
72.26
59,95
47.80
61.57
62.19
70.60
66.08
61.02
$2.60
PK
14 +LOF
X
61.19
$8.51
92.55
64.25
58.76
91.20
$7.40
$1.42
$8.20
OCGIN [5
65:07:12.55
60, 13:2.4
77.59:55.55
70.4812.72
71.77.11.84
86 16.7010.71
68. 39:14.777
66.05-5111
$2.50-7.500
GLoczlKD
29
86,2240.78
87.5920.87
25.7245.90
71.8240.47
72.9110.24
70,042:.322
63.42.0.60
58 58.03=0..44
70.28-1833
GraphDi:
95.53:3363
94.78:5.09
19.24:9.33
72.15
71.8632.54
64.40:10.41
69.15:1.111
67.40=0.51
50:30:0033
4.2
Main Results (Q1)
We train and evaluate each model under the settings as described in the last section (more hyperparam- eter and training/testing details in Appendix D). All the experiments are run over 5 different random seeds. More experimental results can be found in Appendix We make the following observations:
Debiasing results. Tab. reports GraphDE's debiasing performance on SPMotif. In this setting, we treat the robust GNN baselines and two variants of our GraphDE as plug-in modules and apply them to all the four backbones for comparison. The results show that GraphDE consistently (for all the backbones) outperforms the baselines by large margin along with low variance. Specifically, for the TopKPool backbone, GraphDE-a a surpasses the backbone by 10.11% 1% and the strongest baseline (GRAND) by 5.29%. Such improvements strongly suggest that GraphDE can achieve better debiasing performance for various backbones. Besides, the results also show that the GraphDE-a generally outperforms GraphDE-v, as the EM algorithm can give a tight approximation for the log- ligliioll
Fig. 3 iillusrrttes GraphDE's s performance on three real-world datasets. In this setting, we mainly study the debiasing performance w.r.t. different biased ratios, so the backbone for robust GNN baselines and GraphDE are all fixed as GAT. As shown in the figure, GraphDE consistently outperforms baselines on the three datasets for all the biased ratios. The backbones' performance drops drastically as the biased ratio gets higher, and the robust GNN baselines can mitigate this effect to some extend. In comparison, GraphDE performs much more stable. This advantage more pronounced when the biased ratio is large, c.g. GraphDE surpasses all the other baselines by nearly 5% on Collab when the biased ratio is 0.2. An interesting observation is that GraphDE can also achieve better test accuracy when the biased ratio is O, implying that the pure training set also violates the i.i.d. assumption.
Detection results. Tab. reports GraphDE's detection performance three real-world datasets. As can be seen from the table, the max softmax score (MSP) achieves low detection performance. It suggests that vanilla GNNs are poorly calibrated (35] and it is of critical need to develop new graph- level OOD detectors. The results show that GraphDE performs the best on 7 out of 9 benchmarks. Specifically, on MNIST-75sp. GraphDE surpasses the strongest bascline by approximately 10% for AUROC, while also pulls down the false positive rate (FPR95).
4.3 Further Study (Q2)
Impact of prior ratio. We select different prior ratios - p(e) to study its impact debiasing performance. As shown in the Fig. 4Aa), the ID test accuracy doesn't fluctuate much from 0.05 to 0.7, but drops drastically when prior ratio goes higher than 0.7. Besides, we also find that the test accuracy peaks at prior ratio 0.1 for biased ratio 0. and 0.2 for biased ratio 0.2, exactly when Lat becomes 0.
Ablation on Creg- We remove Lrey in the objective to study the structure estimation model's impact on debiasing performance. As illustrated in Fig. 4bb] we can find that the test accuracy drops obviously at all biased ratios. Specifically, The test accuracy drops over 6% at biased ratio 0.25. The results prove the structure estimation model's 's capability of doin-weighting outliers in training data.
Ablation on Cets. We remove Lete to study the influence of the classification model on the OOD detection performance. As shown in Fig. 4 we plot the detection AUROC on the testing dataset w.r.t. different biased ratios. The figure illustrates that the AUROC generally drops as the biased ratio gets higher, since the outliers will hurt the fitting performance of the structure estimation model. Typically, can see that the blue line (without Lats) is consistently lower than the red line, with the
9

---

Delection AuccionnURRO AUROG
80
Test Accuracy
Test Accuracy
84
62
70
Slored rabo
0:10
Prior Ratio
Biased Ratio
Biased Ratio
(a) Prior Ratio
(b) Structure Estimation Model
(c) Classification Model
Figure 4: Sensitivity analysis and ablation studies (on Collab). We use the GraphDE-a variant.
SPMottf
DrugOOD
SPMott
Drugood
Test AUROCU
Frequency
8
6A 3.6
-02 30
24
Vi Probabilty Score wu Ground Truth
VI Probab itty Score wi Ground butth
(a) Training Procedure
(h) OOD Score Distribution
Figure 5: Explanatory experiments. We use the GraphDF-a variant and the biased ratio is set as 0.2.
gap getting larger as the biased ratio goes higher. Specifically, the performance gap is approximately 3% when biased ratio 0.3. The results prove that the classification model can help wweigtt training outliers, thereby promoting the detection performance of the structure estimation model.
Training procedure. We plot GraphDE's s test accuracy after every training epoch ID and OOD (i.i.d. to training outliers) datasets. As shown in Fig. 5(a) the ID test accuracy simply fluctuates, rises, and converges. In comparison, the trend of OOD test accuracy separated by the green dashed line, we can see the red line first increases then decreases. Generally, in the increasing phase, GraphDE optimized to better fit the outliers in the training data. However, in the decreasing phase, as the outliers are down-weighted by a large extend, GraphDE focuses on fitting ID data. This transition prevents overfitting of outliers and promotes the ID test accuracy.
be divided into two phases. As
Visualization of inferred probability. We visualize the recognition model's ' inferred probability 9s(e 1 X, the training dataset. As shown in Fig, 5(b) ID data is assigned with higher probability on both datasets. In particular, most outliers are assigned with probability at around on SPMotif. This directly indicates that the outliers down-weighted during the training procedure.
Conclusion and Outlook
In this paper, we have provided a viable approach to the problem of debiased learning and OOD detection over graph data. Specifically, generative process is modeled capture distribution shifts of graph data. By introducing a variational recognition model to infer the environment variable and two-component mixed generative models, the learning objective for GraphDE derived, which can identify and down-weight outliers during training, as well as inducing an effective OOD detector on new data. While our framework is mainly designed for graph data where both the debiased learning and OOD detection remain relatively under-explored, it can be potentially generalized to other data formats like images or texts, which we leave for future studies.
Acknowledgement
This work was partly supported by National Key Research and Development Program of China A2100A,0) National Natural Science Foundation of China (61972250, 7206 127003), and Shanghai Municipal Science and Technology (Major) Project SHZDZXX01,,, 2251 1005100).
10

---

References
[1] G. Algan and Ulusoy. Label noise types and their effects on deep learning. CoRR, 104/2, 2020.
[2] M. Arjovsky. L. Bottou, I. Gulrajani, and D. Lopez- Paz. Invariant risk minimization. arXiv preprint 190.02297, 2019.
[3] D. Arpit, S. Jastrzæbski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, T. Maharaj, A. Fischer,
A. Courville, Y. Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pages 233-242. PMLR, 2017.
[4] P. H. Avelar, A. R. Tavares, T. L. da Silveira, C. R. Jung, and L. C. Lamb. Superpixel image classification with graph attention networks. In 2020 33rd SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), pages 203-209. IEEE, 2020.
[5] M. M. Breunig, H.-P. Kriegel, R. T. Ng. and J. Sander. Lof: identifying density- -bated local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93-104, 2000.
[6] Y. Chen, X. S. Zhou, and T. S. Huang. One-class svm for learning in image retrieval. In Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205), volume 1, pages 34-37. IEEE, 2001.
[7] T.-J. Chin, Z. Cai, and F. Neumann. Robust fitting in computer vision: Easy hard? In Proceedings of the European Conference on Computer Vision (ECCV), pages 701-716, 2018.
[8] E. Dai, W. JIN H. Liu, and S. Wang. Towards robust graph neural networks for noisy graphs with sparse labels, 2022.
[9] D. Duan, L. Tong. Y. J. for anomalous link detection. In 2020 IEEE International Conference on Data Mining (ICDM), pages 1002-1007. IEEE, 2020.
J. Lu, L. Shi, and C. Zhang. Aane: Anomaly aware network embedding
[10] Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv: 2019.
[11] W. Feng, J. Zhang, Y. Dong, Y. Han, H. Luan, Q. Xu, Q. Yang, E. Kharlamov, and J. Tang. Graph random neural network for semi-supervised learning on graphs, 2020.
[12] W. L. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv: 1rXiv:/709.05584 2017.
[13] D. Hendrycks and K. Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. 2016.
[14] D. Hendrycks, M. Mazeika, and T. Dictterich. Deep anomaly detection with outlier exposure. arXiv preprint #rXiv:1812.04600 2018.
[15] P. D. Hoff, A. E. Raftery, and M. S. Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 109000))090-1000 2002.
[16] Y. Ji, L. Zhang, J. Wu, B. Wu, L.-K. Huang. T. Xu, Y. Rong. L. Li, J. Ren, D. Xue, et al. Drugood: cat-of-distribution (ood) dataset curator and benchmark for ai-aided drug discovery-a focus on affinity prediction problems with noise annotations. arXiv preprint arXiv:2201.00 09637, 2022.
[17] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[18] B. Knyazev, G. W. Taylor, and M. Amer. Understanding attention and generalization in graph neural networks, 2019.
[19] 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 Machine Learning, pages 5815-5826. PMLR, 2021.

---

[20] D. Lan, X. Yang, Q. Wu, and J. Yan. Variational inference for training graph neural networks in low-data regime through joint crructure-labl estimation. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages $24-834, 2022.
[21] Lee, Lee, and J. Kang. Self-attention graph pooling, 2019.
[22] H. Li, X. Wang, Z. Zhang, and W. Zhu, Ood-gnn: Out-of-distribution generalized graph neural network, 2021.
[23] J. Li, D. Cai, and X. He. Learning graph-level representation for drug discovery. arXiv preprint arXiv:1709.03741, 2017.
[24] D. Liben-Nowell and J. Kleinberg. The link- predictiion problem for social networks. Journal of the American society for information science and technology. 58(7):1019-103) 2007.
[25] T. Liu, K. M. Ting, and Z.-H. Zhou. Isolation forest. 2008 eighth ieee international conference data mining, pages 413-422. IEEE, 2008
[26] N. Liu, X. Huang, and X. Hu. Accelerated local anomaly detection via resolving attributed networks. In IJCAI, pages 2337-2344 2017.
[27] W. Liu, X. Wang, Owens, and Y. Li. Energy- based out-of-distribution detection. Advances in Neural Information Processing Systems, 33:21464 21475, 2020.
[28] Ma, W. Tang, J. Zhu, and Q Mei. A flexible generative framework for graph-based semi- supervised learning. Advances in Neural Information Processing Systems, 32, 2019.
[29] R. Ma, G. Pang, L. Chen, and A. den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, ACM, feb 2022.
[30] H. Masnadi-Shirazi, V. Mahadevan, and N. Vasconcelos. On the design of robust classifiers for computer vision. In 2010 IEEE Computer Society Conference Computer Vision and Pattern Recognition, pages 779-786. IEEE, 2010.
[31] G. J. McLachlan and T. Krishnan. The EM algorithm and extensions, volume 382. John Wiley Sons, 2007.
[32] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. CoRR, aws/aabsssooe 100.02244 2018.
[33] B. Müller, J. Reinhardt, and M. Strickland. Neural networks: an introduction. Springer Science & Business Media, 1995.
[34] M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102()):209-2)) -2500 2016.
[35] Nixon, M. W. Dusenberry, L. Zhang, G. Jerfel, and D. Tran. Measuring calibration in deep learning. In CVPR Workshops, volume 2, 2019.
[36] 7.. Peng, M. Luo, J. Li, I.. Xue, and Q. Zheng. deep multi-view framework for anomaly detection on attributed networks. IEEE Transactions on Knowledge and Data Engineering, 2020.
[37] S. Reed, H. Lee, D. Anguelov, C. Szegedy, D. Erhan, and A. Rabinovich. Training deep neural networks noisy labels with bootstrapping. arXiv preprint arXiv: 2014.
[38] M. Ren, W. Zeng, B. Yang, and R. Urtasun. Learning to reweight examples for robust deep learning. In International conference machine learning, pages 1334-43433 PMLR, 2018.
[39] Y. Rong, W. Huang, Xu, and Huang. Dropedge: Towards deep graph convolutional networks node classification, 2019.
12

---

[40] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weiseeiler-ehmann graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[41] Y. Sun, S. Wang, X. Tang, T.-Y. Hsieh, and 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.
[42] A. Vaswani, Shazeer, N. Parmar, Uszkoreit, L. Jones, N. Gomez, Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[43] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks, 2017.
[44] H. Wang, C. Zhou, X. Chen, J. Wu, S. Pan, and J. Wang. Graph stochastic neural networks for semi-supervised learning. Advances in Neural Information Processing Systems, 33:19839- 19848, 2020.
[45] Q. Wu, H. Zhang, J. Yan, and D. Wipf. Handling distribution shifts graphs: An invariance perspective. In International Conference on Learning Representations, 2022.
[46] K. Xu, W. Hu, J. Leskovee, and Jegelka. How powerful are graph neural networks? CoRR, abs/18 110.008866, 2018.
[47] P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[48] C. Yang, Q. Wu, Q. Wen, Z. L. Sun, and J. Yan. Towards out-of-distribution sequential event prediction: causal treatment. In Advances in Neural Information Processing Systems, 2022.
[49] N. Yang, K. Zeng, Q. Wu, X. Jia, and Yan. Learning substructure invariance for out-of- distribution molecular representations, In Advances in Neural Information Processing Systems, 2022.
[50] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec. Gnnexplainer: Generating expla- nations for graph neural networks. Advances neural information processing systems, 32, 2019.
[51] C. Zhang, J. Bütepage. H. Kjellström, and S. Mandt. Advances in variational inference. IEEE transactions on pattern analysis and machine intelligence, 41(8):2008-2022 2018.
[52] L. Zhao and L. Akoglu. On using classification datasets evaluate graph-level outlier detection: Peculiar observations and new insights, 2020.
[53] D. Zügner, A. Akbarnejad, and S. Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &amp Data Mining. ACM, jul 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix G
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
13

---

(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] See Appendix D for dataset information. See the supplementary for the codes. They will be released public upon publication.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix D and Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See experiment section.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix [
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix B
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ZSSxDGr3FGT", "reviewer": "Reviewer_bxvk", "summary": "In this work the authors propose a method for jointly addressing outliers present in training data as well as learning an OOD detection model. Using a simple binary environment variable they learn a unified probability mixture model and demonstrate performance on both the debiased learning and OOD detection tasks.", "questions": "1. In line 42, do you actually agree with the statement that test time is just about feature/covariate shift? I would argue the very premise of a need for a method such as yours, plus basic knowledge of real world data characteristics together suggest that joint distribution shift is also a test time issue (I know it's arguably hard to address directly with any method)\n2. For the generative structural process you are making the assumption that the connectivity, or the adjacency matrix, is implied (caused) by the node features - cites random graph theory/homophily. Is this a valid assumption? Under this assumption it seems to follow that the distribution shift is therefore caused by node feature shift. Could your method be extended to when this assumption does not hold?\n3. Figure 3 and Table 1 seem to display the same kind of data? Could they be visualized the same way, or was this choice made because the bias ratio was fixed for the table? (why was this fixed for that table?)", "limitations": "1. This method introduces the requirement for a choice of prior on the cleanliness of the training set - this will have some effect on the final model performance, unknown in a real deployment setting.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**Quality**: The joint perspective on training time outliers and the task of OOD detection at test time is principled and correct, in this reviewer's opinion. The choice of datasets and the analyses are appropriate for the problem setup and the augmentation methods are relevant baselines. The explanatory ablation results at the end help address appropriate questions about the design choices made.\n\n**Originality**: The main novelty comes from the end-to-end manner in which they address weighting examples at training time as well as extracting the OOD model\n\n### Weaknesses\n\n**Clarity**: The section where Propositions 1 and 2 are stated is lacking proper backing for its claims, or rather in its current form, it's unclear whether this section contributes meaningfully. Overall, the concept of predicting the binary environment variable in order to learn a more optimal model conditioned on the environment variable makes sense, but the assumptions on the perfect recognition and perfect generative models are too strong to just state in this section. I don't feel the sections add significant justification for the approach.\n\n**Significance**: Results on more updated large scale data (say derived from OGB) would help demonstrate that the binary environment variable approach doesn't break down at scale - which matters for practical adoption of new methods, especially those focused on real world problems like distribution shift.\n\nWork would generally benefit from a close editing pass from a native english speaker, _but this does not factor into my assessment_.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Orf7LqzZmH1", "reviewer": "Reviewer_xAwj", "summary": "This paper aims to address two challenging tasks, i.e. 1) learning debased GNN model from the training data with OOD samples and 2) detecting the OOD samples from testing data, with a unified framework. To this end, a novel method named GraphDE is produced on the basis of variational inference. A probabilistic generative model is introduced to model the distribution of ID and OOD samples, and the classification module and OOD detection module are integrated into the learning framework. Experiments are conducted to verify the performance of GraphDE on both debiased learning and OOD detection tasks.\n", "questions": "- Is that practical to define the larger graphs in a dataset (i.e. Collab) or the images with gaussian noise (i.e. MNIST-75sp) as the OOD samples? It is hard to say these samples are generated from a different distribution. \n- In Line 134, the authors say \"p_\\theta(X|A,e)\" is composed of an ID component and an OOD component. Is there a typo? Because the assumption is that A is generated from X. \n", "limitations": "The authors have provided the limitations and potential negative impacts of the proposed framework in Appendix G and H, respectively. However, more discussion for potential negative impacts should be given, for example, the debiased learning paradigm may cause the concern about fairness.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The research problem is interesting.\nBoth debiased graph learning and graph OOD detection are attractive and interesting topics in the research community. The authors discuss the similarities and differences of these two tasks and address both tasks with a unified learning framework, which is promising and challenging.\n- The results are promising.\nIn the experiment, the authors conduct quite extensive experiments, and the proposed method achieves very good results, which prove its effectiveness.\nCons:\n- The construction of graph generative model is defective.\nIn the generative model, the distribution of feature p(X) is not modelled specifically, and the generation of feature X is not involved in the generating process. However, the ID and OOD data obviously have different feature distributions. For example, molecules from different domains tend to be formed by different atoms. In this case, it is not practical to model ID/OOD graph data without considering the difference in feature distribution.\n- The instantiation of OOD structure distribution p_0 is not practical.\nIn the instantiation, the authors use a simple distribution p(a=1)=1/2 to model the OOD data. However, in practice, the real-world OOD data can be universal, which cannot be simply modelled by such an impracticable distribution. Moreover, the ID data is also possible to follow \"p(a=1)=1/2\". In this case, how to distinguish ID/OOD distributions in practice? Therefore, I believe modelling OOD data with more complex or with learnable distribution is more persuasive in this method.\n- There is potential leakage in the evaluation of OOD detection.\nSince the model is trained on data composed by both ID and OOD data, the patterns of OOD data have already been seen by the model. In this way, a concern raises that the knowledge about OOD data would leak during the learning procedure. Such leakage may lead to unfair comparison in evaluation.\n- More baseline methods should be considered for comprehensive comparison.\nAlso graph debiased learning and graph OOD detection are both new-born directions in graph learning, there are already some pioneering works that focus on these topics. However, the authors consider limited baselines for comparison, which reduces the persuasion of experiments. So, more baselines can be consider for debiased learning (e.g., [*1], [*2]) and OOD detection (e.g., [*3]). More related papers can be found in survey [*4].\n[*1] Fan, Shaohua, et al. \"Generalizing Graph Neural Networks on Out-Of-Distribution Graphs.\" arXiv preprint arXiv:2111.10657 (2021).\n[*2] Li, Haoyang, et al. \"Ood-gnn: Out-of-distribution generalized graph neural network.\" arXiv preprint arXiv:2112.03806 (2021).\n[*3] Ma, Rongrong, et al. \"Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation.\" Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022.\n[*4] Li, Haoyang, et al. \"Out-of-distribution generalization on graphs: A survey.\" arXiv preprint arXiv:2202.07987 (2022).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Dg7_l9TMqUf", "reviewer": "Reviewer_gt4u", "summary": "This paper focuses on the problem of debiasing learning and out-of-distribution detection in graph data. The authors argue that existing works typically address these two tasks independently, but the intrinsic connections between training outliers and OOD test samples are overlooked. To this end, the authors propose a novel model called GraphDE to tackle debiasing learning for training data and OOD detection for test data under a unified probabilistic model. Extensive experiments are conducted on different GNN backbones, and the results validate the superiority of the proposed method over the baselines. Theoretical analyses are also provided to justify the effectiveness of the model.", "questions": "Why does not GraphDE outperform OCGIN or other baselines on Collab in terms of AUPR and on DrugOOD in terms of FPR95? More discussions on the undesirable results may be helpful.", "limitations": "No potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper focuses on an interesting and important problem. Outliers in training data and OOD samples are very common in the graph domain. Properly handling them is important to ensure the performance of a GNN model in practical usage.\n\n2. The paper manages to solve the problem of graph debiased learning and OOD detection in a novel perspective. That is, a unified framework is proposed to model the generative process of both the training data and the test data, where the two problems are tackled dependently.\n\n3. The paper is well-written and easy for readers to follow.\n\n4. The experimental results show that the proposed method achieves consistent performance improvements over the baselines, which demonstrates its superiority. Also, a detailed theoretical analysis is provided to justify the rationale of GraphDE.\n\nWeaknesses:\n1. It would be better if the authors can discuss under what condition the proposed model may not achieve desirable performance. For example, why GraphDE cannot achieve the best performance on Collab in terms of AUPR and on DrugOOD in terms of FPR95?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CtB6b_wgtPm", "reviewer": "Reviewer_iPSD", "summary": "This paper studies debiased learning and OOD detection for GNNs. Specifically, the authors propose GraphDE, a probabilistic generative framework to model the distribution shifts of graph data. The proposed method contains three main modules: the recognition model to infer the environment variables, the structure estimation model to detect outlier and OOD testing data, and the classification GNN model. Theoretical and empirical justifications of the proposed method are provided.", "questions": "See above", "limitations": "N.A.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros  \n[+] The motivations are clearly present. Figure 1 also helps understand the research problem of this paper.  \n[+] The proposed method shows improvements in the adopted datasets.   \n[+] The sensitivity analysis and ablation studies are provided to gain deeper insights into the proposed method.  \n\nCons:  \n[-] The novelty of the paper is somewhat limited. The essential idea of the proposed method is building a variational inference module on top of the existing GNNs, which are both heavily studied in the literature. Besides, the variational inference to infer the environment variable seems rather general and hardly connected with graph data (i.e., it may also be applied to other data types). However, the authors claim the challenges of non-Euclidean graph data in the introduction.  \n  \n[-] The authors do not provide time complexity analysis or the time cost in practice, so the efficiency aspect of the proposed method is unclear.  \n  \n[-] The experiments are not entirely convincing.  \na) Most importantly, the authors do not compare with OOD baselines, including general OOD methods (e.g., IRM, DRO, etc.), which can be directly combined with GNN backbones, and recent methods designed explicitly for graphs (e.g., DIR and OOD-GNN). \nb) The authors only consider GCN and GAT as the backbone but ignore more popular and powerful backbones such as GIN.  \nc) Though I acknowledge that some real-world graph benchmarks are adopted, it would make the experiments more convincing if OGB datasets, widely adopted in the literature, are further included.   \n  \n[-] The writing of the paper could be improved:  \na) Prop 4.1 and 4.2 are in plain language and thus may not be rigorous. It would be better if these propositions are provided in mathematical terms.  \nb) Some of the claims are not well supported. For example, one of the claimed contributions is that the modules are optimized in a mutually-promoting manner, which is not verified in the experiments. The necessary discussions on the inferred environments during the training of GNNs (as stated in line 12) have also not been present in detail.   \nc) The problem formulation in Section 2 seems to be literally identical to the existing work EERM, e.g., lines 69-73 and Section 2.1 in EERM. Such textual overlap without quotation should be avoided.  \n  \n[-] The authors claim in line 109: “For the first time to our best knowledge, we formally define and deal with the graph debiased learning problem.”, which misses important related works such as [1-2].  \n[1] Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data, NeurIPS 2021  \n[2] Debiased Graph Neural Networks with Agnostic Label Selection Bias, TNNLS 2022  \n\nMinor:  \n(1) More related works in Appendix B seem to highly relate to the paper and should be moved to the main paper.  \n(2) The font of “idx” in line 222 should be kept consistent with that in Eq. (14).  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "28OVnYATqxs", "reviewer": "Reviewer_hmWz", "summary": "This paper proposes a framework called GraphDE, which unifies debiased learning and OOD detection for graph data. GraphDE takes a generative view to model the joint distribution of $\\{G, y, e\\}$, with an additional recognition model that infers an OODness indicator variable $e$. The loss is carefully designed according to the framework, with interpretable justification. Various and extensive experiments demonstrate the effectiveness of GraphDE, which is expected to provide reference for future related works.", "questions": "I have a few confusions. Please correct me if I am wrong:\n1. How do you calculate the threshold in Eq. (3)? \n2. Line 107-108, the authors mention that prior works are limited to feature-label shift but ignore the variation in the feature space. Can GraphDE capture the variation in the feature space?\n3. Line 132, why are the two distributions parameterized by the same $\\theta$?\n4. Line 134, I think there is a typo, i.e. $p_\\theta(X|A,e)$ should be $p_\\theta(A|X,e)$.\n5. In the last term of Eq. (7), should $p(e)$ be $p(e_i)$?\n6. I am very confused with line 181-182 which mentions that $p(e)$ is a scalar $\\in[0,1]$. If so, why $p(e)$ is not canceled out in Eq. (8)? I think it should be a discrete distribution over ID and OOD input.\n7.  Do you have the assumption that training and test data have the same $p(e)$? Because $p(e)$ (I suppose it is obtained in the training set) is used in the inference on test data (in Eq.(8)). If test data have a different $p(e)$, will GraphDE still work?\n8. Eq.(9) is used to predict label on test data. Do you still output a label even when OOD is detected?\n9. What is the role of GraphDE-v? Since you can compute the posterior analytically, it seems to me GraphDE-a works perfectly, and it is also confirmed in Table 1 that GraphDE-v is entirely outperformed by GraphDE-a.\n10. Figure 4 is counter-intuitive to me. Eq.(2) tells me that debiased learning can be reduced to ignoring updates from outliers (because training on outliers will hurt the performance), and proof in Appendix A.2 tells me that optimizing the proposed $L_{cl}$ is equivalent to optimizing Eq.(2). Then I suppose $L_{cl}$ is why GraphDE can boost test accuracy as in Figure 1(a). However, the ablation study shows that removing $L_{cl}$ makes literally no difference to the performance, while removing $L_{reg}$ shows more impact. Do you have any interpretation on this result?", "limitations": "The authors addressed the limitations and societal impact in their paper (in the end of appendix).", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The framework unifies debiased learning and OOD detection, i.e. the OOD detector is obtained during the debiased learning.\n2. The loss is well-interpretable.\n3. Experimental results are fairly good.\n\n\nWeakness:\nSee my questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept