MultiNet: Adaptive Multi-Viewed Subgraph Convolutional Networks for Graph Classification

Dear Reviewer 7WyT,

We sincerely thank you for your careful reading of our paper and for the valuable questions and suggestions. Below, we provide detailed responses to each of your comments. We have made every effort to clarify our contributions and address your concerns with additional explanations, experiments, or theoretical analysis where appropriate.

We hope that our responses can resolve your concerns and better convey the significance of our work. We would greatly appreciate any additional feedback you may have.

Response to Q1: Thanks for the suggestion. Although Eq. (4) and Eq. (8) appear similar in form, they serve entirely different purposes and carry distinct semantic meanings within our model. The attention matrix P in Eq. (4) is used during the multi-view division stage, where the nodes of the original graph are assigned to m subgraph views based on their attention scores. This process enables diverse local substructure modeling and emphasizes the relative importance of nodes across different perspectives. In contrast, the matrix S in Eq. (8) is introduced at the final representation generation stage as an alignment-based aggregation matrix. It maps the final node embeddings into s globally shared clusters to facilitate structural alignment and produce the graph-level representation. These two matrices correspond to two distinct phases in our architecture. While they may share a similar mathematical form, their usage and semantic roles are fundamentally different. We will clarify this distinction further in the revised version.

Response to Q2: Thanks for the suggestion. Although the node-level and graph-level over-smoothing are closely related, they differ in their focus. The node-level over-smoothing occurs within a single graph, where repeated graph convolutions lead to overly similar node representations, ultimately degrading the ability to distinguish nodes for node classification tasks. In contrast, the graph-level over-smoothing refers to the phenomenon where the graph-level representations of different graphs become excessively similar after the readout stage, making it difficult for the model to distinguish between graphs and thus harming performance in graph classification. In our work, we have explicitly distinguished these two types of over-smoothing in Section 2, provided a formal definition and theoretical analysis of graph-level over-smoothing in Section 2.2, and offered an illustrative example in Figure 3. We will further enhance the discussion in the revised version.

Response to Q3: Thanks for the suggestion. We will thoroughly review the entire manuscript to correct any grammatical errors and typographical mistakes.

Response to Q4: Thanks for the suggestion. We have clearly indicated the source of the experimental results in Section 5.2. For the baseline deep learning methods, we follow the fair comparison protocol provided in [1], which does not report results on the MUTAG and PTC_MR datasets. Accordingly, we did not include these baselines on the two datasets in our initial submission. To address your concern, we have reproduced the results for these models using the official code from [1]. As shown in the table below, our proposed MultiNet still achieves superior performance on both datasets, further demonstrating its effectiveness and robustness. We will update the manuscript to incorporate additional results and relevant discussions.

[1] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In Proceedings of ICLR, 2020.

Dear Reviewer xLjw,

We sincerely thank you for your careful reading of our paper and for the valuable questions and suggestions. Below, we provide detailed responses to each of your comments. We have made every effort to clarify our contributions and address your concerns with additional explanations, experiments, or theoretical analysis where appropriate.

We hope that our responses can resolve your concerns and better convey the significance of our work. We would greatly appreciate any additional feedback you may have.

Response to W1: Thanks for the suggestion. Although over-smoothing was originally identified in the context of node classification, we argue that it also has a significant impact on graph classification. When stacking multiple graph convolution layers, node features across structurally different regions may become overly similar, thereby diminishing the ability to preserve and distinguish informative local substructures. This issue is further exacerbated by the simple permutation-invariant global readout functions (e.g., sum or mean), which can obscure the structural differences among graphs and reduce the discriminative power of graph-level representations. To address this, we provide a formal definition of graph-level over-smoothing in Section 2.2, along with a theoretical analysis of its causes and implications. In addition, Figure 3 offers an illustrative example showing how over-smoothing degrades the distinctiveness of graph representations in classification tasks. We will strengthen this theoretical discussion further in the revised version.

Response to W2: Thanks for the suggestion. Traditional pooling operations such as sum, mean, or max are indeed widely used due to their simplicity, but they tend to overlook the local structural and the feature differences among nodes. In contrast, our alignment-based readout learns a cluster assignment matrix that aligns the order of node clusters and preserves the local topology across graphs, enabling the use of a more expressive MLP mapping. This enhances the ability to capture discriminative subgraph structures. We have highlighted these advantages in Section 3.4 and Section 4, and further validated the effectiveness of the alignment readout by replacing it with average and sum readouts in the ablation studies presented in Section 5.4. We will improve the explanation of this design choice in the revised version.

Response to W3: Thanks for the suggestion. We have clearly indicated the source of the experimental results in Section 5.2. To ensure a fair comparison, we report the results from the fair comparison [1] for the baseline deep learning methods. For other models, we adapt their best results from their original papers. Since the referenced literature lacked comparative analyses on these specific datasets, we did not initially include their experimental results. Following the experimental protocol established in [1], we have preliminarily supplemented the performance evaluation of baseline deep learning methods on both MUTAG and PTC_MR datasets. As shown in the table below, our proposed MultiNet still achieves superior performance on both datasets, further demonstrating its effectiveness and robustness. We will update the manuscript to incorporate additional results and relevant discussions.

[1] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In Proceedings of ICLR, 2020.

Response to W4: Thank you for the suggestion. Most existing literature has primarily focused on the node-level over-smoothing, and there is a notable scarcity of studies addressing the over-smoothing problem at the graph level. In our paper, we take a step forward by providing a strict definition of the graph-level over-smoothing for the first time in Section 2.2. Furthermore, in Section 5.3, we introduce a scientific metric to measure the graph-level over-smoothing and validate it through experiments. Although the work in [2] proposes a strategy to mitigate over-smoothing and applies it for graph classification tasks, it still focuses on alleviating over-smoothing at the node level and lacks the experiments addressing over-smoothing at the graph level. Thus, our work fills this gap and offers a more comprehensive analysis. We will provide additional explanations in the revised version to enhance our contribution.

[2] Stevan Stanovica, Benoit Gaüzère, and Luc Brun. Graph Neural Networks with maximal independent set-based pooling: Mitigating over-smoothing and over-squashing. Pattern Recognit. Lett., 187, 14–20, 2025.

Dear Reviewer XtUo,

We sincerely thank you for your careful reading of our paper and for the valuable questions and suggestions. Below, we provide detailed responses to each of your comments. We have made every effort to clarify our contributions and address your concerns with additional explanations, experiments, or theoretical analysis where appropriate.

We hope that our responses can resolve your concerns and better convey the significance of our work. We would greatly appreciate any additional feedback you may have.

Response to weakness and limitations: Thanks for the suggestion. In our design, we adopt a soft attention mechanism instead of the hard assignment to ensure differentiability and stable gradient backpropagation. The adaptive node attention allows the model to emphasize important nodes in each subgraph view, guiding it to focus on more discriminative local regions in terms of structure. While some information may still flow between the low-attention nodes, such propagation is effectively suppressed by the attention weights, which significantly limits its influence. This constrained message propagation mechanism mitigates the global feature homogenization and thereby alleviates the graph-level over-smoothing issue. We will further refine our theoretical analysis in section 4 to clearly explain how our method suppresses over-smoothing while preserving the flexible information propagation, as well as discussing the potential information flow among the low-attention nodes.

Response to Q1: Thanks for the suggestion. The notation $P^(j)$ should be written as $P_j$, which denotes the attention vector for the j-th subgraph view. We will correct this notation in the final version.

Response to Q2: Thanks for the suggestion. We have clearly indicated the source of the experimental results in Section 5.2. For the baseline deep learning methods, we follow the fair comparison protocol provided in [1], which does not report results on the MUTAG and PTC_MR datasets. Accordingly, we did not include these baselines on the two datasets in our initial submission. To address your concern, we have preliminarily reproduced the results for these models using the official code from [1]. As shown in the table below, our proposed MultiNet still achieves superior performance on both datasets, further demonstrating its effectiveness and robustness. We will update the manuscript to incorporate additional results and relevant discussions.

[1] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In Proceedings of ICLR, 2020.

Thanks for the response. I decide to keep the score unchanged.

Dear Reviewer YyPC,

We sincerely thank you for your careful reading of our paper and for the valuable questions and suggestions. Below, we provide detailed responses to each of your comments. We have made every effort to clarify our contributions and address your concerns with additional explanations, experiments, or theoretical analysis where appropriate.

We hope that our responses can resolve your concerns and better convey the significance of our work. We would greatly appreciate any additional feedback you may have.

Response to Q1: Thanks for the suggestion. We argue that our focus is not on permutation-invariant readout functions causing graph-level over-smoothing, but rather on how overly simplistic global readout functions (e.g., sum or average pooling) can exacerbate the graph-level over-smoothing when the node representations become homogeneous. Specifically, graph classification tasks inherently require the permutation-invariant readouts to ensure the output consistency regardless of the node ordering. However, most traditional GNNs often rely on the overly simplified global pooling schemes that treat all nodes as equally important. This approach ignores both the local node features and the topological structures. When combined with the node-level over-smoothing, it results in indistinguishable graph representations and severely degrades the discriminative power of the model. To support this claim, we have provided a formal mathematical proof in Theorem 1 (Section 2.2), which shows how the simple readout functions can lead to the graph-level representation convergence under the node feature homogenization. In addition, we offer an illustrative example in Figure 3 (left) and empirical evidence in Section 5.4 through the ablation studies comparing alignment readout with the traditional avg/sum pooling. We will revise the relevant discussion in the final version to ensure clarity and rigor.

Response to Q2: Thanks for the suggestion. We agree that the permutation invariance is a necessary property for the readout functions in graph classification, as the predicted graph labels should not depend on the node ordering. However, we argue that the issue lies not in the permutation invariance itself, but in the simplicity of the traditional permutation-invariant global readout functions, such as sum or average pooling, which treat all nodes equally. The root reason of this issue lies in the disorder of nodes within the graph. To address this, we aim to establish a reliable ordered correspondence for node clusters, which leads us to introduce an alignment-based readout mechanism. Specifically, we learn a cluster assignment matrix S using a shared function across all graphs, which ensures that clusters are aligned in a consistent order across different samples. This aligned structure allows us to apply a non-symmetric MLP at the cluster level, assigning different importance weights to different clusters. This mechanism preserves permutation invariance at the graph level, while avoiding the uniform treatment of nodes, thereby improving the discriminative power of the graph representation and effectively mitigating the graph-level over-smoothing. For this issue, we have clearly explained our motivation in the Introduction and provided a theoretical explanation in Section 4. We will further elaborate on this mechanism in the revised version.

Response to Q3: Thanks for the suggestion. Our goal is to enhance the discriminative power of graph representations by alleviating the graph-level over-smoothing, rather than relying solely on the deeper propagation for performance gains. As shown in Table 1 and Figure 4, our model already outperforms other baselines under shallow configurations (e.g., L=2~4), demonstrating that the proposed subgraph convolution and the alignment-based readout are inherently effective without requiring deeper networks. Furthermore, the trends in Figure 4 indicate that our model degrades much more slowly as the number of layers increases, effectively alleviating the performance deterioration typically observed in deeper GCNs. Notably, in some datasets, deeper versions (e.g., L=16 or L=32) even outperform shallower ones. This shows that our method not only improves the stability in deeper architectures but also retains the potential to benefit from deeper propagation. Therefore, we believe our model is practically valuable, as it adapts well to both shallow and deep settings, offering robust and competitive graph-level representations. We will follow your suggestion and revise the relevant sections to enhance clarity.

Response to Q4: Thanks for the suggestion. In Figure 4, we conduct a systematic comparison across different network depths. The results show that our method consistently achieves higher classification accuracy than other models under both shallow and deep settings. Notably, under deeper configurations (e.g., L=16 or L=32), our MultiNet achieves competitive or even superior classification accuracy compared to its shallower variants on certain datasets, which further demonstrates its ability to mitigate over-smoothing while preserving the advantages of deeper propagation. We will follow your suggestion and revise the relevant sections to enhance clarity.

Response to Q5: Thanks for the suggestion. In Table 1 of our paper, we have included over eighteen representative and state-of-the-art graph classification models, such as p-RWNN (2020), GKNN-WL (2024), GKNN-GL (2024), and QBMK (2024), covering both recent graph neural networks and graph kernel approaches. The results demonstrate that our proposed MultiNet consistently achieves superior classification accuracy across various datasets. Furthermore, Section 5.2 provides a comparative analysis of graph-level representation effectiveness, while the ablation studies in Section 5.4 confirm that each component of our model plays a crucial role in enhancing representation quality. We appreciate the suggestion and will include additional comparisons with more recent methods in the revised version to further strengthen the empirical validation.

Response to Q6: Thanks for the suggestion. Our method is fundamentally different from the traditional matrix factorization in both its motivation and computational process. First, the core objective of our alignment-based readout is to establish the consistent cluster-level correspondences across graphs, thereby overcoming the limitations of the conventional global readout functions in preserving structural information. This design enhances the expressiveness of the graph-level representations by explicitly retaining the local features and structural distinctions, rather than merely compressing node embeddings. Therefore, the process cannot be simply interpreted as the feature compression or the low-rank approximation. Second, in terms of the computational mechanism, the node-to-cluster assignment matrix is adaptively learned in an end-to-end fashion based on both the graph structure and node features. This assignment is not a static matrix nor derived from a predefined decomposition objective. Consequently, we consider our design conceptually distinct from classical matrix factorization techniques. We have already discussed and justified this design choice in the Introduction and further elaborated it in Section 3.4. We will include a more detailed discussion of this distinction in the revised version to improve theoretical clarity.

I would like to thank the authors for the response. This rebuttal partially resolved my concerns. Despite my consistent questioning about the permutation-invariant aggregation, I would like to raise my score due to the reviews given by the other reviewers. I will also not be against the acceptance of this paper.