GLASS: GNN with Labeling Tricks for Subgraph Representation Learning
Authors: Xiyuan Wang
Muhan Zhang
Venue: ICLR 2022 Poster (2022)

Abstract: Despite the remarkable achievements of Graph Neural Networks (GNNs) on graph representation learning, few works have tried to use them to predict properties of subgraphs in the whole graph. The existing state-of-the-art method SubGNN introduces an overly complicated subgraph-level GNN model which synthesizes three artificial channels each of which has two carefully designed subgraph-level message passing modules, yet only slightly outperforms a plain GNN which performs node-level message passing and then pools node embeddings within the subgraph. By analyzing SubGNN and plain GNNs, we find that the key for subgraph representation learning might be to distinguish nodes inside and outside the subgraph. With this insight, we propose an expressive and scalable labeling trick, namely max-zero-one, to enhance plain GNNs for subgraph tasks. The resulting model is called GLASS (GNN with LAbeling trickS for Subgraph). We theoretically characterize GLASS's expressive power. Compared with SubGNN, GLASS is more expressive, more scalable, and easier to implement. Experiments on eight benchmark datasets show that GLASS outperforms the strongest baseline by $14.8\%$ on average. And ablation analysis shows that our max-zero-one labeling trick can boost the performance of a plain GNN by up to $105\%$ in maximum, which illustrates the effectiveness of labeling trick on subgraph tasks. Furthermore, training a GLASS model only takes $37\%$ time needed for a SubGNN on average. 

Published as a conference paper at ICLR 2022
GLASS: GNN WITH LABELING TRICKS FOR SUBGRAPH REPRESENTATION LEARNING
Xiyuan Wang'
Muhan Zhang!
Institttee for Artificial Intelligence, Peking University BBeijing Institute for General Artificial Intelligence (wangxi yuan, muhan @pku. edu.cn cn
ABSTRACT
Despite the remarkable achievements of Graph Neural Networks (GNNs) on graph representation learning, few works have tried to use them to predict properties of subgraphs in the whole graph. The existing state-of-the-ard method SubGNN introduces an overly complicated subgraph-level GNN model which synthesizes three artificial channels each of which has two carefully designed subgraph-level message passing modules, yet only slightly outperforms a plain GNN which per- forms node-level message passing and then pools node embeddings within the subgraph. By analyzing SubGNN and plain GNNs, we find that the key for sub- graph representation learning might be to distinguish nodes inside and outside the subgraph. With this insight, we propose an expressive and scalable labeling trick, namely max-zero-one, to enhance plain GNNs for subgraph tasks. The re- sulting model is called GLASS (GNN with LAbeling trickS for Subgraph). We theoretically characterize GLASS's expressive power. Compared with SubGNN, GLASS is more expressive, more scalable, and easier to implement. Experiments on eight benchmark datasets show that GLASS outperforms the strongest baseline by 14.8% on average. And ablation analysis shows that our max-zero-one label- ing trick can boost the performance of a plain GNN by up to 105% in maximum, which illustrates the effectiveness of labeling trick on subgraph tasks. Further- more, training GLASS model only takes 37% time needed for SubGNN on average.
INTRODUCTION
Graph is natural tool for modeling objects with complex internal relationships, which is widely used in fields such as natural language processing (Yao et al. 2019). biology (Fout et al. 2017), and social network (Chen et al.] 2018). Among the various graph representation learning methods, GNN has achieved state-of-the-an art performance on almost all sorts of tasks. Existing GNNs are mainly designed for node (Dabhi & Parmar 2020 Chen et al. 2020), edge (Singh et al. 2021 Galkin et al.,
2021) and whole graph (Ying et al. 2021b Yang et al. 2020) property prediction tasks. An ordinary GNN produces embeddings of a node by aggregating the features from the imulti-hop neighbors of the node, which is equivalent to encoding a be used to predict node properties directly. As for edge and graph tasks, pooling the embeddings of nodes related to the structure is a prevailing method.
(BFS) tree rooted in the node (Xu
et al. 2019). Such embeddings
Though node, edge, and graph tasks are the three most common graph representation learning tasks, properties of subgraphs are also worth predicting. Take company structure network as an example. The nodes are employees, and the edges between them represent cooperation relations. We want to predict the performance of a department, in other words, a subgraph in the network. Obviously, on the one hand, we need to consider the internal organization (such as the collaboration within the department and the competence of individual employees). If the structure is disorganized or the employees are incompetent, we can expect the department to perform poorly. On the other hand, the external information of the department also deserves attention. A department is less likely to be productive if the company as a whole is facing bankrupicy. contrast, close cooperation with
"Corresponding author: Muhan Zhang

---

Published as a conference paper at ICLR 2022
other remarkable departments can be a sign of good performance. As illustrated by this example, subgraph task is to predict the property of subgraphs in the whole graph. It needs to consider the topology both inside and outside the subgraph. It may also need to combine multi-level information of nodes, edges, higher-order substructures, and even the whole graph. Thus, a very general model is needed, and natural idea is to extend ordinary GNNs to subgraph tasks. Figure [eft shows typical subgraph to predict. The target subgraph S is embedded in the whole graph and may have multiple connected components, and our task produce subgraph representation, which can be used to predict properties of S.
However, in experiments, we find that SubGNN (Alsentzer et al. 2020), the current state-of-the-an method for subgraph tasks, only slightly outperforms plain GNNs which directly pool node embed- dings within the subgraph as the subgraph representation. SubGNN replaces the message passing between nodes with subgraph-level message passing framework and designs three channels. Each channel is further divided into an internal and a border module to aggregate subgraph features sep- arately. Despite its performance, SubGNN is both space and time-consuming due to its lengthy precomputation. Furthermore, the units of message passing are subgraph patches sampled from the whole graph randomly, and there is no guarantee of the optimality of the samples, leading to high variance in performance and dubious robustness. Last but not least, the framework of SubGNN is overly complicated-min many of its designs seem ad hoc suboptimal, resulting in poor compatibility with recent advances in GNN research. Nevertheless, by comparing SubGNN with plain GNNs, we find that differentiating internal and external topology crucial for subgraph tasks. Inspired by this insight, we introduce a -ee--zeo--nne labeling trick (Zhang et al. 2021). which explicitly marks whether node is within a subgraph or not, to augment GNNs and show that plain GNNs with this labeling trick are superior to SubGNN.
Here we give brief introduction to labeling trick. First proposed by Zhang al. 2021 J. labeling trick is a theoretical framework for using graph neural networks to produce mulu--ooe representa- tions, which show that producing expressive representations for high-order structures needs to cap- ture the interaction among the different nodes within the structure. This theory shows that directly aggregating node representations to represent high-order structures is not expressive enough, and labeling trick can aid this problem. In implementation, a labeling trick assigns label to each node and combines the node features and the labels as the new input node features to GNNs. Labeling trick has achieved great successes on graph representation learning in previous works. For example, the state-of-the-ee with a carefully designed labeling trick. IDGNN (You et al. [202] 1) differentiates one center node from others, and Distance Encoding (Li et al., 2020) uses the distance to the target nodes to label other nodes, both of which gain improved performance on node, edge, and graph tasks. In this work, we for the first time introduce labeling trick to subgraph problems, and design an expressive and scalable labeling trick called max zero-one. Max-zero-one is the first labeling trick that enables jointly predicting batch of structures within the same graph.
link prediction method SEAL (Zhang & Chen 2018) gains better performance
Present work We propose GLASS (GNN with LAbeling trickS for Subgraph), a novel and simple graph neural network for subgraph tasks. To the best of our knowledge, GLASS is the first sub- graph representation learning method using the ordinary message passing framework and labeling trick. GLASS is more scalable, more expressive, and easier to implement and extend than the ex- isting state-of-the-art method. Theoretically, we prove that GLASS is more expressive than plain GNNs, and can capture range of important subgraph properties defined in SubGNN like density, cut ratio, border, positions, etc. Experiments on eight datasets show that GLASS achieves new state-of-the--ar performance. On synthetic datasets, GLASS with single message passing layer beats SubGNN with three carefully designed channels by up to 48.6% 6%. illustrating the expressive power of node-level message passing augmented by labeling trick for subgraph tasks. On real-world datasets, GLASS also outperforms the strongest baseline SubGNN by up to 14.3%. Moreover, train- ing GLASS model on average only takes 37% time needed to train SubGNN. With the strong performance of GLASS, our work proves the effectiveness of labeling trick on subgraph tasks.
2 RELATED WORK
Subgraph Representation Learning. Though some works have utilized subgraphs to perform
other graph representation tasks (Sun et al. 2021 Wang et al. 202T Huang & Zitnik 2020 or
2

---

Published as a conference paper at ICLR 2022
SubGNN
Sample Patches
Patch-Lene Message Passing
Pool Components
Classifier
or Regressor
GLASS
Label Nodes
Node- Message Passing Pool Nodes
Figure 1: Subgraph tasks are to predict the properties of subgraphs in the whole graph. S (green) the subgraph we want to predict. SubGNN samples anchor patches (grey), aggregates features of anchor patches to connected components of the subgraph through six independent channels (red, blue, and yellow), and pools component embeddings as the subgraph representation. GLASS labels nodes, passes messages between them, and pools node embeddings as the subgraph representation.
studied some specific tasks involving subgraphs (Bordes et al. 2014 Meng et al. 2018 Ying al., 2020), few works have studied the general subgraph representation learning problem. Alsentzer et al. (2020) introduced the problem formally and proposed SubGNN (Alsentzer et al. 2222)) the current state-of-the-art method, which samples patches from the whole graph and aggregates their features produce subgraph representations. Before that, Sub2Vec (Adhikari al.. 2018), designed for graph classification and community detection, samples random walks in subgraphs and feeds them the language model Paragraph2vec (Le & Mikolov 2014) to generate embeddings for subgraphs.
Labeling trick. SEAL (Zhang & Chen 2018) first introduces labeling trick to graph representation learning and applies them link prediction. IDGNN (You et. 202T) uses different message pass- ing parameters for target node and the other nodes, which is essentially labeling trick assigning different labels the target node and others. Distance Encoding (Li et al. 2020) uses distances to target nodes as node labels. /Zhang et al. (202T) give theoretical analysis of labeling trick and prove that they can produce the most expressive representations for substructures with a GNN ex- pressive enough. These previous methods ignore subgraph tasks and have poor scalability due to the relabeling for every target substructure to predict. Besides these deterministic labeling methods, IGIN (Sato et al. (021)) assigns random vector to each nodes its label in each forward process. Similarly, GNN- (Abboud et al., (02T)) randomly initializes node embeddings and can approx- imate any functions mapping graphs to real numbers. Despite the theoretical power, random labels suffer from slow convergence and subpar performance. We also discuss other structural encoding methods in Appendix A.I] Our GLASS is application of labeling trick to subgraph tasks. Its success verifies the theory of using GNNs and labeling trick to produce multi-node representations.
PRELIMINARIES
Let G - (V, X) denote graph with finite node set V = {1, ..., an edge set V x and node feature matrix X, whose 1th row X; is the feature of node i. N(v) refers to the set of nodes adjacent to node v. S = (Vs, Es, Xs) is a subgraph of & if Vs S V and Es S (V x Vs) nE and Xs is the stack of the rows of X corresponding nodes in Vs. In this paper, focus induced subgraphs, whose edge set Es = (Vs x Vs) E. Let C g donate that S is a subgraph in G.
Problem (Subgraph Representation and Property Prediction). Given the whole graph g its subgraphs = (S1, S2,...,,,, and their target properties T = {ts, ts...., ). the goal is to leamn representation vector hss that can be used to predict ts, of S,.
Plain GNN for Subgraph Tasks, Message passing neural network (MPNN) Gilmer et al. 2017) common framework of GNNs. A message passing layer aggregates embeddings from neighbors
3

---

Published as a conference paper at ICLR 2022
Table Six properties in SubGNN, in graph & is target subgraph.
channel
Distance between connected components
Distance between S and the rest of Identity of border nodes Border connectivity
N
Identity of internal nodes Internal connectivity
Table 2: Implementation of each channel in SubGNN for a target subgraph component Ste), N& (S(c)) means the union of the k-hop neighborhood nodes in S(s), rw, refers to random walk in anchor patch A and rwg means random walk in the border of A. SubGNN feeds the sampled node feature sequences into a bidirectional LSTM. dtw(S(o) .A) is the normalized dynamic time warping measure (Mueen & Keogh 2016) between the sorted node degree sequence of ( and A. d(S()) A) is the average shortest path between A and nodes in S(e).
channel property patch sampler
patch representation
similarity
node in S
P
node embedding
1/(d(s(O),A) +1
B
node out of S
node S(c)
N
node embedding
B
node (x()
1/(d(s(C), ,A) 1)
S
I
connected components
rw + LSTM
1/(dtw(S(C), + 1)
B
rw LSTM
to update the representation of a node. The 1tth message passing layer can be formulated as follows.
a (k) AGGREGATE (R) ((h E N(o))),
h (k) COMBINE (h(*-1), (a)))
where (x( is the embedding of node u at the h layer and h X,,
The embeddings at the last layer can be used to predict node properties. As for edge or graph tasks, pooling the multiset of embeddings of nodes belonging to the edge or within the graph is a widely used method. Naturally, be learned by pooling the embeddings nodes within the subgraph as follows, which we call a plain GNN.
extend it to subgraphs, and the representation of subgraph S can
hs = READOUT((A,.u (.))).
(3)
A COMPARISON BETWEEN SUBGNN AND PLAIN GNNS
In this section, we first illustrate the failure of plain GNNs on some simple subgraph tasks. Then, to find the reason for the deficiency, we dive into the state-of teee-ofthhearr art subgraph representation learning method, SubGNN, and compare with plain GNNs. We find that the key advantage of SubGNN comes from dealing with internal and border topology separately, which motivates our GLASS.
Though numerous works have proven plain GNNs' graph representation learning ability, we find that they can fail in some simple subgraph representation situations. For example, the representations of two different subgraphs and S in Figure 2 must be the same as all nodes in the graph have identical neighborhood structures and thus equal embeddings from plain GNNs. The failure differentiate and S' suggests the limitation of using plain GNNs for subgraph representation learning.
Unlike plain GNNs. the existing state-of-ther ing architecture. SubGNN introduces three channels, namely position, neighborhood, and structure (P, N, S for short), and learns each channel's internal and border (I, B for short) properties sepa- rately. Table defines the six properties. They claim that these six properties are key for learning powerful subgraph representations. To capture channel for a target subgraph S, SubGNN samples anchor patches &S = (A("), ..., A (ma)) and then learns representations each connected compo- nent in S by propagating messages from the anchor patches to components of S. See the top half of
method, SubGNN, designs special message pass-
4

---

Published as a conference paper at ICLR 2022
Plain GNNS cammot di iiferenntatee and because of identical all
Direrrmiiaton of internal nodes helps.
Figure 2: Plain GNNs are not enough capture subgraph topology. For example, given graph G with empty node feature, GNN representations of subgraph S and S' must be the same because the homogeneous rooted subtree structures, though these two subgraphs are non-isomorphic. However, differentiation of nodes in and outside helps GNNs generate different embeddings for S and S'. Initially, GNNs can only learn that each node in S and S' has four neighbors. However, with the differentiation, GNNs can learn that all nodes in S have two neighbors inside and two outside, while in S", two nodes, 3 and 8, have one neighbor inside and three outside.
Figure The hthh subgraph-Ievel message passing layer for channel can be formulated follows.
(t,) E , A.)gA, h (k) oW, (ai,st,, h ()
(4)
(,5(0
(5)
where g(e) is the td component of the target subgraph S, (:(S()), is similarity function be- tween g(e) and an anchor patch A₁ 9A, is a (pretrained) representation of patch A,, h (,Sie) is the representation of the component S(c) channel at the 4thh layer, and a is an activation function and W, is a weight matrix. The implementation of each channel in SubGNN can be found in Ta- 2 The representation of the whole subgraph is the sum of the representations of all components. We call the above formulation subgraph-level message passing distinguish from the node-level message passing defined in Equations ( and (2).
In general, SubGNN pretrains plain GNN produce node embeddings, pools them produce patch embeddings and then smoothes the embeddings of the target component with the embeddings of patches close or structurally similar to the target component. Through the carefully designed subgraph-level message passing layer for each of the six properties separately, SubGNN can capture the internal structure, border connectivity, and position relative the rest of the graph. Looking back on plain GNNs. we wonder why they are inferior to SubGNN. By encoding the topology of BFS trees, plain GNNs can easily capture (multi-hop) neighborhood and the position of nodes the whole graph. However, from the example in Figure 2 we can see that plain GNNs cannot represent internal structure and border comnectivity well, as they cannot tell whether a neighbor of a node in the subgraph or in the rest of the graph. Therefore, the missing part of plain GNNs from SubGNN is that SubGNN passes internal and border messages separately, while plain GNNs cannot distinguish nodes in and outside the target subgraph when passing messages between nodes.
GLASS: GNNS WITH LABELING TRICKS FOR SUBGRAPH
Inspired by SubGNN, we aim to differentiate nodes in the target subgraphs from the rest of the graph and see how such differentiation can improve plain GNNs. Still using S and S' in Figure a an example, the initially identical rooted trees become different when we differentiate internal and external nodes for each subgraph (Figure right), leading to different node embeddings between the two subgraphs. Therefore, GNNs can differentiate these two subgraphs after the pooling. Inspired by this insight, propose GLASS, which uses labeling trick enhance plain GNNs.
5

---

Published as a conference paper at ICLR 2022
5.1 THE ZERO-ONE LABELING TRICK FOR SUBGRAPHS
Introduced by Zhang et al. (2021), zero-one labeling trick is general labeling trick for all node-sets. We restate for subgraphs.
Definition 1. Given a graph 9 and subgraph S in G. the zero-one label of node is
[1 if Vs 0 if fo4% Vs
((5)
(6)
GLASS a plain GNN augmented by the zero-one labeling trick. It assigns nodes in and outside the subgraph different labels and enhances the hidden representation of node in each message-pass passsnn layer with its zero-one label. Finally, the representation of is produced by pooling the embeddings of nodes in S. The bottom half of Figure iillustrates the GLASS framework.
The following proposition shows that GLASS more expressive than plain GNNs.
Proposition 1. Given graph and subgraphs and G, if plain GNNs can distinguish them, GLASS can also produce different representations of S and S'. However, there exist puirs of subgraphs that plain GNNs cannot differentiate while GLASS can
In addition, we prove that GLASS can precisely predict two critical metrics used SubGNN to evaluate a model's expressive power for subgraph representation learning, namely cut ratio and density, while plain GNNs cannot.
Theorem 1. Given any graph G, there exists a GLASS model that can precisely predict the density and cut ratio of any subgraph in G.
Now we have seen that GLASS is a more powerful model than plain GNNs for subgraph representa- tion learning. We next compare GLASS with the state-of-the-art model, SubGNN, and analyze their expressive power differences. We show that GLASS can represent all the channels of SubGNN.
Proposition 2. GLASS can cover the six properties of SubGNN defined in Table 7
The concrete analysis and proofs of Proposition 2 can be found in Appendix A 4
In summary,
GLASS can learn all properties designed by SubGNN while using node-level message passing only.
we further characterize the expressive power of GLASS using the theoretical framework introduced by Zhang al.] (202T). We prove that (1) With a GNN expressive enough, GLASS can learn the most expressive structural representations for subgraphs, thus enabling learn- ing any functions over subgraphs (in theory can solve any tasks over subgraphs). (2) However, expressive power of practical GNNs is usually bounded by the 1-dimensional SesfeillrrLehmaal (1-WL) test (Weisfeiler & Leman 1968). We prove that the zero-one labeling trick can also boost those GNNs powerful as 1-WL. for subgraph tasks.
In Appendix A.5
5.2 THE MAX MAX-ZERO-O0 ZERO-ONROOON -ON LABELING TRICK
Though the zero-one labeling trick can boost GNNs, it makes batch training hard, as the input node feature vectors change with different target subgraphs. Time-consuming message passing needs to be done separately for each target subgraph, resulting in higher time complexity than plain GNNs.
To alleviate this issue, we can combine the labels of different target subgraphs and produce their representations in a single forward process. More specifically, we can jointly label batch of sub- graphs within the graph, perform message passing the whole graph, and then pool individual node embeddings to produce multiple subgraph representations at the same time. This enables learning batch of subgraph representations from the same labeled graph instead of learning one subgraph representation from one labeled graph.
However, node labels might conflict with each other for different subgraphs, resulting in inconsisten- cies with the canonical way. Nevertheless, we argue that such processing has a controllable effect on the final results. On the one hand, ordinary k-layer GNNs only encode neighbors within & hops, the representation will not change the node labels of neighbors within & hops stay the same. We expect the errors to be negligible if the change in node labels is distant from the target subgraph.

---

Published as a conference paper at ICLR 2022
This can be achieved if the subgraphs are sparsely located in the graph. On the other hand, such in- consistencies provide a regularization effect, which prevents GNNs from overfitting the node labels of individual subgraphs but promotes learning general node features useful for multiple subgraphs.
How can we combine the node labels for different target subgraphs? One solution is to concatenate them, which seems to have no loss of information. However, this method leads to variable lengths of node labels, and depending on which other subgraphs attend this batch, it leads to possibly different node labels for the same target subgraph. The sum of all labels has similar problems. However, using the max of all labels avoids such problem, which can help the model converge faster and facilitate processing samples in varied batch sizes. Taking the zero-one labeling trick as an example, we will label node by I if at least one subgraph in the batch contains this node. Otherwise, we will label a node by O. We call such a labeling trick the max-zero-one labeling trick. In our experiments, we uniformly used the max-7ero-one labeling trick for GLASS and verified its fast training speed as well as excellent empirical performance.
Previous works have explored other ways to enable batch training. For example, SEAL (Zhang & Chen 2018) segregates small enclosing subgraphs from the whole graph to perform link prediction tasks. However, subgraphs usually contain much more nodes than links, resulting in huge enclosing subgraphs to be segregated. Moreover, in some datasets, subgraphs have multiple components. To capture the interaction among components, the depth of the enclosing subgraphs has to be large, leading to exponentially increasing subgraph sizes. IDGNN (You et al. 2021) uses fabricated addi- tional features instead of labels, leading to loss of expressive power. Moreover, in Appendix AA.6] we show that no labeling trick can avoid the inconsistencies of node labels within a batch. Therefore, it is impossible to solve this problem by designing fancy labeling trick, and approximation is must.
EXPERIMENT
In this section, we compare GLASS with state-of-the-art subgraph representation learning methods, especially SubGNN, on both synthetic and real-world datasets to demonstrate that GLASS a model with superior performance and scalability, despite being much simpler than SubGNN.
6.1 DATASETS AND MODELS
Datasets. We use four synthetic datasets: density, cut ratio, coreness, component, and four weal-world subgraph datasets, namely poi-bp, em-user, hpo-metab, hpo-neuro. The four synthetic datasets are introduced by Alsentzer et al. (2020) to test a model's ability to learn the six properties: density tests the ability to learn internal structure; cut ratic tests border structure; coreness tests border structure and position; and comporent tests internal and external position. The four real-world datasets are also provided by Alssntzzr et al. (2020). The base graph of the ppi-bp dataset is human protein- induced by proteins in a biological process, whose label is its cellular function. The hpo-met ab and hpo-neure datasets are knowledge graphs containing phenotype and genotype information about rare diseases. Each subgraph represents a rare monogenic disease. The em-user dataset contains the workout history of users, where each subgraph makes up a user's workout history, and the label is the gender of the user. Detailed information on these datasets are in Appendix A.10
interaction network. Each subgraph is
Baseline Models. We consider four baseline methods. (1) SubGNN (Alsentzer al. 2020) uses subgraph-level message passing with six artificial channels. We use the numbers provided by the original paper. (2) Sub2Vee (Adhikari al. 2018) samples random walks subgraphs which are fed to Paragraph2Vec to train subgraph embeddings. We train Sub2 Vec using the official implemen- tation to produce subgraph representations and then feed them to an MLP. Like SubGNN, Sub2 can also capture neighborhood and structure without passing messages between nodes. However, it uses node ID and degree ratio in the target subgraph to represent nodes, rather than pretrain- ing GNNs. Moreover, it only learns the internal topology by sampling random walks in the target subgraph. We compare these two existing subgraph representation methods to show the superior performance of GLASS. (3) GNN-seg is ordinary MPNN performing graph classification task on subgraphs segregated from the whole graph. We use to illustrate that subgraph tasks need external topology. (4) MLP and (5) GBDT pool node embeddings to produce subgraph embed-
7

---

Published as a conference paper at ICLR 2022
Table Mean Micro-Fl with standard error of the mean on synthetic datasets. Results are provided from runs with ten random seeds.
Method
density
cut ratio
coreness
component
GLASS
0.930 + 0.009
0.935 = 0.006
0.840 = 0.009
1.000 = 0.000
SubGNN
0.919 + 0.006
0.629 0.013
0.659 + 0.031
0.958 + 0.032
Veb2
0.459 + 0.012
0.354 + 0.014
0.360
= 0.019
0.637 = 0.017
GNN-seg
0.952 + 0.006
0.346 0.011
0.593 + 0.012
1.000 = 0.000
Table Mean Micro-Fl with standard error of the mean on real-world datasets. Results are provided from runs with ten random seeds.
Method
ppi-bp
hpo-metab
hpo-neuro
em-user
GLASS
0.619 + 0. 000007
0.614 = 0.005
0.685 = 0.005
0.888 = 0.006
SubGNN
0.599 + 0.008
0.537 = 0.008
0.644 = 0.006
0.816 = 0.013
Veb2
0.388 + 0.001
0.472 0.010
0.618 + 0.003
0.779 + 0.013
GNN-seg
0.361 + 0.008
0.542 #.009
0.647 = 0.001
0.725 = 0.003
MLP
0.445 0.003
0.386 0.011
0.404 = 0.006
0.524 = 0.019
GBDT
0.446 + 0.000
0.404 0.000
0.513 + 0.000
0.694 + 0.000
dings and classify them. They are graph-agnostic, thus their performance can show the importance of graph topology for subgraph tasks. The details of the implementation of these baselines are in Appendix A.10
GLASS. For real-world datasets, pretrain plain GNN on link prediction tasks produce input node embeddings for GLASS. On synthetic datasets, GLASS uses homogeneous node features. We detail our GLASS architecture in Appendix A.7 and list other hyperparameters in Appendix A.
6.2 RESULTS
Synthetic Datasets. To evaluate the expressive power of GLASS, we test GLASS and other base- lines on four synthetic datasets. Results are shown in Table 3 GLASS significantly outperforms all baselines and outperforms the previous state-of-the-art model SubGNN by 20.4% on average and 48.6% in maximum. The results show that GLASS capture density and cut ratio infor- mation very well as proved. Moreover, they illustrate the expressive power of ordinary node-level MPNNs for subgraph representation learning- do not need to subgraph-level message pass- ing with complicated artificial channels, but a plain GNN with a simple labeling trick is enough. As for GNN-seg. its failure predict ratio and coreness is expected these properties requires topology outside the subgraph. Similarly, Sub2 Vec cannot capture position information and external topology, thus its fallure on cut ratio and component reasonable.
Real-world datasets.
Table shows the results. GLASS gains a 8.2% increase average and 14.3% increase in maxi- mum compared with SubGNN. On hpo-metab and hpo-neure datasets, GNN-seg beats other baselines very easily, which might be because the subgraphs in these two datasets are dense and localized, making the topology outside the subgraph less important.
In contrast, on ppi-bp and em-user, the density of subgraphs is lower, and some subgraphs are even composed of single nodes. Thus GNN-seg can leam little from the internal topology as shown by the worse performance. Sub2Vec less expressive than SubGNN as expected. However, on epi-bp and em-user datasets, it has edge over GNN-seg. We suspect that the node ID can leak some external topology information to Sub2Vec, as the same nodes can appear in different subgraphs.
MLP and GBDT are both graph-agnostic models. They fail on all datasets, which illustrates that capturing graph structure is important for subgraph tasks.
Ablation Analysis To demonstrate the power of the max-zero-one labeling trick, we do an ablation study by removing the max-zero-one labels from GLASS, which is called GNN-plain. A comparison between GLASS and GNN-plain is shown in Our labeling trick improves the performance by 12.% synthetic datasets and 2.8% real-world
datasets) (real world datasets).
8

---

Figure 3: The time needed for training a model (log scale). SubGNN takes more than 48h on Published as a conference paper at ICLR 2022
Table Mean Micro-Fl with standard error of the mean on synthetic datasets. Results are provided from runs with ten random seeds.
Method
density
cut ratio
coreness
component
GLASS
0.930 = 0.009
0.935 + O, 0.006
0.840 = 0.009
1.000 1 0.000
GNN-plain
0.462 + 0.011
0.887 0.008
0.536 0.008
0.998 + 0.002
Table Mean Micro-F1 with standard error the mean on real-world datasets. Results are provided from runs with ten random seeds.
Method
ppi-bp
hpo-metab
hpo-neuro
em-user
GLASS
0.619 + 0.007
0.614
0.005
0.685 + 0.005
0.888 = 0.006
GNN-plain 0.613 - 0.009
0.597 = 0.012
0.668 0.007
0.847 + 0.021
datasets on average. The relatively lower improvement on real-world datasets might be because improving the expressive power is not the most critical factor for real-world datasets, but rather, filtering noise and smoothing features is more effective. In other words, the synthetic datasets require much stronger structure learning ability than the real-world datasets to perform well. This can also be seen from the comparison between SubGNN and GNN-seg in Table where SubGNN only marginally outperforms GNN-seg real-world datasets.
In Appendix II we analyze the effect of batch size GLASS on some datasets. In general, the performance of GLASS drops as the batch size increases. However, the max-zero-onc labeling trick can still boost plain GNNs at a large batch size. The performance gap between GLASS and GNN also shows that the effect of overlapping node labels is insignificant under experimental setting. In Appendix A.9 we also design a score to quantify the overlapping effect.
Computation Time Comparison The precomputation of SubGNN is quite time-consuming, After precomputation, the training of SubGNN is also slower than GLASS. On the 7 used datasets (except -bp), SubGNN average takes 2.7x more time than GLASS converge. Moreover, the ratio jumps to 7.9 when we count in precomputation. The results can be found in Figure
10
SubGNN precompute
SubGNN-train
GLASS
timels
10a
102
component
densily
cul_ratio
coreness dataset
em hpp appam hpo__eure ppi_bp
ppi-bp.
7 CONCLUSION
We have proposed GLASS, simple yet powerful model for subgraph representation learning. We illustrate the failure of plain GNNs on some simplest subgraph learning tasks, and demonstrate the power of labeling trick to enhance plain GNNs both theoretically and empirically. GLASS outper- forms the previous state-of-the-art method SubGNN by 20.4% on synthetic datasets and 8.2% on real-world datasets, verifying the power of node-level message passing for subgraph representation learning. We argue that plain GNNs + labeling trick are enough for learning higher-order substruc- tures, and the complicated subgraph-level message passing not necessary. Despite the success of our max zero-one labeling trick, it is still less powerful and heuristic compared with other existing labeling tricks. We leave the exploration of other labeling tricks for subgraph tasks to future work.

---

Published as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
Our main theoretical contribution in Appendix A.5 and complete proofs are also shown there. Moreover, our proposed model GLASS consists of our max-zero-one labeling trick and a plain GNN. We describe the labeling trick in Section 5.2 and the architecture of GLASS in Appendix A.7 in detail. All datasets used in our experiments are public. Our code available https:// github, com/ www.:///wwwaaaa////ooaoaaa
ACKNOWLEDGEMENTS
The authors greatly thank the actionable suggestions from the reviewers. Zhang is partly supported by the CCF-Baidu Open Fund (N0.2021PP15002200)
REFERENCES
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference on Artificial Intelligence, pp. 2112-2118 2021.
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learn- ing for subgraphs. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pp. 170-182, 2018.
Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. Subgraph neural net- works. Advances in Neural Information Processing Systems, 2020.
Antoine Bordes, Sumit Chopra, and Jason Weston. Question answering with subgraph embeddings. Proceedings of the Conference Empirical Methods in Natural Language Processing, pp. 615- 620, 2014.
Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. CoRR, abs/2011. 2020.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: A prin- cipled approach to accelerating graph neural network training. International Conference on Ma- chine Learning, pp. 1204-1215, 2021.
Benson Chen, Regina Barzilay, and Tommi S. Jaakkola. Path-augmented graph transformer network. CoRR, aas//105..12111 12712, 2019.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International Conference on Machine Learning, pp. 1725-1735. 1735, 2020.
Shrey Dabhi and Manojkumar Parmar. Nodenet: A graph regularised neural network for node classification. CoRR, abs/2006.09022, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. CoRR, abs/2012.09699, 2020.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Proceedings of the 3 ltt International Conference on Neural Informa- tion Processing Systems, pp. 6533-6542, 2017.
Mikhail Galkin, Jiapeng Wu, Etienne Denis, and William I.. Hamilton. Nodepiece: Compositional and parameter-efficient representations of large knowledge graphs. CoRR, abs/2106. 12144, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2022
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Conference on Computer Vision and Pattern Recognition, pp. 9211-9219, 2019.
Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. In Advances in Neural Information Processing Systems, 2020.
Quoc Le and Tomas Mikolov. Distributed representations of sentences and documents, In Pro- ceedings of the 31st International Conference on Machine Learning, volume 32, pp. 1188-1196, 2014.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 2020.
Changping Meng,
Chandra Mouli, Bruno Ribeiro, and Jennifer Neville. Subgraph pattern neural networks for high-order graph evolution prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Abdullah Mueen and Eamonn Keogh. Extracting optimal performance from dynamic time warping. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2129-2130, 2016.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341, 2021.
Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, and Austin R. Benson. Edge proposal sets for link prediction. CoRR, abs/2106.15810, 2021.
Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Yuanxing Ning, Philipp S. Yu, and Lifang He. Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism. Proceedings of the Web Conference 2021, pp. 2081-2091, 2021.
Jinhuan Wang, Pengtao Chen, Yunyi Xie, Yalu Shan, Qi Xuan, and Guanrong Chen. Broad Learning Based on Subgraph Networks for Graph Classification, pp. 49-71. 2021.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. N7I, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Mingqi Yang, Yanming Shen, Heng Qi, and Baocai Yin. Breaking the expressive bottlenecks of graph neural networks. CoRR, abs/2012.07219, 2020.
Yiding Yang, Xinchao Wang, Mingli Song. Junsong Yuan, and Dacheng Tao. SPAGAN: shortest path graph attention network. In Proceedings of the Twenty-Kighth International Joint Conference Artificial Intelligence, pp. 4009-4105. ijcai.org, 2019.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. Proceedings of the AAAI conference artificial intelligence, 33(01):7370-737) 2019.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. International Conference on Machine Learning, pp. 11975-1 1986, 2021.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform bad for graph representation? Neural Information Processing Systems, 2021a.
Chengxuan Ying. Tianle Cai. Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? CoRR, Abs/2106.05234. 2021b.
11

---

Published as a conference paper at ICLR 2022
Rex Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovec. Neural subgraph matching. CoRR, 0ass/2007.03092, 2020.
Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Thirty-Fifth AAAI Conference on Artificial Intelligence, pp. 10737-10745, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets, In Advances Neural Information Processing Systems, pp- 3391-3401,
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. CoRR, http/2001.5514000 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 2021.
A
APPENDIX
A.1 OTHER STRUCTURAL ENCODING METHODS
We discuss other existing structural encoding methods as follows.
Positional Encoding in Graph Transformers. WL-PE (Zhang al. 2020) utilizes the Weisfeiler- Lehman algorithm to produce node labels. As GNN can be as expressive as the WL test, this technique in theory will not increase the expressive power of GNNs. From the design of labeling tricks, Laplacian-PE (Dwivedi & Bresson 2020) is not permutation invariant and cannot differen- tiate nodes within and outside the target subgraph, as isomorphic nodes can have different labels, while noniisomorpiic nodes can have the same label (for example the eigenvector corresponding to eigenvalue 0). Graphormer proposes centrality encoding, which encodes the indegree and outdegree of nodes to help Transformer capture graph structure information. (Ying et al.) 2021a). Though it
specifically useful for graph transformers, GIN (Xu et al. 2019) can casily capture node degree with one message passing layer.
Edge and Path Feature. They are not designed for subgraph tasks and cannot represent node position relative to the target subgraph. Spagan (Yang et al. 2019). Graphormer (Ying et al., 2021a), and PAGTN (Chen et al., 2019) both utilize shortest path encodings to reconstruct the adjacency matrix. They can capture long-range node interaction, which is important for subgraph tasks, but orthogonal to our zero-one labeling trick to distinguish nodes inside and outside the target subgraph. And we easily add our labeling trick EGNN (Gong & Cheng 2019), GINE+ (Brossard al.,
2020
A.2 PROOF OF THROREM 1
Proof. Consider the following GNN, which ignores node features.
00
a
(2(S)
0
+
)
WE NEN(w) (w)
[0]
1
0
0
0
60
1
1
a
0
0
0
0
hs =
Σ
(1))
VEVS
where ((0) is the zero-one label of node v, hy is the representation of subgraph S.
12

---

Published as a conference paper at ICLR 2022
Density d and cut ratio can be predicted with GLASS in transductive setting.
U
T
d(ss)
h
/
hs)
hs - 1)1
(10)
0
001
[
T
[07
chss
0.5
hs)/((
hs) (n
0
hs 1)]
(11)
0
A.3 PROOF OF PROPOSITION 1
Proof. First, we need to prove that given any plain GNN model mi, there exists GLASS model m2 producing the same output for any target subgraph S.
Assuming that the AGGREGATE function of mi f(*), the COMBINE function of my is 9i at the 4thh layer and the READOUT function of m, Φ1. We can define function mapping labeled node features to the initial node features, OCCONCATENATEE/ (k-1) ((())) = h (k-1) which is a well defined function. And we can design GLASS follows.
(k)
h (k-11) 1) CONCATENATE(M) 111()))
(12)
a ((0() (1 I N(r))), h 91 (n!
(13)
(W) (k-1)) a (k)),
(14)
where (a( is the embedding of node the ht layer. We use Φi as the READOUT function, therefore m2 will produce the same embeddings as my for the target subgraph.
Second, GLASS can differentiate at least one pair of subgraphs which plain GNNs cannot distin-
guish. Figure 2 gives example.
A.4 ANALYSIS How GLASS CAN COVER THE SIX PROPERTIES IN SUBGNN
The implementation of the channels in SubGNN are non-deterministic, so GLASS cannot precisely reproduce the behavior of SubGNN. Our goal to prove that GLASS can represent the channels by definition.
As the SubGNN uses embeddings produced by plain GNNs as node features, we first show that GLASS can also produce such node embeddings.
Proposition 3. Given a graph G and node embeddings G produced by plain GNNs, GLASS can also produce the same embeddings.
Proof. We have prove that GLASS is more expressive than plain GNNs in
Therefore, for any GLASS model, we can use some bottom layers to produce node embedding, and the rest of the model is still GLASS. Therefore, are the same as those of SubGNN. Let gı. denote the pretrained GNN embeddings of node u.
assume the input node features of GLASS
We also need to show the performance of plain GNNs. Xu et al. (2019) prove that GNNs map two nodes to the same embeddings only if they have identical BFS structures with identical features (Ti, T2,,., }. where T. means the tree rooted in node u. If READOUT is an injective multiset function like DeepSet (Zaheer et al. (017), plain GNN will be an injective function e {Ts[S S 9) Rd where Ts [Tulu Vs).
plain
the corresponding nodes. Assuming the k-depth rooted subtree set is T
13

---

Published as a conference paper at ICLR 2022
The internal N property encodes the set of nodes in the target subgraph, and the border N property encodes the set of neighbors within & hops of nodes in the target subgraph. Therefore, to show that GLASS can cover the N channel in SubGNN, only need to prove that GLASS can differentiate any pair of neighbor feature sets. See Proposition
Proposition 4, Given a target subgraph S in a graph 9, GLASS can produce different embeddings for any pair of different border neighbor feature sets (guld(u, v) S k, v E Vs) or internal neighbor feature sets (g E Vs).
Proof. For border neighbor feature sets, let function f(Ts) = (gulu E Vr. TE TT). . o is function mapping embeddings border neighbor set. Therefore, GLASS can produce different embeddings for any pair of different border neighbor feature sets (guld(u, v) S k, E Vs).
As for the internal neighbor feature set, we can use GLASS layer whose COMBINE function maps all nodes labeled zero to constant embedding vector gu different from any existing initial node embeddings, and maintain the input embeddings of nodes labeled one and pass it to a GLASS used in last paragraph. Let function ((U) U - {go}. Therefore, v f o 0 maps embeddings to internal neighbor feature sets. Therefore, GLASS can produce different embeddings for any pair of different internal neighbor feature sets {g./u E Vs).
For the P channel, the internal position is defined as the distance (shortest path length) between nodes in the target subgraph, and the border position is the distance between nodes in the target subgraph and nodes in the whole graph.
Proposition 5. Given a target subgraph S in graph G. if emmeddingg of nodes are different from each other, GLASS can produce different embeddings for subgraphs with different position information.
Proof. k-layer MPNN can capture rooted subtree structure. As the node embeddings are different, the set of embeddings of nodes can be mapped to the set of nodes bijectively. gu appear in I-depth rooted subtree but not in ( - 1-depth rooted subtree, we can infer that the distance between the target node and node u is I. Moreover, using the DeepSet function as READOUT, we can capture the distance between nodes in the target subgraph and any other nodes.
Note that though we assume that the node embeddings are different from each other in Proposi- tion [5] we can let the input feature be learnable in implementation. Thus the coincidence of node embeddings can be avoided.
Moreover, with such technique, we can build a bijective function from the embedding space to the node set. The theoretical expressive power of GLASS will be stronger and no longer be limited to node embedding generated by plain GNNs.
As for the S channel, it is defined the internal feature connectivity (the multiset {9g.. ge (u, Es }), and the border feature connectivity (the multiset {(g.. ge) u E Vs, e & Vs. (u, v) E E)).
Proposition 6. GLASS can represent the internal and border structure. In other words, there exists GLASS model mapping the multiset {(gu.9w (00 (u,v) E Es} and ((gu, gu)lu a S and v & S) to the embedding space injectively, where is the pretrained GNN embeddings.
Proof. WLGNN can encode the multiset of feature pairs (1(gu. E N(u)) E Vs} with the following encoder.
Σ f2(g))), vEN(u)
(15)
NEVS
where fi and f2 are some functions whose existence Xu et al. 2019 have proved. In other words, can encode BFS trees whose depth=1.
we concatenate the node labels and (namely g'), and design
{ [2(g)) if L,
f/
(16)
0
otherwise
14

---

Published as a conference paper at ICLR 2022
[2(g))
I, =0
12
(17)
otherwise
Enev ste) (V(EV f2())) can represent {(gu: (c) ) (u, w) E E.
And Eucy slo) fi (V f2(g.)) can represent go)lue e ste) and & St0).
A.5 THE EXPRESSIVE POWER OF GLASS UNDER STRUCTURAL REPRESENTATION THEORY
Zhang al. (202T) introduce a theoretical framework analyze the expressive power of GNNs. Us- ing this framework, we theoretically characterize the expressive power of GLASS, We first introduce some terms of labeling trick theory.
A permutatiinn æ is bijective mapping from 21.2...., n to 2 2.... n), where E N All possi- ble permutations constitute the permutation group II, For node set C V, (U) = (*())] U). where i is the node index in graph 9, and (i) can be node index in G or any other graph. For edge set F C IE, (F) = {i) T (())(( E F}. For node attribute matrix X, π (X)x() = X, And for subgraph S and graph 9, (S)) (r(Vs), 7 (Es), ((x)) and (g) (V() I (E). T (X)).
The definition of labeling trick is as follows.
Definition 2. Given a subgraph S in graph we design a label matrix L R Vixd whose 1hth is the label of node u. satisfies: for any two subgraphs S and St in G
1. (lurge--node--dssiiinuuiiiii L(s) = T (L())) = Vs = =()s)
2. (permutation equivariance) S T = (()) = = (L))
Proved by Zhang et al. (0221) the zero-one labeling trick is a valid labeling trick.
Now we analyze the power of labeling trick. We first define subgraph isomorphism.
Definition 3. Given two n-node graphs G (V,E, X),, g'
(V', E', X'), and one subgraph of G and one subgraph S' of G', S and S' are isomorphic (denoted by S = S') iff 3r E II, (S)) (S') and (g) (g').
Isomorphic subgraphs should be mapped the same embeddings, and the most expressive repre- sentations should differentiate all non non-isomorphic subgraphs. Therefore we introduce the concept of structural subgraph embeddings illustrate such perfect representations.
Definition 4. T(S) is structural subgraph embedding for subgraph if S' ( S = S'
Numerous works have been exploring the expressive power of GNNs on node tasks. However, we focus on how labeling trick can help GNNs on subgraph representation learning. Therefore, we introduce an ideal GNN model for node tasks.
Definition 5. Ifa GNN can map node to the embedding vector h. so that given any two graphs and G', E V. j E V", h; = h2 <> 3m II, T(j) and = x (g'), we call a node-most- expressive GNN.
Though GNN is powerful on various tasks, Zhang et al. (202T) show that node embeddings generated by GNNs are not enough to produce structural subgraph embedding even if we use a node-most- expressive GNN, However, labeling trick can solve this problem. Zhang et al. (202I) prove that with labeling trick and injective READOUT function, node-most- tile--oot-exxpessivee GNNs can produce structural subgraph embeddings.
Theorem 2. There exists function I, where I(S) is structural subgraph embedding for subgraph S, can be formulated as T(S) READOUT((HH)) E Ws}), where H is the node embedding matrix of a nodeemmst-expressvve GNN with node label input.
Please refer Appendix A of (Zhang et al. 2021 for the proof.
15

---

Published as a conference paper at ICLR 2022
However, up to now, scalable node -eee--ooo--ee--eeeeee GNNs have been realized. However, with less expressive GNNs, labeling trick can still make a difference. Figure providdes an example.
Here prove that labeling trick can boost WLGNNs, a kind of GNNs whose expressive power is the same as 1-WL.
Theorem 3. For any 6 IRt, given any graph 9 with nodes, whose node degrees range from to (llog(1-0)) n), and having an empty feature, there exists u222n22-1 pairs of non-isomorphic subgraphs such that any h-layer WLGNN produces the same representation, while with labeling trick WLGNN can distinguish them.
Proof. We prove that there are w(n nodes that WLGNNS cannot differentiate in (1), and get the bound (2).
(1)The bound of the number of nodes in n-hop BFS tree is
h (V S K Σ =d==0d"") = Ollg - n).
(18)
==U
We can add virtual nodes make the trees become complete k-ary trees. And by enumerating the position of the virtual node we can get bound 20 = OOnn' (r) for the number of non-isomorphic trees.
According to the pigeonhole principle, there exist n/ nn/On!=9) 1-) = n² nodes which cannot be differ- entiated with each other by WLGNNs. They form set Visa-
(2) Let us partition Viso = _ Vs, nodes in each VÚ share the same one-hop neighbor. Consider
a node E V V,, # j. There exists a node I-e V [u, w) - N(w). [Vol 2 wo(n - log n). Consider arbitrary subset V, S V. Let S₁ donate the subgraph induced by V. Ufu, w). S₂ donate the subgraph induced by V. Ufv, w). w.J.n The density of S₁ is higher than Sg. And GLASS can fit density perfectly, GLASS can distinguish S₁ and S2. while WLGNNs cannot.
N(u), & N(e). Let V. donate
And the number of pairs (u, u. w) is
II 11=1
V.VV
2 (lVisol isol Σ MVP)
(19)
As nodes in [V] share the same neighbor, [Vi S O(log I-c n). So the expression above
q
II
WIIV, 2
(20)
And the bound for the number of these pairs of subgraphs is
w(nn 200 paponn-nng log tor
w2n2 25-1)
(21)
A.6 THEORETICAL ANALYSIS OF MAX EERO-ONE LABELING TRICK
Take closer look the definition of labeling trick. Node label should be (1) target-nodes- distinguishing. Labels of nodes in S must be different from those out of S. (2) permutation equiv- ariance. Isomorphic nodes (in S and out of S separately) must be mapped to the same label. We can illustrate the function of the conditions with the following theorem.
Theorem 4. For any S,S' in given gruphs G.G' respectively. there exists a node- (1) hs = hg + S S' if((s) = T(((S)) + Vs = sVVs:); (2) hy = hg + S ~ S' i = (S'), G = (G) = ((5) = T(((5)), where h is GNN embedding of subgraph.
GNN with labeling trick satisffyng::
16

---

Published as a conference paper at ICLR 2022
pooling
Prediction
Pretrained SSL
PATT
X
node label
2
Task Prediction
pooling
S
node label
node
Xn
Figure 4: GLASS is composed of node label function, MPNN, pooling layers.
This theorem has been proven in Appendix A of (Zhang al. 2021
Proposition 7. For all labeling tricks, there exists case that given two different subgraphs S, S' in graph G, node label ((5) + ((S))
Proof. Consider three isomorphic nodes, namely u, v, w. in a graph. Let S₁ donate subgraph in-
duced by {u. v/, , S2 donate subgraph induced by {u, w)- Therefore, (Si) I (St) (Sa) ( = T # (. ((()) + ((()))
+ L (Si)
and
Therefore, developing less theoretically powerful tricks is must. Here, we introduce the max max-zero- one labeling trick. Looking back on the definition of labeling tricks, it is invariant but not expressive enough.
Definition 6. Given subgraphs in batch (S. The max-zero-one label of a node is
[ if E [1,2 .... n), E Vs;
D,
t0 otherwise
(22)
With Theorem we can prove the invariance of the max zero-one node labels. Corollary A.1. With node-most-expressiv GNN, injective READOUT and the max-zero-one node labels, in a single batch, = S' = Hs Hs
Though the max zero-one results in loss of expressive power compared with zero-one, experiments show that the model can fit cut ratio and density very well. These two properties need a clear division of nodes and outside the target subgraph.
A.7 GLASS ARCHITECTURE
GLASS takes embeddings produced by pretrained GNN input node feature. Then it uses node label function to transform node embeddings before message passing at each label, where node label functions node label-specific MIPs. Then GLASS pools node embeddings produce subgraph embeddings and use a mip to produce the output. We also use normalization layers (Cai et al. 2021) accelcrate optimization.
A.8 SELF-SUPERVISED LEARNING
SubGNN uses GNN pretrained on link prediction task to produce input node embeddings for GLASS. We also use compare GLASS and GNN-plain with SubGNN, Pretrained GNN em- beddings help GLASS capture distant neighbors. If the pretrained GNN has layers and the GNN used in GLASS has layers, it can capture (1 + k)-hop neighbors, while a k-layer MPNN only capture neighbors within & hops. Moreover, we design GLASS.
SSL tasks to further boost
In practice, subgraph datasets often not large, and target subgraphs often sparse in the whole graph. Thus, training GLASS only from the subgraph property prediction signals tends to overfit. Therefore, we introduce three levels of self-supervised learning (SSL.) tasks to assist the GLASS
17

---

Published as a conference paper at ICLR 2022
Table 7: Mean Micro-Fl with standard error of the mean of GLASS with SSL on test sets, esults are provided from runs with ten random seeds.
dataset em user
GLASS
GLASS+SSL
0.888 + 0.006
0.902 + 0.006
ppi.bp bp
0.619 + 0.007
0.621 0.008
apo_metab
0.614 + 0.005
0.565 + 0.006
ipponnerr
0.685 + 0.005
0.674 0.002
Table Noisy label ratio for each datasets under our experimental setting.
dataset 711
722
dataset
711
172
density
0.022
0.012
em em_user
0.018
0.011
cut_ratio
0.018
0.012
ppi.bp
0.078
0.044
coreness
0.023
0.024
hpo_metab
0.063
0.040
component 0.004
0.028
hpo_neuro 0.097
0.061
training. 1) Node level: We train GNN produce node embeddings to predict A A where A is the adjacency matrix of the whole graph. Intuitively, it helps GNNs differentiate different BFS trees (Ychudai et al. [02I], thus preserving better local subtree information. 2) Edge level: We perform link prediction task the whole graph. Intuitively, it pushes nearby nodes to have similar embeddings, thus encoding the node distance information into the node embeddings. 3) Subgraph level: We let the final subgraph representations predict some subgraph structural properties, includ- ing density, cut ratio, coreness, and the number connected components. It helps the model better capture some higher-order substructure information.
We take a pretraining strategy for node and edge-level SSL tasks, whose output node embeddings used initial features of the GLASS. Then, we jointly train the subgraph-level SSL tasks and the main subgraph property prediction task. Donate the loss for the main task, node-level SSL, edge- level SSL, and subgraph-level SSL Lmain, Lnodes Ledges Liaagg The pretraining loss is given by Lpre = a + &Ledge. and the joint training loss is given by Ljoint = a,3, 7 are hyperparameters.
Lmain + L where
We only use SSL for real-world datasets. The results are listed in Table
SSL tasks boost GLASS em.user and ppi.bp datasets.
A.9 NOISY LABEL RATIO
In this paper, we only analyse the expressive power of zero-one labeling trick but use max-zero-one labeling trick in experiments. If subgraphs are so sparsely located in the subgraph that their k-hop neighbors do not overlap. both tricks are equivalent for k-layer GLASS. However, many real-world graphs have small diameter, so such overlap maybe inevitable. To quantify the overlapping effect, we define noisy label ratio nr; the ratio of i-hop neighbors with inconsistent zero-one and max- zero-one labels computed over all subgraph nodes. In Table we show the nnoisy label ratio of the datasets under our experimental settings. The results show that the overlapping effect brought by using max-zero-one labeling trick is insignificant.
A.10 IMPLEMENTATION DETAILS
Datasets. We use the code provided by SubGNN to produce synthetic datasets and use the real- world datasets provided by SubGNN directly. The statistics of these datasets can be found in Table As for dataset division, the real-world datasets take 80: 10:10 split, and the synthetic datasets follow a 50:25:25 split, following (Alsentzer et al. 2020).
Computing infrastructure. We leverage Pytorch Geometric and Pytorch for model development. Models were trained on an Nvidia V100 GPU to measure the train time and were tested on an Nvidia A40 GPU Linux server.
Implementation of Message Passing Networks. For all cressage-passingg network models, we try three kinds of aggregation methods: sum, mean, and GCN and four kinds of pooling methods: sum,
18

---

Published as a conference paper at ICLR 2022
Table
Detail of datasets
Datasets
V
E
Number of Subgraphs
density
5,000
29,521
250
cut-ratio
5,000
83,969
250
coreness
5,000
118,785
221
component
19,555
43,701
250
ppi.bp 17,080
316,951
1,591
hpo_metab
14,587
3,238,174
2,400
_pp_neurr 14.587
3,238,174
4,000
em_user 57,333
4,573,417
324
mean, max, and size, where the size pooling is to sum the node representations and divide it by the square root of the number of nodes.
Input node feature. We use an all-one vector for GNN-plain, GNN-seg, Graphormer-seg, and GLASS on synthetic datasets. On real-world datasets, GLASS, GNN-plain, MLP, and GBDT use trainable pretrained node embedding. GNN-seg uses node degree.
Pretrained node embeddings were pretrained using a [-layer GNN with node id as the imput node feature. Fixed hyperparameters were batch size = 131072, learning rate 1e - 3, hidden dimension 64. Dropout selected from [0.0, 0.5] and ranges from to
Pretraining GNN.
Baselines. We directly use the results reported for SubGNN. Sub2Vec is designed for connected subgraphs, so we sample random walks each component separately. We utilize the implementation of Vec and use all its channels. For MLP and GBDT, We first pool the node embeddings to produce subgraph embeddings, then use MLP and GBDT (implemented with xgboost) to classify subgraph embeddings.
Model hyperparameter tuning. We use optuna to perform random search. Hyperparameters were selected to optimize Micro-Fl scores on the validation sets. The best hyperparameters selected for each model can be found in our code in the supplement materials. For GLASS, we select the learning rate from {le 4, 2c 4, 5e 4, le 3, 2e 3, 3.5e - 3}; number of layers from {1, 2); hidden dimension, 64 for real-world datasets and {1, 5, 9, 13, 17); dropout, 0.5 for real-world datasets and {0.1, 0.2, 0.33 } for synthetic datasets; aggregation, {mean, sum, gen); pool, { {mean, sum, max, size}; batch size, [ns/800 ns/ /4, ns/20 /0,, ns/ ns/10), 10), where ns is the size of datasets.
Training process. We set upper bound (10000) for the number of forward and backward pro- cesses and use an early stop strategy which finishes training if the validation score does not increase after 1000 forward and backward processes. We utilize Adam optimizer and ReduceeLROnPltteau learning rate scheduler to optimize models.
A.11 TRADE OFF AMONG BATCH SIZE, TRAINING TIME, AND PERFORMANCE
On coreness, cut ratio. and density datasets, we test the performance of GLASS at different training batch sizes. The results are in Figure We also measure the training time of GLASS. The results are in Figure
In general, the performance drops as the batch size gets larger. However, the max-zero-one labeling trick is still effective at large batch size as on all datasets, as the difference of F1 score keeps positive. However, we find that when we set the test and valid batch size to one, the performance of GLASS drops faster, which shows that max-zero-one is not just an approximation of zero-one. With max mex-zeero-ne, GLASS is trained to predict the properties of the target subgraph with the existence of other subgraphs.
As the batch size gets larger, the training becomes faster. The time needed for each forward and backward process nearly irrelevant to batch size, but the gradient is more precise and the model converges faster. For these three datasets, increasing batch size from to 32 reduces training time by about 2/3.
As for other datasets, even plain GNNs can predict component precisely. Furthermore, the targets in real-world datasets less closely connected to subgraph topologies. Last but not least, real-world
19

---

Published as a conference paper at ICLR 2022
0.5
0.5
0.4
0.3
0.3
A score
0.2
0.1
A f1
0.1
cut_ratio
0.0
cut_ratio
coreness
coreness
0.1
-0.1
density
density
0.2
-0.2
1
2
8
16
32
2
8 batch size
4
16
32
batch size
Figure 5: The difference of Fl score between GLASS and GNN-plain. The results are provided with runs on ten random seeds. The left subplot shows the result of testing in batch. The right one shows the performance of testing each sample separately, in other words, setting the valid and test batch size to one.
200
density
175
cut ratio coreness
150
125
training
50
25
2
8
16
32
batch
Figure 6: The training time against batch size. The results provided with runs on ten random seeds.
datasets are bigger, and we also use bigger models for them, leading large variance in performance and high time complexity.
To trade off between performance and training time, we can tune batch sizes for each dataset. In the worst case when the batch size is so large that target subgraphs in the batch are dense enough to cover the whole graph, GLASS degrades to plain GNN. This process is dataset-related. target subgraphs are sparsely located in the graph, large batch sizes can be used without hampering the expressive power. Moreover, small batch sizes are not always promising, due to the noise of gradients. We can take a strategy of trying large batch size first and reducing it until we obtain model with satisfying expressive power.
20


Reviews:
[{"review_id": "lT9NlJQPCj8", "reviewer": "Reviewer_cEit", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper argues that a subgraph-level positional encoding is enough for subgraph representation learning. It gives some theoretical analysis that such trick could fulfill the six properties that subGNN proposed. It also introduces three self-supervised learning task to guide GNN learning.\n\nI think the approach is reasonable and the analysis is sound and convincing. The main concern is:\n\n1) This paper adds the self-supervised learning into the framework, and compare with subGNN without such SSL learning. I think this comparison is not fair. On the one hand, I think SSL learning should be agnostic to GNN model. I think you should compare your model with other GNN model in the same setting, i.e., with SSL training or without.\n2) The motivation and insights of the SSL learning task is less than the subgraph encoding. I think the authors could consider either remove this part, or at least compare with other SSL learning methods, such as graph contrastive learning or generative learning.\n3) The idea of adding structural encoding is also explored in graph transformer (Do Transformers Really Perform Bad for Graph Representation?)\nI recommend the authors also compare this method into subgraph-level modelling.\n\n", "summary_of_the_paper": "This paper proposes a simple subgraph modelling framework by adding a subgraph-level position encoding to node (whether a node belongs to subgraph) to node feature. In this way, the GNN is able to differentiate nodes from different subgraphs, and outperform previous model SubGNN. ", "summary_of_the_review": "The method is simple and effective, but I doubt the current evaluation setup as it uses additional self-supervision to train the model against baselines.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lS9ab6h5A5R", "reviewer": "Reviewer_UU3H", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strength:\n\n1. The paper addresses the overlooked problem of subgraph-level tasks, as most previous GNN models focus on node or graph-level tasks.\n\n2. The proposed approach is simple and intuitive with little overhead on top of plain GNNs. It can be easily implemented and can be trained efficiently.\n\n3. There is a good balance of theoretical and empirical results.\n\nWeakness:\n\n1. The novelty is somewhat incremental. Node labeling trick has been used on GNNs, although not specifically on the subgraph level. There does not seem to have significant challenges (or rather, it is quite straightforward) in extending plain GNNs to the zero-one / max-zero-one strategies.\n\n2. The main theoretical results only apply to the zero-one strategy. For the max-zero-one strategy, \"it can be achieved if the subgraphs are sparsely located in the graph\"--- which is dataset dependent. Furthermore, many real-world graphs have a small diameter, meaning that two random subgraph can easily overlapped k-hop neighborhood even when k is a small number.\n\n3. Proposition 2 states that GLASS can cover the six properties of SubGNN. In this case, what is the advantage of GLASS over SubGNN? Any additional property that SubGNN does not have? In the experiments, it is quite clear that GLASS is more efficient, but GLASS also holds a significant accuracy edge. I wonder if this accuracy advantage actually comes from the self-supervised loss, rather than the labeling trick? In particular, in the ablation study, even after removing the labeling trick, the results are still better than SubGNN on the real datasets. In other words, if SubGNN is also trained with the same self-supervised loss, would its performance become much better?\n\nMinor issues:\n\n4. Figure 2 is a bit hard to read, especially for S and S', since the green shapes intersect with many edges. Maybe using two different colors to highlight the nodes/edges, instead of using another shape to enclose it.\n\n5. It is mentioned that to solve label inconsistency in a batch, concatenation cannot be used as it leads to variable lengths of\nnode labels. I don't quite follow this point. If each batch contain the same number of subgraphs, wouldn't all label vectors have the same length?\n\n--- update after rebuttal ---\nSome of the response is valid, especially regarding the self-supervised loss. Hence I'm upgrading my rating.", "summary_of_the_paper": "In this paper, the authors propose GLASS, a GNN designed for subgraph tasks using labelling tricks. A simple zero-one trick can be used to differentiate nodes in and out of a target subgraphs. However, this would cause efficiency problem as different target subgraphs would require different labels. To fit the classic batch training, a batch of target subgraphs are used to label the nodes together. To resolve conflicts among subgraphs, a zero-max-one trick is proposed. GLASS is easier / intuitive to implement and more scalable. The zero-one trick version is also claimed to have more expressive power than plain GNNs and can capture the six properties in the state-of-the-art method SubGNN. Experiments have been conducted on both real-world and synthetic datasets with generally promising results.", "summary_of_the_review": "My main reason is incremental novelty (W1), and insufficient support for certain claims (W2/W3).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "g0m0KtmMW3p", "reviewer": "Reviewer_8Ehn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Strengths:\n1) This work is well-motivated. The authors claim that distinguishing inside and outside nodes of subgraphs is crucial for subgraph tasks. Based on the insight, the authors propose a novel method for node-level message passing GNNs to perform subgraph representation learning effectively and efficiently.\n2) The authors theoretically analyze the effectiveness of the max-zero-one labeling trick and the expressiveness power of the proposed method.\n3) Experiments demonstrate that the proposed model with labeling tricks outperforms state-of-the-art subgraph representation learning methods on several synthetic and real-world datasets. Experiments on running time also show that the proposed model is more computationally efficient than the subgraph-level learning method SubGNN.\n\nWeakness:\nThe authors may want to improve the presentation of this paper. For example, the introduction and analysis of SubGNN take up too much space that the illustration of the proposed method and experimental settings are not sufficiently detailed in the main text. \n", "summary_of_the_paper": "This paper focuses on predicting the properties of subgraphs in the whole graph. The authors propose a labeling trick to help GNN distinguish nodes inside and outside the subgraph. The authors rigorously analyze the effectiveness of the proposed method. Experiments demonstrate that the proposed method achieves state-of-the-art performance on several benchmarks.", "summary_of_the_review": "The authors propose a labeling trick to enhance plain GNNs for subgraph tasks, and the theoretical and empirical results demonstrate its effectiveness and efficiency. However, the authors may want to detail the model structure and experimental settings in the main text. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5FpHF2z8oYk", "reviewer": "Reviewer_VqVZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The authors study the problem of subgraph classification and propose a simple adaptation of existing GNNs for this task. In particular, their approach augments the initial representation of the node features with label information if a node belongs to a subgraph in a batch.\n\nThe paper is clearly written, provides supportive illustrations, and closes theoretical gaps of preceding works. \n\nAuthors can improve the paper in the following ways. \n\n1. Provide an ablation study on the self-supervised losses. How much does it affect performance? What if you employ the same losses for other approaches? \n\n2. From the last figure in the appendix it's clear that increasing the batch generally degrades performance, hence the batch size of 1 is the most promising one. What batch size you used in experiments? How much is it a problem from training time perspective? Your approach can't clearly have a very large batch size as it would include all nodes of the graph in the subgraph labels and hence there would be no difference between your approach and plain GNNs. So what's the largest batch size you can afford? What's the trade-off between batch size, time, and performance?\n\n3. Can you please add graph-agnostic MLP and GBDT approaches as baselines for the experiments? They often show superior performance than GNNs (see [here](https://openreview.net/forum?id=ebS5NUfoMKL) for example). \n\n4. One of the biggest concerns, however, is not with the paper, but with a studied problem. While authors give an example where predicting subgraph labels can be useful, I don't believe GNNs should be explored there (it's unlikely that the performance of the department is evaluated based on the graph structure rather on their deliverables). The same is true for the employed datasets, even though they are inherited from the previous work. In particular, ppi-bp, hpo-metab, hpo-neuro ask to predict a label for a subset of proteins, which are obtained from the clinical trials, which are expensive to run and utilize information beyond of what's available in the graphs. Besides the subgraph number of nodes in these datasets is about 10, which are very small graphs to evaluate. em-user is even worse: predicting a gender based on workout history graph is a very contrived dataset and thus it's not very insightful. I understand that it's not the authors who introduced the problem and datasets; however, making it clear why this problem is important and why it cannot be solved by other methods better would significantly strengthen the paper. Maybe you can find some relevant applications in the subgraph regression problem, where your approach could be seamlessly adopted. \n\nI am likely to update my score based on the authors' responses.", "summary_of_the_paper": "The paper proposes a simple GNN approach to predict labels of subgraphs. In experiments, it works better than an existing approach. Complementary they show their approach can predict characteristics of a graph such as cut ratio. Additionally, they augment the loss with self-supervised losses of predicting node, edge, and subgraph level information. \n", "summary_of_the_review": "This is a well-written paper, that could be improved by providing more motivation and exploring the performance in more depth by using other baselines and providing ablation studies. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a labeling trick for subgraph representation learning with GNNs. The proposed method, GLASS, improves on subgraph-level tasks. The topic of subgraph representation learning is relatively new, and this paper makes progress in that community which would be appreciated by other researchers interested in the same problem. 

The paper in the original submission state raised some concerns from the reviewers about unclear writing of the motivation and potential applications, technical novelty, and comparisons with existing approaches (even one that are not specifically designed for subgraph representation learning). It is good that the authors conducted additional experiments to show the effect of SSL (that the approach makes improvements without SSL). This and other clarifications from the authors convinced the reviewers to recommend acceptance.
Decision: Accept (Poster)