Inductive and Unsupervised Representation Learning on Graph Structured Objects
Authors: Lichen Wang
Bo Zong
Qianqian Ma
Wei Cheng
Jingchao Ni
Wenchao Yu
Yanchi Liu
Dongjin Song
Haifeng Chen
Yun Fu
Venue:  (2020)
Keywords: Graph representation learning
Graph isomorphism
Graph similarity learning

Abstract: Inductive and unsupervised graph learning is a critical technique for predictive or information retrieval tasks where label information is difficult to obtain. It is also challenging to make graph learning inductive and unsupervised at the same time, as learning processes guided by reconstruction error based loss functions inevitably demand graph similarity evaluation that is usually computationally intractable. In this paper, we propose a general framework SEED (Sampling, Encoding, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. Instead of directly dealing with the computational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples a number of subgraphs whose reconstruction errors could be efficiently evaluated, encodes the subgraph samples into a collection of subgraph vectors, and employs the embedding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis, we demonstrate the close connection between SEED and graph isomorphism. Using public benchmark datasets, our empirical study suggests the proposed SEED framework is able to achieve up to 10% improvement, compared with competitive baseline methods.

Published as a conference paper at ICLR 2020
INDUCTIVE AND UNSUPERVISED REPRESENTATION LEARNING ON GRAPH STRUCTURED OBJECTS
Lichen Wang', Bo Zong", Qianqian Ma², Wei Cheng', Jingehao Ni², Wenchao Yu², Yanchi Liu², Dongjin Song", Haifeng Chen', and Yun Fu² Northheastern University, Boston, USA
2NEC Laboratories America, Princeton, USA "Boston University, Boston, USA
gma 11. com, maqq@bu. edu, yunfußece. nel.eeccceee.eddu.. wanglichenx i
[bzong, weicheng, jni, wyu, yanchi, dsong, heeegggeeeeeoeeeeeeaablllloa com
ABSTRACT
Inductive and unsupervised graph learning is critical technique for predictive or information retrieval tasks where label information difficult to obtain. is also challenging to make graph learning inductive and unsupervised at the same time, as learning processes guided by reconstruction error based loss functions inevitably demand graph similarity evaluation that is usually computationally in- tractable. In this paper. we propose a general framework SEED (Sampling, Encod- ing, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. Instead of directly dealing with the com- putational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples a number of subgraphs whose reconstruction errors could be efficiently evaluated, encodes the subgraph samples into a collection of subgraph vectors, and employs the embedding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis. we demonstrate the close connection between SEED and graph isomorphism. Us- ing public benchmark datasets, our empirical study suggests the proposed SEED framework is able to achieve up 10% improvement, compared with competitive baseline methods.
INTRODUCTION
Representation learning has been the core problem of machine learning tasks graphs. Given graph structured object, the goal to represent the input graph as a dense low-dimensional vec- tor so that are able to feed this vector into off-the-shelf machine learning or data manage- ment techniques for a wide spectrum of downstream tasks, such as classification (Niepert et al.) 2016), anomaly detection (Akoglu et al. 2015), information retrieval (Li et al. 2019), and many others (Santoro et al.) 2017b Nickel et al. 2015).
In this paper, our work focuses on learning graph representations in an inductive and unsupervised manner. As inductive methods provide high efficiency and generalization for making inference over unseen data, they are desired in critical applications. For example, that encodes graphs generated from computer program execution traces into vectors so that we can perform malware detection in a vector space. During real-time inference, efficient encoding and the capability of processing unseen programs are expected for practical usage. Meanwhile, for real-life applications where labels are expensive or difficult to obtain, such as anomaly detection (Zong al.) 2018) and information retrieval (Yan et al.) 22055,, unsupervised methods could provide effective feature representations shared among different tasks.
could train model
Inductive and unsupervised graph learning is challenging, even compared with its transductive or supervised counterparts. First, when inductive capability is required, it is inevitable to deal with the discover common patterns across graphs. Second, in
problem of node alignment such that the case of unsupervised learning, we have limited options to design objectives that guide learning processes. To evaluate the quality of the learned latent representations, reconstruction errors

---

Published as a conference paper at ICLR 2020
Encoding space
Output Vector Representation
Input Graph
Sampling
Encoding
Embedding Distribution
Figure 1: SEED consists of three components: sampling, encoding, and embedding distribution. Given an input graph, its vector representation can be obtained by going through the components.
commonly adopted. When node alignment meets reconstruction error, have to answer a basic question: Given two graphs Gj and G2, are they identical or isomorphic (Chartrand 1977 To this end, it could be computationally intractable to compute reconstruction errors (e.g.. using graph edit distance (Zeng et al. 2009) as the metric) in order to capture detailed structural information.
Previous deep graph learning techniques mainly focus transductive (Perozzi et al., 2014) pervised settings (Li et al. 2019). A few recent studies focus on autoencoding specific structures, such directed acyclic graphs (Zhang al., 2019), trees graphs that can be decomposed into trees (Jin et al.] (2018), and so on. From the perspective of graph generation, You et al. (2018) pro- pose generate graphs of similar graph statistics (e.g., degree distribution), and Bojchevski et al. 2018 provide a GAN based method to generate graphs of similar random walks.
In this paper, we propose general framework SEED (Sampling, Encoding, and Embedding Dis- tributions) for inductive and unsupervised representation learning graph structured objects. As shown in Figure [] SEED consists of three major components: subgraph sampling, subgraph encod- ing, and embedding subgraph distributions. SEED takes arbitrary graphs as input, where nodes and edges could have rich features, or have no features at all. By sequentially going through the three components, SEED outputs vector representation for input graph. One can further feed such vector representations to off-the-shelf machine learning or data management tools for downstream learning retrieval tasks.
Instead of directly addressing the computational challenge raised by evaluation of graph reconstruc- tion errors, SEED decomposes the reconstruction problem into the following two sub- brob-rro.ems...
Q1: How to efficiently autoencode and compare structural data in an unsupervised fashion? SEED focuses a class of subgraphs whose encoding, decoding, and reconstruction errors can be eval- uated in polynomial time. particular, we propose random walks with earliest visiting time (WEAVE) serving as the subgraph class, and utilize deep architectures efficiently autoencode WEAVES. Note that reconstruction errors with respect to WEAVES are evaluated in linear time.
Q2: How measure the difference of two graphs in tractable way? As one subgraph only covers partial information of an input graph. SEED samples number of subgraphs to enhance information coverage. With each subgraph encoded as a vector, an input graph represented by a collection of vectors. If two graphs are similar, their subgraph distribution will also be similar. Based on this intuition, we evaluate graph similarity by computing distribution distance between two collections of vectors. By embedding distribution of subgraph representations, SEED outputs a vector repre- sentation for an input graph, where distance between two graphs' vector representations reflects the distance between their subgraph distributions.
Unlike existing message-passing based graph learning techniques whose expressive power is upper bounded by Weisfeiler-Lehman graph kernels (Xu et al.) 2019; Shervashidze et al. 2011), we show the direct relationship between SEED and graph isomorphism in Section 3.5
We empirically evaluate the effectiveness of the SEED framework via classification and clustering tasks on public benchmark datasets. We observe that graph representations generated by SEED able to effectively capture structural information, and maintain stable performance even when the node attributes are not available. Compared with competitive baseline methods, the proposed SEED framework could achieve up 10% improvement in prediction accuracy. In addition, SEED
2

---

Published as a conference paper at ICLR 2020
achieves high-quality representations when reasonable number of small subgraph sampled. By adjusting sample size, we are able to make trade-off between effectiveness and efficiency.
2 RELATED WORK
Kernel methods. Similarity evaluation is one of the key operations in graph learning. Conventional graph kernels rely on handcrafted substructures or graph statistics to build vector representations for graphs (Borgwardt Kriegel 2005 Kashima et al., [2003] Vishwanathan al. 2010 Horváth al., 2004] SServashidze & Borgwardi]] [ Kriege et al. 2019). Although kernel methods are poten- tially unsupervised and inductive, is difficult to make them handle rich node and edge attributes in many applications, because of the rigid definition of substructures.
Deep learning. Deep graph representation learning suggests promising direction where one can learn unified vector representations for graphs by jointly considering both structural and attribute
information. While most of existing works are either transductive (Perozzi et al.] [014 Kipf &
Welling, 2016 Liu et al. 2018) supervised settings (Scarselli al., 2008 Battaglia et al. 20166]
Defferrard et al. 2016; Duvenaud et al. 2015 Kearnes et al.) 2016 Veličković et al., 2018 Santoro al. 2017a Xu et al.
2018 Hamilton et al. (017), few recent studies focus autoencoding
specific structures, such as directed acyclic graphs (Zhang et al.) 2019), trees or graphs that can be decomposed into trees (Jin al. 2018), and so on. In the case of graph generation. You et al. (2018) propose to generate graphs of similar graph statistics (e.g., degree distribution), and |Bojchevski et al. (208)) provide method to generate graphs of similar random walks. In addition, Li et al. (2019) propose a supervised method to learn graph similarity, and Xu et al. (2019) theoretically analyses the expressive power of existing message-passing based graph neural networks, Micali & Zhu (2016) propose anonymous walks for reconstruction tasks. It reconstructs a Markov process from the records collected by limited/partial observations. In an anonymous walk procedure, the states are visited according to the underlying transition probabilities, but no global state names are known. [vvanvv & Burnaev (218)) deploy anonymous walks crucial strategy for obtaining data- driven and feature-based graph representations. An efficient sampling approach is designed which approximates the distributions for large networks.
Unlike existing kernel or deep learning methods, our SEED framework is unsupervised with induc- tive capability, and naturally supports complex attributes on nodes and edges. Moreover, works for arbitrary graphs, and provides graph representations that simultaneously capture both structural and attribute information.
3 SEED: SAMPLING, ENCODING, AND EMBEDDING DISTRIBUTIONS
The core idea of SEED is to efficiently encode subgraphs as vectors so that we can utilize subgraph distribution distance to reflect graph similarity. We first give an abstract overview the SEED framework Section 3.1 and then discuss concrete implementations for each component Sec- tion 3.2 3.3 and] 3.4 respectively. In Section 3.5 share the theoretical insights in SEED. For the ease of presentation, we focus on undirected graphs with rich node attributes the following discussion. With minor modification, technique also handle directed graphs with rich node and edge attributes.
3.1 OVERVIEW
SEED encodes an arbitrary graph into a vector by the following three major components, as shown in Figure
Sampling. A number of subgraphs are sampled from an input graph in this component. The design goal of this component is to find a class of subgraphs that can be efficiently encoded and decoded so that we are able evaluate their reconstruction errors in a tractable way.
Encoding. Each sampled subgraph is encoded into a vector in this component. Intuitively, subgraph vector representation has good quality, should be able to reconstruct the original subgraph well based on the vector representation. Therefore, the design goal of this component is to find autoencoding system that provides such encoding functionality.
3

---

Published as a conference paper at ICLR 2020
Embedding distribution. A collection of subgraph vector representations aggregated into one vector serving as the imput graph's representation. For two graphs, their distance in the output vector space approximates their subgraph distribution distance. The design goal of this component is to find such aggregation function that preserves a pre-defined distribution distance.
Although there could be many possible implementations for the above three components, we propose a competitive implementation in this paper, and discuss them in details in the rest of this section.
3.2 SAMPLNGG
Vanilla random walk:
ba-b-a-a-b ba-b-a-a-b
2
G
H a
16
[
1b]
2
WEAVE:
0
Figure 2: Expressive power comparison between WEAVES and vanilla random walks: while blue and orange walks cannot be differentiated in terms of vanilla random walks, the difference under WEAVEs is outstanding.
In this paper, we propose to sample class of subgraphs called WEAVE (random Walk with EArliest Visit timE). Let be an input graph of node set (G) and an edge E(g). A WEAVE of length Ie is sampled from G as follows.
Initialization. A starting node (0) is randomly drawn from V(G) at timestamp 0, and its earliest visiting time is set O.
Next-hop selection. Without loss of generality, assume y(()) is the node visited at timestamp (0 S < k). We randomly draw node (((+)) from (PP)s one-hop neighborhood as the node to be visited at timestamp + 1. If ((++1) is node that we have not visited before, its earliest visiting time is set to + 1; otherwise, its earliest visiting is unchanged. We hop to v(++1)
Termination. The sampling process ends when timestamp reaches k.
In practical computation, a WEAVE is denoted as a matrix X = [x (2 {k) In particular, (p) [x x is concatenation of vectors, where x(?) includes attribute information for the node visited at timestamp p. and x((") contains its earliest visit time. As earliest visit time is discrete, we use one-hot scheme represent such information, where x(") is k-dimensional vector and (p) [4] 1 means the earliest visit time is timestamp q. If one aims to sample WEAVEs from an input graph, the output of this component
of matrices X2, X.).
Difference between WEAVES and vanilla random walks. The key distinction comes from the information of the earliest visit time. Vanilla random walks include coarser-granularity structural information, such as neighborhood density and neighborhood attribute distribution (Perozzi et al,, 2014). As vanilla random walks have no memory on visit history, detailed structural information related to loops or circles is ignored. While it is also efficient to encode and decode vanilla ran- dom walk, it is difficult to evaluate finer-granularity structural difference between graphs. Unlike vanilla random walks, WEAVEs utilize earliest visit time to preserve loop information in sampled subgraphs. As shown in Figure [ while we cannot tell the difference between walk wi and walk wy using vanilla random walk, the distinction is outstanding under WEAVEs. Note that it is equally efficient to encode and decode WEAVES, compared with vanilla random walks.
In addition, WEAVE is also related to anonymous random walks (Ivanov & Burnaev 2018 Micali
& Zhu 2016). By excluding attribution information, a WEAVE is reduced to an unonymous random
walk.

---

Published as a conference paper at ICLR 2020
3.3 ENCODING
Given a set of sampled WEAVES of length & (X1, X2,.., Xah. the goal is to encode each sam- pled WEAVE into dense low-dimensional vector. As sampled WEAVEs share length, their matrix representations also have identical shapes. Given a WEAVE X, one could encode it by an autoencoder (Hinton & Salakhutdinov 2006) as follows.
f(X; fe):
X - g=g(z;0)) fa).
(1)
where is the dense low-dimensional representation for the input WEAVE, f(-) is the encoding function implemented by an MLP with parameters O.. and g(-) is the decoding function implemented by another MLP with parameters Oz. The quality of is evaluated through reconstruction errors as follows.
C= |X -13
By conventional gradient descent based backpropagation (Kingma & Ba, 2014). one could optimize de and du via minimizing reconstruction error L. After such an autoencoder is well trained, the latent representation z includes both node attribute information and finer-granulariig structural information simultaneously. Given sampled WEAVEs of an input graph, the output of this component dense low-dimensional vectors {Z1, -2, }.
3.4 EMBEDDING DISTRIBUTION
Let G and H. be two arbitrary graphs. Suppose subgraph (e.g., WEAVE) distributions for 9 and H Pg and Py, respectively. In this component, we interested in evaluating the distance between Pg and Pv. In this work, we investigate the feasibility of employing empirical estimate of the maximum mean discrepancy (MMD) (Gretton et al.) (2012) evaluate subgraph distribution distances, without assumptions on prior distributions, while there are multiple candidate metrics for distribution distance evaluation, such as KL-divergence (Kullback & Leibler 195T) and Wasserstein distance (Arjovsky et al. 2017). We leave the detailed comparison among different choices of distance metrics our future work.
Given subgraphs sampled from G as {z.,.... z.} and s subgraphs sampled from H. as h2), (h,,".,
we can estimate the distance between Pg and PH under the MMD framework:
MMD(Pg,PM) PH) s(3 1)
k(2,, 2,) + s(8 1) 1=1 jzt
kh, hy)
1=1 34
k(Zz: hy)
= =11Øg - أ 1
jág and foz are empirical kernel embeddings Pg and Ph. respectively, and are defined as follows,
igg
(Z.)).
+ ((h)),
(4)
where (b()) is the implicit feature mapping function with respect to the kernel function k(;;)). To this end, Ag and füx are the output vector representation for G and H. respectively.
In terms of kernel selection, we find the following options are effective in practice.
Identity kernel. Under this kernel, pairwise similarity evaluation is performed in the original input space. Its implementation simple, but surprisingly effective in real-life datasets,
Zi
iux
(5)
where output representations are obtained by average aggregation over subgraph representations.
Commonly adopted kernels. For popular kernels (e.g., RBF kernel, inverse multi-quadratics ker- nel, and so on), could be difficult to find and adopt their feature mapping functions, While approx- imation methods could be developed for individual kernels (Ring & Eskofier 2016), could train
5

---

Published as a conference paper at ICLR 2020
deep neural network that approximates such feature mapping functions. In particular,
Big
Öizz Om),
ilu Σ (lh,5
D(Pa, Px) - 11A6 plvll2.
(6)
where o(: mm) is an MLP with parameters 6m and D(:,)) is the approximation to the empirical estimate of MMD. Note that ilg and f4 output representations for & and H. respectively. To
train the function (6; 0, we evaluate the approximation error by
J(Om) PD P+) MMD(Ps
where pm is optimized by minimizing J (0m).
3.5 THEORETICAL INSIGHTS
In this section, we sketch the theoretical connection between SEED and well-known graph isomor- phism (Chartrand] 1977). and show how walk length in WEAVE impacts the effectiveness in graph isomorphism tests. The full proof of theorems and lemmas is detailed in Appendix.
To make the discussion self-contained, we define graph isomorphism and its variant with node at- tributes as follows.
Graph isomorphism. G = (V(g), and H = (V(H), E(H))) are isomorphic if there is a bijection function f V(g) + ((H) such that V(u, E E (f f(), E(H).
Graph isomorphism with node attributes. Let 9 two attributed graphs, where I 12 are attribute mapping functions 1 V(g) + Rd 12 VHH) Rdd and node attributes are denoted as d-dimensional vectors. Then G and H are isomorphic with node attributes if there is a bijection f VG) 4+ V(H), s.t., V(u,v) E(G) + (f(u), f(v) E(H), and Vu E ( (u) = (2(f(w)).
H. - E(H)), be
Identical distributions. Two distributions P and Q identical if and only if their 1st order Wasserstein distance (Rüschendorf 1985) (P Q) = 0.
The following theory suggests the minimum walk length for WEAVEs, if every edge in graph is expected to be visited.
Lemma 1. Let g (V(g), E(G) be connected graph, then there exists walk of length k which can visit all the edges of G. where k: 2 2|E(G)| - 1.
Now, we ready present the connection between SEED and graph isomorphism.
Theorem 1. Let G = (V) E(G)) and H = (V(H), E(H)) be two connected graphs. Suppose we can enumerate all possible WEAVEs from and H. with a fixed-length k. 2 max{[E(G)) [EH)) where each WEAVE has a unique vector representation generated from a well-trained autoencoder. The Wasserstein distance between G 's and H's WEAVE distributions 0 if and only if and H are isomorphic.
The following theory shows the connection in the case of graphs with nodes attributes.
Theorem 2. Let G = (V))), E(G)) and H = (V()), E(H)) be two connected graphs with node attribtess. Suppose we can enumerate all possible WEAVES on & and H with a fixed-length k z 2 max( [(H))) -1, where each WEAVE has a unique vector representation generated from a well-trained autoencoder. The Wasserstein distance between G's 's and H's WEAVE distributions is 0 if and only i and H are isomorphic with node altributes.
Note that similar results can be easily extended the cases with both node and edge attributes, the corresponding details can be found in Appendix E
The theoretical results suggest the potential power the SEED framework in capturing structural difference of graph data. As shown above, in order to achieve the same expressive power of graph isomorphism, we need to sample a large number of WEAVEs with long walk length so that all pos- sible WEAVES can be enumerated. The resouree demand is impractical. However, in the empirical study in Section we show that SEED can achieve state-of-the-an performance, when we sample a small number of WEAVES with reasonably short walk length.

---

Published as a conference paper at ICLR 2020
4 EXPERIMENTS
4.1 DATASETS
We employ seven public benchmark datasets to evaluate the effectiveness of SEED. The brief intro- ductions of the datasets are listed below.
Deezer User-User Friendship Networks (Deezer) (Rozemberczki et al. 2018) social net- work dataset which collected from the music streaming service Deezer. It represents friendship network of users from three European countries (i.e., Romania, Croatia and Hungary). There are three graphs which corresponds to the three countries. Nodes represent the users and edges are the mutual friendships. For the three graphs, the numbers of nodes are 41, 773, 54, 573, and 47, 538, respectively, and the number of edges are 125, 826, 498, 202, and 222, 887, respectively. There exist 84 distinct genres, and genre notations are considered as node features. Thus, node features are represented as 84-dimensional multi-hot vectors.
Mutagenic Aromatic and Heteroaromatic Nitro Compounds (MUTAG) (Debnath al. 1991)
is chemical bioinformatics dataset, which contains 188 chemical compounds. The compounds can be divided into two classes according to their mutagenic effect on a bacterium. The chemical data can be converted to graph structures, where each node represents an atom. Explicit hydrogen atoms have been removed. In the obtained graph, the node attributes represent the atom types (i.e., C, N, O, F, I, CI and Br) while the edge attributes represent bond types (i.e., single, double, triple or aromatic).
NCI1 (Wale et al. 2008 represents a balanced subsets of datasets of chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines, respec- tively. The label is assigned based on this characteristic. Each compound is converted to graph. There are 4, 110 graphs in total with 122, 747 edges.
PROTEINS (Borgwardt et al. 2005) is a bioinformatics dataset. The proteins in the dataset are converted to graphs based on the sub-structures and physical connections of the proteins. Specifically, nodes are secondary structure elements (SSEs), and edges represent the amino-acid sequence between the two neighbors. PROTEINS has 3 discrete labels (i.e., helix, sheet, and turn). There are 1, 113 graphs in total with 43, 471 edges.
COLLAB (Leskovec al. 2005) is scientific collaboration dataset. It belongs social connection network in general. COLLAB is collected from 3 public collaboration datasets (i.e., Astro Physics, Condensed Matter Physies, and High Energy Physies). The ego-networks are generated for individual researchers. The label of each graph represents the field which this researcher belongs to. There are 5, 000 graphs with 24, 574, 995 edges.
IMDE-BINARY (Yanardag & Vishwanathan 2015) is collaboration dataset of film industry. The ego-network of each actor/actress is converted to graph data. Each node represents an actor/actress and each edge is the indication if two actors/actresses if they appear in the same movie. MDDB-BINARY has 000 graphs associated with 19, 773 edges in total.
IMDB-MULTI extends the IMDB-BINARY dataset to a multi-class version. contains a bal- anced set of ego-networks derived from Sci-Fi, Romance, and Comedy genres. Specifically, there are 1, 500 graphs with 19, 502 edges in total.
4.2 BASELINES
Three state-of-the-art representative techniques are implemented baselines in the experiments.
Graph Sample and Aggregate (GraphSAGE) (Hamilton et al. 2017) is an inductive graph rep- resentation learning approach in either supervised unsupervised manner. GraphSAGE explores node and structure information by sampling and aggregating features from the local neighborhood of each node. A forward propagation algorithm is specifically designed aggregates the infor- mation together. We evaluate GraphS AGE in its unsupervised setting.
Graph Matching Network (GMN) Li et al. 2019) utilizes graph neural networks to obtain graph representations for graph matching applications. novel Graph Embedding Network is designed for better preserving node features and graph structures. In particular, Graph Matching
7

---

Published as a conference paper at ICLR 2020
Network is proposed to directly obtain the similarity score of each pair of graphs. In our imple- mentation, we utilize the Graph Embedding Networks and deploy the graph-based based loss function proposed in (Hamilton et al., 2017) for unsupervised learning fashion.
Graph Isomorphism Network (GIN) (Xu et al., 2019) provides a simple yet effective neural network architecture for graph representation learning. It deploys the sum aggregator to achieve more comprehensive representations. The original GIN is a supervised learning method. Thus, we follow the GraphSAGE approach, and modify its objective to fit an unsupervised setting.
Methods Metric
SAGE
GIN
GMN
SEED
SAGE
GIN
GMN SEED
Setting
Datasets
Node Feature Excluded
Node Feature Included
ACC
0,3853
0.4913
0,4924
0.4927
0.3840
0.49.4
0),8088
0.4810
Dezzer
NMI
0.0079
0.0958
0.0726
0.1277
0.0003
0.0893
0.0651
0.0566
ACC
0.6649
0.4997
0,4990
0.8014
0.6649
0,4963
0,4910
0.7260
MUTAG
NMI
0.0150
0.0946
0,0825
0.3214
0.0070
0.0933
0.0917
0.1567
ACC
0.5098
0.5221
0,5022
0,5510
0,5070
0.5204
0.5005
0.5441
NCI1
NMI
0.0003
0.0015
0,0034
0.0073
0.0002
0.0013
0.0042
0.0089
ACC
0.5657
0.5957
0,5966
0.5957
0.5657
0.5957
0.5957
0.5957
Clustering
PROTEINS
NMI
0.0013
0.0038
0.0117
0,0518
0.0004
0.0034
0.0067
0.0689
ACC
0.5208
0.5458
0.5173
0.5973
COLLAB
NMI
0.0025
0.0729
0.0193
0,2108
ACC
0.5069
0.6202
0.5010
0.5776
IMDB-BINARY
NMI
0.0002
0.0459
0.0093
0.0241
ACC
0.3550
3607
0.3348
0.3816
IMDB-MULTI
NMI
0.0019
0.0185
0.0112
0.0214
Dezzer
ACC
0.3775
0.5094
0.5427
0.6327
0.3754
0.5270
0.5627
0.7451
MUTAG
ACC
0.6778
0.6778
0.6889
0.8112
0.6889
0.6778
0.6889
0.8222
NCII
ACC
0.5410
0.5571
0.5123
0.6105
0.5328
0.5231
0.5133
0.6151
Classification
PROTEINS
ACC
0.6846
0.7387
0.6216
0.7207
0.7027
0.7207
0.6357
0.7462
COLLAB
ACC
0.5650
0.6170
0.5460
0.6720
BIDR-BINARY
ACC
0.5400
0.7310
0.5140
0.7660
IMDB-MULTI
ACC
0,3866
0.3843
0,3478
0.4466
Table 1: Evaluating graph representation quality by classification and clustering tasks
Two downstream tasks, classification and clustering, are deployed to evaluate the quality of the learned graph representations.
For classification task, simple multi-layer fully connected neural network is built as a classifier. We report the average accuracy (ACC) for classification performance. For clustering task, an effective conventional clustering approach, Normalized Cuts (NCut) (Jianbo Shi & Malik] 2000). is used to cluster graph representations. We consider two widely used metrics for clustering performance, including Accuracy (ACC) and Normalized Mutual Information (NMI) (Wu et al. 2009). ACC comes from classification with the best mapping, and NMI evaluates the mutual information across the ground truth and the recovered cluster labels based on normalization operation. Both ACC and NMI are positive measurements (i.e., the higher the metric is, the better the performance will be).
4.3 PERFORMANCE ANALYSIS
In this section, we discuss the performance of SEED and its baselines in the downstream tasks. The performance with and without the node features are reported. In this set of experiments, SEED adopts identity kernel in the component of embedding distributions.
As shown in Table T SEED consistently outperforms the baseline methods in both classification and clustering tasks. For GIN and GMN, supervision information could be crucial in order to dif- ferentiate structural variations. As GraphSAGE mainly focuses on aggregating feature information from neighbor nodes, it could be difficult for GraphSAGE to extract effective structural information from an unsupervised manner. In the unsupervised setting, SEED is able to differentiate structural difference finer granularity and capture rich attribute information, leading to high-quality graph representations with superior performance in downstream tasks. Interestingly, for NCI and PRO- TEINS datasets, we see node features bring little improvement in the unsupervised setting. One
8

---

Published as a conference paper at ICLR 2020
possible reason could be node feature information has high correlation with structural information in these cases.
Sampling Number
Classification Accuracy
Clustering
ACC
NMI
Walk Length
Classification Accuracy
Clustering
ACC
NMI
25
0.6832
0.6649
0.0031
50
0.6778
0.6649
0.0005
5
0.7278
0.6649
0.0534
100
0.7778
0.6649
0.0537
0.7778
0.7633
0.2100
150
0.7889
0.6968
0.1081
15
0.8167
0.7723
0.2495
200
0.7778
0.7633
0.2100
20
0.8778
0.8245
0,3351
300
0.7833
0.7502
0.1995
25
0.8722
0.8218
0.3380
400
0.8389
0.7628
0.1928
30
0.8743
0.8285
0.3321
800
0.8111
0.7660
0.1940
Table 3: Representation quality with differ- ent walk lengths
Table 2: Representation quality with differ- ent sampling numbers
10
10
10
-10
-10
100
:10
-10
-5
5
-10
-10
10
-10
Samples 50
Samples 100
Samples
(d) Samples
(e) Samples 400
Figure 3: t-SNE visualziation of the MUTAG representations with different sampling numbers
10
10
-5
-5
-10
-10
-10
-10
10
-10
0
10
-10
0
10
-10
0
(a) Wolk length 5
(b) Walk length 10
(c) Walk length - 15
(d) Walk length 20
(e) Walk length 25
Figure 4: (-SNE visualziation of MUTAG representations with different walk lengths
4.4 ABLATION STUDY
Walk length and sample numbers these two meta-parameters, we can make trade-off between effectiveness and computational effi- ciency. In the experiment, we empirically evaluate the impact of the two meta-parameters on the MUTAG dataset. In Table 2 each row denotes the performance with different sampling numbers (from 25 to 800) while the walk length is fixed 10. Moreover, to 25 while sampling number is fixed to 200 in Table 3 We can see that the performance of SEED in both classification and clustering tasks increases as there are more subgraphs sampled, especially for the changes from 25 to 200. Meanwhile, we observe the increasing rates diminish dramatically when sampling number ranges from 200 to 800. Similarly, the performance of SEED increase as the walk length grows from 20, and the performance starts to converge when the length goes beyond 20.
meta-parameters in the SEED framework. By adjusting
adjust the walk length from
More empirical results are provided in Appendix. In particular, we demonstrate the effectiveness of using DeepSets (Zaheer et al. 2017) for embedding distribution in Appendix F Appendix G consider pure feature based random walk baseline with earliest visit time removed, and eval- uate its performance. Moreover, we present how to leverage Nyström approximation in embedding distribution, and its performance is reported in Appendix H

---

Published as a conference paper at ICLR 2020
10
-5
-10
-10
-5
5
10
-10
0
5
10
(a) Identity Kernel
(b) RBF Kernel
Figure 5: t-SNE visualization of the learned representations from different kernels on MUTAG
5 EMBEDDING DISTRIBUTION
We employ t-SNE Maaten & Hinton 2008 to visualize learned graph representations in Figure and Figure 4 Red and blue colors indicate two labels. We observe that the boundary becomes clearer when sample number walk length increases.
Embedding Classification ACC Clustering ACC Clustering NMI
Identity keme]
0.8112
0,8014
0.3214
RBF kernel
0.7958
0.7984
0.3115
Table 4: Graph representation quality comparison between identity and RBF kernel MUTAG
Identity kernels or commonly adopted kernels could deployed in the component of embedding subgraph distributions. In our implementation, we utilize multi-layer deep neural network to approximate a feature mapping function, for kernels whose feature mapping function is difficult to obtain. Figure 5 shows the t-SNE visualization of learned graph representations based on identity kernel and RBF kernel. As shown in Table 4 SEED variants with different kernels for distribution embedding could distinguish different classes with similar performance the MUTAG dataset.
CONCLUSION
In this paper, propose novel framework SEED (Sampling, Encoding, and Embedding distri- bution) framework for unsupervised and inductive graph learning. Instead of directly dealing with the computational challenges raised by graph similarity evaluation, given an input graph, the SEED framework samples number of subgraphs whose reconstruction errors could be efficiently evalu- ated, encodes the subgraph samples into collection of subgraph vectors, and employs the embed- ding of the subgraph vector distribution as the output vector representation for the input graph. By theoretical analysis, we demonstrate the close connection between SEED and graph isomorphism. Our experimental results suggest the SEED framework is effective, and achieves state-of-the-an predictive performance on public benchmark datasets.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey. Data mining and knowledge discovery, 29(3):626 6260688866888866 2015.
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein gan. arXiv preprint
arXiv: 07875,0 2017.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction net- works for learning about objects, relations and physics. In Proceedings of Advances in neural information processing systems, pp. 4502-4510, 2016.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- crating graphs via random walks. Proceedings of International Conference on Machine Learn- ing. 2018.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path paatestt-pathheee kernels on graphs. In Proceedings of IEEE International conference on data mining, pp. 8 8-pp. 2005.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformaticc, (ssuplL. i47-i56, 2005.
Gary Chartrand. Introductory graph theory. Courier Corporation, 1977.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):88-7777, 1991.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of Advances neural information processing systems, pp. 3844-3852, 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Espuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Proceedings of Advances neural information processing systems, pp. 2224- 2015.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(M77):733-773 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507, 2006.
Tamás Horváth, Thomas Gärtner, and Stefan Wrobel. Cyclic pattern kernels for predictive graph mining. In Proceedings of ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 158-167, 2004.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In Jennifer Dy and Andreas Krause (eds.), Proceedings of International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pp. 2186-2195, Stockholmsmässan, Stockholm Swe-
den, 10-15 Jul 2018. PMLR.
Jianbo Shi and Malik. Normalized cuts and image segmentation. IEEE Transactions Patlern Analysis and Machine Intelligence, 22(8):888-900 Aug 2000.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of International Conference on Machine Learning, 2018.
11

---

Published as a conference paper at ICLR 2020
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of International conference on machine learning (ICML-03), pp. 321-328, 2003.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8): 595-608, 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:/412.6900 2014.
Thomas N Kipf and Max Welling. arXiv:1611.0730,, 2016.
Variational graph auto-encoders.
arXiv preprint
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. CoRR, abs / 1903. 11835
abs/1903. 11835, 2019.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathe- matical statistics, 22(1):79-86, 1951.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrink- ing diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD interna- tional conference on Knowledge discovery in data mining, pp. 177-187. ACM, 2005.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of International Conference on Machine Learning. volume 97,
pp. 3835-3845, 09-15 Jun 2019.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph vari- ational autoencoders for molecule design. Proceedings of Advances Neural Information Processing Systems, pp. 7795-7804, 2018.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 9(Nov) 2609, 2008.
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108-122 2016.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational
machine learning for knowledge graphs. Proceedings of IEEE, 104(1):11-33, 2015.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In Proceedings of International Conference on Machine Learning, pp. 2014- 2023, 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 701-710. ACM, 2014.
Matthias Ring and Bjoern M Eskofier. An approximation of the gaussian rbf kernel for efficient classification with syms. Pattern Recognition Letters, 84:107-113, 2016.
Benedek Rozemberezki, Ryan Davies, Rik Sarkar, and Charles Sutton. Gemsee: Graph embedding with self clustering. arXiv preprint arXiv:1802.03999. 2018.
Ludger Rüschendorf. The wasserstein distance and approximation theorems. Probability Theory and Related Fields, 70(1):117-129, 1985.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski. Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Proceedings of Advances in neural information processing systems, pp. 4967-4976 2017a.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski. Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Proceedings of Advances in neural information processing systems, pp. 4967-4976, 2017b.
12

---

Published as a conference paper at ICLR 2020
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Nino Shervashidze and Karsten Borgwardt. Fast subtree kernels on graphs. In Proceedings of Advances in neural information processing systems, pp. 1660-1668, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(Sep))2539- 2561, 2011.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of International Conference Learning Representations, 2018.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, I1(Apr):1201-222) 2010.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Christopher KI Williams and Matthias Seeger. Using the nyström method speed up kernel ma- chines. In Advances in neural information processing systems, pp. 682-688, 2001.
Junjie Wu, Hui Xiong, and Jian Chen. Adapting the right measures for k-means clustering. In Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 877-886, 2009.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of International Conference on Machine Learning, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? Proceedings of International Conference on Learning Representations, 2019.
Xifeng Yan, Philip S Yu, and Jiawei Han. Substructure similarity search in graph databases. In Proceedings of ACM SIGMOD international conference on Management of data, pp. 766-777. ACM, 2005.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In Proceedings of International Conference on Machine Learning, 2018
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in neural information processing systems, pp- 3391-3401, 2017.
Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou, Comparing stars: On approximating graph edit distance. Proceedings of VLDB Endowment, 2(1):25-36, 2009.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: variational autoencoder for directed acyclic graphs. arXiv preprint arXiv: 1904. 1088, 2019.
Bo Zong, Qi Song, Martin Rengiang Min, Wei Cheng, Cristian Lumezanu, Dacki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. Pro- ceedings of International Conference on Learning Representations, 2018.
13

---

Published as a conference paper at ICLR 2020
A PROOF FOR LEMMA 1
Proof. We will use induction on [E() to complete the proof.
Basic case: Let
[() = 1. the only possible graph is a line graph of length 1. For such a graph, the walk from one node to another can cover the only edge on the graph, which has length 1 = 2- -
Induction: We assume for all the connected graphs on less than m edges (i.e. [E(g)| S m - 1), there exist walk of length k which can visit all the edges if l 2 2[)(G) 1. Then we will show for any connected graph with m edges, there also exists a walk which can cover all the edges on the graph with length & > F[)(
-
Let g = (V( E(g)) be a connected graph with [E(G]] = m. Firstly, we assume 9 is not a tree, which means there exist eycle on G. By removing edge e (v,, b1)) from the cycle, we can get a graph g' on m edges which is still connected. This is because any edge on a cycle is not
Vi ...00 Ur of length k' 2 2(m 1)+ 1 which can visit all the edges on g' (The walk does not necessarily start from node 1, 21 just represents the first node appears in this walk). Next, we will go back to our graph G. as g" is a subgraph of G. w/ is also a walk on G. By replacing the first appeared node v on walk w' with a walk Ug0 we can obtain a new walk w 01 ... 2;0 U2 ... Uy 2t on g. As w can cover all the edges on G' and the edge e with length k k + 2(m 1) - 1 1+2 = 2m - 1, which means it can cover all the edges on G with length A 2 2[E()) - 1.
bridge. Then according the induction hypothesis, there exists walk w' vi 02 ...... 02...... ................................ .....
Next, consider graph G which is a tree. In this case, we can remove leaf v3 and its incident edge e = (Us,2), from G. then we can also obtain connected graph G' with [E(')) according to the induction hypothesis, we can find a walk w' U1222 ... -U ........ 11 on G' which can visit all the m - 1 edges of G' of length K', where k' 2 2(m - 1) - As G' is a subgraph of G. any walk on G' is also a walk on G including walk w'. Then can also extend walk w on G by replacing
m - 1. Similarly,
the first appeared U; with walk U; which produce a new walk w U1 0:0101 8t- w can visit all the edges of G' as well as the edge with length k = K' + 2 2 2(m - 1) I 1+2 = 2m 1. In other words, wo can visit all the edges on G with length k 2 2| E(G) - 1. Now, we have verified
our assumption works for all the connected graphs with m edges, hence we complete our proof. (To
give an intuition for our proof of lemma 1, we provide an example of 5 edges in Figure 6
144
D3
I'S
12s
3
V's
22
1/
F1
W
W
W
Wr
Pi
1/2
1/2
(al) GraphG which not tree (a2) Graph g' comrepoonds g (al) (b1) Graphn which is bre (hi2) Graph comespondds to in (bl)
Figure 6: Different types of graphs with random walk which can visit all the edges.
Figure 6 (al) illustrates an example graph G which is a connected graph on 5 edges but not a tree. By removing an edge (v2, us) from the cycle, we can get a connected graph g' (Figure 6 (a2) with
4 edges. G' has walk w/ = i1 P2 which covers all the edges of g', as w' is also walk on which can visit all the edges of G. Figure 6 (b1) shows an example graph G which is a tree on 5 edges. By removing the leaf U4 and its incident edge (Ma, 23), we can get a tree G' with edges (Figure 6 (b2)). g' has a walk w/ U1 0i which covers all the edges of G', w/ is also walk on G, by replacing vy with vy2443 in w' we can get a walk w Un 0203040335 which can cover all the edges of g.
G. by replacing ii with walk ugU2U5 in w', we can get w = Dj 03
B LEMMA 2
The following lemma is crucial for the proof of Theorem 1.
14

---

Published as a conference paper at ICLR 2020
Lemma 2. Suppose that w, w' are two random walks on graph G and graph H. respectively, if the representation of w and w' are the same, i.e, Tw = Tww, the number of the distinct edges on w and w' are the same, as well as the mumber of the distinct nodes w and w'.
Proof. Let n1, n2 be the number of distinct nodes on w' respectively, let my, m2 be the number of distinct edges on w and w' respectively. First, let's prove nn = 72- We will prove this by contradiction. Assume ni o f22, without loss of generality, let n4 > n22. According to our encoding rule, the largest number appears in a representation vector is the number of the distinct nodes in the corresponding walk. Hence, the largest element in vector Tw is n1 while the largest element in vector Two is n2.. Thus, Tw # Two, which contradicts our assumption. Therefore, we have n1 = m2.-
Next, we will show my = mg. We will also prove this point by contradiction. Assume m + m2, without loss of generality, let mı > m2. As we have proved n1 = n22 each edge on w and w' will be encoded as vector like [k1, k2] where l h2 [mı]] A walk consists of edges, hence the representation of a walk is formed by the representation of edges. Since m, > m2, which means there exists at least two consecutive element [K1, A2] in Tw which will not appear in Tw', thus Th o Twi, which is a contradiction of our assumption. As a result, we can prove my = m2-
C PROOF FOR THEOREM
Proof. We will first prove the sufficiency of the theorem, ie., suppose graphs g = (V(9), F(g)) and H. (V(H), E(H) are two isomorphic graphs, we will show that the WEAVE's distribution on G and H are the same.
Let A be the of all the possible walks with length & on G. B be the of all the possible walks with length & on H. Each element of A and B represents one unique walk on G and H respectively. As we have assumed a WEAVE is a class of subgraphs. which means a WEAVE may corresponds to multiple unique walks in A or B. Consider a walk w = U1 ...... Dt E A (v: represent the ith node appears in the walk), for any edge e (v;, 2yy) on Wc as e E F()), according to the definition of isomorphism, there exists mapping f V(9) - V(H) such that (f(z), f(;)) E E(H). If we map each node on W; to graph H. we can get a new walk w/ = (12).... f(r) on H as each edge (f()), f(x))) E EHH), besides, as the length of ut is also k, we have w/ E B. Hence, we can define a new mapping g : A + B, s.t.
Yu,= = U1 ... Ug E A. g(w;) = f(v:) .. f(ve) w/ E B.
(8)
Next, we will show that y is a bijective mapping. Firstly, we will show that f is injective. Sup- pose g(wi) = g(w2), we want to show wi = W22 Assume wi * W2, there must exists one step such that wi (i) * w2(i), let wi (i) = (v. .u ..)")., w2(1) = (v,²) .uj o.))), then we have (f(ol)) (((()))) + (f(x)"), ((u)2))) due to the definition of isomorphism. According to the map- ping rule of f. (f(v(")) ((u is the ith step of (wI) (f(o)"),, ), f(ofz))) is the ith step of g(w2), thus the walk ((w1) # g(w2), which contradicts our assumption. Therefore, the assumption is false, we have w1 = W2. Then we will show that g is surjective, i.e., for any w' E B, there exists a w E A such that g(w)= = w'. We will also prove this by contradiction, suppose there exists walk w' E B such that we can't find any w E A to make g(w) = w'. Let w' U1 ......2 Uz. according to the defi- (1,)) E(G),
(2)
nition of isomorphism, for any edge (u), U2) EHH) on w', we have where f-1 represents the inverse mapping of Hence
w (v)))
E A,
(9)
as w is a walk on graph H with length k. Now consider g(w), based on the mapping rule of g. we need to map each node w via f, i.e.,
g(w)
= 02 w';
(10)
which is contradiction to our assumption. Thus we have proved g is an injective mapping as well as surjective mapping, then we can conclude that g is bijective mapping.
Then we will show the WEAVES' distribution of G and H. are the same. Since in our assumption,
[F))) is limited, then |A] and [B] are limited, besides, according to encoding rule, different
15

---

Published as a conference paper at ICLR 2020
walks may correspond to one specific WEAVE while each WEAVE corresponds unique represen- tation vector, thus the number of all the possible representation vectors is limited for both ç and H. Thus, the representation vector's distributions Ps for graph & and representation's 's distributions Ph for graph H are both discrete distributions. To compare the similarity of two discrete probability distributions, we can adopt the following equation to compute the Wasserstein distance and check if it is O.
(P(P.Q) = min
((,,))(i,
s.t.
T (i, = Way Vj.
(II)
Σ x(. = Wps Vi, j=1
(i. 2 0, Vi.
where Wi (P,, Q is the Wasserstein distance of probability distribution IP and Q, (i) is the cost function and J) is distance function, Way and w/p are the probabilities of qj and P3 respectively.
Since we have proved g : - B a bijection, besides, according to our encoding rule, g(w) and w will corresponds to the same WEAVE, hence they will share the same representation vector. As a consequence, for each point (gi, Wg:) (g. corresponds to a representation vector, Wy; represents the probability of gb) in the distribution Pg. we can find a point (he, wn,) in Px such that yi = hi, and Wg. = Wh. Then consider (II). for Pg and Px., if we let π be a diagonal matrix with [wp.. Wp...... ........ pp on the diagonal and all the other elements be O, we can make each element in the sum En
1== 2==1 ((t,)) be O, as this sum is supposed to be nonnegative, its minimum is O, hence (PGPG PH) = O, which means for two isomorphic graphs G and H. their WEAVE's distributions Pg and PH are the same.
Next we will prove the necessity of this theorem. Suppose that the Wasserstein distance between the walk representation distributions P'g and Ps is O we will show that graph and H are isomorphic. Let the number of the nodes of graph G is n1, the number of the nodes of graph H. is n2, let the number of the edges on graph G is m1, the number if the edges on graph H. is m2- Let k 2 max m2, m2} - 1.
Now, we will give a bijective mapping f V(G) + (H). First, consider the walks on graph G. as k = 2 max max[m1, (m1,m)) - 2 2m1 - 1, according to Lemma 1, there exists at least one walk of length on graph G which can cover all the edges of G. Consider such a walk we, let rg = [1, 2,,, ..., be the representation vector (corresponds to WEAVE) we obtained according to our encoding rule. Now, we will use this representation to mark the nodes on graph G. Mark the first node in this walk as 41 (corresponds to 1 in the representation), the second node u2 the ith appearing node in wg is ue continue this process untill we marked all the new appearing nodes in this walk. Since wg can visit all the edges of graph G, all the nodes this graph will definitely be marked, hence the last new appearing node will be marked as uny Now, let's 's consider the walks on graph H. As we have assumed that W1(Ps (Pg. PR) O, which means that for each point (gi, w.,) on Pg. we can find point (he, )h,) in Ps such that = h, and Wg. = wh,, As consequence, as rg is a point on Pg. there must be a point Th on H such that 7n Ta = [1, 2, 3, ...,t]T Then choose any walk wny on H. which produce The and apply the same method to mark the nodes in this walk in order as U1 U2 ..y Uny- Now we can define the mapping f, let f (G) + V(H), s.t., f(u,) = for Vi E [Ma], which is exactly the mapping we are looking for.
Next, we just need show for each edge (u,, Uz) E E(G), we have (f(u)), f(u))) E E(H), and vice versa, then we can prove G and H are isomorphic. The first direction is obviously true as wg covers all the edges on G, for any edge (u,, uz) in wg. we have (f(u)), f(;)) (v),1) which belongs to Wh, since Wn is walk on H. we have (vi, 02) E E(H). Then we will prove the reverse direction, i.e., for any (v;, Ui) = (f(u:), f(,)) E E(H), we have (u,, uz) E E()). To prove this, we will first show that the number of edges of graph 9 and H. are the same, i.e., m, = m2- Suppose this is not true, without loss of generality, let mı > m2. Since Pg and Py are the results of random walks for infinite times. Then there must exists some walks which can visit the additional edges 9, as consequence, can obtain some representation vector which will not appear
16

---

Published as a conference paper at ICLR 2020
A
B
Ared
Boreen
A1o0
B1.1
C
D
D green
Cred
D1.3
C1.2
Probabilitty
8
Probability
Probailitty
16
4
16
16
Fnooding
Encnding
Encoding Representations
Representations
Representations
(a) Graph without mode altributes
(b) Graph with discade mode attributes
(c) Graph with continuous node attributes
Figure 7: Walk representation distributions of graphs without attributes, graphs with discrete at- tributes, and graphs with continuous attributes.
m2. Besides, since we have rg = The according to Lemma 2, we can derive that the number of distinct edges on Wl and wh are the same. As Wy covers all the edges on G, hence the number of distinct edges on Wy is mi. Therefore, the number of distinct edges on wh also m1, which means wA also has visited all the edges on H. As for any edge 0g) on wh, we have (u,, Uz) on Wh, in other words, we have (u: u2) ( E B(G). Hence we complete the proof.
in PH, which contradicts our assumption. Hence, we have
Figure shows the walk representation distributions for a nodes ring with walk length = 2 in three different cases: without node attributes, with discrete node attributes, and with continuous node attributes. We can see the attributes will have an influence to the distributions, more specifically, the probability of each unique walk keeps the same no matter what the attributes are, however, the probability of each representation vector may vary as different unique walks may correspond to one representation vector, and the attributes may influence how many representation vectors there will be and how many unique walks correspond to representation vector. To clarify, in Figure (a), the ring graph does not have nodes attributes, there exists 16 unique walks in total, among them walk ABD, BDC, DCA, CAB, DBA, CDB, ACD, BAC will all be encoded as ABA, BAB, BDB, DBD, CDC, DCD, CAC, ACA will be encoded as r2 = [1 2 1] Hence, for a graph in Figure (a), we have Pr(n)) = To Pr(r2) = 16' In Figure 7 (b), each node has discrete attribute, l.e.. red green, there still 16 unique walks in total. However, in this case, there exits four different representation vectors, walk ABC, CBA, ADC, CDA will be encoded
[1 2 3] walk
as [RR 2G 3R) where R represents Red while G represents Green; walk BCD, DCB, DAB, DCB correspond to 72 = [LG 2R 3G] walk ABA, ADA, CDC, CBC correspond to F3 [1R 2G 3R T walk BAB, BCB, DCD, DAD correspond to r3 [LR 2G TR,". In this case, have Pr(ri) Pr(r2) Pr(ra) = Pr(ra) -6 In the last, let's consider the case when there exists continuous nodes attributes, for such graph, the value of nodes attributes has infinite choices, hence, very likely that each node may have different attribute. As a consequence, each unique walk will correspond to a unique representation vector. In our example Figure 7 (c), there also exists 16 unique walks, each walk has a particular representation vector, hence, the probability of each representation vector is T6
D PROOF FOR THEOREM 2
Proof. The proof for Theorem 2 is quite similar as the proof of Theorem 1, this is because the attributes just influence the representation vector form and how many unique walks correspond to representation vector, however, the probability of each unique walk keeps same. Hence, we can use similar method complete the proof. Similarly, will first prove the sufficiency. Let G and H
17

---

Published as a conference paper at ICLR 2020
be two isomorphic graphs with attributes, will prove that the walk representations distribution of and H. are the same. Suppose that A and B are the sets of possible walks of length on & and H respectively. By applying the same analysis method as in the proof of Theorem 1, we can show that there exists a bijective mapping
+ B such that for Ve; = 01 12 Ot E A, we have
g(w,) = =f===f(ooz f(v1)f(v))... f(v)) E B,
(12)
where f: :V) + V(H) satisfies V(v,, v2)) E F((), we have (f(u)), f(2))) E E(H) and for Ve, e V(G). the attribute of v and f(4) are the same. Hence, according to encoding rule, wy and f(wx) will be encoded as the same representation vector, which means for each point (T Pr(r,)) in the representation distribution of G, we find point (rh, Pr(r..) )) in the distribution of H such that Tg Th, Pr(rg.) ) = Pr(rk.) Thus, we can obtain the Wasserstein distance of distribution Pg and the distribution PH is Wi (PG,, PH) 0 via similar approach as in Theorem 1. In other words, we have Pg = PH. In addition, the necessity proof of Theorem 2 is the same as Theorem 1.
E GRAPHS WITH NODE ATTRIBUTES AND EDGE ATTRIBUTES
If both the nodes and edges in graph have attributes, the graph is an attributed graph denoted by = (V, Fr, a, 3), where V > Ln and [3 : E - LE are nodes and edges labeling functions, LN. LE are sets of labels for nodes and edges. In this case, the graph isomorphism are defined as:
Definition Given two graphs G = (V(9), E(G), ag, 3g) and H = (V E(H), on, 0HH 9H), then G and H are isomorphic with node altributes well as edge attributes if there is a bijection f VG) + (H)
Vuv E E(g) + f(u)S(v) E E(H), ag(u) ax(f(u)), Vu V()),
(13)
(14)
Bo(u, v) Bx([(u), (()))
(15)
Corollary 1. Let G = (V) E(G)) and H = (V(H), E(H)) be two connected graphs with node attributes. Suppose we can enumerate all possible WEAVES on G and H with a fixed-length k z 2 ((G), [E(H)) where each WEAVE has a unique vector representation generated from a well-trained autoencoder. The Wasserstein distance between G's 'ss and H's WEAVE distributions is 0 if and only if G and H are isomorphic with both node attributes and edge attributes.
Proof. When both nodes and edges of a graph are given attributes, the representation vectors of ran- dom walks will be different. However, just like the cases with only nodes attributes, the probability of each unique walk on the graph keeps same. Hence, we can follow a similar analysis method as Theorem complete this proof.
Identity Kernel
DeepSet-MMD
Dataset
Classification ACC
Clustering
Classification ACC
Clustering
ACC
NMI
ACC
NMI
NCTI
0.6105
0,5510
0.0073
0.6382
0.5630
0.0095
PROTEINS
0.7207
0.5957
0.0518
0.7103
0.5965
0.0438
COLLAB
0.6720
0.5973
0.2108
0.6572
0.5668
0.2015
BIDB-BINARY
0.7660
0.5776
0.0241
0.7210
0,5219
0.0225
IMDB-MULTI
0.4466
0.3816
0.0214
0.4258
0.3647
0.0168
Table 5: Representation evaluation based on classification and clustering down-stream tasks
F DEEPSET IN THE COMPONENT OF EMBEDDING DISTRIBUTIONS
In this section, investigate whether DeepSet (Zaheer et al. 2017) is effective technique for distribution embedding. In particular, we employ DeepSet to replace the multi-layer neural net- work for feature mapping function approximation, and similarity values generated by MMD serve
18

---

Published as a conference paper at ICLR 2020
supervision signals guide DeepSet training. In our experiments, we compare the SEED imple- mentation based on DeepSet with MMD (DeepSet in T with the SEED implementation based on the identity kernel (Identity Kernel in Table [5). We also observe that the MMD does not have significant performance difference. The result confirms that DeepSet could be strong candidate for the component of Embedding subgraph distributions.
G ABLATION STUDY ON WEAVE
Feature utilized
Classification ACC
Clustering ACC
Clustering NMI
Only node feature
0.6444
0.6744
0.0625
Only earliest visit time
0,8112 0.8222
0.8014
0.3214
Node feature Earliest visit time
0.7260
0.1567
Table 6: The impact of node feature and earliest visit time in WEAVE based on MUTAG dataset
In this section, we investigate the impact of node features and earliest visit time in WEAVE. In T Only node feature means only node features in WEAVE are utilized for subgraph encoding (which is equivalent to vanilla random walks), only earliest visit time means only earliest visit time information in WEAVE is used for subgraph encoding, and Node feature earliest visit time means both information is employed. We evaluate the impact on the MUTAG dataset. As shown above, it is crucial to both node feature and earliest visit time information in order achieve the best performance. Interestingly, on the MUTAG dataset, we observe that clustering could be easier if we only consider earliest visit time information. On the MUTAG dataset, node features seem to be noisy for the clustering task. As the clustering task is unsupervised, noisy node features could negatively impact its performance when both node features and earliest visit time information are considered.
H NYSTRÖM APPROXIMATION IN THE SEED FRAMEWORK
In this section, we evaluate the impact of Nyström based kernel approximation (Williams & Seeger 2001) to the component of embedding distributions.
exact MMD
Response Time (sec)
0.15
Nyström approximation
0.1
0.05
500
1000
1500
2000
Sample Number
Figure 8: Response time comparison between exact MMD and its Nyström approximation
First, we investigate the impact to the effectiveness in the downstream tasks. In this set of exper- iment, implement a baseline named SEED-Nyström, where the Nyström method is applied to approximate RBF kernel based MMD during training phases with 200 sampled WEAVEs. In partic- ular, top 30 eigenvalues and the corresponding eigenvectors selected for the approximation. As shown in Table 7, across five datasets, SEED-Nyströne achieves comparable performance, compared with the where identity kernel is adopted.
In addition, we evaluate the response time exact RBF kernel based MMD and its Nyström ap- proximation. Top 30 eigenvalues and the corresponding eigenvectors selected for the Nyström
19

---

Published as a conference paper at ICLR 2020
RBF Kernel
SEED- SEED-Nyström
Dataset
Classification
Clustering
Classification ACC
Clustering
ACC
ACC.
NMT
ACC
NMI
NCII
0.6211
0.5610
0.0079
0.6281
0.5518
0.0081
PROTEINS
0.7161
0,5857
0.0476
0.7054
0.5738
0.0389
COLLAB
0.6718
0,5212
0,1831
0.6447
0.5217
0.1983
IMDB- BIBB-BINARY
0.7421
0,5582
0.0218
0.7280
0.5018
0.0211
0.4541
0.3985
0.0241
0.4148
0.3676
0.0172
Table 7: Representation evaluation based classification and clustering down-stream tasks
when we range the number of WEAVE samples from 100 to 2000, the Nyström approximation scales better than the exact MMD evaluation.
approximation. As shown in Figure g
In summary, the Nyström method is promising method that can further improve the scalability of the SEED framework in training phases, especially for the cases where a large number of WEAVE samples are required.
20


Reviews:
[{"review_id": "SJgTQ4kwFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The authors propose a method for learning graph embeddings and focus specifically on a setting where not all graphs are part of the training data (the inductive setting). The core problem of graph embedding methods is to find a learnable function that maps arbitrary graphs into a fixed-sized vector representation. There have been several proposals ranging from the class of graph kernels to variations of graph neural networks. The authors propose a method that consists of three steps\n\n(1) sample a number of subgraphs from the original graphs\n(2) learn an encoding function for these subgraphs (subgraph -> vector representation)\n(3) for every graph we, therefore, get a set of vector representations, one per subgraph. We now try to find a similarity measure operating on sets of vectors to compute the distance between graphs.\n\nThe novel bits are\n(a) the way that the subgraphs are sampled (using an algorithm called WEAVE, that stores more information about random walks) and, therefore, is able to be distinguish graphs based on the extracted walks that standard random walk based methods cannot; and \n(b) to define a similarity measure based on the set of vectors. \nThe authors also prove that their method is (under some assumptions) able to decide the isomorphism problem. This is a nice result to have in light of recent papers that have investigated the limitations of GNN in comparison to Weisfeiler-Leman and isomoprhism testing. \n\nUnfortunately, the proposed method has limited novelty. The WEAVE sampling is a small variation on random walk sampling that's been around for a while in graph representation learning. Also, to define the similarity between set of vectors has been addressed before in numerous papers (e.g., all papers investigating learning for sets, DeepSets, etc.) and the method here seems a bit ad-hoc and doesn't compare to existing work. \n\nMy \"novelty\" critique is also made in light of the small number of datasets on which experiments have been conducted. If a new simple random walk strategy would lead to clearly better results on a number of datasets, this would be a significant contribution. As far as I can tell, however, the results are mixed and not very impressive especially due to the small number of datasets. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xbh5Gg9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "In this work, a novel graph similarity learning framework SEED is proposed. Given an input graph, SEED proceeds in 4 steps, namely Sampling subgraphs, Encoding sampled subgraphs using autoencoder, aggregating subgraphs' Embedding Distribution into a vector representation.  Theretically, a connection between proposed SEED and the graph isomorphism is established. Experimentally, simulation on DEEZE and MUTAG datasets validated the effectivety of the proposed graph learning framework.  \n\nPro:\nThe paper is well structured and easy to follow.  Experiments appears convincing, especially the t-SNE plots when varying the number of subgraph samples.\n\nCon:\nIt would be better if experiments can be conducted on a few more benchmark datasets used in the compared methods.\n\nMinor:\nLast sentence in Page 6: each component have been -> each component has been\nthe 5-th sentence in Sec. 4.3, focusing -> focuses\nthe 7-th sentence in Sec. 4.3, At the meantime -> In the meantime", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HkeAKNxptr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The authors propose a general framework SEED (Sampling, Encoding, and Embedding Distributions) for inductive and unsupervised representation learning on graph structured objects. The most innovative part in this paper is random walks with earliest visiting time (WEAVE) in the sampling part. WEAVE has potential power for capturing structure difference and could reflect isomorphism as well. Instead of using language model like word2vec, encoding part leverages MLP to get the embedding of each WEAVE, which is efficient and intuitive. Then, the group of encoding results from all WEAVEs are aggregated with kernel functions, generating the final embedding of a graph. This method achieves better accuracy in both clustering and classification tasks than previous ones including GraphSAGE, GMN and GIN.\nThis method uses an elegant way to embed graphs in an unsupervised manner, and the new random walk approach provides insights into graph structure encoding. Factors like walk length and number of walks are strictly derived then well examined in real experiments.\nQuestions & suggestions:\n1 In WEAVE encoding part, the paper doesn’t show how much the earliest visiting time information improve the model. In another word, if we leave out the timing term (x_t^{(p)}), will the model still perform well?\n2 In embedding distribution part, it seems that only identity kernel is easy to calculate. For commonly adopted kernels, the MLP is “mimicking the behavior of a kernel”, so it will still be limited by the kernel you choose in MMD. There are some statistical approaches to estimate Ф(z) like Nystrom method, maybe that will be another solution other than taking average.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on the problem of finding dense representations of graph-structured objects in an unsupervised manner. The authors propose a novel framework for solving this problem and show that it improves over competitive baselines. The reviewers generally liked the paper, although were concerned with the strength of the experimental results. During the discussion phase, the authors bolstered the experimental results. The reviewers are satisfied with the resulting paper and agree that it should be accepted.
Decision: Accept (Poster)