Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs

Introduction

Convolutional Neural Networks (CNNs) have gained massive popularity in tasks where the underlying data representation has a grid structure, such as in speech processing and natural language understanding (1D, temporal convolutions), in image classification and segmentation (2D, spatial convolutions), or in video parsing (3D, volumetric convolutions) .

On the other hand, in many other tasks the data naturally lie on irregular or generally non-Euclidean domains, which can be structured as graphs in many cases. These include problems in 3D modeling, computational chemistry and biology, geospatial analysis, social networks, or natural language semantics and knowledge bases, to name a few. Assuming that the locality, stationarity, and composionality principles of representation hold to at least some level in the data, it is meaningful to consider a hierarchical CNN-like architecture for processing it.

However, a generalization of CNNs from grids to general graphs is not straightforward and has recently become a topic of increased interest. We identify that the current formulations of graph convolution do not exploit edge labels, which results in an overly homogeneous view of local graph neighborhoods, with an effect similar to enforcing rotational invariance of filters in regular convolutions on images. Hence, in this work we propose a convolution operation which can make use of this information channel and show that it leads to an improved graph classification performance.

This novel formulation also opens up a broader range of applications; we concentrate here on point clouds specifically. Point clouds have been mostly ignored by deep learning so far, their voxelization being the only trend to the best of our knowledge . To offer a competitive alternative with a different set of advantages and disadvantages, we construct graphs in Euclidean space from point clouds in this work and demonstrate state of the art performance on Sydney dataset of LiDAR scans .

We formulate a convolution-like operation on graph signals performed in the spatial domain where filter weights are conditioned on edge labels (discrete or continuous) and dynamically generated for each specific input sample. Our networks work on graphs with arbitrary varying structure throughout a dataset.

We are the first to apply graph convolutions to point cloud classification. Our method outperforms volumetric approaches and attains the new state of the art performance on Sydney dataset, with the benefit of preserving sparsity and presumably fine details.

We reach a competitive level of performance on graph classification benchmark NCI1 , outperforming other approaches based on deep learning there.

Related Work

The first formulation of a convolutional network analogy for irregular domains modeled with graphs has been introduced by Bruna et al. , who looked into both the spatial and the spectral domain of representation for performing localized filtering.

A mathematically sound definition of convolution operator makes use of the spectral analysis theory, where it corresponds to multiplication of the signal on vertices transformed into the spectral domain by graph Fourier transform. The spatial locality of filters is then given by smoothness of the spectral filters, in case of modeled as B-splines. The transform involves very expensive multiplications with the eigenvector matrix. However, by a parameterization of filters as Chebyshev polynomials of eigenvalues and their approximate evaluation, computationally efficient and localized filtering has been recently achieved by Defferrard et al. . Nevertheless, the filters are still learned in the context of the spectrum of graph Laplacian, which therefore has to be the same for all graphs in a dataset. This means that the graph structure is fixed and only the signal defined on the vertices may differ. This precludes applications on problems where the graph structure varies in the dataset, such as meshes, point clouds, or diverse biochemical datasets.

To cover these important cases, we formulate our filtering approach in the spatial domain, where the limited complexity of evaluation and the localization property is provided by construction. The main challenge here is dealing with weight sharing among local neighborhoods , as the number of vertices adjacent to a particular vertex varies and their ordering is often not well definable.

Bruna et al. assumed fixed graph structure and did not share any weights among neighborhoods. Several works have independently dealt with this problem. Duvenaud et al. sum the signal over neighboring vertices followed by a weight matrix multiplication, effectively sharing the same weights among all edges. Atwood and Towsley share weights based on the number of hops between two vertices. Kipf and Welling further approximate the spectral method of and weaken the dependency on the Laplacian, but ultimately arrive at center-surround weighting of neighborhoods. None of these methods captures finer structure of the neighborhood and thus does not generalize the standard convolution on grids. In contrast, our method can make use of possible edge labels and is shown to generalize regular convolution (Section 3.2).

The approach of Niepert et al. introduces a heuristic for linearizing selected graph neighborhoods so that a conventional 1D CNN can be used. We share their goal of capturing structure in neighborhoods but approach it in a different way. Finally, Graph neural networks propagate features across a graph until (near) convergence and exploit edge labels as one of the sources of information as we do. However, their system is quite different from the current multilayer feed-forward architectures, making the reuse of today’s common building blocks not straightforward.

There has been little work on deep learning on point clouds or meshes. Masci et al. define convolution over patch descriptors around every vertex of a 3D mesh using geodesic distances, formulated in a deep learning architecture. The only way of processing point clouds using deep learning has been to first voxelize them before feeding them to a 3D CNN, be it for classification or segmentation purposes. Instead, we regard point cloud as graphs in Euclidean space in this work.

Method

We propose a method for performing convolutions over local graph neighborhoods exploiting edge labels (Section 3.1) and show it to generalize regular convolutions (Section 3.2). Afterwards, we present deep networks with our convolution operator (Section 3.3) in the case of point clouds (Section 3.4) and general graphs (Section 3.5).

The convolution operation, coined Edge-Conditioned Convolution (ECC), is formalized as follows:

Computing $X^{l}$ for all vertices requires at mostIf edge labels are represented by $s$ discrete values in a particular graph and $s<m$, $F^{l}$ can be evaluated only $s$-times. $m$ evaluations of $F^{l}$ and $m+n$ or $2m+n$ matrix-vector multiplications for directed, resp. undirected graphs. Both operations can be carried out efficiently on the GPU in batch-mode.

2 Relationship to Existing Formulations

Our formulation of convolution on graph neighborhoods retains the key properties of the standard convolution on regular grids that are useful in the context of CNNs: weight sharing and locality.

The weights in ECC are tied by edge label, which is in contrast to tying them by hop distance from a vertex , according to a neighborhood linearization heuristic , by being the central vertex or not , indiscriminately , or not at all .

In fact, our definition reduces to that of Duvenaud et al. (up to scaling) in the case of uninformative edge labels: $\sum_{j\in N(i)}\Theta_{ji}^{l}X^{l-1}(j)=\Theta^{l}\sum_{j\in N(i)}X^{l-1}(j)$ if $\Theta_{ji}^{l}=\Theta^{l}\;\;\forall(j,i)\in E$.

This shows that ECC can retain the same number of parameteres and computational complexity of the regular convolution in the case of grids. Note that such equivalence is not possible with none of due to their way of weight tying.

3 Deep Networks with ECC

While ECC is in principle applicable to both vertex classification and graph classification tasks, in this paper we restrict ourselves only to the latter one, i.e. predicting a class for the whole input graph. Hence, we follow the common architectural pattern for feed-forward networks of interlaced convolutions and poolings topped by global pooling and fully-connected layers, see Figure 3 for an illustration. This way, information from the local neighborhoods gets combined over successive layers to gain context (enlarge receptive field). While edge labels are fixed for a particular graph, their (learned) interpretation by the means of filter generating networks may change from layer to layer (weights of $F^{l}$ are not shared among layers). Therefore, the restriction of ECC to 1-hop neighborhoods $N(i)$ is not a constraint, akin to using small 3$\times$3 filters in normal CNNs in exchange for deeper networks, which is known to be beneficial .

We use batch normalization after each convolution, which was necessary for the learning to converge. Interestingly, we had no success with other feature normalization techniques such as data-dependent initialization or layer normalization .

During coarsening, a small graph may be reduced to several disconnected vertices in its lower resolutions without problems as self-edges are always present. Since the architecture is designed to process graphs with variable $n,m$, we deal with varying vertex count $n^{(h_{max})}$ in the lowest graph resolution by global average/max pooling.

4 Application in Point Clouds

Point clouds are an important 3D data modality arising from many acquisition techniques, such as laser scanning (LiDAR) or multi-view reconstruction. Due to their natural irregularity and sparsity, so far the only way of processing point clouds using deep learning has been to first voxelize them before feeding them to a 3D CNN, be it for classification or segmentation purposes. Such a dense representation is very hardware friendly and simple to handle with the current deep learning frameworks.

On the other hand, there are several disadvantages too. First, voxel representation tends to be much more expensive in terms of memory than usually sparse point clouds (we are not aware of any GPU implementation of convolutions on sparse tensors). Second, the necessity to fit them into a fixed size 3D grid brings about discretization artifacts and the loss of metric scale and possibly of details. With this work, we would like to offer a competitive alternative to the mainstream by performing deep learning on point clouds directly. As far as we know, we are the first to demonstrate such a result.

Given a point cloud $P$ with its point features $X_{P}$ (such as laser return intensity or color) we build a directed graph $G=(V,E)$ and set up its labels $X^{0}$ and $L$ as follows. First, we create vertex $i\in V$ for every point $p\in P$ and assign the respective signal to it by $X^{0}(i)=X_{P}(p)$ (or 0 if there are no features $X_{P}(p)$). Then we connect each vertex $i$ to all vertices $j$ in its spatial neighborhood by a directed edge $(j,i)$. In our experiments with neighborhoods, fixed metric radius $\rho$ worked better than a fixed number of neighbors. The offset $\delta=p_{j}-p_{i}$ between the points corresponding to vertices $j$, $i$ is represented in Cartesian and spherical coordinates as 6D edge label vector $L(j,i)=(\delta_{x},\delta_{y},\delta_{z},||\delta||,\arccos\delta_{z}/||\delta||,\arctan\delta_{y}/\delta_{x})$.

For a single input point cloud $P$, a pyramid of downsampled point clouds $P^{(h)}$ is obtained by the VoxelGrid algorithm , which overlays a grid of resolution $r^{(h)}$ over the point cloud and replaces all points within a voxel with their centroid (and thus maintains subvoxel accuracy). Each of the resulting point clouds $P^{(h)}$ is then independently converted into a graph $G^{(h)}$ and labeling $L^{(h)}$ with neighborhood radius $\rho^{(h)}$ as described above. The pooling map $M^{(h)}$ is defined so that each point in $P^{(h-1)}$ is assigned to its spatially nearest point in the subsampled point cloud $P^{(h)}$.

In order to reduce overfitting on small datasets, we perform online data augmentation. In particular, we randomly rotate point clouds about their up-axis, jitter their scale, perform mirroring, or delete random points.

5 Application in General Graphs

Many problems can be modeled directly as graphs. In such cases the graph dataset is already given and only the appropriate graph coarsening scheme needs to be chosen. This is by no means trivial and there exists a large body of literature on this problem . Without any concept of spatial localization of vertices, we resort to established graph coarsening algorithms and utilize the multiresolution framework of Shuman et al. , which works by repeated downsampling and graph reduction of the input graph. The downsampling step is based on splitting the graph into two components by the sign of the largest eigenvector of the Laplacian. This is followed by Kron reduction , which also defines the new edge labeling, enhanced with spectral sparsification of edges . Note that the algorithm regards graphs as unweighted for the purpose of coarsening.

This method is attractive for us because of two reasons. Each downsampling step removes approximately half of the vertices, guaranteeing a certain level of pooling strength, and the sparsification step is randomized. The latter property is exploited as a useful data augmentation technique since several different graph pyramids can be generated from a single input graph. This is in spirit similar to the effect of fractional max-pooling . We do not perform any other data augmentation.

Experiments

The proposed method is evaluated in point cloud classification (real-world data in Section 4.1 and synthetic in 4.2) and on a standard graph classification benchmark (Section 4.3). In addition, we validate our method and study its properties on MNIST (Section 4.4).

This point cloud dataset consists of 588 objects in 14 categories (vehicles, pedestrians, signs, and trees) manually extracted from 360∘ LiDAR scans, see Figure 4. It demonstrates non-ideal sensing conditions with occlusions (holes) and a large variability in viewpoint (single viewpoint). This makes object classification a challenging task.

Following the protocol employed by the dataset authors, we report the mean F1 score weighted by class frequency, as the dataset is imbalanced. This score is further aggregated over four standard training/testing splits.

Our ECC-network has 7 parametric layers and 4 levels of graph resolution. Its configuration can be described as C(16)-C(32)-MP(0.25,0.5)-C(32)-C(32)-MP(0.75,1.5)-C(64)-MP(1.5,1.5)-GAP-FC(64)-D(0.2)-FC(14), where C($c$) denotes ECC with $c$ output channels followed by affine batch normalization and ReLU activation, MP($r$,$\rho$) stands for max-pooling down to grid resolution of $r$ meters and neighborhood radius of $\rho$ meters, GAP is global average pooling, FC($c$) is fully-connected layer with $c$ output channels, and D($p$) is dropout with probability $p$. The filter-generating networks $F^{l}$ have configuration FC(16)-FC(32)-FC($d_{l}d_{l-1}$) with orthogonal weight initialization and ReLUs in between. Input graphs are created with $r^{0}=0.1$ and $\rho^{0}=0.2$ meters to break overly dense point clusters. Networks are trained with SGD and cross-entropy loss for 250 epochs with batch size 32 and learning rate 0.1 step-wise decreasing after 200 and 245 epochs. Vertex signal $X^{0}$ is scalar laser return intensity (0-255), representing depth.

Table 1 compares our result (ECC, 78.4) against two methods based on volumetric CNNs evaluated on voxelized occupancy grids of size 32x32x32 (VoxNet 73.0 and ORION 77.8), which we outperform by a small margin and set the new state of the art result on this dataset.

In the same table, we also study the dependence on convolution radii $\rho$: increasing them $1.5\times$ or $2\times$ in all convolutional layers leads to a drop in performance, which would correspond to a preference of using smaller filters in regular CNNs. The average neighborhood size is roughly 10 vertices for our best-performing network. We hypothesize that larger radii smooth out the information in the central vertex. To investigate this, we increased the importance of the self-loop by adding an identity skip-connection (see Appendix E) and retrained the networks. We achieved 77.0, 79.5 (the new state of the art), and 77.4 mean F1 for ECC, ECC $1.5\rho$, and ECC $2\rho$, respectively. Stronger identity connection allowed for successful integration of a larger context, up to some limit, which indeed suggests that information should be aggregated neither too much nor too little.

2 ModelNet

ModelNet is a large scale collection of object meshes. We evaluate classification performance on its subsets ModelNet10 (3991/908 train/test examples in 10 categories) and ModelNet40 (9843/2468 train/test examples in 40 categories). Synthetic point clouds are created from meshes by uniformly sampling 1000 points on mesh faces according to face area (a simulation of acquisition from multiple viewpoints) and rescaled into a unit sphere.

Our ECC-network for ModelNet10 has 7 parametric layers and 3 levels of graph resolution with configuration C(16)-C(32)-MP(2.5/32,7.5/32)-C(32)-C(32)-MP(7.5/32,22.5/32)-C(64)-GMP-FC(64)-D(0.2)-FC(10), GMP being global max pooling. Other definitions and filter-generating networks $F^{l}$ are as in Section 4.1. Input graphs are created with $r^{0}=1/32$ and $\rho^{0}=2/32$ units, mimicking the typical grid resolution of $32^{3}$ in voxel-based methods. The network is trained with SGD and cross-entropy loss for 175 epochs with batch size 64 and learning rate 0.1 step-wise decreasing after every 50 epochs. There is no vertex signal, i.e. $X^{0}$ are zero. For ModelNet40, the network is wider (C(24), C(48), C(48), C(48), C(96), FC(64), FC(40)) and is trained for 100 epochs with learning rate decreasing after each 30 epochs.

Table 2 compares our result to several recent works, based either on volumetric or rendered image representation . Test sets were expanded to include 12 orientations (ECC). We also evaluate voting over orientations (ECC 12 votes), which slightly improves the results likely due to the rotational variance of VoxelGrid algorithm. While not fully reaching the state of the art, we believe our method remains very competitive (90.8%, resp. 87.4% mean instance accuracy). For a fairer comparison, a leading volumetric method should be retrained on voxelized synthetic point clouds.

3 Graph Classification

We evaluate on a graph classification benchmark frequently used in the community, consisting of five datasets: NCI1, NCI109, MUTAG, ENZYMES, and D&D. Their properties can be found in Table 3, indicating the variability in dataset sizes, in graph sizes, and in the availability of labels. Following , we perform 10-fold cross-validation with 9 folds for training and 1 for testing and report the average prediction accuracy.

NCI1 and NCI109 consist of graph representations of chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines, respectively. MUTAG is a dataset of nitro compounds labeled according to whether or not they have a mutagenic effect on a bacterium. ENZYMES contains representations of tertiary structure of 6 classes of enzymes. D&D is a database of protein structures (vertices are amino acids, edges indicate spatial closeness) classified as enzymes and non-enzymes.

Our ECC-network for NCI1 has 8 parametric layers and 3 levels of graph resolution. Its configuration can be described as C(48)-C(48)-C(48)-MP-C(48)-C(64)-MP-C(64)-GAP-FC(64)-D(0.1)-FC(2), where C($c$) denotes ECC with $c$ output channels followed by affine batch normalization, ReLU activation and dropout (probability 0.05), MP stands for max-pooling onto a coarser graph, GAP is global average pooling, FC($c$) is fully-connected layer with $c$ output channels, and D($p$) is dropout with probability $p$. The filter-generating networks $F^{l}$ have configuration FC(64)-FC($d_{l}d_{l-1}$) with orthogonal weight initialization and ReLU in between. Labels are encoded as one-hot vectors ($d_{0}=37$ and $s=4$ due to an extra label for self-connections). Networks are trained with SGD and cross-entropy loss for 50 epochs with batch size 64 and learning rate 0.1 step-wise decreasing after 25, 35, and 45 epochs. The dataset is expanded five times by randomized sparsification (Section 3.5). Small deviations from this description for the other four datasets are mentioned in the supplementary.

We compare our method (ECC) to the state of the art Weisfeiler-Lehman graph kernel et al. and to four approaches using deep learning as at least one of their components . Randomized sparsification used during training time can also be exploited at test time, when the network prediction scores (ECC-5-scores) or votes (ECC-5-votes) are averaged over 5 runs. To judge the influence of edge labels, we run our method with uniform labels and $F^{l}$ being a single layer FC($d_{l}d_{l-1}$) without biasAlso possible for unlabeled ENZYMES and D&D, since our method uses labels from Kron reduction for all coarsened graphs by default. (ECC no edge labels).

Table 4 conveys that while there is no clear winning algorithm, our method performs at the level of state of the art for edge-labeled datasets (NCI1, NCI109, MUTAG). The results demonstrate the importance of exploiting edge labels for convolution-based methods, as the performance of DCNN and ECC without edge labels is distinctly worse, justifying the motivation behind this paper. Averaging over random sparsifications at test time improves accuracy by a small amount. Our results on datasets without edge labels (ENZYMES, D&D) are somewhat below the state of the art but still at a reasonable level, though improvement in this case was not the aim of this work. This indicates that further research is needed into the adaptation of CNNs to general graphs. A more detailed discussion for each dataset is available in the supplementary.

4 MNIST

To further validate our method, we applied it to the MNIST classification problem , a dataset of 70k greyscale images of handwritten digits represented on a 2D grid of size 28$\times$28. We regard each image $I$ as point cloud $P$ with points $p_{i}=(x,y,0)$ and signal $X^{0}(i)=I(x,y)$ representing each pixel, $x,y\in\{0,..,27\}$. Edge labeling and graph coarsening is performed as explained in Section 3.4. We are mainly interested in two questions: Is ECC able to reach the standard performance on this classic baseline? What kind of representation does it learn?

Our ECC-network has 5 parametric layers with configuration C(16)-MP(2,3.4)-C(32)-MP(4,6.8)-C(64)-MP(8,30)-C(128)-D(0.5)-FC(10); the notation and filter-generating network being as in Section 4.1. The last convolution has a stride of 30 and thus maps all $4\times 4$ points to only a single point. Input graphs are created with $r^{0}=1$ and $\rho^{0}=2.9$. This model exactly corresponds to a regular CNN with three convolutions with filters of size 5$\times$5, 3$\times$3, and 3$\times$3 interlaced with max-poolings of size 2$\times$2, finished with two fully connected layers. Networks are trained with SGD and cross-entropy loss for 20 epochs with batch size 64 and learning rate 0.01 step-wise decreasing after 10 and 15 epochs.

Table 5 proves that our ECC network can achieve the level of quality comparable to the good standard in the community (99.14). This is exactly the same accuracy as reported by Defferrard et al. and better than what is offered by other spectral-based approaches (98.2 , 94.96 ). Note that we are not aiming at becoming the state of the art on MNIST by this work.

Next, we investigate the effect of regular grid and irregular mesh. To this end, we discard all black points ($X^{0}(i)=0$) from the point clouds, corresponding to 80.9% of data, and retrain the network (ECC sparse input). Exactly the same test performance is obtained (99.14), indicating that our method is very stable with respect to graph structure changing from sample to sample.

Furthermore, we check the quality of the learned filter generating networks $F^{l}$. We compare with ECC configured to mimic regular convolution using single-layer filter networks and one-hot encoding of offsets (ECC one-hot), as described in Section 3.2. This configuration reaches 99.37 accuracy, or 0.23 more than ECC, implying that $F^{l}$ are not perfect but still perform very well in learning the proper partitioning of edge labels.

Conclusion

We have introduced edge-conditioned convolution (ECC), an operation on graph signal performed in the spatial domain where filter weights are conditioned on edge labels and dynamically generated for each specific input sample. We have shown that our formulation generalizes the standard convolution on graphs if edge labels are chosen properly and experimentally validated this assertion on MNIST. We applied our approach to point cloud classification in a novel way, setting a new state of the art performance on Sydney dataset. Furthermore, we have outperformed other deep learning-based approaches on graph classification dataset NCI1. The source code is available at https://github.com/mys007/ecc.

In feature work we would like to treat meshes as graphs rather than point clouds. Moreover, we plan to address the currently higher level of GPU memory consumption in case of large graphs with continuous edge labels, for example by randomized clustering, which could also serve as additional regularization through data augmentation.

We gratefully acknowledge NVIDIA Corporation for the donated GPU used in this research. We are thankful to anonymous reviewers for their feedback.

References

Appendix

Appendix A Overview

In the first part, the appendix provides further discussion of the graph classification results (Section B) and investigates robustness of point cloud classification to noise (Section C). In the second part, we explore several extensions of our ECC formulation, specifically with different edge labeling for point clouds (Section D), with identity connections (Section E), with degree labels (Section F), and with a learned normalization factor (Section G).

Appendix B Details on Graph Classification Benchmark

In this section we describe the differences in our network architecture to the one introduced for NCI1 in the main paper and discuss evaluation results for each dataset in detail.

ECC (83.80%) performs distinctly better than convolution methods that are not able to use edge labels (DCNN 62.61%, PSCN 78.59%). Methods not approaching the problem as convolutions on graphs but rather combining deep learning with other techniques are stronger (Deep WL 80.31%, structure2vec 83.72%) but are still outperformed by ECC. While the Weisfeiler-Lehman graph kernel remains the strongest method (WL 84.55%), it is fair to conclude that ECC, structure2vec, and WL perform at the same level.

We use the same ECC-network configuration and training details as described in Section 4.3 for NCI1, since both datasets are similar. ECC (82.14%) performs distinctly better than DCNN (62.86%), which is not able to use edge labels, and is on par with non-convolutional approaches (Deep WL 80.32%, structure2vec 82.16%, WL 84.49%).

As MUTAG is a tiny dataset of small graphs, we trained a downsized ECC-network to combat overfitting. Using the notation from Section 4.3, its configuration is C(16)-C(32)-C(48)-MP-C(64)-MP-GAP-FC(64)-D(0.2)-FC(2), all other details are as with NCI1. While by numbers ECC (89.44%) outperforms all other approaches except of PSCN (92.63%), we note that all four leading methods (Deep WL 87.44%, structure2vec 88.28%, ECC, PSCN) can be seen to perform equally well due to fluctuations caused by the dataset size. We account the tiny decrease in performance with test-time randomization (88.33%) to the same reason.

Due to higher complexity of this task we use a wider ECC-network configured as C(64)-C(64)-C(96)-MP-C(96)-C(128)-MP-C(128)-C(160)-MP-C(160)-GAP-FC(192)-D(0.2)-FC(6) using the notation and other details in Section 4.3. As this dataset is not edge-labeled, we do not expect to obtain the best performance. Indeed, our method (53.50%) performs at the level of Deep WL (53.43%) and is overperformed by WL (59.05%) and structure2vec (61.10%). Note that the gap to the other convolution-based method DCNN (18.10%) is huge and there is an improvement of more than 4 percentage points due to edge labels in coarser graph resolutions from Kron reduction.

Due to large graphs in this dataset we designed a ECC-network with more pooling configured as C(48)-C(48)-C(48)-MP-C(48)-MP-C(64)-MP-C(64)-MP-C(64)-MP-C(64)-MP-GAP-FC(64)-D(0.2)-FC(2) using the notation and other details in Section 4.3. As this dataset is not edge-labeled, we do not expect to obtain the best performance. Our method (74.10%) is overperformed by the others who evaluated on this dataset (PSCN 77.12%, WL 79.78%, structure2vec 82.22%), though the margin is not very large.

Appendix C Robustness to Noise

Real-world point clouds contain several kinds of artifacts, such as holes due to occlusions and Gaussian noise due to measurement uncertainty. Figure 6 shows that ECC is highly robust to point removal and can be made robust to additive Gaussian noise by a proper training data augmentation.

Appendix D Edge Labels for Point Clouds

In Section 3.4 we defined edge labels $L(j,i)$ as the offset $\delta=p_{j}-p_{i}$ in Cartesian and spherical coordinates, $L(j,i)=(\delta_{x},\delta_{y},\delta_{z},||\delta||,\arccos\delta_{z}/||\delta||,\arctan\delta_{y}/\delta_{x})$. Here, we explore the importance of individual elements in the proposed edge labeling and further evaluate labels invariant to rotation about objects’ vertical axis $z$ (IRz). Table 6 conveys that models with isotropic (60.7) or no labels (38.9) perform poorly as expected, while either of the coordinate systems is important. IRz labeling performs comparably or even slightly better than our proposed one. However, we believe this is a property of the specific dataset and may not necessarily generalize, an example being MNIST, where IRz is equivalent to full isotropy and decreases accuracy to 89.9%.

Appendix E Identity Connections

The formulation of ECC in Equation 1 does not treat self-loop edges in a special way. However, the success of residual networks is a strong motivation to consider adding identity skip-connections to our model and encouraging ECC in residual learning. We thus formulate ECC-resnet as follows:

The results listed in Table 7 show that with two exceptions (NCI109 and ENZYMES) ECC does not benefit from identity connections in the specific network configurations. The trend may be different for other configurations, e.g. ECC $1.5\rho$ improved from 76.9 to 79.5 mean F1 score on Sydney due to identity connections as mentioned in Section 4.1.

Appendix F Vertex Degrees in Edge Labels

In the task of graph classification, we used categorical labels (if present) encoded as one-hot vectors for edges in the input graph and scalars computed by Kron reduction for edges in all coarsened graphs.

Here we investigate making the edge labels more informative by including the degrees of the pair of vertices forming an edge. The degree information is implicitly used by spectral convolution methods, as the degree information is contained in the graph Laplacian, and also appears in the explicit propagation rules .

Table 8 reveals that degree information can improve the results considerably, especially for datasets without given edge labels (by up to 5 percentage points for ENZYMES and up to 2.14 percentage points for D&D). However, no variant of $L_{deg}(i)$ can guarantee consistent improvement over all datasets.

Appendix G Vertex Degrees in Normalization

In our experiments, the factor-generating networks $Z^{l}$ have configuration FC(32)-FC(1) with orthogonal weight initialization and ReLUs in between.

The results in Table 9 show that while being helpful on some datasets (NCI109, ENZYMES, ModelNet10), ECC-Z harms the performance on the other ones. Embedding vertex information in labels instead seems to achieve higher performance (Section F).