Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization
Authors: Shurui Gui
Meng Liu
Xiner Li
Youzhi Luo
Shuiwang Ji
Venue: NeurIPS 2023 poster (2023)
Keywords: deep learning
graph neural network
out-of-distribution generalization
distribution shift

Abstract: We tackle the problem of graph out-of-distribution (OOD) generalization. Existing graph OOD algorithms either rely on restricted assumptions or fail to exploit environment information in training data. In this work, we propose to simultaneously incorporate label and environment causal independence (LECI) to fully make use of label and environment information, thereby addressing the challenges faced by prior methods on identifying causal and invariant subgraphs. We further develop an adversarial training strategy to jointly optimize these two properties for casual subgraph discovery with theoretical guarantees. Extensive experiments and analysis show that LECI significantly outperforms prior methods on both synthetic and real-world datasets, establishing LECI as a practical and effective solution for graph OOD generalization.

Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization
Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, Shuiwang Ji
Department of Computer Science & Engineering
Texas A&M University
College Station, TX 77843
{shurui. gui mengliu, 1xe, yzluo, sji] (ttaemum....... edu
Abstract
We tackle the problem of graph graph OOD algorithms either rely restricted assumptions or fail to exploit envi- ronment information in training data. this work, we propose to simultaneously incorporate label and environment causal independence (LECI) to fully make of label and environment information, thereby addressing the challenges faced by prior methods identifying causal and invariant subgraphs. We further develop an adversarial training strategy to jointly optimize these two properties for causal subgraph discovery with theoretical guarantees. Extensive experiments and analy- sis show that LECI significantly outperforms prior methods on both synthetic and real-world datasets, establishing LECI as a practical and effective solution for graph OOD generalization. Our code is available at
(OOD) generalization. Existing
Introduction
Graph learning methods have been increasingly used for many diverse tasks, such as drug discov- ery [1, social network analysis 22, and physics simulation 3. One of the major challenges in graph learning is
(OOD) generalization, where the training and test data are typically from different distributions, resulting significant performance degradation when deploying models to new environments. Despite several recent efforts 74 have been made to tackle the OOD problem on graph tasks, their performances are often not satisfactory due to the complicated distribution shifts on graph topology and the violations of their assumptions premises in reality. In addition, while environment- based methods have shown success traditional OOD fields [8 19, they cannot perform favorably graphs [10]. Several existing graph wewroomment-ceeteee methods [13 aim infer environment labels for graph tasks, however, most methods utilize the pre-collected environment
labels in manner similar to traditional environment-bait based techniques [ 14 [5], rather than exploit- ing them in a unique and specific way tailored for graphs. Therefore, the potential exploitation of environment information in graph OOD tasks remains limited (Sec. 2.2 Although annotating extracting environment labels requires additional cost, it has been proved that generalization without extra information is theoretically impossible [16] (Appx. B.2). This is analogous the impossibility of inferring or approximating causal effects without counterfactualiinteeennn
distributions [17
In this paper, we propose novel learning strategy to incorporate label and environment causal independence (LECI) for tackling the graph OOD problem. Enforcing such independence properties can help exploit environment information and alleviate the challenging issue of graph topology shifts. Specifically, our contributions are summarized below. (1) We identify the current causal subgraph discovery challenges and propose solve them by introducing label and environment causal independence. We further present a practical solution, an adversarial learning strategy, to
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

jointly optimize such two causal independence properties with causal subgraph discovery guarantees. (2) LECI positioned as the first graph-speciin pre-collected environment exploitation learning strategy. This learning strategy is applicable to any subgraph discovery networks and environment inference methods. (3) According to our extensive experiments, LECI outperforms baselines on both the structure/feature shift sanity checks and real-world scenario comparisons. With additional visualization, hyperparameter sensitivity, training dynamics, and ablation studies, LECI is empirically proven to be practically effective method. (4) Contrary to prevalent belief's and results, we showcase that pre-collected environment information, far from being useless, can be a potent tool in graph tasks, which is evidenced more powerful than previous assumptions.
2 Background
2.1 Graph OOD generalization
We represent an attributed graph as G' = (X, A) G. where G is the graph space. X E gnxd and A E [R"x" denote its node feature matrix and adjacency matrix respectively, where n is the number of nodes and d is the feature dimension. In the graph-level OOD generalization setting, each graph G has an associated label Y E y, where y denotes the label space. Notably, training and test data typically drawn from different distributions, i.e., pdr (G,Y) * ptr Ptc(G.)), Y). Unlike the image space, where distribution shifts occur only on feature vectors, distribution shifts in the graph space can happen on more complicated variables such as graph topology 19 20). Therefore, many existing graph OOD methods 7 [1 aim to identify the most important topological information, called causal subgraphs, that they can be used to make predictions that are robust to distribution shifts.
2.2 Environment-basse OOD algorithms
To address distribution shifts, following invariant causal predictor (ICP) 21 and invariant risk minimization (IRM) [9] many environment-basee invariant learning algorithms [14 24] also referred as parts of domain generalization (DG) 27) classify data into several groups called Intuitively, data in the same environment
environments, denoted as F E E = {c1, -..-... 9IE) group share similar uncritical information, such as the background of images and the size of graphs It is assumed that the shift between the training and test distribution should be reflected among environments. Therefore, to address generalization problems in the test environments, these methods incorporate the environment shift information from training environments into neural networks, thereby driving the networks to be invariant to the shift between the training and test distribution.
Several works further consider the inaccessibility of environment information in OOD settings. For example, environment inference methods [T] 28 propose to infer environment labels to make invariant predictions. While in graph tasks, several methods 4 [3 attempt to generalize without the use of environments. However, these algorithms usually rely on relatively strict assumptions that can be compromised in many real-world scenarios and may be more difficult to satisfy than the access of environment information, which will be further compared and justified in Appx C.2 As demonstrated in the Graph the environment information for graph datasets is commonly accessible. Thus, in this paper, we assume the availability of environment labels and focus on invariant predictions by exploiting the given environment information in graph-specific OOD settings. Extensive discussions of related works and comparisons to previous graph OOD methods are available in Appx B
(GOOD) benchmark [10] and DrugOOD 29
Comparisons to other environment-based graph OOD methods. It's crucial to distinguish between the two stages of environmental- based methods: environmental inference and environmental exploitation. The first phase, environmental inference, involves predicting environmental labels, while the second, environmental exploitation, focuses on using pre-acquired environmental labels. Typically, an environmental inference method employs an environmental exploitation method to evaluate its effectiveness. However, an environmental exploitation method does not require an environmental inference method. Recent developments in graph- environmental inference methods [1] 12 and node-level environmental inference methods [13] introduce graph-specific environmental inference techniques. Nevertheless, their corresponding environmental exploitation strategies are not tailored to graphs. In contrast, our method, LECI, bypasses the environmental inference phase and instead introduces a graph-specific environmental exploitation algorithm, supported by justifications in Appx B.3 More environment-related discussions and motivations are available in Appx. B.2

---

3 Method
OOD generalization is a longstanding problem because different distribution shifts exist in many different applications of machine learning. As pointed out by Kaur al. [30], understanding the data generation process is critical for solving OOD problems. Hence, we first formalize the target problems through three topology distribution shift assumptions from a causal and data generation perspective. We further identify the challenges of discovering causal subgraphs for addressing topology distribution shifts. Building on our analysis, we propose a technical solution and a practical implementation to jointly optimize label and environment causal independence in order to learn causal subgraphs effectively.
3.1 Causal perspective of graph OOD generalization
major difference between traditional OOD and graph OOD tasks is the topological struc- ture distribution shift in graph OOD tasks. To analyze graph structure shifts, we commonly assume that only part of a graph determines its target Y; e-g., only the functional motif of a molecule determines its corresponding prop- erty. Therefore, in graph distribution shift stud- ies, we assume that each graph G E G is composed of two subgraphs; namely, causal subgraph Gc E 9 and a spurious subgraph Gg E G shown in the structure causal mod- els (SCMs) 17 18 of Fig. [I] For notational convenience, we denote graph union and sub- traction operations as - and -, respectively; e.g.
E
E
E
G
Gc
(6) Covariate SCM
(b) FIFF SCM
(c) POF SCM
Figure 1: Illustrations of three distribution shift assumptions. In these structural causal models (SCMs), each node denotes a variable, and each di- rectional edge represents causation. Grey nodes observable variables that can be directly accessed, but it does not mean that we "conditioned on" these variables.
G = Gc + G. and Gc G - Gg. It follows from the above discussions that Ge is the only factor determining the target variable Y E Y, while Gs is controlled by an exogenous environment E, such that graphs in the same environment share similar spurious subgraphs.
As illustrated Fig. (a), the covariate shift represents the most common distribution shift. Similar to image problems in which the same object is present with different backgrounds, graphs that share the same functional motif along with diverse graph backbones belong to the covariate shift. Under this setting, G is only controlled by E. Models trained in this setting suffer from distribution shifts because the general empirical risk minimization (ERM) training objective P(Y is conditioned on the collider G, which builds spurious correlation between G. and Y through Y +- Gc G t- Gs. where - denotes a causal correlation. The fully informative invariant features (FIIF) and the partially informative invariant features (PIIF) assumptions, shown in Fig. T (b) and (c), are two other common assumptions proposed by invariant learning studies (6 9 31). In the graph FIIF assumption, Gs is controlled by both Ge and E, which constructs an extra spurious correlation Y + TGG + Gs. In contrast, the graph PIIF assumption introduces an anti-causal correlation between Gs and Y. Our work focuses on the covariate shift generalization to develop our approach and then extends the solution to both FIIF and PIIF assumptions.
Essentially, we are addressing the distribution shifts between ptr Y) and pte (G,Y). Y). Our core assumption, based on the Independence Causal Mechanism (ICM), is that there exists a component Ge within G such that attributed to interventions on Gg = G - Go that are encapsulated as an environment variable E, aligned with the invariant learning literature. The OOD dilemma arises when ptr (E) o ple (E), leading to shifts in both ptr (Gs) and (te(Gs) and consequentially, (²r(G) of (G). It's crucial note that we assume both ptr (Gc) and ple (Gc) retain the same support. Explicitly, our target is to resolve OOD scenarios where the supports of prr (E) and pte (E) differ.
p Gc). The shifts in distribution
exclusively
3.2 Subgraph discovery challenges
A common strategy to make neural networks generalizable to structure distribution shifts in graph OOD tasks is to identify causal subgraphs for invariant predictions 66 19). However, correctly selecting subgraphs is challenging due to the following two precision challenges. (1) The selected
causal subgraph may contain spurious structures, i.e., 3G, S Gs. Gp S Gc, where G. S Go
3

---

LD: Label discriminator
GRL
aLi.
Environment discriminalor
Gs
IP:
Invariant predictor
GRL: Gradient reverse layer
LD: 9L
Loss Lt.
aCL
X1. a0
Gc
Subgraph selector: fo
IP: tlav
Loss Liny
UCB Ag 09
ED: gn:
Loss LB
Forward path
GRL
Backward path
aCg
dgg
Figure 2: An illustration of the invariant prediction process by selecting the causal subgraph Go using an interpretable subgraph discovery network in LECI. This network and training details are described in Sec. 3.4 We multiply the reversed gradients with two hyperparameters Åτ. and dE to control the adversarial training. For clear notations, we define the three losses Liwv LL, and Le in Eq.
6 respectively.
denotes Ga subgraph of Gb, and Ge represents the selected causal subgraph. (2) The model may not select the whole Ge into Ge and leave a part of Ge in Gs Go- Formally, 3G, S Gc, G, S Gs. The reason for the occurrence these precision challenges will be further discussed in Appx.
3.3 Two causal independence properties
To address the precision issues, it is necessary to distinguish between causal subgraphs and spurious subgraphs, both theoretically and in practice. To achieve this, under the covariate assumption, we introduce two causal independence properties for causal and spurious subgraphs, respectively; those are F. 11 Gc and Y 11. Gs-
The first property E IL Ge is a crucial consideration alleviate the first precision problem. As illustrated in Fig. 1 (a), since G acts as a collider that blocks the correlation between E and Gc. the environment factor E should be independent of the causal subgraph Gc. Conversely, due the direct causation between E and Gs, the spurious subgraph Gs is highly correlated with E. This correlation difference with E indicates that enforcing independence between E and the selected causal subgraph Gc can prevent parts of spurious subgraphs in Ge be included, thereby solving the first precision problem. Note that this independence also holds in FIIF and PIIF settings, because Gs acts as another collider and blocks the left correlation paths between Ge and E, i.e., Ge - GG E and Ge + Y + Gg + E.
We propose to enforce the second independence property IL Gs in order address the second precision problem. Under the covariate assumption, the correlation between Y and Gs is blocked by G. leading the independence between Y and Gs. On the other side, the causal subgraph Ge is intrinsically correlated with Y. Similarly, this correlation difference with Y motivates us to enforce such independence, thus filtering parts of causal subgraphs out of the selected spurious subgraphs
Gs. This property Y IL Gs, however, does not hold under the FIFF and PIIF settings, because the Y Gc + Gs and the Y + Gs correlations. Therefore, we introduce a relaxed version of the independence property: for any G, that Gg C Gp. I(Gs; Y) < I(GG; Y) (See Appx. C.I.I
3.4 Adversarial implementation
The above two causal independence properties are intuitively helpful in discovering causal subgraphs. In this section, we present our practical solution learn the label and environment causal indepen- dence (LECI). The overall architecture of LECI is illustrated in Fig. 2 To be specific, we use an interpretable subgraph discovery network the basic architecture, which consists of subgraph selector So G + G and an invariant predictor yio + y. Here, fo and giov model the distributions Po(Gcl ()) and Po.. (Y (Y))), where dimv is the model parameters. Specifically, following Miao et al.

---

[5]. our subgraph selector module selects subgraphs by sampling edges from the original graphs. However, the sampling process is not differentiable and blocks the gradient back propagation. To overcome this problem, we use Gumbell-igmond (32) to bypass the non-differentiable sampling process. The basic training loss for this subgraph discovery network can be written as
Luny
- log Pan (YIG))
worth noting that Gc = GG and Gs G - GG are complimentary. More details of the subgraph selector can be found in Appx. D.1
To incorporate the causal independence properties described in Sec. 3.3 first enforce the condition Gc TL E. Since Ge TT E' is equivalent to I(E; Gc) 0, and (E; Gc) 2 0, the objective I[E; Gc) reaches its minimum when and only when Gc JL E. This leads us to define minimizing I(E; Gc) as our training criterion.
Definition 3.1. The environment independence training criterion is 6 arg min [(E; GC)
(2)
For fixed 0, [(F:; Gc) is essentially constant. However, the mutual information T(E; Gc) E
P(E) cannot be calculated directly, since P(E|Go) is unknown. Following Proposition 1 GAN 331, we introduce an optimal discriminator 9b: : 9 + with parameters OR to approximate
log P(F(GC)
G() as Pon (EIGc), minimizing the negative log-likelihood -E log Po.
We then
have the following two propositions:
Proposition 3.2. For 0 fixed, the optimal discriminator dR is
o
= arg min -E log Po. (E|Gc)
(3)
bg
Proposition 3.3. Denoting KL-divergence KL for 0 fixed, the optimal discriminator óø is dg. s.f.
KL P(E (E)G)) =
(4)
Proposition 3.2 can be proved straightforwarddy by applying the cross-entropy training criterion, while
the proof of Proposition 3.3 is provided in Appx C With these propositions, the mutual information can be computed with the help of the optimal discriminator Φ According to Proposition 3.3 we
have:
T(E; GCF E log Pag Pag (F(Cc)
+ H(F) + KI. PP
(5)
E log P (E)C + (E) + 0.
Thus, by disregarding the constant HF),, the training criterion becomes:
OF = arg min (EE; Gc) = arg min E log Pag (EIGe) = arg min max
log Pon (E|Go)
dE
We can reformulate this training criterion in terms of a negative log- likelihoood form (Cg) to define environment adversarial training criterion (EA):
0 Og E arg max(min LE} 0g og E arg max min -E [log Pog (E (EIGe)
ΦR
(7)
To enforce GS TL Y. we introduce label discriminator It G + y to model P(Y]Gs) with parameters Φb. as Par (Y|Gs). This leads symmetric label adversarial training criterion (LA):
or 00 O0 E arg max(min Le) {ot 0r E arg max dr.
min 61
E log Pou. (YIGs)
(8)
It's important to note that Og and Or are not unique optimal parameters. Instead, they are two optimal parameter sets, including parameters that satisfy the training criteria. We will discuss O and O along with relaxed version of LA, in further detail in the theoretical analysis section 3.5
5

---

Intuitively, as illustrated in Fig. 2 the models and 9L. acting as an environment discriminator and label discriminator, are optimized to minimize the negative log- liceliiiosoods. In contrast, the subgraph selector So tries to adversarially maximize the losses by reversing the gradients during back- propagation. Through this adversarial training process, aim to select causal subgraph Gc that is independent of the environment variables E, while simultaneously eliminating causal information from Gs such that the selected causal subgraph Gc can retain as much causal information as possible for the accurate inference of the target variable Y.
3.5 Theoretical results
Under the framework of the three data generation assumptions outlined Section 3.1 we provide theoretical guarantees to address the challenges associated with subgraph discovery. Detailed proofs for the following lemmas and theorems can found in Appx. C We initiate our analysis with
lemma for Gc T1 E:
Lemma 3.4. Given subgraph Gp of input graph G and SCMs (Fig. it follows that Gp S Go if and only if G I1 E.
This proof hinges on the data generation assumption that any substructures external to Go (i.e., Gs)
maintain associations with E. Consequently, any Ge that fulfills Ge IL will be a subgraph of Gc, denoted as Ge S Gc. We then formulate the EA training lemma as follows:
Lemma 3.5. Given SCMs (Fig.
7. the predicted G = fe(G), and the EA training criterion (Eg. 6).
Go S Gc if and only if E Oz
This lemma paves the way for immediate conclusion: given that Go is not unique under the EA training criterion, the optimal O is likewise non-unin non-unique, rather 0j represents a set of parameters. Any A E Og adheres to the environment independence property. Similarly, under the covariate SCM assumption, when enforce Gş TL Y, Oo represents an optimal parameter satisfying the label independence property.
Lemma 3.6. Given the covariate SCM assumption and the LA criterion (Eq. 7. Gs Gs if and only if E Oz.
Our first subgraph discovery guarantee is direct corollary of Lemma 3.5 and Lemmal 3.6
Theorem 3.7. Under the covariate SCM assumption and both EA and LA training criteria (Eq. and 7 it follows that Gc = Gc if and only if E O n O%
However, the aforementioned theorem does not ensure causal subgraph discovery under FIIF and PHIF SCMs. Hence, we need to consider the relaxed property of Gs IL discussed Sec. 3.3 to formulate more robust subgraph discovery guarantee.
Theorem 3.8. Given the covariate/FlIF/PIiF SCM assumptions and both EA and LA training criteria (Eq. O and 7), it follows that Ge Ge if and only if, under the optimal EA training, the LA criterion optimized, i.c.,9 E arg maxęge; {ming LL).
The proof intuition hinges the assumption that Gs C G under the premise of Go IL E. Hence, taking into account the relaxed property, the mutual information T(Gs; Y' can be minimized when Gg = Gs. i... Go Gc. This, turn, suggests that the LA optimization should satisfy θî S O denoted O = arg maxage; {min,, LL). J. As result, the EA training criterion takes precedence over the LA criterion during training, which is empirically reflected by the relative weights of the hyperparameters in practical experiments.
3.6
Pure feature shift consideration
Even though removing the spurious subgraphs can make the prediction more invariant, the proposed method primarily focuses on the graph structure perspective. However, certain types of spurious information may only be present in the node features, referred to as pure feature shifts. Thus, we additionally apply a technique to address the distribution shifts on node features X. In particular, we transform the original node features into environment-fiue free node features by removing the environment

---

information through adversarially training with small feature environment discriminator. Ideally, after this feature filtering, there are no pure feature shifts left; thus, the remaining shifts can be eliminated by the causal subgraph selection process. The specific details of this pre-transformation step can be found in the Appx. D.2
D.2
3.7 Discussion of computational complexity and assumption comparisons
The time complexity of LECI O + ndf) where n, m, and d denote the number of nodes, edges, and feature dimensions, respectively. To be more specific, the cesssag--aassing neural networks have time complexity O(md + nd²). Our environment exploitation regularizations have time complexity (()) without any extra cost. Therefore, the overall time complexity of our LECI is (md + nd? + 1) = O(md + ndf), ). OOD generalization performance cannot be universal and is highly correlated to the generalizability of the method's assumptions. Therefore, we provide theory and assumption comparisons with previous works 6 in Appx. C.2
4 Experiments
In this section, conduct extensive experiments to evaluate our proposed LECI. Specifically, aim to answer the following research questions through our experiments. RQ1: Does the proposed method address the previous unsolved structure shift and feature shift problems? RQ2: Does the proposed method perform well in complex real-world settings? RQ3: Is the proposed method robust across various hyperparameter settings? RQ4: Is the training process of the proposed method stable enough under complex OOD conditions? RQ5: Are all components in the proposed method important? The comprehensive empirical results and detailed analysis demonstrate that LECI is an effective and practical solution to address graph OOD problems in various settings.
4.1 Baselines
We compare our LECI with the empirical risk minimization (ERM), graph pooling baseline ASAP (34, 4 traditional OOD baselines, and, 4 recent graph-specific OOD baselines. The traditional OOD baselines include IRM 19, VREx (4). DANN 8. and Coral [35,, and the 4 graph-specific worth noting that the implementation of CIGA we use is CIGAv2 and we provide an environment exploitation comparison with GIL's environment exploitation phase (IGA (TS) on the same setting subgraph discovery network
OOD algorithms are DIR 4. GSAT (5), CIGA 6 and GIL [I].
in Appx B.3
Detailed baseline selection justification can be found in Appx. F..3
4.2 Sanity check on synthetic datasets
In this section, we aim to answer RQI by comparing our LECI against several baselines, on both structure shift and feature shift datasets. Following the GOOD benchmark [10), we consider the synthetic dataset GOOD-Motif for structure shift sanity check and the semi-synthetic dataset GOOD-CMNIST for a feature shift sanity check. Dataset details are available in Appx. E.2
Specifically, each graph in GOOD-Motif is composed of a base subgraph and a motif subgraph. Notably, only the motif part, selected from 3 different shapes, determines its corresponding 3-class classification label. This dataset has two splits, a base split and size split. For the base split, environment labels control the shapes of base subgraphs, and we target generalizing to unseen base subgraphs in the test set. In terms of the size split, base subgraphs' size scales vary across different environments. In such split, we aim to generalize from small to large graphs
As shown in Tab. T our method performs consistently better against all baselines. According to the GOOD benchmark. our method the only algorithm that performs close to the oracle result (92.09%) on the base split. To further investigate the OOD performance of our method under the three SCM assumptions, we create another synthetic dataset, namely Motif for covariate, FIIF, and PIIF (Cti-Motif). To be specific, there are two major differences compared to GOOD-Moti First, instead of using paths as base subgraphs in the test environment, we produce Dorogovtsev-Men Mendes graphs [36] as base subgraphs, which can further evaluate the applicability of generalization results. Second, CFt- extends GOOD-Motif with FIFF and PHI shifts. In FIIF and PIIF splits (Fig. [. Ge and Y have a probability of 0.9 to determine the size of Gs. leading to spurious correlations w.r.t. size. Among the three shifts, PHIF the hardest one for LECT due to the stronger correlations between Gs and Y than FIIF, which may cause the relaxed version of independence property (Sec. 3.3 less
7

---

Table I: Results structure and feature shift datasets. The reported results the classification accuracies on test sets with standard deviations in parentheses. All reported results are obtained through automatic hyperparameter selection process with runs. The best and second-best results are highlighted in bold and underline respectively.
GOOD-Motif
GOOD-CMNIST
CFP-Mour
basis
size
color
covariate
FIF
PHF
ERM
(0.93(11.11)
56.63(7.12)
26 (6.442)37)
57,5619.59)
37,22(3.70)
62.45(9.21)
IRM
64.94(4.85)
54152(3.27)
29.632206)
58.11(5.14)
44.33(1.52)
68.34(10..4)
VREX
61.59(6.58)
(5.85())42)
27.13/2.90)
48.78(7.81)
34,78(1.34)
63.33(6.55)
Coral
61.95(10.36) 36)
(5.80)
(6.21(6.87)
57.11(8.35)
42.67(7.09)
60.35(8.85)
DANN
50.62(4.71)
46.61(3.78)
27.86(5.02)
49.45(8.05)
43.22(6.64)
62.56(10.39)
ASAP
45.00(11.66) (.)
42.23(4.20)
23.530.67)
60.00(2366)
43,34(7.41)
35.78(0.88)
DIR
34.39(2.02)
43.11(2778
22.5M2.56)
44.67(0.00)
42.00(6.77)
47.2228870
GSAT
62.27(8.79)
50.03(5.71)
35,02(2.78)
68.22(7.33)
51.56(6.59)
61.2228.88) 80)
37.81(2442)
(5.15)
25.06(3.07)
39.11(7.30)
45.67(7.52)
LECI
84.56(2.22)
71.43(196)
51.80(2.70)
83.20(5.89)
77.73(3855)
69.40(7.54)
Figure 3: Interpretability visualization of LECI. The figure displays the results with the three motifs (crane, house, cycle). The left three graphs selected from the training set with 3 base graphs, namely, ladder, tree, and wheel, respectively. The right three graphs are from the OOD test set with Norogovtsev-Mender graphs their basis. For clarity, the motifs and base graphs colored as green and orange nodes, respectively. The selected causal graphs Gc denoted by red edges.
prominent, i.e., larger I(Gs; Y) may lead smaller gradients from any Gp Gs. Comparing ERM and subgraph discovery OOD methods on GOOD-Mott size and CFP-Motif FIIF/PIFF splits, we observe that although subgraph discovery methods possible to address size shifts, they are more sensitive than general GNNs.
The feature shift sanity check is performed on GOOD-CMNIST, in which each graph consists of colored hand-written digit transformed from MNIST via superpixel technique 337 The environment labels control the digit colors, and the challenge is to generalize to unknown colors in the test set. As reported in Tab. 1 LECI outperforms all baselines by a large margin, indicating the significant improvement of our method on the feature shift problem.
Due to the difficulty of OOD training process, many OOD methods do achieve their theoretical OOD generalization limits. To further investigate the ability of different learning strategies, we deliberately leak the OOD test set results and apply OOD test set hyperparameter selection to compare the theoretical potentials of different OOD principles in Appx. F.
4.2.1 Interpretability visualizations
As illustrated in Fig. LECI can select the motifs accurately, which indicates that LECI eliminates most spurious subgraphs to make predictions. This the key reason behind LECI's ability to generalize graphs with different unknown base subgraphs, making the first method that achieves such invariant predictions on GOOD-Motif. More visualization results are available in the Appx. F2
4.3 Practical comparisons
In this section, aim to answer RQ2, RQ3, and RQ4 by conducting experiments real-world scenarios.
4.3.1
Comparisons on real-world datasets
We cover diverse set of real-world datasets. For molecular property prediction tasks, we use the scaffold and size splits of GOOD-HIV (10) and the assay split of DrugOOD LBAA-core-icc00 (29 to evaluate our method's performance different shifts. Additionally, we compare OOD methods on

---

Table 2: Real-world scenario performance. We compare the performance of 10 methods real- world datasets. The results are reported in terms of accuracy for the first two datasets, and ROC-AUC for the latter two. For each dataset split, ID val and OOD val denote the OOD test set results using the in-distribution and
validation set in each run, repectively.
GOOD-SST2
GOOD-Twiter
GOOD-HW-vsufool
GOOD-HIVaize
DrugOOD-aeay
ID val
0OD val
ID val
0GD val
ID val
00D val
ID val
0OD val
ID val
0OD val
78.37(2.68)
80.4 (0.09)
54.000.95)
57,04(1.0)
09.60(1.2)
19.57(111)
61.6612455
57.3001.0)
70,0301111
72,150.155
IRM
19.75(1.55)
(2)
55.2701-194
57.720
73,35(2.0)
20.890.20)
(8.570.96)
03.862.35
71.560.33
71,900.20
VREa
70 79.31(1.40)
80 00.3301.000 0.99
56 (3.46/099)
56.3700766
51.733.51)
71.156069)
S8. 18.5911554)
60. 60.102209)
002200.86
72.830.50)
Coml
78.2403.20 261
80.97
56.570.42)
56, 14C1.77
71,1912.8 82)
71. 71.122.90 (2)
00.8164766
62,071100 (0)
70 10.190976)
72,070055)
DANN
78, 74.440)
80 (0.60)
55. 52. 27
55,710.25
09.85(3600 160
72,251.59)
61.370053)
00,022111 11)
09.8300955
72.230.261
78.5122.261
56
(8.9722911
61. 61.082266)
(42.42
71,730.
DIR
77.65(0.71)
$1.500055)
55.52(3.85)
56.8100:91)
65.84(2.71)
68.993370)
59.091..9)
608500.52
67.290.723
69.7000.65)
GSAT
19.251100 1.09)
90045 353
55. (1/0000000 66)
56,000.53)
71.55(3.558
71.3911441
62.920.000
10.60111)
71.01(0.54)
72.2500
CIGA
80.97/1.46)
81. 2000.75
57.510).560 563
57. 19.1911155
66.25 899
71.4701.20)
58.2463.78 733
62.5641776)
67. 67.68(1.14)
70.54(0.59) (0.5)
LECI
N2.93002231
23,4400.77
59.35(1.4
59.6400.55)
74.0400.55)
74.4303669
64.8912.99)
65.440.75)
72.67(8.46)
73.45(0.17)
natural language processing datasets, including GOOD-SST SSDD-SST22RO and Twitter 38 The Twitter dataset is split similarly to GOOD-SST2 thus will be denoted as GOOD-Twitter in this paper. According to Tab. 2 LECI achieves the best results over all baselines on real-world datasets. Notably, LECI achieves consistently effective performance regardless of whether the validation set is from the in-distribution (ID) or out-of-distributiin (OOD) domain. This indicates the stability of our training process, which will be further discussed in Sec. 4.3.3 Besides, we provide a fairness justification in Appx. E.I
4.3.2 Hyperparameter sensitivity study
In this study, we examine the effect of the hy- perparameters λE and Ar. on the performance of our proposed method on the GOOD-Motif
and GOOD-Twitte datasets. We vary these hy- perparameters around their selected values and observe the corresponding results. As shown in Fig. LECI demonstrates robustness across dif- ferent hyperparameter settings and consistently outperforms ERM. Notebly, since OOD gener- alizations are harsher than ID tasks, although these results are slightly less stable than ID re- sults, they can be considered as robust in the OOD field compared to previous OOD meth- ods 4 In these experiments, while we apply stronger independence constraints in synthetic datasets, we use weaker constraints in real-worid datasets. This is because the two discriminators are harder train on real-world datasets, so slow down the adversarial training of the sub- graph selector to maintain the performance of the discriminators. More information on the hyperparameters can be found in the Appx. E.5
Tost
GOOD Motif
A
003-
01:00 3.0011 COC 1.R1
GO0D-Twiti
Figure 4: Sensitivity analysis of A and Åg. For each sensitivity study, we fix other hyperparam- eters with the values selected from the previous experiments.
4.3.3 Training stability and dynamics study
The training stability is an important consideration to measure whether method is practical to implement in real-world scenarios or not. To study LECT's training stability, we plot the OOD test accuracy curves for our LECI and the baselines on GOOD-Motif and GOOD-SST2 during the training processes. As illustrated in Fig. many baselines achieve their highest performances at relatively carly epochs but eventually degenerate worse results after overfitting to the spurious information. On GOOD-Motif, several general OOD baselines converge to accuracy around 70% higher than many other baselines, but these results are sub-optimal since 70% accuracy indicates that these methods nearly misclassify one whole class given the dataset only has 3 classes. In contrast, LECI's OOD test accuracy begins to climb up rapidly once the discriminators are well-trained and the independence constraints take effect. Then, LECI consistently converges to the top-grade performance without further degradation. This indicates that LECI has stable training process with desired training dynamics; thus, it is practical to implement in real-world scenarios.

---

Dive into the training dynamics, during the ini- tial phase of the training process depicted in Fig. | independence constraints are minimally applied (or are not applied), ensuring a con-
814
Toosk Ado
Test
ducive environment for discriminator training. This approach is predicated on the notion that adversarial gradients yield significance only post the successful training of discriminators accord- ing to Proposition 3.3 The observed perfor- mance "drop" is attributed to the fact that the generalization optimization is yet to be activated, so it indicates the general subgraph discovery network performance.
Epoch
Epoch
Figure 5: Stability study. The figures illustrate the OOD test accuracy curves during the training process GOOD-Motif and GOOD-SST2. The big red arrows indicate the times when the inde- pendence constraints begin to take effect.
4.4 Ablation study
We empirically demonstrate the effectiveness of LECI through the above experiments. In this section, we further answer RQ5 to investigate the components of LECI. Specifically, we study the effect of environment adversarial (EA) train- ing, label adversarial (LA) training, and pure feature shift consideration (PFSC) by attaching one of them to the basic interpretable subgraph discovery network. As shown in Tab. B] it is clear that applying only partial independence obtains suboptimal performance. lead to worse results as indicated by Motif-size. In comparison, much higher performance for the structure shift datasets can be achieved when both EA and LA are applied simultancously. This further highlights the importance of addressing the subgraph discovery challenges discussed in Sec. 3.2 invariant predictions.
Table 3: Ablation study on LECI. The "None" and "Full" rows represent the results for the basic interpretable network and full LECI model N/A denotes that certain component is not applied to the dataset.
GOOD-Man
GOOD-CMNIST
basis
None LA
58.38(9.52)
65.17 (7()488))))))
33.41(4.63)
62.14(9.37)
(3.57
33.64(4.41)
may even
EA
64.02(21.30)
38.69(1.8
38.29(9.85)
PESC
N/A
N/A
19.33(5.88)
Full
84.56(2.22)
71.43(1.96)
51.80(2700
Overall, the experiments in this section demonstrate that LECI a practical and effective method for handling on both synthetic and real-world datasets and is robust to hyperparameter settings. Additionally, LECI's interpretable architecture and training stability further highlight its potential for real-world applications.
generalization in graph data. It outperforms existing baselines
5 Conclusions & Discussions
We propose technical and practical solution to incorporate two causal independence properties to release the potential of environment information for causal subgraph discovery in graph OOD gener- alization. The previous graph OOD works commonly assume the non-existence of the environment information, thus enabling these algorithms to work on more datasets without environment labels. However, the elimination of the environment information generally brings additional assumptions that may be more strict or even impossible to satisfy as mentioned Sec. Sec.3.7 [3.7] In contrast, environment labels are widely used in the computer vision field [8]. While in graph learning areas, many labels can be accessed by applying simple groupings or deterministic algorithms as shown in GOOD [10 and DrugOOD 29 These labels might not be accurate enough, but the experiments in Sec. have proved their effectiveness over previous assumptions empirically. Moreover, recent graph environment- aware non- non-Euclidean extrapolation work G-Splice [19] also validates the significance environment labels from the augmentation aspect. Another avenue, graph environment inference [2]. has been explored deeper recently by GALA 20 which is conducive to LECI and future environment-based methods. We hope this work can shed light on the future direction of graph environment-centered methods.
10

---

Acknowledgements
This work was supported in part by National Science Foundation grants IIS-2006861 and IIS- 1908200.
References
[1] Mengying Sun, Sendong Zhao, Coryandar Gilvary, Olivier Elemento, Jiayu Zhou, and Fei
Wang. Graph convolutional networks for computational drug development and discovery. Briefings in bioinformatics, 21(3):9199935, 2020.
[2] Seth A Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin. Information network or social network? the structure of the twitter follow graph. In Proceedings of the 23rd International
Conference on World Wide Web, pages 493-498, 2014.
[3] Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning to simulate complex physics with graph networks. In International conference on machine learning, pages 8459-8468. PMLR, 2020.
[4] Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat seng Chua. Discovering invariant rationales for graph neural networks. In ICLR, 2022.
[5] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. International Conference on Machine Learning, 2022.
[6] Yongqiang Chen, Yonggang Zhang. Yatao Bian, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for out-of- distribution generalization on graphs. In Advances in Neural Information Processing Systems, 2022.
[7] Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. Debiasing graph neural networks via learning disentangled causal substructure. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httpss//pppencvvieeeeee/oouuoone http:///wweeeeeeeoommmemddddccdo
[8] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky.
training of neural networks. The journal of machine learning research, 17(1):2096 20300 2016.
[9] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- mization. arXiv preprint 19Xiv:1907.02880 2019.
[10] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph out-of-distribution benchmark. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL http://pppeneeiieeeeee//oommm/mo
[11] Haoyang Li, Ziwei Zhang. Xin Wang, and Wenwu Zhu. Learning invariant graph representa- tions for out-of-distributi generalization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.neeieee http://eeeeoomem/deeeeeeeaa/-e-e
[12] Nianzu Yang, Kaipeng Zeng, Qitian Wu, Xiaosong Jia, and Junchi Yan. Learning substructure invariance for out-of-distribution molecular representations. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, A Advances in Neural Information Processing Systems, 2022. URL
[13] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. arXiv preprint arXiv:2202.022 02466666..226...... 2022.
[14] David Krueger, Ethan Caballero, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. disttibuittiiitionn generalization via risk extrapolation (REx). In International Conference on Machine Learning, pages 5815- 5826. PMLR, 2021.
Jacobsen, Amy Zhang, Jonathan Binas,
[15] Masanori Koyama and Shoichiro Yamaguchi. When is invariance useful in an out-of- distribution generalization problem? arXiv preprint 2008:200..00888 2020.
[16] Yong Lin, Shengyu Zhu, Lu Tan, and Peng Cui. Zin: When and how to learn invariance without environment partition? Advances Neural Information Processing Systems, 35: 2022.
11

---

[17] Judea Pearl. Causality. Cambridge university press, 2009.
[18] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
[19] Xiner Li, Shurui Gui, Youzhi Luo, and Shuiwang Ji. Graph structure and feature extrapolation for out-of-distribution generalization, 2023.
[20] Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Does invariant graph learning via environment augmentation learn invariance? In Advances in Neural Information Processing Systems, 2023.
[21] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78(5):947-1012, 2016.
[22] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv: /9// 1.08731. 2019.
[23] Chaochao Lu, Yuhuai Wu, José Miguel Hermández-Lobato and Bernhard Schölkopf. In- variant causal representation learning for out-of-distribution generalization. In International Conference on Learning Representations, 2021.
[24]
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. The risks of invariant risk mini- mization. arXiv preprint arXiv:2010.05761 2020.
[25] Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip Yu. Generalizing to unseen domains: survey on domain general- ization. IEEE Transactions Knowledge and Data Engineering, 2022.
[26] Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiv:2007.0m 0..000004334 0144,,1444424 2020.
[27] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[28] Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, pages
PMLR, 2021.
[29] Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long-Kat Mai Huang, Tingyang Xu, Yu Rong. Lanqing Li, Jie Ren, Ding Xue, et al. DrugOOD: Out-of outoo--distribttion (OOD) dataset curator and benchmark for Al-aided drug discovery- focus on affinity prediction problems with noise annotations. arXiv preprint arXiv:2201.096
2022.
[30] Jivat Neet Kaur, Emre Kiciman, and Amit Sharma. Modeling the data-generating process is necessary for out-of-distribution generalization. arXiv preprint vxXiv:2206.07837 2022.
[31] Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Jean- -hnn-Chrittophe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of-distribution generalization. Advances in Neural Information Processing Systems, 34:3438-3450, 2021.
[32] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmae arXiv preprint 1:Xivv1611.011 144, 2016.
[33] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 (3(11))1339144 2020.
[34] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. ASAP: Adaptive structure aware pooling for learning hicrarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5470-5477. 2020.
[35] Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision, pages 443-450. Springer, 2016.
[36] Sergey N Dorogovtsev and Jose FF Mendes. Evolution of networks. Advances in physics, 51
(4):1079-1187, 2002.
12

---

[37] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[38] Hao Yuan. Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, arXiv preprint arXiv:2012.15445 2020.
[39] Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of-distribution generalization: A survey. arXiv preprint arXiv:2 /3624, 2021.
[40] John C Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378-1400 2021.
[41] Zheyan Shen, Peng Cui, Tong Zhang, and Kun Kunag. Stable learning via sample reweighting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5692-5699, 2020.
[42] Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. In International Conference on Machine Learning, pages 1804-6815 14. PMLR, 2021.
[43] Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1): 2016.
[44] Lisa Tomey and Jude Shavlik. Transfer learning. In Handbook of research on machine learning applications and trends: algorithms, methods, and techniques. pages 242-264. IGI global, 2010.
[45] Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1):43-76, 2020.
[46]
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey, Neurocomputing, 312:135- 153,, 2018.
[47] Yongqiang Chen, Wei Huang, Kaiwen Zhou, Yatao Bian, Bo Han, and James Cheng. Towards understanding feature learning in out-of-distributtin generalization. In Advances in Neural Information Processing Systems, 2023.
[48] Joaquin Quiñonero-Candele Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2008
[49] Jose Moreno Torres, Troy Raeder, Rocío Alaiz MaizzRooríguuez Nitesh Chawla, and Francisco Herrera. A unifying view dataset shift in classification. Pattern Recognition, 45(1): 521-530, 2012. ISSN 0031-3203, doi: https://doi. org//10. 101 101 pttp://ppco....... 201coog.21110 1.06..19 URL www.:e/eeeeeeeee..ooocccceeeeeee
1tt0:///////0003003333 1002901
[50] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
[51] Gerhard Widmer and Miroslav Kubat. Learning in the presence of concept drift and hidden contexts. Machine learning, 23111111- 1996.
[52] Sinno Jialin Pan, Ivor W Tsang, James Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. IEEE transactions on neural networks, 22(2):199-22 2010.
[53] Vishal M Patel, Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. Visual domain adaptation: A survey of recent advances. IEEE signal processing magazine, 32(3):53-69, 2015.
[54] Garrett Wilson and Diane J Cook. A survey of unsupervised deep domain adaptation. ACM Transactions on Intelligent Systems and Technology (TIST), 11(5):1-46, 2020.
[55] Yuqi Fang, Pew-Thian Yap. Weili Lin, Hongtu Zhu, and Mingxia Liu. fource-free unsupervised domain adaptation: A survey. arXiv preprint arXiv:2301.0022 1000005,,0 2022.
[56] Yuang Liu, Wei Zhang, Jun Wang, and Jianyong Wang. Data-free knowledge transfer: A survey. arXiv preprint arXiv:2112.15272 2021.
[57] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. International conference on machine learning, pages 97-105. PMLR, 2015.
13

---

[58] Guoliang Kang, Lu Jiang, Yi Yang, and Alexander G Hauptmann. Contrastive adaptation network for unsupervised domain adaptation. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognifion, pages 4893-49022 2019.
[59]
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference machine learning, pages 1180-1189. PMLR, 2015.
[60] Yi-Hsuan Tsai, Wei-Chih Hung, Samuel Schulter, Kihyuk Sohn, Ming-Hsual Yang, and Manmohan Chandraker. Learning to adapt structured output space for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7472-7481, 2018.
[61] Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, and Mario Marchand. romain-adversarn neural networks. arXiv preprint arXiv:1412.444 2014.
[62] Eric Tzeng, Judy Hoffman, Trevor Darrell, and Kate Saenko. Simultancous deep transfer across domains and tasks. In Proceedings of the IEEE international conference on computer vision, pages 4068-4076, 2015.
[63] Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE conference on computer vision and puttern recognition, pages 7167-7176, 2017.
[64] Weijie Chen, Luojun Lin, Shicai Yang, Di Xie, Shiliang Pu, and Yueting Zhuang. Self- supervised noisy label learning for source-free unsupervised domain adaptation. In 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 10185- 10192. IEEF, 2022.
[65] Xinyu Liu and Yixuan Yuan. A source-free domain adaptive polyp detection framework with style diversification flow. IEEE Transactions on Medical Imaging, 41(7):1897-1988, 2022.
[66] Guanglei Yang, Hao Tang, Zhun Zhong, Mingli Ding, Ling Shao, Nicu Sebe, and Elisa Ricci. Transformer- based source-free domain adaptation. arXiv preprint arXiv:2105.14133, 2021.
[67] Hu Yu, Jie Huang, Yajing Liu, Qi Zhu, Man Zhou, and Feng Zhao. Source-free domain adaptation for real-world image dehazing. In Proceedings of the 30th ACM International Conference on Multimedia, pages 6645-6654, 2022.
[68] Masato Ishii and Masashi Sugiyama. Source-free domain adaptation via distributional align- ment by matching batch normalization statistics. arXiv preprint arXiv:2101. 10842, 2021.
[69] Xiaofeng Liu, Fangxu Xing, Chao Yang, Georges El Fakhri, and Jonghye Woo. Adapting off-the-shelf source segmenter for target medical image segmentation. In Medical Image Computing and Computer Assisted Intervention Citereentio--MCCCAT 2021: 24th International Conference, Strasbourg, France, September 27-October 1, 2021, Proceedings, Part I1 24, pages 549-559. Springer, 2021.
[70] Jiahao Fan, Hangyu Zhu, Xinyu Jiang, Long Meng, Chen Chen, Cong Fu, Huan Yu, Chenyun Dai, and Wei Chen. Unsupervised domain adaptation by statistics alignment for deep sleep staging networks. IEEE Transactions Neural Systems and Rehabilitation Engineering, 30: 205-216, 2022.
[71] Cian Eastwood, Ian Mason, Christopher KI Williams, and Bernhard Schölkopf. Source- free adaptation to measurement shift via bottom-up feature restoration. arXiv preprint arXiv:2 2021.
[72] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain generalization. In Proceedings of the IEEE international conference on computer
vision, pages 5542-5550, 2017.
[73] Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In International conference machine learning, pages 10-18.
PMLR, 2013.
[74] Aniket Anand Deshmukh, Yunwen Lei, Srinagesh Sharma, Urun Dogan, James W Cutler, and Clayton Scott. A generalization error bound for multi-class domain generalization. arXiv preprint arXiv:1905. 10392, 2019.
[75] Xingxuan Zhang, Linjun Zhou, Renzhe Xu, Peng Cui, Zheyan Shen, and Haoxin Liu. NICO++: Towards better benchmarking for domain generalization. arXiv preprint arXiv:2204.08 08040, 2022.
14

---

[76] Yongqiang Chen, Kaiwen Zhou, Yatao Bian, Binghui Xie, Bingzhe Wu, Yonggang Zhang, MA KAILI, Han Yang, Peilin Zhao, Bo Han, and James Cheng. Pareto invariant risk min- imization: Towards mitigating the optimization dilemma in out-of-distribution generaliza- tion. In The Eleventh International Conference on Learning Representations, 2023. URL.
http://ppnneviieweee//foooooeeee Sittoorummmmi-eSSSSt OpSL.
[77] David Heckerman. A tutorial on learning with Bayesian networks. Springer, 1998.
[78] Yimeng Chen, Ruibin Xiong, Zhi-Ming Ma, and Yanyan Lan. When does group invariant learning survive spurious correlations? Advances in Neural Information Processing Systems, 35:7038-7051, 2022.
[79] Alvaro Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks learnable physics engines for inference and control. In International Conference on Machine Learning, pages 4470-4479. PMLR, 2018.
Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin
[80] David Barrett, Felix Hill, Adam Santoro, Ari Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks. International conference on machine learning, pages 511-520. PMLR, 2018.
[81] David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv: 3rXiv:1904.01533 2019.
[82] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information
processing systems, 29, 2016.
[83] Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gnns. Advances in Neural Information Processing Systems, 33:15811 13:15811-55822, 2020.
[84] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. arXiv preprint arXiv: 1et.199909.9,, 2019.
[85] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanic Jegelka. What can neural networks reason about? arXiv preprint arXiv:1905. 13211, 2019.
[86] Yongqiang Chen, Han Yang. Yonggang Zhang, MA KAILI, Tongliang Liu, Bo Han, and James Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In International Conference Learning Representations, 2022. URL https://openneview.neel forum?idd=kKMGGcccii
[87] Cong Fu, Xuan Zhang, Huixin Zhang, Hongyi Ling, Shenglong Xu, and Shuiwang Ji. Lattice convolutional networks for learning ground states of quantum many-body systems, 2022.
[88] Meng Liu. Cong Fu, Xuan Zhang, Limei Wang, Yaochen Xie, Hao Yuan, Youzhi Luo, Zhao Xu, Shenglong Xu, and Shuiwang Ji. Fast quantum property prediction via deeper 2d and 3d graph networks, 2021.
[89] Xuan Zhang. Limei Wang, Jacob Helwig, Youzhi Luo, Cong Fu, Yaochen Xie, Meng Liu, Yuchao Lin, Zhao Xu, Keqiang Yan, Keir Adams, Maurice Weiler, Xiner Li, Tianfan Fu, Yucheng Wang, Haiyang Yu, YuQing Xie, Xiang Fu, Alex Strasser, Shenglong Xu, Yi Liu, Yuanqi Du Alexandra Saxton, Hongyi Ling, Hannah Lawrence, Hannes Stärk, Shurui Gui, Carl Edwards, Nicholas Gao, Adriana Ladera, Tailin Wu, Elyssa F. Hofgard, Aria Mansouri Tehrani, Rui Wang, Ameya Daigavane, Montgomery Bohde, Jerry Kurtin, Qian Huang, Tuong Phung, Minkai Xu, Chaitanya K. Joshi, Simon V. Mathis, Kamyar Azizzadenesheli, Ada Fang, Alán Aspuru-
Erik Bekkers, Michael Bronstein, Marinka Zitmik, Anima Anandkumar, Stefano Ermon, Pietro Liò, Rose Yu, Stephan Günnemann, Jure Leskovec, Heng Ji, Jimeng Sun, Regina Barzilay, Tommi Jaakkola, Connor W. Coley, Xiaoning Qian, Xiaofeng Qian, Tess Smidt, and Shuiwang Ji. Artificial intelligence for science in quantum, atomistic, and continuum systems, 2023.
[90] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint arXiv:2009, /1848, 2020.
[91] Chenxiao Yang. Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. arXiv preprint (tt::22222099033. 2022.
15

---

[92] Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and gener- alization in graph neural networks. Advances in neural information processing systems, 32. 2019.
[93] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11975-11986. PMLR, 2021.
[94] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning, pages 837-851. PMLR, 2021.
[95] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.1000 2019.
[96] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 13:5812-5823, 2020.
[97] Yiwei Wang. Wei Wang, Yuxuan Liang. Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pages 3663-3674, 2021.
[98] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNEx- plainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[99] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019.
[100] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: 13666 2019.
[101] Shurui Gui, Hao Yuan, Jie Wang, Qicheng Lao, Kang Li, and Shuiwang Ji. Flowx: Towards explainable graph neural networks via message flows. arXiv preprint arXiv:2206. 02122206..9777 /2987, 2022.
[102] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
[103) Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, pages 12241-12252. PMLR, 2021.
[104] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 430-438, 2020.
[105] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems, 35:4805-48117 2022.
[106] Xu Chu, Yujie Jin, Xin Wang. Shanghang Zhang, Yasha Wang, Wenwu Zhu, and Hong Mei. Wasserstein barycenter matching for graph size generalization of message passing neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 6158 6184. PMLR, 23-29 Jul 2023.
[107] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: a benchmark for molecular machine learning. Chemical science, 9()::133-530 2018.
[108] Guy W Bemis and Mark A Murcko. The properties of known drugs. 1. molecular frameworks. Journal of medicinal chemistry, 39(15):2887-2893, 1996.
[109] Michael Zhang, Nimit S Sohoni, Hongyang R Zhang, Chelsea Finn, and Christopher Ré. Conrect-n-contrast: contrastive approach for improving robustness to spurious correlations. arXiv preprint 22X3v:2203.01512 2022.
16

---

[110] Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physies/0004057, 2000.
[111] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pages 1-5. IEFE, 2015.
[112] Hongyang Gao and Shuiwang Ji. Graph U-nets. In international conference on machine
learning, pages
PMLR, 2019.
[113] Meng Liu, Haiyang Yu, and Shuiwang Ji. Your neighbors are communicating: Towards powerful and scalable graph neural networks. hutps//ursivvoor//bb22266 02059, 2022.
[114] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[115] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL htwp:pppaeeiiee..e//ooummmr/ryrr
[116] Petar Veličković, Guillem Cucurall, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Represen- tations, 2018. URL http::/ppweeeeeeeeeeee/////d/ddd
accepted as poster.
[117] Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui. Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, et al. DIG: a turnkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240): 2021.
[118] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272 PMLR, 2017.
[119] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[120] Hongyang Gao, Yi Liu, and Shuiwang Ji. Topology-aware graph pooling networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(12):4512-4511 2021.
[121] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:1 13660-13327,, 2020.
[122] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6991 6980, 2014.
[123] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performane deep learning library. Advances in neural information processing systems, 32, 2019.
17

---

Appendix of LECI
Contents
Broader Impacts
19
Related works
19
B.
Extensive background discussions
19
B.2
Environment information: significance and fairness discussion
20
B.3
Comparisons to previous environment- based graph OOD methods
Theory and discussions
23
Proofs
23
Theory and assumption comparisons with previous graph OOD methods
24
Two precision challenges discussion
25
How the subgraph selector keep invariant under distribution shitts?
26
Challenges and Limitations
27
D LECI implementation details
28
D.I
The architecture of subgraph selector
28
D.2 The architecture of the pure feature shift consideration
28
D.3
LECI's training strategy
28
Detailed experiment settings
29
Fairness discussion
29
Datasets
29
................................
E.3
Baseline selection justification and discussion
................................
30
Training settings
................................
E.5
Hyperparameter sweeping
31
E.6
Software and hardware
32
Supplimentary experiment results
32
A second look at the ability to address structure and feature shifts.
32
Interpretability visualization results
33
18

---

A Broader Impacts
ditoof-distribution (OOD) generalization is a persistent challenge in real-world deployment scenarios, especially prevalent within the field of graph learning. This problem is heightened by the high costs and occasional infeasibility of conducting numerous scientific experiments. Specifically, in many real-world situations, data collection is limited to certain domains, yet there is pressing need to generalize these findings to broader domains where executing experiments is challenging. By approaching the OOD generalization problem through lens of causality, we open a pathway for integrating underlying physical mechanisms into Graph Neural Networks (GNNs). This approach harbors significant potential for wide-ranging social and scientific benefits.
Our work upholds ethical conduct and does not give rise to any ethical concerns. It neither involves human subjects nor introduces potential negative social impacts or issues related to privacy and fairees.. We have not identified any potential for malicious or unintended uses of our research. Nevertheless, we recognize that all technological advancements carry inherent risks. Hence, advocate for continual evaluation of the broader impacts of our methodology across diverse contexts.
B Related works
B.1 Extensive background discussions
cut-of-Distributii (OOD) Generalization.
(OOD) Generalization [39
addresses the challenge of adapting a model, trained one distribution (source), to effectively process data from a potentially different distribution (target). It shares strong ties with various areas such as transfer learning 45 domain adaptation (46), domain generalization 23). causality 17 18) invariant learning 19), and feature learning [47] As a form of transfer learning, OOD generalization especially challenging when the target distribution substantially differs from the source distribution. OOD generalization, also known as distribution or dataset shift [48] 49], encapsulates several concepts
including covariate shift (50), concept shift [51), and prior shift 48 Both Domain Adaptation (DA) and Domain Generalization (DG) can be viewed as specific instances of OOD, each with its own unique assumptions and challenges.
Domain Adaptation (DA). In DA scenarios (2-56), both labeled source samples and target do- main samples accessible. Depending the availability of labeled target samples, DA can be categorized into supervised. semi-supervised, and unsupervised settings. Notably, unsupervised domain adaptation methods [ 33 71 have gained popularity they only necessitate unlabeled target samples. Nonetheless, the requirement for pre-collected target domain samples is a significant drawback, it may be impractical due data privacy concerns the necessity retrain after collecting target samples in real-world scenarios.
Domain Generalization (DG). DG 25 72 [4] strives to predict samples from unseen domains without the need for pre-collected target samples, making more practical than DA in many circum- stances. However, generalizing without additional information is logically implausible, a conclusion also supported by the principles of causality [7 18] (Appx. B.2 As a result, contemporary DG methods have proposed the use of domain partitions 8 75 generate models that are domain- invariant. Yet, due to the ambiguous definition of domain partitions, many DG methods lack robust theoretical underpinning.
Causality & Invariant Learning. Causality 17
18 21 and invariant learning 2 provide theoretical foundation for the above concepts, offering a framework to model various distribution shift scenarios as structural causal models (SCMs). SCMs, which bear resemblance to Bayesian networks [77]. are underpinned by the assumption of independent causal mechanisms, a fundamental premise in causality. Intuitively, this supposition holds that causal correlations in SCMs are stable, independent mechanisms akin to unchanging physical laws, rendering these causal mechanisms generalizable. An assumption of data-generating SCM equates to the presumption that data samples are generated through these universal mechanisms. Hence, constructing model with generalization ability requires the model to approximate these invariant causal mechanisms. Given such a model, its performance is ensured when data obeys the underlying data generation assumption.
76
Peters et al. 21 initially proposed optimal predictors invariant across all environments (or inter- ventions). Motivated by this work, Arjovsky et al. [
proposed framing this invariant prediction
19

---

concept as an optimization process, considering one of the most popular data generation assumptions,
78 reffereed to as invariant learn- environments 21 as environment variable in SCMs. When these environment variables are viewed as domain indicators, becomes evident that this SCM also provides theoretical support for DG, thereby aligning many invariant works with the DG setting. Besides PIIF, many works have considered FIIF and anti-causal assumptions [24] 31 78). which makes these assumptions popular basics of causal theoretical analyses. When we reconsider the definition of dataset shifts, we can also define the covariate data generation assumption, as illustrated
PIIF. Consequently, numerous subsequent works [23 24 ing- iig-considered the initial intervention-hane
31
in Fig. D where the covariate assumption is one of the most typical assumptions in DG 25
Graph OOD Generalization. Extrapolating on non-Euulidean data has garnered increased attention, leading to variety of applications 89] Inspired by Xu et al. [90]. Yang et al. [9] proposed that GNNs intrinsically possess superior generalization capability. Several prior works (92 explored graph generalization in terms of graph sizes, with Bevilacqua et al. [94] being the first to study this issue using causal models. Recently, causality modeling- based methods have been proposed for both graph-level tasks 477 [2] and node-level tasks [13. However, except for CIGA [6], their data assumptions are less comprehensive compared to traditional OOD generalization. CIGA, while recognizing the importance of diverse data generation assumptions (SCMs), misses the significance of environment information and attempts to fill the gap through non-trivial extra assumptions, which
we will discuss in Appx. BB2 and C.2
Additionally, environment inference methods have gained traction in graph tasks, including EERM [3]. MoleOOD [12), and GIL. [I]]. However, these methods face two undeniable chal- lenges. First, their environment inference results require environment exploitation methods for evaluation, but there are no such methods that perform adequately on graph tasks according to the synthetic dataset results in GOOD benchmark [0]. Second, environment inference is essentially a process of injecting human assumptions to generate environment partitions, as we will explain in Appx. B. but these assumptions are not well compared. Hence, this paper can also be viewed as work that aids in building better graph-specific environment exploitation methods for evaluating environment inference methods. Although we cannot directly compare with EERM and MoleOOD due to distinct settings, we strive to modify GIL and compare its environment exploitation method (IGA [5]) with ours under the same settings in Appx. B.
Graph OOD Augmentation. Except for representation learning, graph augmentation is also a promising way to boost the model's 'ss generalizability. While previous works focus on random or inter- polation augmentations (95) Li et al. [99 recently explored enviromment-directed extrapolating graphs in both feature and non- Bun-iuelid spaces, achieving significant results, which sets a solid foundation and renders a promising future data-centric direction, especially in the circumstance of the popularity of large language models.
Relation between GNN Explainability/IIterreeen
and Graph OOD Generalization. GNN 10- aims to explain GNNs from the input space, whereas GNN interpretability research 4.
explainability research [38]
5 102 seeks to build networks that are self-explanatory. Subgraph explanation 103 104 is one of the most persuasive ways to explain GNNs. Consequently, subgraphs
have increasingly become the most natural components to construct graph data generation process, leading to subgraph- based graph data generation SCMs (6, inspired by general OOD SCMs [31].
Comparisons to the previous graph OOD works It is worth mentioning that compared to previous works DIR 4 and GSAT [5), we do not propose new subgraph selection architecture, instead, we propose a learning strategy that can apply to any subgraph selection architectures. While DIR defines their invariance principle with a necessity guarantee, they still cannot tackle the two subgraph discovery challenges (Appx. C.2) and only serve for the FIIF SCM. In contrast, we provide both sufficiency and necessity guarantees to solve the two subgraph discovery challenges under three data generation assumptions. We provide more detailed comparisons in terms of theory and assumptions in Appx. C.2
B.2 Environment information: significance and fairness discussion
In this section, we address three pivotal queries: Q1: it feasible to infer causal subgraphs Ge devoid of environment information (partitions)? Q2: How do environment partitions generated by
20

---

environment inference methods ITE 28 compare to those chosen by humans? Q3: Are the experimental comparisons in this paper fair?
QI. As depicted in Fig. I Gg intrinsically correlates with multiple variables, namely, Gs. Y, and G. Similarly, Ge has correlations with Gs, Y, and G. Absent an environment variable F, Gc. and Gş can interchange without any repercussions, rendering them indistinguishable. Prior graph OOD methods have therefore necessitated supplementary assumptions aid the identification of Gc and Gg. such as the latent separability H (GclY) < H())) outlined by Chen et al. [6. However, both (G))YY) & H(GslY) and its converse (G)l)) 2 H(G)lY) 7 can be easily breached in real-world scenarios. Thus, without environment partitions, achieving OOD generalization is impracticable without additional assumptions.
Upon viewing environment partitions as a variable (Fig. D. the environment variable effectively acts instrumental variable [17] for approximating the exclusive causation between Gs and G. Consequently, we can discern the causal mechanism Gs - G through E, thereby distinguishing between Ge and Gg. We discuss our proposed method and analysis, grounded in intuitive statisties and information theory, in our main paper's 's method section 3
Q2. ZIN [66,, recent work, aptly addresses this question. Lin et al. [16] demonstrate that without predefined environment partitions, there can be multiple environment inference outcomes, with differ- ent outcomes implying unique causal correlations. This implies that absent prearranged enviromment partitions, causal correlations become unidentifiable, leading to conflicting environment inference solutions. Thus, guaranteeing environment inference theoretically is possible only via the of other environment partition equivalent information or through the adoption of plausible assumptions. Therefore, these two factors, extra information, and assumptions, are intrinsically linked, they serve as strategies for integrating human bias into data and models.
Q3. Building upon the last two question discussions, for all methods 6 1 that offer theoretical guarantees, they utilize different forms of human bias, namely, environment partitions or assumptions. Whilst numerous graph OOD methods compare their assumptions, our work demonstrates that simply annotated environment partitions outperform all current sophisticated human made assumptions, countering Yang et al. [12)ss belief that environment information graphs is noisy and difficult to utilize. Therefore, the comparisons with ASAP (34,. DIR [4], GSAT [5]. and CIGA [6] underscore this point. Additionally, through comparisons conventional environment exploitation methods (IRM 191. VREx [14), etc.) in Sec. 4 and the comparison to the environment exploitation phase of GIL 111 (i.e., IGA [5) provided in Appx. B.3] we empirically validate that LECI currently surpasses all other environment exploitation methods in graph tasks. Therefore, our experiments justly validate these claims without engaging any fairness issues.
B.3 Comparisons to previous environment-base graph OOD methods
In this section, we detail comparisons with prior environment-base graph OOD methods from both qualitative and quantitative perspectives. Firstly, we establish that we propose an innovative graph- specific environment exploitation approach. Secondly, focus comparing only the environment exploitation phase of previous work, discussing the methods chosen for comparison and the rationale.
B.3.1 Claim justifications: the innovative graph-specific environment exploitation method
Motivations. The motivation for our work stems from the fact that general environment exploitation methods have been found wanting in the context of graph-based cases, leading to our development of a graph-specific environment exploitation method. We demonstrate significant improvement with the introduction of this method. Subsequently, we justify LECI innovative graph-specific environment exploitation technique.
Justifications. An environment based method usually comprises two phases: environment inference and environment exploitation. Environment inference aims to predict environment labels, while environment exploitation leverages these labels once they are available. The relationship between these two phases not reciprocal; an environment inference method may employ an environment exploitation method to assess its performance, but the converse is not true.
21

---

Recent environment inference methods at the graph level [2 and even the node level [13 do not incorporate graph-specific environment exploitation techniques. Our method, LECI, differs this respect, as shown in the table below:
Table 4: Comparison of Characteristics to Previous Environment- Based Graph OOD Methods.
Method
Environment Inference
Environment Exploit
MolcOOD 12
Not Graph- Graph-Specific
Not
GIL [
Not Graph-Speciffs
EERM 3 (Node-Level)
Graph-Specific
Not Graph-Specific
Ours (LECI)
N/A
Graph-Specife
The criterion determine if an environment exploitation method is graph-specific is whether the environment partition assistant is directly applied to graph-specific components (adjacency matrix: Ac, As) rather than common hidden representations.
This assessment can also be based on a replacement test: does the environment exploitation optimiza- tion remain valid after replacing G and GNN with feature vectors X and MLP?
As shown in Eq. 9 when we replace Equation (7) MoleOOD [2], Equation (8) GIL Equation (5) in EERM 13 with the following optimization objectives:
and
MoleOOD:
Σ
|log go X) - p()x)) (logpr (v x,e)]]
|
(X.w)xX'
+ BE
lolo (y x)]
(9a)
[
(X.))x
GIL::
E (eesupp(Sinnfrr
R (*()(X) Y; A trace (Var Einfer (VoR.))
(9b)
K
EERM: min Var ([I Y;0) : 1 1 k + K
(x Y
(9c)
0
k=1
Iw (G) is replaced with X (samples from environment kt) since Iwg betongs to the environment inference phase. These three optimizations remain valid, thereby suggesting environment exploitation methods in [133 are not graph-specific. Note that this does negate the graph-specific nature of their environment inference phases and network designs. For example, while GIL employs subgraph discovery networks as a basic generalization architecture, its invariant learning loss does not leverage this specialized architecture. as shown in Eq. 9b)
where 0, r are MLP parameters 9a f()) is MLP Eq. 9c
In contrast, substituting G with X in environment optimization leads to problems. For instance, terms such Xc, and operations like XG X and X X -Xc would need redefinition; also, the mapping from (X, A)c to X is not unique. Hence, this optimization is inherently graph-specific.
Therefore, LECI emerges an innovative graph-specific environment exploitation method that offers clear diffcrentiation from previous environment-baat based graph OOD methods. It could be considered appropriate to claim that LECI is the first of its kind in the realm of graph-specific environment exploitation.
B.3.2 Environment exploitation quantitative comparisons
In this section, compare to the environment-basee graph OOD baseline GIL [ since its original implementation is on subgraph discovery network similar to the subgraph discovery network [5] we adopt. Since MoleOOD [[2] has design specific for molecules without using subgraph discovery networks, and EERM [3] is tackling node-level tasks, their settings are too different to be fairly compared with method.
To conduct fair comparison, we replace GIL's subgraph discovery architecture with GSAT 5 to
ensure LECI and GIL are measured under the same network structure. Since GIL applics IGA 15
22

---

as its invariant learning regularizer (environment exploitation method), we adopt the official IGA implementation from Domainbed [8] The hyperparameter sweeping space is strictly aligned with the original GII. paper, i.e. (10-1, 10-3, 10-"). After 3 runs with different random seeds, we have the following OOD validated test results on Motif-base, Motif-size, CMNIST, GOOD-SST2, GOOD-Twiteer, GOOD-HIV-scall
GOOD-HIV-size and DrugOOD-assay.
Table 5: Environment exploitation phase comparisons: Sanity checks
Sanity checks
Motif-base
Motif-size
CMNIST
GIL (IGA) LECI
55.99(3.62)
38.39(3.38) 71.43(1.96)
54.59(4.99)
84.56(2.22)
51.80(2.70)
Table 6: Environment exploitation phase comparisons: Real-world
Real-world
GOOD-SST2
GOOD-Twitter GOOD-HIV-scaffold GOOD-HIV-size
DrugOOD-assa
GIL (IGA)
75.04(5.24)
60.01(0.47)
71.27(1.69) 74.43(1.69)
62.27((0.91)
73.20(0.12) 73.45(0.17)
LECI
83.44(0.27)
59.64(0.15)
65.44(1.78)
The results indicate that except on Twitter, GIL produces sub-optimal results compared to LECI.
C Theory and discussions
In this section, will first provide theoretical proofs of the relaxed independence property. Proposi- tion 3.3] Lemma 3.4 Lemma 3.5 Lemma 3.6 Theorem 3.7 and Theorem 3.8 Then, we provide specific challenge-solvingg assumption comparisons for previous graph OOD methods. Subsequently, we will discuss the subgraph discovery challenges and the subgraph selector invariance. Finally, we will provide the current challenges, limitations, possible solutions, and future directions under the subgraph modeling data generation assumptions.
C.1 Proofs
C.1.1 Relaxed independence property
Proposition C.1. For any Gp that Gs S Gp, I(Gs;Y) < I(G,;))
Proof. T(Gs; Y) s I(Gp; Y) is equivalent to H(Y)Gs) 2 H(Y where H denotes entropy. since H(Y) is constant. We consider random graph Gs consisting of set of random variables (edges) Ag. Gg C Gp means G,'s " set of random edges Ap superset of As. i.e., A, As U A4, where A4 is the set of additional edges in Ap. Therefore, HY))ss) = H( (Y))))) = HYY)),) i.e., (Gs; Y()
C.1.2 Proof of Proposition
3.
Proposition C.2. Denoting KL-divergence KL(-Il-), 0 fixed, the optimal discriminator og is 6E. s.f.
KL [P(E (E)GG)) =
(10)
Proof. Since given fixed 0, I(E; Gc) and H(E) are both constant. Therefore, we have
0 arrgmin d
E [og Pog (EIGo)
Ceamiin,,I((EGrrr E log Pon Por (EICo) (EIGO)) H(E) =argmin, b
(11)
=argmin KI. Po
23

---

C.1.3 Proof of Lemma 3.4
Lemma C.3. Given a subgraph Gp of input graph G and SCMs (Fig. 7. it follows that Gp S Gc if and only if Gp 11 E.
Proof. (=) Contradiction: If Gp S Go. but Gp is not independent to E.i.., [(E; Gy) 0. Since [EE; Gc) 2 I(E; Gp) (this is trivial because Gp is a subset of Gc), we obtain [(E; Gc) > 0, which contradicts to the fact that Ge 11 E.
(+) Contradiction:
Gp I1 E but Gp not a subgraph of Ge; i.e., 3 non-trivial (not empty) G S Gp. s.t. Gg S Gs. According to the three SCMs, Gg is not independent of E; thus, Gp is not independent of E, which contradicts the premise.
Since KL P(E)Ge)) (E))C) 2 O, when dR = 6'g. KL PPEEGG)))P reaches its
minimum 0.
C.1.4 Proof of Lemma 3.5
Lemma C.A. Given SCMs (Fig. D. the predicted Gc fo(G), and the EA training criterion (Eq.
Go S Ge if and only i 0%
Proof. E @g is equivalent to = arg ming [EE; Gc), which indicates I(E; = when 0 E Or. Since according to Lemma 3.4 we have Ge S Gc if and only if Go 1L E, while
T(E; Gc) 0 if and only if Ge II E, follows that Gc C Gc if and only if e Og.
C.1.5 Proof of Theorem 3.7
Theorem C.5. Under the covariate SCM assumption and both EA and LA training criteria (Eq. 6 and 7, it follows that Gc = Go if and only if E 0 n n
Proof. Under the covariate SCM assumption, Lemma 3.6 satisfied. According Lemma 3.5 and 3.6 EA and LA are both optimized (0 O n Q if and only if Go S Gc and Gs Gs. Since Gss Gs S Gg equivalent Ge S Gg. These two inclusive relations Gc S Gc and Gc S Gc imply Ge = Gc. Therefore, we obtain our conclusion that G Ge if and only EA and LA both reach their optimums.
Ge G Gs and Ge =
C.1.6 Proof of Theorem 3.8
Theorem C.6. Given the covariate/FlIF/PI11 SCM assumptions and both EA and LA training criteria (Eq. 77. follows that Gc Gc if and only if. under the optimal EA training, the LA criterion is optimized, 0 E arg max {minoz Li}.
Proof. According to Lemma 6 we have GG under the optimal EA training. Recall the relaxed property: for any Gp that Gs Gp. T(Gg; Y) & I(G Y), which is valid under the three SCMs 1 Under the premise of Go JL E that is equivalent to Gs S Gs, we take the relaxed property into account, i.e., for G. that Gs S Gg. we have I(Gs;Y) < Y) Therefore, when we apply the LA training criterion under the optimal EA training, the mutual information I [(Gs; Y) can be minimized to be Gg Gs. i.e., Go Gc-
C.2 Theory and assumption comparisons with previous graph OOD methods
Many recent graph OOD learning strategies 4 adopt interpretable subgraph selection architectures. but our method is distinct from them in terms of the data generation assumptions, motivated challenges, and invariant learning strategy. To further investigate the key reason behind the LBCI's OOD generalization ability, in Tab. 7 we provide clear comparison with recent OOD generalization methods w.r.f. the subgraph discovery challenges introduced See. 3.2 Specifically, DIR [ proposes to learn causal subgraphs with adaptive interventions. However, its architecture requires the

---

Table 7: Comparison of related methods addressing the two challenges. We compare the problem-solvine capabilities of our proposed method, LECI, with prior methods and the two com- ponents of LECI. In the table, check marks (v) denote that the method is capable of addressing the challenge. Cross marks (X) indicate that the method is unable to solve the problem, or the preconditions nearly impossible to be satisfied. Exclamation marks (!) imply that the method can alleviate the problem under restricted assumptions.
Method
DIR
GSAT
CIGAvI
CIGAv2
E IL Gc
Y
Gs
LECI
Precision
x X
X
X
Precision 2
X
X
X
pre-selected size information of the true causal subgraphs. It proposes solve subgraph discovery challenges under the FIIF assumption, but it fails to provide a sufficient condition of its theoretical guarantees. GSAT [5] proposes to use information constraints to select causal subgraphs under only the FIIF assumption. Its invariant guarantee relies on the anti-causal correlation y- Gc, iee, given Y. Gc should be unique, which does not hold in the general scenario where each class can have multiple modes. CIGA [6] is the first graph OOD method that can work on both FIIF and PIIF assumptions. However, CIGAvI admits the limitation of the requirement of the size of true causal subgraphs, which is not practical even with human resources. CIGAv2 tries to achieve invariant predictions without the requirement of the true size information, but it, instead, requires an implicit assumption of the independence between the selected spurious subgraphs and the non-selected spurious subgraphs (denoted as Gy and G in CIGA), according to the equation (34) in its appendix. This assumption, named as independent components assumption, though weaker than the requirement of IIGAvI, I, still limits its applications, because E, as the confounder of all elements in Gs, can destroy this independence from a finer modeling perspective. Additionally, except for the data generation assumptions (FIIF and PIIF), it requires invariant feature assumption (GG Y) HGGs|Y), However, both H (Gc (Y) S (GY and its converse H (G 2 HY)) 7 can be easily breached in real-world scenarios. Note that, for simplicity, under the subgraph-base data generation assumptions, we slightly abuse Ge and G5 as the latent causal and non-causal factors C' and S.
Learning from the limitations of previous works, LECI is an innovative and effective method that addresses the problem of OOD generalization in graphs by exploiting environment information and learning causal independence. Specifically, LECI addresses the two subgraph discovery challenges by introducing two independence properties as TL Ge and Y IL Gs. By simultancously addressing these challenges, LECI is able to alleviate the two precision problems under the three data generation assumptions. This makes LECI a unique and promising approach for OOD generalization in graph data.
Assumption comparisons. As we have compared previous works on subgraph discovery ability, to avoid possible confusion, we further provide a clear comparison in Tab. X with respect to data generation assumptions (SCMs), theory, and theoretical guarantees. We would like to argue that simple annotated/ /groupedd environment partitions are strong enough to outperform many sophisticated human-designed assumptions.
Table 8: Assumption comparisons.
Methods
SCMs
Theory
Guarantecs
Extra information (aseumptions))
DIR GSAT CIGA+1
Ga|Ge Information bottleneck
Necessity
subgraph size assumption (TSSA)
Sufficiasey Nocessity
Reversible grodictorr assumption
PHI
Intrechess similurit
Sufficiency & Nocessity
TSSA
CIGAV2 FRF & PHF
Intr-ellass similarity
Sufficimey & Necessity N(GGl)) S. HGGalY) & independent components assumption Enviromment partiions
LECI
FIPP& PIP
Two independence & relased property
Sufficiency & Necessity
C.3 Two precision challenges discussion
Under the subgraph-basee graph modeling, it is obvious that the two precision challenges should be solved simultaneously to achieve invariant GNNs; thus, we argue that these two challenges should be analyzed and compared explicitly. While many previous works rely on unilateral causal analysis without discussing and comparing assumptions explicitly, we strive to compare them in the last subsection.
25

---

In this section, we would like to share a failure case to discuss the reasons behind the difficulty of solving the two subgraph discovery challenges. To be more specific. the difficulty may hide in the design of subgraph discovery architecture, e.g., maximizing mutual information T(Y: Gc) can be much less effective than expected. Generally, it is reasonable to believe that the invariant predictor Jinv in Fig. 2 is able to solve the second precision challenge by maximizing the mutual information between the selected subgraph and the label, i.e., I[Y; Gc). This is because maximizing [ GG) is approximately equivalent to minimizing [(;; Gs), i.e., enforcing Gs to be independent of Y. This belief, however, does not hold empirically according to the ablation study in Sec. 4.4 where the subgraph discovery network with only the solution of the first precision problem (EA) fails to generalize. Intuitively, the subgraph selector fo differentiable, but due to its discrete sampling nature. there are many undefined continual states, e.g., the middle states of the existence of an edge. These undefined states will hinder the effectiveness of gradients propagated to the subgraph selector. As result, the invariant predictor can hardly implicitly access the label-correlate information from the unselected part Gs through gradients. This implies that training the invariant predictor alone is not sufficient to address the second precision challenge without support from the Gg side. Therefore, to explain LECI's success intuitively, we can consider Juv and gL as the two information probes from both Go and Gs sides so that we exploit information from both sides to fully support maximizing T(Y;
From the perspective of the LECI optimization, each subgraph discovery challenge has verifiable and unverifiable optimization targets. The unverifiable descriptions include (1) G3 fails cover Gs: (2) Gc fails to cover Gc. These unverifiable descriptions cannot be formed as optimization objects because it is impossible to verify whether one can cover all information unless one enumerates the whole search space. Therefore, we adopt the verifiable objectives (1) Gc contains parts of G and (2) Gg contains parts of Gc.
C.4 How can the subgraph selector keep invariant under distribution shifts?
We discuss this question from two aspects: (1) Can subgraph selector fe recognize Ge with unseen Gs? (2) Will subgraph selector fe be misled to recognize parts of unseen Gg as Gc?
This discussion is under the following assumptions and conditions:
Causal subgraph equal support assumption (CSES): Both per (Gc) and ple have
the same support, where P(Gc) > O.
Assume fe is a K -layerr message passing neural network that only captures K K-hop subgraph information. Theoretically, we have an optimal injective K K-hop subgraph classifier that can distinguish all K-hop subgraphs. This implies only the same K Khhop subgraphs can produce the same result by this classifier, while similar subgraphs cannot.
Architecture:
Information sufficiency: Assume K be certain value that K K-hop subgraphs are large enough to cover Gc.
(1) In essence, Jo operates as a classifier. When provided with an edge, it classifies the associated ego-graph of the edge into either label (when the central edge is part of Ge label 0 (otherwise). We denote the distribution of K-hop ego-graphs on the edges of Ge as P(G C ), and the K-hop ego-graph space as gK_ Therefore, we have fo GK + {0, 1}. where AG E fo = when and only when P(G = GK) > 0, i.e., the distribution of so is only affected by the support of P(G The CSES assumption support. This ensures that Go with unseen Gs can still be recognized. Note that when K is smaller, the assumption is looser. In contrast, when K + +00, this assumption is equivalent to that (*r(G) and pte (G) have the same support, which is stringent. Therefore, K is the "locality rate" for us to loosen global equal support requirement local one.
be relaxed to that P'T(G() and Pt have the same
(2) To answer the second question, we will prove the following proposition:
Proposition C.7. There not a K K-hop subgraph that shares across P(Gc) and pte (Gs)
Proof. Contradiction:
26

---

Edge mask
GNN
Edge Embeddings
MLP
Gumbel
Gc
Sigmeid
G
Ac
Subgraph selection
Figure 6: The architecture of subgraph selector fe-
Given the aforementioned assumptions, suppose there is K K-hop subgraph that shares across P(Gc) and pte (Gş) as described in your example. This indicates that EG C pr (GE) such that there is an edge e, in pte (Gs) whose corresponding K hop subgraph G (centered with this edge) equals to Gp i... G GK Since G Ç ptr (GE), ), the central edge p an edge on Gc. and Gc S G that is implied by the first condition above. Since G Gp the edge e, an edge of Gc, and
Ge S G Therefore, since our basic assumption indicates an edge can either belong to Ge or Gs. and e, belongs to Gc, 6g cannot belong to Gg even though Gg E pte (Gs), which contradicts the supposition. Therefore, there no such K KChopp subgraph that shares across P(Gc) and Ptc O
In conclusion, under these three assumptions, can be argued that P(GclG) remains invariant when such fo is employed.
C.5 Challenges and Limitations
This section discusses the potential challenges, limitations of our methodology, and future research directions that can be pursued to further refine our approach.
significant constraint in method arises from the utilization of common adversarial training. This technique often requires longer training times due to the need for discriminator training. The attainment of optimal diseriminators becomes particularly challenging when subgraph distributions continue to shift as a result the subgraph selection training. A potential area for future research could be the exploration of alternative ways enforce independence properties, for instance, approximations of the min-max optimization could be employed.
Another potential drawback of method pertains to the subgraph discovery architecture [5] that we use. As previously discussed in Section C.3 separating causal from non-causal subgraphs complicates the training process. In response, additional information from both subgraph branches must be provided to facilitate comprehensive optimizations. Consequently. future research could involve the development of new, promising subgraph discovery architectures that alleviate these challenges.
Our method might not directly correlate with OOD errors. For context, current statistical graph modeling techniques, such as [94] [05] [06],, can relate methods to OOD generalization errors, albeit focusing size shift analysis. Methods inspired by explanations, like DIR [4] and proposed approach, offer practical solutions capable addressing a wider range of shifts. Nonetheless, bridging these methods to OOD generalization errors presents substantial challenge.
The limitations and future directions discussed herein have been outlined within the confines of the current three data generation assumptions. Moving forward, future studies could consider wider range of data generation assumptions. Viewing from the lens of graph explainability, these assumptions could not only be at the subgraph-level but could also explore edge-level, node-level, or even flow-level 100 considerations. Such explorations would instrumental in contributing the continuous evolution and refinement of graph OOD models.
27

---

Gradlent
layer
environment diseriminatoe
X
MIP: dr
X
Opeac
dre
Figure 7: The architecture of the pure feature shift consideration (PFSC), The figure illustrates the overall network of the PFSC. The reverse gradient multiplication hyperparameter is denoted as APESC. The loss Cpssc here is the negative -igeliidl in Eq. 12
D LECI implementation details
D.1 The architecture subgraph selector
The architecture our subgraph selector, as illustrated Fig. 6 is based on the work of Miao et al. [5] and uses edges to select subgraphs. The input graph G is passed through general GNN to obtain the hidden representations of nodes. These representations are then transformed into edge embeddings, where each edge embedding is the concatenation of the corresponding node representations. To obtain the edge probability mask, we use multi-layer perceptron (MLP) and a sigmoid function to estimate the sampling probability of each edge. With these sampling probabilities, obtain the sampled adjacency matrix Åc, where we apply the Gumbel-sigmoid [32] technique to make the network differentiable. Finally, the subgraph selector outputs the selected subgraph Ge composed of Åc and the corresponding remaining nodes. Practically, the Go composes all nodes but edge weights are assigned as Åc, which the typical edge representation of subgraphs. Note that to avoid trapping into local minimums caused by artifacts in synthetic datasets, we apply temperature annealing from 10 to 0.1 for Gumbel-sigmoid.
D.2 The architecture the pure feature shift consideration
The technique of pure feature shift consideration (PFSC) used remove environment information from the node feature X. As illustrated in Fig. 7 small MLP transformer, denoted as MLP1, with learnable parameters Φr used transform the node features X into environment-free node features X'. This transformation is achieved through an adversarial training process, where the MLP is trained to remove environment information from X, and the feature environment discriminator aims to approximate the correlation between X' and the environment E. The objective of this process can written as Eq. 12 After this transformation, the input graph G is composed of and X', i.e.. = (X', A). It is worth noting that the use of PFSC alone is not sufficient to achieve optimal performance, as shown in the results the ablation study Tab.
PFSC max min -E [log Pom. (E(X') dr
(12)
dun
D.3 LECT's training strategy
The training strategy of LECI encompasses two implementations. The first one adheres rigorous training process detailed in Sec. 3.4 In this approach, updates to the subgraph selector are performed only upon the convergence of the two discriminators. This iterative training procedure involving the subgraph selector and the two discriminators continues throughout the training process. Despite its thoroughness, this approach
be somewhat time-consuming.
To overcome this hurdle, we resort to the second implementation. Here, we optimize the entire network, including the subgraph selector and the discriminators. The adversarial training hyperpa- rameters, Å and Äg, are initially assigned a value zero. This strategy restricts the influence of the gradients from the discriminators on the subgraph selector, thereby ensuring relatively stable distribution of GC and consistent training of the discriminators.
As the training proceeds and network parameters stabilize over time, with the discriminators moving progressively increase the adversarial training hyperparameters. This strat- egy allows for a gradual implementation of the independence constraints, ensuring the discriminators remain near their optimal states without being abruptly disrupted, as depicted in Fig.
closer to convergence,
28

---

E Detailed experiment settings
In this section, we provide experimental details including fairness discussions, datasets, baseline selec- tion justifications, training and optimization settings, hyperparameter settings, and software/hardware environments.
E.1 Fairness discussion
In all experiments in this paper, all reported results are obtained from 3 runs and are selected by automatic hyperparameter sweeping with respect to ID and OOD validation results. We also provide a fairness discussion about the usage of environment information in Appx. B.2
E.2
Datasets
For our experimental section, we utilize the SST2, Motif, and CMNIST datasets from the GOOD benchmark [0), along with the LBAP-core-ic50 assay split from DrugOOD [2]. Furthermore, we create the GOOD-Twine
and CFP-Motif datasets. All dataset splits target domain generalization and aligns with the guidelines provided in the original literature except CFP-Motif which incorporates PIIF and FIIF shifts described in Sec. 4.2 Although the GOOD datasets are primarily designed for covariate splits, we acknowledge that these splits can include extra spurious correlations, meaning they may also partially satisfy the FIIF and PIIF assumptions.
GOOD-HIV is compact, real-world molecular dataset, derived from MoleculeNet [107]. It contains molecular graphs in which atoms are nodes and chemical bonds are edges, and the task is to predict a molecule's 's potential to inhibit HIV replication. Gui et al. [T0] developed splits based on two domain attributes: the Bemis-Murche scaffold [108), and the number of nodes in molecular graph.
GOOD-SST2 is a sentiment analysis dataset based on real-world natural language, adapted from the work of Yuan et al. [38]. In this dataset, each sentence is converted into a grammar tree graph where individual words serve as nodes, with their associated word embeddings acting as node features. The main task within this dataset is a binary classification exercise aiming to predict the sentiment polarity of each sentence. Sentence lengths are selected the domains, bringing an added layer of complexity to the classification task.
GOOD-Twitter, similarly, is real-world natural language sentiment analysis dataset, adapted from Yuan et al. [38] This dataset applies the same transformation process as in SST2, where sentences converted into grammar tree graphs, with nodes representing words and node features derived from corresponding word embeddings. However, the classification task in this dataset is three-fold, tasked with predicting one of three sentiment polarities for each sentence. As with the GOOD-SST2 dataset, sentence lengths are selected as the domains.
GOOD-CMNIST is semi-synthetie dataset specifically designed to test node feature shifts. It consists of graphs built from hand-written digits extracted from the MNIST database, utilizing superpixel techniques (37) for the transformation. Taking page from the book of Arjovsky et al. () Gui et al. [10] assigned colors to digits based on their domains and concepts. More specifically, in the covariate shift split, digits are colored using seven distinct colors, with the digits exhibiting the first five colors allocated to the training set, those with the sixth color to the validation set, and the remaining digits with the seventh color allocated to the test set.
GOOD-Motif a synthetic dataset, inspired by Spurious-Motts Motif 4 created for structure shift studies. Each graph in the dataset is generated by connecting base graph and a motif, with the motif solely determining the label. The base graph type and the size are chosen as domain features for creating domain generation splits. Specifically, they generate graphs using five label-irrelevant base graphs (wheel, tree, ladder, star, and path) and three label-determining motifs (house, cycle, and crane).
Covariate/FIIF/PII Motif (CFP-Motif) is a synthetic dataset similar to GOOD-Motil and is designed for further structure shift study. The first difference between GOOD-Motif and CFt-M is the base subgraphs of the OOD validation and test set. Specifically, instead of using paths as base subgraphs the test set, we produce Dorogovtsev- Mendoss graphs (36) as base subgraphs. While in the validation set, we assign base graphs as circular ladders. Second, CFP-Motif extends GOOD- Motif with FIIF and PII shifts. FIIF and PIIF splits (Fig. [T. Ge and Y have probability of 0.9 to determine the size of Gs. leading spurious correlations w.n.t. size. That is after determining Gc
29

---

Table 9: Numbers of graphs in training, ID validation, ID test, OOD validation, and OOD test sets for the 7 datasets.
Datasel
Train
ID validation
ID test
00D validatiion
OOD lest
Train
OOD valisdation
ID validatiion
ID tost
ODD test
Scaffold
Size
GOOD-HIV
4112
4112
Length
GOOD-SST2
24744
5301
5301
17206
17490
Length
GOOD-Twittrr
2590
554
554
1785
1457
Color
GOOD-CMNIST
7000
BusisSite
GOOD-Motif
18000
3000
3000
3000
3000
CovariateFIIFPPPP
CPP- 1800
300
300
300
300
Assay
LBAP-ooe-ic50
11683
19028
and Y. the types of causal graphs (FIIF) and the labels (PIIF) will be used to choose the size of Gg from [10, 20, 30J with variances. Note that FIIF and PIIF also contain base graph shifts.
LBAP-core-ic50, dataset derived from DrugOOD 129 is applied in the task of higand-based affinity prediction (LBAP) with the core noise level and IC50 measurement type as domain features.
The selection of these datasets was deliberate to cover: (1) typical molecular predictions with three diverse domains: scaffold, size, and assay; (2) conventional natural language transformed datasets, SST2 and Twitter, with sentence lengths as domains; (3) synthetic datasets that encompass both structure shifts and feature shifts.
All GOOD datasets and datasets created with the GOOD strategy use the MIT license. DrugOOD dataset uses GPL3.0 license.
We provide the dataset statistics Tab.
E.3 Baseline selection justification and discussion
This section offers an in-depth justification for our selection of experimental baselines. Traditional Out-Of-Distribttion (OOD) baselines tend to perform comparably on graph tasks. As such, we elected to use the most typical ones as our baselines, including IRM [9, VREx [14), Coral [35], and DANN X Specifically, DANN serves as essential baseline to empirically demonstrate that direct domain adversarial training is ineffective for graph tasks. We have chosen not to compare our method with GroupDRO [22], is empirically similar to VREx. Furthermore, baselines such as EIIL (28). IB-IRM [31), and CNC [109] were deemed non-comparative due to their performances falling below that of the state-of-the-an graph-specific OOD method [6].
Graph-specific baselines largely concentrate on learning strategies within the subgraph discovery ar- chitecture, except for ASAP [34]. ASAP acts as the subgraph discovery baseline, employing intuitive method for invariant learning, while GSAT (5) incorporates the information bottleneck technique [10. [11] GIB [112], the first graph information bottleneck method, is not included in our experiments due to its performance lagging behind other baselines, as demonstrated by Chen et al. (6) CIGA (d. one of the most recent bate-of-the-att the methods, provides a thorough theoretical discussion about graph OOD generalization. Among these methods, DIR and GSAT perform similarly, with CIGA being the only method that clearly outperforms both ERM and ASAP real-world scenarios, as seen in Fig. 2 The performance shortcomings of DIR and CIGA in synthetic datasets can be partially attributed to the selection of the subgraph size ratio.
techniques to select subgraphs. DIR 4 the original
In addition to CIGA, recent graph- -sepifcpec baselines such as DisC [7], MoleOOD [2] and GIL [I] exist. We provide a comparison with GIL in Appx. B.3 concerning the environment exploitation phase. As for DisC and MoleOOD, we opt not to include them in our baseline due to specific reasons. DisC is not learning strategy that can be universally applied to any subgraph discovery network, and its focus data generation assumptions differs from ours. As for MoleOOD, it is
30

---

specific to molecule predictions, and fair comparison with its environment exploration phase is not feasible, given its inability to work within subgraph discovery architecture. comparison with the entirety of MoleOOD would not provide a controlled comparison, as it would be unclear whether any improvements stem from the environment inference phase the environment exploitation phase.
E.4 Training settings
Among the variety of Graph Neural Networks (GNNs) 121, elect the canonical three-layer Graph Isomorphism Network (GIN) 115 with a hidden dimensionality of 300, a dropout ratio of 0.5, and mean global pooling the encoder for the GOOD-Motif basis split. For the GOOD-Motif size, CFP-Motif, GOOD-CMNIST, and real-world datasets, we extend GIN with the addition of virtual nodes. A linear classifier is used following the graph encoder. The reason for using virtual nodes for GOOD-Motif size and CFP-Motif is that these splits include size shifts which are hard to capture by mean pooling. Instead of using other pooling methods, simply apply virtual node to capture this global information.
Throughout the training phase, utilize the Adam optimizer [12 For GOOD Motif and GOOD- SST2, the learning rate is set to 10 10-3 3 For CFP-Motif, the learning rate is set to 10 with a weight decay from [0, 10- For GOOD-HIV, GOOD-Twitter, and DrugOOD, of 10-1, accompanied by weight decay of 10-1 Across all datasets, the standard number of training epochs is set to 200. A training batch size of 32 is used for all datasets, with the exception of GOOD-CMNIST, where we use batch size of either 64 or 128.
apply learning rate
E.5 Hyperparameter sweeping
In this section, we display the hyperparameter sweeping space of each method. For the traditional OOD method with only one hyperparameter, we denote the only hyperparameter A. For methods ASAP, DIR, and CIGA, we denote the size ratio the causal subgraphs compared to original graphs as As-
E.5.1 Hyperparameters of baselines
IRM: À [10-1 1, 10 10
VREx: [0', 111000 10").
Coral: À [10-3, 10, 1,,00-111 ,
DANN: À [10-3,10 10-22 1,00-,11
ASAP: A. 0..,,0.40066.000
DIR: A [022, 0.4, 0.8] and Awar [10-2,10-1,
10-1 1,,,,, 10"), where Avar is the variance
constraint.
GSAT: 10.5,0.7 and Auecay [10, 20J. Here, and Auecay are the information constraint hyperparameter and the information constraint 0.1 decay epochs, respectively.
CIGA: X = |0.2, 0.4, 0.6, 0.8) a [0.5, 1, 2, 4), and 5 [0.5, 1,2, 4]. a and / are for contrastive loss and hinge loss, respectively.
E,5.2 Hyperparameters of LECI
In GIN-virtuannode cases, we generally apply Ar. E [10-2 1]. AE E [10-2,100 10-1). In real-world
datasets, we adopt APFSC [10 2 10-10 with fixed information constraint 0.7 for stable training on GSAT's subgraph discovery basic architecture. Since GOOD-Twitter is too noisy according to the performance, the environment labels on are far from accurate. Therefore, we extend the search scope as Ag [10- 1] into the hyperparameter sweeping on GOOD-Twitter.
In all synthetic datasets, to investigate the pure constraints proposed by LECI, remove the information constraint, For GOOD-Mott basis and GOOD-CMNIST, we apply strong independence constraints, where the searching range becomes λ₁ E [1, 10), dr E [10, 100), and Aprsc [10-1, 1).
The hyperparameter searching scope can be narrowed down using the loss of the two independence components as follows.
31

---

Table 10: Results the structure and feature shift datasets with the test set hyperparameter
selections
GOOD-Motte
GOOD-CMNIST
CFP-Motiif
basis
size
color
covariate
FIIF
PIIF
ERM
60.93(11.11)
56.63(7.12)
26.64(2.37)
59.33(5.73)
43.00(7.67)
62.45(9.21)
IRM
64.94(4.85)
54.52(3.27)
29.63(2.06)
58.33(5.44)
68.89(4.99)
72.89(4.88)
VREx
64.10(8.10)
57.55(3.99)
31.94(1.95)
62.78(2.47)
44.67(9.73)
71.00(2.05)
Coral
69.47(1.42)
60.60(1.40)
30.79(2.50)
58.44(9.37)
51.67(6.60)
10.44(3.13)
DANN
72.07(1.47)
59.01(1.555
29.36(1.23)
60.22(3.19)
52.00(3.14)
70.00(4.53)
ASAP
45.00(11.66)
42.23(4.20)
26.45(2.06)
64.67(5.63)
44.34(1.70)
41.89(5.28)
DIR
58.49(18.97)
47.70(10.77)
26.73(3.25)
67.33(4.38)
62.66(9.67)
57.67(9.27)
GSAT
62.27(8.79)
57.99(0.91)
35.02(1.78)
71.67(7.09)
55.33(9.69)
61.22(8. 80)
CIGA
67.16(21.59)
57.10(4.07)
27.63(3.19)
60.45(6.38)
72.33(6.62)
57.44(9.12)
LECI
86.97(4.48)
77.57(4.91)
66.75(6.18)
88.78(0.69)
81.56(2.57)
76.67(0.98)
Hyperparameter searching range selection. There isn't set of hyperparameters that works perfectly for every dataset. Fortunately, LECT's valid hyperparameter ranges be easily determined by drawing the loss curve of each component without any test information leaking or extra dataset assumptions. For example, the hyperparameter λg valid only when the loss LE curve implies two-stage training pattern. In the first stage, the discriminator should be well-trained, leading to the decrease and convergence of the loss. the second stage, the adversarial training should take effect; then, the loss will increase. In several simple synthetic datasets, the loss can increase up to the value that indicates a random classification, e.g., this value is log 0.5 for binary classification. While in real-world datasets, the loss increase will be more gentle.
Invalid training. When LE L1. remain high during the training process, directly indicates the learning rate or Ag/Ar. is too high. In this invalid training case, the model can still produce reasonable results, but LECI does not take effect because this case generally indicates the clear violation of Proposition 3.2 Therefore, different from many other constraints, higher or lower hyperparameters can both lead invalid training.
Golden rule. Set the hyperparameter searching space around the golden point where the loss LE and fu,luttuate near their lowest values, where the lowest values can be measured by setting λg and λr. to O. For example, if at the golden point, A = 10-1 and 0E = 10-2 then the searching space is generally A1. [10-2 10"), År. [10-3 10-1] except the invalid training processes occurs when need to narrow the searching space to eliminate them.
This hyperparameter validation process selects the strong constraints for several synthetic datasets, otherwise the loss at the second stage cannot increase to the value that indicates successful adversarial training.
E.6 Software and hardware
Our implementation is under the architecture of PyTorch [23] and PyG [119]. The deployment environments are Ubuntu 20.04 with 48 Intel(R) Xeon(R) Silver 4214R CPU @ 2.40GHz, 755GB Memory, and graphics cards NVIDIA RTX 2080T/NVIDIA RTX A6000.
F
Supplimentary experiment results
In this section, we provide OOD test set validated sanity check results and interpretability visualiza- tions, For the comparison with GIL [I. we provide it in Appx. B.3.2
F1 second look at the ability to address structure and feature shifts.
To further exploit the full power of each OOD learning method, we collect the results on the structure and feature sanity check datasets by using OOD test results to select hypepparameters. As shown
32

---

in Tab. T0, with the leak of OOD test information, several methods improve their performance significantly, yet LECI still markedly outperforms all baselines.
F.2 Interpretability visualization results
visualization results on GOOD-Motif and CFP-Motif, As illustrated in Fig. [ we use thresholds select the top probability edges the interpretability subgraph selections. Specifically, on each row, apply different base subgraphs, including wheel, ladder, tree, path, and small/large Dorogovtsev-Mende graphs. On each column, we attach the base subgraphs with different motifs, namely, crane, house. and cycle. According to the interpretability results, LECI can select subgraph selection and further explains the reason behind the good performance. As shown in the figure, the spurious parts of ladders and paths are more challenging eliminate than other base subgraphs. Fortunately, the latter invariant predictor can distinguish them and make consistent predictions.
We provide interpretability [38, [8]
motifs accurately, which implies its good performance on the causal
33

---

Figure 8: Interpretability results on GOOD-Motif and CFP-Motif covariate shifts. Base sub- graphs and motifs are denoted as orange and green nodes, respectively. The selected subgraphs are indicated by red edges.
34


Reviews:
[{"review_id": "SOXQknFJtq", "reviewer": "Reviewer_tVF4", "summary": "This papers considers the graph OOD generalization problem with given environment information. It proposes a novel invariant learning method based on adversarial loss which is derived from independence conditions of the causal graph. Experimental results show the proposed method is very effective.\n", "questions": "- Since Y is not necessarily independent of G_s in FIIF and PIIF, what is the motivation to even use a soft version of the independence property?\n\n- For model selection, we know most invariant learning methods do not work with in-domain validation set [1] for image datasets. I am curious about what is the overall improvement when using OOD validation set over in-domain validation set in the graph OOD problem.\n\n[1] Gulrajani, Ishaan, and David Lopez-Paz. \"In search of lost domain generalization.\" arXiv preprint arXiv:2007.01434 (2020).\n", "limitations": "- This work only considers causal features and spurious features as subgraphs. But there can other types of high-level graph features that can be causal features.\n\n- This work relies on invariant learning, which itself can be limited. For example, when the invariant features are not highly correlated with label, then the prediction accuracy can be quite low.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Compared with previous work, this work proposes a more graph-specific environmental exploitation algorithm, which includes a subgraph selector.\n\n- The proposed method comes with theoretical results to show that the derived optimal paramteres can lead to learning causal subgraph only for invariant prediction.\n\n- The proposed method outperforms existing methods on various benchmarks by a large margin. Ablation studies show the proposed method is benefiting from each component.\n", "weaknesses": "- In fact, the proposed method can also be not that graph specific. We only need to replace the subgraph selector f_{\\theta} with a feature selector, then we can apply the method to invariant rationalization [1]. So, the claim may not be 100% true.\n\n- The theorems only provide equivalence between optimal paramters and learning causal subgraphs, but they did not mention what can be guaranteed if we cannot achieve optimal parameters (e.g., due to hidden variables).\n\n[1] https://arxiv.org/abs/2003.09772\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and insightful comments! \n\n## Weaknesses:\n\n> In fact, the proposed method ... the claim may not be 100% true.\n\n**Response:** As highlighted on line 564 of the appendix, the mapping from $(X,A)_C \\mapsto X_C$ is non-unique. While it's conceivable to adapt a feature-only method to a combined feature+structure method, the challenges encountered differ significantly. In our approach, we disentangle $A$ into $A_C$ and $A_S$, but refrain from dissecting $X$. In comparison, [1] postulates that $X$ can be disentangled, an assumption that may not hold for graph node embeddings. Thus, our methodology indeed demonstrates graph-specific attributes when juxtaposed with other graph OOD techniques. Nevertheless, in light of your feedback, we are committed to providing further elucidation and will moderate our claim for precision. We trust you appreciate that this assertion helps to distinctly position our work within the graph OOD discourse.\n\n\n> The theorems only provide ... what can be guaranteed if we cannot achieve optimal parameters (e.g., due to hidden variables).\n\n**Response:** Should the optimal parameters remain unattainable, our theorems indicate an associated increase in loss. We recognize the complexities introduced by bi-level optimization, analogous to those observed in GANs. There exist subsequent studies, such as WGAN and consensus optimization methods, dedicated to addressing these optimization challenges. While this particular aspect isn't central to our paper's core message and claims, we acknowledge its significance. As a gesture towards its importance, we have identified it as a noteworthy limitation warranting future exploration and have documented this perspective in line 692 of the appendix.\n\n\nWe hope our answers address your concerns about our paper.\n\n## Questions:\n\n> Since Y is not necessarily independent of G_s in FIIF and PIIF, what is the motivation to even use a soft version of the independence property?\n\n**Response:** The soft independence property encompasses the strict version of the independence property as a specific instance when $I(G_S;Y)=0$. As elucidated in Theorem 3.8, the soft independence property buttresses our learning approach. Transitioning from the strict \"independence property\" to the softer version serves a dual purpose: it not only structures our paper coherently but also progressively guides the readers from simpler covariate SCMs (with strict independence) to the more intricate FIIF/PIIF SCMs (featuring soft independence).\n\n\n> For model selection, ... what is the overall improvement when using OOD validation set over in-domain validation set in the graph OOD problem.\n\n**Response:** For model parameter selection, we've incorporated a table delineating the performance difference from ID to OOD model selections of leading-edge methods across real-world datasets like GOODHIV, GOODSST2, and Twitter. Should it be deemed essential, we stand ready to complete and append a comprehensive table to our appendix.\n\n| | SST2 | Twitter | HIV-scaffold | HIV-size |\n| -- | -- | ---- | ---- | --- |\n| GSAT | 0.08 | 0 | 0.48 | 2.29 |\n| CIGA | 0.57 | 0 | 1.87 | 4.7 |\n| LECI | 1.48 | -0.2 | 1.04 | 1.18 |\n\nIn the case of model checkpoint selections in a single run, the performance difference can be found in Table 2 in our paper.\n\n## Limitations:\n\n> This work ... causal features.\n\n**Response:** Indeed, the scope of our work is primarily centered around causal and spurious features modeled as subgraphs because of the graph modeling we used. In fact, the broader landscape of graph modeling, be it statistical or inspired by explainability, is vast, but statistical modeling methods currently can only tackle size shifts [2,3]. While we have dedicated a segment to feature shifts in Sec. 3.7, it's acknowledged that there are more intricate, high-level graph features that could bear causal significance.\n\n\n> This work relies ... can be quite low.\n\n**Response:** Your observation delves into the profound intricacies of causality in real-world scenarios. Invariant learning, as we've outlined in line 437 of the appendix, draws its inspiration from the annals of causality literature. The scenario you describe, where invariant features may not be observed or cataloged, is intimately tied to data collection methodologies. When our data sources are not comprehensive, the consequent statistical rules we deduce might be flawed. Instances where only spurious features are in focus exemplify an anti-causal assumption, which, while encapsulated by invariant learning, is not the focus of our paper. Your example underscores the nuances of causality assumptions and their applicability. We've delved deeper into this topic in section C.2 of the appendix. It's our assertion that while individual generalization challenges can be tackled piecemeal, a holistic, universal solution, as posited by [4], might be elusive.\n\nBoth points you've raised are indeed pertinent challenges, meriting deeper exploration in subsequent works. We are committed to weaving these insights into our limitation discussion, specifically in section C.4 of the appendix.\n\nSincerely,\n\nAuthors\n\n## References\n\n(They will also be added in our paper.)\n\n[1] Chang, S., Zhang, Y., Yu, M., & Jaakkola, T. (2020, November). Invariant rationalization. In International Conference on Machine Learning (pp. 1448-1458). PMLR.\n\n[2] Bevilacqua, B., Zhou, Y., & Ribeiro, B. (2021, July). Size-invariant graph representations for graph classification extrapolations. In International Conference on Machine Learning (pp. 837-851). PMLR.\n\n[3] Chu, X., Jin, Y., Wang, X., Zhang, S., Wang, Y., Zhu, W., & Mei, H. (2023). Wasserstein Barycenter Matching for Graph Size Generalization of Message Passing Neural Networks.\n\n[4] Kaur, J. N., Kiciman, E., & Sharma, A. (2022). Modeling the data-generating process is necessary for out-of-distribution generalization. arXiv preprint arXiv:2206.07837.\n"}, {"review_id": "swk297xoXv", "reviewer": "Reviewer_6JF6", "summary": "This paper proposes a new graph learning model to incorporate label and environment causal independence (LECI) for solving the graph OOD generalization problem. The authors first introduce two causal independence properties to distinguish causal and spurious subgraphs. Enforcing environment causal independence properties and utilizing the environment label information, LECI is able to identify causal subgraphs for invariant predictions. The authors further leverage an adversarial learning strategy to learn the label and environment casual independence. In contrast to the previous graph OOD methods which commonly assume non-existence of the environment information, LECI instead fully utilizes environment information and introduces a graph-specific environmental exploitation algorithm. Extensive experiments on GOOD and DrugOOD benchmark datasets demonstrate the superiority of LECI among other baseline methods.\n", "questions": "1. Questions in Weaknesses part.\n2. As environment labels may only be observed partially in some real-world scenarios, I wonder if LECI could utilize the observed environment labels to infer the rest of the labels using the adversarial implementation.\n", "limitations": "The authors adequately addressed the limitations and future work in the Conclusion section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The illustration of graph OOD generalization from a causal perspective is clear and easy to understand, and the derived two causal independence properties could be used to distinguish between causal subgraphs and spurious subgraphs for graph OOD future works.\n2. The adversarial learning implementation of LECI is technically sound, and the derivation of the adversarial objective is rigorous.\n3. The theoretical results are convincing.\n4. Extensive experiments on GOOD and DrugOOD benchmark datasets demonstrate that LECI significantly outperforms baselines, and the authors also conducted comprehensive experiments for sensitivity analysis and ablation studies.\n", "weaknesses": "1. LECI assumes the environment information is known, which is a tight requirement. The authors argue that the environment labels can be accessed by applying simple groupings or deterministic algorithms, but in this case, the obtained labels are not accurate. From my perspective, these labels can be served as auxiliary information or as a proxy for ground-truth environment labels, but directly regarding them as environment labels may be not appropriate. However, I do believe LECI can be combined with the existing environment inference methods. I wonder if the authors have made some attempts. \n2. The authors did not discuss the computational complexity of LECI in the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your helpful feedbacks!\n\n## Weaknesses:\n\n> LECI assumes the environment information is known, which is a tight requirement. The authors argue that the environment labels can be accessed by applying simple groupings or deterministic algorithms, but in this case, the obtained labels are not accurate. From my perspective, these labels can be served as auxiliary information or as a proxy for ground-truth environment labels, but directly regarding them as environment labels may be not appropriate. However, I do believe LECI can be combined with the existing environment inference methods. I wonder if the authors have made some attempts.\n\n**Response:** Following your suggestion, we evaluated LECI alongside a cluster-style environment inference (EI) approach that employs k-means on the representations of $G_S$, treating their cluster labels as environment labels. We gathered results across two real-world datasets and one synthetic dataset:\n\n|                | HIV-scaffold | Twitter | Motif |\n| -------------- | ------------ | ------- | ----- |\n| LECI + cluster | 71.38        | 57.17   | 72.67 |\n\n\nIt's crucial to emphasize that without a comprehensive theoretical design to ensure subgraph discovery, this approach doesn't surpass our current LECI implementation that uses environment labels. This can be attributed to challenges like selecting appropriate EI methods and determining the number of environments, etc. We share these results to validate that LECI is indeed compatible with EI methods. Nonetheless, a deep exploration of EI methods is beyond the scope of this study. We acknowledge this and will reference it as a limitation in Section C.4 of the appendix.\n\n> The authors did not discuss the computational complexity of LECI in the paper.\n\n**Response:** Thank you for your suggestion. We include the response in our global rebuttal (the common concerns section).\n\n## Questions:\n\n> As environment labels may only be observed partially in some real-world scenarios, I wonder if LECI could utilize the observed environment labels to infer the rest of the labels using the adversarial implementation.\n\n**Response:** Theoretically, LECI is indeed capable of utilizing the environment discriminator to predict additional environment labels from those that are observed. However, in real-world situations, we often encounter class-incremental tasks in environment inference, where the test environment labels might differ substantially from the observed ones. This creates a challenge that our environment discriminator is not designed to address. To illustrate, consider a scenario where during training, the model learns to differentiate environments $e_1, e_2, e_3$, yet in the testing phase, it encounters environments $e_3, e_4, e_5$. Here, $e_4$ and $e_5$ are unknown quantities, and their prediction would require specialized class-incremental techniques.\n\nSincerely,\n\nAuthors"}, {"review_id": "msAaFzwEhN", "reviewer": "Reviewer_YxXK", "summary": "The paper proposed a novel learning strategy to incorporate label and environment causal independence (LECI) for tackling the graph OOD problem. Enforcing such independence properties can help exploit environment information and alleviate the challenging issue of graph topology shifts. With good empirical results on several datasets and related theoretical analyses, the paper justifies the effectiveness of the proposed LECI.", "questions": "In addition to the questions given above, I also want to ask some additional questions.\n\n4. The question is related to the adversarial mechanism. Take EA as an example. For both equations 6 and 7, the adversarial principles are easy to understand. However, From the mathmatical perspective, I am lost. For equation 6, the inner max can be naturally converted to min L_E, as that in Equation 7. In this way, with the same inner function, the outer operation in Equation 6 is min while that in Equation 7 is max. Is this a contradiction?\n\n5. From figure 4, the curves of LECI drop first and then increase, which is marked by the effect of the two independence constraints. Why do the two independence constraints take effect too late?", "limitations": "The authors provide detailed analysis on limitations in the supplementary materials.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper proposed an effective method for tackling the graph OOD problem. The author proposes to solve the problem by introducing label and environment causal independence, which is a good idea.\n2.\tThe logic is clear and solid, including the well-defined research problem and challenges, the proposed solutions, and theoretical analysis.\n3.\tThe gained empirical improvement is quite significant with the proposed LECI framework. Several ablation studies are shown.\n", "weaknesses": "1.\tI am puzzled for \"graph-specific and \"distribution shift on graph topology\". Compared with other graph-specific OOD baselines, why LECI can solve the problem, as the author mentioned on line 19 and line 20.\n2.\tIt would be better to perform analysis on the complexity analysis, and some details are not explained so clearly of the two discriminators.\n3. Due to the adversarial mechanism, the proposed method cannot scale to large-scale datasets and also it is very hard to train.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable comments and feedbacks! We have carefully considered each one and have endeavored to address your concerns. We believe that our responses will provide the necessary clarifications, and we look forward to your feedbacks.\n\n## Weaknesses:\n\n> I am puzzled for \"graph-specific and \"distribution shift on graph topology\". Compared with other graph-specific OOD baselines, why LECI can solve the problem, as the author mentioned on line 19 and line 20.\n\n**Response:** We recognize the ambiguity and appreciate your patience. We are committed to enhancing clarity in the paper by incorporating pertinent references. Here’s a breakdown of our clarification:\n\n1. In relation to environment-based methods: Please consult section B.3.1 in the appendix. Here, we elucidate that LECI uniquely harnesses environment information in graph contexts in a manner that other methods don't. B.3.2 further demonstrates the result differences.\n\n2. Regarding environment-agnostic approaches:\n    * First, refer to section C.2 and Table 8 in the appendix. This demonstrates that the assumptions guiding other techniques are more susceptible to being compromised compared to using environment information.\n    * Second, regarding the \"distribution shift on graph topology\", please see Table 7 and section C.2 in the appendix. We highlight therein that other strategies falter in addressing dual subgraph discovery challenges, a feat LECI manages to achieve.\n\n3. For a deeper dive into these subgraph discovery challenges, C.3 in the appendix provides comprehensive insights.\n\n> It would be better to perform analysis on the complexity analysis, and some details are not explained so clearly of the two discriminators.\n\n\n**Response:** We genuinely appreciate this constructive feedback. To address this point and similar concerns, we've elaborated in our global rebuttal (under the common concerns section).\n\nWe kindly seek further specificity regarding which details you'd like elaborated about our discriminators, especially beyond our explanations provided in Eq. (7) and Eq. (8). We've made our code available as supplementary material, which should provide comprehensive insight into the detailed workings. However, if you believe there are critical aspects to be incorporated into the paper itself, we stand ready to make those modifications.\n\n> Due to the adversarial mechanism, the proposed method cannot scale to large-scale datasets and also it is very hard to train.\n\n**Response:** Indeed, your observation regarding the limitations posed by the standard adversarial mechanism is astute. We have explicitly discussed this point in section C.4 of our appendix. Nevertheless, it's crucial to emphasize that this specific limitation does not detract from the primary claims and conclusions of our study, as underscored in our global response.\n\n## Questions:\n\n> The question is related to the adversarial mechanism. Take EA as an example. For both equations 6 and 7, the adversarial principles are easy to understand. However, From the mathmatical perspective, I am lost. For equation 6, the inner max can be naturally converted to min L_E, as that in Equation 7. In this way, with the same inner function, the outer operation in Equation 6 is min while that in Equation 7 is max. Is this a contradiction?\n\n**Response:** Thank you for your question. To clarify, the equations operate as follows:\n\nFor Eq. (6), the operative function is:\n$$\\theta^*_\\text{E} = argmin_{\\theta} \\left\\\\{\\max_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_E}(E|\\hat{G}_C)} \\right]\\right\\\\}$$\n\nHowever, if we introduce a negation within the argmin, it translates to argmax:\n\n$$argmin\\_{\\theta} \\left\\\\{\\max_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}\\_C)} \\right]\\right\\\\} = argmax_{\\theta} \\left\\\\{ - \\max_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}_C)} \\right]\\right\\\\}$$\n\nUpon transposing the negative sign and the max operation:\n\n$$ argmax_{\\theta} \\left\\\\{ - \\max_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}\\_C)} \\right]\\right\\\\} = argmax_{\\theta} \\left\\\\{\\min_{\\phi_E} - \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}_C)} \\right]\\right\\\\} $$\n\nYour assertion \"For equation 6, the inner max can be naturally converted to min L_E\" is partially accurate. Yes, in the context of the optimal $\\phi_E$, it holds that \n\n$$argmax_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}\\_C)} \\right] = argmin_{\\phi_E} L_E. $$\n\nHowever, the overall optimality of their values contrast, hence \n\n$$ max_{\\phi_E} \\mathbb{E} \\left[ \\log{P_{\\phi_\\text{E}}(E|\\hat{G}\\_C)} \\right] = - min_{\\phi_E} L_E. $$ \n\nThis inherent \"minus\" justifies the outer argmax in Equation 7.\n\n> From figure 4, the curves of LECI drop first and then increase, which is marked by the effect of the two independence constraints. Why do the two independence constraints take effect too late?\n\n**Response:** We've addressed this in our global rebuttal under the common concerns section, and we thank you for highlighting it.\n\nSincerely,\n\nAuthors"}, {"review_id": "zyEQuWE7YS", "reviewer": "Reviewer_psug", "summary": "This paper proposes a novel adversarial approach called LECI, for OOD generalization. The paper leverages label and environment information to identify the causal and invariant graph, thereby enhancing the accuracy and reliability of causal and invariant subgraph identification. The authors conduct extensive experiments on various real-world datasets under different distribution shift and demonstrate the effectiveness of the proposed approach. ", "questions": "see Weaknesses", "limitations": "na", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "(1) The paper proposes an effective learning strategy to incorporate label and environment causal independence for tackling the graph OOD problem.\n\n(2) Detailed theoretical guarantees for casual subgraph discovery are provided.\n\n(3) Extensive experiments on synthetic and real-world datasets, which provide insightful empirical findings.\n \n", "weaknesses": "1. Limited novelty. Since environment inference and environment exploitation are often combined, and previous methods have used environment-based approaches specifically for graphs[1-2], it is puzzling why the author propose that previous methods did not explicitly mention graph-specific designs in line 26. Moreover, if representations are obtained by both structural and feature information using message passing, it begs the question of whether invariant learning on such representations has already addressed by previous works. The novelty of the article requires more presentation.\n\n2. Tables 1 and 2 do not include a comparison with GIL[2] as mentioned in line 266. Furthermore, based on my limited knowledge, GIL also involves capturing and optimizing invariant subgraphs, utilizing invariant learning for optimization. It is recommended to provide an explanation regarding the explainability of subgraphs between LECI and GIL. It appears that the paper requires additional elaboration on its novelty.\n\n3.Does the presence of three relatively independent adversarial training criteria in the main model pose significant challenges to the model training, such as difficulties in convergence similar to DANN? From Figure 4 on the left, a similar trend can be observed. It seems that this model requires dedicated hyper-parameters such as learning rate and number of epochs in order to achieve better results.\n\n[1] Chen, Yongqiang, et al. \"Learning causally invariant representations for out-of-distribution generalization on graphs.\"  NIPS, 2022.\n\n[2] Li, Haoyang, et al. \"Learning invariant graph representations for out-of-distribution generalization.\" NIPS, 2022.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the effort and time you have dedicated to reviewing our paper. We understand that some aspects may have led to certain misconceptions, and it is our foremost intention to address and clarify these points. We hope this further elucidation will assist in reevaluating our work.\n\n## Weaknesses:\n\n> Limited novelty. Since environment inference and environment exploitation are often combined, and previous methods have used environment-based approaches specifically for graphs[1-2], it is puzzling why the author propose that previous methods did not explicitly mention graph-specific designs in line 26.\n\n**Response:** Thank you for pointing out the concerns related to the novelty and positioning of our work in relation to existing literature.\n\n1. While we acknowledge the contributions of [1], it fundamentally operates as an environment-agnostic method. One can observe this from Figure 1(b) in [1], even though they did delve into analyses that involve environments.\n\n2. The ambiguity in line 26 is duly noted, and we appreciate your suggestion. To elaborate:\n   - Our stance in line 26 is elucidated in lines 76-88.\n   - For a comparative understanding with environment-based methods including [2], we direct your attention to section B.3.1 in the appendix.\n   - For a comparison with other methodologies, section C.2 in the appendix sheds light.\n\nOur intention was to underline unexplored avenues in this domain, and the references and justifications we've provided aim to demarcate our contributions distinctly. We remain open to further discussions and clarifications on this matter.\n\n> Moreover, if representations are obtained by both structural and feature information using message passing, it begs the question of whether invariant learning on such representations has already addressed by previous works. The novelty of the article requires more presentation.\n\n**Response:** Thank you for highlighting the need for clarity on the novelty of our approach, especially in the context of invariant learning on combined structural and feature representations. \n\nTo specifically address this concern: \n- We delve deep into this topic in section B.3.2 of the appendix. Therein, we performed experiments that hold all other variables constant, allowing for a direct comparison between graph-specific (our method, LECI) and non-graph-specific (like GIL/IGA) environment exploitation strategies.\n- The findings conclusively indicate that merely applying invariant learning on the combined representation (of structure and feature) falls short in addressing the challenges, and in fact, produces suboptimal outcomes in contrast to our graph-specific exploitation approach.\n\nWe believe that this rigorous experimental comparison further underscores the novelty and significance of our proposed method.\n\n> Tables 1 and 2 do not include a comparison with GIL[2] as mentioned in line 266. Furthermore, based on my limited knowledge, GIL also involves capturing and optimizing invariant subgraphs, utilizing invariant learning for optimization. It is recommended to provide an explanation regarding the explainability of subgraphs between LECI and GIL. It appears that the paper requires additional elaboration on its novelty.\n\n**Response:** Thank you for pointing it out, and we appreciate the opportunity to clarify:\n\n1. Firstly, our discussions and justification for the novelty, particularly in the context of GIL, can be found in section B.3.1 of the appendix. We believe this section provides a thorough insight into our approach and its distinctiveness.\n   \n2. As for the direct comparison with GIL as noted in line 266, due to space constraints in the initial submission and the added complexity of capturing environment exploitation comparisons, the results were shifted to B.3.2 in the appendix. Please be assured that, upon acceptance, we will reintegrate these comparisons into the main content of the paper to provide a clearer and more comprehensive perspective.\n\nWe strive for clarity and completeness in our presentation and appreciate your feedback which aids us in achieving that.\n\n> Does the presence of three relatively independent adversarial training criteria in the main model pose significant challenges to the model training, such as difficulties in convergence similar to DANN? From Figure 4 on the left, a similar trend can be observed. It seems that this model requires dedicated hyper-parameters such as learning rate and number of epochs in order to achieve better results.\n\n**Response:** We acknowledge your concern regarding the potential challenges posed by the inclusion of adversarial training criteria in the primary model. Indeed, the complexities associated with such a setup could be reminiscent of those seen in DANN, as evidenced by the trend in Figure 4 on the left. \n\nHowever, it's crucial to emphasize that while these challenges are present, they don't substantially hamper the validity of our claims or the conclusions we draw from our experiments. For a more comprehensive understanding of these challenges and our response to them, we refer you to our global response section (under common concerns & limitations).\n\nFurthermore, detailed specifications of our chosen hyper-parameters can be found in section E.5.1 of the appendix. A noteworthy observation, as shown in Table 10, is that **even with hyper-parameter optimization using the test set, other existing methods still do not manage to match LECI's performance**. This underscores the notion that our approach's merits aren't product of hyper-parameter tuning but instead arise from its inherent design and functionality.\n\nSincerely,\n\nAuthors\n\n## References\n\n[1] Chen, Yongqiang, et al. \"Learning causally invariant representations for out-of-distribution generalization on graphs.\" NIPS, 2022.\n\n[2] Li, Haoyang, et al. \"Learning invariant graph representations for out-of-distribution generalization.\" NIPS, 2022.\n"}, {"review_id": "pHpslIM3e9", "reviewer": "Reviewer_Csim", "summary": "This work addresses the issue of graph out-of-distribution (OOD) generalization by considering the data generation assumption of the presence of a causal subgraph and a spurious subgraph within each graph, and the assumption of label and environment causal independence. The paper proposes an adversarial training approach that leverages accessible environment information in the dataset. By jointly optimizing over these properties, the method aims to discover causal subgraphs for invariant prediction. Experimental evaluations on synthetic and real-world datasets demonstrate the method's superior performance compared to existing approaches.", "questions": "1. As mentioned in the weakness section, what is the theoretical definition of the graph OOD problem that this paper is trying to tackle?\n2. As far as I understand, the theoretical statements claim that if the model is optimized optimally, then the subgraph selector $f_\\theta$ should select the optimal causal subgraph in the training graph. However, for the test data with a different distribution, how to guarantee the subgraph selector is still able to find the correct causal subgraph?\n3. In line 160, it is said “for any $G_p$ such that $G_s\\subset G_p$, $I(G_S;Y) \\leq I(G_p; Y)$”. It is unclear whether this statement is an assumption or a proven fact. Since in the line 599, it is said “$I(E; G_C)\\geq I(E; G_p)$ is trivial since $G_p$ is a subset of $G_C$”. Why is it trivial? If it is trivial, does it mean “for any $G_p$ such that $G_s\\subset G_p, I(G_S;Y) \\leq I(G_p; Y) $” is also trivial?\n4. In the synthetic dataset section, it seems the dataset follows the Covariant SCM setting. Is it possible to add synthetic experiments for dataset following the FIIF and PIIF settings?\n5. Is it possible to know which SCM does each real-world dataset follow?\n6. Most real-world datasets show comparable performance across methods, including the ERM baseline. In many cases, the OOD validation performances are better than in-distribution performances. These observations raise questions regarding the difficulty of the OOD task investigated in this section. Can you provide any insights or explanations for these findings?\n7. The experimental section primarily focuses on the GOOD benchmark dataset, where the environment information is readily available. Although the paper suggests that obtaining environment labels is feasible by applying the algorithms from GOOD to other datasets, it is worth considering the value and applicability of the environment information in datasets beyond the GOOD benchmark. Clarifying whether the proposed approach can still benefit from the environment information in datasets outside of the benchmark would enhance the understanding of its generalizability.\n8. Typo: There are multiple instances of the word \"casual\" in the paper, which should be corrected to \"causal\" for accuracy and clarity.\n", "limitations": "1. The components of the method are not particularly novel on their own since it is standard adversarial training. The theoretical guarantee of OOD generalization performance is not fully justified.\n2. The accessibility and quality of environment information in general graph datasets are not thoroughly addressed in the paper. Exploring the possibility of incorporating environment information into other existing methods would provide a more comprehensive evaluation and a fairer comparison across different approaches.\n", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, organized, and effectively conveys its ideas. A notable distinction from prior work is the assumption of access to environmental information, but the authors provide a thorough evaluation of this assumption's fairness compared to existing methods.\n2. This paper introduces a novel approach to address the graph OOD problem by integrating environment and label independence, allowing for the comprehensive utilization of environmental information. The proposed method is accompanied by theoretical guarantees, enhancing its credibility.\n3. The empirical evaluation is carefully designed, incorporating diverse datasets, relevant baselines, and comprehensive sanity checks. The authors further enhance their study with sensitivity analysis and ablation studies, providing a robust evaluation framework.\n", "weaknesses": "1. The paper introduces assumptions about the data generation process but lacks a formal definition of the OOD task within the paper. It would be beneficial to clarify details such as the training data distribution, test data distribution, and the specific differences between them. Specifically, is the difference solely attributed to the environment variable E, and are new E values observed in the test distribution? Additionally, it would be helpful to address whether the support for $P^\\text{tr}(E)$ and $P^\\text{te}(E)$ should be the same.\n2. Although the paper has theoretical analysis of the proposed approach, it does not directly connect to the OOD generalization error. It is not explicitly stated how the proposed model's performance will be in various OOD settings theoretically. \n3. The paper explores three different distribution shift assumptions, but it appears to place more emphasis on the Covariate SCM assumption. In the experimental section, it would be advantageous to clarify the specific SCM that the data satisfy and provide further details regarding how the data satisfy the SCM.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and comments. We have incorporated your suggestions to refine the robustness and clarity of our paper. Below, we provide detailed answers to your questions in order to address your concerns listed in weaknesses.\n\n## Questions:\n\n1. We deeply appreciate your request for clarity on this fundamental aspect of our work.\n\nBeyond the preliminary in Sections 2.1 and 2.2, the theoretical definition can be summarized as an interpretation of our SCM assumptions. Essentially, we are addressing the distribution shifts between $P^{tr}(G,Y)$ and $P^{te}(G,Y)$. Our **core assumption**, based on the Independence Causal Mechanism (ICM), is that there exists a component $G_C$ within $G$ such that $P^{tr}(Y|G_C) = P^{te}(Y|G_C)$ (as also discussed in lines 437-446). \n\nThe shifts in distribution are exclusively attributed to interventions on $G_S = G - G_C$ that are encapsulated as an environment variable $E$, aligned with the invariant learning literature. The OOD dilemma arises when $P^{tr}(E) \\neq P^{te}(E)$, leading to shifts in both $P^{tr}(G_S)$ and $P^{te}(G_S)$, and consequentially, $P^{tr}(G) \\neq P^{te}(G)$. It's crucial to note our assumption that both $P^{tr}(G_C)$ and $P^{te}(G_C)$ retain the same support (namely, the **causal subgraph equal support assumption (CSES)**). Explicitly, our target is to resolve OOD scenarios where the supports of $P^{tr}(E)$ and $P^{te}(E)$ differ.\n\n2. Indeed, your question goes to the core of the subgraph discovery. Let's delve deeper into the mechanics of $f_\\theta$ which elucidates a more relaxed form of the aforementioned causal subgraph equal support assumption.\n\nIn essence, $f_\\theta$ operates as a classifier. When provided with an edge, it classifies the associated ego-graph of the edge into either label 1 (when the central edge is part of $G_C$) or label 0 (otherwise). We denote the distribution of $K$-hop ego-graphs on the edges of $G_C$ as $P(G^{K}\\_C)$, and the $K$-hop ego-graph space as $\\mathcal{G}^K$. Therefore, we have $f_\\theta: \\mathcal{G}^K \\mapsto [0,1]$, where $\\forall G^{K}\\_p \\in \\mathcal{G}^K, f_\\theta(G^{K}\\_p)=1$ when and only when $P(G^{K}\\_C=G^{K}\\_p) > 0$, i.e., the distribution of $f_\\theta$ is only affected by the support of $P(G^{K}\\_C)$. The CSES assumption can be relaxed to that $P^{tr}(G^{K}\\_C)$ and $P^{te}(G^{K}\\_C)$ have the same support. This ensures the invariance of $f_\\theta$ across both training and test distributions. Based on this relaxed assumption, it can be argued that $P(G_C|G)$ remains invariant when $f_\\theta$ is employed.\n\nNote that when $K$ is smaller, the assumption is looser. In contrast, when $K→+∞$, this assumption is equivalent to that $P^{tr}(G)$ and $P^{te}(G)$ have the same support, which is stringent. Therefore, $K$ is the \"locality rate\" for us to loosen a global equal support requirement to a local one.\n\n3. Clarification: $I(G_S;Y)\\le I(G_p;Y)$ is equivalent to $H(Y|G_S) \\ge H(Y|G_p)$ where $H$ denotes entropy, since $H(Y)$ is a const. We consider a random graph $G_S$ consist of a set of random variables (edges) $A_S$. $G_S \\subseteq G_p$ means $G_p$'s set of random edges $A_p = A_S \\cup A_{-}$, where $A_{-}$ is the set of additional edges in $A_p$. Therefore, $H(Y|G_S)=H(Y|A_S)\\ge H(Y|A_S,A_{-}) = H(Y|A_p)= H(Y|G_p)$, i.e., $I(G_S;Y)\\le I(G_p;Y)$.\n\n4. Absolutely. We've added **the table in the pdf of the global response.**\n\n5. You raise an important point. After extensive discussions with domain experts, it's evident that currently, no robust method exists to measure this aspect. It is challenging yet intriguing, and I'm keen to delve deeper into this in my upcoming research.\n\n6. \n(1) Your observation aligns with findings from DomainBed, where the OOD val results are better than ID val results. \n(2) As shown in the GOOD benchmark's Table 1, the differences in OOD performance on graphs aren't huge, which might relate to insights in [1].\n(3) Another consideration is the expressiveness of GNNs, which might impose constraints on the capabilities of OOD methods.\n\n7. \n(1) For clarity, both Twitter and DrugOOD are datasets external to the GOOD benchmark, i.e., at least 2 out of 5 real-world datasets lie outside the GOOD benchmark.\n(2) The availability of graph OOD datasets is somewhat limited, and our efforts were made towards encompassing the most widely-recognized graph-level datasets—molecules and languages. These datasets, aside from being utilized in established methods, provide robust empirical support for our claims. If you have specific datasets in mind, we are open to considering their inclusion.\n\n8. We appreciate your attention to detail. The identified typos have been corrected.\n\n## Limitations\n\n1. After refining our theoretical framework and assumptions, we can affirm that the OOD generalization performance is underpinned by the invariant $f_\\theta$ and $g_{inv}$.\n\n2. We understand that our method might not directly correlate with OOD errors. For context, current statistical graph modeling techniques [2, 3] are related to OOD generalization errors, albeit focusing on size shift analysis. Methods inspired by explanations, like DIR and LECI, offer practical solutions capable of addressing more shifts. Nonetheless, bridging these methods to OOD generalization errors presents a substantial challenge, which may not be solved in this single study.\n\n2. We have experimented with integrating environment information into GIL in B.3.2.\n\nDue to the space limit, please refer to our global response for more limitation discussions.\n\nSincerely,\n\nAuthors\n\n[1] Yang, C. et al. (2022). Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. arXiv preprint arXiv:2212.09034.\n\n[2] Bevilacqua, B. et al. (2021, July). Size-invariant graph representations for graph classification extrapolations. In ICML (pp. 837-851). PMLR.\n\n[3] Chu, X. et al. (2023). Wasserstein Barycenter Matching for Graph Size Generalization of Message Passing Neural Networks."}]

Author rebuttal:
# Rebuttal of LECI

## The strengths of this paper

We would like to extend our gratitude to all the reviewers for their invaluable time and insightful feedback. It is encouraging to observe that our contributions and strengths resonated positively with you:

- Novelty (Reviewer tVF4, YxXK, Csim)
- Presentation & Organizaion (Reviewer 6JF6, Csim)
- Motivations & Challenges & Problem formulation (Reviewer 6JF6, YxXK, Csim)
- Graph-specific exploitation method (Reviewer tVF4, 6JF6, YxXK, Csim)
- Theoretical results (Reviewer tVF4, 6JF6, YxXK, psug, Csim)
- Significant and diverse experimental results (Reviewer tVF4, 6JF6, YxXK, psug, Csim)
- Assumption's fairness comparisons (Reviewer Csim)

## The main message this paper can convey to the graph OOD community:

Utilizing a **graph-specific environment exploitation** method with **simply annotated environment partitions** can outperform all contemporary methods rooted in **refined human-made assumptions** (inductive bias), which underscores the need to reevaluate the practical implications of existing assumptions.

## The position of this paper

- The innovative graph-specific environment exploitation method (line 26)
- The first graph OOD method that passes structural shift sanity checks (line 294)

We recognize, as highlighted by Reviewer psug, that the absence of clear reading guidance in line 26 might have given rise to certain misinterpretations and concerns. To preclude any further misunderstandings, we present a comprehensive claim support list for any reviewers who might share these concerns or have related queries:
1. Extentions of the claim in line 26: line 76-88
2. Compared with environment-based methods (detailed claim justifications): Sec. B.3.1 in the appendix
3. Compared with environment-agnostic methods : Sec. C.2 and B.2 in the appendix.
4. Subgraph discovery challenge solution comparisons: Table 7 in the appendix.
5. Result comparisons between non-graph-specific and graph-specific environment exploitation methods under a fair/variable controlled setting: Sec. B.3.2 in the appendix.

This guidance will be integrated into the introduction of the paper.

## Common concerns

### Computational complexity analysis (Reviewer 6JF6, YxXK)

We will integrate this discussion following our method introduction: The time complexity of LECI is $O(md + nd^2)$ where $n$, $m$, and $d$ denote the number of nodes, edges, and feature dimension, respectively. To be more specific, the message-passing neural networks have time complexity $O(md+nd^2)$. Our environment exploitation regularizations have time complexity $O(1)$ without any extra cost. Therefore, the overall time complexity of our LECI is $O(md + nd^2 + 1) = O(md + nd^2)$.

### Explanations of the training dynamics in Figure 4. (Reviewer YxXK, psug)

During the initial phase of the training process depicted in Figure 4, independence constraints are minimally applied (or are not applied), ensuring a conducive environment for discriminator training. This approach is predicated on the notion that adversarial gradients yield significance only post the successful training of discriminators. The observed performance "drop" is attributed to the fact that the generalization optimization is yet to be activated, so it indicates the general subgraph discovery networks' performance. 

This is a normal phenonmenon, and we can directly apply high independence constrains if we pretrain the discriminators.

## Additional experiments

- One large table for empirical comparisons on FIIF and PIIF synthetic datasets in the attached PDF file.
- Other experiments are included in one-to-one responses.

## Limitations of this work

The main limitations of this work are challenges that might not cover by this paper but **do not affect the main claims and conclusions of this paper**.

### The training difficulty in standard adversarial training.

We acknowledge the intrinsic complexities of adversarial training (characterized by bi-level optimization). However, two clarifications are in order: (1) refining the bi-level optimization process (e.g., the implementation of Wasserstein loss or consensus optimization) does not constitute the crux of our paper, and (2) despite these complexities, standard adversarial training has still rendered robust results, vindicating our claims. We've documented this limitation in section C.4 of our appendix.


### The accessibility and quality of environment labels.

Employing simple grouping strategies may inadvertently introduce noise into environment labels. Yet, our results unequivocally demonstrate that even such "noisy" environment labels surpass the efficacy of current sophisticated inductive biases. To obtain deeper insights into this comparison, please refer to section B.2 in our appendix. This observation, in turn, reinforces the resilience of our primary claims.

--------------------------------------

We're deeply appreciative of the insightful comments and open questions presented. We're eager to delve into these during our one-to-one rebuttal discussions. It's pertinent to note that while many of the questions are indeed thought-provoking and present fascinating challenges, the expansive nature of some may be beyond the scope of this singular piece of work. We humbly request that this be taken into consideration during the paper's reevaluation. Our sincere gratitude for the time invested and the invaluable feedback.

Sincerely,

Authors

Meta-review: This paper addresses the problem of graph out-of-distribution generalization by incorporating label and environment causal independence simultaneously. I thank the authors and reviewers for the engaging and very comprehensive discussions. 

The reviewers have highlighted that the paper is technically sound; that the illustration of graph OOD generalization from a causal perspective is clear and easy to understand; that theoretical results are strong and rigorous, showing that the derived optimal parameters can lead to learning causal subgraph only for invariant prediction;  and that the empirical evaluation is comprehensive, with the proposed approach outperforming existing methods by a large margin. 

Some weaknesses were pointed out, for example, regarding computational complexity. I believe these have been addressed by the authors satisfactorily. The main critical point, however, is that of novelty, which was raised by one of the reviewers (psug). Novelty is largely a subjective criterion and none of the other reviewers either expressed a concern or praised the paper about it. Furthermore, Reviewer psug did not express additional _specific_ concerns wrt this issue after the authors’ rebuttal. I believe the authors have clarified how the paper relates to previous work (e.g., [1-2]) and how the paper contributes to the literature wrt other methods that have used environment-based approaches. 

Overall, I believe this paper has enough contributions to be presented at NeurIPS and I trust the authors’ judgment to make the necessary changes, including the material presented at the rebuttal and in the appendix (esp. wrt to clarity on the novelty and relation to previous works).
Decision: Accept (poster)