Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification
Authors: Kai Zhang
Yaokang Zhu
Jun Wang
Haibin Ling
Jie Zhang
Hongyuan Zha
Venue:  (2021)
Keywords: Graph Pooling
Graph Classiciation
Interaction Preserving Graph Pooling
Structure Landmarking

Abstract: Graph neural networks are promising architecture for learning and inference with graph-structured data. However, generating informative graph level features has long been a challenge.  Current practice of  graph-pooling typically summarizes a graph by squeezing it into a single vector. This may lead to significant loss of predictive, iterpretable structural information, because properties of a complex system are believed to arise largely from the interaction among its components. In this paper, we analyze the intrinsic difficulty in graph classification under the unified concept of ``"resolution dilemmas" and propose `SLIM, an inductive neural network model for Structural Landmarking and Interaction Modelling, to remedy the information loss in graph pooling. We show that, by projecting graphs onto end-to-end optimizable, and well-aligned substructure landmarks (representatives), the resolution dilemmas can be resolved effectively, so that explicit interacting relation between component parts of a graph can be leveraged directly in explaining its complexity and predicting its property. Empirical evaluations, in comparison with state-of-the-art, demonstrate promising results of our approach on a number of benchmark datasets for graph classification.


Under review as a conference paper at ICLR 2021
STRUCTURAL LANDMARKING AND INTERACTION MODELLING: ON RESOLUTION DILEMMAS IN GRAPH CLASSIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks are promising architecture for learning and inference with graph-structured data. However, generating informative graph level features has long been challenge. Current practice of graph-pooling typically summarizes a graph by squeezing it into single vector. However, from complex systems point of view, properties of a complex system are believed arise largely from the interaction among its components. In this paper, we analyze the intrinsic difficulty in graph classification under the unified concept of "resolution dilemmas" and propose "SLIM", inductive neural network model for Structural Landmarking and Interaction Modelling, to remedy the information loss in graph pooling. We show that, by projecting graphs onto end-to-end optimizable, and well-aligned substructure landmarks (representatives), the resolution dilemmas can be resolved effectively, so that explicit interacting relation between component parts of graph can be leveraged directly in explaining its complexity and predicting its property. Empirical evaluations, in comparison with state-of-the-ard, demonstrate promising results of our approach on number of benchmark datasets for graph classification.
INTRODUCTION
Complex systems are ubiquitous in natural and scientific disciplines, and how the relation between component parts gives rise to global behaviour of system is central research topic in many areas such as system biology (Camacho et al. 2018), neural science (Kriegeskorte) (015)., and drug and material discoveries (Stokes et al., 2020 Schmidt al.) 2019). Recently, graph neural networks provide a promising architecture for representation learning on graphs - the structural abstraction of a complex system. State-of-the-art performances
observed in various graph mining tasks (Bronstein
et al. 2017, Defferrard et al. 2016 Hamilton et al.) 20177] Xu et al. [019:] Velickovic et al.] 2017 Morris al. 2019 Wu et al. 2020; Zhou al.) 2018 Zhang al., 2020). However, due to the
non-Euclidean nature, important challenges still exist in graph classification. For example, in order to generate a -iee-diimesiooall representation for a graph of arbitrary size, graph pooling is typically adopted to summarize the information from each each node. In the pooled form, the whole graph is squeezed into a "super-node", in which the identities of the constituent sub-graphs and their inter- connections are mixed together. Is this the best way to generate graph-level features? From complex system's 's view, mixing all parts together might make it difficult for interpreting the prediction results, because properties of a complex system arise largely from the interactions among its components (Hartwell et al. 1999 Debarsy et al.) 2017 Cilliers 1998).
The choice of the "ccolapsingg" -tyle graph pooling roots deeply in the lack of natural alignment among graphs that are not isomorphic. Therefore pooling sacrifices structural details for feature (dimension) compatibility. Recent years, substructure patterns patterns"[drav draw considerable attention in graph mining, such as motifs (Milo et al. 2002 Alon 2007 Wernicke] 2006 Austin R. Benson] (0066) and graphlets (Shervashidze al. 2009). It provides an intermediate scale for structure comparison or counting, and has been applied to node embedding (Lee et al. [2019] Ahmed et al. (0118), deep graph kernels (Yanardag & Vishwanathan 2015) and graph convolution (Yang al. 2018). However, due to combinatorial nature, only substructures of very small size (4 or 5 nodes) can be considered (Yanardag)
Informally, substructure in this paper means connected subgraph and will be used interchargeably with it.

---

Under review as a conference paper at ICLR 2021
& Vishwanathan 2013
Wernicke 2006), greatl limiting the coverage of structural variations; also, handling substructures as discrete objects makes it difficult to compensate for their similarities, and so the risk of overfitting may rise in supervised learning scenarios (Yanardag & Vishwanathan 2015).
We view these intrinsic difficulties as related to resolution dilemmas in graph-structured data pro- cessing. Resolution is the scale at which measurements can be made and/or information processing algorithms are conducted, and here we will discuss two types of resolution and related dilemmas: the spatial resolution (dilemma) and the structural resolution (dilemma).
Spatial resolution relates to the geometrical scale of the "component" that can be identified from the final representation of graph (based which the prediction is performed). In GNN, since graph pooling compresses the whole graph into single vector, node and edge identities are mixed together and the spatial resolution drops to the lowest. We call this vanishing spatial resolution (dilemma). Structural resolution is the fineness level in differentiating between two substructures. Currently practice of exact matching makes it computationally intractable handle the exponentially many sub-gree sibbgrraphhhh instances, and the risk of overfitting may also rise as observed in deep graph kernels (Yanardag& Vishwanathan| (015)) and dictionary learning (Marsousi et al. 2014)) We will call this over-delicate substructure profiling an exploding structural resolution (dilemma). In fact, these two resolution dilemmas are not isolated. They have a causal relation and the origin is the way we perform identification and comparison of discrete substructures (more in Section 2.3
Our contribution. Inspired by the well-studied science of complex systems, and in particular the importance of the interacting relation between component parts of a system, propose a simple neural architecture called "Structural Landmarking and Interaction Modelling" - or SLIM. It allows graphs be projected onto a set of end-to-end optimizable, well-aligned structural landmarks, so that identities of graph substructures and their interactions can be captured explicitly to explain the complexity and improve graph classification. We show that, by resolving the two resolution dilemmas, and subsequently respecting the structural organization of complex systems, SLIM can be empirically very promising and offers new possibilities in graph representation learning.
In the rest of the paper, we will first define the resolution dilemmas of graph classification in Section 2 together with the discussion of related works. We then cover in Section 3 4 5 the design, analysis, and performance of SLIM, respectively. Finally, the last section concludes the paper.
2 RESOLUTION DILEMMAS IN GRAPH CLASSIFICATION
complex system often composed of many parts interacting with each other in a non- non-trivial way. Since graphs are structural abstraction of complex systems, accurate graph classification depends on how global properties of a system relate to its structure. believed that property of a complex system arises from interactions among its components (Debarsy et al.) [017] Cilliers 1998). Consequently, accurate interaction modelling should benefit prediction. However, it is non-trivia due to resolution dilemmas, as described in the following subsections.
2.1 SPATIAL RESOLUTION DIMINISHES IN GRAPH POOLING
Graph neural networks (GNN) for graph classification typically involves two key blocks, graph convolution and graph pooling (Kipf & Welling, 2017: [Hamilton et al. 2017 Xu et al.) (2019), at significantly different spatial resolutions. The goal of convolution is to pass information among neighboring nodes in the general form of
hg = A ( (fh,, u E NN,))
where N₂ is the neighbors of u (Hamilton et al. 2017 Xu et al. 2019). Here, the spatial resolution is controlled by the number of convolution layers: more layers capture lager substructures/sub-teer and 2019). In other words, the spatial resolution
can lead to improved discriminative power (Xu et al.) in the convolution stage can be controlled easily, and multiple resolutions may be even combined
together via CONCATENATE function (Hamilton et al. 2017 Xu et al. 2019) for improved modelling.
The goal of graph pooling is to generate compact, graph- or subgraph-level representations that are compatible across graphs. Due to the lack of natural alignment between non-isomorphic graphs, graph pooling typically "squeezes" a graph G into a single vector (or "super-node") in the form of hg READOUT ((J(h=), Vo E V)),
2

---

Under review as a conference paper at ICLR 2021
Diminishing Spatial Resolution
Rd
R
IRd
Graph pooling
Spatial
Resolution
Diminishes
Spatial
resolution Mode
Resolution
Preservable
Graph convolution
Figure I: Spatial resolution tunable in convolution phase (bottom, with 3 resolution level examples illustrated), but vanishes in the pooling phase (top, which mixes all the node vectors into one vector).
where V the vertex set of G. The readout functions include: max-pooling (Cangea et al. 2018). sum-
pooling (Xu et al. 2019), some other pooling functions (Hamilton et al. 2017). or deep sets (Zaheer
et al.
2017); attention has been used to evaluate node importance in attention pooling (Lee et al.
2019) and gPool (Gao Ji 2019); hierarchical pooling has also been investigated (Ying et al. 201 2018). The spatial resolution drops significantly in graph pooling, shown in Figure Since all the nodes (and their representation) are mixed into one vector, subsequent classifier can no longer identify any individual substructure regardless of the spatial resolution used in the convolution stage. We call this "diminishing spatial resolution". A diminishing spatial resolution will mix the identity of sub-structures (c.g., functional modules of molecule), making it non-trin non-trivial to trace the behaviour of the classifier back to meaningful parts the graph for interpretation.
2.2 STRUCTURAL RESOLUTION EXPLODES IN SUBSTRUCTURE IDENTIFICATION
Substructures are the basic unit to accommodate interacting relations. A global criterion to identify and align substructures the key to preserving substructure identities and comparing the inherent interactions across graphs. Again, the granularity in determining whether two substructures are "similar" or "different" is subject to wide spectrum of choices, which we call "structural resolution".
Generalization
performance
Exploding structural resolution
(Exact matching)
Structural Resolution
Low/coarse (underfit)
Medium
High/delicate (overfit)
Figure 2: Over-delicate structural resolution may hamper the generalization performance.
We illustrate the concept in Figure The right end denotes the finest resolution differentiating substructures: exact matching, as we manipulate motif/graphlet (Milo et al.) 2002 Alon 2007]] Wernicke 2006 Yang et al. 2018 Shervashidze et al., 2009). The exponential configuration of sub- graphs will finally lead to "exploding" structural resolution, because maintaining a large number of unique substructures is computationally infeasible, and easily overfits (Yanardag & Vishwanathan 2015). The left end of the spectrum treats all substructures the and underfits the data. We interested a medium structural resolution, where similar substructures are mapped to the same identity, which we believe can benefit the generalization performance (empirical evidence in Fig. 5)
3

---

Under review as a conference paper at ICLR 2021
Graph-1
Substructure distribution
Embedding space
"Landmark Graph
Graph-2
landmarks
Luxtrad MAyZ
B
Connected
Graph.2
Bivvv wxye
Substructure
Graph-p
Edges between sub structures not shown for visual darity
M
CH
Substructure Landmarking (similarity connection)
3. Identity Preserving Graph Pooling
1. Sub-structure Embedding:
(Graph-2 as example)
Figure 3: Three steps of the SLIM network. Sub-structure embedding: extract k-hop local sub- sub-graphs around each node and embed them new space. Substructure landmarking: compute sub-structure representatives through unsupervised clustering of sub-structures actoss graphs. ddentity-preservinn graph pooling: project each graph on the common set sub-structure landmarks for final prediction.
2.3 RELATION BETWEEN SPATIAL AND STRUCTURAL RESOLUTION DILEMMAS
The two resolution dilemmas have a causal relation, and logic chain as follows.
1. Due difficulty of characterizing discrete subgraphs, exact matching is typically adopted.
2. As result, exploding structural resolution (dilemma) is caused.
3. Such an over-delicate granularity makes it infeasible to compare substructure across graphs.
4. As a result, a collapsing- graph pooling has to be adopted that summarizes the whole graph into single vector, serving compatible graph-level features.
5. As result, vanishing spatial resolution (dilemma) caused finally.
Namely, the exploding structural resolution makes (collapsing-style) graph pooling an inevitable choice, which in turn leads to diminishing spatial resolution. Since the root cause of exploding structural resolution is how we typically manipulate discrete sub-structures, i.e., exact matching, we will replace it with structural landmarking in SLIM, so that both dilemmas are coordinately solved.
STRUCTURAL LANDMARKING AND INTERACTION MODELLING (SLIM)
The key idea of SLIM is compute landmarks (or representatives) from the distribution of sub- structures (embedded in a continuous space) across different graphs. By doing this, identification and comparison of sub-structures become much easier, and so an adentity-preservve graph pooling becomes applicable that explicitly models interaction between component parts of graph.
Problem Setting, Give a of labeled graphs {Gi, yn I for i 1, with each graph defined on the node/edge set G; (V,, E,) with adjacency matrix A; E Ruxx where
VVll and Vi E {+1}. Assume that nodes are drawn from e categories, and the node attribute matrix for G, is X; E Rnixe Our goal is train an inductive model to predict the labels of the testing graphs
The SL.MM network has three main steps: (1) substurcture embedding, (2) substructure landmarking, graph pooling, as shown in Figure 3 Detailed discussion follows.
and (3)
3.1 SUBSTRUCTURE EMBEDDING
The goal of substructure embedding is to extract substructure instances and embed them in a metric space. One employ multiple layers of graph convolution (Hamilton et al. 2017 Xu al. 2019)
4

---

Under review as a conference paper at ICLR 2021
to model substructures (in fact, rooted sub-trees growing from each node). In Figure B sub-graphn sub-graphs in each shaded circle represents a substructure instance associated with one atom.
More specifically, extract sub-gra sub-graph instance from each node using ht-hop breadth-fixg
search. Let A (8) be the hth -odder adjacency matrix, i.e., the py entry equals only node p and are within k-hops away. Since each sub-graph is associated with one node, the sub-graphs extracted from 9, can be represented as Z: = A, (A) X, whose jth row is c-dimensional vector summarizing counts of the node-types in the sub-grap -abbgrraphhh around the jth node. Again, different variations of graph convolution (Kipf & Welling 2017 Hamilton et al., 2017) can be adopted (see Appendix A
Next we consider embedding the substructure instances (i.e., rows Z 's) from each graph jointly into a latent space so that statistical manipulations become feasible. The embedding should preserve important proximity relations facilitate subsequent landmarking: if two substructures are similar, or they frequently inter-connect with each other, their embeddings should be close. In other words, the embedding should be smooth with regard to both structural similarities and geometrical interactions.
A parametric transform on Z''s 's with controlled complexity can guarantee the smoothness of embed- ding w.r.t. structural similarity, c.g., an autoencoder (with one hidden-layer as example)
(I) Here T and are the transform matrix and bias term of the autoencoder. Let H, = f(z,) E Rnd be the embedding of the n, sub-graph instances extracted from Gi- To maintain the smoothness of H,'s 's w.r.t. geometric interaction, we maximize the bog-likelihood of the co-occurrence of substructure instances in each graph, similar to word2vec (Mikolov al. 2013
(ZZ (Z, T b).
exp ( (j.)) (L.)))
max ΣΣΣ log
exp (H.(H) H.(l,,))
-IJ=LEEN
Here (j:))) is the jth row of H,, (.) is inner product, and Ai are the neighbors of node j in graph G, This loss function tends to embed strongly mntercconnettng substructures close to each other.
3.2 SUBSTRUCTURE LANDMARKING
The goal of structural landmarking is to identify set of informative structural landmarks in the continuous embedding space such that these landmarks have: (1) high statistical coverage, namely, they should faithfully recover distribution of the substructures from the input graphs, that can generalize them to new substructure examples from the distribution; and (2) high discriminative power, namely the landmarks should be able reflect discriminative interaction patterns for classification.
Let U = {1 .... pk} } be the set of structural landmarks. In order for them to be representative of the substructures from the input graphs, it is desirable that each sub-graph instance can be faithfully approximated by the closest landmark in U. Thus, we minimize the following distortion loss
n As
min 1.....KKKK
(H,(j:)) 1
Here H;(;:) denotes the jth row (substructure) from graph Gi. In practice, we implement soft assignment by using a cluster indicator matrix W, _ for each graph G., whose jk entry
is the probability that the jth substructure of Gú belongs to the ttth landmark μ4 Inspired by deep embedding clustering (Xie et al., 2016). W, is parameterized by a Student's 's t-distribution
Wi(jkk) = (1+ (j.)) 1 112/a)
(1+ (j.:) aa) T
and the loss function can be greatly simplified by minimizing the KL-divergence
W) W. k) W.). s.t. W.G. ΣN (W/,.M/E W((L
Σ KL W (W:
min U.H:'
(4)
Here, W, is a self-sharpening version of W. s. and minimizing the KL-distance forces each substruc- ture instance be assigned to only small number of landmarks similar to sparse dictionary learning. Besides the unsupervised regularization in 3 or 4 learning of the structural landmarks is also affected by the classification loss, guaranteeing the discriminative power of the landmarks.
5

---

Under review as a conference paper at ICLR 2021
3.3
GRAPH POOLING
The goal of identity-and-aa woand-inteaattionpreessee graph pooling is to project structural details of each graph onto the common space of landmarks, that a compatible, graph-level feature can be obtained that simultaneously preserves the identity of the parts (substructures) and models their interactions.
The structural landmarking mechanism allows computing rich, compatible graph-level features.
1. Substructure distribution in each graph. The density of the K substructure landmarks in graph 93 can be computed as
W 1 1m,11
P
2. First-order moment of substructures in each graph. The mean of the substructures belonging each of the K landmarks in graph 9j is
M, X W. P.
with P, dpag(p.): leth column of M, is the mean of sub sub-graphs with the kth landmark.
3. Sub-structure interaction in each graph. We can model how the K landmarks interact with each other in graph 9,. To do this, we can project the adjacency matrices A, 's onto the landmark sets and obtain an IR K* interaction matrix
C C:=W A; W
(7)
which encodes the interacting relations (geometric connections) among the K structural landmarks. We can further normalize this interaction as C, = P. C.P.
These features can be used together for final classification. For example, they can be concatenated to feed into fully-connected layer. One can also combine them together and transform each graph Gj into constant-sized "landmark" graph with node feature M, node weight pi, and edge weights C,. Then the standard graph convolution can be applied to the landmark graphs to generate graph-level features (without pains of graph alignment anymore). In experiments, we simply use normalized sub-structure interaction matrix C, (re-shaped vector) graph-level feature (more details in Appendix
We illustrate the architecture of SLIM in Figure 4 Here, the final graph features are fed into one fully-connected layer with dimension 64 for final prediction. Globally, the objective function includes the supervised part, namely the cross-entropy loss for classification, and the unsupervised part, namely the node2vee loss reflecting geometric connections between substructures within each graph, and the clustering loss reflecting the sub-structure similarity across different graphs. Weights for unsupervised loss terms and are and 10, respectively. More details are in Section
Graph
Equdion (5) (7)
Graph
Groph
preseiit graph pooling
Graph
Graph
Supervised loss
Groph
(cross entropy)
P: (density)
zjs sub-graphs
His
μl2 :
(mean)
Prediction
Autoencoder Figuation (1)
Landmarking (clustering)
C, (interaction)
FC-Layer
Mk landmarks
Subgraph embedding
projected graphs features
Unsupervised loss Fepation22. (4)
Exgation (5)- (7)
Equation (80-011
Figure 4: End-to-end training architecture of the SLIM network.
DISCUSSIONS
4.1 STRUCTURAL RESOLUTION FROM CODING PERSPECTIVE
The structural resolution is controlled by the landmark size K, which can be deemed as the number of basis in dictionary learning. Note that graphs can be considered constructed from (inter-connected)

---

Under review as a conference paper at ICLR 2021
substructure instances, each instance z represented by the landmarks as z Σx axdee In other words, the structural landmarks can be deemed as code vectors (or basis) in a dictionary.
In dictionary learning. it known that in general neither too small nor too large dictionary is desirable. A too small number of code-vectors fail to recover basic data structures, whereas too many basis may result in overfitting (Marsousi et al.) 2014). In particular, when the redundancy of the basis vectors, as measured by the "mutual coherence", " exceeds a certain range, the probability of a faithful signal recovery diminishes due to instability of sparse coding (Donoho & Huo. 2001 Mehta & Gray 2013).
We have very similar observations on the choice of structural resolution K. Note that in case of exact sub-structure matching, which corresponds to a maximal K due the combinitorial nature of substructures, the redundancy in structural landmarks increases significantly, which violates the recovery condition and leads to inferior performance. This why we prefer reasonable control on the structural resolution, in contrast to exact sub-structure matching as in graphlets or motif discovery. In the Appendix [ (Theorem D. we provide a more detailed theoretic analysis on how the mutual coherence of the structural landmarks depends on the choice of structural resolution K.
4.2 COMPARISON WITH RELATED METHODS
Graph Isomorphism. GNNs have great potential in graph isomorphism test by generating injective node embedding, thanks to the theoretic foundation in (Xu et al. 2019: Morris et al.) 2019). SLIM provides new insight here: (1) it finds a tradeoff' in handling similarity and distinctness; while graph isomorphism network (Xu et al. 2019) tries to discern even the slightest difference of sub-structures, SLIM network groups similar sub-structures (using tunable granularity), so that graphs can be projected onto structural landmarks; (2) it explores new ways of generating graph-level features: instead of aggregating all parts together, it taps into the vision of complex systems so that interaction relation is leveraged to explain the complexity and improve the learning (more in Appendix D..
Graphlets, Graph Kernels, and Embedding Methods. Graphlets and Graph kernels both exploit substructures to characterize graphs and their similarity. The SLIM network has some key differ- ences. First, we consider sub-structure landmarks that are end-to-end optimizable for generating discriminative, graph-level interacting patterns, while graph kernels or graphlets typically enumerate sub-structures offline. Second, SLIM models interaction between sub-structures, which is very different from graph kernels. Recently, Deep Divergence Graph Kernel -fo-Rfou al.) 2019) is proposed for unsupervised graph similarity learning. The authors designed isomorphism attention mechanism to compare nodes from source and target graphs, while SLIM uses global clustering across a batch of (training) graphs. Finally, embedding -ttpe type methods mostly focus on node- or edge-level representations (Mikolov et al. 2013 Ahmed et al.] [s18) more in Appendix [).
Other Aggregation or Pooling Methods. Hierarchical pooling (Ying et al. 2018 Gao & Ji 2019
Lee et al., (019 KKaaahhadi al., 2020) can exploit non-flat graph organization, but the final output is still in the form of a single, aggregated node vector. Sortpooling re-arranges graph nodes in a lincar chain and perform Id-convolution (Zhang al. [0188: SEED uses distribution of multiple random walks to capture graph structures (Wang et al.] 2019); Deep graph kernel evaluates graph similarity
by subgraph counts (Yanardag & Vishwanathan 2015). Explicit modelling of the interactionrelation
in graphs is still not considered in these approaches.
EXPERIMENTS
Benchmark data. We used the following benchmark data sets. (1) MUTAG: chemical compound with 188 instances and two classes; there are node/atom types. (2) PROTHINS: protein molecules with 1,113 13 instances and three classes/node-types (3) NCI1: chemical compounds for cancer cell lines with 4,110 instances and two classes. (4) PTC: chemical compounds for toxicology prediction with 417 instances and 8 classes. (5) D&D: enzyme classification with 1,178 instances and two classes. (6) IMDB-B: B: movie collaboration data set with 1,000 instances and two classes. (7) IMDB-M MM: movie collaboration data set with 1,500 instances and three classes. COLLAB: scientific collaboration network from 3 physics fields (classes). We list the detailed statistics of the graph data sets in Table
7

---

Under review as a conference paper at ICLR 2021
Table I: Statistics of the benchmark data-sets (bioinformatics & social-net).
Data
Num graphs
Classes
Node labels
Avg. nodes
Arg. edges
Class Ratio
MUTAG
7
17.93
1.9
PTC
344
2
19
14.29
14,69
1: 1.2
NCTI
37
29.
1:
Protein
1
2
3
39.06
72.82
1: 1,4
DD
1,178
2
82
284.32
715.66
1:4
IMD8-B
1000
1
19.77
96.53
1.0
IMDB-M
1500
1
13.0
65.94
1: 1.0
COLLAB
5000
1
74.49
2457.78
::1
Competing methods. We considered (1) Graph neural tangent kernel (GNTK) (Du et al. 2019); (2)
Graph Isomorphism Network (GIN) (Xu al. 2019); (3) End-to-end graph classification (DCGNN)
(Zhagg et al. 2018); (4) Hierarchical and differential pooling (DifiPool) (Ying et al. 2018: : (5) Self-
attention Pooling (SAG) (Lee et al. 2019); (6) Convolutional network for graphs (PATCHY-SAN)
(Niepert et al. 2016); (7) Graphlet kernel (GK) (Shervashidze et al. 2009): (8) Peesfeiler-Lehmar
Graph Kernels (WLGK) (Shervashidze al.) 2011): ; and (9) Propagation kernel (PK) (Neumann et al.)
2016). For method (7)) we directly cited their reported results due to unavailability of their codes; for other competing methods we run their codes and report the results.
Experimental setting. Following setting in (Xu et al. 2019) and (Niepert et al., 2016), we evenly split the data into folds and report the average and standard deviation of the accuracies of the 10 rounds. Our spatial resolution is controlled by BFS with 3 hops; the structural resolution is set to K = =000 Hyper-pane parammeeeeeter selection is based on small portion of the training splits as validation set, including: (1) the number of hidden units in the autoencoder Eq, [Ip is chosen from fd, d/2, 2d, 8, 16) where d is the input dimension the encoder; (2) the optimizer iS chosen from SGD and Adagrad, with learning rate {le 2, 5e 2, 1e 5e le 4); (3) local graph representation, including node distribution, layer-wise distribution, and weighted layer-wise summation (more Appendix A).
Structural Resolution. In Figure 5 we amine the performance of SLIM with different structural resolution (K). As can be seen, the accuracy curve is bell-shaped. When K is either
MUTAG data PTC
Accuracy
50
25
8
too small (underfitting) too large (coherent landmarks that overfit), the accuracy is inferior, and the best performance typically obtained around median K value. This justifies our con- jecture, as well as the usefulness of structural landmarking in improving graph classification.
220
500
K (strucutral resolution)
Figure 5: Accuracy vs structural resolution K.
Classification Performance. We compare the performance of different methods in Table 2 We use three social network data sets (IMDB- B, IMDBMM, COLLAB) and five bioinformat- ics data sets (MUTAG, PTC, NCI1 PROTEINS, DD). As can be seen, in Table 2 overall, neural network-based approaches are more competitive than graph kernels, except that graph kernels have lower fluctuations, and the WL-graph kernel per- form the best on the NCII dataset. For social network data, the SL.M network gains com- petitive score on IMDB-B and IMDB-M, but is worse the COLLAB. We speculate that social network data do not have node features and so the advantage of SLIM might be less significant. From Table 3 SLIM yields the highest average ranking among all the benchmark datasets.
1.0
0.9
0.2
Accuracy
0.2
0.d
0.5
GIN
0.4
GNTK
0.3
SLIM
0.2g
200
epochs
Figure 6: Algorithm stability on the Mutag
dataset. More examples in Appendix G
Algorithm Stability. In Figure 6 (more results in Appendix G. Figure 9., we plot the evolution of the testing accuracy versus the training epochs, so as to have a more comprehensive evaluation on algorithm stability. As can be seen, our approach has accuracy curve that converges relatively faster
8

---

Under review as a conference paper at ICLR 2021
Table 2: Averaged algorithm performance on benchmark data-sets (bioinformatics & social-net).
ALG.
MUTAG
PTC
NC11
Proiein
D&D
IMDB B
IMDB M
COLLAB
GK
81.38=11.74
05.65=00.46
62.49::0.27
01.39=0.31
74.38::0.69
63.87=0.98
43,89-20.38
72.84=0.28
PK
76.00:12..9
59.50=22.44
82.54:
73.68=00.68
78.25::0551
WLGK
84.11=1991 $7.97=2.49
84.46:1:0,45
74.68=0.49
08.34::0.22
73.40=4.63
49.33:44.75
79.02=11
PC-SAN
92.63444221
60.0024.82
78.39:11.80 1989
13.8922.76
17.12:2411
71:00:2..29
45.23 84
72 72.60=2.1
DOCNN
85.63:1:1.66
58.59:12.47
74.46:100.47
79.37::1.05
73.76=0.49
DilPool
90.52.1.3.98
76.53.1..23
75.82
78.95:1.2440 2.40
78.08.14.22
53.13.14.70
79.70 1.84
90.12:48..58
15.20:--1.53
75.61 24.24
79.42-4:2.18
76.90=3.60
52.80:1:4.60
SAG
73.53--9.66
09.67=+3112
74.18++1.229
71.86=0.97
76.91
78. 18.1004420
53, $3,80 08
79.88= 11.88-=10 1.02
GIN
90.03-+8.88
64.60:17.00
79.84:24.57
71.28 2.666-222665
71.58:22.94
75.10=5.110
52.30:
80.21=1.92
SLIM
93.28
74.41 6.992
80.53.12.01
77.47 1..47:14.34
2..61
80.20 2.10
54.00.14.00
78.22 2.00
Table 3: Averaged ranking of different algorithms on the 8 benchmark data-sets.
ALG.
WLGK
DGCNN
DifiPool
GNTK
Rank
8.7
6.4
5.6
3.8
5.8
4.1
3.7
4,7
4.6
1,9
and remains more stable with respect to the epochs. This signifies small variance during the training process and makes it practically easy to determine when to stop training. Other GNN algorithms can also attain high accuracy on some of the benchmark datasets, but the prediction performance fluctuates significantly across the training epochs (even by using very large mini-batch sizes). In such cases, determining when to stop can be challenging. We speculate that stability of the SL.M network arises from explicit modelling of the sub-structure distributions. In Figure note that on the MUTAG data the proposed method produces classification with 100% accuracy on more than half of the runs across different folds, and converges to the perfect classification steadily. demonstrates the power of the SLIM network in capturing important graph-level features.
6 it is also worthwhile to
Accuscy
Spotisl hesokutoonkkhop
The wiggh hockivec Ios
The Degght chaleing Ioo
(a) Impact of spatial resolution.
(b) Impact of node2vec loss
(c) Impact of clustering loss
Figure 7: Impact of spatial resolution and the unsupervised losses on the prediction result.
Impact of Spatial Resolution and Unsupervised Loss. Impacts of spatial resolution and unsuper- vised loss are shown in Figure 7 In Figure 3-hop sub-graphs tend to be a good choice for spatial resolution in bioifnormatics data. This could be consistent with the scale of meaningful functional modules in molecule. Figure (t)) and (c), both the node2vec loss (2) and the clustering loss (4) are shown to benefit prediction with properly chosen weight. As expected, the node2vec loss promotes smoothness of embedding with regard to geometric interactions between sub-structures, while the clustering loss tends promotes more "frequent" sub-structure representatives as the landmarks, thus making things more stable. Overall, the unsupervised loss serves as a regularization benefit the learning task, and we will perform more in-depth studies in future research.
CONCLUSION
Graph neural networks provide a popular state-of of-the-art computational architecture for graph mining. In this paper, we designed the SLIM network that employs structural landmarking to resolve resolution dilemmas in graph classification and capture inherent interactions in graph-structured systems.

---

Under review as a conference paper at ICLR 2021
Encouraged by the promising experimental results, we expect this attempt to open up possibilities in designing GNNs with informative structural priors.
REFERENCES
Nesreen K. Ahmed, Ryan Rossi, John Boaz Lee, Theodore L. Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. Learning role-based graph embeddings. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2018.
Rami A1-Rfou, Dustin Zelle, and Bryan Perozzi. Ddgk: Learning graph representations for deep
divergence graph kernels. In Proceedings of the 2019 World Wide Web Conference, 2019.
Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8:450-461, 2007.
Jure Leskovec Austin R. Benson, David F. Gleich. Higher-order organization of complex networks. Science, 353:163 166, 2016.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7: 2399-2434, 2006.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, pp. 18 18-42, 2017.
D.M. Camacho, K.M. Collins, R.K. Powers, J.C. Costello, and J.J. Collins. Next-generation machine learning for biological networks. Cell, 173(7):1811-122 2018.
C. Cangea, P. Velicković, N. Jovanović, T. Kipf P., and Lió. Towards sparse hierarchical grap classifiers. In preprint arXiv:1811.01287 2018.
Paul Cilliers. Complexity and Postmodernism: Understanding Complex Systems. Psychology Press. 1998.
Adam Coates and Andrew Y. Ng. Learning feature representations with k-means. Neural Networks: Tricks of the Trade, pp. 561 580, 1993.
Nicolas Debarsy, Stéphane Cordier, Cem Ertur, François Nemo, Déborah Nourrit-Lucas, Gérard Poisson, and Christel Vrain. Understanding Interactions in Complex Systems, Toward a Science of Interaction. Cambridge Scholars Publishing, 2017.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29, pp. 1884-38522
Curran Associates, Inc., 2016.
D. I.. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory, 47:2845-2862. 2001.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems 32, pp. 5723-5733, 2019.
H. Gao and S. Ji. Graph u-net. In Proceedings of the 36th International Conference on Machine Learning, 2019.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, 2017.
L.H. Hartwell. J.J. Hopfield, S. Leibler, and A.W. Murray. From molecular to modular cell biology. Nature, 2:47-52, Dec 1999.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Leel, and Quaid Morris. Memory- based graph networks. In International Conference on Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2021
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Nikolaus Kriegeskorte. Deep neural networks: A new framework for modeling biological vision and brain information processing. Annual Review of Vision Science, 1:417-446, 2015.
J.B. Lee, R.A. Rossi, Xiangnan Kong, X. Kong, E. Koh S. Kim, and A. Rao. Graph convolutional networks with motif-based attention. In Proceedings of the 28th ACM International Conference Information and Knowledge Manugement, pp. 499-508, 2019.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. self-attention graph pooling, In International Confer- ence of Machine Learning, pp. 3734 3743, 2019.
Mahdi Marsousi, Kaveh Abhari, Paul S. Babyn, and Javad Alirezaie. An adaptive approach to learn overcomplete dictionaries with efficient numbers of elements. IEEE Transactions on Signal Processing. 62(12):3272 - 3283, 2014.
Nishant A Mehta and Alexander G. Gray. Sparsity-basee generalization bounds for predictive sparse coding. In Proceedings of the 30th International Conference on International Conference on Machine Learning, pp. 36 44, 2013.
Tomas Mikolov, 1lya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed represen- tations of words and phrases and their compositionality. Neural and Information Processing System, 2013.
R. Milo, S. Ohen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon. Network motifs: Simple building blocks of complex networks. In Science, pp. 224-827,1 2002.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty- third AAAI Conference on Artificial Intelligence, 2019.
M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102(():209 245,, 2016.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In In Proceedings of The 33rd International Conference on Machine Learning, 2016.
Vitaly Maiorov Ron Meir. Distortion bounds for vector quantizers with finite codebook size. IEEE Transactions on Information Theory, 4565):1621 1648, 1999.
Jonathan Schmidt, Mário R. G. Marques, Silvana Botti, and Miguel A. L. Marques. Recent advances and applications of machine learning in solid-state materials science. NPJ Computational Material, 5:1581-1592, 2019.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume 5, pp. 488-495, 2009.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Efficient graphlet kemnlls for large graph comparison. In David Dyk and Max Welling (eds.), Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pp. 488-495, 16-18 Apr 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhom. and Karsten M. Borgwardt. Weisfeiler.Ichman graph kernels. Journal of Machine Learning Research, 12(77): 2539-2561, 201
11

---

Under review as a conference paper at ICLR 2021
Jonathan M. Stokes, Kyle Swanson Kevin Yang, Wengong Jin, Andres Sobillos-RRizz Nina M. Donghia, Craig R. MacNair, Shawn French, Lindsey A. Carfrae, Zohar Bloom-Ackermant Victoria M. Tran, Anush Chiappino-Pepe, Ahmed H. Badran, lan W. Andrews, Emma J. Chory, George M. Church, Eric D. Brown, Tommi S. Jaakkola, Regina Barzilay, and James J. Collins. A deep learning approach to antibiotic discovery. Cell, 180(4):688-702, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2017.
Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Song, Haifeng Chen, and Yun Fu. Inductive and unsupervised representation learning graph structured objects. International COnference on Learning Representations, 2019.
S. Wernicke. Efficient detection of network motifs. JEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):347-335) 2006.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Xie, R. Girshick, and A. Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Learning Representations, 2016.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Pinar Yanardag and SVN V N Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Carl Yang, Mengxiong Liu, Vincent W. Zheng, and Jiawei Han. Node, motif and subgraph: Lever- aging network functional blocks through structural convolution. In IEEE/ACM International Conference on Advances Social Newworks Analysis and Mining, 2018
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Proceedings the 32nd International Conference on Neural Information Processing Systems, pp. 4805-4815 15, 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances Neural Information Processing Systems 30, pp- 3391-3401. Curran Associates, Inc., 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning archi- tecture for graph classification. In The Thirty-Secome AAAI Conference on Artificial Intelligence, 2018.
Z. Zhang, P. Cui, and W. Zhu. Deep learning graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. In ArXiv. Arixv, 2018.
A REPRESENTATION OF SUBSTRUCTURES
As we have discussed in Section 3.1 the simplest form for quantifying a sub-graph is
Z, = A,X;
(8)
Here we list few simple variations used for representing the sub-graph that is grown from each node, including (1) emphasize the center node,
Z: [ A
12

---

Under review as a conference paper at ICLR 2021
inspired by (Xu et al. 2019;; (2) layer- wise node type distribution
Z, [A, X;; A (2) X.; A (2) X
(10)
(1) summation
where A specifies whether two nodes in Gj are exactly k- away, or (3) weighted Layer-wise
Z: = a2
X
(11)
where Ogg are non-negative weighting that decays with k, which is a more delicate summary of node-type distributions each layer of BFS.
B MUTUAL COHERENCE OF STRUCTURAL LANDMARKS
In the following, we quantify a lower-bound of the coherence as a factor of the landmark size K in clustering- -ased basis selection, since the sparse coding and k-means algorithm generate very similar code vectors (Coates & Ng 1993).
Theorem 1. The lower bound of the squared mutual coherence of the landmark vectors increases monotonically with K. the number of landmarks in clustering maastering-base based sparse dictionary learning.
4C,Cp
(²(()) 2
1
+1
2
Kd
mas
Here, d is the dimension, Ca Th5 (ogldd())/d) vaVa. where T d log(d log(d)) and Va ())) /dr(()(()))))))))))))))))) is the volume of the d-dimensional unit ball; Uman is the maximum tz-norm of (a subset) of the landmark vectors p4 's, and CG is a factor depending data distribution p(-).
Proof. Suppose we have n spatial instances embedded in the d-dimensional latent space as {z,, 22,2... ), and the landmarks (or codevectors) are defined f1,42 --- PK-- Let p(z) be the density function of the instances. Define the averaged distance between the instance and the closest landmark point
Me(i)]l2
(12)
where c(1) is the index of the closest landmark to instance i. As expected, s will decay with the number of landmarks with the following rate (Ron Meir 1999)
(1(K)
$
K
$ CdCp
+1
K K-a
(13)
2
where Ca is dimension-dependee factor Ca 3/8
[1+
d
Ya. with Va / the
volume of the unit ball in k-dimensional Euclidean space and Ya 1 1 doog(d (d)); Cp
(Jz(z)
factor depending on the distribution p.
Since is the average distortion етror, we can make sure that there exists non-empty subset of instances S2 such that ||z, Me(e) ll s for Ωg. Next we will only consider this subset of instances and the relevant set of landmarks will be denoted by Ω., For the landmarks μ4, E P.,, make a realistic assumption that there are enough instances so that we can always find one instance falling in the middle of μd and its closest landmark neighbor up. In this case, have then bound the distance between the closest landmark pairs as
||p - Hgl| < I|p - z||2 + ||m - z||2 $ 2s.
For any such pair, assume that the angle spanned by them is Opg. we can bound the angle between the two landmark vectors by
sin (0pg) 5 ||pl|
(14)
13

---

Under review as a conference paper at ICLR 2021
Let Umaz max EQ, l|p 12, finally low-bound the normalized correlation between close landmark pairs, and henceforth the coherence of the landmarks, as
1 (2) 2
max cos c (8py)
p.gelty
max - sin? (0pa) p.gell.
482 maa
(1())*
K
K 2
+1
maz
This indicates that the squared mutual coherence of the landmarks has a lower bound that consistently increases when the number of the landmark vectors, K, increases in dictionary learning process.
This theorem provides important guidance on the choice of structural resolution. It shows that when a clustering-based dictionary learning scheme is used to determine the structural landmarks, the size of the dictionary K can not be chosen too large; or else the risk of overfitting can be huge. Note that exact sub-structure matching as is often practiced in current graph mining tasks corresponds to an extreme case where the number landmarks, K, equals the number of unique sub-structures; therefore it should be avoided in practice. The structural landmarking scheme is a flexible framework to tune the number of landmarks, and to avoid overfitting.
C CHOICE OF SPATIAL AND STRUCTURAL RESOLUTIONS
The spatial resolution determines the "size" of the local sub-structure (or sub-graph), such as func- tional modules in molecule. Small strbstuuutures can be very limited in terms of their representation power, while too large sub-structures can mask the right scale of the local components crucial to the learning task. An optimal spatial resolution can be data-dependent. In practice, we will restrict the size of the local sub-graphs to 3-hop BFS neighbors, considering that the "radius" of the graphs in the benchmark data-sets are usually around 5-8. We then further fine-tune the spatial resolution by assigning non-negative weighting code in the local subgraph. Such weighting is shared across all the sub-graphs and can be used to sub-graph. The weighting be chosen
the nodes residing different layers from the central
adjust the importance of each layer of the monotonously decaying function, or optimized through learning.
The choice of structural resolution has similar flavor in that too small or too large resolutions neither desirable. On the other hand, it can be adjusted conveniently by tuning the landmark set size K based on the validation data. In experiments, K can be chosen by cross validation; for simplicity, we fix K 100.
Finally, note that geometrically larger substructures (or sub-graphs) are characterized by higher variations among instances due to the exponential amount of configuration. Therefore, the structural resolution should also commensurate with spatial resolutions. For example, substructures constructed by 1-hop-BF' may use a smaller landmark size K than those with D-hop-BFS. In our experiments we not consider such dependencies yet, but will study in our future research.
D HIERARCHICAL VERSION
D.1 SUBTLETY IN SPATIAL RESOLUTION DEFINITION
First we would like to clarify a subtlety in the definition of spatial resolutions. In physics, resolution is defined as the smallest distance (or interval) between two objects that can be separated; therefore it must involve two scales: the scale of the object, and the scale of the interval. Usually these two scales are proportional. In other words, you cannot have large intervals and small objects, the opposite (a small interval and large object). For example, in the context of imaging, each object is a pixel and the size of the pixel is the same the interval between two adjacent pixels.
14

---

Under review as a conference paper at ICLR 2021
In the context of graphs, each object is sub-grapl, centered around one node, whose scale is manually determined by the order of the two sub- -obbpaaphs may be smaller than the size of the sub uub-graph. For example, two nodes i and j are direct neighbors, and each of them has a 3-hop sub-graph. Then, the interval between these two subgraphs, if defined by the distance between and j, will be 1-hop; this is smaller than the size of the two sub-graphs, which is 3-hop. In other words, the two objects/subgraphs indeed overlap with each other, and the scale of the object and the scale of the interval between objects is no longer commensurate (large objects and small interval in this scenario).
centered around that node. Therefore, the interval between
This scenario makes it less complete define spatial resolutions just based on the size of the sub- graphs (as in the main text), since there are actually two scales to define. To avoid unnecessary confusions, we skip these details. practice, one has two choices dealing with the discrepancy: (1) requiring that the around each node; instead, we just explore a subset of the srthhggrahs. This can be implemented in hierarchical version which we discuss in the next subsection; (2) we still allow each node to have a local sub-graph and study them together, which helps cover the diversity of subgraphs since theoretically, an ideal choice of the subgraph is highly domain specific and having more sub -gagph examples gives a better chance to include those sub-gray sub-graphs that are beneficial to the prediction task.
are not overlapping. i.e., we do not have to grow one k-hop subgraph
D.2 HIERARCHICAL SLIM
We can implement hierarchical version of SLIM so that sub sub-graphs of different scales, together with the interacting relation between sub-graphs under each scale, can be captured for final prediction. Note that in (Ying et al., 2018) a hierarchical clustering scheme is used to partition one graph, in a bottom up manner, to less and less clusters. We can implement the same idea and construct a hierarchy of scales each of which will host number of sub-structures. The structural landmarking scheme will be implemented in each layer of the hierarchy to generate graph-level features specific to that scale. Finally these features can be combined together for graph classification.
E SEMI-SUPERVISED SLIM NETWORK
The SLIM network is flexible and can be trained in both fully supervised setting and semi-supervised setting. This is because the SLIM model takes a parametric form and so is inductive and can generalize to any new samples; on the other hands, the clustering- based loss term in (4) can be evaluated on both labeled samples and unlabeled samples, rendering the extra flexibility to look into the distribution of the testing sample in the training phase, if they are available. This is in flavor very similar to the smoothness constraint widely used in semi-supervised learning, such as the graph-regularized manifold learning (Belkin et al. 2006). Therefore, the SLIM network can be implemented in the following modes
Supervised version. Only training graphs and their labels are available during the training phase, and the loss function 44) is only computed on the training samples.
Semi-supervised version. Both labeled training graphs and unlabeled testing graphs available. The loss function 4 will be computed on both the training and testing graphs wile the classification loss function will only be evaluated on the training graph labels.
F INTERPRETABILITY
The SLIM network not only generates accurate prediction in graph classification problems, but can also provide important clues on interpreting the prediction results, because the graph-level features in SLIM bear clear physical meaning. For example, assume that we use the interaction matrix C; for the 7th graph G. as its feature representation; and the pg entry then quantifies the connectivity strength between the th sub-structure landmark and the 9th structure landmark. Then, by checking the K2 2 dimenssionl model coefficients from the fully-connected layer, one can then tell which subset of substructure-ae con.tttciitotniiiiiiiiii..y.yyyy (i.e., two substructures directly connected in graph) is important in making the prediction. To improve the interpretability one can further imposes a sparsity constraint on the model coefficient.
15

---

Under review as a conference paper at ICLR 2021
Figure Two pairs of molecules from different classes MUTAG data, with their respective instamcctre-interacto---teee marked on top of the learned structural landmarks. Red and blue colors signify the class labels.
In traditional graph neural networks such as GraphSAGE of GIN, node features are transformed through many layers and finally mingled altogether through graph pooling. The resultant graph-level representation, whose dimension is manually determined and each entry pools the values across all the nodes in the graph, can be difficult to interpret.
In Figure 8, we illustrate the sub-structure embedding and learned landmarks of SLIM network on the MUTAG dataset. Here, molecules belonging to different classes marked with red and blue edges. As can be observed, the sub-structures landmarks can generate highly discriminative features for graph classification; furthermore. by examining the substructure instances associated with each landmark, domain experts can acquire valuable clues for interpretating the underlying mechanism of classification. In fact, discriminative roles of the landmarks can be discriminative by being associated with one class more often than the other. Second, even in scenarios where both classes may share some common sub-structure landmarks (which is possible in molecules due to some common functional modules), the interacting pattern defined among the landmarks can still serve as an effective discriminator. We believe the dual discriminating mechanism using structural landmarks can be quite desirable in solving difficult graph classification problem, which we will investigate in more detail in our future studies.
two-fold. First, landmark themselves
G ABLATION STUDY (TEST ACCURACY EVOLUTION)
G.1 ALGORITHM STABILITY
Here we have reported the evolution of the testing accuracies for a number of competing algorithms more all the benchmark training data, in Figure
G.2 TIME COMPLEXITY
We also report the relationship between the accuracy and time of SLIM and several other methods to complete 200 epochs on the MUTAG and PTC data sets. As in Figure IO The accuracy of our method is better than most methods on the two data sets, When running for 200 epochs, our method is faster than most methods on the MUTAG data set. The time cost our approach mainly on the calculation of spatial resolution, structural resolution and back propagation when updating model parameters. Assuming that the size of each mini-batch size is n, the average number of nodes each graph is m, and each batch is running for all nodes in the graph to establish the computational spatial resolution required Onnm [Wg]) time, where [N is the averaged --hoo-neighhor size. Considering that DEC clustering is needed to calculate the structural resolution, this part needs to minimize the KL divergence between and the auxiliary target distribution, assuming bn is the number landmarks, the time complexity is only O(um ko).
16

---

Under review as a conference paper at ICLR 2021
Accurso
Accurat)
Accuraay
DocI
44
SAG
SAG
SAG
SUM
SUM
(a) NCI data.
(b) Protein data.
D&D data.
Acorra))
Accuracy
Accuracy
CNVY 0A5 S11
GIN CITT SUM
GH
SUM
020
epochs
epochs
spachs
PTC data.
(e) IMDB-B data.
IMDB-M data.
Figure 9: Testing accuracy of different algorithms over the training epochs.
Table Performance of SLIM using different final graph features.
feature
MUTAG
PTC
NCTI
Protein
D&D
IMDB
IMDB-M
COLLAR
SLIM-GNN
92.11=22.7
72.3224.16
80.44:2.005
71:21:1499
79.61=2.66
78.40:1112
$3.17433199
78.22:42.02
IM-Conccat
90.27:4-.12
70.28-17.25
79.21
75:35:13.27
79.0413.07
80.20
77.61:0077
SLIM-C
93.28-+3.36
74.41=6922
80.53:22.01
77.47+2.01
78.33#5.74
79.80+44221
53.20-24.36
76.38:11.45
H RICH GRAPH LEVEL FEATURES
The structural landmarking mechanism allows computing rich graph-level features by using different approaches to project structural details each graph onto the common space of landmarks.
SLIM-C. Using the (normalized) sub-structure interaction matrix for each graph its feature, as discussed in Section 3.3
SLIM-Concat.
Concatenating the density, mean, and interaction features discussed in Section 3 together (after re-shaping into vectors), One could also transform the interaction feature to a smaller matrix via bilateral dimension reduction before reshaped into a vector. Then fully connected layer follows for the final prediction.
SLIM-GA GNNN (Landmark Graph). Each graph G, can be transformed into landmark- -rapph a with fixed number K (landmark) nodes, with p, and C, quantifying the weight of each node and the edge between every pair of nodes, and M, the feature of each node (see definition in Section3.3). Then, this graph can be subject to a graph convolution such as D, M,M generate exeedddimensionl graph-level feature without having to take care of the varying graph size. We will study this in our future experiments. In Table 4 we compare the performance of using different features of the projected graph. Overall, interaction matrix C. = A, W/, which encodes the interacting relations (geometric connections) among the K structural landmarks are slightly better than GNN-features and concatenation features. except that SLIM-GNN have lower fluctuations. For most bioinformatics data, the SLIM-C gains competitive score on MUTAG, PTC, NCI and Protein data sets.
17

---

Under review as a conference paper at ICLR 2021
MUTAG vazime
PTC acc vs, time
0.9
0.0
0.3
57
0.0
4
MU
0.5
GNTX
GIN
GINTK
0.3
04
Attention
SUM
SLM
0.2g
205
400
902
200
1200
53
2003
400
000
592
(a) MUTAG data
(b) PTC data
Figure 10: Average wall-clock time comparisons of SLIM and other methods.
INTERACTION VERSUS INTEGRATION
The SLIM network and existing GNNs represent two different flavors of learning, namely, interaction modelling versus integration approach. Interaction modelling is based on mature understanding of complex systems and can provide physically meaningful interpretations or support for graph classification; integration based approaches bypass the difficulty of preserving the identity of sub- structures and instead focus on whether the integrated representation is an injective mapping, as typically studied in graph isomorphism testing.
Note that an ideal classification different from isomorphism testing and is not injective. good classifier, the goal of deciding which samples are similar and which are not are equally important. Here comes the tradeoff between handling similarity and distinctness. The Isomorphism-flawe GNN's aimed at preserving the differences between local sub-structures (even just very minute difference), and then map the resultant embedding to the class labels. Our approach. on the other hand, tries absorb patterns that are sufficiently close to the same landmark, and then map the landmark -aased features to class labels. In the latter case, the structural resolution can be tuned in flexible way explore different fineness levels, thus tuning the balance between "similarity" and "distinctness"; in the meantime, the structural landmarks allow preserving sub-structure identities and exploiting their interactions.
J COMPARISON WITH RELATED METHODS
Graph kernels are powerful methods to measure the similarity between graphs. The key idea is compare the sub-structure pairs from the graphs and compute the accumulated similarity, where examples of substructures include random walks, paths, sub-graphs, or sub-trees. Among them. paths/sub-grapheeee stochastic sequences (of nodes) in a graph.
are deterministic sub-structures in graph, while random walks
Although the SLIM network considers sub-structures basic processing unit, has a number of important differences. First, we consider sub-structure landmarks that are end-to-end optimizable, aimed at both reconstructing substructure distribution and generating discriminative interacting pattern for graph classification; while sub-structures in graph kernels graphlets are typically identified offline. Second, graph kernels measure similarity between all possible pairs of sub-structures across two graphs; while SLIM network models interaction between sub-structures, i.c., the functional organization of a graph, which is very different from graph kernels. Third, interpretation is challenging due to nonlinearity of kernel methods and exponential number of candidates in graphlets; while SLIM maintains a reasonable amount of discriminative "landmark" sub-structures easier to interpret.
In recent years, embedding algorithms have drawn considerable attention that transform nodes (or sub- graphs) into dimensiooii Euclidian space, as pionecred by the word-to- word-to-vector work (Mikoloy) et al. 2013). It is worthwhile to note that these algorithms focus node- edge-level embedding,
18

---

Under review as a conference paper at ICLR 2021
while our target is graph-level classification. As result, our approach emphasizes innovation in modelling the interacting relation between component parts of a graph, as inspired by the views from complex systems. In fact, our most important contribution lies exactly in learning substructure landmarks jointly across graphs to enable prreeetyp graph pooling. This is rarely consideration in algorithms whose main focus is just to embed the nodes sub-graphs.
the
Here we use Role2Vec (Ahmed et al. 2018) as an example to illustrate the similarity and difference between our approach and embedding-type methods. Similarity: both methods embed nodes or subgraphs, and consider high-order subgraph features. Differences: (1) Tasks are different; Role2 Vec node-level embedding, while ours is graph-level classification; (2) Data are different: Role2Vec focuses on single graph, we simultaneously handle many graphs, i.c., align sub-structures from different graphs and project each graph onto shared structural landmarks a new framework for graph pooling; (3) Methods are different; Role2Vec designs attributed random walk, we use KI. to fit substructure distribution; R2V finds subgraph motifs offline like in graphlets, we optimize discriminative substructure landmarks in an end-to-end fashion.
Recent years, various hierarchical pooling strategies (Ying et al. 2018 Lee et al. 2019; Khasahmadi et al. 2020) have been proposed to fully exploit non-flat graph organization and show promising results in graph classification. However, despite the hierarchical process that reduces the number of nodes layer by layer, the final representation is still in the form of single, aggregated node vector for feature compatibility, leading to potential loss of informative graph structural details. Note that hierarchical methods usually perform grouping inside each graph, while in approach the substructure landmarks are identified by jointly clustering the substructure instances across all the graphs. Therefore our landmark set size is typically larger than the number of clusters in hierarchical methods, in order to accommodate the diversity in sub-structure distribution. Note that some of the hierarchical methods need sort the nodes of the graph as a pre- pre-processing procedure (Ying et 2018 Khasahmadi et al. 2020).
We are also aware some other types of aggregation strategies: Sortpooling re-arranges graph nodes in a linear chain and perform Id-convolution (Zhang et al. 2018); SEED uses distribution of multiple random walks to capture graph structures (Wang al. 2019: Deep graph kernel evaluates graph similarity by subgraph counts (Yanardag & Vishwanathan, 2015), Again, explicit modelling of the interaction between constituent parts of the graph is not considered in these approaches.
19


Reviews:
[{"review_id": "iNSvPiMTZ3T", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe proposed SLIM algorithm organizes graph neural networks around substructures surrounding \"landmarks\" in the graph.  In addition to presenting the three steps of the SLIM algorithm (sub-structure embedding, sub-structure landmarking, and \"identity-preserving\" graph pooling), the authors compare to other approaches on a graph classification problem.  A large part of the paper is also given over to a high-level discussion of \"resolution dilemmas.\"\n\nThe idea of organizing around landmarks (and making the landmark choice a part of the optimization) is a nice one, and the new approach certainly seems to improve performance in the graph classification problem.  But I would have loved to see a more quantitative treatment of the \"resolution dilemmas.\"  All the ideas in this space involve lossy compression of the graph, and the authors characterize this in terms of loss of spatial resolution (ability to understand the \"high-level\" topology of the graph) or loss of structural resolution (ability to understand the prevalence of different types of local structures or motifs).  The attempt to balance these types of resolution concerns is the main motivation for the current paper.  But the discussion of these types of resolution is purely qualitative; the only place where there is really a quantitative discussion is in the experimental section in Figure 4.  Given the amount of space given over to discussing these different types of resolution, and the connections made (however briefly) to regularization ideas, I would have loved so see more of the discussion focus on how spatial and structural resolution can be measured, and how those measures might be used to guide the selection of algorithm hyper-parameters like the number of landmarks.\n\nThere is also a repeated statement that using substructure landmarks makes the representation easier to interpret.  This seems intuitive; but there are no examples illustrating such interpretability.\n\n### Typos\n\n- Abstract: \"iterpretable\"\n- Sec 2.1: \"tow key blocks\", \"capture lager substructures\"\n- Sec 2.2: \"Milo1, et al\"\n- Sec 3: \"sub-sturcture embedding\"\n- Fig 4: \"stuctutral resolution\"\n\n### Update\n\nThanks to the authors for their response to the reviews, and to the other reviewers for their comments as well.  It seems that we were all confused about many of the same things.\n\nThe authors have clarified some of the points raised, and I appreciate that.  I also continue to appreciate that the empirical results are promising.  At the same time, I personally remain confused about how to reason in a quantitative way -- suitable for diagnosing problems, determining hyperparameters, etc -- about the resolution tradeoffs that are described.  In other settings involving graph coarsenings, wavelets, graph Fourier transforms, etc, there is usually a more quantitative way of expressing what information is lost and retained by a given type of compression.  The discussion of coherence in the appendices says something about this, but not in a way that I would understand how to operationalize.\n\nI also appreciate that the chemistry example in the appendix exists, but I do not understand how to visually interpret the picture.\n\nMy recommendation remains a weak accept, as I think it is likely worthwhile to put the empirical results out in the world, and the theory may follow.  But I remain wary of my own lack of understanding of the theory in a quantitatively meaningful way, and would also welcome the chance to read a future version that had some of these aspects more clearly worked out and explained.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cK_4v1WfYvQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nAuthors introduces two new concepts spatial resolution and structural resolution in regards to understanding the graph structured data which are quite interesting and enlightening. Idea about projecting graph information \ninto structural landmarks is intriguing. To help make stronger case, I would suggest to do proper ablation study as it is not clear how much gain is coming unsupervised learning.\n\nPros:\nOverall I like intuition and the method about capturing the spatial resolution and structural resolution in a strategic manner. Author have some strong empirical performance especially on Protein, PTC and IMDB-M dataset.\n\nCons:\nAuthors argue that the classic graph neural networks which employ graph pooling operations are the bottleneck in identifying necessary substructures (or their interactions) for yielding high discriminative performance.  However, such statements are quite loose and need further theoretical justification given the fact graph pooling operations such as deepsets or sum-pooling are universal/injective functions in nature and thus can reflect any changes in the graph sub-structure (however their function smoothness or amount of representative power captured is entirely different issue).\n\nIt not clear why right hand side spectrum in Figure 2 will lead to lower generalization performance or over-fitting. Most of the time motifs/graphlets act as an atomic structure of a graph and their frequency distribution drives the discriminative performance.  As such identifying all such atomic structures should be helpful rather than harmful. It would be great if authors can expand on their explanation here and provide a real world example that would be more convincing to support their hypothesis. \n \nThere are certain paragraphs which are hard to read. For instance, Figure 1 lacks detail description and it is not clear what \"all the nodes are mixed into one\" means in the context. Also, a general suggestion would be to add more descriptive caption for each Figures in the paper.  \n\nI would suggest to provide compelling real-world examples (or do more qualitative analysis) besides the strong empirical performance in the main paper (there is some discussion in appendix but highlights can be included in the main context). \n\nAblation study is missing and thus hard to answer questions such as , is unsupervised learning (i.e., learning in Equation 2) even needed for getting strong results? I would really like to see the performance gains due to unsupervised learning.\n\nCan authors discuss the computation complexity of their method?\n\nTypos:\n\nVariables $T$, $b$ in equation (1) are not defined.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WKlGckq2I6f", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strengths\n\n1. This paper studied an important problem of graph mining on graph classification tasks by investigating the challenges that previous graph models encountered and solving them with the proposed method.\n\n2. The developed method is novel and interesting by proposing an inspiring concept called structural landmarking and capturing inherent interactions with it.\n\n3. The analysis and survey of related work with respect to the two mentioned resolution types is comprehensive.\n\n4. The paper is well written and easy to follow.\n\nWeakness\n\n1. The paper lacks enough analyses of behaviors of learned structural landmarks, with only an analysis of choices of their numbers.\n\n2. The time complexity of the developed method is not analyzed and its running time comparison with other baseline methods are also missing.\n\n3. The analysis of how the choices of each part of features learned in graph pooling would affect the results is missing.\n\n4. The experimental part lacks the analysis of why the method performs very well on some datasets while not performing well on others.\n\nSummary: This paper studies the problem of graph classification on chemical and social datasets. Existing graph classification methods with graph neural networks learn node embeddings via aggregation of neighbors and combine all node features into a final graph feature for classification, while such operations usually lack the ability for identifying and modelling the inner interactions of substructures. To remedy the information loss in graph pooling, the authors leverage the learned substructure landmarks to project graphs onto them for modelling the interacting relations between component parts of a graph. In this regard, an inductive neural network model for structural landmarking and interaction modelling is developed to resolve potential resolution dilemmas in graph classification and capture inherent interactions in graph-structured systems. Empirical experiments on both chemical and social datasets validate the effectiveness of the method. Generally speaking, the paper is well written and easy to follow, with clear motivation and organization. However, I have concerns about the lack of analysis for learned structural landmarks, since in the paper only the choice of its number is well discussed. Also, the time complexity of the developed method is not well studied. The detailed comments and suggestions of this paper are as follows.\n\n1.The paper proposes to learn structural landmarks and obtain representations of graphs by projecting them. Therefore, the quality of learned landmarks is crucial while the paper lacks enough analyses for them. I suggest providing a more comprehensive analysis for them.\n\n2.The proposed method generates various kinds of graph-level features while lacking enough analyses of their impacts on results. I suggest conducting more experiments of ablation study for this part.\n\n3.The detailed statistics of benchmark datasets are not mentioned such as the distribution of number of nodes in graphs.\n\n4.Although the results are competitive compared with other baselines, the authors didn’t explain why the method performs well on some datasets while not performing well on others. I suggest analyzing the reasons comprehensively.\n\n5.Only one evaluation metric is used in experiments, which is the accuracy. Since it’s a classification task, I suggest using various metrics to show the effectiveness.\n\n6.There are some typos in the paper that requires double checking: For example, \"breath-first search \" -> \"breadth-first search\", \"an molecule\" -> \"a molecule\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "EQzi_ra-YKQ", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==========Summary==========\n\nIn this paper, the authors investigate how to learn graph representations from structural landmarks. In particular, SLIM, an end-to-end trainable method, is proposed to simultaneously learn landmark and graph representations guided by downstream graph classification signals. Empirical results demonstrate the effectiveness of the proposed method on public benchmark datasets.\n\n==========Reason for the rating==========\n\nAt this moment, I am standing between 4 and 5. Overall, I feel the technique proposed in this paper is potentially interesting. However, its current presentation could also deliver quite confusing information. Hopefully, the authors could address my concerns in the rebuttal.   \n\n==========Strong points==========\n1. Structural landmark is an interesting idea to approach graph representation learning. This study goes beyond the assumption of \"bag of structures\", and investigates the angle of modeling interaction between discovered structures.\n\n2. The authors propose the SLIM framework that implements the proposed idea well.\n\n3. The provided empirical evidences suggest the SLIM technique is promising in graph classification tasks.\n\n==========Weak points==========\n1. The key insight \"resolution dilemma\" could be confusing. While one expects graph pooling causes the struggling between spatial and structural resolution, the two resolutions seem to be two orthogonal dimensions.\n    - The discussion on spatial resolution seems to be around the assumption for graph classification: bag of structures (BOS) or some more complex model that considers relations between discovered structures. Existing graph pooling methods mostly assume the BOS model, and develop different \"counting methods\" to generate one fixed-size vector for each graph. From the perspective of counting, it is difficult to see how existing pooling reduces spatial resolution, while indeed such pooling methods cannot consider relations between structures. Could the authors clarify what exactly \"diminish\" means in the context of \"spatial resolution\"?\n    - The discussion on structural resolution seems to be around model selection in terms of expressive power from learned representations: if we really can make a choice, which one could result in the most promising generalization performance. This problem is indeed meaningful, but it is not caused by pooling layers and is not necessary to address it at pooling layers.\n    - Overall, it is difficult to see the connection between section 2 and 3. After zooming into the two dimensions in section 2, they seem orthogonal, with weak coupling with pooling layers. The authors may need to provide stronger reasoning or evidences to motivate the proposed technique from the perspective of \"resolution dilemma\".\n\n2. The expressive power of substructure embedding could be a potential concern. Using $A^{(k)}$, different layouts within k-hops (k > 1) may not be able to be differentiated anymore. Does this imply different structures within k-hops do not matter?\n\n3. The presentation in section 3 could be further improved. \n    - The details on how to end-to-end train SLIM is missing in section 3, while one may find some relevant information in the experiment section. To make each section self-contained and the technique clearly described, the authors may put down the relevant contents in section 3.\n    - Section 3.3 is definitely critical in the whole framework; however, the current presentation could unnecessarily increase the difficulty in understanding the idea behind.\n\n==========Questions during rebuttal period==========\n\nPlease address and clarify the weak points above. \n\nIn addition, the current draft could use more proofreading to clear typos and grammar errors. The idea of landmark has also been discussed in a recent work [1], in the context of unsupervised learning. The authors may need to highlight their unique perspective.\n\n==========Reference==========\n[1] DDGK: Learning Graph Representations for Deep Divergence Graph Kernels, WWW 2019\n\n==========Post rebuttal comments==========\n\nThe rebuttal has addressed my main concerns. In general, I believe the core idea of modeling substructure interactions in GNNs should be shared in front of more audience. Therefore, I have increased the rating accordingly.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The proposed approach seems to have elements of novelty, it is well presented  and  reasonably motivated by the authors. In addition, empirical results seem to be promising. However, although rebuttal helped to clarify some of the pending issues, there are concerns on the fact that the raised issue about "resolution dilemmas" does not find in the paper a quantitative treatment. Without that, it is difficult to fully understand how to drive the learning of useful structural landmarks. Thus, notwithstanding the paper seems to contribute in a significant way to the advancement of the GNN field, it still needs additional work to better develop  the proposed concepts in a quantitative theory. 
Decision: Reject