Title: SHIFT AGGREGATE EXTRACT NETWORKS

Abstract: The Shift Aggregate Extract Network (SAEN) is an architecture for learning representations on social network data. SAEN decomposes input graphs into hierarchies made of multiple strata of objects. Vector representations of each object are learnt by applying shift, aggregate and extract operations on the vector representations of its parts. We propose an algorithm for domain compression which takes advantage of symmetries in hierarchical decompositions to reduce the memory usage and obtain significant speedups. Our method is empirically evaluated on real world social network datasets, outperforming the current state of the art.

1. INTRODUCTION:

Many different problems in various fields of science require the classification of structured data, i.e. collections of objects bond together by some kind of relation. A natural way to represent such structures is through graphs, which are able to encode both the individual objects composing the collection (as vertices) and the relationships between them (as edges). A number of approaches to the graph classification problem has been studied in graph kernel and neural network literature.

Graph kernels decompose input graphs in substructures such as shortest paths (Borgwardt & Kriegel, 2005) , graphlets (Shervashidze et al., 2009) or neighborhood subgraph pairs (Costa & De Grave, 2010) . The similarity between two graphs is then computed by comparing the respective sets of parts. Methods based on recursive neural networks unfold a neural network over input graphs and learn vector representations of their nodes employing backpropagation though structure (Goller & Kuchler, 1996) . Recursive neural networks have been successfully applied to domains such as natural language (Socher et al., 2011) and biology (Vullo & Frasconi, 2004; Baldi & Pollastri, 2003) . An advantage of recursive neural networks over graph kernels, is that the vector representations of the input graphs are learnt rather than handcrafted.

Learning on social network data can be considerably hard due to their peculiar structure: as opposed to chemical compounds and parse trees, the structure of social network graphs is highly irregular. Indeed in social networks it is common to have nodes in the same graph whose degree differs by orders of magnitude. This poses a significant challenge for the substructure matching approach used by some graph kernels as the variability in connectivity generates a large number of unique patterns leading to diagonally dominant kernel matrices.

We propose Shift Aggregate Extract Networks (SAEN), a neural network architecture for learning representations of input graphs. SAEN decomposes input graphs into H-hierarchies made of multiple strata of objects. Objects in each stratum are connected by "part-of" relations to the objects to the stratum above.

In case we wish to classify graphs we can use an H-hierarchical decomposition in which the top stratum contains the graph G that we want to classify, while the intermediate strata contain subgraphs of G, subgraphs of subgraphs of G and so on, until we reach the bottom stratum which contains the vertices v of G.

Unlike R-convolution relations in kernel methods (which decompose objects into the set of their parts), H-hierarchical decompositions are deep as they can represent the parts of the parts of an object.

Recursive neural networks associate to the vertices of the input graphs vector representations imposing that they have identical dimensions. Moreover, the propagation follows the edge connectivity and weights are shared over the whole input graph. If we consider that vector representations of nodes (whose number of parents can differ by orders of magnitude) must share the same weights, learning on social network data with recursive neural networks might be nontrivial.

SAEN compensates the limitations of recursive neural networks by adding the following degrees of flexibility:

1. the SAEN computation schema unfolds a neural network over H-decompositions instead of the input graph, 2. SAEN imposes weight sharing and fixed size of the learnt vector representations on a per stratum basis instead of globally.

Indeed SAEN allows to use vector representations of different sizes for different strata of objects (e.g. graphs, subgraphs, subgraphs of subgraphs, edges, vertices etc.) The SAEN schema computes the vector representation of each object by applying shift, aggregate and extract operations on the vector representations of its parts.

Another contribution of this paper is the introduction of a domain compression algorithm, that we use in our experiments to reduce memory usage and runtime. Domain compression collapses objects in the same stratum of an H-hierarchical decomposition into a compressed one whenever these objects are indistinguishable for the SAEN computation schema. In particular objects made of the same sets of parts are indistinguishable. In order obtain a lossless compression an H-hierarchical decomposition we store counts on symmetries adopting some mathematical results from lifted linear programming (Mladenov et al., 2012) . The domain compression algorithm is also reminiscent of the work of Sperduti & Starita (1997) in which common substructures of recursive neural networks are collapsed in order to reduce the computational cost.

2. SHIFT-AGGREGATE-EXTRACT NEURAL NETWORKS:

We propose a neural network architecture that takes as input an undirected attributed graph G = (V, E, X) where V is the vertex set, E ⊆ V × V is the edge set, and X = {x v ∈ R p } v∈V is a set of p-dimensional vertex attributes. When vertices do not have associated attributes (for example this happens in some of the social network datasets of § 4.1), we can set x v to some vertex invariant such as node centrality or betweenness.

2.1. H-HIERARCHICAL DECOMPOSITIONS:

Most graph kernels decompose graphs into parts by using an R-convolution relation (Haussler, 1999) . We extend this approach by decomposing graphs into a hierarchy of π-parametrized "part of" relations. Formally, an H-hierarchical decomposition is a pair ({S l } L l=0 , {R l,π } L l=1 ) where: • {S l } L l=0 are disjoint sets of objects S l called strata, or levels of the hierarchy. The bottom stratum S 0 contains non-decomposable objects (e.g. individual vertices), while the other strata S l , l = 1, . . . , L contain composite objects, o i ∈ S l , whose parts o j ∈ S l-1 belong to the preceding stratum, S l-1 .

• {R l,π } L l=1 is a set of l, π-parametrized R l,π -convolution relations. A pair (o i , o j ) ∈ S l × S l-1 belongs to R l,π iff "o j is part of o i with membership type π". For notational convenience, the parts of o i are denoted as R -1 l,π (o i ) = {o j |(o j , o i ) ∈ R l,π }.

The membership type π is used to represent the roles of the parts of an object. For example, we could decompose a graph as a multiset of π-neighborhood subgraphs1 in which π is the radius of the neighborhoods (see Figure 1 on the left). Another possible use of the π membership type is to

Ego Graph ⇡ : R O O T ⇡ : ELEM ⇡ : E L E M Graph ⇡ : 0 ⇡ : 0 ⇡ : 0 ⇡ : 0 ⇡ : 1 ⇡ : 1 ⇡ : 1 ⇡ : 1 ⇡ : 1

Ego graph (stratum S 1 ) decomposed into vertices (stratum S 2 ).

⇡ : 0 Root of the ego graph. Other vertices of the ego graph. Ego graphs of radius 0.

Ego graphs of radius 1.

Graph (stratum S 2 ) decomposed into ego graphs of radius 0 and 1 (stratum S 1 ).

Figure 1 : Image of an H-hierarchical decomposition (in particular the EGNN explained in § 4.2).

On the left we decompose a graph into rooted ego graphs of radius 0 and 1, while on the right we decompose an ego graph into the set of its vertices. The directed arrows represent "part of" relations labeled with their membership type π. The membership type π represents the radius π = 0, 1 of the ego graphs (decomposition on the left) and the role (i.e. π = ROOT, ELEM) of a vertex in the ego graph (decomposition on the right) respectively.

distinguish the root from the other vertices in a rooted neighborhood subgraph (see Figure 1 on the right).

An H-hierarchical decomposition is a multilevel generalization of R-convolution relations, and it reduces to an R-convolution relation for L = 1.

2.2. SHIFT AGGREGATE EXTRACT SCHEMA FOR LEARNING REPRESENTATIONS:

We propose Shift Aggregate Extract Network (SAEN) to learn vector representations for all the objects of all the strata {S l } L l=0 in an H-hierarchical decomposition. SAEN unfolds a neural network architecture over an H-hierarchical decomposition by using the Shift Aggregate Extract (SAE) schema.

According to the SAE schema the vector representation of each object in the H-hierarchical decomposition is either computed by applying a neural network on the vertex attributes (for the objects in bottom stratum) or defined in terms of the vector representations of its parts (for the other objects).

More formally, the SAE schema associates a d l -dimensional representation h i ∈ R d l to each object o i ∈ S l of the H-hierarchical decomposition according to the following formula:

h i =                  f 0 (x vi ; Θ 0 ) if o i ∈ S 0 f l π∈Π l oj ∈R -1 l,π (oi) (z π ⊗ h j ) Shif t Aggregate ; Θ l Extract otherwise (1)

where f l (•; Θ l ), l = 0, . . . , L are multilayer neural networks with parameters Θ l .

With respect to the base case (first branch of Eq. 1) we have that each object o i in the bottom stratum S 0 is in one-to-one correspondence with the vertices v i ∈ V of the graph that we are decomposing. Indeed the vector representations h i are computed by evaluating f 0 (•; Θ 0 ) in correspondence of the vertex attributes x vi ∈ X.

The recursion step (second branch of Eq. 1) follows the Shift Aggregate Extract (SAE) schema:

• Shift: each part representation h j ∈ R d l-1 is remapped into a space R |Π l d l-1 | made of |Π l | slots,

where each slot has dimension d l-1 . This transformation shifts part representations h j by using the Kronecker product ⊗ between an indicator vector z π ∈ R |Π l | and the vector representation make sure that vector representations h j of object parts will fall in the same slot if and only if they have the same membership type π. • Aggregate: the shifted representations (z π ⊗ h j ) of the parts o j are then aggregated with a sum.

h j of part o j ∈ S l-1 . The indicator vector z π ∈ R |Π l | defined as z i = 1 if i=π 0 otherwise.

• Extract: the aggregated representation is compressed to a d l -dimensional space by a Θ lparametrized nonlinear map

f l (•, Θ l ) : R |Π l d l-1 | → R d l implemented with a multilayer neural network.

The shift and aggregate steps, that we have seen so far, are identical to those used in kernel design when computing the explicit feature of a kernel k(x, z) derived from a sum π∈Π k π (x, z) of base kernels k π (x, z), π ∈ Π. In principle, it would be indeed possible to turn SAEN into a kernel method by removing the extraction step E from the SAE schema. However, such an approach would increase the dimensionality of the feature space by a multiplicative factor |Π l | for each level l of the Hhierarchical decomposition, thus leading to an exponential number of features. When using SAEN, the feature space growth is prevented by exploiting a distributed representation (via a multilayered neural network) during the E step of the SAE schema. As a result, SAEN can easily cope with Hhierarchical decompositions consisting of multiple strata.

2.3. EXPLOITING SYMMETRIES FOR DOMAIN COMPRESSION:

In this section we propose a technique, called domain compression, which allows to save memory and speedup the SAEN computation. Domain compression exploits symmetries in H-hierarchical decompositions by collapsing equivalent objects in each stratum. The greater the number of collapsed objects the highest the compression ratio.

Two objects a, b in a stratum S l are collapsable a ∼ b if they share the same representation (i.e. h a = h b ) for all the possible values of Θ l . A compressed stratum S comp l is the quotient set S l/∼ of stratum S l w.r.t. the collapsibility relation ∼. We assume that the attributes of the elements in the bottom stratum S 0 are categorical, so that the same vector representation can be shared by multiple elements with non-zero probability.2 While objects in the bottom stratum S 0 are collapsable when their attributes are identical, for all the other strata S l , l = 1, . . . , L, objects are collapsable if they are made by the same sets of parts for all the membership types π.

In Figure 2 we provide a pictorial representation of the domain compression of an H-hierarchical decomposition (EGNN, described in § 4.2). On the left we show the H-hierarchical decomposition of a graph taken from the IMDB-BINARY dataset (see § 4.1) together with its compressed version on the right.

2.3.1. DOMAIN COMPRESSION ALGORITHM:

In order to compress H-hierarchical decompositions we adapt the lifted linear programming technique proposed by Mladenov et al. (2012) to the SAEN architecture. If a matrix M ∈ R n×p has m ≤ n distinct rows it can be decomposed as the product DM comp where M comp is a compressed version of M in which the distinct rows of M appear exactly once. The Boolean decompression matrix, D, encodes the collapsibility relation among the rows of M so that D ij = 1 iff the i th row of M falls in the equivalence class j of ∼. A pseudo-inverse C of D can be computed by dividing the rows of D by their sum (where D is the transpose of D).

Example 1 If we look at matrix M in Eq. 2 we notice that row 1 and 4 share the encoding [0, 0, 0], rows 3 and 5 share the encoding [1, 1, 0] while the encoding [1, 0, 1] appears only once at row 2.

Matrix M comp is the compressed version of M . M =      0 0 0 1 0 1 1 1 0 0 0 0 1 1 0      M comp = 0 0 0 1 0 1 1 1 0 D =      1 0 0 0 1 0 0 0 1 1 0 0 0 0 1      C = 1 /2 0 0 1 /2 0 0 1 0 0 0 0 0 1 /2 0 1 /2 (2)

Matrix M can be expressed as the matrix product between the decompression matrix D and the compressed version of M comp (i.e. M = DM comp ), while the matrix multiplication between the compression matrix C and the M leads to the compressed matrix M comp (i.e.M comp = CM ).

To apply domain compression we rewrite Eq. 1 in matrix form as follows:

EQUATION

where:

• H l ∈ R |S l |×d l is the matrix that represents the d l -dimensional encodings of the objects in S l .

The rows of H l are the vector representations h i in Eq. 1, while the rows of H l-1 are the vector representations h j in Eq. 1;

• X ∈ R |S0|×p is the matrix that represents the p-dimensional encodings of the vertex attributes in V (i.e. the rows of X are the x vi of Eq. 1);

• f l (•; Θ l ) is unchanged w.r.t. Eq. 1 and is applied to its input matrices row-wise;

• R l,π ∈ R |S l |×|S l-1 | ∀π ∈ Π l are the matrix representations of the R l,π -convolution relations of Eq. 1 whose elements are (R l,π ) ij = 1 if (o j , o i ) ∈ R l,π and 0 otherwise.

Domain compression on Eq. 3 is performed by the DOMAIN-COMPRESSION procedure (see Algorithm 3) that takes as input the attribute matrix X and the part-of matrices R l,π and returns their compressed versions X comp and the R comp l,π

respectively. The algorithm starts by invoking (line 1) the procedure COMPUTE-CD on X to obtain the compression and decompression matrices C 0 and D 0 respectively. The compression matrix C 0 is used to compress X (line 2) then we start iterating over the levels l = 0, . . . , L of the H-hierarchical decomposition (line 4) and compress the R l,π matrices. The compression of the R l,π matrices is done by right-multiplying them by the decompression matrix D l-1 of the previous level l -1 (line 5). In this way we collapse the parts of relation R l,π (i.e. the columns of R l,π ) as these were identified in stratum S l-1 as identical objects (i.e. those objects corresponding to the rows of X or R l-1,π collapsed during the previous step). The result is a list

R col comp = [R l,π D l-1 , ∀π = 1, . . . , |Π l |] of column compressed R l,π -matrices.

We proceed collapsing equivalent objects in stratum S l , i.e. those made of identical sets of parts: we find symmetries in R col comp by invoking COMPUTE-CD (line 6) and obtain a new pair C l , D l of compression, and decompression matrices respectively. Finally the compression matrix C l is applied to the column-compressed matrices in R col comp in order to obtain the Π l compressed matrices 

DOMAIN-COMPRESSION(X, R) 1 C 0 , D 0 = COMPUTE-CD(X) 2 X comp = C 0 X / / Compress the X matrix. 3 R comp = {} / / Initialize an empty container for compressed matrices. 4 for l = 1 to L 5 R col comp = [R l,π D l-1 , ∀π = 1, . . . , |Π l |] / / column compression 6 C l , D l = COMPUTE-CD(R col comp ) 7 for π = 1 to |Π l | 8 R comp l,π = C l R col comp π // row compression 9 return X comp , R comp

3. RELATED WORKS:

When learning with graph inputs two fundamental design aspects that must be taken into account are: the choice of the pattern generator and the choice of the matching operator. The former decomposes the graph input in substructures while the latter allows to compare the substructures.

Among the patterns considered from the graph kernel literature we have paths, shortest paths, walks (Kashima et al., 2003) , subtrees (Ramon & Gärtner, 2003; Shervashidze et al., 2011) and neighborhood subgraphs (Costa & De Grave, 2010) . The similarity between graphs G and G is computed by counting the number of matches between their common the substructures (i.e. a kernel on the sets of the substructures). The match between two substructures can be defined by using graph isomorphism or some other weaker graph invariant.

When the number of substructures to enumerate is infinite or exponential with the size of the graph (perhaps this is the case for random walks and shortest paths respectively) the kernel between the two graphs is computed without generating an explicit feature map. Learning with an implicit feature map is not scalable as it has a space complexity quadratic in the number of training examples (because we need to store in memory the gram matrix).

Other graph kernels such as the Weisfeiler-Lehman Subtree Kernel (WLST) (Shervashidze et al., 2011) and the Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) (Costa & De Grave, 2010) deliberately choose a pattern generator that scales polynomially and produces an explicit feature map. However the vector representations produced by WLST and NSPDK are handcrafted and not learned.

A recent work by Yanardag & Vishwanathan (2015) proposes to uses pattern generators such as graphlets, shortest paths and WLST subtrees to transform input graphs into documents. The generated substructures are then treated as words and embedded in the Euclidean space with a CBOW or a Skip-gram model. The deep upgrade of existing graph kernels is performed by reweighing the counts of the substructures by the square root of their word-vector self similarity.

Another recent work by Niepert et al. (2016) upgrades the convolutional neural networks CNNs for images to graphs. While the receptive field of a CNN is usually a square window (Niepert et al., 2016) employ neighborhood subgraphs as receptive fields. As nodes in graphs do not have a specific temporal or spatial order, (Niepert et al., 2016) employ vertex invariants to impose an order on the nodes of the subgraphs/receptive fields.

4. EXPERIMENTAL EVALUATION:

We answer to the following experimental questions: Q1 How does SAEN compare to the state of the art? Q2 Can SAEN exploit symmetries in social networks to reduce the memory usage and the runtime?

4.1. DATASETS:

In order to answer the experimental questions we tested our method on six publicly available datasets first proposed by Yanardag & Vishwanathan (2015) .

• COLLAB is a dataset where each graph represent the ego-network of a researcher, and the task is to determine the field of study of the researcher between High Energy Physics, Condensed Matter Physics and Astro Physics. 

4.2. EXPERIMENTS:

In our experiments we chose an H-hierarchical decomposition called Ego Graph Neural Network (EGNN), that mimics the graph kernel NSPDK with the distance parameter set to 0.

Before applying EGNN we turn unattributed graphs (V, E) into attributed graphs (V, E, X) by annotating their vertices v ∈ V with attributes x v ∈ X. We label vertices v of G with their degree and encode this information into the attributes x v by employing the 1-hot encoding.

EGNN decomposes attributed graphs G = (V, E, X) into a 3 level H-hierarchical decomposition with the following strata (see Figure 1 for a pictorial representation of EGNN):

• stratum S 0 contains objects o v that are in one-to-one correspondence with the vertices v ∈ V .

• stratum S 1 contains v root -rooted r-neighborhood subgraphs (i.e. ego graphs) e = (v root , V e , E e ) of radius r = 0, 1, . . . , R and has part-of alphabet Π 1 = {ROOT, ELEM}. Objects o v ∈ S 0 are "ELEM-part-of" ego graph e if v ∈ V e \ {v root }, while the are "ROOT-part-of" ego graph e if v = v root . • stratum S 2 contains the graph G that we want to classify and has part-of alphabet Π 2 = {0, 1} which correspond to the radius of the ego graphs e ∈ S 1 of which G is made of.

E1:

We experimented with SAEN applying the EGNN H-decomposition on all the datasets. For each dataset, we manually chose the parameters of SAEN, i.e. the number of hidden layers for each stratum, the size of each layer and the maximum radius R. We used the Leaky ReLU (Maas et al.) activation function on all the units. We report the chosen parameters in Table A1 of the appendix. In all our experiments we trained the neural networks by using the Adam algorithm to minimize a cross entropy loss.

The classification accuracy of SAEN was measured with 10-times 10-fold cross-validation. We manually chose the number of layers and units for each level of the part-of decomposition; the number of epochs was chosen manually for each dataset and we kept the same value for all the 100 runs of the 10-times 10-fold cross-validation. The mean accuracies and their standard deviations obtained by our method are reported in Table 4 , where we compare these results with those obtained by Yanardag & Vishwanathan (2015) and by Niepert et al. (2016) .

Although our method was conceived for social network data, it can also handle other types of graphs.

For the sake of completeness in Table 5 we report the mean accuracies obtained with SAEN on the molecule and protein datasets studied in previous works (e.g. Niepert et al. (2016) ). 1 we show the file sizes of the preprocessed datasets before and after the compression together with the data compression ratio. 3 We also estimate the benefit of the relational compression from a computational time point of view and report the measurement of the runtime for 1 run with and without compression together with the speedup factor.

For the purpose of this experiment, all tests were run on a computer with two 8-cores Intel Xeon E5-2665 processors and 94 GB RAM. Uncompressed datasets which exhausted our server's memory during the test are marked as "OOM" (out of memory) in the table, while those who exceeded the time limit of 100 times the time needed for the uncompressed version are marked as "TO" (timeout).

4.3. DISCUSSION:

A1 As shown in Table 4 , EGNN performs consistently better than the other two methods on all the social network datasets. This confirms that the chosen H-hierarchical decomposition is effective on this kind of problems. Also the results for molecule and protein datasets (see Table 5 ) are in line with the current state of the art.

A2:

The compression algorithm has proven to be effective in improving the computational cost of our method. Most of the datasets improved their runtimes by a factor of at least 4 while maintaining the same expressive power. Moreover, experiments on REDDIT-MULTI5K and REDDIT-MULTI12K have only been possible thanks to the size reduction operated by the algorithm as the script exhausted the memory while executing the training step on the uncompressed files.

:

The r-neighborhood subgraph (or ego graph) of a vertex v in a graph G is the induced subgraph of G consisting of all vertices whose shortest-path distance from v is at most r.

Vectors of real valued attributes could be discretized using clustering techniques. However, we leave discretization in SAEN to future works.

The size of the uncompressed files are shown for the sole purpose of computing the data compression ratio. Indeed the last version of our code compresses the files on the fly.

Figures and Tables:

DOMAIN-COMPRESSION    of stratum S l (line 8). Algorithm 3 allows us to compute the domain compressed version of Eq. 3 which can be obtained by replacing:X with X comp = C 0 X, R l,π with R comp l,π = C l R l,π D l-1 and H l with H comp l. Willing to recover the original encodings H l we just need to employ the decompression matrix D l on the compressed encodingsH comp l , indeed H l = D l H comp l .As we can see by substituting S l with S comp l , the more are the symmetries (i.e. when |S comp l | |S l |) the greater the domain compression will be.

Figure 4: Comparison of accuracy results.

Figure 2: Pictorial representation of the H-hierarchical decomposition of a graph taken from the IMDB-BINARY dataset (see § 4.1) together with its compressed version.

Table content: <table><tr><td>.....original</td><td>.....compressed</td></tr><tr><td>H-decomposition</td><td>H-decomposition</td></tr><tr><td>whole graph</td><td/></tr><tr><td>....domain</td><td/></tr><tr><td>compression</td><td/></tr><tr><td>ego graph</td><td/></tr><tr><td>patterns</td><td/></tr><tr><td>vertices</td><td/></tr><tr><td>original graph</td><td>compressed graph</td></tr></table>

• IMDB-BINARY, IMDB-MULTI are datasets derived from IMDB where in each graph the vertices represent actors/actresses and the edges connect people which have performed in the same movie. Collaboration graphs are generated from movies belonging to genres Action and Romance for IMDB-BINARYand Comedy, Romance and Sci-Fi for IMDB-MULTI, and for each actor/actress in those genres an ego-graph is extracted. The task is to identify the genre from which the ego-graph has been generated. • REDDIT-BINARY, REDDIT-MULTI5K, REDDIT-MULTI12K are datasets where each graph is derived from a discussion thread from Reddit. In those datasets each vertex represent a distinct user and two users are connected by an edge if one of them has responded to a post of the other in that discussion. The task in REDDIT-BINARYis to discriminate between threads originating from a discussion-based subreddit (TrollXChromosomes, atheism) or from a question/answers-based subreddit (IAmA, AskReddit). The task in REDDIT-MULTI5Kand REDDIT-MULTI12Kis a multiclass classification problem where each graph is labeled with the subreddit where it has originated (worldnews, videos, AdviceAnimals, aww, mildlyinteresting for REDDIT-MULTI5Kand AskReddit, AdviceAnimals, atheism, aww, IAmA, mildlyinteresting, Showerthoughts, videos, todayilearned, worldnews, TrollXChromosomes for REDDIT-MULTI12K).

Table content: <table/>

Comparison of sizes and runtimes of the datasets before and after the compression.

Table content: <table><tr><td>DATASET COLLAB IMDB-BINARY IMDB-MULTI REDDIT-BINARY REDDIT-MULTI5K REDDIT-MULTI12K</td><td>SIZE (MB) ORIGINAL COMP. 1190 448 68 34 74 40 326 56 952 162 1788 347</td><td>RATIO 0.38 0.50 0.54 0.17 0.17 0.19</td><td>ORIGINAL 43' 18" 3' 9" 7' 41" TO OOM OOM</td><td>RUNTIME COMP. 8' 20" 0' 30" 1' 54" 2' 35" 9' 51" 29' 55"</td><td>SPEEDUP 5.2 6.3 4.0 ≥ 100.0 --</td></tr><tr><td>E2 In Table</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2017):
The paper contributes to recent work investigating how neural networks can be used on graph-structured data. As far as I can tell, the proposed approach is the following: 1. Construct a hierarchical set of *objects* within the graph. Each object consists of multiple *parts* from the set of objects in the level below. There are potentially different ways a part can be part of an object (the different pi labels), which I would maybe call *membership types*. In the experiments, the objects at the bottom level are vertices. At the next level they are radius 0 (just a vertex?) and radius 1 neighborhoods around each vertex, and the membership types here are either *root*, or *element* (depending on whether a vertex is the center of the neighborhood or a neighbor). At the top level there is one object consisting of all of these neighborhoods, with membership types of *radius 0 neighborhood* (isn*t this still just a vertex?) or *radius 1 neighborhood*. 2. Every object has a representation. Each vertex*s representation is a one-hot encoding of its degree. To construct an object*s representation at the next level, the following scheme is employed: a. For each object, sum the representation of all of its parts having the same membership type. b. Concatenate the sums obtained from different membership types. c. Pass this vector through a multi-layer neural net. I*ve provided this summary mainly because the description in the paper itself is somewhat hard to follow, and relevant details are scattered throughout the text, so I*d like to verify that my understanding is correct. Some additional questions I have that weren*t clear from the text: how many layers and hidden units were used? What are the dimensionalities of the representations used at each layer? How is final classification performed? What is the motivation for the chosen *ego-graph* representation? The proposed approach is interesting and novel, the compression technique appears effective, and the results seem compelling. However, the clarity and structure of the writing is quite poor. It took me a while to figure out what was going on---the initial description is provided without any illustrative examples, and it required jumping around the paper to figure for example how the pi labels are actually used. Important details around network architecture aren*t provided, and very little in the way of motivation is given for many of the choices made. Were other choices of decomposition/object-part structures investigated, given the generality of the shift-aggregate-extract formulation? What motivated the choice of *ego-graphs*? Why one-hot degrees for the initial attributes? Overall, I think the paper contains a useful contribution on a technical level, but the presentation needs to be significantly cleaned up before I can recommend acceptance.