Title: SPECTRAL CONVOLUTIONAL NETWORKS ON HIERARCHICAL MULTIGRAPHS

Abstract: Spectral Graph Convolutional Networks (GCNs) are a generalization of convolutional networks to learning on graph-structured data. Applications of spectral GCNs have been successful, but limited to a few problems where the graph is fixed, such as shape correspondence and node classification. In this work, we address this limitation by revisiting a particular family of spectral graph networks, Chebyshev GCNs, showing its efficacy in solving graph classification tasks with a variable graph structure and size. Current GCNs also restrict graphs to have at most one edge between any pair of nodes. To this end, we propose a novel multigraph network that learns from multi-relational graphs. We explicitly model different types of edges: annotated edges, learned edges with abstract meaning, and hierarchical edges. We also experiment with different ways to fuse the representations extracted from different edge types. We achieve state-of-the-art results on a variety of chemical, social, and vision graph classification benchmarks.

1. INTRODUCTION:

Convolutional Neural Networks (CNNs) have seen wide success in domains where data is restricted to a Euclidean space. These methods exploit properties such as stationarity of the data distributions, locality and a well-defined notation of translation, but cannot model data that is non-Euclidean in nature. Such structure is naturally present in many domains, such as chemistry, social networks, transportation systems, and 3D geometry, and can be expressed by graphs (Bronstein et al., 2017; Hamilton et al., 2017b) . By defining an operation on graphs analogous to convolution, Graph Convolutional Networks (GCNs) have extended CNNs to graph-based data. The earliest methods performed convolution in the spectral domain (Bruna et al., 2013) , but subsequent work has proposed generalizations of convolution in the spatial domain. There have been multiple successful applications of GCNs to node classification (Velickovic et al., 2018) and link prediction (Schlichtkrull et al., 2018) , whereas we target graph classification similarly to Simonovsky & Komodakis (2017) .

Our focus is on multigraphs, a graph that is permitted to have multiple edges. Multigraphs are important in many domains, such as social networks. Some data, such as images, have inherent hierarchical structure, which we also represent as multigraphs, enabling us to exploit the hierarchy. The challenge of generalizing convolution to multigraphs is to have anisotropic convolution kernels (such as edge detectors). Anisotropic models, such as MoNet (Monti et al., 2017) and SplineCNN (Fey et al., 2018) , rely on coordinate structure, work well for vision tasks, but are suboptimal for nonvisual graph problems. Other general models exist (Battaglia et al., 2018) , but making them efficient for a variety of tasks is impeded by the "no free lunch theorem" (Goodfellow et al., 2016, § 5.2.1) .

Compared to non-spectral GCNs, spectral models have filters with more global support, which is important for capturing complex relationships. We rely on Chebyshev GCNs (ChebNet) (Defferrard et al., 2016) . Even though it was originally derived from spectral methods Bruna et al. (2013) , it does not suffer from their main shortcoming -sensitivity of learned filters to graph size and structure.

Contributions::

We propose a scalable spectral GCN that learns from multigraphs by capturing multi-relational graph paths as well as multiplicative and additive interactions to reduce model complexity and learn richer representations. We also learn new abstract relationships between graph nodes, beyond the ones annotated in the datasets. To our knowledge, we are the first to demonstrate that spectral methods can efficiently solve problems with variable graph size and structure, where this kind of method is generally believed not to perform well.

2. MULTIGRAPH CONVOLUTION:

While we provide the background to understand our model, a review of spectral graph methods is beyond the scope of this paper. Section 6.1 of the Appendix reviews spectral graph convolution.

2.1. APPROXIMATE SPECTRAL GRAPH CONVOLUTION:

A graph G = (V, E) consists of N nodes, V, and edges, E. Nodes v i ∈ V usually represent specific semantic concepts such as atoms in a chemical compound or users in a social network. Nodes can also denote abstract blocks of information with common properties, such as superpixels in images. Edges e ij ∈ E define the relationships and scope of which node effects propagate.

In spectral graph convolution (Bruna et al., 2013) , the filter g ∈ R N is defined on an entire input space. Although it makes filters global, which helps to capture complex relationships, it is also desirable to have local support since the data often have local structure.

To address this issue, we can model this filter as a function of eigenvalues Λ (which is assumed to be constant) of the normalized symmetric graph Laplacian L: g = g(Λ). We can further approximate it as a sum of K terms using the Chebyshev expansion, where each term

T k (Λ) = 2ΛT k-1 (Λ) - T k-2 (Λ) contains powers Λ k .

Finally, we apply the property of eigendecomposition to eliminate computationally inconvenient eigenvectors U ∈ R N ×N from spectral graph convolution:

L k = (U ΛU T ) k = U Λ k U T .

(1)

In general, for the input X ∈ R N ×Xin with N nodes and X in -dimensional features in each node, the approximate convolution is defined as:

EQUATION

where X ∈ R N ×XinK are features projected onto the Chebyshev basis T k ( L) and concatenated for all orders k ∈ [0, K -1] and Θ ∈ R XinK×Xout are trainable weights, where L = L -I.

This approximation scheme was proposed in Defferrard et al. (2016) , and Eq. 2 defines the convolutional layer in the Chebyshev GCN (ChebNet), which is the basis for our method. Convolution is an essential computational block in graph networks, since it permits the gradual aggregation of information from neighboring nodes. By stacking the operator in Eq. 2, we capture increasingly larger neighborhoods and learn complex relationships in graph-structured data.

2.2. GRAPHS WITH VARIABLE STRUCTURE AND SIZE:

The approximate spectral graph convolution (Eq. 2) enforces spatial locality of the filters by controlling the order of the Chebyshev polynomial K. Importantly, it reduces the computational complexity of spectral convolution from O(N 2 ) to O(K|E|). In this work, we observe an important byproduct of this scheme: that learned filters become less sensitive to changes in graph structure and size due to excluding the eigenvectors U from spectral convolution, so that learned filters are not tied to U . The only assumption that still makes a trainable filter ĝ sensitive to graph structure is that we model it as a function of eigenvalues ĝ(Λ). However, the distribution of eigenvalues of the normalized Laplacian is concentrated in a limited range, making it a weaker dependency on graphs than the spectral convolution via eigenvectors, so that learned filters generalize well to new graphs. Moreover, since we use powers of L in performing convolution (Eq. 2), the distribution of eigenvalues Λ further contracts due to exponentiation of the middle term on the RHS of Eq. 1. We believe that this effect accounts for the robustness of learned filters to changes in graph size or structure (Figure 1 ).

2.3. GRAPHS WITH MULTIPLE RELATION TYPES:

In the approximate spectral graph convolution (Eq. 2), the graph Laplacian L encodes a single relation type between nodes. Yet, a graph may describe many types of distinct relations. In this section, we address this limitation by extending Eq. 2 to a multigraph, i.e. a graph with multiple (R ≥ 1) edges (relations) between the same nodes encoded as a set of graph Laplacians { L(r) } R 1 . Extensions to a multigraph can also be applied to early spectral models (Bruna et al., 2013) but, since ChebNet was shown to be superior in downstream tasks, we choose to focus on the latter model.

Two dimensional Chebyshev polynomial. The Chebyshev polynomial used in Eq. 2 (see Section 6.1 in Appendix for detail) can be extended for two variables (relations in our case) similarly to bilinear models, e.g., as in Omar et al. (2010) :

EQUATION

and, analogously, for more variables. For R = 2, the convolution is then defined as:

EQUATION

where Xi,j = T i ( L(r1) )T j ( L(r2) )X. In this case, we allow the model to leverage graph paths consisting of multiple relation types (Figure 2 ). This flexibility, however, comes at a great computational cost, which is prohibitive for a large number of relations R or large order K due to exponential growth of the number of parameters: Θ ∈ X in K R X out . Moreover, as we demonstrate in our experiments, such multi-relational paths do not necessary lead to better performance.

Multiplicative and additive fusion. Motivated by multimodal fusion considered in the Visual Question Answering literature (e.g. Kim et al., 2016) , we propose the multiplicative operator:

EQUATION

In this case, node features interact in a multiplicative way. The advantage of this method is that the model can learn separate transformations f r for each relation type r and has fewer trainable parameters preventing overfitting, which is especially important for large K and R. The elementwise multiplication • in Eq. 5 can be replaced with summation to perform additive fusion.

Concatenating edge features.:

A more straightforward approach is to concatenate features X(r) for all R relation types and learn a single matrix of weights

Θ ∈ R XinKR×Xout : Y = [ X(0) , X(1) , ..., X(R-1) ]Θ. (6) v 1 v 4 v 2 v 5 Edge type r 2 Edge type r 1 v 3 2d Cheb v 1 v 4 v 2 v 5 v 3 Other methods v 1 v 4 v 2 v 5 Edge type r 2 Edge type r 1 v 3 2d Cheb v 1 v 4 v 2 v 5 v 3 Other methods v 1 v 4 v 2 v 5 Edge type r 2 Edge type r 1 v 3 2d Cheb v 1 v 4 v 2 v 5 v 3

Other methods

(a) (b):

Figure 2 : Comparison of (a) the fusion method based on a two-dimensional Chebyshev polynomial (Eq. 3, 4) to (b) other proposed methods in case of a 2-hop filter (a filter averaging features of nodes located two edges away from the filter center -v 1 in this case). Note that (a) can leverage multirelational paths and the filter centered at node v 1 can access features of the node v 3 , which is not possible for other methods (b). In this work, edge type r 1 can denote annotated or spatial relations, while r 2 denotes hierarchical or learned ones. We also allow for three and more relation types.

This method, however, does not scale well for large R, since the dimensionality of Θ grows linearly with R. Note that even though multi-relational paths are not explicit in Eq. 5 and 6, for a multilayer network, relation types will still communicate through node features. In Figure 2 , node v 2 will contain features of node v 3 after the first convolutional layer, so that in the second layer the filter centered at node v 1 will have access to features of node v 3 by accessing features of node v 2 . Compared to the 2d polynomial convolution defined by Eq. 4, the concatenation-based, multiplicative and additive approaches require more layers to have a larger multi-relational receptive field.

3. MULTIGRAPH CONVOLUTIONAL NETWORKS:

A popular assumption of current GCNs is that there is at most one edge between any pair of nodes in a graph. This restriction is usually implied by datasets with such structure, so that in many datasets, graphs are annotated with the single most important relation type, for example, whether two atoms in a molecule are bonded (Duvenaud et al., 2015) . Meanwhile, data is often complex and nodes tend to have multiple relationships of different semantic, physical, or abstract meanings. Therefore, we argue that there could be other relationships captured by relaxing this restriction and allowing for multiple kinds of edges, beyond those annotated in the data.

3.1. LEARNING EDGES:

Prior work (e.g. Schlichtkrull et al., 2018; Bordes et al., 2013) , proposed methods to learn from multiple edges, but similarly to the methods using a single edge type (Kipf & Welling, 2016), they leveraged only predefined (annotated) edges in the data. We devise a more flexible model, which, in addition to learning from an arbitrary number of predefined relations between nodes (see Section 2.3), learns abstract edges jointly with a GCN. We propose to learn a new edge e (r) ij between any pair of nodes v i and v j with features X i and X j using a trainable similarity function:

EQUATION

where the softmax is used to enforce sparse connections. This idea is similar to Henaff et al. (2015) , built on the early spectral convolution model (Bruna et al., 2013) , which learned an adjacency matrix, but targeted classification tasks for non graph-structured data (e.g. document classification, with each document represented as a feature vector). Moreover, we learn this matrix jointly with a more recent graph classification model (Defferrard et al., 2016) and, additionally, efficiently fuse predefined and learned relations. Eq. 7 is also similar to that of Velickovic et al. (2018) , which used this functional form to predict an attention coefficient α ij for some existing edge e ij . The attention model can only strengthen or weaken some existing relations, but cannot form new relations. We present a more general model that makes it possible to connect previously disconnected nodes and form new abstract relations. To enforce a symmetry of predicted edges we compute an average: (e 2018), who considered small-scale image classification problems such as MNIST (LeCun et al., 1998) . In this work, we present a model that scales to more complex and larger image datasets, such as PASCAL VOC 2012 (Everingham et al., 2010) . We follow Monti et al. (2017) and compute SLIC (Achanta et al., 2012) superpixels for each image and build a graph, in which each node v i corresponds to a superpixel and edges e ij are computed based on the Euclidean distance between the coordinates p i and p j of their centers of masses:

EQUATION

Next, we introduce a novel hierarchical graph model (Figure 3 ). We compute superpixels at several different scales and create children-parent relations based on intersection over union (IoU) between superpixels v i and v j at different scales encoded as an adjacency matrix A (rhier) : where A

EQUATION

(rhier) ij = 0 for superpixels at the same scale. Spatial relations are computed as in flat models using Eq. 8, treating superpixels at different scales as a joint set of superpixels.

3.3. LAYER POOLING VERSUS GLOBAL POOLING:

Inspired by convolutional networks, previous works (Bruna et al., 2013; Defferrard et al., 2016; Monti et al., 2017; Simonovsky & Komodakis, 2017; Fey et al., 2018) built an analogy of pooling layers in graphs, for example, using the Graclus clustering algorithm (Dhillon et al., 2007) . In CNNs, pooling is an effective way to reduce memory and computation, particularly for large inputs. It also provides additional robustness to local deformations and leads to faster growth of receptive fields. However, we can build a convolutional network without any pooling layers with similar performance in a downstream task (Springenberg et al., 2014) -it just will be relatively slow, since pooling is extremely cheap on regular grids, such as images. In graph classification tasks, the input dimensionality, which corresponds to the number of nodes N = |V|, is often very small (∼ 10 2 ) and the benefits of pooling are less clear. Graph pooling, such as in Dhillon et al. (2007) , is also computationally intensive since we need to run the clustering algorithm for each training example independently, which limits the scale of problems we can address. Aiming to simplify the model while maintaining classification accuracy, we exclude pooling layers between conv. layers and perform global maximum pooling (GMP) over nodes following the last conv. layer. This fixes the size of the penultimate feature vector regardless of the number of nodes (Figure 4 ).

4. EXPERIMENTS:

We evaluate our model on chemical, social, and image-based graph classification datasets. For each dataset, there is a set of graphs with an arbitrary number of nodes N = |V| and undirected edges |E| of a single type (R = 1) and each graph G has a single, categorical label that is to be predicted. Dataset statistics are presented in Table 3 of the Appendix.

4.1. DATASET DETAILS:

Chemical compounds. We consider five chemical compound datasets frequently used in previous work: NCI1 and NCI109 (Wale et al., 2008) , MUTAG (Debnath et al., 1991) , ENZYMES (Schomburg et al., 2004) , and PROTEINS (Borgwardt et al., 2005) . Every graph represents some chemical compound labeled according to its functional properties.

G 1 =(V 1 , E ( r ) ) G=( V , E (r ) ) Input image G 1 =(V 1 , E ( r ) ) G n =(V n , E ( r ) )

Graph propagation layers:

Global pooling over nodes Superpixels at different scales Classification with FC layers

1× X out 1×N classes G l =(V l , E (r ) )

Hierarchical Multigraph

G 1 =( V 1 , E ( r ) ) G l =(V l , E ( r ) )

Learned edges ) and returns a graph with the same nodes and edges. Node features become increasingly global after each subsequent layer as the receptive field increases, while edges are propagated without changes. As a result, after several graph convolutional layers, each node in the graph contains information about its neighbors and the entire graph. By pooling over nodes we summarize the information collected by each node. Fully-connected layers follow global pooling to perform classification. For chemical/social datasets we use a similar pipeline, but the input graph G is provided by the dataset rather than built from images and does not have hierarchical edges.

v i ∈ℝ X out v i ∈ℝ X in

Social networks. We experiment with three social network datasets. COLLAB (Leskovec et al., 2007; Shrivastava & Li, 2014 ) is a scientific collaboration dataset of researchers publishing in different subfields of physics. IMDB-B (Yanardag & Vishwanathan, 2015) is a movie collaboration dataset of actors/actresses appearing in different genres of movies. IMDB-M is similar to IMDB-B, but has more graphs and more genres. Each graph in the social datasets corresponds to an egonetwork of a researcher or actor/actress and the task is to predict the subfield of physics for COL-LAB or a genre of movies for IMDB. Graph nodes are featureless, i.e. each example (ego-network) in the dataset is defined only by an adjacency matrix A. To add features to some i th node, we use the square root of node degree √ D i , which was shown to be a strong feature in Simonovsky & Komodakis (2017) , despite its simplicity.

The chemical and social datasets vary in the number of graphs (188 -5000) and class labels (2 -6) and, thereby, represent a comprehensive benchmark for our method. We follow the standard approach to evaluation (Shervashidze et al., 2011; Yanardag & Vishwanathan, 2015) and perform 10-fold cross-validation on these datasets reporting average classification accuracies.

Images.:

To demonstrate the scalability of our model and its ability to leverage hierarchical edges, we experiment with three image datasets. MNIST (LeCun et al., 1998) consists of 70k grayscale 28×28 px images of handwritten digits. CIFAR-10 (Krizhevsky, 2009) has 60k colored 32×32 px images of 10 categories of animals and vehicles. PASCAL Visual Object Classes 2012 (Everingham et al., 2010) is a more challenging dataset with realistic high resolution images (up to 500 × 500 px) of 20 object categories (people, animals, vehicles, indoor objects). We use standard classification splits, training our model on 5,717 images and reporting results on 5,823 validation images. We note that CIFAR-10 and PASCAL have not been previously considered for graph-based image classification, and in this work we scale our method to these datasets. In fact, during experimentation we found some other graph convolutional methods unable to scale (see Section 4.3).

4.2. ARCHITECTURAL DETAILS AND EXPERIMENTAL SETUP:

In all experiments, we train a ChebNet with three graph convolutional layers followed by global max pooling (GMP) and 1-2 fully-connected layers (Figure 4 ). Batch normalization (BN) and the ReLU activation are added after each layer, whereas dropout is added only before the fully-connected layers. Projections f r ( X(r) ) in Eq. 5 are modeled by a single layer neural network with C = 128 hidden units and the tanh activation. The edge prediction function f edge (see Eq. 7, Section 3.1) is a two layer neural network with 128 hidden units, which acts on concatenated node features. Detailed network architectures are presented in Table 3 of the Appendix.

We train all models using the Adam optimizer (Kingma & Ba, 2014) with learning rate of 0.001, weight decay of 0.0001, and batch size of 32. For chemical and social datasets, the learning rate is decayed after 25, 35, and 45 epochs and the models are trained for 50 epochs as in Simonovsky & Komodakis (2017) . For visual datasets, the learning rate is decayed after 17 epochs and the models are trained for a total of 25 epochs, similar to Monti et al. (2017) .

Table 1 : Chemical (left five columns) and social (right three columns) graph classification results (accuracy in %). Multigraph ChebNet obtains better results by leveraging two types of edges: annotated and learned, whereas all other models use only annotated edges. *We implemented MoNet, GCN and ChebNet. To make a fair comparison to Multigraph ChebNet, we use the same network architectures, batch-normalization, global max pooling and node degree features (for the social datasets). For MoNet, coordinates are defined using node degrees as in Monti et al. (2017) . The top result across all methods for each dataset is underlined and bolded, second from the top is bolded. For chemical and social datasets, we run cross-validation for different fusion methods (Section 2.3) and Chebyshev orders K in range from 2 to 6 (Section 2.1), while for image datasets, we train the models for K = 7 for superpixels in case of MNIST and CIFAR-10 and for K = 15, 20, 25 (respectively for each convolutional layer) for full grid MNIST.

Graph formation for images. For MNIST, we compute a hierarchy of 75, 21, and 7 SLIC superpixels and use mean superpixel intensity as node features, X ∈ R N ×1 . For CIFAR-10, we add two more levels of 300 and 150 superpixels and add coordinates features, X ∈ R N ×5 , because images are more complex. For PASCAL, due to its even more challenging images, we further add one more level of 1,000 superpixels and add features from the last convolutional layer of VGG-16 (Simonyan & Zisserman, 2014) pre-trained on ImageNet (Russakovsky et al., 2015) . We feed images of original resolution to VGG-16 and add a bilinear upsampling layer on top of the last convolutional layer to obtain feature maps of the same spatial size as the input images. We then use superpixel masks to extract features for each superpixel and average features inside each mask, so that we have a fixed 512 dimensional vector for each superpixel. These are concatenated with the superpixel coordinates and fed to the graph convolutional model, i.e. X ∈ R N ×515 . VGG-16 features are very descriptive and local features already contain global image features, which are usually captured with higher orders of K (more global filters) in our model, so we found K = 2 to be optimal.

4.3. RESULTS:

Chemical and social graph classification: on five chemical compounds datasets, previous works typically show strong performance on one or two datasets (Table 1 ). In contrast, the Multigraph ChebNet, leveraging two relation types (annotated and learned, see Section 3.1), shows high accuracy across all datasets. On two chemical datasets, ENZYMES and PROTEINS, we outperform all previous methods. We also obtain competitive accuracy on NCI1 outperforming all but one prior work (Shervashidze et al., 2011) . Importantly, the Multigraph ChebNet with two edge types, i.e. predefined dataset annotations and the learned edges (Section 3.1) consistently outperforms the baseline ChebNet with a single edge, which shows efficacy of our approach and demonstrates the complementary nature of predefined and learned edges. Lower results on NCI1 and NCI109 can be explained by the fact that the node features in the graphs of these datasets are imbalanced with some features appearing only a few times in the dataset. This is undesirable for our method, which learns new edges based on features and the model can predict random values for unseen features.

On MUTAG we surpass all but one method Niepert et al. (2016) . But in this case the dataset is tiny, consisting of 188 graphs and the margin from the top method is not statistically significant. On the three social datasets, COLLAB, IMDB-B and IMDB-M, we win by a large margin compared to previous works (Table 1 ). This high performance can be partially explained by using degree features, but we still observe a further boost by using learned edges in a Multigraph ChebNet. 

Fusion method # of parameters:

Single edge* (Eq. 2) XinKXout Concat (Eq. 6) XinKRXout 2d Cheb (Eq. 4)

XinK R Xout Multiply (Eq. 5)

C(XinKR + Xout) Sum (Eq. 5)

C(XinKR + Xout) M-shared (Eq. 5)

C(XinK + Xout) S-shared (Eq. 5)

C(XinK + Xout) We observe that some methods perform well for lower order K, such as 2d Chebyshev convolution winning in 21/80 cases for K = 2, while others perform better for higher K, such as Multiply-shared. Multiply generally performs well across different K. All fusion methods, except for Sum-shared, outperform the Single-edge baseline. We also show the number of parameters in Θ for the Chebyshev convolution layer depending on the number of input features X in , number of output features X out , number of relation types R, order K and some constant C (number of hidden units in a projection layer f r in Eq. 5). *Single-edge denotes using only annotated edges. All other methods additionally use the second edge, learned based on node features.

Evaluation of edge fusion methods. For the chemical and social datasets, we train a model using each of the edge fusion methods proposed in Section 2.3 and report the summary of results in Figure 5 . We count the number of times each method outperforms the others treating all 10 folds independently. As expected, graph convolution based on the two-dimensional Chebyshev polynomial is better for lower orders of K, since it exploits multi-relational graph paths, effectively increasing the receptive field of filters. However, for larger K, the model complexity becomes too high due to quadratic growth of the number of parameters and performance degrades. Sharing weights for multiplicative or additive fusion generally drops performance with a few exceptions for social datasets in the multiplicative case. This implies that predefined and learned edges are of a different nature. It would be interesting to validate these fusion methods on a larger number of relation types.

Image classification. For image classification tasks, we observe several interesting results (Table 2). First, by adding batch-normalization and global max pooling, and increasing the learning rate to 0.001 compared to 0.0001 in Monti et al. (2017) , accuracies surge both for MoNet (Monti et al., 2017) and ChebNet (Defferrard et al., 2016) (to 98.59% and 97.12% respectively from the reported 91.11% and 75.62%) reducing the gap between the two methods (from 15.49% to 1.47%). It supports our claim that spectral methods, in particular ChebNet, can efficiently perform graph classification for arbitrary sized graphs. Here, the arbitrariness is due to the number of superpixels being the upper bound in all cases, since SLIC often returns fewer superpixels.

Next, we observe that the hierarchical connections modeled by Hierarchical ChebNet are important for MNIST and CIFAR-10, substantially improving accuracy. Learned connections implemented by Multigraph ChebNet also provide a boost in performance, but in a less consistent way. For MNIST, they contribute almost 1% in the case of full grid, while only ∼0.3% in the case of superpixels.

Combining hierarchical connections and multiple edge types (Hierarchical Multigraph ChebNet), we observe a further gain in performance, however, it is less pronounced and less consistent.

For PASCAL VOC, we obtain the best performance using Multigraph ChebNet with R = 2 relation types. Interestingly, our results are better in this case compared to the baseline ConvNet. The baseline results were obtained by stacking and training three convolutional layers (with the same number of filters as in ChebNet) on top of the last convolutional layer in VGG-16 to make a more fair comparison to our graph network, so that both the ConvNet and ChebNet take the same input. The ChebNet, however, uses coordinates as additional features, which can explain the phenomenon.

5. RELATED WORK AND DISCUSSION:

Our method relies on a fast approximate spectral graph convolution known as ChebNet (Defferrard et al., 2016) ), which was designed for graph classification. A simplified and faster version of this 2016), which is practically equivalent to the ChebNet with order K = 1, has shown impressive node classification performance on citation and knowledge graph datasets in the transductive learning setting. In all our experiments, we noticed that using more global filters (with larger K) is important (Tables 1, 2 ). Other recent works Hamilton et al. (2017a) ; Velickovic et al. (2018) also focus on node classification and, therefore, are not empirically compared to in this work.

Closely related to our work, Monti et al. (2017) formulated the generalized graph convolution model (MoNet) based on a trainable transformation to pseudo-coordinates, which led to learning anisotropic kernels and excellent results in visual tasks. In some cases, it outperforms our model in image classification (Table 2 ). However, in non-visual tasks, when coordinates are not naturally defined, the performance gain is less pronounced (Table 1 ). Notably, the computational cost (both memory and speed) of MoNet is higher than for ChebNet due to the patch operator in Monti et al.

(2017, Eq. ( 9)-( 11)). The argument in favor of MoNet against ChebNet was the sensitivity of spectral convolution methods, including ChebNet, to changes in graph size and structure. We contradict this argument and show comparable performance on visual tasks and better performance on chemical and social graph classification datasets. SplineCNN (Fey et al., 2018) is similar to MoNet and is good at classifying both graphs and nodes, but it is also based on pseudo coordinates and, therefore, has the same shortcoming of MoNet. So, its performance on general graph classification problems where coordinates are not well defined is expected to be inferior.

6. CONCLUSION:

In this work, we address several limitations of current graph convolutional networks and show superior graph classification results on a number of chemical, social, and image-based datasets. First, we revisit the spectral graph convolution model based on the Chebyshev polynomial, commonly believed to inherit shortcomings of earlier spectral methods, and demonstrate its ability to learn from graphs of arbitrary size and structure. Second, we design and study edge fusion methods for multirelational graphs, and show the importance of validating these methods for each task to achieve optimal performance. Third, we propose a way to learn new edges in a graph jointly with a graph classification model. Our results show that the learned edges are complimentary to edges already annotated, providing a significant gain in accuracy. Finally, we show that by adding hierarchical edges for images and fusing them with spatial and learned edges, we can further improve results.

:



Figures and Tables:

Figure 1: Histograms of eigenvalues of the rescaled graph Laplacian L for the (a) ENZYMES, (b) COLLAB and (c) MNIST (for 75 superpixels, see Section 3.2 for detail) datasets. Due to the property of eigendecomposition ( Lk = U Λk U T ) the distribution of eigenvalues shrinks when we take powers of L to compute the approximate spectral graph convolution (Eq. 2).

EDGES FOR IMAGES Image classification was recently formulated as a graph classification problem in Defferrard et al. (2016); Monti et al. (2017); Fey et al. (

Figure 3: Top row:We compute superpixels at several scales and combine all of them into a single set. We then build a graph, where each node corresponds to a superpixel from this set and has associated features, such as mean RGB color, coordinates of center of masses or convolutional VGG-16 features. Bottom row: Using Eq. 8 and 9, we compute spatial (a) and hierarchical (c) edges between nodes represented as scaled graph Laplacians L. Nodes 0 to 300 correspond to the first level of hierarchy (first scale of superpixels), and 300 to 400 corresponds to the second level, and so forth. Notice that spatial edges (a) are created both within and across the levels, while hierarchical (c) edges exist only between hierarchical levels. (c, d) Powers of these graph Laplacians LK=7 allow edges to diffuse over the graph making it possible to learn filters with more global support.

Figure 4: Graph classification pipeline for images. Each l th convolutional layer in our model takes the graph G l = (V l , E (r) ) and returns a graph with the same nodes and edges. Node features become increasingly global after each subsequent layer as the receptive field increases, while edges are propagated without changes. As a result, after several graph convolutional layers, each node in the graph contains information about its neighbors and the entire graph. By pooling over nodes we summarize the information collected by each node. Fully-connected layers follow global pooling to perform classification. For chemical/social datasets we use a similar pipeline, but the input graph G is provided by the dataset rather than built from images and does not have hierarchical edges.

Figure 5: Comparison of edge fusion methods on chemical and social datasets for 10 folds.We observe that some methods perform well for lower order K, such as 2d Chebyshev convolution winning in 21/80 cases for K = 2, while others perform better for higher K, such as Multiply-shared. Multiply generally performs well across different K. All fusion methods, except for Sum-shared, outperform the Single-edge baseline. We also show the number of parameters in Θ for the Chebyshev convolution layer depending on the number of input features X in , number of output features X out , number of relation types R, order K and some constant C (number of hidden units in a projection layer f r in Eq. 5). *Single-edge denotes using only annotated edges. All other methods additionally use the second edge, learned based on node features.

Image classification results. *Compared to tne implementation of ChebNet inDefferrard et al. (2016);Monti et al. (2017), our implementation has GMP without any pooling between convolutional layers, BN, a different learning rate and filter order K. R is the number of relation types.† LeCun et al. (1998) for MNIST,Hinton et al. (2012) for CIFAR-10, VGG-16(Simonyan & Zisserman, 2014) pre-trained on ImageNet for PASCAL. ‡ On 3× GTX Titan Black GPUs in PyTorch.

Table content: <table><tr><td>Model</td><td>R</td><td colspan="2">MNIST</td><td colspan="2">CIFAR-10</td><td>PASCAL</td></tr><tr><td>Node features</td><td/><td colspan="2">mean color</td><td colspan="3">mean color + coord vgg16 + coord</td></tr><tr><td>Graph</td><td/><td>Full grid</td><td>75 sp</td><td>Full grid</td><td>300 sp</td><td>1000 sp</td></tr><tr><td>ConvNet  †</td><td>-</td><td>99.33</td><td>-</td><td>84.40</td><td>-</td><td>85.88</td></tr><tr><td>GCN (Kipf &amp; Welling, 2016)-ours*</td><td>1</td><td>79.28</td><td>80.35</td><td>43.94</td><td>45.51</td><td>84.25</td></tr><tr><td>MoNet (Monti et al., 2017)-ours*</td><td colspan="4">1 &gt; 7 days  ‡ 98.59 &gt; 7 days  ‡</td><td>75.23</td><td>80.05</td></tr><tr><td colspan="2">ChebNet (Defferrard et al., 2016)-ours* 1</td><td>98.45</td><td>97.12</td><td>72.15</td><td>69.95</td><td>86.41</td></tr><tr><td>Multigraph ChebNet</td><td>2</td><td>99.36</td><td>97.43</td><td>72.98</td><td>70.96</td><td>86.78</td></tr><tr><td>Hierarchical ChebNet</td><td>2</td><td>99.09</td><td>97.79</td><td>74.39</td><td>73.15</td><td>86.55</td></tr><tr><td>Hierarchical Multigraph ChebNet</td><td>3</td><td>99.24</td><td>98.16</td><td>75.67</td><td>73.35</td><td>86.43</td></tr><tr><td colspan="4">model, Graph Convolutional Networks (GCN) Kipf &amp; Welling (</td><td/><td/><td/></tr></table>

Peer review (iclr2019):
 # Summary of the paper This paper presents a method for graph classification based on spectral convolutional neural networks. At its heart, the paper applies a standard decomposition in terms of the graph Laplacian and uses Chebyshev polynomials to obtain an approximation of node feature convolution. This is now extended to graphs with multiple edge relation types by performing the same calculations for every Laplacian that is induced by a certain relation , and either extended the Chebyshev polynomials to multiple variables, or multiplying/adding the resulting feature vectors. # Review The main idea of this paper, i.e. improving graph classification results by exploiting different types of edges, is very interesting. In particular for data sets with additional hierarchical information, this could well increase performance significantly. However, in its present form, the paper suffers from several issues. The following is a brief listing; each point will be expanded on below: 1. Issues with originality: at times, it is unclear in what ways previous work is extended 2. Issues with clarity: while most of the parts of the method can be *reconstructed* through literature knowledge, the paper is not self-contained and often uses terms without explaining them. 3. Issues with experiments: the reported results are *not* state-of-the-art for several data sets and I doubt the correctness of the setup. In particular the experimental issues I consider to be highly problematic at the moment. ## Originality: The paper needs to be more clear about its contributions. Some parts read like an introduction to GCNs, but it is often not clear what is novel here: - The main contribution, as far as I understand it, should be an extension of `ChebNet` to multigraphs. However, different relations in a graph appear to be modelled by calculating multiple graph Laplacians, which in turn can be stacked; this strikes me as a rather straightforward extension. Furthermore, the operation in Eq. 5 also appears a straightforward extension that uses learned node embeddings for each relation type. - The learning of edges for each relation, described in Section 3.1, is also a straightforward formulation/re-use of previous work (the papers cites Velickovic et al. (2018) as an example), and I do not exactly what is novel here: Velickovic et al. use the same equation to predict coefficients, as claimed in the paper, but how is this different from learning a weight for all edges as in Eq. 7? In Velickovic et al., this coefficient is only calculated for some of the edges. Is the novelty then that this is calculated for _all_ edges here? ## Clarity: - The explanation of the Chebyshev expansion could be improved: Kipf & Welling (2016), for example, explain this in term of signal convolution (Eq. 3--5 in their paper), while for this paper, the introduction of node features in Eq. 2 is not clear. - What is in Eq. 5? Is this an input signal at the nodes of a graph or an additional function defined on it, such as in the `ChebNet` paper by Monti et al.? - What is in Eq. 7? - What is in EQ. 5? The preceding section only introduces a notation for with multiple indices, but suddenly, is now indexed over the number of relations. - p. 4: The paper seems to be contradicting itself at places: the multi-variable polynomials from Eq. 3 and Eq. 4 are said to have a great computational cost and an exponential number of parameters for many relations. But the edge feature concatenation introduced at the bottom of p. 3 is dismissed by saying that it grows _linearly_ with . What am I missing here? - The paper claims that most data set, except for the image, only have a single relation type ( ); later on, *learned edges* are added for training. While I understand this and the benefits of adding them, I think that this should be clarified more: the advantage of the current approach seems to be that it can leverage more information by treating learned edges as a separate entity. This should be highlighted better. - In general, the paper would benefit from a section that describes the full method, preferably with a few equations, so that the readers can see at one glance which parts are involved. At present, I am doubtful about the reproducibility of the method. ## Experimental setup This is the major issue for me: the paper claims to follow a *standard approach to evaluation* (p. 6) that consists of a 10-fold cross-validation. However, only average classification accuracies are reported, even though the sources I checked (Shervashidze et al., Yanardag & Vishwanathan, Niepert et al.) provide also the *standard deviation* along with the mean accuracy. This is important to know, since often (in particular for smaller data sets), there is a lot of overlap in terms of accuracy +- sdev. Moreover, the reported accuracies are just not state of the art: the 2016 paper *On Valid Optimal Assignment Kernels and Applications to Graph Classification* by Kriege et al. describes a novel variant of the Weisfeiler-Lehman graph kernel, referred to as WL-OA. The reported accuracies +- sdev are as follows: - NCI1: 86.1±0.2 (better than in the current paper) - NCI109 86.3±0.2 (better than in the current paper) - MUTAG: 86.0±1.7 (worse than in the current paper; WL instead of WL-OA) - ENYZMES: 59.9±1.1 (worse than in the current paper) - PROTEINS: 76.4±0.4 (better/equal to the current paper) - COLLAB: 80.7±0.1 (better than in the current paper) Even accounting for standard deviations, WL-OA appears to have a good *safety margin* in terms of accuracy here. The claim that the new method *wins by a large margin* here is thus flatly false. Furthermore, I find the way results are reported somewhat misleading: since Table 1 shows the second-best result in bold, the Multigraph Chebnet results appear to be more important. At the very least, the standard deviations have to reported, and the experimental setup should be described in more detail, because the graph kernel publications also clarify that they learn their parameters on an inner validation such that only training data is used for hyperparameter tuning. It is unclear whether the paper is following the same approach here. # Minor issues - p. 2: use a consistent notation for the real space, i.e. or - p. 2: the justification of Eq. 1 could be phrased more succinctly: since is an orthogonal matrix, the convolution equation simplifies the way it is described; I find the description of *...property of eigendecomposition to eliminate computationally inconvenient eigenvectors* somewhat confusing - I don*t see the significance of Figure 1; it only expresses that matrix powers make eigenvalues smaller if (this property of the Laplacian is not mentioned, by the way) - p. 3: the notation for the number of relations is not optimal: should be rather rephrased as * is a matrix of the following dimensions* - The bibliography needs to be updated: there are some inconsistencies with respect to capitalization (such as in journal titles); also, at least the citation of Kipf & Welling should be adjusted as it is *not* a pre-print any more but was published in ICLR 2017 - p. 3: Figure 2 needs a better explanation to be fully useful: its purpose appears to show that a 2D Chebyshev polynomial captures a different sort of information than a 2-hop filter because it does use information about different edge relations. Is this not clear from the onset since multi-hop filters operate only on a _single_ view of the graph? - p. 3: Eq. 5 seems to be a Hadamard product, so another operator should be used (essentially a circle with a dot); at present, the operator is implying that one _composes_ features by first applying one filter, then another, and so on.