IMPaCT GNN: Imposing invariance with Message Passing in Chronological split Temporal Graphs

Authors: Sejun Park, Joo Young Park, Hyunwoo Park
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Domain Adaptation, Distribution Shift, Temporal Graph, Chronological Split, Semi-Supervised Node Classification, Generalization Bound

Abstract:
This paper addresses domain adaptation challenges in graph data resulting from chronological splits. In a transductive graph learning setting, where each node is associated with a timestamp, we focus on the task of Semi-Supervised Node Classification (SSNC), aiming to classify recent nodes using labels of past nodes. Temporal dependencies in node connections create domain shifts, causing significant performance degradation when applying models trained on historical data into recent data. Given the practical relevance of this scenario, addressing domain adaptation in chronological split data is crucial, yet underexplored. We propose Imposing invariance with Message Passing in Chronological split Temporal Graphs (\IMPaCT), a method that imposes invariant properties based on realistic assumptions derived from temporal graph structures. Unlike traditional domain adaptation approaches which rely on unverifiable assumptions, \IMPaCT explicitly accounts for the characteristics of chronological splits. The \IMPaCT is further supported by rigorous mathematical analysis, including a derivation of an upper bound of the generalization error. Experimentally, \IMPaCT achieves a 3.8\% performance improvement over current SOTA method on the ogbn-mag graph dataset. Additionally, we introduce the Temporal Stochastic Block Model (TSBM), which replicates temporal graphs under varying conditions, demonstrating the applicability of our methods to general spatial GNNs.

Decision: reject
Reviewer scores: 5, 3, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1730539577180

thread_type:
official_review

<thread_object>
creator: reviewer_xzdb

<content>
summary:
The paper addresses non-stationary behaviors observed at the temporal boundaries of temporal graphs. Specifically, it proposes weighting techniques to adjust message-passing operations, enabling the learned representations to maintain a degree of invariance over time. While the novelty is reasonable rather than groundbreaking, I appreciate the effort to tackle these issues, as I am not aware of other papers that address them explicitly.

strengths:
- Addressing biases introduced by data partitions is a relevant and valuable challenge.
- Some of the proposed techniques are demonstrated effective in mitigating the targeted issues.

weaknesses:
- The paper presentation does not appear mature enough for publication. 
- The math appears insufficiently rigorous.
- The proposed methods are limited to a specific family of message-passing operators that rely on average aggregation, without accommodating more complex methods like attention or target node-dependent messages.
- Some of the experiments are not convincing.

questions:
Questions.
- The concept "Relative connectivity $\mathcal P$" is not clearly introduced. Does it represent the empirical distribution of edges across time and node classes?
- Where does the randomness associated with  $x_{yt}^{(k)}$ come from? Does it originate solely from the system model generating the node features? 
- Eq 7. Why is "IID"? It looks to me that they are not "identically distributed" as they depend on $k$, $y$ and $t$, nor independent due to the message passing.
- Eq 28, part b is said to be an approximation. If so then the equality symbol should not be used. Could you clarify in the paper which steps involve approximations and which provide strict equalities?
- Line 219 is in contrast with assumption 3. If the probability decays then the two contributions do not match. Am I missing something here? How can this apparent contradiction be reconciled?
- Training times in Table 3. How is it possible that training for 200 epochs takes only a fraction of a second? Why does PMP on SGC take less time than the baseline? 
- PNY and JJnorm on GCN have extremely long training times (about 500 X more than the others), which is concerning. Could you comment on it?
- Results on OGB-mag data are around 90% accuracy which does not appear in line with their website reporting ~57% for leading models. Could you elaborate on this?
- How difficult is it to port the designed techniques to more general message-passing operators and to apply them to the methods leading the OGB benchmarks?
- I could not find a discussion about the extent to which trainable model parameters within the message passing impact the proposed weighing techniques. Could you elaborate?
- Line 22. Which "unverifiable assumptions" are you referring to exactly?
- Line 128 "data from different environments may have interdependencies, and the extrapolating nature of environments complicates the problem." is completely unclear to me. Could you clarify it?


Further comments and suggested improvements:
- The addressed temporal graph learning problem is not formally stated. It becomes clear only once the datasets are presented. I suggest providing a thorough formulation and introducing there the adopted notation. In this regard, I suggest formulating a more general message passing involving a temporal graph so that the reader can relate to it the new methods later on.
- Figures 2 and 3 are not super informative and, in my opinion, unnecessary. Figure 2 only shows a decay along the temporal semi-axes - a concept that could be given for granted. Figure 3 is not accompanied by a description. 
- Denoting a distribution as $x_{yt}^{(k)}$ is rather confusing. 
- One important element is that the non-stationary behavior (here called invariance - which, by the way, I don't think is the most appropriate term to use here) comes from the edges rather than the node features, as per the assumptions made. However, such dependency from the edges does not emerge from the math developments. 
- What does "discrete value" mean in A.4? They are indeed positive integers.
- The term "persistent" in 4.1 is unclear.
- Table 3. Please provide variability indices (eg, std) alongside results.
- Decoupled GNN seems to not be introduced or referenced.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730640650566

thread_type:
official_review

<thread_object>
creator: reviewer_hosu

<content>
summary:
This paper addresses domain adaption issues in graph data, particularly in datasets where the train and test splits are organized chronologically. The proposed method, named IMPaCT, assumes the separability of relative connectivity among nodes in the graph at different time points. Based on this assumption, the authors impose the invariance property in message-passing methods and provide various theoretical analyses on the generalization error.

strengths:
- The paper is well structured, clearly presenting the problem and the proposed solution. The theoretical foundation of the proposed methods is robust, and experiments are presented to demonstrate their effectiveness.
- If we accept the correctness of the assumptions, especially Assumption 3 regarding the separability of relative connectivity, the proposed idea is quite intuitive. That is, if the first moment of the previous representation remains invariant over time t, the expectation of the aggregated message can be independent of t when the target node (label y, time t) receives information twice from neighbors in T_{single}.

weaknesses:
The Assumption 3 may raise the following issues:
- Ensuring invariance of 1st moment of the previous representation: the authors introduce Assumption 2 to address this concern. If the 1st moment of the previous representation is not invariant, how can the invariance of the aggregated message be maintained. How to ensure the 1st moment of initial features of graph nodes invariant?
- Effectiveness of graph modification: While modifying the original graph may benefit average message passing procedure, this approach might not be effective for other frameworks, such as Graph attention network or Message passing neural networks, where the weighting of average procedures is not independent of time t.

Minor comments:
- Line 852: Equation (30) may contain a typo.
- Line 1737, Equation (161), do P on the left-hand side and right-hand side refer the same one?
- in Subsection 6.1, the def of f(y,t) from Assumption 3 is not provided

questions:
- See Weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730659824321

thread_type:
official_review

<thread_object>
creator: reviewer_u8i5

<content>
summary:
This paper studies the problem of domain adaptation on temporal graph data under chronological splits. It introduced a novel IMPaCT approach to enforce invariant message passing via the 1st and 2nd moment alignments. The invariance of the proposed invariant message passing is theoretically analyzed. Experimental results also demonstrated the effectiveness of the invariance regularizations on real-world temporal graphs.

strengths:
**Originality:** This paper studied the issues of chronological splits in applying GNNs to temporal graphs. It empirically observed the distribution shifts induced by the chronological splits. Then a novel IMPaCT was proposed by enforcing invariant node representation learning. Both the 1st and 2nd moments of aggregated messages were leveraged to improve the feature invariance. 

**Quality:** Theoretical analysis showed the invariance of the iterative message aggregation using the proposed approaches. Besides, the generalization error bound based on the Wasserstein-1 distance was derived to show the impact of invariant message aggregation.


**Clarity:** The motivation of the studied problem was clear. The issues of chronological splits were validated in several real-world temporal graphs. 


**Significance:** The developed theoretical analysis and algorithms extended the applications of GNNs from standard static graphs to temporal graphs under distribution shifts.

weaknesses:
(W1) The defined approximate expectation $\hat{\mathbb{E}}[M^{k+1}_v]$ requires the IID assumption of $X_w$. This assumption is not justified on temporal graphs.

(W2) Theorem 4.1 and Theorem 5.1 show that PMP layers result in the invariance if the previous representation is invariant. It is unclear how the invariance of the initial representation can be guaranteed. If the previous representation is not invariant, will the aggregation of PMP layer worsen the invariance?

(W3) Another concern is the related work and baselines in the experiments. Graph domain adaptation and temporal GNNs have been studied in recent years. Those works can be discussed in the related works, and recent graph domain adaptation and temporal GNNs can be employed as the baselines to validate the effectiveness of the proposed approaches.

questions:
(1) It is confusing why the target node receives twice the weight from $\tilde{t} \in \mathbf{T}_t^{double}$ against $\tilde{t} \in \mathbf{T}_t^{single}$.

(2) The generalization error bound depends on $C$ and $V$ defined in Section 4.3. The tightness of the derived generalization error bound can be further illustrated. As shown in lines 311-314, $V$ can be large in some cases.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730682006352

thread_type:
official_review

<thread_object>
creator: reviewer_6xgv

<content>
summary:
This paper studies the impact of chronological split in temporal graph learning. The authors propose a family of message passing methods named IMPaCT that accounts for the distribution shift between training and test due to the temporal effect.

strengths:
S1. Chronological split affects the temporal graph learning's performance, and this paper aims to study this important problem.

S2. Experimental results show improvements in test accuracy.

weaknesses:
W1. There are many related works about out-of-distribution generalization and invariant representation learning on graphs, as evidenced by several surveys and GitHub repo. It seems a bit contradicting to the authors' claim that there are not many related works. It would be great if the authors could further explain why these lines of works are not discussed.

W2. The observation about the decreasing proportion of neighbors as $|\tilde{t} - t|$ increases are mostly driven by the example in citation networks. I think this makes sense in citation networks, but it is unclear whether this trend also holds in other networks, say user-item interaction graphs in recommender systems or online social networks, where users can join or leave the system/network at any time. 

W3. It would be great if the authors could discuss what types of shift (or the discrepancy between which distributions) this paper considers in a more formal way.

W4. I am a bit confused where the authors discussed the claim: "As discussed, the target node receives twice the weight from $\tilde{t}\in\mathbf{T}^{\text{double}}\_{t}$ against $\tilde{t} \in \mathbf{T}^{\text{single}}_{t}$." Could you please provide a pointer?

W5. It is questionable whether aligning first and second moment implies invariance, as skewness, tailedness, modes could all affect the shape of a distribution.

W6. Overall this paper is not self-contained. I have a hard time understanding many math notations in theorems given the lack of explanation in the main body (e.g., almost all theorems starting from theorem 4.3), and I need to check back and forth between main body and appendix to understand the paper. I believe a reorganization of the contents are needed for better clarity.

W7. The evaluation protocol is unclear to me. For example, PNY is proposed but never evaluated, so I am not sure what the purpose is to have PNY here. MMP, PMP, JJNorm is only evaluated on LDHGNN, but not on RevGAT and GAMLP, while GenPMP is not evaluated on LDHGNN. 

W8. What is the rationale of evaluating on LDHGNN, RevGAT, and GAMLP rather than classic temporal graph learning models? Also, the authors do not explain what SimTeG, TAPE, and GLEM are. Overall, the choice of baseline methods are very vague.

questions:
Please see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730883129322

thread_type:
official_review

<thread_object>
creator: reviewer_l1bx

<content>
summary:
This paper explores the problem of domain adaptation of temporal maps and proposes a method to realize the invariant property based on realistic assumptions. The method takes into account the characteristics of temporal splitting and also introduces the Temporal Stochastic Block Model (TSBM) to replicate the temporal graph under different conditions.

strengths:
1. This paper addresses the intriguing challenge of proposing the invariant messaging function IMPaCT to tackle the domain adaptation issues in graph data that arise from temporal splitting.
2. The authors establish a framework of assumptions grounded in observable properties and introduce an invariant theory for first-order and second-order moments, which offers a robust theoretical foundation for future research.
3. The IMPaCT method demonstrates substantial improvements in classification accuracy across multiple datasets when compared to existing state-of-the-art methods, highlighting its advantages in processing graph data effectively.

weaknesses:
1.The paper explores the problem of out-of-distribution generalization in temporal graphs; however, the INTRODUCTION section does not adequately address the unique challenges associated with this issue. The authors should elaborate on how the difficulties of out-of-distribution generalization in temporal graphs differ from those encountered in static graphs and Euclidean data (e.g., images). A clearer articulation of these challenges would enhance the understanding of the problem's significance and context.

2.There is a lack of comparison between relevant aspects of the proposed work and existing methods. Could the authors clarify how their approach measures up against current state-of-the-art techniques in the domain?

3.How is the effectiveness of the PMP and MMP in adjusting the invariance of the first moments assessed?The MMP only collects information from past nodes, which may lead to insufficient information. How do the authors explain the potential impact of this limitation on model performance?

4.On what theoretical basis is the weight adjustment of generating nodes in GenPMP based? Can the authors explain in detail how the rationality of \(P_{t_{\text{max}}}(\Delta)/P_{\tilde{t}}(\Delta)\) was determined and its impact on the results?

5.Please explain why different baselines are used on different datasets?

6.The authors assert that this paper tackles the challenge of domain adaptation in graph data resulting from temporal splitting. However, as far as I am aware, the ogb datasets are predominantly utilized for node classification in static graphs. How effectively does the proposed method perform on dynamic graph datasets, such as Tmall and MathOverflow?

questions:
Please see Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732709920777

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear reviewers, we have uploaded a revised version of our paper. Please check it out, and we respectfully ask considering re-evaluation of initial scores if the concerns are addressed.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies what the reviewers agree is an important and interesting issue that arises when applying machine learning to temporal graphs: if the training/test split is not random but rather chronological (e.g., training nodes arrived in the graph before test nodes), this can lead to distribution shift between the training and test set, necessitating the application of some sort of domain adaptation method. The paper proposes such a method, based on message passing, which attempts to ensure that the distribution of node features after message passing has certain time-invariant properties that the authors posit are reasonable for many real-world temporal graph datasets.

Reviewers had several concerns that would need to be addressed before the paper is ready for publication. Primary among them are:
1. The paper does not extensively compare again other domain adaptation methods in the graph ML literature. In the rebuttal the authors comment that this is because such methods do not scale to large graphs. But at least more discussion of existing approaches and justification for why they would not scale/apply would be needed.
2. The presentation of the paper and the mathematical rigor need significant improvement. The authors did provide a new version of the manuscript which is a step in the right direction.
3. Empirical comparisons should be better motivated/more consistent across datasets and should include more baselines when possible. Verification of invariance assumptions should go beyond citation networks.

Overall, the ideas in this paper have potential but need more work before being ready for publication.

As a minor point: the AC would like to point out that a 'Temporal Stochastic Block Model (TSBM)' has already been introduced in prior work (https://arxiv.org/abs/2210.00032). The authors should consider citing this work and potentially using a different name to distinguish their related but different model.