Subgraph-To-Node Translation for Efficient Representation Learning of Subgraphs

Thank you for your review and constructive feedback. We address your comment on the lack of backbone architectures in the general response. Here, we provide answers to your individual questions below.

​​Lack of Novelty

The graph coarsening process lacks novelty. It is quite straightforward and well-known to treat the subgraphs into a single node and link the nodes that share the nodes in the original graphs.

We argue that the value of simplicity and the improved performance and efficiency over existing methods reinforce the genuine novelty of our contributions. We would like to offer the following points to counter the critique.

• Value of Simplicity: The simplicity of our proposed approach is one of its key strengths and contributions. By distilling the problem to its core and focusing on a simple yet effective idea, we can provide an efficient and effective solution for subgraph-level tasks.
• Novel Perspective and Fundamental Question: We emphasize that it is not well-known to treat the subgraphs into a single node and link the nodes that share the nodes for subgraph representation learning. How to design an efficient data structure for subgraphs is a novel perspective that not only complements but advances the field's understanding and approaches to the problem.
• Outperforming State-of-the-Art: We note that our proposed S2N translation is on par with or better than the state-of-the-art. Our approach is fast and lightweight while maintaining performance levels, and should not be dismissed as straightforward.

Last but not least, we would like to quote the other reviewer 1NPi's evaluation of the novelty: "The idea of using graph coarsening for subgraph classification is novel (to the best of my knowledge) and deserves further study."

We think our strengths have not clearly revealed in the introduction, and based on the above bullets, we will revise them so that they are clearly visible. We would appreciate you reconsidering the novelty of our method.

Answers to Questions

Can this approach distinguish the two subgraphs that share the same number of nodes, i.e., is the proposed structure reconstructable? For instance, what if the red subgraph is connected to the right side of the blue subgraph in Figure 1? It may generate the same subgraphs and same number of shared nodes.

Generally, S2N can distinguish between two subgraphs with the same number of nodes. This is because S2N's node will have different neighborhoods in the S2N graph depending on neighbor subgraphs in the global graph. The case where S2N cannot distinguish between two subgraphs of the same size is when (1) the global structure around subgraphs is completely identical and (2) features of subgraphs are identical. However, it is difficult to exist due to real-world graphs' rich features and complex dynamics.

Lack of details for the selection step of the subgraphs to be mapped into new nodes. How do you select the subgraphs and how do you prove that the selected subgraph is the optimal choice?

In this study, all given subgraphs are mapped to new nodes. In detail, all training subgraphs are translated into nodes in the training stage, and all training and evaluation subgraphs are translated into nodes in the evaluation stage (See Section 5). How to select subgraphs that make up the optimal S2N graph is an interesting research topic but is not the scope of this paper. We leave this as a future study and will mention it in the revised paper.

What is the difference between the existing works and the proposed works on super-nodes? I cannot clearly understand what the node boundaries in super-nodes are unknown is in Section 2.

A node boundary is the boundary between a subgraph (or super-nodes) and the global graph. When we say node boundary is unknown, the super-node is not given to existing graph coarsening methods. These methods aim to find a set of super-nodes that partitions a given graph according to specified constraints. Unlike these, we view given subgraphs as super-nodes and explore whether performance and efficiency differ in subgraph-level downstream tasks when the super-nodes are mapped to nodes. That is, the purpose and primary conditions of the research are different. We will revise this part clearly by choosing straightforward terminologies.

Justification for the Choice of the Random Graph Model

I am not sure about handpicking the Configuration Model (CM) as a justification for low computational complexity of S2N. Why has this model been picked: One could definitely study some other random graph models and ask the same questions?

The complexity of S2N strongly depends on the distribution of translated edge weights. Thus, we need a random graph model that can analytically calculate the distribution of edge weights (i.e., the number of shared edges in two subgraphs). When using the configuration model (CM), the distribution of S2N's edge weights can be derived from the degree distribution of the global graph. This is possible because CM calculates the probability of edge existence through the degrees of a pair of nodes. Note that CM is frequently used in analytically calculating numerous network measures [1].

We also emphasize that CM only requires a degree sequence or a distribution. That means CM can also generate graphs generated by other random graph models. For example, when the degree distribution is Poisson distribution, CM generates graphs close to the Erdős–Rényi model. CM can also generate degree distributions with other distributions, for example, power-law distributions. See [2] for more details.

We will add this justification to the revised paper.

[1] Barabási, Albert-László. "Network science." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371.1987 (2013): 20120375.

[2] Newman, Mark. Networks. Oxford university press, 2018.

Answers to Questions

When you coarsen a graph, how is the structure of the original subgraphs preserved? It is not clear how to use the coarsened graph to say something about the subgraphs in the original graph.

It seems that graph coarsening in CoS2N has not been written clearly and in detail. The details of this are as follows, and we will include them in the revised paper.

1. Apply the graph coarsening method to the global graph. The output is a partition of nodes in the global graph. In other words, graph coarsening assigns one super-node to each node in the global graph.
2. Construct induced subgraphs of the global graph per a set of nodes in the same super-node. We call them virtual subgraphs.
3. Merge a set of virtual subgraphs and an existing set of real subgraphs. Until this step, the structures of the original subgraph are preserved as is.
4. Perform S2N translation of this union set of subgraphs.

Thank you for your review and constructive feedback. We provide answers to your questions below.

More Experiments on Synthetic Datasets

There are not many real-world datasets for the supervised subgraph classification. The authors should definitely consider synthetic datasets, e.g. those considered by Alsenter et. al. (2020). It is not clear why the authors have not considered such synthetic datasets.

Thank you for your suggestion. We agree with your comment about synthetic datasets and have conducted experiments on them. The table below summarizes the performance of GCNII+S2N on synthetic datasets.

S2N+A outperforms the state-of-the-art (GLASS) on Density, Coreness, and Component datasets. S2N+0 shows the same performance as GLASS only in Component. For each dataset, the attributes that affect the subgraph properties (i.e., labels of synthetic datasets) are known (as illustrated in the table below) [1]. Because S2N compresses the global graph structure, it is challenging to learn Cut-Ratio, which requires exact information about the border structure (i.e., global structure). Learning Density and Coreness of subgraphs require their internal structures. Therefore, S2N+0, which does not maintain internal structure, relatively underperforms baselines.

To address this issue, we can add structural encoding to the input features, particularly Random Walk Positional Encoding (RWPE) [2]. The efficiency of S2N is maintained since the RWPE is computed once before training and only requires the memory complexity of $O(N)$. RWPE allows S2N to significantly improve the performance of Density and CutRatio, but not of Coreness. We interpret that RWPE for subgraphs can encode internal and border structures well but cannot encode border positions. We leave the development of structural encoding for S2N as future work.

Above all, tasks that depend only on specific attributes barely exist in the real world. We can find evidence from the high performance of S2N on real-world datasets. Our proposed methods provide GNN practitioners with an efficient solution for real-world subgraph-level applications. It is analogous to lossy compression of images (e.g., JPEG) to serve them efficiency-sensitive applications.

We will add all results and discussion to the revised paper.

[1] Alsentzer, Emily, et al. "Subgraph neural networks." Advances in Neural Information Processing Systems 33 (2020): 8017-8029.

[2] Dwivedi, Vijay Prakash, et al. "Graph Neural Networks with Learnable Structural and Positional Representations." International Conference on Learning Representations. 2022.

Clarification on Computational & Memory Bottleneck

The authors do not clarify if the considered datasets are adequately large so that the GPU speed/memory really forms a bottleneck for learning.

For the datasets we used, the number of nodes is 17K, 15K, 57K, and the number of edges is 317K, 3.2M, 4.6M (Table 4 in the Appendix). In the table below, we introduce some datasets referred to as large-scale in our GNN research community. The number of edges compared to these datasets is at a similar level; thus, similar scalability is required to model the datasets in this paper using GNNs. Particularly, when using attention models (e.g., GATv2), we cannot load the largest dataset using baselines into a single GPU of 11G VRAM.

[1] Lim, Derek, et al. "Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods." Advances in Neural Information Processing Systems 34 (2021): 20887-20902.

[2] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

Answers to Questions

How is the proposed CoS2N related to DiffPool "Ying, Zhitao, et al. "Hierarchical graph representation learning with differentiable pooling." Advances in neural information processing systems 31 (2018)."? At a high level, both of them perform pooling and allow further message passing between the pooled clusters/subgraphs. DiffPool adopts a learnable/differentiable way to pool nodes, whereas the proposed method adopts Variation Edges for coarsening. Of course, the task is different, yet I would like to hear from the authors more about the model-architecture-level comparison. This would help readers better see the novelty of the proposed methods with respect to related work designed for different asks.

Thanks for the suggestion on the new perspective. We provide a model-level comparison between CoS2N and DiffPool below. This will be added to the Appendix.

DiffPool learns the hierarchy of a graph to obtain graph-level representations. DiffPool softly assigns each node to a cluster during training by optimizing the downstream task loss. To stabilize the soft clustering assignment, the authors of DiffPool employ link prediction loss and entropy regularization loss. The problem is that the assignment matrix must be maintained in GPU memory, which requires quadratic memory complexity regarding the number of nodes. In other words, we cannot apply DiffPool to large graphs such as global graphs in our use cases.

This study aims to efficiently perform subgraph representation learning by compressing data to be loaded into GPU memory. Memory-intensive graph coarsening, such as DiffPool's soft clustering assignment, should not be used to keep CoS2N efficient. Instead, we can secure the efficiency of CoS2N by performing graph coarsening before training the model, relying only on the structure of the global graph.

Thank you for your review and constructive feedback. We addressed questions about the lack of GNN models other than GCN and GCNII in the general response. We provide answers to your individual questions below.

Ablation Studies and Hyperparameter Analysis

What is more important, the number of layers is tuned between 1 and 2 layers (Section A.3), and it is unclear how much performance fluctuates with even more or less (0 layers, i.e. no message passing) layers. Similarly, it is unclear if alternative readout methods and graph coarsening methods are experimented with. Adding such additional experiments certainly require more work and resource, but would further help improve the soundness of the paper.

Thank you for your suggestion. Now, we are planning to conduct ablation studies on important hyperparameters, including the number of layers, and readouts. Due to the computational resource constraint, we have yet to finish the experiments, but we will include the results as soon as they come out.

Detailed Descriptions of Architectural Differences

I suggest the authors provide more descriptions of existing methods, esp. SubGNN and GLASS. For example, if and what GNN models are used. There is some detail in Appendix A, but an additional section that focuses on the architectural comparison of all the methods would further enhance the clarity of the paper.

We agree with the reviewer's comment that a detailed architecture description will help with clarity. We describe the architectural differences between SubGNN, GLASS, and S2N below. This will be included in the Appendix.

SubGNN, GLASS, and S2N improve different parts of the machine learning pipeline to solve subgraph-level tasks. SubGNN designs a whole model, GLASS augments input data through a labeling trick, and S2N uses a new data structure.

SubGNN performs message-passing between subgraphs (or patches). Through this, the properties of internal and border structures for three channels (position, neighborhood, and structure) are learned independently. To learn a total of 6 (2 x 3) properties, SubGNN designs patch samplers, patch representation, and similarity (weights of messages) for each property in an ad hoc manner. To learn internal positions, for example, SubGNN patches nodes inside the subgraph uses its representation as a message, and uses distance-based similarity as weights. By the complex model design, SubGNN requires a lot of computational resources for data pre-processing, model training, and inference.

GLASS uses plain GNNs but labels input nodes as to whether they belong to the subgraph (the label of one) or not (the label of zero). Separate node-level message-passing is performed for each label to distinguish the internal and border structures of the subgraph. GLASS's labeling trick is effective, but hard to handle multiple labels from multiple subgraphs in a batch. Although the authors of GLASS propose a max-zero-one trick to address this issue, small batches are still recommended. In addition, using a large global graph requires significant computational and memory resources.

In comparison, our proposed S2N uses the new data structure that stores and processes subgraphs efficiently. By compressing the global graph, computational and memory resource requirements are reduced. There are no restrictions on batch learning so we can train S2N graphs in the full batch.

Dear Reviewer AUEj.

We kindly remind you that there is one day left until the discussion period ends. We uploaded the revised paper addressing your concerns. If you have any additional questions after reading our revised paper, we are happy to discuss them.

In summary, our revision includes:

1. We added experiments using GATv2 (a more recent GNN) and GIN (Table 6 and Appendix A.8).
2. We cited the GIN paper.
3. We added ablation studies regarding the number of layers (including no message-passing) and readout methods (Table 7, 8 and Appendix A.9).
4. We provided more descriptions of existing methods, SubGNN and GLASS (Appendix A.1.1).
5. We added the model-architecture-level comparison with DiffPool (Appendix A.1.2).

Thank you again for your time and effort in reviewing our paper. We are looking forward to your response.

We would like to inform you that the discussion period will be closed soon. We have faithfully reflected on the reviewers' comments and questions in our latest revision. We would appreciate it if reviewers could respond to our responses and the revision.

We sincerely thank you for your time and effort in reviewing our paper and for your constructive comments.