Wide & Deep Learning for Node Classification

Thank you very much for your review, suggestions, and questions. We have carefully addressed your concerns shown below.

Q1: Conducting a separate hyperparameter search under your method's framework would be a fairer comparison.

A1: Thanks for your suggestion. We re-optimized all hyperparameters, and the experimental results can be found in https://anonymous.4open.science/r/GCNIII_supplement.

Q2: The ablation study lacks experiments on LLMs. If your method incorporates LLMs as auxiliary tools, it would be beneficial to include similar methods in the baselines or enhance existing GNNs with LLMs.

A2: Your suggestion is very reasonable. We consider that the focus of this paper is not LLM, so the content related to LLM will be deleted.

Q3: Could you compare your method against more recent baselines?

A3: Thanks for your suggestion. We conducted comparative experiments between GCNIII and recent baseline methods, with results available at https://anonymous.4open.science/r/GCNIII_supplement.

Q4: Have you observed the same phenomenon on other datasets?

A4: The same phenomenon is more likely to occur on homophilic datasets.

Q5: In Appendix C, I recommend increasing the training ratio in the data split rather than relying solely on training accuracy, as evaluating only training accuracy is not practical in real-world scenarios.

A5: We consider this limit case in order to verify the node classification ability of the linear models rather than the generalization ability.

Q6: In Figure 6, there seems to be no significant improvement in the training error of GCNIII over GCNIII.

A6: We suspect your question stems from Figure 5, which illustrates a clear trend: as γ increases, the training error decreases significantly. Our goal is to strike a balance, as we also aim to prevent the model from overfitting.

Q7: What exactly is over-generalization? How does it impact performance? Specifically, does it degrade test accuracy? Why does over-generalization occur in GCNII?

A7: The over-generalization phenomenon shown in Figure 1 refers to the situation where training error remains significantly higher than validation error during model training. This phenomenon has currently only been observed when training deep GCNs. It does not lead to test accuracy degradation, but it means that the utilization efficiency of features in the model training process will be reduced, which is why linear models are introduced. We provide a detailed analysis of over-generalization phenomenon in GCNII in Section 4.

Q8: What is the final architecture of GCNIII? What are the key differences between GCNII and GCNIII? How do these differences address the over-generalization problem?

A8: The structure of GCNIII is shown in Figure 2. Compared with GCNII, GCNIII introduces a linear model and uses Intersect memory, Initial residual and Identity mapping as optional modules. GCNIII is a more flexible framework. We believe that the improved training error curve of GCNIII indicates a better balance between the model’s fitting ability and generalization, which successfully demonstrates that GCNIII can more effectively balance the trade-off between the over-fitting of GCN and the over-generalization of GCNII.

Q9: In the section on intersect memory, an adjacency matrix is applied before the feature transformation (Equation 12). Why not directly use a GCN layer for this purpose?

A9: Our proposed technique applies attention mechanisms to the output of a linear model, where graph convolution is not the only possible choice.

Q10: Does this mean the model architecture is dataset-dependent?

A10: Yes, details are in Appendix B.

Q11: you mention, "Equation (8) is not commonly seen in the design of GCNs, but it is indeed one of the key aspects of the GCNII model." However, dropout is widely used in GNNs—even the early GCN paper incorporates dropout.

A11: We mean that it is not common to use dropout in Feature Embedding prior to the GCN layers.

Q12: In Equation 2, the cross-product transformations ϕ(x) are included in the wide component. However, in GCNIII, this part is removed in Equation 7. What is the reasoning behind this change? If it is removed, why is this component still considered wide?

A12: Intersect memory creates a new 'wide' effect, where attention enables each node's output representation to incorporate information from more nodes.

Q13: Some descriptions of attention are unclear. For instance, in line 267, what does "both" refer to? Additionally, what is the 'attention' of GCNII?

A13: $\hat{G}$ and $\alpha(I_{n}-{(1-\alpha)\hat{G})}^{-1} (1)$. Initial residual causes the “attention” of GCNII to asymptotically approach (1) as the number of layers increases indefinitely.

Q14: In line 259, you state, "Graph Convolution G~\tilde{G} corresponds to the attention matrix on the left-hand side of Equation (13)." However, Equation 13 does not have a left-hand side.

A14: Sorry for the confusion. We meant the left side of the multiplication sign.

We thank you for your reviews and address your concerns as follows.

Q1: The authors claimed on page 5 that "The former is 0.0018, while the latter is 0.8423, which demonstrates that GCNII’s “attention” captures more information, leading to stronger generalization." However, it is not clear what is the connection between the "attention weights", "information", and "generalization".

A1: Thank you for your questions and suggestions, we will provide additional explanations. The attention matrix corresponds to $softmax(\frac{Q{K}^{T}}{\sqrt{{d}_{k}}})$. We formally define attention density as the proportion of non-zero elements in this matrix. Higher density indicates that a node's feature representation aggregates information from more other nodes, thereby capturing broader contextual information and enhancing generalization capacity (details in Appendix G).

Q2: On page 4, lines 198, the paper mentioned "The attention matrix between the nodes is the adjacency matrix" which is confusing.

A2: Sorry for the confusion caused by the inaccuracy of our description. The expression should be changed to 'The attention relationship between nodes can be obtained by the adjacency matrix'. If the self-attention mechanism is used for all nodes in the graph, the usual operation needs to learn the node characteristics to get the attention matrix, but the graph itself contains the relationship information among nodes. The neighbor of a node is the prior attention, so the neighbor matrix tells us which other nodes we should pay attention to for a certain node, which can be used as an attention matrix.

Q3: The baseline methods used in this paper are pretty old.

A3: Thank you very much for your suggestion. We conducted comparative experiments between GCNIII and recent baseline methods, with results available at https://anonymous.4open.science/r/GCNIII_supplement.

Q4: The proposed method incorporates LLM into the framework. Hence, for a fair comparison, many LLM-incorporated node classification methods should be compared, such as [1-2].

A4: Thank you for highlighting these key references. We declare at the beginning of Chapter 3 that embedding large language models (LLMs) into the framework for upgrading is only a technical idea, not the focus and main contribution of this paper. We focus on the analysis and improvement of GCNII. If it has an impact on the whole paper, we will consider deleting the part related to LLM.

Q5: The authors mentioned on page 5 that "We suggests that graph can be viewed as a form of static, discrete self-attention mechanism (Vaswani et al., 2017)." Actually, this is a well-known fact that "the attention matrix can be viewed as a fully-connected weighted graph", e.g., in papers [1-3].

A5: Thank you for pointing out this important reference, we have cited this paper. We think that treating the attention mechanism as a fully connected graph is not the same insight as using the graph as a static attention mechanism. A priori attention that does not need to be learned is an important reason for the over-generalization phenomenon in deep GCNs. Although the training stage has not yet ended, the accuracy of the verification set has far exceeded the accuracy of the training set.

Q6: I think the so-called "over-generalization" is interesting, but it may only be due to the dropout, so the models in training and validation are different.

A6: Thanks for your recognition, we believe that the overgeneralization phenomenon has a great impact on understanding and exploring the direction of deep GCNs, and further exploration is needed to fully understand its causes and mechanisms.

Q7: the difference between the proposed GCNIII and the existing model GCNII is that this paper has an extra module "Intersect memory", which is essentially an attention module (line 195).

A7: The most important thing in GCNIII is to introduce the linear model and conduct joint training. Intersect memory, Initial residual and Identity mapping are three kinds of techniques as optional hyper-parameters, but not necessary. Compared to the fixed-structure GCNII, the GCNIII framework is more flexible and can better adapt to different datasets.

Q8: Many notations are wrapped with {}. E.g., {$\psi$} is Eq. (7). It is unclear why they are presented like this.

A8: We state in lines 117-119 that {} represents non-essential module that need to be adjusted for different datasets and tasks. We found that these often overlooked components can have a big impact on how models perform on different datasets, so the GCNIII framework was designed to be more flexible.

Q9: I think the notation in Eq. (12) is problematic. The notation $\tilde{G}$ is a matrix (line 110), but it is also used as a function in Eq. (12).

A9: The notation $\tilde{G}$ is still a matrix in Eq. (12) rather than a function. $A_{IM}$ in Eq. (12) also represents a generalized attention matrix rather than a function.

Thanks a lot for your review, suggestions, and questions. We have carefully addressed your concerns shown below.

Q1: The proposed techniques demonstrate limited innovation in their conceptual design. Specifically, the intersect memory mechanism appears overly simplistic in its implementation. Furthermore, both the initial residual and identity mapping components show substantial similarity to existing methodologies, raising concerns about their novelty and originality.

A1: Thank you for your criticism and concern. Intersect memory is merely an optional technique (hyper-parameter) in our model, while our approach focuses on bringing linear models in and conducting joint training. Despite its apparent simplicity, this design proves remarkably effective in balancing the trade-off between over-fitting and over-generalization. The novelty of our work is primarily reflected in the following aspects: We revisit two highly influential works (with ~2000 citations) on deepening GCNs - APPNP and GCNII, where we are the first to identify the over-generalization phenomenon. We argue this phenomenon holds significant implications for understanding both deep GCNs and even the fundamental mechanism of graph convolution.The reason why GCNIII can alleviate the over-generalization phenomenon is due to the linear model's memory ability of node features during the training stage. Appendix E confirms that node characteristics are critical to the effectiveness of GCN in node classification tasks (often overlooked in previous studies), and Appendix C confirms that linear models also have strong node classification capabilities on these datasets. The analysis in sec.4 offers a novel interpretation of the deep GCNII model and provides insights that led to our proposal of GCNIII. The deep GCNII can be viewed as a chimera of multiple models, specifically 2-MLP, 1-GCN, 2-GCN, ..., k-GCN, where models closer to the output layer play a more significant role. Previous research on GNNs has never explored using the simplest linear model (2-MLP is considered in [1]). We argue that the most straightforward yet effective way to address GCNII’s limitations is to jointly train a linear model with GCNII. This approach is empirically validated by our experimental results (Figure 5 and 'Over-Generalization of GCNIII' in Section 6.2).

Q2: The semi-supervised node classification experiment demonstrates only marginal improvements over baseline methods. Furthermore, the ablation study yields mixed findings: while it confirms the necessity of the initial residual component, it paradoxically shows inconsistent performance when either the intersect memory or identity mapping components are removed, which contradicts the authors' original hypotheses.

A2: Thanks for your criticism and questions. GCNIII demonstrates consistent improvements over the baseline, with detailed experimental results provided in Appendix F. The model achieves peak accuracy of [86.1, 74.0, 81.4] on these three datasets respectively. The results obtained in the ablation experiment are not contradictory. As detailed in Section 3.2, the three techniques - Intersect Memory, Initial Residual, and Identity Mapping - serve as optional hyper-parameters in GCNIII that do not universally improve performance. Our analysis reveals these techniques are dataset-dependent, demonstrating GCNIII's enhanced flexibility over GCNII. Details of the use of these three techniques in all experiments are documented in Appendix B.

Q3: To achieve a more effective balance between over-fitting and over-generalization, have you conducted comparative experiments with state-of-the-art models specifically designed for heterogeneous datasets?

A3: Thank you for your questions and suggestions. The over-generalization phenomenon we identified is specific to deep GCN models (such as the classic work APPNP, GCNII, etc.), which are primarily designed for homophilic and heterophilic graphs. The heterogeneous graphs you mentioned (containing different types of nodes and edges) are outside the scope of this study. Notably, neither the literature we cited nor recent works discussed in Section 5 ('Other Related Work') have performed comparative experiments on heterogeneous graph benchmarks. As far as I know, homogenous graphs and heterogeneous graphs are two different research fields.

We thank you for your reviews and address your concerns as follows. 

Q1: There is lack of comparison between the training error and the validation error (like figure 1) for the proposed method, only training losses are reported in Figure 5 for three different models.

A1: Regarding Figure 5: To save space, we only plotted the training error comparison to demonstrate that our GCNIII model effectively mitigates over-generalization as the hyper-parameter λ increases, without suffering from over-fitting like shallow GCNs. The over-generalization phenomenon we found highlights a discrepancy between training and validation/test performance in deep GCNII, suggesting that the core issue lies in the training phase rather than the validation phase. We appreciate your suggestion and will include the complete comparison figures in the appendix to save space.

Q2: How the proposed model resolves this problem need to be fully justified with theoretical analysis/empirical results, besides the discussion in sec.4.

A2: The reason why GCNIII can alleviate the over-generalization phenomenon is due to the linear model's memory ability of node features during the training stage. Appendix E confirms that node characteristics are critical to the effectiveness of GCN in node classification tasks (often overlooked in previous studies), and Appendix C confirms that linear models also have strong node classification capabilities on these datasets. The analysis in sec.4 offers a novel interpretation of the deep GCNII model and provides insights that led to our proposal of GCNIII. The deep GCNII can be viewed as a chimera of multiple models, specifically 2-MLP, 1-GCN, 2-GCN, ..., k-GCN, where models closer to the output layer play a more significant role. Previous research on GNNs has never explored using the simplest linear model (2-MLP is considered in [1]). We argue that the most straightforward yet effective way to address GCNII’s limitations is to jointly train a linear model with GCNII. This approach is empirically validated by our experimental results (Figure 5 and 'Over-Generalization of GCNIII' in Section 6.2).

Q3: No results and explanation (if unavailable) about semi-supervised learning on heterophilic graph.

A3: As an improvement to GCNII, we used the same datasets of semi-supervised node classification as in the GCNII paper[2] for comparative experiments. The papers we cited, including some recent related studies mentioned in sec.5, also did not carry out semi-supervised learning on heterophilic graphs.

Q4: The limitations of the proposed method should be discussed.

A4: In our proposed method, the three techniques of Intersect memory, Initial residual and Identity mapping are regarded as hyper-parameters, which need to be selected according to the dataset, and the selection of hyperparameter γ should also be very careful when balancing over-fitting and over-generalization.

Q5: It is claimed in the last lines of left column, page 2, that wide & deep can more effectively balance the trade-off between over-fitting and over-generalization, which lacks of justification.

A5: In our original paper, we said 'a Wide & Deep architecture model as shown in Figure 2', meaning GCNIII. Specific evidence for balanced trade-offs can be seen in 'Over-Generalization of GCNIII' in Section 6.2 and [Q2-A2].

Q6: why GCNIII achieves marginal improvements compared to GCNII on homophilic graphs for both semi-supervised and full-supervised tasks? is the superiority of GCNIII on heterophilic graphs attributed to the wide component, since this component is less relevant to the graph structure (which is semantically inconsistent with node attributes)? Does intersect memory participate in this senario?

A6: GCNII remains a highly competitive model. While only marginal gains are observed on homophilic graphs, our method achieves significant improvements on heterophilic graphs. This stems from its more principled structural design, demonstrating GCNIII's superiority over GCNII in heterophily scenarios. Details about the use of intersect memory can be found in Appendix B.

Q7: In the 'attention is all your need' part, they calculate the attention density values for both on Cora with $\alpha$ be 0.1, ? I guess something missing here.

A7: Sorry, we don't fully understand your question. In our study, attention density value is defined as the proportion of non-zero elements in the attention matrix.

Q8: In Table 5, does the ablation study on the wide component use intersect memory?

A8: Sorry for the confusion caused by our unclear expression. In the original paper, the term 'a basic linear classification model' refers to a linear model that does not include intersect memory.

[1]Yang, C., Wu, Q., Wang, J., and Yan, J. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. In ICLR, 2023.

[2]Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In ICML, 2020.