Temporal Generalization Estimation in Evolving Graphs

Thanks for your time and valuable comments that may help us for further improvement. We hope the following responses will serve to address your concerns.

Q1: Additional baselines and evaluation metrics.

R1: Thanks for your valuable suggestions. We have conducted additional two baselines (DoC and Supervised) with 4 classical evaluation metrics for regression task (MAPE, RMSE, MAE and Standard Error). The performance comparison is shown in Table 1 of the general response. Our SMART consistently outperforms both Linear and DoC, and closely approach the supervised methods. We provide more detailed information in Appendix H.3 in our revised paper. Regarding the methods discussed in related work in Appendix D.2, these methods focus on how to improve model performance on evolving graphs, instead of on how to characterize the model performance dynamics in graph evolution. Since the target is different, these methods therefore can not be used for estimating generalization dynamics.

Q2: Performance on latest GNN backbone.

R2: Thanks for your comment. To fully validate and compare the effectiveness of different methods, we add Graph Transformer backbone besides GCN, GAT and GraphSAGE. As shown in Table 5, first of all, our SMART shows consistent best performance among different architectures. For different graph neural network architectures, they tend to capture the structure and feature information from different aspects. Due to the simple model structure of GCN, our SMART shows advanced prediction performance among other architectures, which is also consistent with the theory of classical statistical machine learning.

Table 5. Performance comparison of different GNN architectures

Q3: Assumptions in theoretical analysis, including ever-growing and zero-mean normalized feature.

R3: Thanks for your valuable suggestions. We generalize these two assumptions in the following way. (1) Regarding the ever-growing assumption of graphs, we modify it to the setting where nodes appearing after deployment have a probability of disappearing (Assumption 3-3). (2) Regarding the zero-mean normalized feature, we modify it to the setting where the feature vector has a constant mean conditioned on all previous graph states (Assumption 3-4). The completed assumptions please refer to Assumption 3 in Appendix C.2. Based on this assumption, we further extend the unavoidable representation distortion theorem to Theorem 4, and the proof of Theorem 4 can be found in Appendix C.4 and C.5.

Q4: The connection between information loss and graph reconstruction.

Thanks for your comments. Please refer to the response to Q3 in general response.

Q5: The definition of function $I$ and the generalization error.

R5: Thanks for your advice. In our paper, $I$ denotes the mutual information. For two random variable $X$ and $Y$, the mutual information $I$ is denoted as follows:

$I(X ; Y)=\sum_{x \in X} \sum_{y \in Y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)}$

Generalization error refers to the performance of a trained model when making predictions on new, unseen data compared to the performance on the data it was trained on. In our work, the generalization error we estimate is the performance of the trained GNN model on the test samples during the graph evolution process. We have added the above definition to the revised paper, and we believe that this will be more helpful for readers to understand our work.

Thanks for appreciating our work and give very detailed reviews. We are greatly encouraged that you appreciated our contributions including novel and convincing methods, problem significance, clear writing and potential impact of our study. We hope the following response will serve to address your concern and improve your confidence.

Q1: Supplement to related work.

R1: Thanks for your comments. Please refer to the response to Q4 in general response.

Q2: Clarification of information loss by representation distortion and graph reconstruction.

R2: Thanks for your comments. Please refer to the response to Q3 in general response.

Q3: More data augmentation techniques in graphs.

R3: We have added three graph data augmentation methods to generate different views for self-supervised graph reconstruction in a contrastive manner, i.e., DropEdge [5], DropNode [6] and Feature Mask [7]. Table 3 shows the experimental results, and our SMART shows the best performance on three datasets. We observe that different data augmentation methods on performance have similar performance.

Table 3. Performance comparison with different graph data augmentation methods.

Q4: Extension of theoretical analysis for more complex GNN model.

R4: Thanks for your comments. As we mentioned in the general response, we generalize Theorem 1 to a more general class of multi-layer graph neural network architectures (i.e., Theorem 3). Specifically, we consider the model where a feedforward neural network of an arbitrary depth is concatenated with the graph convolution network. The detailed theoretical analysis please refer to Appendix C.1 and the proof can be found in Appendix C.3.

Q5: Explanation of Figure 3.

R5: Thanks for your comment. Y-axis indicates the prediction loss of GNN model on test datasets during graph evolution. It is also possible to use other performance indicators, while the loss on the test sample is just a simple and intuitive indicator.

Q6: The selection of time series models to capture the temporal variations.

R6: To capture the temporal dynamics of GNN generalization variation, we propose an RNN-based method (i.e. LSTM) and achieve satisfied estimation performance. In our paper, we used the vanilla LSTM model to demonstrate the importance of temporal encoding via time series models. We do agree that under a more complex scenario, advanced time series model may achieve better performance.

To further investigate this problem, we additionally replace the LSTM with other two time series model Bi-LSTM and TCN. As depicted in Table 4, our SMART achieves the best performance among three different time series models on both OGB-arXiv and Pharmabio datasets. On DBLP dataset, SMART achieves the best performance using LSTM, while SMART equipped with Bi-LSTM and TCN show comparable performance with DoC. In order to maintain consistency in the experiment, we adopted the same hyperparameter settings. From the perspective of parameter size, the parameter quantity of Bi-LSTM is nearly twice that of LSTM, while the parameter quantity of TCN is very small. We observe that as the parameter size increases, the prediction error generally decreases first and then increases. From these preliminary results, it is indeed important to choose appropriate models and parameter settings based on the complexity of the data.

Table 4. Performance comparison with different time series model.

Thanks for your time and constructive suggestions. We are pleased for your positive comments. In the response below, we provide answers to your questions in order to address the concerns and increase your confidence.

Q1: Model comparison with other baselines.

R1: Thank you very much for pointing out a relevant paper [1] in the field of computer vision. After in-depth reading, we adopt the DoC method proposed in this paper as a baseline for performance comparison. We present some additional experimental results in Q2 of the general response, where 4 evaluation metrics are shown in Table 1. We observe that in our experimental settings, SMART shows consistent better performance than DoC. This may be due to the reason that DoC method is optimized for the setting where the testing distribution slightly differs from training data. However, in our setting, graph evolution is very fast and the evolving graphs are usually very different from their initial states. We also provide more detailed discussion in Appendix H.3 in our revised paper.

[1] Devin Guillory, et al. "Predicting with Confidence on Unseen Distribution." ICCV, 2021.

Q2: The definition of beta and the consideration of homogeneity assumption of graphs in theoretical analysis.

R2: Thanks for your valuable advice. In our theoretical analysis, $\beta$ is the slope ratio for negative values instead of a flat slope in ReLU. We have added an explanation of $\beta$ in our revised paper. Regarding the homogeneity of graphs, we do not make any assumptions in both theoretical analysis and empirical study. Meanwhile, we conduct a data analysis of the changes of homogeneity ratio over time on all the datasets as shown in Figure 10 of Appendix G. We observe that different datasets exhibit diverse variations in the homogeneity ratio of graphs and that SMART consistently outperforms the other two self-supervised baselines in all cases.

Q3: Explanation of contrastive way in self-supervised graph reconstruction.

R3: Constrastive self-supervised learning is a popular and effective learning strategy to enrich the supervised signals. It can be divided into two stages: first is the graph augmentation and then is the contrastive pretext tasks. Therefore, a general learning objective of contrastive self-supervised learning approaches is denoted as follows:

$\theta^*, \varphi^* = \arg \min_{\theta, \varphi} \mathcal{L}(p_{\varphi}(f_{\theta}(\tilde{A}^{(1)}, \tilde{X}^{(1)}), f_{\theta}(\tilde{A}^{(2)}, \tilde{X}^{(2)})))$

where $\tilde{A}^{(1)}$ and $\tilde{A}^{(2)}$ are two augmented graph adjacency matrices, $\tilde{X}^{(1)}$ and $\tilde{X}^{(1)}$ are two node feature matrices under different augmentations. In our setting, We perform data augmentation (e.g., randomly dropout node, dropout edge, mask feature) on the graph data with a probability of 0.5, keeping it unchanged with a probability of 0.5. Afterwards, we define a pretext task is to minimize the distance of two augmented graphs via link prediction and node feature reconstruction. We note that our proposed SMART is actually a special setting in the general contrastive learning framework.

Thanks for your time and valuable comments. We are encouraged that you appreciated our technical contributions including problem significance, theoretical proof and well-written presentation. In the response below, we provide answers to your questions in order to address the concerns.

Q1: Extension of theoretical analysis to a more complex scenario.

R1: Thanks for your comments. As we mentioned in the general response, we generalize Theorem 1 to a more general class of multi-layer graph neural network architectures (i.e., Theorem 3). Specifically, we consider the model where a feedforward neural network of an arbitrary depth is concatenated with the graph convolution network. For the detailed theoretical analysis, please refer to Appendix C.1 and the proof can be found in Appendix C.3. We also generalize the assumption that allows missing nodes and non-zero feature bias in evolution.

Q2: More model comparisons, e.g. a supervised manner.

R2: Thanks for your suggestion. We have added a supervised baseline and compared it with our SMART. Please refer to Q2 in general response. We also provide more detailed information in Appendix H.3 in our revised paper. Overall, SMART achieves comparable performance on dataset OGB-arXiv, while achieving slightly worse performance on dataset Pharmabio, when compared to the supervised baseline.

Q3: Generalizability of SMART for label changes and concept drift.

R3: We agree with the reviewer that the graph topology $A$, feature vectors $X$ on all nodes and even labels $Y$ can change during the graph evolution. In other ways, the joint distribution $P(A,X,Y)$ can change during the graph process. Using the definition of the conditional probability, we must have $P(A,X,Y)=P(Y|A,X)P(A,X)$. This implies that the change of joint distribution $P(A,X,Y)$ can be due to the change of $P(Y|A,X)$,$P(A,X)$or both of them. In this paper, we aim at the problem where only $P(A,X)$changes and theoretically showed the inevitable representation distortion even without of change of $P(Y|A,X)$. We proposed the algorithm SMART mainly to address the case where only $P(A,X)$ and thus do not consider the setting where the label changes and concepts drift. But we do believe techniques focusing on the changing labels can be fused with our algorithm for handling the case where both distribution $P(Y|A,X)$ and $P(A,X)$ evolve.

Thank you for your positive and constructive comments. We are pleased that you acknowledged the novelty and significance of our focused problem, promising results and straightforward presentation. In the following response, we answer your comments/questions point by point.

Q1: More model comparisons to make the results more convincing.

R1: We have added two additional baselines, DoC and Supervised, and conducted performance comparison on 3 datasets. The experimental results are shown in the general response (Table 1), and we also provide more detailed experimental results (Table 9-10, Figure 12-16) in Appendix H.3 in our revised paper.

Q2: Clarify the meaning of Figure 1.

R2: Thanks for your valuable suggestion. Figure 1 depicts the changes of the graph scale and GCN classification performance nearly 30 years on Pharambio dataset. Therefore, the x axis is the range of year. Each node in the graph means a paper in an academic co-authorship graph.

Q3: The impact of information loss in graph representation on the generalization estimator.

Thanks for your comments. Please refer to the response to Q3 in general response.

Q4: More evaluation metrics for the synthetic datasets.

R4: We have added MAPE, RMSE and MAE on the synthetic datasets. The results are presented in following Table 2. The detailed analysis please refer to Appendix F. Since the DoC method only applies to classification problems using the average confidence, we thus do not compare it with our SMART on the synthetic setting.

Table 2. Performance comparison on different Barabási–Albert graph setting.

Q3. Further clarification of information loss by representation distortion and graph reconstruction.

We analyzed the representation distortion via the information loss and showed that the zero information loss implies zero reconstruction error. To see this, by data processing inequality, we have $I(X;Y)\ge I(\varphi(X);Y)$ for any function $\varphi$. By the property of mutual information, equality holds if and only if the function $\varphi$ is a bi-jective function. This further indicates that

$\min_{\phi}\mathbb{E}[\|X-\phi\circ\varphi(X)\|^2]=0.$ In our paper, the information loss induced by the representation distortion is

I({G(A_\tau,X_\tau)\}^k_{\tau = t_{deploy}+1},\mathcal{D};\ell_k) - I(\{\varphi \circ G(A_\tau,X_\tau)\}^k_{\tau=t_{deploy}+1},\mathcal{D};\ell_k) \ge 0.

To minimize the information loss, i.e., achieve equality, we have to choose an appropriate $\varphi$ such that $\varphi$ is a bijective map. By information theory, equality further indicates that

$\min_{\phi}\sum_{\tau}\mathbb{E}\|G(\tau, X_\tau)-\phi\circ\varphi\circ G(A_\tau, X_\tau) \|_2^2=0.$

This can be viewed as the setting where the minimum reconstruction error is zero. We have revised the paper to clarify the relationship between zero information loss and optimal reconstruction.

Q4. Supplement to related work.

R4. In Appendix E, we have discussed the related work about distribution shift estimation and evolving graph representation. In order to provide a clearer overview of the relevant work, we have added a brief summary in the introduction section of our revised paper.

Summary of the Paper Revisions

The main updates are summarized as follows:

1. Page 1, Sec. 1, add an overview of related works about distribution shift evalution.
2. Page 4, Sec. 2.3, add an extension of theoretical analysis about GNN representation distortion.
3. Page 5, Sec. 3.2, highlight the relationship between information loss and graph reconstruction.
4. Page 6, Sec 3.3, highlight the usage of graph reconstruction in pre-deployment phase.
5. Page 8, Sec 5.2, add more baseline comparison and experimental analysis.
6. Page 16-22, we add a new section Appendix C to present the detailed theorem and theoretical proof for extensions on Theorem 1.
7. Page 26, Appendix F, we add the complete experiment results on synthetic BA random graph datasets.
8. Page 27-32, we re-write Appendix H, which provides a detailed explanation of our experimental details and analysis, including baseline experiments, comparison of different GNN backbones, time series models, graph data augmentation methods, etc.