How can we generalise learning distributed representations of graphs?
Authors: Paul M Scherer
Pietro Lio
Venue:  (2020)
Keywords: graphs
distributed representations
similarity learning

Abstract: We propose a general framework to construct unsupervised models capable of learning distributed representations of discrete structures such as graphs based on R-Convolution kernels and distributed semantics research. Our framework combines the insights and observations of Deep Graph Kernels and Graph2Vec towards a unified methodology for performing similarity learning on graphs of arbitrary size. This is exemplified by our own instance G2DR which extends Graph2Vec from labelled graphs towards unlabelled graphs and tackles issues of diagonal dominance through pruning of the subgraph vocabulary composing graphs. These changes produce new state of the art results in the downstream application of G2DR embeddings in graph classification tasks over datasets with small labelled graphs in binary classification to multi-class classification on large unlabelled graphs using an off-the-shelf support vector machine. 

Under review as a conference paper at ICLR 2020
HOW CAN WE GENERALISE LEARNING DISTRIBUTED REPRESENTATIONS OF GRAPHS?
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper consists of two parts. Firstly, we specify a general framework for constructing systems capable of learning distributed representations of graphs in an unsupervised manner. We show how systems such as Deep Graph Ker- nels, Graph2Vec and Anonymous Walk Embeddings can be formulated under this framework. In the second part of this paper, we exemplify the construction of instance of this framework by proposing a model which extends Graph2Vec. called G2DR. This model extends Graph2 Vec's current implementation to en- able application on unlabelled graphs and tackles issues of diagonal dominance through pruning of the substructure vocabulary. These extensions help G2DR achieve state of the art results in downstream application of learned embeddings graph classification tasks over datasets with small labeled graphs in binary classifi- cation to multiclass classification on large unlabelled graphs using an off-the-shelf support vector machine.
INTRODUCTION
A fundamental prerequisite for machine learning algorithms to learn about input data is the abil- ity to discern one observation from another. Even more powerful is the ability determine how similar or dissimilar such observations are from one another to make more detailed associations. For observations represented in Euclidean space with feature vectors the concept of similarity be- tween observations is intuitive as it may be computed as distance using Fuclidean distance or cosine similarity formulas. Unfortunately, for observations represented as graphs defining the notion of similarity, and even more so designing methods for computing similarity has been long ongoing challenge in maths and computer science. This is partly because assessing comparability of graphs does not only consist of looking for similar elements (nodes) but also structural similarities between the substructures within. An obvious real world example on the importance this distinction can be found in chemistry where molecules called isomers exhibit identical chemical formulas but different structural properties which induce different behaviours and traits (Petrucci et al. (017). The diffi- culty of comparing graphs is highlighted by the graph isomorphism test (Garey & Johnson| 1990), which despite its complexity only gives binary evaluation of the structural equivalence between two graphs which is insufficient for demands of fine grained machine learning tasks.
Consequently, the graph learning domain predominantly features kernel methods which approximate the comparability of graphs using invariants substructures such nodes, subgraphs and random walks within the graphs (Vishwanathan et al., 2010). Whilst they are powerful and intuitive, such kernels are dependent and often tied certain methods such as support vector machines (SVM) to perform learning tasks (Yanardag & Vishwanathan, 2015). Hence, existing methods utilizing kernel methods are often unable to handle other downstream learning tasks such as regression or clustering without significant revision.
More recently, deep learning approaches for graph representation learning have gained significant research activity with the successful interpretation of graph convolutional methods for learning node
representations (Kipf & Welling 2017| Scarselli et al. 2009; Veličković et al. 2018). Representa- tions at the graph level then constructed through application of different pooling operations which aggregate node representations into a single representation for the entire graph (Ying et al. 2018 Goyal & Ferrara 2018).

---

Under review as a conference paper at ICLR 2020
Our approach takes different perspective through the distributive modelling of graphs based on discrete substructure/subgrapb patterns across the graph dataset. This builds fixed size vector repre- sentations of graphs within distributed vector space created by training a neural language model which exploits the distributive hypothesis (Harris 1954). The positions of the distributed vector representations are contextualized by the subgraph patterns within graphs with respect to the pat- terns seen within other graphs across the dataset. This is analogous to the distributive modelling of arbitrary sized text documents in Le & Mikolov (2014), but the implementation typically closer to word2vec models in Mikolov et al.] (2013). We show that the construction and application of distributed representations of graphs can be summarized in three step framework. The first step involves reducing graphs into higher order subgraph patterns to create graph documents summariz- ing the patterns seen in each graph. Together the graph documents constitute a corpus of graphs. The second stage trains a neural language model on the graph document corpus, thereby building a distributed embedding for each graph within the dataset. In the third and final stage the embed- dings may be used with off- the-shelf learning systems for downstream tasks such classification, regression, clustering, or even in transfer learning scenarios.
To exemplify the construction of system described using this framework, we propose system which extends Graph2Vec called G2DR. Our proposed extensions allow distributed representations to be learned labelled and unlabelled graphs by incorporating the suggestion use node degrees for unlabelled nodes from (Shervashidze et al., 2011). Furthermore we directly use [hhevaahhizee ct al. (201T)'s Weisfeiler-Lchmar (WL) node relabeling algorithm for more computationally effi- cient algorithm for constructing the subtree vocabulary of the graph dataset which is equivalent to the WL algorithm described in Graph2 Like Graph2Vec, G2DR uses a skipgram with negative sampling to learn distributed representations of graphs based on subtree patterns induced with the WL algorithm. However we introduce vocabulary pruning heuristic to help the skipgram model further alleviate the issue of diagonal dominance which typically hurt graph kernel methods. This heuristic helps G2DR during our evaluation of the learned embeddings on graph classification tasks with publicly available graph kernel datasets (Kersting et al.) 2016). Datasets and tasks were lected to cover a range of graphs from small labelled graphs to large unlabelled graphs exhibiting complex substructures. To be comparatively fair within our assessment with kernel methods that inspire G2DR we utilised support vector machines (SVM) on the distributed representations and outperformed kernel methods and stands competitively amongst popular supervised GNN methods. This helps validate the distributed perspective as a useful inductive bias (Battaglia et al. 2018) for constructing graph level representations alongside pooling efforts, and a possible research avenue for more unsupervised techniques to graph-structured data.
In section 2 we provide comprehensive background into graph learning and related methods such as graph kernels. Section 3 describes our 3 stage framework for constructing models. Section 4 describes the construction of G2DR using the framework in Section 3. Section 5 describes the downstream application of the distributed representations in graph classification tasks with details about datasets and experimental setup, followed by results and discussion.
BACKGROUND AND RELATED WORK
Many real world phenomena such as chemical compounds (Petrucci et 2017), protein structures (Borgwardt et al. 2005), application process calls (Gascon et al. 2013). and social networks (Ya-) nardag& & Vishwanathan 2015) can be naturally represented using graphs. For example, in chemistry the graph makes an intuitive model for a molecule where nodes represent atoms and edges the bonds between them. Here the graph is an appropriate representation as captures not only the pres- ence of the atoms in the molecule, but the edges also capture the specific bonding patterns between the atoms which is important for distinguishing isomers that a classical chemical formula cannot describe (Petrucci al.) (017).. In other words, the resulting graph topology created by the relation- ships between the nodes in a graph reveal a structural complexity that can be analysed as a source of information in pattern recognition problems.
Described more formally, a graph is an abstract structure which defines a set of entities which are related in some way. Graphs contain nodes representing said entities with related nodes being con- nected by an edge which records the relation. We define G = (V. E) as a graph where V is a set of nodes and E. C (V x V) be a 2-tuple set of edges in the graph. Hence if and are nodes in G, their
2

---

Under review as a conference paper at ICLR 2020
relation is recorded with an edge (u, v) E E. The neighbours of node in graph 9 = (V, E), is the set of nodes which share an edge with v, denoted N ((() = {ul(e, u) E E}.
Graphs can be categorised depending on the attributes of the nodes and edges. A labelled graph is graph whose nodes or edges have labels, which may or may not be unique. Nodes and/or edges can be labelled, with the graphs then being called node- edge-labelled graphs respectively. Otherwise it is simply known as an unlabelled graph. Edges can either directed or undirected. Directed edges are uni-directional relations from a starting to node u to a target node and recorded as (u, v) E E and (u, v) o (v, u). Undirected edges describe bi-directional relationships between nodes u and v, hence (u, 2) (v, u).
2.1 GRAPH LEARNING AND KERNEL METHODS
An operational assumption made in learning with graph-structured data is that similar phenomena represented by graphs will also exhibit similar topological properties. Hence the ability to quantify the similarity of graph topologies is central to graph learning algorithms. As topological patterns are not intuitively well represented using classic feature vectors, research has predominantly focused on using kernel methods for machine learning tasks involving graphs. Kernel methods are machine learning algorithms which rely which define a relation or more contextually, a similarity over pairs of data points using their raw representations. Subsequently one can use kernel methods which can operate on kernels such as support vector machines (SVMs) (Yanardag & Vishwanathan 2015).
kernel for the pattern recognition task. Kernels are functions
Ideally kernel would be similarity function sim(g, 9") d, d E R where d or "distance" between graphs G and G' is small if they have similar structural properties, and a larger distance otherwise. The most intuitive measure of similarity is the binary indication of whether two graphs are topologically identical or isomorphic.
This is also known the Graph Isomorphism (GI) test. Despite being rudimentary measure of similarity, the complexity of the GI test is in NP and has neither been proven to be NP complete nor solved by polynomial time algorithm (Garey & Johnson 1990). Out of the twelve computational complexity problems listed in Garey and Johnson (Garey & Johnson 1990). only the GI problem and integer factorisation remain unsolved. In addition to being computationally expensive, the binary measure of similarity provided by GI based measures requires graphs to be identical or contain large identical subgraphs in order to be considered similar. This is too restrictive to be used effectively by machine learning methods. As result number of more flexible kernels based on approximate and inexact matching of graphs were proposed to address this problem.
Examples of these approximate kerness include graph edit distance methods and invariant based methods. Graph edit distance methods as proposed by [unkke & Allermann (1983); Neuhaus & Bunke (205) define set of graph edit operations and associates "cost" with each operation. The distance between the graphs can then be approximated by the minimum number and cost of edits needed to transform one graph into another. Slightly less intuitive, but powerful kernels exploit graph invariants. Kondor & Borgwardt (2008) introduced the skew spectrum where the invariant feature known as the graph skew is computed from the graph and extracted bispectral invariants can be compared into kernel value. Less than a year later, Kondor et al. (2009) proposed the graphlet spectrum which computes a spectrum of matrices relative a set of subgraphs. These features capture the number and position of the subgraphs which could then be compared between graphs.
Yanardag & Vishwanathan (0015) noted that kernel methods such as the graphlet spectrum are part a larger family of graph kernels which evaluate the similarity between graphs & and G' by decompos- ing them into atomic substructures such as random walks, shortest paths, graphlets, and subgraph patterns. The kernel value is then calculated by some function such as counting the number of com- mon substructures over G and G'. These kernel values would then be exploited by kernel methods performing the machine learning task. Such count based graph kernels can largely be grouped into three major families: those based on finite size subgraphs (Kondor et al. 2009; Horváth et al. [2004] Shervashidze et al. 2009), , subtree patterns (Shervashidze et al. [001 Shervashidze & Borgwardt 2009 Ramon & Gärtner 2003), and walks or paths (Borgwardt & Kriegel 2005| Kashima et al,
2003
Vishwanathan et al. 2010).
3

---

Under review as a conference paper at ICLR 2020
Graph kemels are intuitive, efficient and perform well on smaller benchmark datasets however hibit two limitations. Firstly, most kernels do not create explicit graph embeddings. This makes many out of the box machine learning algorithms that rely on vector embeddings such as Random Forests, Neural Networks, Naive Bayes, etc. unable to work with graph data. Secondly, the sub- structures which the graphs are decomposed have to be determined manually with well defined functions that help extracting such substructures from graphs. When such substructures are used in very large datasets this can lead to building extremely high-dimensional, sparse, and non-smooth representations of graphs (Narayanan et al. 2017).
2.2 DEEP LEARNING APPROACHES
More recently, success in the node classification tasks with graph convolutional networks (GCN) (Kipf & Welling 2017) and successful translation of attention models (GAT) (Veličković et al., 2018) brought a flurry of attention to learning representations of substructures and whole graphs using deep learning. Whilst majority of research in this regard has focused on learning repre- sentations of nodes (Goyal & Ferrara 2018 [Bttaglia et al. 2018) methods have been proposed to pool or aggregate substructure representations into graph level representations (Goyal & Ferrara 2018). A notable example is Ying et al. (2018) which hierarchically clusters and coarsens substruc- ture representations towards a graph representation with stacks of graph neural networks. These have produced excellent empirical results on graph classification datasets overcoming some of the limitations of graph kernels on datasets with large graphs. The recent GIN in Xu et al.] (2019) is currently the most powerful supervised example and is included in this work for comparison. How- ever these methods face interesting challenges as they are sensitive to network initialisations and jumping knowledge structures, and simple cructure-unawarr MLPs and single layer GCN models have been shown to display comparable performance to the most powerful models despite their great algorithmic and memory complexity shown in Luzhnica et al. (2019).
One deep learning approach that works slightly differently is Niepert et al. (2016) PATCHY-SAN.
This method incorporates ideas from work in kernels and assigns labels to nodes using the labelling procedure from the Weisfeiler-Lehman kernel (Shervashidze et al.) (011)), and sorts the node labels into a line. Subsequently, PATCHY-SAN defines receptive field around each node by selecting fixed number of nodes in d-hop neighbourhood where d is a natural number chosen by the practi- tioner. It then uses a standard convolutional neural network learn a representation of the graph. This method features prominently as a state of the art supervised approach to graph classification.
2.3 DEEP GRAPH KERNELS AND GRAPH2VEC
Our work is inspired by Deep Graph Kernels (Yanardag & Vishwanathan 2013) and Graph2 Vec (Narayanan et al.] 2017). Yanardag & Vishwanathan (2015) recognised that many graph kernel methods can be formulated as instances of the R R-Convolutional kernel framework (Haussler) 1999) which decomposes discrete structures such graphs into smaller substructure patterns to define kernels compatible with kernel methods like SVMs. Yanardag & Vishwanathan (2015) then utilised graph-edit distance methods or learning methods based on neural language models compute similarity matrix over the substructures to define kernel functions.
Vraph2Vec (Narayanan al. 2017) a specific model which builds upon principles of Deep Graph Kernels. The authors defined a recursive subgraph decomposition algorithm based on the Weisfeiler- Lehman test (Weisfeiler & Lehman 1968) to find subtree patterns for each node labelled and undi- rected graphs, subtree patterns are recorded as strings in documents for each graph. An extension of this specific algorithm based on Shervashidze et al. (201T) node relabel algorithm presented in the Section 4. A key deviation from Deep Graph Kernels is the subsequent input of the documents into a neural language model based on word2vec's skipgram architecture (Mikolov et al. 2013). This produced a scalable unsupervised approach to building distributed vector representations of graphs which captures generic structural properties of graphs. Yet the effectiveness of the embeddings, at least where data is publicly available, was only shown with classification datasets consisting of small labelled graphs. Nonetheless, the potential of the underlying methodology and potential motivates the general framework and the extensions we propose through G2DR described in the Section 4.
4

---

Under review as a conference paper at ICLR 2020
3 FRAMEWORK FOR CREATING MODELS WHICH LEARN DISTRIBUTED REPRESENTATIONS OF GRAPHS
We present a 3 stage framework for constructing models that can learn distributed representations of graphs.
1. Substructure pattern extraction: The first stage consists of decomposing each graph into subgraph patterns using methods that respect the R-Convolution kernel framework, such graphlets, subtree patterns, and walks. During this process hash function is used to record patterns to unique string labels within a dictionary which defines vocabulary of the different subgraph patterns found across the dataset. The string labels of patterns found in a graph are recorded in an associated text document called a graph document. This process creates a collection of graph documents corresponding each graph in the dataset forming a graph document corpus representative of the input graph dataset.
2. Distributed representation learning: This stage borrows concepts from statistical lan- guage modelling where the distributional hypothesis (Harris) 1954) is used to imbue se- mantic meaning to words and documents based on context. This distributional hypothesis suggests that words which are used and exist in the same context have similar meanings (Harris) 1954). We may adopt the same view about graphs by hypothesising that graphs which exhibit similar subgraph patterns entail similar properties and classifications. There- fore fixed distributed representations of graphs may be learned via neural language models such as word2vec (Mikolov et al.) 2013), doc2vec (Le & Mikolov 2014), or GloVe (Pen-) nington et al. 2014) on the corpus of graphs of stage 1.
3. Downstream application: The third and final stage involves the downstream application of the distributed representations learned in stage 2. As the learning models in stage 2 produce fixed-size vector representations of each graph, any off-the-shelf learning algorithm can readily be applied such as SVMs and multi-layer perceptrons for classification, or K-Means for clustering, or decision trees for regression.
Specific systems such as Deep Graph Kernels, Graph2 and Anonymous Walk Embeddings can all be described under this framework. Deep Graph Kernels (Yanardag & Vishwanathan, 2015) induce graphlets, shortest-paths, subtree patterns within the first stage associating the subgraph pat- terns with graphs to define a context. Within the second stage Deep Graph Kernels use a word2vec model where graph is contextualised by its induced subgraphs. Graph2Vec (Narayanan al. 2017) uses subtree-patterns extracted using an algorithm based on the Weisfeiler-Lehmaal graph isomor- phism test and contextualises each graph with its induced subtrees in the first stage. In the second stage, Graph2Vec uses a skipgram with negative sampling on the graph-induced substructure pairs. The more recently published Anonymous Walk Embeddings (AWE) (Ivanov & Burnaev] 2018) is similar to Graph2Vec except it induces anonymous walks from each graph for the first step. and uses these to build distributed representations with a skipgram model. In the next section, we present G2DR model which extends Graph2vec described using this framework above.
4 PRESENTING G2DR IN TERMS OF THE FRAMEWORK
4.1 STAGE 1: SUBTREE DECOMPOSITION VIA "EISSEILER-LEHMMNN REDUCTION
In the first stage G2DR utilises a subtree decomposition algorithm based on the Weisfeiler-Lehman (WL) graph isomorphism test. Amongst the possible algorithms tackling graph isomorphism the Weisfeiler-
(WI.) test (Weisfeiler & Lehman 1968) stands out as particularly effective solution that differentiates graphs based on the composition of the subtree patterns extracted from the nodes, and works for most cases except those covered in Cai et al. (1922). In its essence, the WL test consists of iteratively assigning unique labels to the multisets formed by nodes label with the labels of its neighbours. As this is performed on each node within the graph, the dth iteration of node relabeling is equivalent to encoding subtree pattern formed of node and the neighbourhood within d' hoho If the composition of assigned labels differs between graphs at any iteration, the WL test considers them non-isomorphic.
5

---

Under review as a conference paper at ICLR 2020
We wish to find subtree patterns of degrec/depth for every node within the graph of every graph in the dataset. This achieved as a byproduct of the WL test's node relabeling (Shervashidze et all, (01I) and is fully described in Algorithm [ for reference. G2DR utilises subtree patterns over other atomic substructures which could compose graphs for two reasons. Firstly, subtrees are higher order substructures
nodes which offer richer description of not only the nodes in graph but the local neighbourhood structures which when sampled can give better embeddings of graphs. Secondly, compared to linear patterns such walks and paths, non-linear subtree patterns capture the structure of node neighbourhoods more generally (Narayanan et al. 2017).
Algorithm 1: WL-Rellbel (G,
Input G (2 92. In. set of n graphs
the desired degree of rooted subgraph found from each node
Output: G with each of the node relabellings made at each iteration saved all nodes of all graphs for i 0 d, by 1 do
Multiset-Label determination
if set Mx(e) lo()) X(v)
if > 0, assign multiset-label M, (v) to each node in G for all G G which
consists the multiset (4-1(u)]u (V))
Sorting each multiset
Sort elements in (v) in ascending order and concatenate them into string 8; (v)
Concatenate (v) prefix to (v) and set the resulting string as s,
Label Compression
Sort all of the strings s;(v) for all e form G E G in ascending order.
Map each string s; (v) to a new compressed label, using a hash function
f: + Σ such that (s:(t)) f(s(ww) iff (T) = s,(w)
Node Relabelling
Set 4(v) (s)( for all nodes in G E G
end
Algorithm generates rooted subgraphs (subtrees) t(d) of depth around every node of graph G E G. In this iterative algorithm starting from = 0 to i = d, hash function is initialised at the beginning of each iteration which maps the subgraph pattern to compressed multiset labels. When i == no subgraph needs to be extracted and hence the original label of node is returned (line 1). If the graph is unlabelled, the degree of node is set as its label. Using degree as the initial node label can also apply labelled graphs and will effectively construct vocabulary of structural patterns (Shervashidze et al. (011). When >> the labels of the previous iteration are used to create new compressed labels. For each node we find the previous iterations' labels of all v's neighbours as a multi set (4-1 (u)lu E (N)) and sort the elements in ascending order. The sorted set is then turned into string (y(v) with v's label in the previous iteration prepended to it. These strings are passed into the hash function to assign new compressed labels for the multiset string s; (v))) Note that this makes sure that if the same subgraph pattern of is found in another graph, that node is given the same compressed label due to the hashmap, simultaneously building "vocabulary" V of the different subtree patterns in G. Furthermore, at each iteration of this algorithm compressed labels (v) are produced which correspond to subtree patterns of depth i rooted at v.
At the end of algorithm each graph G5 E will have relabellings for each the nodes v E Gy in string form s:(v) which we store attributes inside of NetworkX graph object (Schult) 2008). For each graph G E G, we generate a graph document by writing each of the compressed relabellings sc(v) for all i [1, d. of every node G into text file. All of the graph documents together form our corpus of graphs. Alternatively one can see this as a dataset recording every pair of graph with its induced subtree patterns (9,, 1),4 E

---

Under review as a conference paper at ICLR 2020
Algorithm| I deviates from the algorithm presented in the Graph2 paper (Naaayanan et al. 2017) where multisets representing subtree patterns are recursively constructed using the labels of neigh- bours of target node for each node of all graphs in the dataset, and then assigned to that node. Instead the proposed WIL-Relabel algorithm iteratively assigns compressed multiset labels based on nodes previous multiset label, and in the case of an unlabelled graph, runs initial relahelling based on the degree of the node. Our changes bring three advantages. One, it allows extraction of subgraph patterns for unlabelled graphs, allowing G2DR to learn distributed representations of unlabelled graphs and labelled graphs; and can apply directly to directed graphs. Two, during the iterative process, the subtree patterns of each degree prior to the user specified degree are observed and can be used or saved without finding them again. Three, the compressed labels are a memory efficient alternative to saving entire subgraph patterns for each node.
4.2 STAGE 2: DISTRIBUTED REPRESENTATION LEARNING WITH SKIPGRAM USING NEGATIVE SAMPLING
Once the graph documents have been generated using algorithm T it is possible to learn a distribu- tional vector space in a completely unsupervised manner using a distributed vector space model. We follow Graph2Vec' Vec's i example (Narayanan et al. (017)) and use a skipgram model with negative sam- pling (Mikolov et al. 2013). In order to exploit the distributive hypothesis the "context" of graph is defined as the subtree patterns induced during stage 1. The data DD upon which the skipgram trained consists of Graph-Subtee Subtree pairs (G.. E where graph Gi E G and e V is a sub- tree pattern in the vocabulary induced during application of the WL-Relabel algorithm. Distributed representations can then be learned by optimising the objective function:
==
ΣΣ (((9..) E ()oooga S.) + hs EANE [log (loga(-0; (w]) IEEGEE
Where & E R. Gix6 is the ā dimensional matrix of graph embeddings of the graph dataset G, and Φ; is embedding for G; E G. Similarly, S E g are the ó dimensional embeddings of the subtree patterns in the vocabulary so St represents the vector embedding corresponding to subtree pattern f. The embeddings of the subtree patterns are also tuned but ultimately not used, as we are interested in the graph embeddings in Φ l is the number of negative samples with iN being the sampled con- text subtree, drawn according to the empirical unigram distribution (t) = (EI,G,,G.GG..tEED))
DI
4.2.1 FURTHER TACKLING DIAGONAL DOMINANCE WITH VOCABULARY PRUNING
A main limitation of graph kernel methods based on computing kernels across frequency vectors of induced subgraph patterns is the number of subgraph patterns used to compare graphs to one another. For subtree patterss extracted using the WL algorithm the degree of subtrees to be extracted from the graphs in the dataset directly affects the vocabulary size. As the subtree degree to be analysed increases, the number of unique substructure patterns which enter the vocabulary also increases. For example, using the WL relabeling algorithm on the NCII dataset induces 267 subtrees of degree 1, 4033 of degree and 22923 unique subtree patterns of degree 3 across the graphs of NCII.
Graph kernels would then typically have to compute the kernel between two graphs based on fre- quency vectors whose dimensions the size of the vocabulary considered. Consequently as the number of features (vocabulary size) grows, we run into the sparsity problem, where only a few substructures will be common across the graphs. This leads the phenomenon known as diagonal dominance, where graphs become more similar to themselves but more distant from other graphs in the dataset (Yanardag & Vishwanathan 2015).
The main contribution of Deep Graph Kernels and subsequent methods was the use of the embed- ding method to produce dense low dimensional distributed representations. However, we can see from Equation| 1 the graph embeddings will still be affected by the embeddings S, of infrequently appearing subgraph patterns. Hence, graph embeddings are still indirectly are affected by the con- cept of diagonal dominance. A naive yet natural fix which addresses this concern infrequent subgraphs is to modify the vocabulary so that a subgraph pattern has to occur a set minimum num- ber of times in the dataset to be included in the vocabulary and hence the skipgram model. We chose
7

---

Under review as a conference paper at ICLR 2020
to set a minimum threshold of 2 occurrences to be included in the vocabulary if half the number of singleton subgraph patterns was higher than the number of graphs in G.
STAGE 3: EVALUATION ON DOWNSTREAM GRAPH CLASSIFICATION
After training the graph neural language model, contains the distributed representations of every graph 9, G, where the embedding of 9; is denoted 4; The task agnostic nature of the embeddings allows any downstream task such as classification, regression, clustering, etc. to be performed on the graphs of G simply by applying the appropriate methods which accept vector inputs.
We utilised the embeddings trained on graph classification datasets to assess the suitability of the approach, and as benchmark against other graph learning methods. One of the key motivations of this work was to assess the suitability of the distributed representations beyond small labeled graphs towards larger (also unlabelled) graphs where the limitations of specification in graph ker- nels were expected to show. For ease of replicability a suite of public datasets were selected from Kersting al. (2016) based on frequency papers and size. The selection of benchmark datasets and tasks range from smaller, classic datasets with graphs averaging 17 nodes in size tasked on binary classification, to significantly larger graphs averaging over 500 nodes in size over 11929 examples in a multi-communig prediction task. This list includes the MUTAG (Debnath et al., 1991 PTC (Helma al., 2001). PROTEINS (Borgwardt et al., 2005) NCII, NCII09 (Wale et al. 2008), REDDIT-BINARY. REDDIT
(Yanardag & Vish- wanathan 2013) datasets. The datasets represent applications from a number research domains including: chemoinformatiis, bioinformatics, and social networks whose properties are summarised in Table 3
REDDIT-MULTI-22
in the supplementary material.
We were particularly keen investigate the case of unlabelled graphs and large datasets with mul- tiple graph labels where the 'large' applies to both the number of data points as well as the size of the graphs therein. The large graphs make the representation learning inherently more complex as the number of expected subgraph patterns substantially increases (Yanardag & Vishwanathan 2015) and questions the necessary specificity required to compare large graphs each other well as large graphs to small graphs.
5.1 EXPERIMENTAL SETUP
For fairer comparative analysis with graph kernel methods and experimental setups of Deep Graph Kernels Yanardag & Vishwanathan (2015) and Vec Narayanan et al. (2017). G2DR uses an off-the-shelf C-Support Vector Machine implemented the SciKit-Leern package (Pedregosa et al.) 2011) the learned embeddings for each dataset. 10 fold cross validation used evaluate test classification accuracy. The C' value for each fold was independently tuned using training data from that fold. In order exclude random effects of the fold assignments, each experiment repeated 10 times, and mean classification accuracies with their standard deviations were recorded.
Results are presented over two section, dedicated to datasets whose graphs labelled, and the other dedicated to datasets of graphs which are initially unlabelled and hence get labelled through Algorithm using the degree of the nodes in Shhrrvassiddee al. (2011) T). For comparative purposes of existing methods we have selected prominent methods applicable to each of the graph types and recorded the results they have published.
G2DR was experimented using embedding dimensions of 16, 32, 64, 128, 256, 512, 1024, 2048 a consideration of subtree degrees of 1,2,3. For each configuration the neural network was trained over 1000 epochs with an initial learning rate of 0.5 set on an linear decay over the epochs towards 0.001. A negative sampling size of 10 was used throughout as Graph2 Vec (Narayanan et al. 2017). The best downstream results on the different embedding configurations is reported in the results of the next section.
5.2 RESULTS: LABELLED GRAPHS
ssoww that the labelled graph datasets have range of different properties, including datasets with small graphs and a small number of distinct labels such as the MUTAG dataset to larger datasets with larger graphs and number of distinet labels. It was expected that lower-order substructure
8

---

Under review as a conference paper at ICLR 2020
Table I: Mean classification accuracy and standard deviation on labelled graph classification, itali- cised results indicate an unsupervised model for learning representations or kernels.
Dataset
MUTAG
PTC
PROTEINS
NCII
NC1109
node2vec
72.62 1 10.20
55.85 - 8.00
57.49 + 3.57
54.89 + 1.61
52.68 1.56
sub2vec
61.05 + 15.79
59.99+6..3
53.03 + 5.55
52.84 1.47
50.67 + 1.50
Graphlet Kerel
81.66 2.11
57.26+1.44
71.67 0.55
62.28 = 0.29
62.60 0.19
Shortest Path Kernel
2:.4
58.24
75.07 0.54
73.00 1:00:02: 0.24
73.00 0.26
WL Kernel
3.00
$6.97
72.92
80.13 0.50
80.22 + 0.34
Deep GK
82.66 4: 1.45
4.73
71.68 + 0.50
62.48 0.25
62.69 + 0.23
Deep SP
87.44
60.08 = 2.55
75.68 0.54
73.53 0.51
73.26 7
Deep WI.
+2.94+2.66
59.17 1.56
73.30 + 0.82
80.31 0.46
80.32 0.33
Vreph2Vec
83.15
60.17 6.86
73.30 + 2.05
73.22 1.81
74.26 1.47
AWE
87.87 + 9.76
PATCHY-SAN (K=10)
88,95 4.67
62.29 1 5.68
75.89 + 2.76
76.34 - 1.68
76.37 1.43
SUM-MLP (GIN-O))
89.4
64.60 + 7.00
76,20 + 2.80
82.7 1.70
SUM-MLP (GIN-E)
89.0 - 6.00
63.70 + 8.20
75.9 + 3.80
82.7 + 1.60 1.60
G2DR + SVM
89.12 + 1.71
63.84 + 3.19
75.61 + 1.31
83.70 = 0.70
83.79 0.57
embedding methods such as node2vec (Grover & Leskovec 2016) and sub2vee (Adhikari et al. 2017) would perform well in datasets of small graphs with few labels, but gradually perform worse as the graphs became more complex. As shown Table [ these methods initially perform well on smaller datasets, but suffer from the naive agglomeration schemes for larger datasets, barely performing better than random on NCI1 and NC1109. Sub2vec samples only one random walk of fixed length from the given graph and learns its representations using fixed length linear context skipgram models. This prevents sub2vec from learning structurally meaningful embeddings of the entire graph, and suffers considerably when applied to larger graphs as can be seen in the difference between MUTAG and NCI109.
The graph kernels perform better overall, as they have been purpose built for this task, with the WL- kernel performing particularly well in the larger datasets, which also initially prompted the decision to use subtrees in G2DR. The deep graph kernels, Graph2 and AWE, attempt overcome the limitation of previous methods by addressing the sparsity problem of graph kernels. This raises the performance significantly over node2vee and sub2vec, however only marginally better than the traditional graph kernels upon which they are based.
The proposed embedding learning system combined with an out-of-the-box C-SVM returns highly competitive results. The success of this method is attributed to the descriptive power of non-linear subgraph patterns described in WL-subtrees and the usage-based representations learnt of the sub- graphs within the graphs leading to similar graphs being closer to each other, and dissimilar graphs more distant, allowing the C-SVM to compute more effective hyper planes which maximise the separation of graphs of different classes. The improvement over Graph2Vec well Deep Graph Kernels and AWE is based on the consideration of vocabulary pruning which overcomes the indirect issues of diagonal dominance (Yanardag & Vishwanathan 2015) discussed in section 4.2.1. The heuristic can also be introduced to both of their systems. The unsupervised system can be shown to perform competitively against supervised GNN methods such as PATCHY-SAN and GIN, however we see its limitations in the unlabelled graph case in the next section.
The PTC dataset is particularly challenging dataset for all methods. Despite being relatively small dataset with an average graph size of 25.5 nodes, there are 19 distinct labels allowing large number different subgraph patterns which may have the same "shape" but are different structures as they have different node labels. This can make the attraction between graphs of the same class difficult as they may be exhibiting forms diagonal dominance which cannot be alleviated by the encoding process of the embedding method particularly over the small number of graphs in the dataset. NCII and NCI109 in comparison have many more graphs in their dataset.
5.3 RESULTS: UNLABELLED GRAPHS
The social network datasets of Yanardag & Vishwanathan 2015). distinguish themselves from the previous set of graphs in 3 ways. Firstly, the graphs within the dataset are unlabelled hence the proposed system labels the nodes within the graphs by their degree and cannot be utilised in the

---

Under review as a conference paper at ICLR 2020
Table 2:
Mean classification accuracy and standard deviation on unlabelled graph elassification,
italicised results indicate an unsupervised model for learning representations or kernels.
Datasets
REDDIT-BINARY
REDDIT-SK
REDDIT-12K
Graphlet Kernel
0.148
31.82 = 0.08
Deep GK
78.04 0.39
41.27 0.18
32.22 0.10
AWE (Data Driven)
87.89 2.53
50.46
39.20 + 2.09
PATCHY-SAN (K=10)
86.30 = 1.58
0.70
41.32 0.42
2D-CNN
89.12
52.11
48.13 = 1.47
SUM-MLP (GIN-O)
92.40 2.50
57.50 + 1.50
SUM-MLP (GIN-c)
92.2 + 2.30
57.00 + 1.70
G2DR + SVM
82.32 + 1.21
52.82 + 0.52
41.02 + 0.91
unmodified Veee system. Secondly, the graphs are considerably larger than those seen in the classic benchmarks, having a direct effect on the complexity and number of substructures within, which in turn have a significant effect on the vocabulary size used in the neural language model. Finally, for REDDIT-5K and REDDIT-12K, is a multi-class classification task as opposed to the previous binary classification tasks. As a result, several of the previous methods are unsuitable for this task, and we have included another system, 2D-CNN (Tixier et al., 2019), which represents graphs as multi-channel image-like structures so that they can be fed into image convolutional neural networks. This system is another supervised model alongside PATCHY-SAN, GIN-O and GIN-e.
As seen in table 2 G2DR performs better than the GK kernel and the Deep Graph Kernel variant Deep GK as expected. However, it fails to achieve the performances of supervised methods such as 2D>CNN and GIN as the specificity and sheer number, of unique subgraph patterns makes limita- tions of Graph2Vec apparent. A quick investigation showed that the lower performance could partly be attributed the extremely large vocabulary of subtrees that is produced from the combination of very large complex graphs and a high number of data points in the dataset. This manifests into two related problems in the system. Foremost, whilst Graph2 Vec reduces the effect of diagonal dom- inance by exploiting the distributional hypothesis and dimensionality reduction via the skipgram model, the sheer number of infrequently occuring subgraphs can still inadvertently cause diagonal dominance. Vocabulary pruning helps slightly, and can be seen push the performance slightly be- yond AWE in the REDDIT5/12K problem set. AWE performs better than G2DR in the REDDIT BINARY dataset, as seen in graph kernel method work Vishwanathan et al. (2010) different sub- structures work better in different cases. This can also be seen in the labelled case amongst the deep graph kernels. Nonetheless the relatively high results of AWE and G2DR against supervised GNN methods, makes unsupervised distributed representation learning an interesting option for learning vector representations of graphs.
CONCLUSION
We have presented a general framework for constructing models which can learn distributed rep- resentations of graphs, that can be further generalised other discrete structures under the R- Convolution kernel framework. This combines the theoretic frameworks of Deep Graph Kernels and advancements under Graph2Vec exemplified by our own instance. G2DR, which builds upon both previous works. G2DR is a scalable system which can leamn task agnostic distributed repre- sentations of unlabelled/lahellldd and directedtundirretee graphs of arbitrary size in a data driven manner. The suitability of this unsupervised approach is validated against graph kernels and su- pervised neural approaches in downstream graph classification tasks, where G2DR displays strong state of the art results despite its unsupervised nature and use of off-the-shelf SVM. This enables the application of G2DR as tool to numerous real world questions on graphs in different research domains. Furthermore, this suggests that the distributional perspective of graphs compositions of discrete substructures is an useful inductive bias for building smooth vector representations of graphs along other research in hierarchical graph coarsening and substructure pooling.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B. Aditya Prakash. Distributed representa- tions of subgraphs. 2017 IEEE International Conference on Data Mining Workshops (ICDMW),
pp. 111-117, 2017.
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner,
Caglar Gulcehre, Francis Song, Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani,
Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wier-
stra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Re- lational inductive biases, deep learning, and graph networks. arXiv, 2018. URL https:
7/arxiv. wwtp 1806.
Karsten M. Borgwardt and Hans-Peter Kriegel. Shortest-path kernels graphs. In Proceedings of the Fifth IEEE International Conference on Data Mining, ICDM '05, pp. 74-81, Washington, DC, USA, 2005, IEEE Computer Society. ISBN 0-7695-2278-5.. doi: 10.1 10.1109/CDM.2000.
Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(1): 47-56, January 2005. ISSN 1367-4803.
H Bunke and G Allermann. Inexact graph matching for structural pattern recognition. Par- tern Recognition Letters, 1(4):245 - 253, 1983. ISSN 0167-8655. doi: https///oi.org 10.101601667-865563990900883
URL http: /wwp///ww...../// sci encedi rect. wwm com/sciennee.
ktt.ccee/.11011766555338
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identification. Combinatorica, 12(4):389 Dec 1992. ISSN 1439-6912. doi: 10.
1007/BF01305232. [RRL/attss://cc..oo wtw./////...11110001111001111111
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):786-797, Feb 1991. ISSN 0022-2623. doi: 10. 16.001//0000002046.
Michael R. Garey and David S. Johnson. Computers and Intractability; Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990. ISBN 07167 10455.
Hugo Gascon, Fabian Yamaguchi, Daniel Arp, and Konrad Rieck. Structural detection of android malware using embedded call graphs. In Proceedings of the 2013 ACM Workshop Artificial Intelligence and Security, AlSec '13, pp. 45-54, New York, NY, USA, 2013. ACM. ISBN 978-
1-4503-2488-5. doi: 10. 0..144/25173122251733
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledgee Based Systems, 151:78 94, 2018. ISSN 0950-7051. doi: https://doi. org/10. 100i:000006/1.nnsyy2200000101 201. 022. ARLhttpp: http::/wwwww.ii....... www.eiiiiiiiciircc......... com/ sccssciooo aaciende ence/
attricle/p11/509500011111
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
KDD '16, pp. 855-864, New York, NY, USA, 2016. ACM. ISBN 978- 978-1-45503-4232-22 doi: 10. 1145/2939672.29397554 URL DRRL:ttp:///aa acm www. 1ttp:/....115//93333 29397754
Zellig S. Harris. Distributional structure. WORD, 10(2-3) 1954.11
1954. doi: 10.1080/0043995
David Haussler. Convolution kernels on discrete structures. Technical report, University of Califor- nia Santa Cruz, Santa Cruz, CA, USA, 1999.
C. Helma, R. D. King, S. Kramer, and A. Srinivasan. The predictive toxicology challenge 2000 2001. Bioinformatics, 17(1):077-108 2001. doi: 10. 10.009/hionnfrrmaicc/1....100
11

---

Under review as a conference paper at ICLR 2020
Tamás Horváth, Thomas Gärtner, and Stefan Wrobel. Cyclic pattern kernels for predictive graph mining. Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '04, pp. 358-167, New York, NY, USA, 2004. ACM. ISBN doi: 10. 10.1145/101405..1 105110447221111172...
1-581 13-8818-8-..
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In Jennifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2191-2200, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL B VBC/ivanovl 8a. html
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the Twentieth International Conference on International Conference on Ma- chine Learning, ICML'03, pp. 321-328. AAAI Press, 2003. ISBN 1-57735-18944. URL
http::/dl acm. org/ wttp//ttttttteoooooooooo.etttttt wwt.tiii.iiiinnnnooo wtw..ccmmmmccnmeeecc 3041879
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann, Bench- mark data sets for graph kernels, 2016. URL
tu do-dortmuund.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Risi Kondor and Karsten M. Borgwardt. The skew spectrum of graphs. In Proceedings of the 25th International Conference Machine Learning, ICML '08, pp. 496-503, New York, NY, USA, 2008. ACM. ISBN 778-1-660558-20544 doi: 01144///30156.139022 URL http:
//doi. acm. wtt..//rrr1111111111111111100010 113.0900116611111999 1390219
Risi Kondor, Nino Shervashidze, and Karsten M. Borgwardt. The graphlet spectrum. In ACM International Conference Proceeding Series, volume 382, pp. 67, 01 2009.
Quoc Le and Tomas Mikolov. Distributed representations of sentences and documents. In Proceed- ings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICML'14, 14, pp. 11-1188-11-116. JMLR.org, 2014. URL http: //dl. acm. org/ citation wtt.ecfcmmmmm.mmm00
3045025
Enxhell Luzhnica, Ben Day, and Pietro Liò. On graph classification networks, datasets and baselines. In 36th International Conference on Machine Learning, ICLM' 19, 2019.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word repre- sentations in vector space. In 1st International Conference on Learning Representations, ICLR 2013, Scoutsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings, 2013. URL. www./agg/////oooooo/ooo.//...ere httg///s//331111 /101 300.37711111113
http://arxiv. or.. abs /
Annamalai Narayanan, Mahinthan Chandramohan, Rajasckar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. CoRR, 0/5/1777.05000 2017.
05005
M. Neuhaus and H. Bunke. Self-organizing maps for learning the edit costs in graph matching. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 35(3):003-514, June 2005. ISSN 1083-4419. doi: 10.1109TTSMCB www.2005.8444. 846635. 200..866635.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. CoRR, abs/1605.00 abs/1605.05273, 2016. URL http:///axxiv...r//bba/
05273
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Couraaeaau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2823 2011.
12

---

Under review as a conference paper at ICLR 2020
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543,
2014. URL http: www. wwwwwb.www.......... org/ http///toooooyoolllaLa11
R.H. Petrucci, F.G. Herring, J.D. Madura, and C. Bissonnette. Generul Chemistry: Principles
and Modern Applications. Pearson Education, 2017. ISBN 9780133400588. URL https:
wooogleec..uk.... //books.. google. co. w...u//boe wukkbookss.o Ber.cccKss.---EECCAAAAEEEE
Jan Ramon and Thomas Gärtner. Expressivity versus efficiency of graph kernels. In Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences, pp. 65-74, 2003.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. Trans. Neur. Netw. 20(1):61-80, January 2009. ISSN 1045- 9227. doi: 10. 10.109NNN..000.2000
URL http: www.dx..ooo..oooooooo www.oorgg//oooo wtt.://///.....//...... 1109/TNN.
2008. 2005605
Daniel A. Schult. Exploring network structure, dynamics, and function using networkx. In In Proceedings of the 7th Python Science Conference (SciPy), pp- 11-15, 2008
Nino Shervashidze and Karsten M. Borgwardt. Fast subtree kernels on graphs. In Proceedings of the 22Nd International Conference on Neural Information Processing Systems, NIPS'09, pp. 1660-1668, USA, 2009. Curran Associates Inc. ISBN 978-1-61557-911 /RL http:://l.. acm. www.grgggtta...o. on cfm? cfm22d=2384093. 00E.4449.3...9222.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In David van Dyk and Max Welling (eds.), Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, vol- ume 5 of Proceedings of Machine Learning Research, pp. 488-495, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16-18 Apr 2009, PMLR.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lhhman graph kernels. J. Mach. Learn. Res., 11-2539-2560 November 2011. ISSN 1532-4435.
Antoine J.-P. Tixier, Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Graph classification with 2d convolutional neural networks. In Igor V. Tetko, Vēra Kürková, Pavel Karpov, and Fabian Theis (eds.), Artificial Neural Networks and Machine Learning ICANN 2019: Workshop and Special Sessions, pp. 578-593, Cham, 2019. Springer International Publish- ing. ISBN 978-3-030-30493-5
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. /RR ftt.:e/eee/ooommmee....oooo
S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kerels.. J. Mach. Learn. Res., 11:1201-1242, August 2010. ISSN 1532-4435.
Nikil Wale, Ian A. Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowl. Inf. Syst., 14(3):447337, March 2008. ISSN 0219-1377. doi: 0011077//101155007-000003
B. Weisfeiler and A. A. Lehman. A reduction of graph canonical form and an algebra arising during this reduction. Nouchno-Techhicheskeee Informatsia, 999):22-16 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openrevien ew. www. fest/foormmidddrrGGttt d A5Km
Pinar Yanardag and S. V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '15, pp- 1365 1374, New York, NY, USA, 2015. ACM 978-1-5503336666 2783417. URL http:://ddd acm. htt....o......11////2333333333 2783441
doi: 10.1145/278,
13

---

Under review as a conference paper at ICLR 2020
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec.
Hierarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference Neural Information Processing Systems. NIPS' 18, pp. 4805- 4815, USA, 2018. Curran Associates Inc. URL http:/ /dl. aam. acm.orggcciatiinn. cfm?
id=3327345. 3327389
14

---

Under review as a conference paper at ICLR 2020
A
SUPPLEMENTARY MATERIAL: FIGURES AND TABLES
Datasets
Size
Classes
Avg. Nodes
Distinct Labels
MUTAG
188
17.93
7
PTC
344
2
25.5
19
PROTEINS
1113
39.06
3
NCII
4110
29.87
37
NCT109
4127
29.68
38
REDDIT-BINARY
2000
2
429.61
unlabelled
REDDIT-MULTI-SK
4999
508.52
unlabelled
REDDIT-MULTI-122 12K
11929
11
391.41
unlabelled
Table 3: Properties of the benchmark graph classification datasets.
15


Reviews:
[{"review_id": "ryexkwlRKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "Strength:\n-- The paper is well written and easy to follow\n--  Learning the unsupervised graph representation learning is a very important problem\n-- The proposed approach seems effective on some data sets.\n\nWeakness:\n-- The novelty of the proposed approach is very marginal\n-- The experiments are very weak. \n\nThis paper studied unsupervised graph representation learning. The authors combined the techniques for Deep Graph Kernels and Graph2Vec, which essential extract substructures as words and the whole graph as documents and use doc2vec for learning the representations of both graphs and substructures. Experimental results on a few data sets prove the effectiveness of the proposed approach. \n\nOverall, the paper is well written and easy to follow. Learning unsupervised graph representation learning is a very important problem, especially for predicting the chemical properties of molecular structures. However, the novelty of the proposed method is very marginal. Comparing to the Deep Graph kernel methods, the authors simply changed from the word2vec style methods to doc2vec style methods. The paper could be better fit to a more applied conference. Moreover,  I have some concerns on the experiments. \n(1) The data sets used in this paper are too small. For unsupervised pretraining methods, much larger data sets are expected. \n\n(2) The results in Table 1 are really weird. Why do the performance of your method have a much lower standard deviation? It is really hard to believe the proposed methods have much stable performance compare to other methods.  Can you explain this?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xV-886FS", "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": "This paper proposes a framework for learning distributional representations of graphs in the following way: First, each graph is represented as a collection of subtree patterns. Second, the neural language model of doc2vec is applied to these collections of patterns to learn graph embeddings. These embeddings are then exploited in downstream analyses such as classification. Overall, the idea of formulating graph representation learning as a language model is interesting. The experiments show that it perform better than kernel methods. I have the following major comments:\n\n1. The main issue with this method is the computational complexity due to exponential growth of vocabulary of subtree patterns size for large graphs. Particularly , for experiments with unlabeled graphs, the performance is significantly worse than CNN based models. How would the performance be on unlabeled small graphs? For example, have you verified the performance on small graphs of section 4.2 when labels are ignored? (downstream clustering task)\n\n2. The neural language models rely on the concept of context in documents. How the concept of context defined for subtree patterns extracted by Weisfeiler-Lehman algorithm?\n\n3. The issue of diagonal dominance should be clarified. How does the pruning tackles this issue?\n\n ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxnW6eCFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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 paper presents an unsupervised method for graph embedding. \n\nDespite having good experimental results, the paper is not of the quality to be accepted to the conference yet. The approach is rather a mix of previous works and hence not novel. \n\nIn particular, the algorithm for WL decomposition is almost fully taken from the original paper with a slight modification. Advantage of using it for unlabeled data is poorly motivated as unlabeled graphs can easily take statistics such as degree as the node labels, which was shown well in practice. \n\nModified PV-DBOW is in fact the same algorithm as the original CBOW model but applied to different context. It has been used in many papers, including Deep GK, graph2vec, anonymous walks. \n\nAlso, the Figure 1. is taken from the original paper of WL kernel. The algorithms 1 and 2 are taken from the original papers with slight modifications. \n\nThere is no discussion of [1], which uses CBOW framework, has theoretical properties, and produces good results in experiments. There is no comparison with GNN models such as [2]. \n\nI would be more interested to see explanation of the obtained results for each particular dataset (e.g. why MUTAG has 92% accuracy and PTC 67%); what so different about dataset and whether we reached a limit on most commonly used datasets. \n\n[1] Anonymous Walk Embeddings? ICML 2018, Ivanov et. al. \n[2] How Powerful are Graph Neural Networks? ICLR 2019, Xu et. al.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a general framework to construct unsupervised models for representation learning of discrete structures. The reviewers feel that the approach is taken directly from graph kernels, and the novelty is not high enough. 
Decision: Reject