Geom-GCN: Geometric Graph Convolutional Networks
Authors: Hongbin Pei
Bingzhe Wei
Kevin Chen-Chuan Chang
Yu Lei
Bo Yang
Venue:  (2020)
Keywords: Deep Learning
Graph Convolutional Network
Network Geometry

Abstract: Message-passing neural networks (MPNNs) have been successfully applied in a wide variety of applications in the real world. However, two fundamental weaknesses of MPNNs' aggregators limit their ability to represent graph-structured data: losing the structural information of nodes in neighborhoods and lacking the ability to capture long-range dependencies in disassortative graphs. Few studies have noticed the weaknesses from different perspectives. From the observations on classical neural network and network geometry, we propose a novel geometric aggregation scheme for graph neural networks to overcome the two weaknesses.  The behind basic idea is the aggregation on a graph can benefit from a continuous space underlying the graph. The proposed aggregation scheme is permutation-invariant and consists of three modules, node embedding, structural neighborhood, and bi-level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom-GCN, to perform transductive learning on graphs. Experimental results show the proposed Geom-GCN achieved state-of-the-art performance on a wide range of open datasets of graphs.

Published as a conference paper at ICLR 2020
GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS
Hongbin Pei geihb150mar 1s. edu.cnd
Bingzhe Wei
bwei 601 1 noiis .ediisseds
Kevin Chen-Chuan Chang 2.3
Yu Lei
Bo Yang 1,5,1 @do on
kcchang@i wiw.oiiiiiiiiiiii...iimimmiiiiii edu
csylei@comp. polyu, edu. hk
1 "College of Computer Science and Technology, Jilin University, China
2 *Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign. USA
3 DDepartment of Computer Science. University of Illinois at Urbana- Urbana-Champann Champaign, USA
"Department of Computing, Hong Kong Polytechnic University, Hong Kong 6 Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, China
ABSTRACT
dlessage-passingg neural networks (MPNNs) have been successfully applied representation learning on graphs in a variety of real-world applications. However, two fundamental weaknesses of MPNNs' aggregators limit their ability to repre- sent graph-structurre data: losing the structural information of nodes in neigh- borhoods and lacking the ability to capture long-range dependencies in disassor- tative graphs. Few studies have noticed the weaknesses from different perspec- tives. From the observations on classical neural network and network geometry, we propose novel geometric aggregation scheme for graph neural networks overcome the two weaknesses. The behind basic idea is the aggregation on a graph benefit from continuous space underlying the graph. The proposed aggregation scheme is permutation-invariant and consists of three modules, node embedding, structural neighborhood, and bi-level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom- GCN, to perform transductive learning on graphs. Experimental results show the proposed Geom-Go GCCN achieved state-of-the ohette-arttt performance on a wide range of open datasets graphs.
INTRODUCTION
beessag--passing neural networks (MPNNs), such GNN (Scarselli al., 2008), ChebNet (Deffer- rard et al., 2016), GG-NN (Li al., 2016), GCN (Kipf & Welling, 2017), are powerful for learning on graphs with various applications ranging from brain networks to online social network (Gilmer et al., 2017: Wang et al., 2019). In a layer of MPNNs, each node sends its feature representation, a "message", to the nodes in its neighborhood; and then updates its feature representation by aggregat- ing all "messages" received from the neighborhood. The neighborhood is often defined as the set of adjacent nodes in graph. By adopting permutation-invant maximum, and mean), MPNNs are able to learn representations which are invariant to isomorphic graphs, i.e., graphs that are topologically identical.
aggregation functions (e.g., summation,
Although existing MPNNs have been successfully applied in a wide variety of scenarios, two fun- damental weaknesses of MPNNs' aggregators limit their ability to represent graph-structured data. Firstly, the aggregators lose the structural information of nodes in neighborhoods. Permutation in- variance an essential requirement for any graph learning method. To meet it, existing MPNNs adopt permutation sermutaaion-invariant aggregation functions which treat all "messages" from neighborhood as
"Tii work is conducted partially during his visit at University of Illinois at Urbana- Cabana-Champaign. Corresponding author.

---

Published as a conference paper at ICLR 2020
set. For instance, GCN simply sums the normalized "messages" from all one-hop neighbors (Kipf & Welling, 2017). Such aggregation loses the structural information of nodes in neighborhood be- cause it does not distinguish the "messages" from different nodes. Therefore, after such aggregation, we cannot know which node contributes what to the final aggregated output.
Without modeling such structural information, as shown in (Kondor et al., 2018) and (Xu et al., 2019), the existing MPNNs cannot discriminate between certain non-isomorphic graphs. In those cases, MPNNS may map non-isomorphic graphs to the same feature representations, which is obvi- ously not desirable for graph representation learning. Unlike MPNNs, classical convolutional neural networks (CNNs) avoid this problem by using aggregators (i.e.. convolutional filters) with struc- tural receiving filed defined on grids, i.c., a Euclidean space, and are hence able to distinguish each input unit. As shown by our experiments, such structural information often contains clues regard- ing topology patterns in graph (e.g., hierarchy), and should be extracted and used to learn more discriminating representations for graph-structured data.
Secondly, the aggregators lack the ability to capture long-range dependencies in disassortative graphs. MPNNs, the neighborhood is defined as the set of all neighbors one hop away (e.g.. GCN), or all neighbors up to hops away (e.g.. ChebNet). In other words, only messages from nearby nodes are aggregated. The MPNNs with such aggregation are inclined to learn similar repre- sentations for proximal nodes in graph. This implies that they are probably desirable methods for assortative graphs (e.g., citation networks (Kipf& & Welling, 2017) and community networks (Chen et al., 2019)) where node homophily holds (i.e., similar nodes are more likely to be proximal, and vice versa), but may be inappropriate to the disassortative graphs (Newman, 2002) where node ho- mophily does not hold. For example, Ribeiro al. (2017) shows disassortative graphs where nodes of the same class exhibit high structural similarity but are far apart from each other. In such cases, the representation ability of MPNNs may be limited significantly, since they cannot capture the important features from distant but informative nodes.
A straightforward strategy to address this limitation is to use a multi-layered architecture so as to receive "messages" from distant nodes. For instance, due to the localized nature of convolutional filters in classical CNNs, a single convolutional layer is similarly limited in its representational ability. CNNs typically use multiple layers connected in a hierarchical manner to learn complex and global representations. However, unlike CNNs, it is difficult for multi-layer MPNNs to learn good representations for disassortative graphs because of two reasons. On one hand, relevant messages from distant nodes are mixed indistinguishably with a large number of irrelevant messages from proximal nodes in multi-layer MPNNs, which implies that the relevant information will be "washed out" and cannot be extracted effectively. On the other hand, the representations of different nodes would become very similar in multi-layer MPNNs, and every node's representation actually carries the information about the entire graph (Xu et al., 2018).
In this paper, we overcome the aforementioned weaknesses of graph neural networks starting from two basic observations: i) Classical neural networks effectively address the similar limitations thanks to the stationarity, locality, and compositionality The notion of network geometry bridges the gap between continuous space and graph (Hoff et al., 2002; Muscoloni et al., 2017). Network geometry aims to understand networks by revealing the latent continuous space underlying them, which assumes that nodes are sampled discretely from a latent continuous space and edges are established according to their distance. In the latent space, complicated topology patterns graphs can be preserved and presented as intuitive geometry, such as subgraph (Narayanan et al., 2016), community (Ni et al., 2019), and hierarchy (Nickel & Kiela, 2017: 2018). Inspired by those two observations, we raise an enlightening question about the aggre- gation scheme in graph neural network.
continuous space (Bronstein et al., 2017); ii)
Can the aggregation on a graph benefit from a continuous latent space, such as using geometry in the space to build structural neighborhoods and capture long-range dependencies in the graph?
To answer the above question, we propose a novel aggregation scheme for graph neural networks, termed the geometric aggregation scheme. In the scheme, we map a graph to continuous latent space via node embedding, and then use the geometric relationships defined in the latent space to build structural neighborhoods for aggregation. Also, design bi-level aggregator operating on the structural neighborhoods to update the feature representations of nodes in graph neural networks, which are able to guarantee permutation invariance for graph-structured data. Compared with exist-
2

---

Published as a conference paper at ICLR 2020
ing MPNNN, the scheme extracts structural information of the graph and can aggregate feature representations from distant nodes via mapping them to neighborhoods defined in the latent space.
We then present an implementation of the geometric aggregation scheme in graph convolutional net- works, which we call Geom-GCN to perform transductive learning, node classification, on graphs. We design particular geometric relationships build the structural neighborhood in Euclidean and hyperbolic embedding space respectively. We choose different embedding methods to map the graph suitable latent space for different applications, where suitable topology patterns of graph are pre- served. Finally, we empirically validate and analyze Geom-GCN on wide range of open datasets of graphs, and Geom Bonn achieved the state-of-the-ass results.
In summary, the contribution of this paper is three-fold: i) We propose novel geometric aggregation scheme for graph neural network, which operates in both graph and latent space, overcome the aforementioned two weaknesses; ii) We present an implementation of the scheme, Geom-GCN for transductive learning graph; iii) We validate and analyze Geom-GCN via extensive comparisons with oftte-o methods on several challenging benchmarks.
2 GEOMETRIC AGGREGATION SCHEME
In this section, we start by presenting the geometric aggregation scheme, and then outline its ad- vantages and limitations compared to existing works. As shown in Fig. the aggregation scheme consists of three modules, node embedding (panel A1 and A2), structural neighborhood (panel B and B2), and bi-level aggregation (panel C). We will elaborate on them in the following.
A1
Original graph
B2 Structural neighborhood
Bi-level aggregation
(N,(o), T
A2
Latent space
B1
Local latent space
0.6
0.40
0.6
in
0.37
0.2
Low aggregation
Virtual
0.3
High level aggregaatio
0.2 0.1
0.6
0.8
0.007
The original graph is mapped to a latent continuous space. B1-B2 The structural neighborhood. All adjacent nodes lie in a small region around center node in B1 for visualization. In B2, the neighborhood in the graph contains all adjacent nodes in graph; the neighborhood in the latent space contains the nodes within the dashed circle whose radius is p. The relational operator т is illustrated by a colorful unit is corresponding to geometric relationship to the red target node. C Bi-level aggregation on the structural neighborhood. Dashed and solid arrows denote the low-level and high-level aggregation, respectively. Blue and green arrows denote the aggregation the neighborhood in the graph and the latent space, respectively.
Figure 1: An illustration of the geometric aggregation scheme. A1-A2
3 grid where each
A. Node embedding. This is a fundamental module which maps the nodes in a graph to latent continuous space. Let G = (V, F) a graph, where each node V has a feature vector a and each edge E E connects two nodes. Let graph to a representation vector. Here, 2, R2d can also be considered as the position of node v in a latent continuous space, and d is the number of dimensions of the space. During the mapping, the structure and properties of graph are preserved and presented as the geometry in the latent space. For instance, hierarchical pattern in graph is presented as the distance to the original in embedding hyperbolic space (Nickel & Kiela, 2017). One can employ various embedding methods to infer the latent space (Cai et al., 2018; Wang et al., 2018).
- Z be mapping function from a node in
3

---

Published as a conference paper at ICLR 2020
B. Structural neighborhood. Based the graph and the latent space, we then build structural neighborhood, (V()) ((() = (o), N. (.)), for the next aggregation. The structural neighborhood consists of set of neighborhood {N, (v)), and relational operator neighborhoods т.
The neighborhood in the graph, (b)()) = {u u E V, v) E E}, is the set of adjacent nodes of v.
The neighborhood in the latent space, (v) {ulu E V, V,d(zu=*t z.) < p), is the set of nodes from which the distance to v is less than a pre-given parameter p. The distance function d(.,.) depends on the particular metric in the space. Compared with (v),), NN(u) may contain nodes which are far from v in the graph, but have a certain similarity with v, and hence are mapped together with y in the latent space though preserving the similarity. By aggregating on such neighborhood (v),, the long-range dependencies in disassortative graphs can be captured.
The relational operator is a function defined in the latent space. inputs an ordered position pair (ze, zu) of nodes v and u, and outputs discrete variable which indicates the geometric relationship from to in the latent space. For u, v E V.
T: (Z z.) +re R,
where R is the set of the geometric relationships. According the particular latent space and application, r can be specified as an arbitrary geometric relationship of interest. A requirement on that it should guarantee that each ordered position pair has only one geometric relationship. For example, r is illustrated in Fig. 1B by colorful 3 x 3 grid in 2-dimensional Euclidean space, in which each unit is corresponding to a geometric relationship to node e.
C. Bi-level aggregation. With the structural neighborhood ((v), we propose a novel bi-level ag- gregation scheme for graph neural network to update the hidden features of nodes. The bi-level aggregation consists of two aggregation functions and operates in neural network layer. It can ex- tract effectively structural information of nodes in neighborhoods as well as guarantee permutation invariance for graph. Let h' be the hidden features of node v at the (-th layer, and hg x, be the node features. The [-th layer updates h' for every V E V by the following.
r.1+1 p( (hi Ni(1), T(u,; zw) r)), Vi E (r, R (Low-level aggregation)
((r))
ml+1- = q ic(g.))rER
((e())) (i,r)))
(High-level aggregation) (1)
h+t = -WW
(Non-linear transform)
In the low-level, the hidden features of nodes that are in the same neighborhood and have the same geometric relationship are aggregated to virtual node via the aggregation function p. The features of the virtual node are (k,r) 1. and the virtual node indexed by (i.r) which is corresponding the combination of neighborhood and relationship r. It is required adopt a permutation-invariii function for p. such as an Lp -n-no (the choice of p = 1, 2, or results in average, energy, max pooling). The low level aggregation illustrated by dashed arrows Fig. IC.
In the high-level, the features of virtual nodes are further aggregated by function q. The inputs of function q contain both the features of virtual nodes e.l+1 and the identity of virtual nodes ri. That is, q can be function that take an ordered object as imput, e.g., concatenation, to distinguish the
((ir))
features of different virtual nodes, thereby extracting the structural information in the neighborhoods explicitly. The output of high-level aggregation a vector !+1, Then new hidden features of v, 1.(+1)) are given by a mon-linear transform, wherein Wi is learnable weight matrix on the I-th layer shared by all nodes, and ((.) is non-linear activation function, e.g., ReLU.
Permutation invariance is an essential requirement for aggregators in graph neural networks. Thus, we then prove that the proposed bi-level aggregation, Eq. 1, is able to guarantee invariance for any permutation of nodes. We firstly give definition for ietpuuttttioiiivviiiii mapping of graph.
Let a bijective function 3a V V be a permutation for nodes, which renames W V as (w) E V. Let V' and F. be the node and edge set after a permutation t/, respectively. A mapping of graph, d(G), is permutation Crmmtaatoo-invariantt if, given any permutation v. have o(G) (6g') ), G (V', E.).
Definition
Lemma 1. For a composite function o, o (9)) if (2(9) is ionmuutaiio-imaaiian the entire composite function Φ1 (22l) is permutation-invariont
4

---

Published as a conference paper at ICLR 2020
Proof. Let G' be isomorphic graph of G after a permutation s, as defined in Definition 1. If (9) is permutation invarrinn,, we have d2(G) (g ). Therefore, the entire composite function Φ1 (2())) is permutation-invarian because Φ1 o x2( - Φ1 o (g')
Theorem 1. Given graph G EV) and its structural neighborhood (/(iioood((()))))))))))))) (c)), Vu e V. the bi-level aggregation, Eq. 1, is a cntrmuutatio-invaiiinn mapping of graph.
Proof. The bi-level aggregation, Eq. 1, is composite function, where the low-level aggregation is the input of the high-level aggregation. Thus, Eq. is permutation-invarii if the low-level aggregation is permutation-invann invariian according to Lemma 1.
We then prove that the low-level aggregation is permutationninvariann, The low-level aggregation consists of f2x R| sub-aggregations, each of which is corresponding to the nodes in neighborhood i and with a relationship r to v. Firstly, the input of each sub-aggregations is permutation-invarian be- cause both i {g. s} and E R are determined by the given structural neighborhood (())., Ve E V, which is constant for any permutation. Secondly, Eq. I adopts a permutation-invarian aggregation function p for the sub-aggregations. Thus the low-level aggregation is permutation-invaritt
2.1 COMPARISONS TO RELATED WORK
We now discuss how the proposed geometric aggregation scheme overcomes the two aforementioned weaknesses, i.e., how it effectively models the structural information and captures the long-range dependencies, in comparison to some closely related works.
To overcome the first weakness of MPNNs, i.e., losing the structural information of nodes in neigh- borhoods, the proposed scheme explicitly models the structural information by exploiting the ge- ometric relationship between nodes in latent space and then extracting the information effectively by using the bi-level aggregations. In contrast, several existing works attempt to learn some im- plicit structure-like information to distinguish different neighbors when aggregating features. For example, GAT (Velickovic et al., 2017), LGCL (Gao et al., 2018) and GG-NN (Li et al., 2016) learn weights on "messages" from different neighbors by using attention mechanisms and node and/or edge attributes. CCN (Kondor et al., 2018) utilizes covariance architecture to learn structure- aware representations. The major difference between these works and ours is that we offer an explicit and interpretable way to model the structural information of nodes in neighborhood, with the assistance of the geometry thus can be readily incorporated to further improve their performance. In particular, we exploit geo- metric relationships from the aspect of graph topology, while other methods focus on that of feature representation- the two aspects are complementary.
latent space. We note that our work is orthogonal with existing methods and
For the second weakness of MPNNs, i.e., lacking the ability to capture long-range dependencies, the proposed scheme models the rong-range dependencies in disassortative graphs in two different ways. First of all, the distant (but similar) nodes in the graph can be mapped into a latent-space- based neighborhood of the target node, and then their useful feature representations can be used for aggregations. This way depends on an appropriate embedding method, which is able to preserve the similarities between the distant nodes and the target node. On the other hand, the structural information enables the method to distinguish different nodes in a graph-based neighborhood (as mentioned above). The informative nodes may have some special geometric relationships to the target node (e.g., particular angle or distance), whose relevant features hence will be passed to the target node with much higher weights, compared to the uninformative nodes. As a result, the long-range dependencies are captured indirectly through the whole message propagation process in all graph-based neighborhoods. In literature, a recent method JK-Nets (Xu et al., 2018) captures the range dependencies by skipping connections during feature aggregations.
2.1.1 CASE STUDY ON DISTINGUISHING NON-ISOMORPIIC GRAPIIS
In literature, Kondor et al. (2018) and Xu et al. (2019) construct several non-isomorphic exam- ple graphs that cannot be distinguished by the aggregators (e.g., mean and maximum) in existing MPNNs. We present a case study to illustrate how to distinguish the non-isomorphic example graphs once the structural neighborhood is applied. We take two non-isomorphic graphs in (Xu et al., 2019) as an example, where each node has the same feature a and after any mapping f(a) remains the same across all nodes, shown in Fig. 2 (left). Then the aggregator, e.g., mean or maximum, over fa) remains f(a), and hence the final representations of the nodes are the same. That is, mean and maximum aggregators fail distinguish the two different graphs.
5

---

Published as a conference paper at ICLR 2020
6
Vs
Vi
VS
Vi
VS
F5
V/2
V4
Figure 2: An illustration distinguish non-isomorphic graphs by proposed structural neighborhood.
In contrast, the two graphs become distinguishable once we apply a structural neighborhood in aggregation. With the structural neighborhood, the nodes have different geometric relationships to the center node V1 in the structural neighborhood, as shown in Fig. 2 (right). Taking aggregation for Vi as an example, different geometric relationship r to V1- Then, the aggregator in two graph have different inputs, (f2(a), fs [a]} in the left graph and (f2(a), fr()), fa(a)] in the right graph. Finally, the aggregator (mean or maximum) will output different representations for the node V in the two graphs, thereby distinguishing the topological difference between the two graphs.
adopt different mapping function J,," E R the neighbors with
GEOM-GCN: AN IMPLEMENTATION OF THE SCHEME
In this section, we present Geom-GCN, specific implementation of the geometric aggregation scheme in graph convolutional networks, to perform transductive learning in graphs. To implement the general aggregation scheme, one needs to specify its three modules: node embedding, structural neighborhood, and bi-level aggregation function.
Node embedding the fundamental. As shown in our experiments, a common embedding method which only preserves the connection and distance pattern in a graph can already benefit the aggre- gation. For particular applications, one can specify embedding methods to create suitable latent spaces where particular topology patterns (e.g., hierarchy) preserved. We employ three embed- ding methods, Isomap (Tenenbaum et al., 2000), Poincare embedding (Nickel & Kiela, 2017). and struc2vec (Ribeiro al., 2017), which result in three Geom-GCN variants: Geom-GCN-I, Geom- GCN-P, and Geom-GCN-S. Isomap is a widely used isometry embedding method, by which distance patterns (lengths of shortest paths) are preserved explicitly in the latent space. Poincare embedding and struc2vec can create particular latent spaces that preserve hierarchies and local structures in graph, respectively. We use an embedding space of dimension 2 for ease of explanation.
The structural neighborhood N(v) ((Ng(e), (v)),, T) of node includes its neighborhoods in both the graph and latent space. The neighborhood-in ieoood-i--grrrr graph (v) consists of the of e's adjacent nodes in the graph, and the neighborhood -n-dd-ii--aaaa latellteet--ppe space N2(v)) those nodes whose distances to are less than a parameter in the latent space. We determine p by increasing p from zero until the average cardinality of N. equals to that of (v). Ve E V-i.e., when the average neighborhood sizes in the graph and latent spaces are the same. We use Euclidean distance in the Euclidean space. In the hyperbolic space, approximate the geodesic distance between two nodes via their Euclidean distance in the local tangent plane.
Here simply implement the geometric operator four relationships of the relative positions between two nodes in 2-D Euclidean or hyperbolic space. Particularly, the relationship set = (upper left, upper right, lower left, lower right). and a T(*,, 2,) is given by Table Note that, we adopt the rectangular coordinate system in the Euclidean space and angular coordinate in the hyperbolic space. By this way, the relationship "upper" indicates the node nearer the origin and thus lie in a higher level in hicrarchical graph. One can design a more sophisticated operator т, such borrowing the structure descriptors in manifold geometry (Kokkinos al., 2012: Monti et al., 2017), thereby preserving more and richer structural information in neighborhood.
Table 1: The relationship operator
T [Zz Z.) 2,
z [0] > 2g, upper left lower left
2. S x. 00]
2,
upper right
2,
2.
lower right

---

Published as a conference paper at ICLR 2020
Finally, to implement the bi-level aggregation, adopt the same summation of normalized hidden features as GCN (Kipf & Welling, 2017) as the aggregation function p in the low-level aggregation,
Σ 8(T(Zu: z.), r) (dde(v))dee)))) h. E Vr. R, (EN)(()
(1.7)
where deg(v) is the degree of node e in graph, and ((;-) is Kronecker delta function that only 2.t+1
allows the nodes with relationship r to e to be included. The features of all virtual nodes (f.r) are further aggregated in the high-level aggregation. The aggregation function q is a concatenation for all layers except the final layer, which uses mean for its aggregation function. Then, the overall bi-level aggregation of Geom-GCN is given by
h 4+1 oW
(ir)
(E(g,)
PER
where we use ReLU as the non-linear activation function (--) mate by backpropagation.
and Wi is the weight matrix to esti-
4 EXPERIMENTS
We validate Geom-GCN by comparing Geom-GCN's performance with the performance of Graph Convolutional Networks (GCN) (Kipf & Welling (2017)) and Graph Attention Networks (GAT) (Velickovic al. (2017)). Two state-of-the-an graph neural networks, transductive node-label classification tasks on a wide variety of open graph datasets.
4.1 DATASETS
We utilize nine open graph datasets to validate the proposed Geom GCN. An overview summary of characteristics of the datasets is given in Table 2.
Table Datasets statistics
Dataset
Cora
Cite.
Pubm.
Cham.
Squi.
Actor
Corn.
Texa.
Wisc.
# Nodes
2708
3327
19717
2277
5201
7600
183
183
251
# Edges
5429
4732
44338
36101
217073
33544
295
309
499
# Features
1433
3703
500
2325
2089
931
1703
1703
1703
Classes
7
5
5
5
Citation networks. Cora, Citeseer, and Pubmed are standard citation network benchmark datasets (Sen al., 2008: Namata et al., 2012). In these networks, nodes represent papers, and edges denote citations of one paper by another. Node features are the hag-of-words representation of papers, and node label the academic topic of paper.
WebKB. WebKB is a webpage dataset collected from computer science departments of various universities by Carnegie Mellon University. We use the three subdatasets of it, Cornell, Texas, and Wisconsin, where nodes represent web pages, and edges are hyperlinks between them. Node features are bag-of-words representation of web pages. The web pages are manually classified into the five categories, student, project, course, staff, and faculty.
Actor co-occurrence network. This dataset is the actor-only induced subgraph of the film-director- actor-writer network (Tang al., 2009). Each nodes correspond to actor, and the edge between two nodes denotes co-occurrence on the same Wikipedia page. Node features correspond to some keywords in the Wikipedia pages. We classify the nodes into five categories in term of words of actor's Wikipedia.
Wikipedia network. Chameleon and squirrel are page-page networks specific topics in Wikipedia (Rozemberczki et al., 2019). In those datasets, nodes represent web pages and edges are mutual links between pages. And node features correspond several informative nouns in the Wikipedia pages. We classify the nodes into five categories in term of the number of the average monthly traffic of the web page.
http::/ http:://wwr www.. cmu cmv. edu/afs
cmu. https//c..ccc.eeceeeeoeee/eaaa www.mmmmm..pooojjeeeeeeee... 11 1/www/wwke
7

---

Published as a conference paper at ICLR 2020
4.2 EXPERIMENTAL SETUP
As mentioned in Section 3, we construct three Geom-GCN variants by using three embedding meth- ods, Isomap (Geom-GCN-a Poincare the dimension of embedding space as two, and use the relationship operator т defined in Table 1, and apply mean and concatenation as the low- and high- level aggregation function, respectively.
and struc2vec GGeom-GCN-S We specify
With the structural neighborhood, we perform a hapee--arrmetter search for all models on validation set. For fairness, the size of search space for each method is the same. The searching hyper- parameters include number of hidden unit, initial learning rate, weight decay, and dropout. We fix the number of layer to 2 and use Adam optimizer (Kingma & Ba, 2014) for all models. We use ReLU the activation function for Geom-GCN and GCN, and ELU for GAT.
The final hyper parameter setting is dropout of p = 0.5, initial learning rate of 0.05, patience of 100 epochs, weight decay of 5E-6 (WebKB datasets) or 5E-5 (the other all datasets). In GCN, the number of hidden unit is 16 (Cora), 16 (Citeseer), 64 (Pubmed), 32 (WebKB), 48 (Wikipedia), and 32 (Actor). In Geom-GCN the number of hidden unit is 8 times as many the number in GCN since Geom-GCN has 8 virtual nodes. For each attention head in GAT, the number of hidden unit is 8 (Citation networks), 32 (WebKB), 48 (Wikipedia), and 32 (Actor). GAT has 8 attention heads in layer one and 8 (Pubmed) or 1 (the all other datasets) attention heads in layer two.
For all graph datasets, we randomly split nodes of each class into 60%. 20%, and 20% for training, validation and testing. With the models on the test sets over random splits.
parameter setting, we report the average performance of all
4.3 RESULTS AND ANALYSIS
Results are summarized in Table 3. The reported numbers denote the mean classification accuracy in percent. In general, Geom-GCN achieves state-of-the-art performance. The best performing method is highlighted. From the results, Isomap embedding (Geom-GCN-I) which only preserves the connection and distance pattern in graph can already benefit the aggregation. We can also specify an embedding method create a suitable latent space for particular application (e.g., disassortative graph or hierarchical graph), by doing which a significant performance improvement is achieved (e.g., --o--GCN-P).
Table 3: Mean Classification Accuracy (Percent)
Dataset
Cora
Cite.
Pubm.
Cham.
Squi.
Actor
Corn.
Texa.
Wisc.
GCN GAT
85.77
73.68
88.13
28. 18
23.96
26.86
52.70
52.16
45.88
86.37
74.32
87.62
42.93
30.03
28.45
54.32
58.38
49.41
Geom-GCN-I
85.19
77.99
90.05
60.31
33.32
29.09
56.76
57.58
58.24
Geom-GCN-P 84.93
75.14
88.09
60.90
38.14
31.63
60.81
67.57
64.12
Geom-GCN-S 85.27
74.71
84.75
59.96
36.24
30.30
55.68
59.73
56.67
4.3.1 ABLATION STUDY ON CONTRIBUTIONS FROM TWO NEIGHBORHOODS
The proposed Geom-GCN aggregates "message" from two neighborhoods which are defined in graph and latent space respectively. In this section, we present an ablation study to evaluate the contribution from each neighborhood though constructing new Geom-GCN variants with only one neighborhood. For the variants with only neighborhood in graph, we use "g" as suffix of their name (e.g., Geom-GCN-I-g), and use suffix "s" denote the variants with only neighborhood in latent space (e.g., Geom-GCN GCN-I-s). Here we set GCN as a baseline so that the contribution can be measured via the performance improvement comparing with GCN. The results are summarized in Table 4, where positive improvement is denoted by an up arrow and negative improvement by down arrow 4. The best performing method highlighted.
We also design an index denoted by 3 to measure the homophily in graph,
Number of e's neighbors who have the same label Number e's neighbors
DEV
A large B value implies that the homophily, in term of node label, is strong in graph, i.e., similar nodes tend to connect together. From Table 4, one can see that assortative graphs (c.g., citation networks) have much larger /3 than disassortative graphs (e.g., WebKB networks).
8

---

Published as a conference paper at ICLR 2020
Table 4 exhibits three interesting patterns: i) Neighborhoods in graph and latent space both benefit the aggregation in most cases; ii) Neighborhoods in latent space have larger contributions in dis- assortative graphs (with small () than assortative ones, which implies relevant information from disconnected nodes is captured effectively by the neighborhoods prise, several variants with only one neighborhood (in Table 4) achieve better performances than the variants with two neighborhoods (in Tabel 3). We think the reason is that Geom-GCN with two neighborhoods aggregate more irrelevant "messages" than Geom-GCN with only one neighbor- hood, and the irrelevant "messages" adversely affect the performance. Thus, we believe an attention mechanism can alleviate this issue- which we will study as future work.
latent space; iii) To our sur-
Table 4: Mean Classification Accuracy (Percent)
Dataset
Cora
Cite.
Pumb.
Cham.
Squi. 0.22
Actor 0.24
Corn. 0.11
Texa. 0.06
Wisc.
B
0.83
0.71
0.79
0.25
0.16
86.26
80.64
90.72
68.00
46.01
31.96
65.40
72.51
68.23
Geom-GCN-L-g
10.48
16.96
12.59
139.82
122.05
14.04
112.70
121.35
122.35
77.34
72.22
85,02
61.64
37.98
30.59
62.16
60.54
64.90
Geom-GCN-I-s
J8.34
41.46
J3.11
133.46
114.02
12.67
19.46
18.38
119.01
86.30
75.45
88.40
63.07
38.41
31.55
64.05
73.05
69.41
Geom-GCN-P-g
10.52
11.76
10.27
134.89
114.45
13.63
11.35
121.89
123.53
73.14
71.65
86.95
43.20
30.47
34.59
75.40
73.51
80.39
Geom-GCN-P4
412.63
J2.04
11.18
115.02
16.51
16.67
122.70
121.35
134.51
87.00
75.73
88.44
67.04
44.92
31.27
67.02
71.62
69.41
Geom-GCN-S-g
11.23
12.04
10.31
138.86
120.96
13.35
14.32
19.46
123.52
66.92
66.03
79.41
49.21
31.27
30.32
62.43
63.24
64.51
Geom-GCN-S-s
418.85
47.65
J8.72
121.03
17.31
12.40
19.73
111.08
118.3
4.3.2 ANALYSIS OF EMBEDDING SPACE COMBINATION
The structural neighborhood in Geom-GCN is very flexible, where one can combine arbitrary em- bedding space. To study which combination embedding spaces is desirable, we construct new Geom-GCN variants by adopting neighborhoods built by different embedding space. For the vari- ants adopted Isomap and poincare embedding space to build neighborhood in graph and in latent space respectively,
to denote it. The naming rule is the same for other com- binations. The performances all variants are summarized in Table One can observe that several combinations achieve better performance than Geom-GCN with neighborhoods built by only one embedding space (in Table 3); and there are also many combinations that have bad performance. Thus, we think it's significant future work to design an end-to-end framework that can automatically determine the right embedding spaces for Geom-GCN.
Table 5: Mean Classification Accuracy (Percent)
Dataset
Cora
Cite.
Pubm.
Cham.
Squi.
Actor
Corn.
Texa.
Wisc.
Geom-GCN-IP
85.13
79.41
90.49
65.77
45.49
31.94
60.00
66.49
62.75
Geom-GCN-PI
85.09
75.08
85.64
59.19
32.65
29.16
58.11
58.11
58.63
Geom-GCN GCN-IS
84.51
77.83
88.66
58.40
35.29
29.41
54.32
57.57
57.65
Geom-GCN-SS 85.31
75.50
85.52
62.13
32.57
28.97
57.30
60.00
55.10
Geom GRnn-GCNPPS
85.65
74.84
84.96
56.34
28.27
29.53
58.11
62.43
60.59
Geom- CCom-GCN-SP
85.43
75.71
88.00
65.81
44.53
31.16
58.38
67.84
65.10
4.3.3 ANALYSIS OF TIME COMPLEXITY
Time complexity is very important for graph neural networks because real-worke graphs always very large. In this subsection, we firstly present the theoretical time complexity of Geom-GCN and then compare the real running time of GCN, GAT, and Geom-GCN.
To update the representations of one node, the time complexity Geom Geom-GCN is O(n x m x 2) where n is the size of input representations, is the number of hidden unit in non-line non-linear transform

---

Published as a conference paper at ICLR 2020
for each virtual node (i.e.. (i,r)), and R| is the number of virtual nodes. Geom-GCN has 2| times complexity than GCN whose time complexity is O(n x m).
We also compare the real rumning time (500 epochs) of GCN, GAT, and Geom-GCN on all datasets with the syper-parametent described in Section 4.2. Results are shown in Fig. 3 (a). One can see that GCN is the fastest, and GAT and Geom-GCN are the same level. An important future work to develop accelerating technology so as to solve the scalability of Geom-GCN.
Running Time Comparison
Nunnigg twreel Spedts Secoral
10'
GAT
Geom-GCN
t0
10'
Texa.
Com.
Viseo
Cite
Cora
Actor
Pabm.
Chams.
Squs.
Figure 3: (a) Running time comparison. GCN, GAT, and Geom-GCN both run 500 epochs, and axis is the log seconds. GCN is the fastest, and GAT and Geom-GCN are the same level. (b) visualization for the feature representations
Cora obtained from Beom-GGN-P in a 2-D space. Node colors denote node labels. There two obvious patterns, nodes with the same label exhibit a spatial clustering and all nodes distribute radially. The radial pattern indicates graph's hierarchy learned by Poincare embedding.
4.3.4 VISUALIZATION
To study what patterns are learned in the feature representations of node by Geom-GCN, we vi- sualize the feature representations extracted by the last layer of Gcom-GCN-P on Cora dataset by mapping into 2-D space though t-SNE (Maaten & Hinton, 2008), as shown in Fig. (b). In the figure, the nodes with the same label exhibit spatial clustering, which could shows the discriminative power of Geom-GCN. That all nodes distribute radially in the figure indicates the proposed model learn graph's s hierarchy by Poincare embedding.
4.4 CONCLUSION AND FUTURE WORK
We tackle the two major weaknesses of existing message-passing neural networks over graphs- losses of discriminative structures and long-range dependencies. As our key insight, we bridge a discrete graph to continuous geometric space via graph embedding. That is, exploit the princi- ple of convolution: spatial aggregation over a meaningful space- and our approach thus extracts or "recovers" the lost information (discriminative structures and long-range dependencies) in em- bedding space from a graph. We proposed a general geometric aggregation scheme and instantiated with several specific Geom-GCN implementations, and our experiments validated clear advan- tages over the state-of-the-at As future work, we will explore techniques for choosing right embedding method- depending not only on input graphs but also on target applications, such as epidemic dynamic prediction on social contact network (Yang et al., 2017: Pei et al., 2018).
ACKNOWLEDGMENTS
We thank the reviewers for their valuable feedback. This work was supported in part by National Natural Science Foundation of China under grant 61876069, 61572226 and 61902 145, National Sci- ence Foundation IIS 16-19302 and IIS 16-33755, Jilin Province Key Scientific and Technological Research and Development project under grants 201 20180201067GX and 201 2018020104440 044GX, Univer- sity science and technology research plan project of Jilin Province under grants JJKH201901566 Zhejiang University ZJU Research 083650, Futurewei Technologies HF2017060011 and 094013, UIÚC OVCR CCIL Planning Grant 434S34, UIUC CSBS Small Grant 434C8U, Advanced Digital Sciences Center Faculty Grant, and China Scholarships Council under scholarship Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the funding agencies.
70202..
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. A comprchensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering, 106))1666-1667, 2018.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference Learning Representations (ICLR), 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems (NeurIPS), pp. 3844-3852, 2016.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1416-1424. ACM, 2018.
Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neu- ral message passing for quantum chemistry. In International Conference on Machine Learning (ICML). pp. 1663-1272, 2017.
Peter D Hoff, Adrian E Raftery, and Mark S Handcoek. Latent space approaches to social network analysis. Journal of the american Statistical association, 1794609)1090-1098, 2002.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412.6980, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
lasonas Kokkinos, Michael M Bronstein, Roee Litman, and Alex M Bronstein. Intrinsic shape context descriptors for deformable shapes. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 159-166. IEFE, 2012.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon M. Anderson, and Shubhendu Trivedi. Co- variant compositional networks for learning graphs. In International Conference on Learning Representations (ICLR), 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. 7emel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(Nov):2579-2600) 2008.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 5115-
5124, 2017.
Alessandro Muscoloni, Josephine Maria Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Vit- torio Cannistraci. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature communications, 8(1):1615, 2017.
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In International Workshop on Mining and Learning with Graphs, 2012.
Annamalai Narayaman, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Sam- inathan. subgraph2vec: Learning distributed representations of rooted sub- aab-graphs from large graphs. CoRR, abs/ 606.08928, 2016.

---

Published as a conference paper at ICLR 2020
Mark EJ Newman. Assortative mixing in networks. Physical review letters, 89(20):08871,, 2002. 2002.
Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific reports, 91))9994, 2019.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6338-6347, 2017.
Maximilian Nickel and Douwe Kiela. Learning continuous hierarchies the lorentz model of
hyperbolic geometry. In International Conference on Machine Learning (ICML), pp. 3776-3785, 2018.
Hongbin Pei, Bo Jiming Liu, and Lei Dong. Group sparse bayesian learning for active surveil- lance on epidemic dynamies. In Thirty-Second AAAI Conference on Artificial Intelligence, pp- 800-807, 2018.
Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 385-394, 2017.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. arXiv:1909.13021, 2019.
Multi-scale attributed node embedding.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93-93 2008
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 807-816. ACM, 2009.
Joshua Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(55000)2311-22233 2000.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710. 10903, 2017.
Hao Wang, Enhong Chen, Qi Liu, Tong Xu, Dongfang Du Wen Su, and Xiaopeng Zhang. A united approach learning sparse attributed network embedding. In IEEE International Conference Data Mining, pp. 237-566, 2018.
Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du Han Wu, and Wen Su. MCNE: end-to-end framework for learning multiple conditional network representations of social network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, pp. 1064-1072 1072, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML), pp. 5449-5458, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations (ICLR), 2019.
Bo Yang, Hongbin Pei, Hechang Chen, Jiming Liu, and Shang Xia. Characterizing and discovering spatiotemporal social contact patterns for healthcare, IEEE Trans. Pattern Anal. Mach. Intell., 39 15:1552-1546, 2017.
12


Reviews:
[{"review_id": "rkeT4UtIcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS \n\nThe paper introduces a novel GCN framework, whose purpose is to overcome weaknesses of existing GCN approaches, namely loss of structural neighbor information and failure to capture important dependencies between distant nodes. The paper uses a mapping from nodes to an embedded space and introduces a second type of a neighborhood: a proximity in the embedded space. In the embedded space, a set of relations of nodes is defined. For each node v, the paper uses a 2-stage convolution scheme: 1) for each neighborhood type, the nodes in the same relation with v are combined; 2) the resulting nodes are again combined into a new feature vector. This approach allows one to overcome the issues described above. The experiments show that in most cases the approach outperforms the existing GCN solutions, sometimes with a large gap.\n\nI have the following concerns about the paper:\n-- My main concern is the learning time, which is an issue for a straightforward GCN implementation. There were multiple attempts to decrease it (GraphSAGE, FastGCN, etc.). Therefore, I would like to see running times on the presented graphs as well as on relatively large graphs (see e.g. https://arxiv.org/pdf/1902.07153.pdf for candidates). If some techniques were used to make the implementation faster, I would be good to include them in the paper (or, if they are standard, they should be referenced). At the very least, I believe it should be prioritized as a future direction.\n-- It’s unclear why we should use the same latent space and the same τ for both N_g and N_s. I would expect that mapping into different spaces could provide better results: the two neighborhood types seem very different, and I don’t see why the neighbors should be aggregated in the same way. If using different spaces doesn’t provide an improvement, an explanation for this would be very useful.\n-- α and β are defined and shown in Table 2, but they are never used (as it stands now, α and β can simply be removed). If the results in Table 3 correlate with them, then this dependence should be highlighted. In such case, it would also be better to move α and β to Table 3.\n-- The paper uses 3 different node embedding strategies. These strategies can be combined in q with different weights (which can be learned as hyperparameters). Will it produce the best of 3 (or better) result?\n-- “We use an embedding space of dimension 2 for ease of explanation” But what τ is used in the real implementation?\n-- There are various GCN implementations; however, the comparison is performed with only 2 of them. I would like to see either comparison with more implementations, or the explanation why the comparison with the given two suffices.\n-- Is it possible to make the implementation available?\n\nWhile there are a lot of possible improvements, I believe that some of them can be addressed in a future research, and the paper’s novel approach is noteworthy in itself. My current verdict is 5/10, and I’ll be happy to improve it if the above issues are fixed.\n\nPresentation issues:\n-- The notation used in definition of m_v^l is unclear.\n-- Why τ is a part of each node’s structural neighborhood? It’s a global function, isn’t it?\n-- Introduction: I believe that the exact problems which GCNs solve (e.g. node classification) should be mentioned.\n-- The flow in Section 2.1 is a bit weird. Namely, it says “To overcome the first weakness”, but the first wickness wasn’t stated in the previous paragraph (of course, one can deduce it, and it also was defined long ago, but it’s disturbing for a reader).\n-- Figure 1B is confusing: it looks like the nodes from N_g(v) lie in a small region around v.\n-- I think that splitting Figure 1C into 2 figures would make it clearer.\n", "extra_scores": {"experience_assessment": "I have read many 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": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJgofPeTKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis work proposes geometric aggregation scheme for GCNs, which aims to overcome the limitations in traditional GCNs; those are lacking long distance dependencies and structure information in nodes. In particular, each node is transformed into a latent space. To overcome the first limitation, some nodes that are not directly connected but fall in a near range are also used in aggregation. A relational operator is used to provide position information for each pair of nodes. In this way, the structure information in graph can be used.\n\nThe method proposed in this work is novel and interesting. However, I am confused how this method can overcome the two limitations faced by previous GCNs. To my understanding, GEOM-GCN maps all node in to a 2D latent space. This can be treated as a lower-dimension representation for each node. Based on this, some similar nodes are clustered together. The relational operator is a kind of ranking operator that can rank two nodes based on latent space representations. If my understanding is wrong, please correct me.\n\nBased on this understanding, I didn't find this method can solve the two limitations.\n \n1. To overcome the long-term dependency limitation, GEOM-GCN selects some nodes that are close but not directly connected for aggregation. However, the selected nodes in this way may not connect to the center node. This is a issue that if two nodes that are not connected should be aggregated. The authors should clarify this.\n\n2. The relational operator is used to provide a ranking between two nodes. However, how such kind of operators can be used to aggregate the structure information as described in GIN. For example, how to distinguish those example graphs using this work. I think it would be a plus if authors can make this clear in the paper.\n\n3. The experimental studies are quite weak. Some ablation studies should be done to evaluate the contribution of each proposed methods. For example, how N_{s}(v) contributes to the performance. This is very important for fully evaluating your methods.\n\n4. More tasks and datasets can be added such as graph classification and social networks.\n\n5. Some notations are quite confusing. Like in eq.(1), why m is bold but W is not.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJluLVxXqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work is based on the premise that existing MPNNs have two main weaknesses: (i) the loss function doesn't properly capture the spatial information during graph convolution, and (ii) the difficulty to manage the information encoded in the long range connections.\n\nThe main contribution of this work is a novel method called geometric aggregation. The proposed method is based on two elements: (i) a latent space mapping to capture spatial information using a new bi-level operator, (ii) an integration of geometric aggregation inside GCN, namely geom-GCN. More in detail the idea reported in this work is to map the input graph into an embedding where the geometric relations between nodes are preserved. The graph is embedded using a usual embedding function that guarantees to preserve some graph property of interest like the hierarchy of nodes. After the node embedding, the authors propose to create a structural neighbourhood both (i) in the latent space, taking the nodes within an arbitrary radius, and (ii) in the original space, by taking the adjacent nodes. The expectation here is that with the proper embedding the latent space can catch connections, which are long range in the original space. The message passing is actuated exploiting first the structural neighbourhood to do low-level aggregation, which aggregates nodes that have the same geometric relationship using permutation invariant operators, and then the result of these aggregations, which are virtual nodes, are aggregated again through high-level aggregation making use of operators like concatenation.       \n\nThe goal of this work is clearly formulated by posing the proper research questions. The topic is relevant and it is part of the research agenda of ICLR. A key point of the proposed method is the ortogonalithy of geometric aggregation with respect to other aggregators like GAT. The design of the structural neighboorhood allows the network to choose which neighbors are the most important for the learning task.\n\nSome minor comments.\nThe strong dependency from the embedding fuction does not guarantee the discovery of long range connections. It may happen that the proposed embedding does not catch the relevant information for the task; in these cases the a-priori knowledge on the task becomes crucial. This potential issue is partially supported by the results presented in the mauscript, where there is a gain only when the correct embedding is chosen. \nA further critical point is the choice of the radius. Such a choice can be operated only with an empirical assessment. It is not clear whether it migth be meaningful to choose a radius thatwould encode the same neighbourhood as in the original sapce of data.\nThe authors claim that even if there are more hops between two nodes the relevant information would arrive from the far node to the target node. Nevertheless we may conceive a situation where the relevant information is washed out during the hops. It may happen when the information of the far node is relevant for the target node, but it is not relevant for the target neighbour nodes.\nThe use of concatenation as high level operator is critically dependent from the radius and from the number of edges in the graph. In cases of large values for radius or very dense graphs, the concatenation may increase the spatial complexity of the networks.\nConcerning the Section on empirical analysis, it might be of interest to investigate whether with a proper number of layers a GCN would emulate a geom-GCN.", "extra_scores": {"experience_assessment": "I have read many 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 did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is consistently supported by all three reviewers and thus an accept is recommended.
Decision: Accept (Spotlight)