Fully Convolutional Graph Neural Networks using Bipartite Graph Convolutions
Authors: Marcel Nassar
Xin Wang
Evren Tumer
Venue:  (2020)
Keywords: Graph Neural Networks
Graph Convolutional Networks

Abstract: Graph neural networks have been adopted in numerous applications ranging from learning relational representations to modeling data on irregular domains such as point clouds, social graphs, and molecular structures. Though diverse in nature, graph neural network architectures remain limited by the graph convolution operator whose input and output graphs must have the same structure. With this restriction, representational hierarchy can only be built by graph convolution operations followed by non-parameterized pooling or expansion layers. This is very much like early convolutional network architectures, which later have been replaced by more effective parameterized strided and transpose convolution operations in combination with skip connections. In order to bring a similar change to graph convolutional networks, here we introduce the bipartite graph convolution operation, a parameterized transformation between different input and output graphs. Our framework is general enough to subsume conventional graph convolution and pooling as its special cases and supports multi-graph aggregation leading to a class of flexible and adaptable network architectures, termed BiGraphNet. By replacing the sequence of graph convolution and pooling in hierarchical architectures with a single parametric bipartite graph convolution, (i) we answer the question of whether graph pooling matters, and (ii) accelerate computations and lower memory requirements in hierarchical networks by eliminating pooling layers. Then, with concrete examples, we demonstrate that the general BiGraphNet formalism (iii) provides the modeling flexibility to build efficient architectures such as graph skip connections, and autoencoders.

Under review as a conference paper at ICLR 2020
FULLY CONVOLUTIONAL GRAPH NEURAL NETWORKS USING BIPARTITE GRAPH CONVOLUTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have been adopted in numerous applications ranging from learning relational representations to modeling data irregular domains such as point clouds, social graphs, and molecular structures. Though diverse in na- ture, graph neural network architectures remain limited by the graph convolution operator whose input and output graphs must have the same structure. Due to this restriction, representational hierarchy can only be built by graph convolution operations followed by non- parameterized pooling or expansion layers. This is very much like early convolutional network architectures, which later have been replaced by more effective parameterized strided and transpose convolution oper- ations in combination with skip connections. In order to bring a similar change to graph convolutional networks, here we introduce the bipartite graph convolu- tion operation, parameterized transformation between different input and output graphs. Our framework is general enough to subsume conventional graph convolu- tion and pooling as its special cases and supports multi miilliggrapphha aggregation leading to a class of flexible and adaptable network architectures, termed B BiGraphNet t. By replacing the sequence of graph convolution and pooling in hierarchical ar- chitectures with a single parametric bipartite graph convolution, we (i) answer the question of whether graph pooling is necessary, and (ii) accelerate compu- tations and lower memory requirements in hierarchical networks by eliminating pooling layers. Further, with concrete examples, we demonstrate that the general 3i EiGraphle BiGraphNet formalism (iii) provides the modeling flexibility to build efficient architectures such as graph skip connections, and graph autoencoders.
INTRODUCTION
Convolutional neural networks (CNNs) have been widely adopted in many applications from com- puter vision to natural language processing. CNNs' success stems from the flexibility of the convo- lution operation and its adaptability to various applications with seemingly different objectives such as localization and classification. Convolution operates sampled signals such as images and audio; thus, we refer to it as lattice convolution throughout this paper. In classification tasks, feature maps typically downsampled to achieve spatial invariance by reducing the spatial dimensions of the representation while learning higher-level abstractions.
implicit lattice representing uniformly-
While neural networks initially used pooling layers downsample the feature maps between convo- lution layers, more recent architectures have incorporated downsampling into the convolution layers by using strided convolution (He et al. 2016). Adding parameter-less "shortcut" or skip connections allows for deeper networks to be trained increasing their accuracy (He et al., 2016). Conversely. tasks such as super-resolution and semantic segmentation require the generation of details from coarser representations: this is achieved by the use of transposed (or fractionally strided) convolutions (Long) jet al., 2015). Furthermore, dilated convolutions can used to aggregate information and provide context over larger receptive ficlds without increasing the number of parameters (Yu & Koltun, 2016). Non-local networks introduce a convolution- operator that adds long-range connections into the typical lattice convolution operation (Wang al. (018c).
Though it natural for lattice convolution to exploit the inductive bias, namely translation- equivariance, employed by all CNNs, it is not straightforward generalize to irregularly sampled data, such as point clouds, molecular structures, and social networks. One approach to deal with such domains is to graph to describe the structure of the irregular domain and then apply graph

---

Under review as a conference paper at ICLR 2020
neural networks (GNNs), flavor of deep learning defined over graph strutsrt data for various learning tasks. In particular, graph convolutional networks (GCNs), the graph counterpart of CNNs, have been shown to be effective at exploiting the same translation-equuvariinee bias as the CNNs over the neighborhoods induced by the graph.
Though existing GCNs share basic common features with lattice CNNs in terms of localized pa- rameter sharing, the ways in which deep network architectures can be constructed based thereon are more limited in comparison. In particular, current GCNs depend on stacking separate graph pooling layers after graph convolution layers to build deep hierarchy, similar to early lattice CNN architec- tures such as AlexNet and VGGNet (Krizhevsky et al. 2012 Simonyan & Zisserman, 2014). Such conoolutionpoooling layer stacks have serious draw backs in constructing very deep networks, and eventually gave way to modern lattice CNN architectures such as ResNets (He et al. 2016), which use skip connections to enable much deeper architectures without accuracy loss. Analogously, exist- ing GCNs using graph convolution-pont poollnnnognggggooooo stacks likely suffer from the same problems, leading to inefficiency both in computation and in memory requirements that severely limit deeper graph CNN architectures and consequently their applications to large scale data sets such as dense point clouds or extensive relational databases.
How can one generalize graph convolution operations to construct analogous building blocks em- ployed by modern lattice CNN architectures, such as strided, transpose and dilated convolutions, as well as skip connections? To address this question, we present a novel learnable graph convolu- tion architecture defined over bipartite graphs that allows the input and output vertex sets and the edges between them to be specified in a flexible and learnable manner. We claim the following contributions:
1. Does graph pooling matter? We show that deep hierarchical GCN architectures built with the proposed learnable fully convolutional bipartite graph convolution layers in place of the sequence of graph convolution and non-parametric pooling layers retain or improve the performance of the original networks on numerous popular benchmarks.
2. Furthermore, by eleminating explicit pooling layers, the resulting bipartite graph convolutional architecture offers reduced computational and memory load.
3. Then, we demonstrate through concrete examples that the proposed bipartite graph convolution layer provides flexible primitive for building various architectures such as: graph skip connec- tions, and graph encoder-decode architectures leading to superior performance.
Since our proposed architecture is made up entirely from learnable (parameterized) graph convolu- tional layers, we refer to as being fully convolutional.
RELATED WORK
Graph neural networks (GNNs): introduced by F. Scarselli & Monfardini (2009), GNNs have recently become an active area of research especially GCN that extend localized parameter sharing (Bronstein et al. 2017 Battaglia & et. al., 2018) Wu et al. 2019). Bruna et al. (2014) introduced spectral methods that compute graph convolution in the Fourier domain through the decomposition of the graph Laplacian. This was later simplified by KKip' & Welling (2017) to operate the 1-hop spatial neighborhoods of the graph. Since then, significant progress has been made on extending graph convolution on the neighborhoods induced by the graph structure (Monti et al., 2016;; Si- monovsky & Komodakis] 2017 Hamilton et al.) 2017), such as adding graph attention (Veličkovid [al.|2018)) and providing general frameworks such as neural message passing (Gilmer et al. 2017))
Hierarchical GCNs: typically achieved through statically pooling and expansion; however, a
number of recent studies proposed dynamical hierarchical GNN operations that go beyond the sim- plc graph pooling. These are described in more detail in sections 3.2 and 3.3
Bipartite Graph Representation Learning: deals with applying GNNs learn representations of bipartite graphs. While limited in quantity, He et al. (2019) recently proposed using adversarial GNN techniques tackle this problem. It should be noted that this is a fundamentally different problem than the one addressed in this paper. This paper casts a hierarchy of two related graphs of any type into a single bipartite graph improve GCN architectures in general.
Continuous Point Convolutions: were introduced by Wang et al. (2018)) as a learnable operator that can operate on point clouds in metric spaces and applied to LIDAR data. This was later extended
2

---

Under review as a conference paper at ICLR 2020
bipartite gconv
06
M4
graph convolve
pooled clusters
0/
2/2
V1g
17
1/2
11g
15
G3
175
cluster assignments
07g
GpG.z....
cluster
cluster
edge legend:
non-parametric
parametric
(a)
(b)
Figure 1: Given a graph clustering, two approaches to construct hierarchical graph convolution from u-nodes to u-nodes: (a) parametric graph convolution followed by non-pant non-parametric pooling based on edges {(v,, Mj)]kes I (b) the proposed parametric bipartite graph convolution layer directly connects v-nodes to clustered u-nodes.
in Engelmann et al. (019) to include dilatation. Both of these are special cases of our proposed architecture which generalizes the concept more general graphs and convolution kernels.
HIERARCHICAL GRAPH CONVOLUTION NETWORKS
Hierarchy is typically achieved through two operations: (i) pooling or downsampling and (ii) un- pooling expansion. Figure [ a) shows how conventional GCNs employ two-layer approach to construct network hierarchy: a parametric graph convolution followed by non-parametric graph pooling or expansion. The following section describe each component in more detail.
3.1 GRAPH CONVOLUTION OPERATOR
graph G E G tuple EV,E) denoted by G(V,E) consisting of a vertex set V Ny and Ne an edge set E | 1=1- In weighted directed graphs, each edge ej is in turn a 3-tuple (v, u, r) where v is the source node, the destination node, and is the edge label, whereas each edge in an undirected graph can be represented as 2-tuple (v,u),r)
graph signal is mapping 8 V + T such that fi = s(n;) where fi is referred as the node feature of vertex V; graph convolution operator g : RIVXNN
IR V uses the graph
structure and locally aggregates the graph signal as follows:
(v.v;) red ([We)faly (g()), s(;))))
where red is a permutation-invarian reduction operation such as max, mean, or sum. 6g(vs) the neighborhood of the node in G. W.j E RMXN is feature weighting kernel transform- ing the graph's 'spp's --dimensional features to M-dimensional ones. Figure [[a) illustrates a graph convolution performed on node V1 (in red): the features of the nodes in the vi's neighborhood 5(v1) {U2, D3 U4, U3} are multiplied by a kernel followed by a reduction operation.
The form of the weighting kernel Wa, depends on the particular flavor of the GCN model:
Edge Conditioned Kernel: Wi, is a parameterized function dependant on the label of the edge between nodes 1; and vy denoted by ra.j. i.e. W.j ko(r),), where 0 are learnable parameters.

---

Under review as a conference paper at ICLR 2020
The edge labels, Pa.j. represent the relationship between the nodes connected by the edge. The parameterization of the kernel generation function varies: (i) in Simonovsky & Komodakis (2017).
ko()) is chosen to be neural network (typically mip); (ii) Monti al. (2016) Kg (a()) mixture
of Gaussians parameterized by their means and covariance matrices.
Graph Attention Kernel: Veličković et al. (0188) uses an attention mechanism (Vaswani et al, 2017) on the node features to construct the weighting kernel Wi, a4, where Oii soltmax (mlp(W]J Ji, W ([D)). In contrast, (Shang et al. 2018 uses the edge labels ri,5 to steer the attention mechanism; i.c. as.j softmax (mip(ra,))-
3.2 GRAPH CLUSTERING AND EXPANSION
The clustering operation constructs (or learns as in Ying et (2018)
membership relationship
mapping from each vertex between the two graph hierarchies. If < [V], then a coarser hierarchy with fewer nodes is created analogous strided CNNs. If K 2 [ then expanded graph is created analogous transposed CNNs. The set is analagous to the implicit www.---amlle//pssaaeee
G into a set of groups C. G J defining the relationship
grid in CNNs.
The clustering can be static: depending only the input graph. Then, C can be pre-computed as part of the data pre-processing. The clustering algorithm used depends on the type of graph data be- ing processed, e.g. VoxelGrid (Simonovsky & Komodakis 2017) and Self Organizing networks (Li et al. 2018) for point cloud data, and Graclus (Dhillon et al. (2007) for general weighted graphs. Recently, a new class of data-driven dynamic graph pooling architectures have been proposed. Wang et al. (201 8d) dynamically rebuild their graph structure by clustering features computed by the pre- ceding graph convolution. A more direct approach to dynamic pooling is to predict soft cluster membership for each node using a neural net followed by clustering as is proposed by Ying et al. (2018). Another computationally efficient method to simply drop fraction of the nodes based on computed score as used in Gao & Ji] (2019) and Cangea et al. (2018).
Graph expansion is less ubiquitous with applications in upsampling of point clouds as described by Fan et al. (2017), Yu et al. (2018), and Waan et al. (2018a). A common expansion pattern is simply to reverse the clustering maps obtained during encoding for decoding; such as the gUnpool layer in Graph U-Net (Gao & Ji 2019).
3.3 GRAPH POOLING AND UNPOOLING
This is a non-parametric (not learned) layer that takes as input cluster assignments given by de- termined by a clusteringlexpansion algorithm. Figure (a) illustrates the pooling procedure: given a cluster assignment Gs. propagate features along all edges (V,, us) where Uj E Gy followed by a reduction to get the feature vector at ug as:
po(ux) = red((Ul E Gk,Jz= = =((;)})
where r red is the chosen reduction operation (max or mean). Given that the pooling has traverse all edges the complexity required is on the order O(EE) Ex [Gx)) which is comparable to the graph convolution layer. For unpooling. typically a common feature is broadcast to all connected nodes instead of the reduction operation.
4 BIPARTITE GRAPH CONVOLUTION
Here, we introduce the bipartite graph convolution (BGC) operation illustrated figure [b). We show that stacked BGC layers generates fully convolutional hierarchical graph neural networks and describe their computational and architectural advantages.
4.1 BIPARTITE GRAPH CONVOLUTION (BGC)
A bipartite graph BG U, E) is graph G(V E) where all the edges are strictly between V and U4 i.c. the set of all edges & {(v, uilu E V,u E U4.
If we set the two sets of nodes V and 2/ as the inputs and outputs of the model, respectively, we can define the following graph convolution operator as
gsg (u) red ((W.,ifil) d5g (w), s(v))),
(3)
4

---

Under review as a conference paper at ICLR 2020
Vu E U where red is reduction operation, Wo, E R is feature weighting kernel and (u) = {u E (2, u) E {) is the neighborhood of the node u in BG (note that (Bg(u) C V). Equation B can be interpreted as a function whose domain is given by the set V. while its co-domain is given by the set I (see figure 2b)).. As a result, the bipartite graph convolution computation is driven by the edges connecting the output set 2/ nodes the input nodes in set V. As shown in figure 2bb), these edges are provided by an external clustering algorithms (static or dynamic) as
discussed in section 3.2 For example, the feature fi of node 4j U in figure 2 (fi = gBc (u1))
is function of the features of nodes {2, [u. 1- A key feature of the bipartite graph convolution as defined in equation B is that the input and output nodes are effectively disentangled allowing for the implementation of any relationship between the two sets in single operation just by specifying the edge set E. Furthermore, unlike the static pooling and unpooling, there is no restriction on the operation performed and in fact this operation can perform learnable combination of features through an appropriate choice of the kernel (see Section section 3.1.
Graph Convolution using BGC: By defining the graph convolution on the bipartite graph, BGC makes both graphs explicit through the two sets l/ and V. As a result, any typical graph convolution defined E can be written a bipartite graph convolution defined over BG(V, V, E)
Computational and Memory Complexity: A bipartite graph convolution operating on BG(V, E) will require ((max[|V), [2[] + (81) memory and computational resources. This is similar to a regular graph convolution and is exactly the same when the bipartite graph convolu- tion is used to implement regular graph convolution (u=V)). However, since a bipartite graph convolution can replace a sequence of graph convolution and graph pooling layer, it is fair to com- pare the requirements of single bipartite graph convolution layer to the combination of the both a graph convolution and pooling graph layers. Roughly, the sequence of graph convolution and graph pooling will have a complexity of 20(mxx ([maa|([pood |Ecomol)) } + max (V) (4))) while that of the bipartite graph convolution will be (maxx [pootl, i [Ecovel) | + max [V. [21]). (24)). Thus, by replac-
ing the pooled graph CNNs by BiGr GrGapphet. we save on computational resources and accelerate inference will be demonstrated in the experiments.
4.2 HIERARCHICAL FULLY CONVOLUTIONAL BIPARTITE GNNS
Fully convolutional graph neural networks (FullConvGNNs)) are composed only from graph con- volution layers without explicit pooling operations. Using the proposed parametric bipartite graph convolution, conventional hierarchical (containing non- non-parametric pooling or unpooling) GCN, la- beled pooled GCN (PoolGCNN), can be converted to FullConvGNT version.
Each basic block of a PoolGCN can be represented by two sequential layers (see figure a:): a parametric graph convolution layer operating graph Geone (V, E followed by a graph pooling layer that depends on some computed clustering (either static or dynamic), resulting in an output graph Gpo Epoot). A similar graph connectivity structure can be induced by using the bipartite graph whose input nodes are given by V and output nodes are given by U (BG(V, E')) (see figure (b)) To ensure the same connectivity, we set E" = Epoool o Egonv where o operation denotes a direct path; i.e. (v,u)= E E' iff 3o's st. v') E Econs and (v' (v',u) E Epool- It should be noted that, in general, a graph convolution followed by pooling is not equivalent to a bipartite graph convolution due to the presence of the max in pooling. In practice, the (G,V,,, by connecting the edges in E' according the pooling relationship instead of tracing the graph and pool domains. For example, in point cloud data the pooling can be done by downsampling using VoxelGrid and thus a k-d tree algorithm can construct BG directly.
can be constructed directly
Similar to downsampling, BiGraphNet can casily support expansion to any arbitrary graph by defining its output graph and the connecting edges. This is particularly powerful as it allows the connection of arbitrary node domains though a single learnable layer. Examples of this mixed- domain graph processing can be the projection of abstract relationship graphs into 2D arrays, or connecting points across different related domains as shown in Section
4.3 BIGRAPHNET ARCHITECTURES AND OPERATIONS
In this section, we describe some interesting architectures that can be constructed using the Bi GraphNeet architecture, Additional architectures are given a supplementary material.
5

---

Under review as a conference paper at ICLR 2020
BC(V) UV,, u,e" UE
source V/1
source V domain
domain
0000
doesin traesfor carafoor
donain traesfoore
cluster wespanssenoooo
33
doratn 24
Figure 2: Aggregation of two input graphs with vertex sets V and 1 into same output graph with vertex set U. Each the two input graphs can contain information from different graph domains or scales producing mixed fusion of information.
Skip Connection
Bipartite Graph Convolution
Bipartite Graph
Multi-graph
Convolation
Aggregation
Figure 3: A conceptual representation of graph autoencoder with both down-sampling and up- sampling strided BGC layers and skip connection to implement ResNet/U-NG style architecture.
Multiple Graph Aggregation Convolution: The output nodes determine the output domain of the graph convolution; however, there is no restriction on the input domain V. In fact, there is no restriction on the number of input sets that connect the output set. Given this fact, we can now define multiple graph aggregation convolution on a fixed output vertex set U from a collection of bipartite graphs (B9 (v* 5,C {
Jager (u)
Σ | x (8ec
(4)
Σn
|
An example with two input graphs is shown in Fig. This examples can be used to implement skip connection to produce graph ResNet equivalents. Furthermore, the multiple aggregation convolu- tions can be used to fuse mix domain graphs.
Graph AutoEncoders and BiGraphNet U-Net: Fig. 3 illustrates how to use the multi-graph aggregation to combine multi-scale graphs from different layers. This can be used to produce ResNet (He al. 2016) and U-Net (Ronneberger et al., 2015) style graph networks.
EXPERIMENTS
In this section, perform experiments to demonstrate our main claims presented in section [ Towards that goal, we tackle a suite tasks that typically employ hierarchical graph representations. Since these benchmarks typically employ pooling refer to them PoolGConvNet while our proposed architecture denoted as either FullConvGNN: (highlighting the fact that they are fully convolutional) Bi BiGrahNNet. See Appendix A for detailed experimental setup.

---

Under review as a conference paper at ICLR 2020
Run timee [ms] [forward + backward)
200
FuLLCWw
600
Pooled (ECC)
FullConv
PooLCCoNvARE
160
460
90.0 ModelNet40
ModelNet10
92.4 0.5
87.0
89.0 + 0.4
100
3001
NCI1
76.8
76.8 + 0.4
150
Enzymes 45.6
45.8 + 1.2
D&D
72.5
78.6 + 0.6
64
256
Batch size
(a)
(b)
Figure 4: (a) 3D point cloud classification and graph classification results. Instance precisions of graph-based ModelNet classifiers are shown for ModelNet10 and ModelNet40, and classification accuracies for the graph kernel benchmark data sets (b) Comparison of forward and backward run times (lines, left axis) and the memory consumption (bars, right axis) for the DD dataset as a function of batch size for FuIIConvGNN and PoolGConvNet.
5.1 DOES GRAPH POOLING MATTER? AND AT WHAT COST?
In this section, we pick tasks from 3D computer vision and general graph learning. These tasks involve the classification of certain 3D shapes and different molecular compounds. We choose the ECC network architectures given in (Simonovsky & Komodakis 2017) (referred to as Pooled in figure 44) and convert them Bi BiGraphNet architecture described in section 4.2 Both the original and derived architectures share the same number of parameters and are described in the Appendix A
We compare the performance of BiGraphNet (FullConv) against PoolGConvNets (ECC) on the ModeINet10/40 data sets and the graph classification tasks in Figure 4a] We directly compare only with PoolGConvNets since the architectural primitives are maintained in order to measure the ef- fectiveness of removing pooling layers. Also, no augmentations are used so that the comparison only across architectural primitives. With equal number of parameters, the BiGraphNet model, which has no pooling layers, achieves improved performance over PoolGConvNets. This may be due to the model learning a better aggregation through the parametrized convolutional layers.
Furthermore, we demonstrate the computational and memory saving resulting from using BiGraphNet fully convolutional architecture (FullConyGNN) vs. comparable pooled graph ConvNet (PoolGConvNett.. As discussed in Section 4.1 we expect FullConvGNN to outperform PoolGConNNet. We run this experiment the D&D dataset which has significant pooling layers. Fig [bg[4] the runtime the forward/backward pass and memory requirements both of these networks at different batch sizes. The figure shows that the FullConvGNN significantly outperforms the typical PoolGConvNet.
These experiments suggest that explicit non-parametric pooling layers typically used on hierarchical GCN might not be necessary and are leading to increased computational and memory loads.
5.2 FUNCTIONAL AUTOENCODER
Next present example of how the proposed bipartite graph convolution layer offer in- creased modeling and architectural flexibility in deploying GNNs. In particular, we apply GNNs to functional approximator presented in Garnelo et al. (2018) called Conditional Neural Processes (CNP). In their work neural network was used to replace the computationally expensive process of inferring the values of a Gaussian process (GP) set of target points using contextual observa- tions of the process. An autoencoder-like network was able to learn synthetic data set composed of random realizations of a GP to predict the functional form of novel GP realizations and do so effi ciently. Due to aggregation of the latent encoding over the whole context set, this model suffers from under-fitting at the context points where the function value is known. A GNNO-based autoencoder could preserve the local information from the the context points and generate better predictions at the target points. Here we show that a bipartite graph neural network can achieve better accuracy and the bipartite layers naturally allow for the input of context points and the output of prediction at different set of target points. Fig. Je. the autoencoder style model design taking set of context points and encoding those observations into latent representation. The decoder generates

---

Under review as a conference paper at ICLR 2020
Encoder
BiGraphNet bridge
Decoder
Figure 5: Irregularly sampled points (circles) from underlying realization of GP (red line) are processed by a GNN encoder which performs graph convolution over neighborhoods the input (dashed outlines). A BiGraphNet bridge transforms the representation from the input to output graph, and then "decoded" by a GNN to generate an approximation of the function at the target points. For validation, the model output is estimated line) to determine how well the underlying process (red dashed line) is captured.
uniformly sampled grid of points (blue
Model
#Params
Test NI.I
Test MSR
Model
#Params
Test MSB
64)
0.3271
0.06422
MLP
222, 384
0.089
CNP (d 96)
34,386 386
0.5602
0.04398
CouvNet
1,385
0.095
Grapb-AE
4,876
0.087
CGNP 64, p= KCGNP (d p 0.3)
75, 520
-05344
0.05272
712
-0.7652
0.03286
Graph U-Net
4,876
0.066
Table 1: Left: Parameter count, test NLL and MSE of CNP, CGNP and bCGNP models; Right: Parameter count and test MSE for graph encoder-decoder.
prediction of the function across the domain range (blue line) to test the performance against the ground truth (red dashed line). The left panel of table [ compares the BiGr BiGraphNet (bCGNP) results to the CNP results presented in Garnelo al. (2018). In particular, the bipartite graph conv layer further improves the performance of our graph based aggregator by adding the extra flexibility of connecting targets context points.
5.3 GRAPH ENCODER- DECODER ARCHITECTURES
Finally, we demonstrate the flexibility of the fully convolutional BiGraphNet by implementing a graph autoencoder MNIST images.
The results are given in the right half of Table T The Graph-AE performs significantly better than the ConvNet and par with the MLP that has an order of magnitude architecture performs even better by utilizing the multiscale encoder feature maps. This implies that edge and location based encoding of features is very useful in image recovery. In particular, an edge-based graph autoencoder (Graph-AE) achieves the same performance as fully connected autoencoder (MLP) fraction of the parameters orders of magnitude); alternatively. for the same number of parameters (Nu 4800), the edge-based graph autoencoder (Graph-AE) significantly im- proves the performance (zs 10% reduction in test mean squared error).
parameters. The U-Net
CONCLUSIONS
Here we show a novel form of graph neural network, called the BiGrahNet. that splits the graph into two parts: an input and an out graph. This innovation allows for development of computa- tional layers for the graph that are analogues to layers used in lattice convolutional networks such as strided convolutions, deconvolution and skip connections. Such modules are critical components for building hierarchical representations of graph based data sets. We compare BiG BiGraphNet based networks on some common applications to show that they can generate comparable or better perfor- mance.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Peter W. Battaglia and Relational inductive biases, deep learning, and graph networks. 2018.
Michael Bronstein, Xavier Bresson, Yann Lecun, Arthur Szlam, and Joan Bruna. Geometric deep learning graphs. IEEE Signal Processing Magazine, (July), 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. ICLR, 2014.
Ctlina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò. Towards Sparse Hierarchical Graph Classifiers, NeurIPS Workshop on Relational Representation Learning (R2L), 2018.
DeepMind. deepmiiddonndtionnleeennppppsss 2018. /reemmiind/onnniiionaall
URL httts:://ithub... com/
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted Graph Cuts without Figenvectors: A Multilevel Approach. PAMI, 2007.
Francis Engelmann. Theodora Kontogianni, and Bastian Leibe. Dilated point convolutions: On the receptive field of point convolutions. ArXiv, abs/1907.12046, 2019.
A. C. Tsoi M. Hagenbuchner F. Scarselli, M. Gori and Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20, 2009.
Haoqiang Fan, Hao Su, and Leonidas Guibas. A Point Set Generation Network for 3D Object Reconstruction from a Single Image. CVPR, 2017.
Hongyang Gao and Shuiwang Ji. Graph U-Net. ICLR, 2019.
Marta Garnelo, Dan Rosenbaum, Chris J Maddison, Tiago Ramalho, David Saxton, Murray Shana- han, Yee Whye Tch, Danilo J Rezende, and S M Ali Eslami. Conditional Neural Processes. ICML, 2018.
Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural Mes- sage Passing for Quantum Chemistry. ICML, 2017.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. NIPS, 2017.
Chaoyang He, Tian Xie, Yu Rong, Wen-bing Huang, Junzhou Huang, Xiang Ren, and Cyrus Sha- habi. Adversarial representation learning on large-scale bipartite graphs. CoRR, abs/1906. 1994, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. CVPR, 2016.
Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Net- works. ICLR, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems 25, pp- 1097- 1105. 2012.
Jiaxin Li, Ben M Chen, and Gim Hee Lee. SO-Net: Self-Organizing Network for Point Cloud Analysis. CVPR, 2018.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully Convolutional Networks for Semantic Segmentation. CVPR, 2015.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda. and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. CVPR, 2016.

---

Under review as a conference paper at ICLR 2020
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional Networks for Biomed- ical Image Segmentation. pp. 234-241, 2015.
Chao Shang. Qinqing Liu, Ko-Shin Chen, Jiangwen Sun, Jin Lu, Jinfeng Yi, and Jinbo Bi Edge attention-based multi-relational graph convolutional networks. CoRR, abs/1802.04944, 2018.
Martin Simonovsky and Nikos Komodakis. Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs. CVPR, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. NIPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. ICLR, 2018.
Nanyang Wang, Yinda Zhang, Zhuwen Li, Yanwei Fu, Wei Liu, and Yu-Gang Jiang. Pixel2Mesh: Generating 3D Mesh Models from Single RGB Images. 2018a.
Shenlong Wang, Simon Suo, Wei-Chiu Ma, Andrei Pokrovsky, and Raquel Urtasun. Deep paramet- ric continuous convolutional neural networks. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2018b.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local Neural Networks. CVPR, 2018c.
Yue Wang. Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael Bronstein, and Justin Solomon. Dynamic Graph CNN for Learning on Point Clouds. CoRR, abs/1801.07829, 2018d.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. CoRR, 0bs//1901.0056, 2019.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical Graph Representation Learning with Differentiable Pooling. NeurlPS, 2018
Fisher Yu and Vladlen Koltun. Multi-Scale Context Aggregation by Dilated Convolutions. ICLR, 2016.
Lequan Yu, Xianzhi Li, Chi-Wing&& Fu, Daniel Cohen-Or, and Pheng-Am Heng. PU-Net: Point
Cloud Upsampling Network. CVPR, 2018.
A. Khosla F. Yu L. Zhang X. Tang Z. Wu, S. Song and J. Xiao. 3D ShapeNets: A Deep Represen- tation for Volumetric Shape Modeling. CVPR, 2015.
10

---

Under review as a conference paper at ICLR 2020
A EXPERIMENTAL DETAILS
A.1 MODEL ARCHITECTURES
Model architectures of PoolGConvNets and corresponding FullConvGNNs are listed in Table 2
Experimental data sets and model architectures based on Simonovsky & Komodakis (017). GC, BGC correspond to a graph convolution and a bipartite graph convolution, respectively; MP, GMP, GAP correspond max-pooling layer, global max-pooling and global average-pooling layers, respectively; while mip indicate multi-layer perceptron network (i.e. fully connected lay- ers). The [-] indicates the feature dimensions with indicating multiplicity.
Table 2:
DATASET
ARCHITECTURE SPECIFICATION
MODELNETT0 Pool GCoNNNET GC(16, 32] - MP - GC| x 2 MP 6C[64] - GMP MT. [64, 10]
FULLCONVGNN 8GC[16, 32 x 3, 64] - MT.F (64, 10)
MODELNETT0
Pool GCONWNET FULLCONYGNN BGC 48 3, 96] MLF [64, 40]
GC/24, 48] - MP GC|48) x 2 MP 6C[96]
GMP MLP [64, 40)
NCII
POOLGCONVNET 6C[48] 3 MP GC[48, 64 MP GC[64] GAP MLP [64,
FULLCONYGNN BGC (8 4, 64 x xLP 664 2]
ENZYMES
POOLGCONYNET 6C(61, 64, 96] MP GG]|96, 128]
MP GC [128, 160]
MP
GC]]60]
GAP xip x1 192, 6]
FULLCONYGNN
BGC 2, x 2, 128 x 2, 160
MLE [192, 6
D&D
PoO..GCoNVNET GC[18] 3 MP -P- GC|48]
MP MP- GC[61]
MP GC[64] MP
GC (4] MP MPP GC|64]
MP GAP
MI. [64,
FULLCONYGNN GC[48 x 4, 6. x
X_P (64,2]
MNIST
POoL GCONVNET GC[16] MP GC 32
MP GC[64] MP GC[128) XT
FULLCONYGNN GC 16, 32, 64, 128]
ALE [10]
A.2
3D POINT CLOUD CLASSIFICATION
We test the performance of the BiG BiGraphNet architecture applied to classifying dense point clouds. For classification invariance, a graph neural network classifier needs to construct a hierarchy of down sampled signals down to vector representation used for classification (Simonovsky & Komodakis, 2017). The down sampling is also crucial for practical concerns such as GPU memory constraints that limit the model size. In typical graph NNs, such PoolGConvNets, the down sampling is composed of graph convolution followed by a graph pooling layer, while in BiG BiGraphNet this is performed using just one bipartite graph convolution layer.
We choose two point cloud data sets: the ModelNet10 and ModelNet40 benchmarks (Z. Wu & Xiao 2015). These are two commonly used data sets comprised of mesh surfaces of 10 and 40 different categories of objects, respectively. See/https://gitie httptthhwwbooooooooooee/eeee//ee and Simonovsky & Komodakis (2017) for details.
A.3 GRAPH CLASSIFICATION
We focus on 3 data sets typically used to verify the performance of graph classification networks: Enzymes, D&D, NICI. NCII consist of graph representations chemical compounds screened for activity against non-small cell lung cancer. ENZYMES contains representations of tertiary structure of 6 classes of enzymes. D&D database of protein structures classified as enzymes and non- enzymes.
A.4 FUNCTIONAL AUTOENCODER
Given family of functions F {fe} (fe : Y) parameterized by some parameters 0, we gen- crate a data set of samples from these functions D = [D+). where D; {(x,, yr = fe, (x;)) i=o for some valid parameter Oz. Using this data set of observations, we train a neural network to learn representation summarizing each sample Dj by representation rx. representation that can be used to interpolate the functional values other points (æ) and function parameters (0) not sampled in the data set (D). The input data irregularly sampled and areas with higher sample density will provide more context for estimating the function near those points. Functional approximation with these
11

---

Under review as a conference paper at ICLR 2020
constraints naturally fits into a bipartite graph ConvNet since GNNs allow for efficient exploitation of the induced metric as a relationship between two samples. We use an autoencoder (Fig. 3 archi- tecture and test the encoded representation F& by using it to estimate the values of the function at target points (1D regression task). This work analogous to the Conditional neural process (CNP) model Garnelo al. (2018) and show the advantages of Bi GraphNet over CNP.
Gaussian process (GP) is used to generate the training data set, a family functions with shared statistical properties. GPs are very powerful for fitting observed data for which the underlying process may not be known, but do so with a heavy computational price.
Our graph based model for this application is called Conditional Graph Neural Process (CGNP). Our final functional auto-encoder architecture is illustrated in Fig. 5 The Bi BiGraphNe* is particu- larly well suited to implement this fully convolutional architecture from the context all the way to the targets. The parameter d represents the dimensionality of the latent representation Further- more, we added pre-activation aatch-normalization layers, which improved model performance.
The CNP model, which will be used as baseline against which we compare the BiGraphNet per- formance, CNP uses the following to compute its representation: r mlp (Ir y:): red (r; Mi, Ø; ml r)), Each point of the input is processed independently, then all the encoded points (r+) are aggregated. The function approximated
the target points (x₂) by the decoder which takes the aggregated signal (r) concatenated with the target points input. The baseline CNP model taken from Deep.Mind (2018) with the encoder and decoder composed of 3-layer and 2-layer multi-layer perceptron (MLP), respectively.
Our CGNP model follows the published CNP architecture in terms of the encoder and decoder depths (3 and 2) and width (d), but replaces the MLP networks with bipartite graph convolutional networks. The radius of graph connection neighborhood is set to be p = 0.3.
A.S IMAGES AS GRAPHS
Each image (I) can be interpreted as signal (given by the pixel intensity) defined over set of coordinate nodes P = (<., y) x, E {0.... ,27)]- We follow the experiments described in Si- monovsky & Komodakis (207)) and use the spatial neighborhood to define relationship between two (abstract) nodes Vi, vy as follows
with rij = P: - P, iff pj E (p:)).
(5)
where 5p(-) represents the spatial neighborhood of radius p 2.9. Graph coarsening is implemented using the VoxelGrid algorithm Simonovsky & Komodakis (2117).
We try encoder-decoder architectures as described Section 4.3 particular, we implement an autoencoder (AE) and a graph U-Net with skip connections. We use the MNIST Bi BiGrapNNet net- work (without the mlp layer) given Table as the encoder and its inverse as the decoder. We also compare against the typical MLP and ConyNet autoencoder.
12


Reviews:
[{"review_id": "SkeIGYybcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new graph neural network model named BiGraphNet, which introduces a parameterized bipartite graph convolution operation to perform transformation between input and output graphs. The proposed method is claimed to have advantages over existing deep hierarchical GCN architectures mainly in terms of being able to construct analogous building blocks employed by modern lattice CNN architectures and the reduced computational and memory cost. The main weaknesses of this paper are listed as follows:\n\n1) The motivation is relatively weak, which is to bring in the analogous building blocks in CNN architectures. Although GNN is closely related to CNN and RNN, the graph learning tasks may not have the same property as in computer vision or natural language processing. It would be better to convince the readers from the GNN itself and carefully argue the necessity of the proposed method.\n\n2) The experiments in this paper are rather weak and not convincing. First there is no performance comparison to state-of-the-art GNN models, such as DGCNN, DIFFPOOL and GIN, etc. At least on the D&D dataset, many existing models report graph classification accuracy over 78.0, but the baseline method used in this paper only achieves 72.5. Thus it is not fair to claim the proposed method can retain or improve the performance of existing GNN models.\n\n3) The related work comparison is not sufficient. For example, some existing works have already explored to apply skip connections to the graph neural networks, such as [1], which is not mentioned and compared in this paper.\n\nBased on the above arguments, I would like to recommend a reject for this paper.\n\n\n[1] Xu, Keyulu, et al. \"Representation learning on graphs with jumping knowledge networks.\" arXiv preprint arXiv:1806.03536 (2018).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlhsq6d9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduced a novel parametrized graph operation called bipartite graph convolution (BGC). The proposed bipartite graph convolution layer functions as a regular graph convolution followed by a graph pooling layer, but it uses less memory. Also, the BGC layer can be used to aggregate multiple different graphs with various number of nodes. This paper further discussed the possibility of extending it to construct bipartite graph U-net structure with skip connections. Experimental evaluations have been focused on (1) comparing BGC against regular graph convolution layer followed by graph pooling layer in terms of classification accuracy and memory cost; and (2) comparing the regular graph-AE with the graph U-Net built on the proposed BGC layer with the unsupervised feature learning task.\n\nOverall, reviewer is very positive about the technical novelty of the paper. However, the experimental results seem not very strong. \n\n(1) The ECC model (Simonovsky and Komodakis, 2017) is no longer the state-of-the-art one on ModelNet. Please consider more recent papers such as the following one. Besides that, the performance delta seems very incremental.\n\n-- Dynamic Graph CNN for Learning on Point Clouds. Wang et al. In ACM Transactions on Graphics, 2019. \n\n(2) The current results are not very convincing as only one network structure is compared for each of the experiment. The ablation studies on graph structure (e.g., number of layers) are currently missing (Figure 4 and Table 1). \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1exCVyg9H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes BiGraphNet, which proposes to replace the graph convolution and pooling with a single bipartite graph convolution. Its motivation comes from using stride(>1) convolution to replace pooling in CNN. The authors claim that the computation and memory can be reduced with the proposed bipartite graph convolution, because the pooling layers are removed. The authors also conduct experiments about graph skip connection and graph encoder-decoder to show that their method's flexibility.\n\nCons:\n1. If I understand it correctly, the bipartite graph convolution still needs a cluster algorithm to determine the output graph, which is identical to cluster-based pooling methods like DiffPool. In addition, previous pooling methods like DiffPool, gPool are NOT non-parametric as suggested by Figure 1. Therefore, the advantage of the proposed method is vague.\n2. The idea of bipartite graph convolution seems different from that of stride convolution. The connection should be better explained.\n3. The experiments of this paper are not very convincing. Comparison with more baselines and ablation study are needed to demonstrate the effectiveness of this method. On graph classification tasks, many other methods (GCN with pooling) are worth comparing with, like DiffPool, SAGPool, gPool, etc. More datasets should be included. In addition, it will be more convincing to do ablation study, e.g. single layer replacement.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are consistently negative on this paper. Thus a reject is recommended.
Decision: Reject