Implicit Subgraph Neural Network

We appreciate the reviewer's feedback.

---

Time Consumption

Yes, EIGNN requires a preprocessing step. Our method incorporates a pretraining stage. Below is a comparison of the total runtime (in seconds) for both methods on the PPI_BP dataset. The reported values are the means over 10 runs. We will update the running time results in the paper to reflect your suggestion.

---

Compare with GEQ

Thanks for pointing out a missing reference. I think this paper proposes an interesting algorithm and has the potential to be adapted to subgraph representation learning. We would love to include this method as one of our baselines. However, the author did not release their code (the GitHub link does not work in their paper). We will reach out to them after the review period and include the paper in our literature review.

We appreciate the reviewer’s detailed feedback. Below are our responses addressing each concern:

---

Logic and Motivation Problems

In the revised manuscript, we will include an expanded discussion on why implicit graph neural networks are particularly suited for subgraph learning tasks. We will clarify how capturing long-range dependencies through fixed-point iterations provides a distinct advantage over conventional methods, thereby reinforcing the motivation behind our approach.

---

Novelty and Contribution of the Paper

While our method builds on implicit graph neural networks, our contribution lies in:

1. Novel Extensions: Developing new extensions to these models specifically for subgraph learning.
2. Label-Aware Integration: Integrating label-aware subgraph-level information via a novel hybrid graph framework.
3. Bilevel Optimization Formulation: Formulating the training as a bilevel optimization problem with convergence guarantees.

These aspects, to our knowledge, are the first to be explored in the subgraph context and lead to significant performance improvements over state-of-the-art subgraph neural networks. We will further elaborate on these contributions in the revision.

---

Motivation for Using Bi-level Optimization

The objective of implicit models can be naturally formalized as a bilevel optimization problem. The lower-level problem involves finding the fixed-point embeddings for the current setting, and the upper-level problem focuses on minimizing the classification loss given the fixed-point embedding from the lower level. Bilevel optimization provides a different angle to train implicit models, offering computational advantages. The stability of implicit models is a very interesting topic for further exploration, and to the best of our knowledge, no work has investigated this area so far.

---

Explanation and Clarification of Symbols

We will check and revise the manuscript to ensure that all symbols are clearly defined.

---

Convergence

Both the implicit differentiation (via fixed-point iteration) formulation and the bilevel optimization formulation often lead to equivalent problems, meaning that optimally solving one also solves the other. However, the resulting algorithms differ in various settings. In our case, there are higher practical computational costs for implicit differentiation, which arise due to the following two differences:

• Iteration Flexibility: Bilevel optimization permits the use of minimal fixed-point iterations during the early phases of training—empirically, one iteration per gradient step is often sufficient. In contrast, implicit differentiation requires a relatively larger number of fixed-point iterations at each gradient step to maintain accuracy.

• Backward Gradient Computation: Implicit differentiation involves computing backward gradients through an additional fixed-point iteration, which adds extra computational overhead compared to bilevel optimization.

---

We hope these responses address your concerns and clarify the contributions in our work.

We thank you for your valuable feedback. Our responses are as follows:

Motivation

While traditional graph neural networks focus on node-level or entire graph-level representations, many real-world problems require understanding the structure within parts of a graph. Subgraphs often represent meaningful patterns—like communities, motifs, or functional units—that are lost when only considering individual nodes. Moreover, traditional GNNs perform poorly on subgraph-level tasks due to their limited ability to capture localized and complex structural nuances, resulting in weak generalization when applied directly to subgraph classification or related tasks. Therefore, researchers incorporate subgraph information into their models to achieve better generalization. Previous works only consider structural or membership information of subgraphs, which means they primarily leverage the connectivity patterns or the existence of subgraph membership without integrating additional contextual cues. In contrast, our approach augments this by incorporating label-aware subgraph-level information that enriches the representation. By explicitly modeling both the inherent structure and the associated label information, our method not only differentiates between subgraphs with similar structural features but also captures long-range dependencies and complementary interactions among subgraphs. This holistic integration of node-level and subgraph-level cues ultimately leads to more expressive embeddings and significantly improved performance on subgraph-level predictive tasks.

---

Mistake in Figure

We thank the reviewer for pointing out this mistake. We will correct it.

---

Connection between Max-Zero-One Label Trick and Weisfeiler-Leman Test

Max-zero-one labeling enhances subgraph representation learning by augmenting node features based on their membership in subgraphs. It serves as a relaxation of the zero-one trick [1]—which processes each subgraph individually by assigning binary labels. The zero-one trick is capable of producing embeddings with expressiveness equivalent to the $1$-Weisfeiler-Leman ($1$-WL) test, meaning it can distinguish graph structures as well as the $1$-WL test does. Since the max-zero-one trick relaxes these binary assignments by jointly processing multiple subgraphs, it is inherently weaker. Therefore, its discriminative power is limited to that of the $1$-WL test and cannot exceed it.

---

[1] Zhang, Muhan, et al. "Labeling trick: A theory of using graph neural networks for multi-node representation learning." Advances in Neural Information Processing Systems 34 (2021): 9061-9073.

---

We hope these responses address your concerns and clarify the contributions and design choices in our work.

We thank you for your valuable feedback. Our responses are as follows:

---

Sensitivity to Subgraph-Level Graph Construction Methods

In our experiments, we previously compared four subgraph-level graph construction methods—random, neighborhood, position, and structure. The goal was to show that these classical methods do not significantly improve classification performance, as they achieve similar results to using random subgraph information. This observation echoes conclusions from prior work like GRASS and SSNP.

To further the comparison, we introduce additional label-aware methods:

• class-rand: For each class, we randomly connect k pairs of training supernodes.
• Star: For each class, we select a centroid supernode and connect it with all other supernodes within that class.

Experimental Results on HPO-METAB

The ISNN-class-rand method improves performance over ISNN-rand by using label information to ensure that subgraphs within the same class have similar embeddings, making classification easier. The ISNN-Star method further boosts performance by selecting a centroid supernode for each class and connecting it to all other supernodes, reinforcing intra-class similarity, though it introduces more edges. Our ISNN method connects only the top-k most distant pairs of supernodes, balancing label-aware benefits with a sparse graph structure.

---

Additional Hyperparameter Sensitivity Analysis

We further investigate the sensitivity of hyperparameter gamma on ISNN.

Ablation Results on Gamma for PPI_BP

Ablation Results on Gamma for EM_USER

These results show that the best performance occurs when gamma is between 0.01 and 0.1. For example, PPI_BP achieves its best performance at gamma = $0.01$, while EM_USER peaks at gamma = $0.1$. Gamma values outside this range lead to worse performance, highlighting the importance of using a moderate gamma.

---

Applicability and Adaptations for Dynamic or Streaming Graph Settings

ISNN is designed to capture long-range dependencies via implicit iterations and a hybrid graph framework. To achieve this, the model requires access to the entire graph to compute the fixed-point embedding. Therefore, directly adapting ISNN to dynamic or streaming settings is challenging. However, if a smooth condition on the embeddings can be ensured (for example, bounding the change in the fixed-point embedding under edge perturbations), the error in approximating the final fixed-point embedding could be controlled. This approach offers a potential pathway to adapt ISNN to dynamic settings, which we plan to investigate in future work.

---

Justification for Label-aware Subgraph-Level Information Versus Random Edge Assignment

Our approach, ISNN, significantly outperforms random edge assignment. Please compare the performance of ISNN on the HPO-METAB dataset in Table 3 against that of ISNN-rand in Table 4 of our manuscript.

To further illustrate the benefit of our label-aware subgraph information, consider the following example: if two subgraphs with different labels are connected through random edge assignment, the GNN is forced to make their embeddings more similar, which complicates the classification task. Our label-aware design, on the other hand, reinforces the inherent differences between subgraphs, thereby facilitating more discriminative embeddings.

---

Scalability of Our Method

The complexity of a standard GCN is given by:

$O(n \cdot d^2 + E \cdot d)$

where:

• $n$ is the number of nodes,
• $E$ is the number of edges, and
• $d$ is the hidden dimension.

For our method, the complexity becomes:

$O((n+s) \cdot d^2 + (E+k) \cdot d)$

where:

• $s$ is the number of subgraphs, and
• $k$ is the number of additional edges introduced.

Thus, the additional overhead introduced by ISNN is an additive term of:

$O(s \cdot d^2 + k \cdot d)$

Empirically, $k$ can be controlled to remain small, and $s$, which is part of the input, is typically small in most practical subgraph learning tasks. Therefore, ISNN exhibits scalability similar to that of a standard GCN in most practical scenarios.

---

We hope these responses address your concerns and clarify the contributions and design choices in our work.