Implicit Subgraph Neural Network
Authors: Yongjian Zhong
Liao Zhu
Hieu Vu
Bijaya Adhikari
Venue: ICML 2025 poster (2025)
Keywords: Subgraph Classification
Implicit Models
Primary area: deep_learning->graph_neural_networks

Abstract: Subgraph neural networks have recently gained prominence for various subgraph-level predictive tasks. However, existing methods either \emph{1)} apply simple standard pooling over graph convolutional networks, failing to capture essential subgraph properties, or \emph{2)} rely on rigid subgraph definitions, leading to suboptimal performance. Moreover, these approaches fail to model long-range dependencies both between and within subgraphs—a critical limitation, as many real-world networks contain subgraphs of varying sizes and connectivity patterns.  
In this paper, we propose a novel implicit subgraph neural network, the first of its kind, designed to capture dependencies across subgraphs. Our approach also integrates label-aware subgraph-level information. We formulate implicit subgraph learning as a bilevel optimization problem and develop a provably convergent algorithm that requires fewer gradient estimations than standard bilevel optimization methods.  
We evaluate our approach on real-world networks against state-of-the-art baselines, demonstrating its effectiveness and superiority.

Implicit Subgraph Neural Network
Yongjian Zhong'
Liao Zhu
Hieu Vu
Bijaya Adhikari
Abstract
Subgraphs capture critical internal structures within graphs, which are essential for variety of applications. For exam- ple, echo chambers in social networks are subgraphs vital for studying misinformation diffusion and polarization (Cinelli et al., 2021); fraudulent activities within e-commerce net- works induce subgraphs with properties that distinguish them from the rest of the graph (Song et al., 2021); and cascades of cospital-acquiree works create subgraphs that aid in detecting asymptomatic infections (Jang et al., 2021).
Subgraph neural networks have recently gained prominence for various subgraph-level predictive tasks. However, existing methods either 1) ap- ply simple standard pooling over graph convolu- tional networks, failing to capture essential sub- graph properties, or 2) rely on rigid subgraph definitions, leading to suboptimal performance. Moreover, these approaches fail to model long- range dependencies both between and within subgraphs critical limitation, as many real- world networks contain subgraphs of varying sizes and connectivity patterns. In this paper, we propose a novel implicit subgraph neural net- work, the first of its kind, designed to capture dependencies across subgraphs. Our approach also integrates label-aware subgraph-level infor- mation. We formulate implicit subgraph learn- ing bilevel optimization problem and de- velop a provably convergent algorithm that re- quires fewer gradient estimations than standard bilevel optimization methods. We evaluate our approach on real-world networks against state-of- the-art baselines, demonstrating its effectiveness and superiority. Our code is avaliable https: / //github.. www.cooo//////.e.eee www./o.//r/rrp///......
infections in healthcare net-
The ubiquity of graphs and relational data has driven ad- vancements in machine learning algorithms tailored to graphs, with graph neural networks (Wu et al., 2020) emerg- ing as the dominant method across many, if not all, of these domains. While most current graph neural networks focus node, edge, and graph-level tasks, there have been some, albeit limited, advancements in subgraph neural networks and subgraph representation learning.
(Adhikari et al., 2018) proposed Sub2Vec, a subgraph- level representation learning framework that captures a sub- graph's 's neighborhood and structural information in la- tent space. However, the approach is simplistic and fails to achieve state-of-the-e performance. (Alsentzer et al., 2020) introduced Subgraph Neural Networks (SubGNN), one of the first neural networks explicitly designed for subgraphs, incorporating positional information (i.e., where a subgraph is located within the entire graph) alongside neighborhood and structural properties. However, SubGNN relies on arti- ficially sampled patches and, later studies show, offers only marginal improvements over standard GNNs.
1. Introduction
Graphs serve as natural abstractions for complex relational data across numerous domains, including but not limited to the web (Kumar et al., 2000; Kleinberg et al., 1999), health- care (Wang al., 2020), social networks (Leskovec al., 2007; Ugander et al., 2011), language and speech (Nas- tase al., 2015), and e-commerce (Huang et al., 2004). A subgraph of graph G(V, E) is another graph S(V", ('") in- duced by subset V C V of nodes, where naturally E' C E.
Subsequent works, GLASS (Wang & Zhang, 2021) and SSNP (Jacob et al., 2023), focus on pooling node-level representations to learn subgraph embeddings. GLASS em- ploys a "labeling trick" to indicate node membership in a subgraph, learning node embeddings that are then aggre- gated into subgraph representations. SSNP first transforms node embeddings and applies multi-step stochastic pooling to generate subgraph embeddings. Notably, both methods rely solely on node memberships and overlook additional subgraph-level information.
'Department of Computer Science, University of Iowa, Iowa City, USA. Conrepondencee <yongjian-zhor cathon@@ioww.ccdu... Bijaya Adhikari <bijaya- adhikari @ uio
Yongjian Zhong
Moreover, capturing long-range dependencies between sub- graphs is critical in subgraph representation learning, as subgraphs that are far apart in the graph may still share
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Implicit Subgraph Neural Network
complementary structural information that enhances clas- sification performance. None of the prior work explicitly captures long-range dependency.
the algorithm reaches a stationary solution when one exists. Our key contributions are as follows:
To address these issues, we first propose incorporating label- aware subgraph-level information alongside node embed- dings to learn more expressive subgraph representations. Leveraging subgraph-subee subgraph relations provides an addi- tional advantage (see Figure 3). As shown in the figure, explicitly modeling these relationships reveals hidden con- nections between subgraphs that may not be apparent in the original graph. While incorporating subgraph-subgraph relations allows our model to capture certain long-range dependencies, it remains insufficient for ensuring general long-range interactions across subgraphs. To fully address this, we formulate our subgraph neural network using the Implicit Neural Network framework (Sitzmann et al., 2020).
We introduce the first implicit subgraph neural net- work, leveraging both node-level and label-aware subgraph-level information.
We propose an efficient bilevel optimization algo- rithm for training ISNN, replacing gradient descent in the inner loop with fixed-point iteration, reducing gradient complexity while ensuring convergence.
We conduct extensive experiments on four bench- mark datasets, demonstrating that our approach con- sistently outperforms state-of-the-ard baselines in F1- score across all datasets and in AUROC across all but one dataset.
Implicit graph neural networks (TGNNs) have gained popu- larity for capturing long-range dependencies while avoiding performance degradation (Baker et al., 2023; Liu et al., 2022). At high level, IGNNs iterate a single graph convo- lution operator until the learned node representations con- verge to a fixed point. Since the number of iterations is unbounded, the representations can incorporate information from topologically distant nodes. While various INNN ex- ist ist-incudiing models for dynamic (Zhong et al., 2024) and heterogeneous graphs (Gu et al., 20eee are currently no implicit models designed for subgraphs. Moreover, con- ventional INNS cannot be trivially adapted to subgraph learning. as they become unstable when approaching the fixed point (see Section 4.2).
2. Related Work
Subgraph Neural Networks: Initial works like Sub2 Vec (Adhikari et al., 2018) introduced subgraph-level representa- tion learning by focusing on capturing two important prop- erties of subgraphs - structural and neighborhood. However, its simple architecture limited its expressiveness, leading to suboptimal performance compared more sophisticated graph neural networks. Subgraph Neural Networks (Sub- GNN) (Alsentzer et al., 2020), was one of the first attempts to explicitly account for positional information of subgraphs within the entire graph, as well as their local structural fea- tures. To capture the full topologies of subgraphs, SubGNN samples anchor patches from the base graph and propagates messages between the anchors and the subgraph across mul- tiple channels. However, this process of sampling channel- specific anchor patches and then propagating them is com- putationally intensive.
Present work. In this paper, we propose the IMPLICIT SUBGRAPH NEURAL NETWORK (ISNN), the first implicit model for subgraph representation learning (see Figure 2). Our approach consists of an IGNN applied to both the origi- nal graph and a newly constructed hybrid graph. This hybrid graph extends the original structure by incorporating compo- nents that explicitly model relationships between subgraphs, as well as interactions between subgraphs and original graph nodes.
Recent approaches, such as GLASS (Wang & Zhang, 2021) and Stochastic Subgraph Neighborhood Pooling (SSNP) (Jacob al., 2023), have focused on improving subgraph representation learning by using node-level representations. These methods first employ node embeddings then pool them to form subgraph embeddings. GLASS utilizes a novel labeling trick to distinguish whether a node belongs to a subgraph, and SSNP offers a multi-step stochastic pool- ing method to process node embeddings. However, even with these advances, both models focus mainly on node memberships and do not fully utilize other subgraph-level properties, such as structural or relational information be- tween subgraphs.
However, training such a model presents significant chal- lenges (see Section 4). To address this, we reformulate the problem as a bilevel optimization problem (Sinha et al., 2017), where the upper-level objectíve corresponds to the subgraph classification task, while the lower-level con- straints enforce the fixed-point conditions of the implicit representation. Although optimizing non-convex functions in bilevel settings is generally difficult, our formulation in- cludes non-expansive constraints, enabling us to develop an efficient bilevel optimization algorithm. This algorithm leverages fixed-point iteration instead of gradient descent in the inner loop, reducing gradient oracle calls. We further provide a theoretical convergence guarantee, ensuring that
Graph Implicit Models: Implicit models define their out- put through fixed-point equations. (Bai et al., 2019) provides an equilibrium model for sequence data based on an equilib- rium equation's 's fixed-pone point solution. Implicit Graph Neural
2

---

Implicit Subgraph Neural Network
S1
S
S3
Subgraph Labels
So
C₁
C2
(a) A graph with three subgraphs
(b) Corresponding subgraph-level graph
Figure 1: The distance between the two subgraphs S1 and S3 in the original graph (a) is approximately 2/2 (where n is the number of nodes in the blue circle). However, in the subgraph-level graph (b) the distance for the same two subgraphs is only 2.
Network (IGNN) (Gu et al., 2020) showcases an implicit model, leveraging several layers of graph convolution net- work (GCN) discover long-range dependencies. (Park et al., 2021) introduce the equilibrium GNN-based model with a linear transition map while ensuring the transition map is contracting such that the fixed point exists and is unique. (Liu et al., 2021a) present an infinite-depth GNN which captures long range dependencies in the graph while avoiding iterative solvers through deriving closed-form solution. (El Ghaoui et al., 2021) present general implicit deep learning framework and discusses the well-posedness of implicit models. (Chen et al., 2022) employ the diffusion equation as the equilibrium equation and solve a convex optimization problem to find the fixed point in their model.
number of nodes and d be the feature dimension. We are given a set DD of subgraphs drawn from and their cor- responding labels, i.e., D {(S. &.,, v:)) where V; S V is subset of nodes and & is the edges induced by V (naturally, E, C E), and is the total number of subgraphs. This work focuses on the task of subgraph clas- sification, where the goal is to predict the correct label yi for each subgraph St.
Graph Implicit Models: Implicit models (Gu et al., 2020; Liu et al., 2021a; Zhong et al., 2024) typically follow the structure Z XX, where f is a function, often parameterized by neural network, X represents the input data, and Z denotes the learned representation. The fixed-point solution can be obtained iteratively as Z = lim Ze+1 = lim f'Zx; = f(Z", X). Finally, the implicit models output the fixed-point represen- tation for the downstream tasks.
Bilevel Optimization: Bilevel optimization has gained significant popularity in recent years due to its applicability in various domains. A bilevel problem involves two nested optimization tasks: an upper-level problem and lower- level problem, where the leper-level decision depends on the solution of the lower-level problem. These problems are generally difficult to solve. For bilevel problems with a strongly-conwe lower-level problem, algorithms based on the Implicit Gradient (IG) method have been proposed, as seen in the works of (Pedregosa, 2016; Ghadimi & Wang, 2018). Another branch of bilevel optimization is Itera- tive Differentiation (TTD) methods, which approximate the lower-level solution using iterative optimization techniques, as discussed by (Liu et al., 2021c; Hu et al., 2022). Addition- ally, penalty-based methods, such as barribrrier and gradient norm penalty, have been introduced to solve bilevel prob- lems, as explored by (Liu et al., 2021b; Shen & Chen, 2023). Bilevel optimization has also been successfully applied in various fields, including federated learning (Tarzanagh et al., 2022) and ranking (Qiu et al., 2022).
The labeling trick (Zhang et al., 2021) in subgraph learning is a technique aimed at enhancing the expressive power of Graph Neural Networks (GNNs) for multi-node representation learning. It involves assigning labels to nodes based on their membership A common example is the zero-one labeling trick, where nodes belonging the target subgraph are labeled as 1, and all others are labeled O. The zero-one labeling trick requires relabeling for each different target subgraph, which can be computationally expensive. To address this, a more efficient variant, the max-zero-one (Wang & Zhang, 2021) labeling trick, enables batch processing by assigning labels based on the presence of any subgraph in the batch. For instance, a node is labeled in the batch, allowing for the handling of multiple target subgraphs in single forward pass.
Labeling Trick:
subgraph.
if it belongs to a subgraph
3.2. Enhanced Subgraph Representation
3. Methodology
The tfate-of-the-ar subgraph learning algorithms can be broadly categorized into two approaches: 1) learning from subgraphs, such as SubGNN (Alsentzer et al., 2020); and 2) learning from nodes, such as GLASS (Wang & Zhang, 2021) and SSNP (Jacob et al., 2023). As discussed earlier,
3.1. Preliminaries
Notation:
Consider a graph G (V,E,X,, X), where V rep- resents the set of nodes, E represents the set of edges, and
X E R is the feature matrix. Additionally, let be the
3

---

Implicit Subgraph Neural Network
Z:
Edge conseraction
Zn
Classification Loss
S
S
Classifier
IGNN
Attu 2eo 2,)
S
Supermodd--upeerrde edges
S
S1
IGNN
Nocle Sapereospe edges
Supervised Pretzaining
Figure 2: Overview our method. We first construct a hybrid graph that consists both regular nodes and supernodes, representing subgraphs. The edges between supernodes are inferred via pertaining (See Section 3.5). Finally, we learn node and subgraph embeddings jointl.. The entire framework trained using a novel bi-level optimization algorithm.
SubGNN does not fully leverage node-level information, and its subgraph-level information is not powerful enough to lead to state-of-the-ar performance. On the other hand, methods like GLASS and SSNP completely ignore the sub- graph information. However, it is intuitive that subgraph information, leveraged properly, is essential in subgraph representation learning. Consider the example in Figure The dependency between subgraphs S₁ and S3 is difficult to capture in the node-level graph but is easy establish in the subgraph-level graph.
Proof. Subgraph enhancement can simulate the labeling trick with an additional aggregation step and auxiliary dimension. Subgraph nodes send messages to other nodes, and a node the node-level graph receives any message, its auxiliary feature is marked as I; otherwise, is marked as O. Afterward, the subgraph-level graph can be disregarded.
By incorporating appropriate subgraph-level i information, our framework enhances the expressivity of GNNs, enabling them distinguish between subgraphs that the max-zero- one labeling trick fails to differentiate, as shown in Figure 3. Consider graph with no node features. this case, S1 and S are indistinguishable, even with the max-zero-one labeling trick, since all nodes belong least one subgraph and are labeled 1. However, Figure 3 also demonstrates that by adding nodes to represent subgraphs and directed subgraph-level edges, the two trees become distinguishable.
To address these limitations, we propose label-aware sub- graph enhancing framework that integrates both subgraph- level and node-level information, offering flexibility and expressivity. The high-level concept is illustrated in Figure 2. The subgraph enhancing framework starts by construct- ing hybrid graph G = ((V U V.J. (E U & U Ens }, X) where each supernode in V. represents a subgraph. E, is the set of edges among super-nodes in V. (capturing subgraph-subgraph relationship), and Ens is the set of edges between V and V. (capturing membership relationship). X (=+m))x is the corresponding feature matrix. Then, obtain (Zn, ?..) the embeddings of G using the pro- posed approach. Finally, the subgraph embeddings are ob- tained by using attention
Another key challenge in subgraph learning is that sub- graphs of the same class may be widely separated within the base graph. Effectively learning meaningful embeddings for these subgraphs requires capturing long-range dependencies between them. Graph Implicit Models (GIMs) are particu- larly well-suited for this task, as they naturally propagate information across distant nodes. To address this issue, we propose the Implicit Subgraph Neural Network (ISNN). In the following sections, we formally introduce our model, provide theoretical guarantees, and detail the construction of the hybrid graph G.
= Attention 2n,, 2,))
We will discuss the exact & construction later section. However, as demonstrated by the following proposition, the subgraph enhancing framework is more flexible than the labeling trick proposed in (Wang & Zhang, 2021) (also described in the Preliminaries section).
3.3. Formulation and Optimization
Proposition 3.1. Max-zero-one labeling trick a special case of subgraph enhancing.
A straightforward way ahead is to train an implicit model di- rectly on the hybrid graph G. However, as demonstrated by

---

Implicit Subgraph Neural Network
Suhgraph Labds
c:
(a) Original graph
(b) Assymetric rooted trees
Figure 3: An example where max-zero-one labeling trick fails. Consider the graph on the left with empty features. GNN cannot distinguish S and S2 since every node in these subgraphs has the same topology, and the max-zero-one label trick assigns all nodes. The figure on the right demonstrates these two subgraphs can be distinguishable if the introduced subgraph-level edge has asymmetric weights.
our experiments, this approach does not lead to a desirable performance. This is primarily because directly computing fixed-point embeddings on the hybrid graph which involves a relatively complicated aggregation step is unstable (this the main reason why standard IGNN baselines do not perform well for subgraph-level tasks). To overcome this problem bilevel optimization
Chen, 2023), which is first-order Hessian-free penalty- based nonconvex bilevel optimization algorithm. Such a penalty-based algorithm solves an alternative problem
min F(x: 2) + (g(x, Z) g(ar Z²)) aEN'Z
(4)
issue, we formulate problem and solve it approximately. Our bi-level objective can be written as follows:
where g(x, = 1 - f(z W)ll denotes the lower-level problem. g is a Polyak-t.ojasiewier (PI.) func- tion, solving this problem with large enough y can deliver stationary solution (Proposition & 2 in (Shen & Chen, 2023)). Since solving Z* for each gradient descent step is intractable, prior works use proxy variables to approximate it (Hu et al., 2022).
min F(:; Z*) æEN
{vi,, du (Z)li)
s.t. 2 A
arg min
Z - f(z, ((z,G;s
2 2
The main difference between our algorithm and V-PBGD is that we used the fixed-point iteration to update the proxy embeddings Ż. We will show that our objective is spe- cial case of nonconvex bilevel problem with lower-level PL function. Thus, this allows to adopt existing techniques, and the additional non non-expansiveness allows us to get bet- ter gradient oracle complexity (see Remark 3.9). (Zhong et al., 2024) also proposed a bilevel algorithm using fixed- point iteration the inner loop. However, their algorithm heuristic and does not provide convergence guarantees.
where Z' E Rm is the subgraph embeddings. [ de- notes the i-th row of Z'. represents the classification loss, e.g., cross-entropy, and dy is a classifier parameterized by 9. Let æ denote the set of all parameters, and X' denotes the feasible set. This paper adopts a linear fixed pooling fune- tion and simple mean aggregation. However, our approach is flexible and supports learnable pooling and aggregation functions. f is implicit model parameterized by and W. In particular, we use the EIGNN (Liu et al., 2021a) formulation for f.
3.4. Convergence Analysis
G,E, W) aAZb(W) + (X)
(2)
WTW
Let us start with some definitions.
(WW) ||I]|W +
(3) Definition 3.2. function f is said to be p-contractive if it
satisfies f] - f(y) 12 < 41l x - = for any x, in the domain of f.
In the equations presented above, A denotes the normalized adjacency matrix, while a E (0, 1) is controlling, and eμ small float for numerical stability. The a selected small enough so that f a non-expansive operator w.r.t. Z.
Definition 3.3. A function f is said to be a J--Polykk
Lojasiewicz function it satisfies |[V Z =(f(x)) f*), for any x in the domain of f and f inf f(x).
We propose Algorithm 1 to find stationary solution of prob- lem 1. The algorithm consists of two for-loops. The inner loop runs the fixed-point iteration K times, and the outer loop runs gradient descent with proxy embeddings, where Vf == (Q.f. and ff == (0.f.0) 0). This training al- gorithm follows the framework of V-PBGD from (Shen &
To state the convergence result, we first make the following assumptions.
The upper-level function and lower- level function g are Lsooth for all variables, the upper-level function F is -ipsschhii for all variables.
Assumption 3.4.
5

---

Implicit Subgraph Neural Network
Algorithm 1 ISNN Training Algorithm
Now, are ready to state our convergence result.
1: Input: Graph G = (VUV,, X), Learning
Theorem 3.8. Consider Algorithm 1, suppose Assump-
rate 17. hyperparameter 7
tion 3.5 and 3.4 hold. Choosing 1 E (0, Lr + 7(2T.g + Ologg v ), and ? (2(--0.)) where e is the desired error. Let 2 denote the list of all parameters
2:
Z +- 0;
2 2(1- )l, 1,
12
3: for i=I....,TT do
4:
Zi Z
{ar, 2}, and A,(2) := F(xx, Z) (g( Z) g(x, 2)) be
5:
for for j do
the loss of penity problem. Let = == Proj( 2 V AA, (z²)) be the solution updated by the exact gradient. We have the following
6:
2 -1 G;);
7:
end for
8:
Vg = Vg(æ', ) - Vg xxx
9:
VF, = Fa'''; : 2 + Vg
T Σ C1 2/1 184 + 10
10:
(x++1, 1)+ t Proj (ax', 7 - -1 F,))
(8)
11: end for
12: Return: (x" 2z")
Remark 3.9. Theorem 3.8 indicates the Algorithm 1 can produce stationary solution to the bilevel optimization problem if it converges. The sample complexity is ((6-1.)), which matches the result in (Shen & Chen, 2023). To note that, our method only computes gradient once per iteration. However, the method in (Shen & Chen, 2023) needs to compute K 1 gradients per iteration. Thus, our method more efficient in training implicit models.
Assumption 3.5. Assume that -(x -) is p-contractive for all x E X' and X' is nonempty.
Note that the Assumption 3.4 is standard in bilevel optimiza- tion literature (Hu et al., 2022; Shen & Chen, 2023). The additional Assumption 3.5 is natrual requirement for im- plicit models to ensure the well-posedness (Gu et al., 2020), which we can maintain by choosing small enough a. We defer most of the proofs in this section to the Appendix.
3.5. Hybrid Graph Construction
There are several elements in the hybrid graph Ô that need to be described: & Ens. and X. The feature matrix X can be constructed by concatenating node features with subgraph features. The subgraph feature, in turn, can be defined as the average node feature within each subgraph. Similarly, an edge (i, E Ens exists if node i is a member of subgraph j. The key challenge is defining &,. This paper presents three possible ways to define it. However, before diving into these details, let us first explore alternative methods.
Remark 3.6. The lower-level problems is 2(1 (1) PL function.
Proof. For simplicity, we denote g(x, 2), f(Z, G;g, W) by gr (Z), (Z), and Z denotes the vectorized Z. By the definition of function g. we have
gz) = (1 (Z)
(i fz (2)
Z
Many subgraph-level methods (e.g.. Sub2Vec and SubGNN) adopt a similar framework, but they learn em- beddings solely from the subgraph-level graph, i.e.. G = (V., S,, X). These methods construct & using three ap- proaches - 1) Position: defines edge weights based on the distance between subgraphs, 2) Neighborhood: Computes edge weights using the number of overlapping neighbors be- tween subgraphs, and 3) Structure: Measures edge weights based on the topological similarity of subgraphs. However, these approaches do not achieve good performance in prac- tice. We empirically show that they perform no better than assigning random edge weights (see Section 4.2). This is be- cause these strategies ignore the downstream tasks, and the three types of information may not necessarily be beneficial for later training.
v.. = =I([1 (Z) (Z fa (2))
(5)
7
Since fa. is j-contractive function, the operator norm of its Jacobian is bounded by μ. Therefore, the operator norm of T (Z) is lower bounded by - J.. Thus,
Z
IV (2) 2 2(1 mm (Z)
Moreover,
0 Z (Z) II(T-
(Z fz(2))) (Z)
7
(7)
Therefore, instead of focusing on the structural properties of the graph, we propose an approach that directly addresses the task. For a classification task, two intuitive assumptions can be made: 1) Embeddings of supernodes belonging to the same class should be similar. 2) A test supernode is more
Remark 3.7. Based on the Assumption 3.5, the model is well-posed i.c., the lower-level problem admits a unique fixed point.
6

---

Implicit Subgraph Neural Network
Table I: Statistic of datasets.
Table 2: Micro-F1 on real-world datasets averaged over 10 runs, for all models. Bold indicates the best result, and underline indicates the second best result.
Dataset
#Nodes
#Edges
#Subgraphs
#Labels/Clasees
PPI-BP
17,080
316,591
1,591
HPO-METAB
14,587
3,238,174
2,400
Method
PPI-BP
HPO-METAB
HPO-NEURO
EM-USER
HPO-NEURO
14,587
3,238,174
4,000
10
MLP
0.297
0,443
0,490
0.808-0135
EM-USER
57,333
4,573,417
324
GCN-plain
=.398
0.452eares
0.535emm8s
0,561=0021
Sub2Vec
0. g.309
0.1 1411400
0.206gamm
0.522:0041
GLASS
0.618=00x
0,598
0.675=a0.0r
0.884-0000
SubGNN
0. g009
0.531
0.644 nos
0.815
likely to share the same label as its most similar supernode in the training set.
SSNP
0.636_puam
1.5m7
0.682, jucon
0.888 tuo0s
IGNN-plain
a.389
0.284
0.215
0.579
EIGNN-plain
0.425 _edde
0.252
0.312_n00r
0.591 _.99s
To this end, our framework begins by pretraining the model with an empty &.. Based on the pretrained embeddings and these two assumptions, we introduce two label-aware strategies tailored for different scenarios:
SofTGGN
=u594
0.520aamx
0.653
0.820-
SORTEGGNN
0.592_na2
0.522iome
0.658
0.829
ISNN
0.731=0022
0.6466:9014
0.688:00.04
0.914:0098
Table 3: AUROC scores on real-world datasets averaged over 10 runs, for all models. Bold indicates the best result, and underline indicates the second best result.
Binary & Multi-class: For each class, we connect k pairs of the most distant training supernodes.
Multi-label: We select certain labels and convert them from binary to integer values, thereby treating the data as multi-class.
Method
PPI-BP
IPO-METAB
IPO-NEURO
EM-USER
MLP
0.814
0.764
0.896
GCN-plain
0,663
0.772
0.773gpmm
0.525_uee
Sub2Vec
0.544
0.496
0.504
0.518:
In all these strategies, each test node connected its closest training node in the latent space during inference.
GLASS
0,835 Lanee
0,891 tame
0.8521000
0,960_nx
SubGNN
0.816
0.862
0.843=0014
0.91
SSNP
0,831
0.883
0.867100M
0,952,ua01
Klan-plain
0,514
0.496
0.709
4. Experiments
EIGNN-plain
0.630
0.579
0.601 1.121
0.553
SoRTGNN
0.797
0.818
0.868
0.932:ua05
SofEEGGN
0.821 1s
0.868: boor
0.927
Dataset: We assess our model's performance and scalability by benchmarking it against various subgraph classification baselines on four real-world datasets. Following the experi- mental setup of SubGNN (Alsentzer et al., 2020), we evalu- ate our approach on PPI-BP, HPO-METAB, HPO-NEURO, and EM-USER. The statistics of the datasets are summarized in Table 1.
ISNN
0.924:0812
0.919:axcc
0.896=
0.959
pects of subgraph topology. This enables SubGNN to have expressive subgraph representations.
SSNP: aggregates both subgraph and neighborhood information without any labeling tricks to classify sub- graphs. SSNP generates subgraph embeddings by first processing node features using transformation layers (GCN, MLP, etc.) and then, for every subgraph, ag- gregating the node features of the subgraph and its neighborhood through SSNP.
Models: We take the following models as our baselines.
Plain/Soft models: use the backbone model gener- ate node embeddings then aggregate them to subgraph embeddings. The soft models are the plain models trained by our optimization algorithm.
Hyperparameter: For all datasets, we employ a 2-layer GNN and a 2-layer MLP for classification, with a fixed hidden dimension of 64, consistent with the SubGNN settings. For our method, we vary the value of y in {0.0001, 0.001, 0.013 and the number of inner-loop iter- ations K in 21,2,3,4,5).
Sub2Vee: generates subgraph embeddings by first cap- turing two main properties, neighborhood and struc- tural, of each subgraph and projecting these features into low-dimensional continuous vector space.
GLASS: employs a max-zero-one labeling trick, distin- guishing nodes within the target subgraph from those outside it. GLASS effectively captures the internal and external topology that influence subgraph properties using standard message passing framework.
Configuration: We rerun each experiment 10 times (max of 1500 epochs) and report the average performance. We conducted experiments on AMD EPYC 7763 64-Core Pro- cessor with 2 TB memory and on NVIDIA A30 GPUs.
propagates neural messages between sub- graph components and anchor patches from the under- lying graph by utilizing three distinct channels: neigh- borhood, structure, and position to capture various as-
SubGNN:
4.1. Subgraph Classification
The results are presented in Tables 2 and 3, demonstrat- ing that our model outperforms baselines across almost all
7

---

Implicit Subgraph Neural Network
Table 4: Performance of four variants of our model, which uses different ways of constructing subgraph-level graph.
Metab: Gamma Micro
PPI BP:
C54
Accuracy
HPO-METAB
ISNN-P
ISNN-S
IGNN-N
ISNN-rand
F1
0.58620001
0.598
a.589
AUROC
0.87420007
0.874-6000
0.87620007
0.876=0.008
C48
Foounett WIROMM
0.0
06
22
22
04
05
Gamma
Gamma
datasets and metrics. Notably, our model excels on the two multi-class datasets, PPI-BP and HPO-METAB, where label-aware subgraph information plays a crucial role. By leveraging this information, the model learns more con- centrated embeddings for each class, resulting in a clearer classification boundary. Even in the simpler binary classi- fication setting (EM-USER) our approach achieves an ap- proximately 3% improvement in Fl score compared to the state-of-the-ar method. However, for the multi-label dataset HPO-NEURO, the conversion process for class labels does not fully capture the relationships between subgraphs, limit- ing our advantage.
(a)
(b)
Figure 4: Sensitivity analysis on 7. Running SofIGGN and
SoftEIGNN on HPO-METAB and PPI-BP datasets.
Table 5: Average runtime per run of 1500 epochs in seconds over 10 runs
Method
PPI-BP
HPO-NEURO
HPO-METAK
EM-USKR
SSNP
130.4724110
15
162.34
158 158.29..143
IGNN-plain
439 29
1629 022988649..
1142,88
1386. 28
EIGNN-plain
114.35
275/48a140
185.82
176.99
ISNN
104.66:28144
128.26::451
160.83
135.29-31..0
We also observe that training GNNs implicit models naively for subgraph representation learning is challenging and unstable. However, our bilevel optimization algorithm enables stable training of implicit models while achieving performance comparable to SubGNN. Notably, SubGNN leverages subgraph-leve graphs to learn embeddings, effee- tively providing shortcuts in the original graph. The fact that soft implicit models achieve similar performance sug- gests that it successfully captures long-range dependencies without relying subgraph-level information, as intended.
perform a sensitivity analysis on 7 to evaluate its impact on our algorithm. We conduct experiments by running Soft- IGNN and SoftEIGNN on HPO-METAB and PPI-BP with varying 7. The results are presented in Figure
As observed, both methods exhibit poorer performance and higher variance y increases. A larger implies that the soft models become more similar to conventional models. This experiment suggests that strictly enforcing the fixed- point constraint may negatively impact the training process.
4.2. Ablation Study
Subgraph-level Information: In this section, we investi- gate whether subgraph-level information can aid classifica- tion and, if so, which types are most effective. We conduct experiments on HPO-METAB, considering four methods for constructing subgraph-level graphs: position, neighbor- hood, structure, and random. The first three methods have been introduced in Section 3.5, while the random method assigns edge weights following normal distribution.
4.3. Efficiency
We also measure the runtime of our method compared to baseline approaches. The results, presented in Table 5, con- firm that our algorithm introduces minimal overhead. This is expected, as the inner loop consists solely of fixed-point iterations, which do not require gradient computation.
Based these constructions, we define four model variants: ISNN-P, ISNN-N, ISNN-S, and ISNN-rand, correspond- ing to the position, neighborhood, structure, and random subgraph-level information, respectively. The results are summarized in Table While all models achieve perfor- mance comparable to state-of-ther ofette-art methods, the choice of subgraph construction does not appear to significantly im- pact the results. Surprisingly, all variants perform similarly, including the random approach.
5. Conclusion
We introduced ISNN, the first implicit model for subgraph representation learning, along with a provably convergent bilevel optimization algorithm for training. Additionally, we proposed graph-enhaneing framework learn more ex- pressive subgraph representations. This framework consists of three steps: 1) Pretrain the model to obtain subgraph em- beddings. 2) Construct a hybrid graph using the pretrained embeddings and label information. 3) Use the hybrid graph for subsequent training. As demonstrated in our experi- ments, this framework leads to significant improvements.
Sensitivity: In our optimization algorithm, the trade-off pa- rameter y in Equation (4) plays a crucial role in controlling the strength of the fixed-point constraint, In this section, we
8

---

Implicit Subgraph Neural Network
Acknowledgement
Hu, Q., Zhong, Y., and Yang. T. Multi-block min-max bilevel optimization with applications in multi-task deep auc maximization. Advances in Neural Information Pro- cessing Systems, 35:29552- 225552, 2022.
This work was supported in part by the NSF Cyber-training award 2320980, NSF SCH award 2306331, a start-up up from the University of Iowa, and the CDC under cooperative agreement U01-CK000594.
Huang, Z., Chung, W., and Chen, H. A graph model for e-commerce recommender systems. Journal of the Amer- ican Society for information science and technology, 55 (3):259-274, 2004.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Jacob, S. A., Louis, P., and Salehi-Abari, A. Stochastic sub- graph neighborhood pooling for subgraph classification. In Proceedings of the 32nd ACM international conference on information and knowledge management, pp. 3963- 3967, 2023.
References
Jang, H., Pai, S., Adhikari, B., and Pemmaraju, S. V. Risk- aware temporal cascade reconstruction to detect asymp- tomatic cases: For the edc mind healthcare network. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 240-249. IEEE, 2021.
Adhikari, B., Zhang, Y., Ramakrishnan, N., and Prakash, B. A. Sub2vec: Feature learning for subgraphs. In Ad- vances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part I1 22, pp- 170-182. Springer. 2018.
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. S. The web as a graph: Measure- ments, models, and methods. In Computing and Com- binatories: 5th Annual International Conference, CO- COON '99 Tokyo, Japan, July 26-28, 1999 Proceedings 5, pp. 1-17. 1 Springer, 1999.
Alsentzer, E., Finlayson, S., Li, M., and Zitnik, M. Sub- graph neural networks. Advances in Neural Information Processing Systems, 33:8017-8029, 2020.
Bai, S., Kolter, J. Z., and Koltun, V. Deep equilibrium mod- els. Advances neural information processing systems, 32, 2019.
Kumar. R., Raghavan, P.,, Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. Stochastic models for the web graph. In Proceedings 41st Annual Symposium on Foun- dations of Computer Science, pp. 57-65 IEEE, 2000.
Baker, J., Wang, Q., Hauck, D., and Wang, B. Implicit graph neural networks: monotone operator viewpoint. In International Conference on Machine Learning, pp. 1558. PMLR, 2023.
Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolu- tion: Densification and shrinking diameters. ACM trans- actions on Knowledge Discovery from Data (TKDD). 1 (1):2-es, 2007.
Chen, Q. Wang, Y., Wang, Y., Yang, J., and Lin, Z. Optimization-incuued graph implicit nonlinear diffusion. In International Conference Machine Learning, pp- 3648-3661. PMLR, 2022.
Liu, J., Kawaguchi, K., Hooi, B., Wang, Y., and Xiao, X. Eignn: Efficient infinite-depth graph neural networks. Advances in Neural Information Processing Systems, 34: 18762-18773, 2021a.
Cinelli, M., De Francisci Morales, G., Galeazzi, A., Quat- trociocchi, W., and Starnini, M. The echo chamber effect on social media. Proceedings of the National Academy of Sciences, 1 2880)332003301 18, 2021.
Liu, J., Hooi, B., Kawaguchi, K., and Xiao, X. Mgnni: Multiscale graph neural networks with implicit layers. Advances in Neural Information Processing Systems, 35: 11358-21377 2022.
El Ghaoui, L., Gu, F., Travacca, B., Askari, A., and Tsai, A. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930-958 2021.
Liu, R., Liu, X., Yuan, X., Zeng, S., and Zhang, J. A value- function-based interior-point method for non-convex bi- level optimization. In International conference on ma- chine learning, pp. 6882-6892. PMLR, 2021b.
Ghadimi, S. and Wang, M. Approximation methods for bilevel programming. arXiv preprint 80x.0:180..02246, 2018.
Liu, R., Liu, Y., Zeng, S., and Zhang, J. Towards gradient- based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662 8675, 2021c.
Gu, F., Chang, H., Zhu, W., Sojoudi, S., and El Ghaoui, L. Implicit graph neural networks. Advances in Neural Information Processing Systems, 33:1 1988--19955 2020.

---

Implicit Subgraph Neural Network
Nastase, V., Mihalcea, R., and Radev, D. R. survey of graphs in natural language processing. Natural Language Engineering, 21(5):665-698, 2015.
Wu, Z.,, Pan, S., Chen, F., Long, G., Zhang, C., and Philip,
S. Y. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning sys- tems, 32(1):4-24 2020.
Nouiched, M., Sanjabi, M., Huang, T., Lee, J. D., and Raza- viyayn, M. Solving class of non-convex min-ma max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L. Label- ing trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-90733 2021.
Park, J., Choo, J., and Park, J. Convergent graph solvers. arXiv preprint arXiv:2106.000 2000000000000000,, 2021.
Zhong, Y., Vu, H., Yang, T., and Adhikari, B. Efficient and effective implicit dynamic graph neural network. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4595-4600 2024.
Pedregosa, F. Hyperparameter optimization with approxi- mate gradient. In International conference muchine learning, pp. 737-746. PMLR, 2016.
Qiu, 7. Hu, Q., Zhong, Y., Zhang, I.., and Yang, T. Large-scale stochastic optimization of ndeg surrogates for deep learning with provable convergence. arXiv preprint arXiv:2202. 12183, 2022.
Shen, H. and Chen, On penalty-based bilevel gradient descent method. International Conference on Machine Learning, pp. 30992-31015. PMLR, 2023.
Sinha, A., Malo, P., and Deb, K. A review on bilevel opti- mization: From classical to evolutionary approaches and applications. IEEE transactions on evolutionary compu- tation, 22(2):276-29) 295, 2017.
Sitzmann, V. Martel, J., Bergman, A., Lindell, D., and Wetzstein, G. Implicit neural representations with peri- odic activation functions. Advances in neural information processing systems, 33:7462-7477 2020.
Song. J., Qu, X., Hu, Z., Li, Z., Gao, J., and Zhang, J. A subgraph-based knowledge reasoning method for collec- tive fraud detection in e-commerce, Neurocomputinng 461:587-597, 2021.
Tarzanagh, D. A., Li, M., Thrampoulidis, C., and Oymak, S. Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pp.
PMLR, 2022.
Ugander, J., Karrer, B., Backstrom, L.. and Marlow, The anatomy of the facebook social graph. arXiv preprint 1rXiv:1111.4503 2011.
Wang, F., Cui, P., Pei, J., Song, Y., and Zang, C. Recent advances on graph analytics and its applications in health- care. In Proceedings of the 26th ACM SIGKDD Inter- national Conference on Knowledge Discovery & Data Mining, pp. 3545-3546, 2020.
Wang, X. and Zhang, M. Glass: Gnn with labeling tricks for subgraph representation learning. In International Conference on Learning Representations, 2021.
10

---

Implicit Subgraph Neural Network
A. Ablation Study on SubGNN
Additionally, we conduct an experiment where we replace all subgraph information of position, neighborhood, and structure used by SubGNN with random. The results, presented in Table 6, follow a similar trend.
Table 6: Average Fl score of SubGNN with random subgraph-level graph
Method
PPI-BP
HPO-METAB HPO-NEURO
EM-USER
SubGNN SubGNN-rand
0.598 0.597
0.531 0.538
0.644
0.815
0.629
0.810
B. 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 such as GRASS and SSNP.
To further the comparison, we introduce additional label-aware methods:
class-rand: For each class, 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
Metric
ISNN-rand
ISNN-class-rand
ISNN-Star
ISNN
F1
0.589
0.672
0.707
0.731
AUROC
0,876
0.901
0.916
0.924
Table 7: Performance comparison of different subgraph-level graph construction methods on HPO-METAB.
The CSNN-class-rane 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 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.
C. Additional Hyperparameter Sensitivity Analysis
We further investigate the sensitivity of the hyperparameter ISNN. The results are presented follows
Gamma
Fl (10 Runs)
0.001
0.713 + 0.014
0.01
0.726 = 0.022
0.05
0.670 = 0.008
0.1
0.655 = 0.007
0.5
0.654 + 0.022
0.634 + 0.025
Table 8: F1 scores for different values of PPIBBP dataset.

---

Implicit Subgraph Neural Network
Gamma
F1 (10 Runs)
0.001
0.869 = 0.012
0.01
0.808 + 0.027
0.05
0.853 + 0.027
0.1
0.913 = 0.031
0.5
0.857 = 0.018
0.771 + 0.035
Table 9: scores for different values of on EM.USER dataset.
These results show that the best performance occurs when y between 0.01 and 0.1. For example, PPI BP achieves its best performance at ? 0.01, while IMUSRER peaks at 7 0.1. Gamma values outside this range lead worse performance. highlighting the importance of using moderate y.
D. Scalability of Our Method
The complexity of standard GCN given by:
O(n de + E..d)
(9)
where:
n. is the number of nodes,
F. is the number of edges, and
d the hidden dimension. For our method, the complexity becomes:
((n++)) - + k) d)
(10)
where:
is the number of subgraphs, and
A: the number of additional edges introduced.
Thus, the additional overhead introduced by ISNN is an additive term of:
O(s dl + +
(11)
Empirically, can be controlled to remain small, and 8, which is part of the input, is typically small in most practical subgraph learning tasks. Therefore, ISNN exhibits scalability similar to that of standard GCN in most practical scenarios.
E. Proof of Theorem 3.8
Based on the analysis framework from (Shen & Chen, 2023), we present the proof of Theorem 3.8. Fisrt, provide the convergence result on the inner loop.
Lemma E.1. (Convergence of fixed point) Suppose Assumption 3.5 and 3.4 hold. Given any x' X and Zi after running K steps of the inner updates, the 2' satisfies
< 2μ μ
12
22
g(xt 2%)
12

---

Implicit Subgraph Neural Network
Proof. The inner loop updates:
z h(x², Z.). By assumption, we know h(-) a p-contracctvve mapping
1 h(a², z )12 - |||| 2 - h(w" -11? S 1M ||Zg h(('', zb)1
Moreover, we know (7-Z"(x²)) || - --p Z h(x', Z}|l for any Z. Then, taking Z to be 2
1 12xx - h(x', 2x) v p K
24 1 - g(ø", 2b)
1/x - (2')11 -
1/6- h/x', 2b)113
(12)
Next, we will give proof to Theorem 3.8.
Proof. (of Theorem 3.8) In this proof, we denote (xx, Z). Then the update be written
z _+1 Proj(z* Ax"",, zxx)
where (z', Zxx) == + - Vg( (xx)). Based on the assumptions we made and Lemma A.5 from (Nouiched et al., 2019), function A, is Lipsschhht smooth with Ly LF + 72 + p4). Then the smoothness implies
Ly 1 - =11
1z <An(2") + (=4, 2t11 - 2²) +
2
<x,(2*) + (VA,(z' 2xx) 2 24) + 2n
|| 2012
+ (=" - VA, (z 2xx), z ++1 z²
(13)
The second inequality because we ensure 1) S 1. Now the problem bounding terms
For the 1+1 can be represented the minimizer of the following problem
1 -|== 21
min "iin(V,,('* 2)),2) #E2
2n
Then, according to the first order optimality,
(2A, ,2x) + -(2tt1 - =²², =² 50 Vx E Z
(2' 2 =2 < - 1 | - 20
(14)
11
Consider + by Young's 's inequality, we have
(VA)(z)) - VA,(2* 2%x, 2 ++1 x²)= $ (x' - VA,(2* 1..a,,2))10 21
1z 1+1 2012
(15)
4n
13

---

Implicit Subgraph Neural Network
then
VVga' 2²
Vg(x", Z )l(
L =xxl2
(By Assumption 3.4)
27 Lz
1 90(0", 2%
(By Lemma E.1)
2 Ti
$ (1 u)²
V29(2' 21111
(By Remark 3.6)
< 2 Ligh K
2
21
|
1/
(1 un²
11222
72
L 12 K
2 1||2
2²122 + 21
(1 11)
172
1
13.1
241
=21
(16)
81p2
2/72
The last inequality is because we choose K = max (-2log,
/Bbg.
-2 -2 I-p ). Follow the steps after (B.9) in (Shen
Vint
I-#
Chen, 2023), we can obtain the bound.
2 (x')
|
+ 101 L
(17)
7
14


Reviews:
[{"review_id": "pCWsenOkf5", "reviewer": "Reviewer_Qr7p", "summary": "The paper introduces the Implicit Subgraph Neural Network (ISNN), an innovative approach designed to enhance subgraph representation learning. ISNN is the first to use implicit neural network models explicitly for subgraphs, addressing limitations in existing methods, particularly concerning capturing long-range dependencies between subgraphs. The authors formulate subgraph representation learning as a bilevel optimization problem, providing theoretical guarantees for convergence and introducing a computationally efficient training algorithm. Experimental results demonstrate that ISNN significantly outperforms existing state-of-the-art approaches across multiple benchmark datasets.\n\n---\n\n(+) The introduction of implicit neural networks for subgraph representation is original and fills a gap in existing subgraph learning methods.\n\n(+) The paper provides solid theoretical backing for the convergence of their proposed bilevel optimization method.\n\n(+) Extensive experiments on multiple datasets clearly show superior performance in terms of Micro-F1 and AUROC scores compared to existing baselines.\n\n(+) The proposed method demonstrates practical runtime efficiency, addressing scalability concerns.\n\n---\n\n(-) Limited sensitivity analysis and ablation studies on certain critical hyperparameters, potentially affecting the interpretability and broader applicability of the approach.\n\n(-) The effectiveness of various proposed methods for constructing the subgraph-level graph is not deeply explored, as shown by their similar performances, even when random edges are introduced.\n\n(-) The reliance on pretraining for constructing subgraph-level graphs could limit applicability in dynamic or real-time settings.\n\n---\n\n## update after rebuttal\n\nThanks to the authors for the detailed and clear rebuttal. The new experiments on label-aware subgraph construction are helpful and support your design choices well. The gamma sensitivity results are also useful and show reasonable stability.\n\nI understand the current limitations around dynamic graphs, and I agree it’s a valuable direction for future work. Overall, your responses strengthen the paper, and I still lean toward a weak accept (solid contribution with room to grow).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable feedback. Our responses are as follows:\n\n---\n\n## Sensitivity to Subgraph-Level Graph Construction Methods\n\nIn 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.\n\nTo further the comparison, we introduce additional label-aware methods:\n- **class-rand:** For each class, we randomly connect *k* pairs of training supernodes.\n- **Star:** For each class, we select a centroid supernode and connect it with all other supernodes within that class.\n\n\n### Experimental Results on HPO-METAB\n\n| Metric    | ISNN-rand | ISNN-class-rand | ISNN-Star | ISNN  |\n|-----------|----------|--------------|---------|-------|\n| **F1**    | 0.589     | 0.672           | 0.707     | 0.731 |\n| **AUROC** | 0.876     | 0.901           | 0.916     | 0.924 |\n\nThe **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.\n\n\n\n---\n\n\n## Additional Hyperparameter Sensitivity Analysis\n\nWe further investigate the sensitivity of hyperparameter **gamma** on ISNN.\n\n### Ablation Results on Gamma for PPI_BP\n\n| Gamma | F1 (10 Runs)    |\n|-------|-----------------|\n| 0.001 | 0.713 ± 0.014   |\n| 0.01  | 0.726 ± 0.022   |\n| 0.05  | 0.670 ± 0.008   |\n| 0.1   | 0.655 ± 0.007   |\n| 0.5   | 0.654 ± 0.022   |\n| 1     | 0.634 ± 0.025   |\n\n### Ablation Results on Gamma for EM_USER\n\n| Gamma | F1 (10 Runs)    |\n|-------|-----------------|\n| 0.001 | 0.869 ± 0.012   |\n| 0.01  | 0.808 ± 0.027   |\n| 0.05  | 0.853 ± 0.027   |\n| 0.1   | 0.913 ± 0.031   |\n| 0.5   | 0.857 ± 0.018   |\n| 1     | 0.771 ± 0.035   |\n\nThese 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.\n\n\n---\n\n## Applicability and Adaptations for Dynamic or Streaming Graph Settings\n\n**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.\n\n---\n\n## Justification for Label-aware Subgraph-Level Information Versus Random Edge Assignment\n\nOur 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.\n\nTo 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.\n\n---\n\n## Scalability of Our Method\n\nThe complexity of a standard GCN is given by: \n\n$$ O(n \\cdot d^2 + E \\cdot d) $$\n\nwhere:\n- $n$ is the number of nodes,\n- $E$ is the number of edges, and\n- $d$ is the hidden dimension.\n\nFor our method, the complexity becomes:\n\n$$ O((n+s) \\cdot d^2 + (E+k) \\cdot d) $$\n\nwhere:\n- $s$ is the number of subgraphs, and\n- $k$ is the number of additional edges introduced.\n\nThus, the additional overhead introduced by ISNN is an additive term of:\n\n$$ O(s \\cdot d^2 + k \\cdot d) $$\n\nEmpirically, $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.\n\n---\n\nWe hope these responses address your concerns and clarify the contributions and design choices in our work.", "claims_and_evidence": "The claims made regarding performance improvements and computational efficiency are well-supported through clear experimental evidence and theoretical analysis. However, the claims regarding the benefit of explicitly constructed subgraph-level information are less convincing, as experiments suggest similar performance even with random graph construction.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the subgraph classification problem. Utilizing standard benchmarks (PPI-BP, HPO-METAB, HPO-NEURO, and EM-USER) aligns well with community standards, providing convincing comparisons against established baselines.", "theoretical_claims": "The correctness of the theoretical claims has been checked, particularly regarding the convergence analysis (Theorem 3.8 and Lemma B.1). No immediate issues were found, and the proofs appear sound and complete.", "experimental_designs_or_analyses": "The experimental design is robust, evaluating performance on several real-world datasets and comparing against multiple baselines. The analyses are thorough and valid, with clear performance metrics and adequate runtime comparisons.", "relation_to_broader_scientific_literature": "The paper appropriately situates its contributions within existing literature on subgraph neural networks and implicit models. It effectively highlights shortcomings in previous models such as SubGNN, GLASS, and SSNP, clearly articulating how ISNN extends beyond these methods to address specific limitations in capturing subgraph-level information and long-range dependencies.", "essential_references_not_discussed": "The paper extensively covers relevant literature. However, it could benefit from discussing more works on dynamic or evolving graph scenarios (if available) since the current formulation and pretraining step may be restrictive in such contexts.", "other_strengths_and_weaknesses": "(+) Strong motivation clearly identifying practical limitations of existing subgraph models.\n\n(+) Clear visualization and description of methodological innovations.\n\n(+) Practical significance and clear demonstration of superior performance.\n\n(-) Limited investigation of the impacts of graph construction techniques.\n\n(-) Potential issues in scalability and practicality for real-time updates due to reliance on pretraining.", "other_comments_or_suggestions": "- Additional discussion on the scalability of the model to large-scale dynamic networks would strengthen the paper.\n\n- Clarification on hyperparameter sensitivity analysis, especially regarding γ, could enhance the practical utility of the paper.", "questions_for_authors": "1. How sensitive is ISNN to changes in subgraph-level graph construction methods, beyond the initial random comparison?\n\n2. Can you elaborate on the potential applicability or adaptations required for ISNN in dynamic or streaming graph settings?\n\n3. Could you provide further justification or examples where explicit subgraph-level information significantly impacts performance compared to random edge assignment?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zZsUG1CLfg", "reviewer": "Reviewer_hQDC", "summary": "This paper combines the information from both subgraphs and nodes to form a hybrid graph to tackle the subgraph-level graph learning problem.  Instead of directly training a GNN on the hybrid graph, it uses implicit GNN combined with a bilevel optimization way to enhance model performance.  Convergency guarantee is provided for this method.  Experiment results show that this method achieved good performance on the evaluated datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your valuable feedback. Our responses are as follows:\n\n## Motivation\n\nWhile 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.\n\n---\n\n### Mistake in Figure\n\nWe thank the reviewer for pointing out this mistake. We will correct it.\n\n---\n\n### Connection between Max-Zero-One Label Trick and Weisfeiler-Leman Test\n\nMax-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.\n\n---\n\n[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.\n\n---\n\nWe hope these responses address your concerns and clarify the contributions and design choices in our work.", "claims_and_evidence": "The claim that directly train a implicit GNN on the hybrid graph leads to poor performance is underpinned by the experiments.", "methods_and_evaluation_criteria": "I am not familiar with subgraph-level graph learning tasks, so I am not sure whether these datasets are good.", "theoretical_claims": "I checked the proof in the main paper.", "experimental_designs_or_analyses": "The experiment looks valid to me.", "relation_to_broader_scientific_literature": "This paper is closely related to a broader scope of implicit and unfolded GNNs, where bilevel optimizations are commonly used.", "essential_references_not_discussed": "I am not aware of such.", "other_strengths_and_weaknesses": "The motivation is not clear to me.  I would appreciate it if the author can elucidate why subgraph neural networks are important.", "other_comments_or_suggestions": "In Fig 3 (b), the (1) under (S2) should be (2), and its children should be (1), (3), (6).", "questions_for_authors": "What is the connection between max-zero-one label trick and Weisfeiler-Leman test?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1lAsVrejCk", "reviewer": "Reviewer_Red8", "summary": "This paper introduced ISNN, the first implicit model for subgraph representation learning, along with a provably convergent bilevel optimization algorithm for training. The proposed ISNN also integrates label-aware subgraph-level information. This paper converts the fixed-point iteration into bi-level optimization to improve the stability of subgraph-level learning tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s detailed feedback. Below are our responses addressing each concern:\n\n---\n\n## Logic and Motivation Problems\n\nIn 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.\n\n---\n\n## Novelty and Contribution of the Paper\n\nWhile our method builds on implicit graph neural networks, our contribution lies in:\n1. **Novel Extensions:** Developing new extensions to these models specifically for subgraph learning.\n2. **Label-Aware Integration:** Integrating label-aware subgraph-level information via a novel hybrid graph framework.\n3. **Bilevel Optimization Formulation:** Formulating the training as a bilevel optimization problem with convergence guarantees.\n\nThese 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.\n\n---\n\n## Motivation for Using Bi-level Optimization\n\nThe 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.\n\n---\n\n## Explanation and Clarification of Symbols\n\nWe will check and revise the manuscript to ensure that all symbols are clearly defined.\n\n---\n\n## Convergence\n\nBoth 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:\n\n- **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.\n  \n- **Backward Gradient Computation:** Implicit differentiation involves computing backward gradients through an additional fixed-point iteration, which adds extra computational overhead compared to bilevel optimization.\n\n---\n\nWe hope these responses address your concerns and clarify the contributions in our work.", "claims_and_evidence": "The author's statement is somewhat convincing in the paper, but the plausibility and reproducibility of the experimental results need to be further examined.", "methods_and_evaluation_criteria": "The proposed methodology has research implications for the study of the issue at hand.", "theoretical_claims": "I think the authors' proof of Theory 3.8 is essentially correct.", "experimental_designs_or_analyses": "The experiment is generally correct, see weekness for details.", "relation_to_broader_scientific_literature": "I finished reading this paper and for the time being I did not find the main contribution of the paper to be relevant to the wider scientific literature.", "essential_references_not_discussed": "I don't think there are any important references that have not been discussed.", "other_strengths_and_weaknesses": "Strengths：\n1.This paper is novel and a good target for research.\n2.The article is overall easy to read, although there are some logic problems.\n\nWeakness:\n1. The writing logic of the paper is somewhat lacking and lacks clear motivation. \n2. This paper uses implicit graph neural networks to solve subgraph learning tasks, but lacks sufficient novelty and contribution. \n3. Although the authors give an experimental motivation for using bi-level optimization, the experimental results indicate that smaller gamma values may also lead to instability. Therefore, I still doubt the validity of this motivation and whether the author can provide more rigorous theoretical analysis.\n4. Some symbols in this paper lack sufficient explanation and clarification.\n5. It seems feasible to convert the fixed-point iteration into bi-level optimization, and I would like to know the difference in the final convergence between these two methods.", "other_comments_or_suggestions": "For more information, see Weaknesses.", "questions_for_authors": "For more information, see Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nr1ZBj7gxT", "reviewer": "Reviewer_JyUo", "summary": "This paper proposes a bi-level optimization framework for subgraph-level predictive tasks, where the outer level is to minimize the subgraph-level prediction loss, and the inner-level is to enforce the fixed-point conditions of the implicit representation of the subgraphs, so that they don't have to rely on rigid subgraph definitions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's feedback.\n\n---\n\n### Time Consumption\n\nYes, 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.\n\n| Method | Preprocessing Time (s) | Training Time (s) | Total Time (s) |\n|--------|------------------------|-------------------|----------------|\n| ISNN  | 248.43                 | 807.69            | 1056.12        |\n| EIGNN   | 1201.84                | 956.54            | 2158.39        |\n\n---\n\n### Compare with GEQ\n\nThanks 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the assumptions and conclusions of the theoretical claims about all the theorems. The assumption to ensure convergence is the general assumption made in implicit GNNs. I didn't check the detailed proof of Thm. 3.8, but the conclusion intuitively makes sense.", "experimental_designs_or_analyses": "I checked the comparison on subgraph classification datasets, and also the ablation studies about the subgraph-level Information and sensitivity analysis. Both looks good to me except the Sec 4.3 about the efficiency analysis. \nAs far as I know, EIGNN takes a nonnegligible amount of time for preprocessing. Could you please also specify the time consumption, besides average runtime per epoch?", "relation_to_broader_scientific_literature": "This paper is a direct application of graph implicit models and bilevel optimization, where the latter enables the usage of the former to flexibly deal with the subgraph representation learning problem. This is a novel strategy since it is the first work to apply GIM to subgraph learning and benefits from the long-range dependencies and flexible problem design.", "essential_references_not_discussed": "Could you please compare with GEQ (Efficient and scalable implicit graph neural networks with virtual equilibrium, https://drive.google.com/file/d/1u2zJ_LJyIEFOjatUiT2gG1QXVLkTY3_y/view?pli=1)? \nIt is not for subgraph learning tasks, but it also formulates node classification as a bilevel optimization problem and develops a provably convergent algorithm and \"replace gradient descent in the inner loop with fixed-point iteration\". Can this framework be adapted to subgraph learning also?", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could you please resolve my questions in the Experimental Designs Or Analyses and Essential References Not Discussed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes an implicit neural network model for subgraph representation learning. Model training is formulated as a bilevel optimization problem and an algorithm is provided to find a solution to the optimization problem.

This paper was reviewed by four expert reviewers. The reviewers raised concerns about the scalability of the proposed method, the clarity of the presentation, the method's sensitivity to the graph construction method, and missing baselines and comparisons. Some reviewers also raised concerns about the novelty of the proposed model. After rebuttal, all the reviewers are positive about this paper. Overall, I personally agree with the reviewers that this work is a direct application of well-established techniques to the problem of subgraph representation learning. Although there remains room for improvements, I also agree that the contributions are solid and interesting for the community, and therefore I recommend acceptance. I strongly encourage the authors to revise the paper and improve the writing taking into account the detailed comments in the reviews.
Decision: Accept (poster)