Dissecting the Failure of Invariant Learning on Graphs

We thank Reviewer nx4e for your careful reading and detailed comments! We'd like to address your concerns in the following points:

Q1: G in Fig. 1 is not mentioned in the text

A1: Sorry for the lack of clarity. $G$ refers to the graph data.

Q2: limitation: the definition of the GNN in Eq. 3 which is a linear model

A2: Justifications for analyzing a linear model: 1) Some recent works [8] [9] observed that linear GNNs achieve comparable performance to nonlinear GNNs. [5] also theoretically proved that SGC can outperform GCN under some mild assumptions. 2) many recent works on the theoretical analysis of graphs/OOD generalization adopt linear networks ([4] [10] [11]). 3) Our theory matches the experimental results on the nonlinear GCN and GAT that CIA outperforms IRM and VREx.

Q3: line 204: it is a bit counter-intuitive why invariant node features of nodes with the same class should significantly diverge when they are far apart in the graph.

A3: Although the invariant features of the same class are basically invariant across environments, they still show some slight intra-class deviation (see Fig. 7-10). In the same class, the invariant feature difference between nodes that are farther apart is larger than the difference between nodes that are closer together. In Fig. 7/8, despite the curve's slight fluctuations, the invariant feature difference shows a clear positive correlation with the distance from the starting point.

Q4: a brief definition/discussion of concept and covariate shift would be beneficial for clarity

A4: Due to word limitation, we invite you to refer to the A1 to the reviewer yNy3.

Q5: in line 232: why is a sum operator employed here instead of a mean?

A5: We employ a 'sum' in line 232 because $r_i^c$ is the ratio of nodes of class $c$ in the $L$-hop neighborhood, which has already been normalized by the size of the neighborhood. It won't be affected by the graph size/connectivity.

Q6: in theorem 4.2 it is unclear what $\\alpha$ is and what the inequation $0<\\alpha<\\frac{1}{4}$ means. Discussion on the goodness/tightness of the given bound?

A6: Sorry again for the lack of clarity. $\\alpha$ is defined in Assumption 3 of [6]: "...... Assume that there exists some $0<\\alpha<\\frac{1}{4}$ satisfying $\\operatorname{Pr}_{h \\sim P}\\left(\\mathcal{L}_m^{\\gamma / 4}(h)-\\mathcal{L}_0^{\\gamma / 2}(h)>N_0^{-\\alpha}+c K \\epsilon_m \\left\\lvert\\, T_h^L \\epsilon_m>\\frac{\\gamma}{8}\\right.\\right) \\leq e^{-N_0^{2 \\alpha}}$". This assumption is needed for proving Lemma 6 in [6], which we rely on to prove of Lemma G.11 in our paper.

• Tightness of Theorem 4.2: when there are no distributional shifts in spurious node features and heterophilic neighborhood distribution between training and test environments, the terms (a)-(d) in Eq. 109 becomes zero, and the upper bound becomes \\widehat{\\mathcal{L}}\_{e^{\\text{tr}}}^\\gamma(\\tilde{h})+const=\\widehat{\\mathcal{L}}\_{e^{\\text{tr}}}^\\gamma(\\tilde{h})+\\frac{1}{N_0^{1-2 \\alpha}}+\\frac{1}{N_0^{2 \\alpha}} \\ln \\frac{L C\\left(2 B_{e^{\\text{te}}}\\right)^{1 / L}}{\\gamma^{1 / L} \\delta}, i.e., our bound only larger than the ideal error \\widehat{\\mathcal{L}}_{e^{\\text{tr}}}^\\gamma(\\tilde{h}) by a constant $const$. When the number of training samples $N_0$ is large, $const$ will be small enough and can be negligible. Hence, the tightness of our bound is guaranteed.

Q7: proof G 1.1.: the proof only shows that $\\theta_2=0$ is a possible solution, but not a unique solution, isn't it?

No. $\\theta_2=0$ is a unique solution. Please see lines 855-861, line 868.

Q8: **Eq. 34: the entire term does not depend on $\\theta_2$, so it is unclear why $\\theta_2$ is the solution to that equation. **

A8: Eq. (34) is the result of plugging $\\theta_2=0$ into the expression $\\frac{\\partial\\mathbb{V}_e[R(e)]}{\\partial \\theta_2}$, thus $\\theta_2$ disappears.

Q9: won't all mutliplicative terms entailing $\\epsilon^e$ cancel out in the expectation?

A9: Although $\\mathbb{E}_e[\\epsilon^e]=0$, but \\mathbb{E}_e[{\\epsilon^e}^\\top\\epsilon^e]=N_e\\sigma^2>0, where $\\sigma^2=\\mathbb{V}_e[\\epsilon^e_i],~i=1,...,N_e$. So the terms multiplied by {\\epsilon^e}^\\top\\epsilon^e won't be canceled out.

Q10: line 995: which property are you referring to exactly?

A10: For two vectors $a$ and $b$ ($a\\neq \\lambda b$, $\\lambda$ is any scalar), we have $|a\\cdot b|^2 \\leq |a|^2|b|^2$.

Q11: it would be good to see some more recent baselines such as [1] and [2]

A11: We have already included [1] (SRGNN) in our main experiment in Table 2 of the orginal paper. We didn't compare with [2] since it requires the graphs of different environments to have the same nodes but our datasets don't satisfy this. However, we add two more recent graph OOD methods CIT ([7] suggested by reviewer LzeD) and CaNet ([12] suggested by reviewer empj) as baselines. Please see Table B of the rebuttal PDF. CIA-LRA outperforms CIT and CaNet on all splits.

Q12: line 296: why does CIA-LRA improve upon CIA? It is counter-intuitive since CIA-LRA has no access to the environment labels

A12: We also invite you to refer to A6 to the reviewer yNy3.

Q13: missing related works

A13: We've already discussed [1] in Appendix A.3. Here we discuss [2]. [2] proposed to align the aggregation weights of the same edge across environments ("locally stable learning") and align the cross-environment loss ("global stable learning"). There are some drawbacks. First, the "locally stable learning" requires the graphs from different environments to have the same nodes and topological structures, which is impractical; second, the "global stable learning" is actually a VREx loss that we proved to have failure cases in node-level OOD tasks.

Q14: repeating experiments & typos

A14: We repeat our experiments with three different random seeds. We have fixed all typos you mentioned.

We thank Reviewer yNy3 for your careful reading and detailed comments! We'd like to address your concerns in the following points:

Q1: The author may want to clarify the reasoning behind the two SCMs corresponding to the two types of distribution shifts, as this connection is not entirely clear

A1: Here we'd like to clarify the connection between the SCMs and the two type of distributional shifts.

Definitions of the two shifts:

Concept shift: $p_{Y|S}(y|s)$ changes across environments, and $p_X(x)$ is invariant across environments; Covariate shift: $p_X(x)$ changes across environments, and $p_{Y|S}(y|s)$ is invariant across environments.

Concept shift and Fig. 1(a): Suppose $X=f(C, S)$. In Fig. 1(a), $S$ is the direct cause of $Y$ and the mapping from $Y$ to $S$ is affected by environments $E$. This means $p_{S|Y}(s|y)$ changes across environments. Now we show that this makes $p_{Y|X}(y|x)$ varies with environments. $p_{Y|X}(y|x)=\\frac{p_{X,Y}(x, y)}{p_X(x)}=\\frac{\\sum_{c, s: x=f(c, s)} p_{Y \\mid C, S}(y \\mid c, s) \\cdot p_{C, S}(c, s)}{p_X(x)}$. Taking out the $p_{Y \\mid C, S}(y \\mid c, s)$ in the molecule, we have $p_{Y \\mid C, S}(y \\mid c, s)=\\frac{p_{S|Y}(s|y)p_{C|Y}(c|y)p_Y(y)}{p_{C,S}(c,s)}$. Since $p_{S|Y}(s|y)$ varies with environments, we conclude that $p_{Y|X}(y|x)$ is also variant, which matches the definition of the concept shift.

Covariate shift and Fig. 1(b): In Fig. 1(b), $S$ is independent of $Y$ and only depends on $E$, which means $p_{Y|X}(y|x)$ is invariant across environments. Additionally, $p_X(x)=\\sum_{c,s}p_{X|C,S}(x|c,s)p_{C,S}(c, s)=\\sum_{c,s:x=f(c,s)}p_{C,S}(c,s)=\\sum_{c,s:x=f(c,s)}p_{C|S}(c|s)p_{S}(s)$. According to Fig. 1(b), $S$ is the direct cause of $E$ so $p_{S}(s)$ changes with environments. Hence, we conclude that $p_X(x)$ changes with environments, which matches the definition of the covariate shift.

Q2: Assuming the same label corresponds to the same invariant factors, it is unclear why $r^{same}$ is necessary for reweighting.

A2: In practice, although the causal features of the same class are basically invariant across environments, they still show slight deviation among the samples within this class (shown in Fig. 7-10), and this intra-class discrepancy in invariant features has a positive correlation with the difference in same-class neighborhood label distribution (evidence in Fig. 15). Hence, we design $r^{same}$ to prevent the over alignment that may cause the collapse of the invariant features. Table 4 and Fig. 2 reveal the positive role of $r^{same}$.

Note that the main purpose of this assumption is for the ease of theoretical analysis. However, this assumption is also acceptable in practice, supported by two pieces of evidence: 1) CIA improves over most non-graph-specific baselines 2) In Table 4, merely removing $r^{same}$ (63.91) from CIA-LRA still outperforms IRM (61.14) and VREx (61.32).

Q3: the typical node-level classification setting is semi-supervised, which limits the applicability of this method.

A3: Our experiments are exactly conducted in a semi-supervised setting in which only 30%~40% of nodes are labeled. CIA-LRA only operates on the labeled data to gain improvements.

Q4: The authors may want to compare and contrast their approach with CIGA.

A4: Differences between CIA-LRA and CIGA:

• CIGA cannot solve covariate shifts. CIGAv2 maximizes the mutual information between the estimated spurious subgraph $\\hat{G_s}$ and labels $I(\\hat{G_s};Y)$ to reduce including part of $\\hat{G_s}$ into the true invariant graph $G_c$. For covariate shifts, $G_s$ contains no information about $Y$, thus $\\max I(\\hat{G_s};Y)$ may not capture the correct $G_s$. Therefore, the estimation of the invariant subgraph $\\hat{G_c}=G-\\hat{G_s}$ will be also inaccurate.
• CIA-LRA works for both shifts. Our strategy doesn't rely on the concept shift assumption to minimize the OOD error. There are two main reasons. First, under covariate shifts, CIA-LRA removes environment-related spurious node features when the selected pairs potentially come from different environments. Second, CIA-LRA can simultaneously reduce the error caused by structural shifts of heterophilic neighborhood label distribution (the term (c) in the error bound in Theorem 4.2 can be minimized by CIA-LRA regardless of the type of the distributional shifts).

Q5: CIA-LRA learns masked subgraph, is the experiment inductive or transductive?

A5: All four datasets of our experiments are transductive.

Q6: In line 318-321, why CIA will be less performant than CIA-LRA, it seems not reasonable, as CIA will adopt environment labels while CIA-LRA doesn’t.

A6: The role of environment labels is to distinguish spurious features so that the they can be eliminated by cross-environment alignment. However, even if spurious features are removed (Fig. 2 right, CIA), learning a collapse representation of invariant features can also hurt generalization (shown in Fig. 2 Left and Mid, CIA). Although CIA-LRA doesn't use environment labels, it can remove spurious features by intra-class alignment and the proposed $r^{diff}$ (see Fig. 2 right, CIA-LRA and term (b) (c) in Theorem 4.2). Moreover, it avoids the collapse of invariant features caused by overalignment by only aligning local pairs and using $r^{same}$ (Fig. 2 Mid, CIA-LRA). Therefore, CIA-LRA outperforms CIA even without environment labels.

Q7: $\\theta_m$ is separated from $\\theta$, how to ensure it will learn the invariant subgraph, under what assumptions?

A7: We are sorry that we did not fully understand which parameter in Eq. (3) the "$\\theta_m$" you mentioned here refers to. We'd like to address any of your further questions.

Q8: typos

A8: Thank you for carefully identifying all typos! and we have fixed all typos you mentioned:

• Eq. (9): $\\phi(i)\\rightarrow \\phi(j)$
• Line 231: "to pairs with" $\\rightarrow$ "to pair with".
• Line 854: Removed ${\\tilde{A}^e}^k$

I appreciate the reviewer’s great efforts for the response. However, I still have some concerns.

Q9

I understand the author’s explanation regarding concept shift and covariate shift. However, I believe that the SCM presented in Figure 1 merely represents an underlying data generation process, which may not directly correspond to the types of distribution shifts. This could be potentially misleading.

Q10,12

• Although there is no edge from C to S in Figure 1b, according to the definition of FIIF, the condition $I(S;Y|C)=0$ still holds.
• FIIF and PIIF represent data-generating processes, and therefore do not directly correspond to concept shift.
• CIGA primarily addresses covariate shift, where the conditional distribution $P(Y|G)$, i.e., the underlying mechanism, remains unchanged, while $P(G)$ shifts due to spurious features.
• I recognize the contribution of this work in addressing excessive alignment. However, the basic idea aligns with supervised contrastive learning, which is why I perceive similarities with previous studies like CIGA.
• The utilization of techniques such as neighborhood label distribution is indeed novel, but they are not directly applicable to graph-level OOD. This is why I consider CIA-LRA to be an adaptation of supervised contrastive learning for node-level OOD.
• Overall, I remain positive about this work due to its high-quality writing and rigor. However, I also have concerns about the level of novelty in the proposed method. Additionally, some design choices in the methodology appear heuristic (in Sec. 3.2), which also raises some concerns.

Dear reviewer yNy3, we note that you have lowered your score from 6 to 5. If you have any questions please let us know and we will be happy to answer them!

Thanks for the authors' efforts for constructing the response. Some of my concerns cannot be addressed in the rebuttal stage, such as:

1. in Q15, under FIIF, since $I(S;Y|C)=0$, which implies that $P(Y|C,S)=P(Y|C)$ when conditioned on $C$.

2. The claim that the approach would solve concept shift is also problematic. Most invariant learning methods ever since IRM would assume a stable relations between semantic objects and $Y$, hence they aim to solve covariate shift but not concept shift. One example would be a cow in a picture would always be mapped to $Y=1$, hence it is invariant; Otherwise, in concept shift, a cow would be mapped to a different label, indicating that there is no stable features, but instead, the underlying responsive mechanism changes, rather than the spurious features. The claim that this approach, which is a refinement of supervised contrastive learning, can solve concept shift is not convincing.

3. Some designs in the approach remain heuristic.

For the above reasons, I won't raise my score, and won't lower my score given the strength of this work. However, I strongly suggest that the authors reconsider the claim that CIA would solve concept shifts, which is my biggest concern for this work.

We thank Reviewer LzeD for your careful reading and detailed comments! We'd like to address your concerns in the following points:

Q1: Limited comparison to recent node-level OOD method [1].

A1: We've added the evaluation of CIT [1], the results are in Table B of the rebuttal PDF. We use the default hyperparameter setting for CIT from the code provided by the authors of [1]. CIA-LRA outperforms CIT on all splits.

Q2: Lack of visualization of the overall method architecture to help readers understand intuitively.

A2: We've added a figure to better illustrate the overall framework of CIA-LRA, please refer to Fig. A in the rebuttal PDF file.

Q3: a more detailed analysis of the computational complexity and runtime comparisons of CIA and CIA-LRA against baselines would be valuable.

A3: We show the time cost to reach the best test accuracy on our largest dataset Arxiv (with 50k~60k nodes) in Table C below. On smaller datasets (Cora, WebKB, CBAS), the running time gap is small and negligible (all methods including CIA-LRA only cost less than 60s to reach the best performance). Table C shows that the time costs of CIA-LRA and CIA are comparable to baseline methods.

Table C: Time cost (seconds) to achieve optimal test performance on Arxiv using GAT on a single RTX 3090 GPU.

Q4: Insufficient citations of recent methods, such as [2] [3].

A4: Thank you for pointing out the missing related works.

[2] address the graph-level OOD generalization. Their task settings differ from ours in two aspects: 1) They focus on covariate shift, so they enforce $Y\\perp G_s$ which doesn't hold for concept shifts. However, our proposed CIA and CIA-LRA work for both covariate and concept shifts. 2) They assume the availability of environment labels while our work tackles invariant learning without environment labels.

[3] address both the graph-level and node-level OOD generalization. They proposed to minimize the mutual information (MI) between the input graph and its representations to eliminate spurious features and maximize the MI between the representations and corresponding labels to learn invariant features. However, their method lacks rigorous analysis of how it can achieve the above two goals. Additionally, their setting is also different from ours: [3] assumes the availability of multiple graphs, while our work focuses the learning on a single graph.

Dear reviewer LzeD,

I hope this message finds you well. As the discussion deadline is approaching in a few hours, I kindly wanted to remind you of the pending feedback for our submission. We have tried our best to address the concerns and revised our paper accordingly. Your insights are invaluable to us, and we eagerly await your comments to improve our work further.

Thank you for your time and consideration!

We thank Reviewer empj for your careful reading and detailed comments! We'd like to address your concerns in the following points:

Q1: The authors seem to leave out some baselines in their experiments. The authors should better motivate which baselines they compare against and which they don't.

A1: As you advised, we've added experiments of CaNet [Wu et al., 2024]. We didn't compare with [Li et al., 2023b] since their methods require the graphs of different environments to have the same nodes and edges so that their proposed locally stable regularizer can be applied, however, the datasets used in our experiments don't have this property. To include more baselines, we further implement CIT ([7], NeurIPS 2023, suggested by reviewer LzeD), a recent node-level Graph OOD method. The results are included in Table B in the global author rebuttal PDF. We use the default hyperparameters for CaNet and CIT. We observe that CIA-LRA outperforms CIT and CaNet on all splits.

Q2: As such, it reasons that MatchDG should be included in the experiments as a baseline.

A2: We've added the experiments of MatchDG in Table B in the rebuttal PDF. The results show that: 1) MatchDG outperforms IRM and VREx on 12 out of 16 splits. 2) MatchDG underperforms CIA on average (averaged over 16 splits except on Arxiv, CIA: 57.56, MatchDG: 56.73), and MatchDG got out of memory on Arxiv. We emphasize that although CIA is similar to MatchDG, our contribution is that we're the first to extend the idea of MatchDG to the node-level OOD task by providing a theoretical characterization of CIA’s working mechanism on graphs (Theorem 3.1) and reveal its superiority in node-level OOD scenarios. More importantly, our main contribution is that we further extend CIA to the scenarios where environment labels are unavailable by proposing CIA-LRA, which shows significant empirical gains (Table B) with theoretical guarantees (Theorem 4.2).

Q3: There's a lack of discussion on the efficiency (time complexity) of the method.

A3: To show the running time of CIA-LRA, we show the time cost to reach the best test accuracy on our largest dataset Arxiv (with 50k~60k nodes). The results are in Table C below. The time cost of CIA-LRA is comparable to baseline methods.

Table C: Time cost (seconds) to achieve optimal test performance on Arxiv using GAT on a single RTX 3090 GPU.

Q4: What's IRMv1? You begin by mentioning the failure of IRM but then start calling it IRMv1

A4: Sorry for the lack of clarity. IRMv1 refers to the practical implementation of the original challenging IRM objective, which is proposed by the authors of IRM. IRMv1 relaxes the bi-leveled optimization of IRM that $w$ should be the optimal classifier in all training environments to a gradient penalty term:

$(\\text{IRM}) \\min_{w, \\phi} \\mathbb{E}_e\\left[\\mathcal{L}\\left(w \\circ \\phi\\left(X^e\\right), Y^e\\right)] \\quad \\text{s.t.} w\\in \\arg\\min\_{\\bar{w}} \\mathcal{L}\\left(\\bar{w} \\circ \\phi\\left(X^e\\right), Y^e\\right)\\right\\|_2^2 ~ \\text{for all} ~ e \\in \\mathcal{E}^{tr}$

$(\\text{IRMv1}) \\min_{w, \\phi} \\mathbb{E}_e\\left[\\mathcal{L}\\left(w \\circ \\phi\\left(X^e\\right), Y^e\\right)+\\beta\\left\\|\\nabla\_{w|w=1.0}\\mathcal{L}\\left(w \\circ \\phi\\left(X^e\\right), Y^e\\right)\\right\\|_2^2\\right]$

Q5: How different would the conclusions be if we considered a more standard GNN like GCN

A5: When we consider a GCN rather than an SGC, the main difference is that we will apply a weight matrix at each layer rather than just at the final layer. Still, consider the simple 2-dim data case, for a GCN (without activation functions), we can rewrite the inference of a layer as:

where $H_1^{(l)}$ and $H_2^{(l)}\\in\\mathbb{R}^{N\\times1}$ follows the definition of the original paper in Eq.(3), $\\theta_1^{(l)}$ and $\\theta_2^{(l)}\\in \\mathbb{R}^{1\\times2}$ . For the GCN, the parameters of the first layer of the weight matrix $\\theta_1^{(1)}$ and $\\theta_2^{(1)}$ correspond specifically to invariant (first dimension of $x$) and spurious (second dimension of $x$) features, respectively. From the second layer upwards ($l\\geq 2$), both dimensions of the representation at layer $l$ will be the linear combination of the two dimensions of the representation at layer $l-1$. Hence, the GCN removes spurious features only when the parameter at the first layer $\\theta_2^{(1)}=0$. In conclusion, we only need to focus on the first layer to analyze wether GCN learns spurious node features. This resembles the case of SGC where we only need to focus on the weights at the last layer. So the conclusions of the SGC could be easily extended to the GCN.