Genetic-evolutionary Graph Nerual Networks: A Paradigm for Improved Graph Representation Learning

1. I recommend that the authors include a review of existing literature in the introduction to highlight the contribution of this study and its distinctions from previous work.

Response: Thank you for the comment. We have added a brief comparison of our work with previous work in the introduction section as follows. "Unlike previous methods, such as residual connections (He et al., 2016), SSFG (Zhang et al., 2022) and PariNorm (Zhao & Akoglu, 2020), this work proposes operations by drawing inspiration from genetic algorithms for addressing the over-smoothing problem in graph neural network. Our framework has good interpretablilty as it views the layerwisely node embedding process as analogous to the genetic evolutionary process."

2. The over-smoothing problem can be mitigated through graph structure learning, residual connections, and similar techniques. I suggest that the authors add baseline experiments with these approaches.

Response: Thanks a lot for the suggestion. The baseline models of GPS/Finetuned GPS, GCN, SSFG, GatedGCN already used the techniques, such as residual connections, batch normalizations and structural encoding. Otherwise the model performance would be more significantly reduced. We have further compared our method with the basic GCN in which residual connections and batch normalizations (BN) are not used on MNIST and CIFAR10. The results have been added in Table 5 in our revised manuscript. It can be seen from Table 5 that the model performance drops without using these techniques and that the joint use of our method with residual connections and batch normalizations yields the best task performance.

3. The Related Work section have not evolutionary-based GNNs, but there has been considerable research in this area, like literature [1,2]. I recommend including a discussion of these relevant studies.

Response: We have included the relevant studies in the Related Work section. The two studies both use the evolutionary method to search and optimize graph neural network models and hyperparameters. Unlike these studies, we use the genetic-evolutionary strategy to maintain embedding diversity for addressing the oversmoothing problem in the node embedding generation process. It is a general method that can be applied in different graph nerual network models.

4. I suggest that the authors use a more general pseudocode format (e.g., a higher-level process description) instead of framework-specific syntax to better adhere to pseudocode standards—focusing on the logical flow rather than the framework implementation. This will enhance the paper’s accessibility and allow readers without a specific framework background to more easily understand the algorithm’s principles.

Response: Thank you. We have added a more general pseudocode for the operations of crossover and mutation in the appendix section (see Algorithm 3 and Algorithm 4).

5. To improve the transparency and reproducibility of this research, I recommend that the authors consider open-sourcing their code to promote academic exchange and development in this field.

Response: We have added the code of the crossover and mutation functions in Pytorch to the appendix section. The full project code will be made publicly available if this work could be accepted for publication.

6. The Crossover and Mutation operations in this paper are not sufficiently innovative.

Response: Thank you for the comment. We would like to clarify that, to the best of our knowledge, this is the first work of integrating the genetic-evolutionary strategy into graph neural network for node embedding generation. The use of the two operations inspired by genetic algorithms prevents the generated embeddings from becoming too similar to one another when more graph network layers are used.
The proposed framework helps to alleviate over-smoothing, a common issue in most current graph neural network models. The results show that our method achieves performance improvements on strong baseline models on different datasets.

1. This paper does not fully clarify the concept of Genetic-Evolutionary. For example, to my understanding, the process of evolution/genetic should also include Evaluation (to evaluate the quality or potential of each offspring based on certain strategies) and Selection (to choose offspring based on their fitness or performance). Without these components, the process seems incomplete.

Response: Thank you very much for the comments. We are sorry for the confusion. We would like to clarify that this paper is not simply a combination of genetic/evolutionary algorithms and graph neural networks. This paper draws inspiration from genetic algorithms and views the node embedding generation process as a genetic-evolutionary process, wherein each of the graph neural network layers produces a new generation of embeddings.

To prevent the embeddings become very similar to one another, we introduce operations inspired by crossover and mutation to maintain the embedding diversity. The crossover and mutation operation introduced in this paper can be integrated into current graph neural network models (the Pytorch implementations of the key operations are included in the appendix section). Otherwise if node embeddings become very identical to each other, the original input node attributes or features become lost, and the model performance can be significantly reduced.

To summarize, this paper proposes operations, i.e., crossover and mutation, by drawing inspiration from genetic algorithms, and it is not a simply use of genetic algorithms for node embedding generation. The proposed operations are used to maintain or increase the diversity of generated embeddings. We don's use selection or evaluation of selected embeddings. The selection and evaluation strategies are commonly used for search purposes. These strategies are not used in our embedding generation problem.

2. The Crossover operation is a random selection process rather than an iterative optimization process. Therefore, is it reasonable to interpret the proposed model’s optimal performance as a result of coincidental randomness? Additionally, I suggest the authors include a clearly defined objective function.

Response: Thank you for the comment. The Crossover operation is a random selection process, and the Mutation operation also increases randomness. The two operations help prevent node embeddings from becoming similar to one another. However, it is not simply a results of coincidental randomness. We evaluated the method of Dropout on MNIST and CIFAR10 and found that the use of Dropout achieved nearly the same performance compared to without using Dropout. The results are consistent with the work of Dwivedi et al. (2020), wherein the rate for Dropout is set to in the base models, including GCN, GAT and GatedGCN. Also, from Figure 5 in the appendix section, it can be seen that the model performance improves as the number of graph neural network layers increases from 4 to 12 with out method. Whereas without using our method, the performance drops as the layer number increase, a common phenomenon as a result of over-smoothing .

3. It appears that the authors are avoiding discussing Evolutionary-based GNNs. There are already numerous similar GNN papers published in this area. Why did the authors not cite any of them?

Response: We apologize for uploading not the latest revised version. We thought we uploaded the version that has discussions about the two related studies you kindly suggested. We have only now found out that we didn't uploaded the latest version. If we could be given the chance, we will upload the version with discussing about evolutionary studies inducing the two you kindly recommended in graph neural networks.

The work of Shi et al. (2022) uses the evolutionary approach for search graph neural network architectures as well as hyperparameters. The work of Liu et al. (2023) adopts the evolutionary approach for optimizing graph structures, enabling the graph neural network model can better defend againast adversarial attacks.

[1] Shi, Min, et al. "Genetic-gnn: Evolutionary architecture search for graph neural networks." Knowledge-based systems 247 (2022): 108752.

[2] Liu, Zhaowei, et al. "EGNN: Graph structure learning based on evolutionary computation helps more in graph neural networks." Applied Soft Computing 135 (2023): 110040.

4. To my knowledge, one natural advantage of introducing Evolutionary Algorithms into GNNs is to provide diversity for node embeddings. However, the contribution of this work seems to merely reintroduce Evolutionary/Genetic approaches into GNNs to address overfitting caused by multi-layer architectures. This method lacks originality and depth, and I do not believe it meets the standards of a top-tier conference like ICLR. The authors might consider submitting this work to a lower-tier conference or journal.

Response: Thank you for the comment. However, we don't agree. Firstly, our method does not simply address the overfitting problem. In the right of Figure 4, it can be seen that our method improves both the training performance and test performance. It improves the overall graph representation learning performance, which is not only by addressing overfitting. As mentioned in our responses to your question 2, we evaluated the method of Dropout on MNIST and CIFAR10 and found that the use of Dropout achieved nearly the same performance compared to without using Dropout. The use of the Dropout regularization method does not improve the model performance. Wheras our method can effectively improve the performance on different datasets. It can address overfitting and underfitting for different tasks (see Figure 4 and Figure 5).

5. I recommend the authors conduct a thorough review of the latest literature. It is evident that this is not the first work integrating the Genetic-Evolutionary strategy into Graph Neural Networks for node embedding generation.

Response: Thank you for the comment, and we apologize again for uploading not latest version. The work of Shi et al. (2022) uses the evolutionary approach for search graph neural network architectures as well as hyperparameters. The work of Liu et al. (2023) adopts the evolutionary approach for optimizing graph structures, enabling the graph neural network model can better defend againast adversarial attacks. In object detection, evolutionary approach was also used for optimizing hyperparameters in latest YOLO models (Redmon, 2016). Unlike these studies, which primary use genetic evolution as an approach to search for the graph structures, or graph neural network architectures or hyperparameters. This paper draws inspiration from genetic algorithms and views the node embedding generation process as a genetic-evolutionary process, wherein each of the graph neural network layers produces a new generation of embeddings. We introduce key operations, i.e., crossover and mutation, inspired by evolutionary algorithms to maintain the embedding diversity, which prevents embedding from becoming similar to one another, a common issue in graph neural networks.

[1] Shi, Min, et al. "Genetic-gnn: Evolutionary architecture search for graph neural networks." Knowledge-based systems 247 (2022): 108752.

[2] Liu, Zhaowei, et al. "EGNN: Graph structure learning based on evolutionary computation helps more in graph neural networks." Applied Soft Computing 135 (2023): 110040.

[3] Redmon, Joseph, et al. "You only look once: Unified, real-time object detection." In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016

1. The evaluation could be more balanced. GPS is a strong GNN model, and the authors should demonstrate that the proposed framework performs well with other GNN architectures, such as applying genetic algorithms with GCN.

Response: We have experimented of our method on GCN on MNIST, CIFAR10 and PascalVOC-SP. The results have been added in Table 1 and Table 2 in the revised version. We have also experimented of our method on GCN with different layers CIFAR10. The results are reported in Figure 5 in the appendix section. It can be seen from Figure 5 that our method effectively improves the generalization performance compared to the base model.

2. The authors could consider adding more detailed descriptions of how the evolutionary operators function within the proposed framework. From my understanding, this framework operates similarly to other GNNs optimized by backpropagation, while evolutionary algorithms (EAs) traditionally do not rely on backpropagation. In this context, the evolutionary operators seem to act more like activation functions or non-parametric layers, primarily generating diverse outputs that are subsequently optimized through backpropagation. Clarifying this distinction would help readers better understand the role and novelty of these operators within the framework.

Response: Thank you. The operations of crossover and mutation, which are inspired by genetic algorithms, apply on node embeddings. The crossover operation can be implemented using Algorithm 1. For the mutation operation, it can be implemented using the reparameterization technique. Therefore, the two kinds operations can be integrated into current graph neural networks, and the model can be optimized using backkpropagation.

We have added the implementation of the two operation in Pytorch in Figure 6 and Figure 7 in the appendix section. Hopefully, the codes could be helpful for reproducing the results and for our framework to be better understood.

3. If I missed any details, please correct me. There are two types of crossover operators—why didn’t the authors consistently apply both across all datasets?

Response: Thank you. The cross-generation crossover operation and mutation operation are parameter-free methods and do not introduce additional trainable model parameters.
The results in Table 1 and Table 2 are obtained by applying the two operations on base GPS mode. We think it is a good way to the performance improvements that are made by using our method. For results in Table 3, we found that the use of cross-generation could only yiled marginally improved performance. Therefore we chose to use sibling crossover and mutation, the use of sibling crossover increases model parameters because multi-head output need to be generated. We appreciate your suggestion, and we understand that the joint use of the two crossover operations could potentially improve the overall performance. Due to the limitation of time, we have not obtained the results. However, we will be continuing working on this.

4. The ablation study is not convincing.

Response: We have further conducted experiments to analysis the performance of our method on the base Finetuned GPS model with different layers on CIFAR10 and PascalVOC-SP. The results have been added in Figure 4 in the revised version. We have also analyzed the the performance of our method on the base Finetuned GPS model with different layers on CIFAR10. The results have been added in Figure 5 in the appendix section. It can be seen from Figure 4 and Figure 5 that the use of our method improves the model generalization performance on the base models

5. How many repeated experiments did you run, considering that crossover and mutation introduce randomness? Are all results statistically significantly different?

Response: We followed the experimental setup of GPS (Rampasek et al., 2022), 10 runs of experiments are conducted for and the mean and standard deviation are reported as the model performance. Although our method introduces randomness, we can see from the experimental results that our method yields a lower standard deviation value compared to the base models. This suggests that our method improves the stability of optimization.

1. For evolutionary theory to work, it relies on randomness and scale i.e. over large number of iterations, small changes produce variety and adaptable traits. How many iterations can GNN be applied for a reasonable analogy to the theoretical foundations of evolutionary theory is unclear.

Response: Thank for the time reviewing our paper. We would like to clarify that this work proposes operations by drawing inspiration from genetic algorithms for addressing the over-smoothing problem, a common issue in most graph neural networks. The key operations, i.e, crossover and mutation, can be integrated into current graph neural networks, and the model can be optimized using backkpropagation. The number of iterations is the same as that used for optimizing the graph neural network model with backpropagation.

2. The authors say - This makes it interpretable and easy for understanding. It is not clear how does this make it more interpretable, when it is making more random and introducing distinctness, even in cases when there is no need based on features or structure.

Response: Thank you for the comment. We would like to clarify that this paper proposes operations by drawing inspiration from genetic algorithms for addressing the over-smoothing problem in graph neural network. Our framework has good interpretablilty as it views the layerwisely node embedding process as analogous to the genetic evolutionary process. The introduced operations,i.e, crossover and mutation, helps prevent the generated embeddings from becoming too similar to one another when more graph network layers are used.

3. After Crossover operation and mutation, evolutionary pressures which select the fit traits and the rest are discarded i.e. fail to reproduce enough. However, I do not see how these selection is happening in the GNN framework. If there is no selection, then it means all crossover and mutations are good, which is contrary to evolutionary theory.

Response: We would like to clarify that the use of the two operations, i.e., crossover and mutation, inspired by genetic algorithms prevents the generated embeddings from becoming too similar to one another when more graph network layers are used. The proposed framework helps to alleviate over-smoothing, a common issue in most current graph neural network models. Our framework does not use the selection mechanism. Our framework is not simply a combination of genetic algorithms with graph neural networks.

4. Typos: Line 125, 134, 208,

Response: Thank you, the typose have been fixed.

1. "It is important to preserve the diversity of generated embeddings throughout their layerwisely generation process." It is true that a GNN with good performance needs some extent of diversity in the node embedding. However, is it also true that diverse embedding will definitely lead to good performance? In other words, is diverse embedding a sufficient condition for good GNN performance?

Response: Thank you for the comment. The issue of over-smoothing is a common issue in graph neural networks. The embeddings of nodes tend to become very similar to one another after repeatedly apply graph convolutions due to the over-smoothing problem. The consequence is that the original input node attributes or features become lost, and the model performance can be significantly reduced. In this paper, by "preserving the diversity of generated embeddings", the model basically prevents the node embeddings becoming too similar to one another, which prevents the issue of the input node attributes or features being washed out.

From another perspective, we view the layerwisely embedding generation process as an evolutionary process. The methods of crossover and mutation are introduced to generate diversed embeddings (or populations) than very homogeneous ones. Homogeneous populations are regarded as a major issue for premature converging to suboptimal solutions (Whitley, 2001) in genetic algorithms. By preserving the diversity of embeddings, the model can be prevented from premature converging to local minima.

2. Equation (2) and (3) look like random pooling operations. Is there any relation?

Response: In the model training stage, the feature at each position is randomly selected from one of the input vectors (in Equations (2) and (3)). This operation is essentially the same as the randomly pooling operation. The difference is that, in the model inference stage, we use a deterministic output, which is computed based on the sampling factor (see Algorithm 1).

3. How many layers does the model have in your experiments?

Response: Finetuned GPS model. The number of layers is 6 and 8 on MNIST and CIFAR10 respectively, and the number of layers is set to 8 on PascalVOC-SP and COCO-SP. In Table 3, our results on Finetuned GCN also uses the same of number of layers (6 layers) as the base Finetuned GCN model.

4. How does your model performance changes as the layer goes to deep? Need ablation study for different operations in your model.

Response: We have further conducted experiments to analysis the performance of our method on the base Finetuned GPS model with different layers on CIFAR10 and PascalVOC-SP. The results have been added in Figure 4 in the revised version. We have also analyzed the the performance of our method on the base Finetuned GPS model with different layers on CIFAR10. The results have been added in Figure 5 in the appendix section. It can be seen from Figure 4 and Figure 5 that the use of our method improves the model generalization performance of the base models.

5. How does your model work on node classification problem, especially on heterophilic graphs[1]?

Response: We would like to clarify that Table 2 already showed the results on node classification on PascalVOC-SP and COCO-SP. The two datasets contain superpixel graphs, and the task is to predict if a node corresponds to a region of an image which belongs to a particular class. We used the same model hyper-parameters as the base Fine-tuned GPS model and achieved improved performance compared with the base model on the node classification task on the two datasets.

Additionally, we have discussed the work of Luan et al. (2024) about the impact of graph homophily on learning using graph neural networks.