Curvature Graph Network
Authors: Ze Ye
Kin Sum Liu
Tengfei Ma
Jie Gao
Chao Chen
Venue:  (2020)
Keywords: Deep Learning
Graph Convolution
Ricci Curvature.

Abstract: Graph-structured data is prevalent in many domains. Despite the widely celebrated success of deep neural networks, their power in graph-structured data is yet to be fully explored. We propose a novel network architecture that incorporates advanced graph structural features. In particular, we leverage discrete graph curvature, which measures how the neighborhoods of a pair of nodes are structurally related. The curvature of an edge (x, y) defines the distance taken to travel from neighbors of x to neighbors of y, compared with the length of edge (x, y). It is a much more descriptive feature compared to previously used features that only focus on node specific attributes or limited topological information such as degree. Our curvature graph convolution network outperforms state-of-the-art on various synthetic and real-world graphs, especially the larger and denser ones.

Published as a conference paper at ICLR 2020
CURVATURE GRAPH NETWORK
Ze Ye
Kin Sum Liu
Department of Biomedical Informatics Stony Brook University ze ge.yyesttonyrroo..cem
Department of Computer Science
Stony Brook University
kiliu0cs stonybrook, edu
Tengfei Ma IBM Research Al Tengfei. Ma @ bm. com
Jie Gao
Department of Computer Science Rutgers University ig 2uttrrrrrrrsss edu
Chao Chen
Department of Biomedical Informatics Stony Brook University
chao. chen. 8 @stonybrokk. edu
ABSTRACT
Graph-structured data prevalent in many domains. Despite the widely celebrated success of deep neural networks, their power in graph-structured data is yet to be fully explored. We propose novel network architecture that incorporates advanced graph structural information, specifically, discrete graph curvature, which measures how the neighborhoods of a pair of nodes are structurally related. The curvature of edge (x, y) is defined by comparing the distance taken to travel from neighbors of x to neighbors of y, with the length edge (r, y). a much more descriptive structural measure compared to previously ones that only focus on node specific attributes or limited graph topological information such as degree. Our curvature graph convolution network outperforms state-of-the-an methods various synthetic and real-world graphs, especially the large and dense ones.
INTRODUCTION
Despite the huge success of deep neural networks, it remains challenging fully exploit their power on graph-structured data, i.e., data whose underlying structure is captured by graphs, e.g., social networks, telecommunication networks, biological networks and brain connectomes. Inspired by the power of convolutional neural networks on image data, convolutional networks have been proposed for graph-structured data. Existing works can be roughly divided into two categories, depending on whether convolution is applied to the spectral or spatial domain.
Spectral approaches (Bruna al. 2013 Defferrard al. 2016 Henaff et al. 2015 Veličković et al. 2017) apply convolution to eigen-decome digen-decomposed graph Laplacians and are generally efficient in both computation and memory. However, the learned convolution filters are graph-specific and cannot generalize to different graphs.
Spatial approaches execute "convolution" directly on the graph and operate on the neighborhood as defined by the graph topology. A spatial method iteratively updates the representation of each graph node by aggregating representations from its neighbors, i.e., adjacent nodes (Xu et al.) 2018). Nonlinear transformations message. These transformations have the same input/output dimension, i.c., the dimension of the node representation. They be shared and learned across different nodes and even different graphs.
applied the representation passed from node to another, called
For spatial approaches, important to incorporate local structural information the graph. Node degree has been used to re-parametrize the non- lineir transformation of messages (Monti et al. 2017) or as an additional node feature (Hamilton et al. (017). However, node degree is fairly limited; there can be different graph topologies with the same degree distribution. The limitation is illustrated in

---

Published as a conference paper at ICLR 2020
y
X
y
(a) Tree: Kzy -0.5
(b) Grid: Kay -0
(c) Clique: Kay
0.625
Figure I: Illustration of structural information. In all three graphs, the degrees of x and y the same, However, the Ricci curvature of the edge (z, y) is negative, zero, and positive, respectively. All edges have weight 1. a 0.5 so each node keeps 50% of the probability mass to itself.
Figure Nodes and y have the same degree in three significantly different graphs: tree, grid and clique. To effectively make use of graph structural knowledge, one would need feature with more discriminative power; one that can distinguish these three scenarios Figure
In this paper, we propose a novel graph neural network that exploits advanced structural information. Notice that node degree only describes the number of neighbors of each node, but does not say how these neighbors are connected among themselves. We seek to use structural information characterizing how neighborhoods are well separated in different branches of tree. In grid graph, the two neighborhoods are within parallel shift of each other. In a clique, they completely overlap. To quantify such pairwise structural information, draw inspiration from recent study of graph curvature (Ollivier) 2009 Lin et al.
pair of nodes relate to each other. Figure []] the neighborhoods
and
2011 Weber et al. 2016).
Similar to curvature in the continuous domain, c.g., the Ricci curvature of a Riemannian manifold, the discrete graph curvature measures how the geometry of a pair of neighborhoods deviates from a "flat" case, namely, the case of a grid graph. There several definitions of discrete curvature for graphs. The most notable one is Ollivier's Ricci curvature (Ollivier 2009).. The edges of an infinite grid graph have zero curvature. The curvature of edge tree negative and is positive in complete graph. Intuitively, the graph curvature measures how well two neighborhoods are connected and/or overlap with each other. Such information related to how information propagates in the neighborhood, and should be leveraged by graph convolutional network.
We propose Curvature Graph Network (CurvGN), the first graph convolutional network built on advanced graph curvature information. The use of curvature information allows CurvGN to adapt to different local structural scenarios and filter messages passed between nodes differently. Notice that curvature captures how easily information flows between two nodes. Within well-connected com- munity, neighborhoods of adjacent nodes have large overlap and many shortcuts. The corresponding curvature is positive and passing information between the nodes is easy. For edge serving bridge of two clusters, its curvature is negative and is hard for information to pass. The key to our success is that the messages in graph convolution. We exploit the curvature information in a data-driven manner and learn how to use it to reweigh different channels of the messages.
choose to be agnostic whether eurvature should be used to block accelerate
To further investigate how curvature information affects graph convolution, we carried out extensive experiments with various synthetic graphs and real-world graphs. Our synthetic graphs generated according to various well-established graph models, e.g., stochastic block model (Decelle et al. 2011)
StrogaStrogatz network (Watts Strogatz 1998). Newman- Watts network (Newman & Watts 1999) and Kleinberg's 's navigable small world graph (Kleinberg) 2000). On these data, CurvGN outperforms vanilla graph network and networks using node degree information and self attention, demonstrating the benefit of curvature information in graph convolution. Such benefit is more apparent as the graph size increases. We hypothesize that graph convolution alone can adapt to any graph topology, at the cost of more convolutional layers and more training data. This is corroborated by our experiments on real-world graphs. CurvGN outperforms state-of of-the-art graph neural networks, especially on large and dense graphs, which tend to have large variation of local structures. The success of CurvGN demonstrates how topological intuitions inspire better practical solutions. It encourages us to continue the endeavor in applying theoretical insights in successful deployments of deep learning.
2

---

Published as a conference paper at ICLR 2020
2 RELATED WORK
We briefly summarize previous works on graph convolution. In early works (Frasconi et al. 1998;
Sperduti & Starita 1997), recursive neural networks were applied on data whose underlying structures are directed acyclic graphs. In Graph Neural Networks (GNNs) (Gori et al. 2005 Scarselli et al. 2009), the recursive network framework was extended to general graphs. Li al. (2015) introduced gated recurrent units into the framework in order to improve the performance. Since Convolutional Neural Networks (CNNs) have demonstrated strong performance in grid-like-structured data, various
methods have been proposed to implement "convolution" on graph-structured data. The efforts can be roughly divided into spectral approaches and spatial approaches. Below we will review both categories in details.
Spectral approach. [Bruna al. (2013) transformed the graph convolution into spectral domain multiplication by graph Fourier transform. This method is expensive due to the need to perform matrix gggen-decomposition.. Furthermore, it cannot create spatially localized filters as in CNNs. Henaff et al. (2015) applied smooth coefficients on spectral filters make them spatially localized. Defferrard et al. (2016) used Chebyshev expansion of the graph Laplacian to approximate the filters as a k-polynomial function. Kippf & Welling (2016) simplified those methods by reducing to degree one polynomials. Their method is to essentially filter the graph with a kernel whose receptive field is the one-hop neighborhood of each node. The common limitation of spectral approaches is that the convolution filters depend on the Laplacian of each specific graph.
Spatial approach. The main challenge of spatial approaches is to design an operator which applies to neighborhoods with different topology and still maintains shared filters. [Monti et al. (2017)
introduced mixture model CNN (MoNet) that maps graph neighborhood into spatial neighborhood
(with pseudo-coordinates) for spatial convolution. Hammilon et al. (2017) proposed GraphS AGE that samples fixed size neighbors and aggregates their representations. Veličković et al. (2017) proposed Graph Attention Network (GAT), which uses self-attention mechanism to reweigh graph convolution. Recently, there have been other methods which studied graph neural networks from different perspectives, such as pooling (Gao & Ji. 2019 Ying et al.) 2018).
Discrete graph curvature. Different proposals for discrete graph curvature have been introduced in recent years, including Ollivier-Ricci curvature (Ollivier [2099] Lin et al. 2011) and Forman curvature (Forman) 2003). We focus on Ollivier-Ricii curvature as it is more geometric in nature, while Forman curvature (Forman) 2003) is combinatorial and is faster to compute. Both curvatures have been applied to real-world graphs Ni et al. (2015) showed that Ollivier-Rice curvature can be used to identify backbone edges of an Internet AS graph and is closely related to network vulnerability, Similar applications are shown in the characterization of complex biological networks (Sandhu et al. 2015). There are also applications of Ollivier- Ollivier-Ricci curvature in network alignment (Ni al. (0188) and community detection (Ni et al.) 2019 Sia et al.) 2019). Forman curvature is shown to have similar effect (Weber al. 2017 2016). To the best of our knowledge, graph curvature has not been used in graph neural networks.
3 CURVATURE GRAPH NETWORK
We first formulate the node label prediction problem and explain the mechanism of a Graph Neural Network (GNN). Suppose we have an undirected graph G (V, E) with features on the vertices H = (h1, fu2................. ... ), h4 E IR Here n = [V] is the number of nodes in the graph and F is the feature dimension of each node. Given labels of some nodes in V, we would like to predict the labels of the remaining nodes. A GNN iteratively updates the graph G's node representation and eventually predicts node labels. GNN consists of multiple hidden layers that update node representation from a lower level node representation H' E R where F feature dimension at the t-th layer to a higher level representation 11++1 E p*+1 In particular, H is the input feature Hl and F² = F. The last node representation, H², are fed fully connected layer or linear classifier to predict node labels. The layers and node representations are illustrated in the top of Figure
Now we explain how to construct hidden layers that update node representations from H' to H*+1 We focus on spatial approaches and treat convolution as message passing scheme. The (t + 1)-th representation of node x is computed by aggregating messages passed from x's neighbors. We also include the message from x to itself. There are several aggregation methods, such as mean, max and sum. We choose summation as it is a commonly used aggregation method (Kipf & Welling 2016
3

---

Published as a conference paper at ICLR 2020
62
A
M
Lineart Lo
Lolkyy
Linearto
Son tmmaagrs
Thp or Kg
Figure 2: An overview of our Curvature Graph Network. The top row represents the iterative feature update function H' implemented by consecutive non-lineat layers. The bottom row represents the computation of reweighting parameter Ty from the edge curvature information.
Veličković et al.
2017 Xu et al. 2018). Denote by N(x) N(xx) U {x} the neighborhood of
including itself. We have h-+1 az (vET(()) Mt Mi in which og is non-linear transformation. message passed from y to x: linear transformation y's representation. We also introduce weight Ty whose purpose will be clear later. Formally, we have M - Tzy W in which W is the linear transformation matrix learned through training. Formally, we have the updating equation
++1 = oe
Tay Thy W
(3.1)
It is crucial to obtain suitable reweighting parameter Th since is directly affecting how information from neighbors of node x passed z. Some papers use node degree information as Thy (Kipf Welling 2016, Monti et al. (207)) and other work uses joint node features to compute self attention as Tay /Veličkovi et al. 2017). We propose to use more advanced structural information, i.c., the Ricci curvature, to compute T It is also known that the reweighting parameter T is not necessarily a scalar. can be anything between a scalar and F++1, x pt+1 matrix. Empirically, we choose Tf as vector in the experiments because vector has expressive power than scalar and is easier to train than a matrix.
To develop the curvature convolution layer in Equation 3..
define discrete Ricci curvature in the context of general graph in Section 3.1 We explain how to compute Tzy from the curvature in Section 3.2
3.1 RICCI CURVATURE
In Riemannian geometry, curvature measures how a smooth object deviates from being flat, or being straight in the case of a line. Similar concepts can be extended to a non-smooth setting for discrete objects. In particular, eurvature has been studied for metric-measure space (Bonciocal 2014
Bonciocat & Sturm 2009 Lott & Villani 2009 Sturm et al. 2006), Markov chain (Ollivier 2009) and general graphs Ollivier 2009; Lin et al. 2011). There are number of possibilities define discrete curvature for an edge in a graph. For example, the Gaussian curvature for a triangulated surface could defined s.t. curvature of a vertex is (or π) minus the sum of corner angles (the angles of the triangles) at it. if it is interior (or boundary) vertex. The definitions of curvatures easier to generalize in discrete and general graph setting are sectional curvature and Ricci curvature.
Curvature computation. For point on the surface, considers two tangent vectors and Wa- Let y be the end point of the tangent vector U at æ. Imagine transporting in parallel w₂ along v to a tangent vector Wy at y. If the surface is flat, any pair of points z' and y' which is away from and along W and wy will have the same distance as z and y. Its deviation from |o| defines the sectional curvature. Then averaging it over all directions of uz gives the Ricci curvature which only depends
4

---

Published as a conference paper at ICLR 2020
on the tangent vector Intuitively, instead of Was can think of S₂ be the set of end points of all tangent vectors at z with length c. Again, if we map Sg to Sy using parallel transport along v, the distance between point at Sr and its corresponding image at Sy can be different from |u] if the surface is not flat.
To generalize Ricci curvature discrete spaces, Ollivier (2009) takes coarse approach and repre- sents Sg as a probability measure m, of total mass I around σ. Thus the distance can be measured by Wasserstein distance (or Earth Mover distance) which finds the optimal mass-preserving trans- portation plan between two probability measures. Then the coarse Ricci curvature Kay on edge (z. y) is defined by comparing the Wasserstein distance W (m,. my) to the distance d(x, y), formally, Kzy = 1 - W (mz, my) /d(r,))))
The natural analogy of small ball S2 at point æ in the metric space is the I-hop neighborhood N N(x) of node r in graph. This motivates the Ollivier-Rice curvature on graph edges. For an undirected graph G = (V. E), denote the set of neighboring nodes of a node x E V as N(x) {xi, (2,,,2,... ] Then we can define a probability measure m² at x::
if
(xx) = (1 a)/k if ((x)
otherwise
where a is a parameter within [0. 1]. It to keep probability mass of at node x itself and distribute the rest uniformly over the neighborhood. We set 0.5, similar to (Ni et al. 20188). To compute the Wasserstein distance W (m,. mg) between the probability measures around two end points x, of the edge (z,, y). the optimal transportation plan can be solved by the following linear programming:
min Σ d(zi, U;) (zi, 4j) s.t. Σ M ( v,) m2 (zx), Vi; Σ (1s, vy) = (1,)), Vj (3.2)
where (2,, 83) is the amount of probability mass transported from node I; to y/ along the shortest path with length d( y5). In the language of graph theory, if the Ollivier-Ricct curvature is negative (W (mg, æ, m3) > d(x, y)), the edge (z. y) serves as the bridge connecting the neighborhood around and y. This aligns with the intuition in the smooth setting where the small balls S2 and Sy are closer to each other than their centers.
3.2
CURVATURE-DEA -RIVIURE-DRIVEN GRAPH CONVOLUTION
Next we present how Ricei curvature used in our graph convolutional network. Intuitively, curvature measures how easily message flows through an edge, and could be used to guide message passing in convolution. But its usage should really depend on the problem and data. We choose to be agnostic on how the knowledge of edge curvature should be used. We resort to data-driven strategy and learn a mapping function that maps Ricci curvature Kzy to the weight of messages, i.e., Tzy in Equation (3.1. We first explain how the mapping is learned end-to-end (CurvGN-1). Next we expand the mapping to a multi-valued version, to incorporate more flexibility in the model (CurvGN-n).
CurvGN-1. As mentioned before, Thy can be anything between scalar and F++1 x F++ matrix. We first assume Th is scalar. Then the mapping function can be defined as:
f : Kay
Tay
(3.3)
We create a multi-layer perceptron (MLP) to approximate the mapping function I since MLP is proved to be universal approximation machine and can be easily incorporated into our GNN model for end-to-end training. Denote the MLP at the f-th layer as MLP'. As summation is used as the aggregation function in Equation (3.1). the messages may accumulate an arbitrarily large value. To prevent a numerical explosion, we apply a softmax function, St, to MLP' MKzy of all neighbors of x including itself, E (xr) nodes.
by = S'MPP' (Kzy))
(3.4)
Figure shows how MLP transforms curvature to reweigh messages.
CurvGN-n. Messages M are usually multi multi-channeled. In particular, they are F++ -dimensional. The scalar weight generated using curvature is not necessarily the same for different channels. To
5

---

Published as a conference paper at ICLR 2020
improve the expressing power of myy. we create similar mapping function f in Equation (3. but
it generates reweighting vector Tzy E R instead. In other words, we learn to reweigh different message channels differently. In principle, we can even learn a matrix of dimension R x F*+ to reweigh the message. However, vector has significantly fewer parameters to train and is found to be sufficient in practice.
Using the same strategy as CurvGN-L, 1, the vector Ty is calculated by applying a MLP' with F++1 outputs. Then, we apply a channel-wise softmax function, st, that normalizes the MLP outputs separately on each message channel: Tay S S' (MLP((Ka))
Substituting Tay into Equation (3.)) we have the convolution of CurvGN-n:
1 = ot (E (
(3.5)
where diag(Tzy) is a matrix whose diagonal entries are entries of Tzy. For the details of MLP', please refer Appendix A.
3.3 DESIGN DETAILS OF THE NETWORK
In practice, we use wwo-convolutional-lyye CurvGN model. The first layer is linear transform layer that produces an output feature vector paired with a three layer MLP that computes reweighting vector. The output feature is pushed into an exponential linear unit layer to add non-linearity. The second layer is for classification, with the same structure as the first layer except that the output feature now length of class number. The hyperparameters are similar GAT implemented in Veličkovid et al. (2177). For synthetic experiments, the hidden layer output is reduced to 8 dimensions.
EXPERIMENTS
We have evaluated our method for both synthetic and real-world graphs. Our method outperforms the state-of-the-art methods. especially on large and dense graphs, which tend have heterogeneous topological structures. To demonstrate the prediction power, we use different graph theoretical models in synthetic experiments and different parameter settings to gain insights of how curvature information helps graph convolution. We focus on node classification tasks, while our method easily generalizes to graph classification tasks.
4.1 GRAPH THEORETICAL MODELS
We generate synthetic data using different graph theoretical models. We start with the Stochastic Block Model (SBM) (Holland et al. 1983), which assumes a partition of the graph into communities. We create random graphs, each with 1000 nodes and equally partition the node set into five disjoint communities. Nodes in the same community have the same class label. Edges are randomly sampled with an intrancommunity probability, p. for nodes within the same community and with an inter- community probability, q, for nodes in different communities. We randomly create 100 graphs with ranging in {0.05, 0.07. 0.23) } and ranging in (0.0, 0.005, ... 0.045). For each generated graph, randomly select 400 nodes the training set, another 400 nodes as the validation set and the remaining 200 nodes as the test set. We assign each node with randomly generated feature of dimension 10 and use them as uninformative input of our CurvGN.
Baselines. We compared our proposed methods, CurvGN-1 and CurvGN-n, with two popular state-of-the-art methods: GCN Kippf & Welling 2016) and GAT (Veličković et al. (017)). For these methods, we use the same setting as for Cora dataset mentioned in (Veličković et al. 2017 Kipf & Welling 2016), except that the dimension of the hidden layer We also included baseline method which aggregates messages without reweighting, namely, Vanilla GN. Compared with Vanilla GN, GCN reweighs messages using node degrees. GAT reweighs messages using self attention map computed using node representations. CurvGN-1 and CurvGN-n reweigh messages using the scalar and vector forms computed from Ollivier-Rice curvature.
We ran all methods on 100 random graphs. For each graph, ran the training and inference task 10 times and took average accuracy. For each training. we run 200 epochs and use validation set for early sshws stopping. Figure 3 shows the heat maps for all methods. The title of each heatmap includes the max
and average performance over all parameter settings. In Figure 3 c). we run the same experiments on graphs with different sizes and report the average accuracy.

---

Published as a conference paper at ICLR 2020
(a).GCN: max:0.36 mean:0.25
(b).GAT: max:0.35 mean:0.23
Mean accuracy of maps
(c).Mean accuracy curves
0.05
CurvGN-1
0.35
Inta-Coomuniay
0.1
0.3
0.15
0.2
0.2
0.25
Nodes number per graphın
(d). Vanilla GN: max:0.40 mean:0.28
CurvGNi:: max:0.47 mean:0.31
(f).CurvGN-n: max:0.54 mean:0.36
0.05
Intra Communityy p
0.15
0.2
0.25
0.2
0.02 Inter Community: q
0.04
Inter Community:
Inter Community:
Figure 3: Heat maps on synthetic data by SBM. The top-right figure the performance of Vanilla GN, CurvGN-1 and CurvGN-n over different graph sizes.
Discussion. From the heatmaps, we observe that Vanilla GN, GCN and GAT are not better than random guessing. This implies node degree information not enough. Meanwhile, observe improved performance by CurvGN-1, confirming the power of reweighting with curvature in graph convolution. In addition, CurvGN-n outperforms Cur,GN-L, suggesting that the multi-channel reweighting based curvature is beneficial. Furthermore, in Figure Be),, we observe that the benefit of curvature increases as the graph size increases. We hypothesize that the graph convolution is sufficient in small graph setting to fully explore the graph structure and advanced structural information becomes important on graphs large in size and rich in structural diversity.
We also visualize the prediction results on one particular graph generated at (p.g) (0.21,0. 0.025) Figure We observe that CurvGN-1 and CurvGN-n make high quality predictions except for small portion of data in few communities. Mcanwhile, other baselines can completely mix different communitics and results are unsatisfactory.
(a). Ground Truth
(b).GCN
(c).GAT
(d) Vanilla GN
(e). CurvGN-1
(f) CurvGN-N
Figure 4: One SBM result with (p.4) = (0.21, 0.025). Small nodes are training set. Large nodes are testing set. Colors correspond to the predicted node labels.

---

Published as a conference paper at ICLR 2020
Further studies on different graph theoretic models. To further examine the expressive power of Ricci curvature, we run synthetic experiments using several well-accepted graph theoretical models: Watts model (Watts & Strogatz 1998), Newman- Watts model (Newman & Watts 1999) and Kleinberg's 's navigable small world graphs [Kleinberg 2000). A Watts-Strogatz network randomly rewires edges of a ring graph. A Newman- Watts network randomly adds new edges the ring. The Kleinberg's ss model also adds random edges, but the probability of a new edge is inversely proportional to the shortest path distance on the ring. In all these settings, we partition the ring into different communities and design experiments similar to the Stochastic Block Model. More details can be found in the Appendix A..
We compared all five methods on these different graph models and report the average accuracy over different parameter settings in Table The standard deviations on these results are generally large as we are averaging over different parameter settings. We observe consistently better performance of CurvGN-n than other methods. This confirms that curvature information is beneficial in broad spectrum of graphs. We also note that GCN and GAT are indeed doing well for Watts-Strogatz and Newman- Watts models. This is because, in these networks, edge rewiring and addition enlarge differences in node degrees. Bridges crossing different communities tend to have higher node degree. Therefore, node degrees carry useful structural information and can help with graph convolution. We do not observe the same benefit of node degree information in SBM and Kleinberg's model in these models, node degree is not correlated with the locations of bridges. More heatmap results can be found in the Appendix A.2
Newman-Watts
Table I: Average prediction accuracy four different graph models.
Method
SBM
Watts-Strogatz
Newman-Watt Watts
Kleinberg
GCN
24%
32%
32%
23%
GAT
23%
30%
30%
22%
Vanilla GN
28%
26%
27%
28%
CuryGN-1 CurvGN-n 36%
31%
29%
29%
27%
32%
33%
31%
4.2 REAL- WEALDW BENCHMARKS
Our real-world benchmarks include two families of datasets: small sparse graphs and large dense graphs. We compare our networks CurvGN-1 and CurvGN-n with several strong baselines. Besides GCN and GAT that have been used in the experiments on synthetic data, we also compared CurvGN-1 and CurvGN-n with multilayer perceptron (MLP). MoNet (Monti et al. (017)) WSCN (Morris et al., 2019) and GraphSAGE with mean aggregation (GS-mean) (Hamilton al. 2017)) Our method is on par with state-of satt--of-the-aze the-art methods on relatively small graphs and greatly outperforms state-of-the-an methods on large and dense graphs, which tend to have heterogeneous graph topology.
Datasets. We use three popular citation network benchmark datasets: Cora, citetseer and PubMed (Sen et al. 2008). We categorize Cora and citetseer into the first family since both Cora and citetseer graphs are relatively small and sparse. They have thousands of nodes and edges with an average node degree below 2. We also use four extra datasets: Coauthor CS and Coauthor Physics which are co-authorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 challenge; Amazon Computers and Amazon Photos which are segments of the Amazon co-purchase graph in McAuley et al. 2015). These graphs, together with PubMed, are large and dense graphs. Those graphs have more than 10 thousands node and 200 thousands edges with an average node degree as high as 20. We use the exact data splitting as in
learning setting used in Kipf & Welling (2016); Veličković et al. al. (2017): using 20 nodes per class for training, 500 nodes for validation and 1000 nodes for testing. The descriptions and statistics for all datasets our experiments can be found in the Appendix A.3
During the training stage, we set L2 regularization with À = 0.0005 for all datasets. Also, all the models are initialized by Glorot initialization and trained by minimizing cross-entropy loss using Adam SGD optimizer with learning rate 0.005. We apply early stopping strategy based on the validation set's ' accuracy with a patience of 100 epochs. We compute curvature exactly following Eq. (.2) for all datasets but one. For the Amazon Computer dataset, we approximation scheme
8

---

Published as a conference paper at ICLR 2020
for computational efficiency (Ni al. 2018). The linear programming problem is solved using interior point solver (ECOS).
We report the mean and standard deviation of classification accuracy test nodes 100 runs and re-use the metrics reported by Monti ct al. (0177; Shohur et al. (2018); Veličković et al. (2017) for other mate-of-ther of-the-art methods. The results reported in Table Our method is on par with state-of-ther methods for relatively small graphs and achieves superior performance on large and dense graphs. This is consistent with our conclusion from synthetic experiments: when the graph large and has heterogeneous topology, advanced structural information becomes critical in graph convolution.
Table 2: Performance on real-world benchmarks.
Method
Cora
CiteSeer
PubMed
Coauthor CS
Coauthor Physics
Amazon Computer
Amazon
Photo
MLP
58.2
59.1
70.012.11
88.310.7
88.911.1
44.911..8
69.613.8
MoNet
81.7
71.2
78.612.3
90.810.6
92.5=0.9
83.512.2
91.2+11.3
GS-mean
79.2
71.2
77.4:22.2
91.312.8
93.010.8
82.411.8
91,4111.
WSCN
78.910..
67.410.8
78.110..6
89.110.77
90.710.9
67.613.7
82.111.2
GCN
81.5110.5
70.910.5
79.011.33
91.1100.5
92.811.0
82.61224
91.211:22
GAT
83.0.10.7
72.510.7
79.0
90.510..6
92.510.9
78.0119.0
85.11:20.3
CuryGN-1 82.6.10.6
71.510.8
78.8.0.66
92,910.4
94.110..3
86,310.77
92.510055
CurvGN-n 82.710.7
72.1
79.2.10.5
92.8100.3
94.310.2
86.5100.7
92.5
5 CONCLUSION
We introduce a novel graph convolution network to leverage advanced graph structural information, namely, the graph curvature. The curvature information effectively helps to achieve superior per- formance on synthetic and real-world datasets, especially on large and dense graphs. This shows how principled mathematics and theory help the deployment of deep learning and encourages to continue the endeavor in bridging the gap between graph theoretical foundation and neural networks.
Acknowledgement. Liu and Gao would like to acknowledge supports from NSF CNS- 16199,, DMS-1737812, OAC-1939459, Ye and Chen's research was partially supported by NSF IIS- 1909089,, IIS-1855759, CCF-1855760.
REFERENCES
Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In Advances in Neural Information Processing Systems, pp. 1964-1974, 2017.
Anca-luliana Bonciocat. A rough curvature-dimension condition for metric measure spaces. Open Mathematics, 12(2)362-380, 2014.
Anca-luliana Bonciocat and Karl-Theodor Sturm. Mass transportation and rough curvature bounds for discrete spaces. Journal Functional Analysis, 256(9):2944-2966 2009.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 2013.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in
neural information processing systems, pp. 2292-2300, 2013.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):0661 06, 2011.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852 2016.

---

Published as a conference paper at ICLR 2020
Robin Forman. Bochner's method for cell complexes and combinatorial ricci curvature. Discrete and Computational Geometry, 29(3):323-3744 2003.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. IEEE transactions Neural Networks, 9()):68- 786, 1998.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In International Conference Machine Learning. pp. 2083-2092, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume pp. 729-734, IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. pp. 1024-1034, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv: 2015.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels; First steps. Social networks, 5(2): 109-137, 1983.
Thomas Kipf and Max Welling. Semi- sumi-supereieed classification with graph convolutional networks. arXiv preprint (rXi::660000200) 2016.
Jon M Kleinberg, Navigation in small world. Nature, 406(6798):845, 2000.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks, arXiv preprint arXiv:1571.05493 2015.
Yong Lin, Linyuan Lu, and Shing-Tung Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, 63(4))605-66 627, 2011.
John Lott and Cédric Villani. Ricci curvature for metric-measure spaces via optimal transport. Annals of Mathematics, pp. 903-991, 2009.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- recommendations styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 43-52. ACM, 2015.
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 IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115-5124, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602 4609, 2019.
Mark EJ Newman and Duncan Watts. Renormalization group analysis of the small-world network model. Physics Letters A, 263(4-6):341-346 1999.
Chien-Chun Ni, Yu- Yao Lin, Jie Gao, Xianfeng David Gu, and Emil Saucan. Ricci curvature of the internet topology. 2015 IEEE Conference on Computer Communications (INFOCOM), pp. IEEE, 2015.
Chien-Chun Ni, Yu-Yao Lin, Jie Gao, and Xianfeng Gu. Network alignment by discrete ollivier-ricci flow. In International Symposium on Graph Drawing and Network Visualization, pp. 447-462. Springer, 2018.
Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao. Community detection networks with ricci flow. Scientific Reports, 9(9984), July 2019.
Yann Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, (6663):810-644 2009.
10

---

Published as a conference paper at ICLR 2020
Romeil Sandhu, Tryphon Georgiou, Ed Reznik, Liangjia Zhu, Ivan Kolesov, Yasin Senbabaoglu, and Allen Tannenbaum. Graph curvature for differentiating cancer networks. Scientific reports. 5(1): 1-13, 2015.
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, 2009.
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.
Olcksandr Shehur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 1.05668, 2018.
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-ricci curvature-based method commu- nity detection in complex networks. Scientific reports, 2011
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 83)::714-735, 1997.
Karl-Theodor Sturm et al. On the geometry of metric measure spaces. Acta mathematica, 196(1): 65-131, 2006.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world' (6684):440, 1998.
networks. 'smaal-wwrrdnneetorrss nature, 393
Melanie Weber, Jürgen Jost, and Emil Saucan. Forman-ricci flow for change detection large dynamic data sets. Axioms, 5(4):26, 2016.
Melanie Weber, Emil Saucan, and Jürgen Jost. Characterizing complex networks with forman-ricci curvature and associated geometric flows. Journal of Complex Networks, 5(4):527-550, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.000 000.000006..... 2018.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pp. 4800-4810, 2018

---

Published as a conference paper at ICLR 2020
A APPENDIX
A.1 THE DETAILS OF CURVATURE TRANSFORMATION
We describe the details of MLPP' for the 1-th convolutional layer, which maps the curvature Kizy of the edge to the weight vector Tzy E IRF"1 MLP" has three layers: an input layer, followed by a non-linear transformation layer and an output layer. The input layer In linearly transforms the Ricci curvature Key into an output vector with the same size as the message My E I We use LeakyReLU function in our non-linear layer. For output layer Out, we use a transformation matrix with size p++1, x F++1 to compute reweighing vector Tzy. Formally,
MLP' = -Out(Leaky
(A.1)
Recall node also passes message to itself. To generate the weight vector Thy we set Kgzz 0, as if the edge (æ,, .) is grid edge. For the case when we reweigh the message using single scalar Tay (e.g., CurvGN-1 network), we change the size of transformation matrix of output layer into Fi+1 x 1.
A.2 DIFFERENT NETWORK MODELS FOR SYNTHETIC EXPERIMENTS
All three models, Sttts-Stroogaz. Newman- Watts and Kleinberg's 's model, are created by randomly modifying/adding edges ring graph A ring graph has n nodes embedded on a circle, with each node connected to its l nearest neighbors. Figure Salis is an example ring graph with n = 20 and & = 4. To create communities, we partition the nodes into equal-size sets according to their locations on the circle. In addition, we remove the edges cross different communities. Next we explain how edges of the ring graph are randomly changed for Watts-Strogatz, Newman- Watts and Kleinberg's 's model, respectively.
Wttts-Strogatz Network. Watts-Strogatz Network (Watts & Strogatz 1998 is created by randomly rewiring edges of the ring graph with a predefined probability, p. See Figure 5b for example of Watts- Watts-Strogatz network.
In our experiments, we generate 100 random Watts- Satts-Strogatz graphs of size 1000 using different parameter combinations of and p. E (5, 10, ... 50} and p E {0.02, 0.04. ... 0.2]. For each nodes with different labels. We randomly generate
graph, the 5 communities correspond 10-dimensional feature for each node, as in Stochastic Block Model experiments. The training set is created by randomly sampling 400 nodes in one graph. The validation set and testing are create in the same way with size 400 and 200, respectively. For each graph, we run the experiment 10 times with 200 epochs each time and report the average.
Figure 6a shows the results of all five methods (GCN, GAT, Vanilla GN, CurvGN-1 and CurvGN-n). We observe that CurvGN-n has the best performance compared with others. suggests that edge curvature information is crucial in prediction: a rewired edge has a high probability to be a bridge with negative curvature. Curvature information can effectively distinguish bridges and cntra-community edges, and therefore help graph convolution. It is also worth mentioning that GCN also has good performance. We hypothesize that this is because rewired edges (likely bridges) tend to have higher degrees on adjacent nodes, and thus can be distinguished using degree information alone.
Newman- Newman-Watts Network. The Newman-Wart network (Newman & Watts 1999) is similar to the Watts-Strogann model except that it adds random edges the ring graph with probability p. instead of rewiring existing edges. We run the experiments in the same setting as Watts- Satts-Sttrogtz model. The results are shown in Figure 6b We observe similar effects as Watts-Strogatz model.
Kleinberg's Navigable Small World Graph. Instead of randomly generating edges with a fixed probability p. Kleinberg's model (Kleinberg) 2000) adds fixed number of additional long-range edges to the ring graph. For each node u, add e random edges (u, v) with v picked with a probability proportional to 1/d(u, v), in which d(u, v) is the distance between and in the circle." We slightly modify the original definition by making all edges undirected and removing self-loops. Figure [cc shows an example graph of Kleinberg's 's model with 100 nodes. We observe much fewer long range (cross-come cross-community) connections and more intra- antracoommunty connections than the other models.
Note these models can he huilt on any d-dimensional grid. Ring is a special case when d = 1. In general, the probability could be proportional to 1 1/d(u, w)"h. We choose m be 1.
12

---

Published as a conference paper at ICLR 2020
(a) example ring graph with n 20, t: 4.
(b) An example Watts-Strogatt graph with 100 nodes.
(c) An example Kleinberg's graph with 100 nodes.
Figure 5: Visualization of theoretical graph models
We generate 100 different graphs using different combinations of parameters and et. Here e, (floor(2.5), floor(5), ... floor(25)) controls the distance upperbound for short-range neighbors; any nodes within distance e, of is connected with is very similar to k in Wattz-Strogatz graph. Similar to previous models, we run experiments on each graph 10 times and use the validation set for early stopping.
Since the edge is added with a probability proportional to 1/d(u, v), there can be long distance inter- community edges. And the node degree can longer capture the structural information introduced by the added edges. The GCN behaves similar to random guessing in this case. However, the Ricci Curvature is still negative those inter community edges and it can still detect communities. Figure 6c shows the heatmaps of five different algorithms. CurvGN-n n outperforms other methods by large margin.
13

---

Published as conference paper at ICLR 2020
(a).GCN: max:0.43 meen:0.32
(b).GAT: max:0.41 mean:0.30
Vanilla GN: max:0.35 mean:0.24
Shartcul Probabiltty:
0.05
0.11
0.2
0.35
Shartouu Probabilyyy p
0.1
0.15
0.25
10
20
40
50
20
30
Nearest neighbor:
Nearest neighbor: k
(a) Heatmaps of Wttts-Strogatz Network
(a).GCN: max:0.45 mean:0.32
(b):GAT: max:0 40 mean:0.30
[c), Vanilla GN: max:0.33 mean:0.22 27
Shorlout Probabillyy,
0.05
0.1
0.15
0.2
(d). CurGG---: max0..4 mean:0 29
CurvGN-n: max:0.4 .44 mean:0.33
0.35
Shortoat Probabaliyy p
0.05
0.1
0.16
0.55
10
20
30
40
50
10
20
30
40
50
Nearest neighbort
Nearest neighbor k
(b) Heatmaps of Newman- Watts Network
(a):GCN: mak:0.20 mean:0.23
(b).GAT: max:0.30 mean:0.22 22
(a).Vanille GN: max:0.35 mean:0.28
10
Shartouls
30
50
Ju.CCrGGN-1 max0.33 mean:0.27 27
(e) CurvGN-n: max:0.39 mean:0.3 31
10
Shortculs
30
40
20 Neighbor distance: eg
Neighbor distance:
(c) Hcatmaps of Kleinberg's 's navigable small world graph
Figure 6: Results on different theoretical graph models.
14

---

Published as a conference paper at ICLR 2020
Table 3: Statistics of graph datasets including graph characteristies, training details and time for curvature computation. "*" indicates the usage of approximation method.
Cora
CiteSeer
PubMed
Coauthor
Coauthor Physics
Amazon Computer
Amazon Photo
CS
#Node
2708
3327
19717
18333
34493
13381
7487
#Edge
5429
4732
44338
100227
282455
259159
126530
#Edge/#NNode
2.0
1.42
2.25
5.47
8.19
19.37
16.90
#Class
15
5
#Feature
1433
3703
500
6805
8415
767
745
#Training
140
120
60
300
100
200
160
Curvature
Comp. Time(s)
2.38
2.04
28.8
49.5
215.2
1873.5*
1237.6
A.3
STATISTICAL DETAIL OF BENCHMARKS
We describe the statistical details of all datasets in Table Cora and Citeseer considered small and sparse graphs while PubMed, Coauthors and Amazons are considered as large and dense graphs.
A.4 COMPLEXITY OF CURVATURE COMPUTATION
Exactly calculating the curvatures is somewhat time-consuming. We need to solve linear program- ming (LP) problem for each edge. For edge (æ, y). the LP problem has dg x dy variables and de + dy linear constraints, in which dy and dy are the degrees of the nodes x and y. Take the interior point solver (ECOS) the complexity of matrix multiplication (the best known is 2.373).
example, the complexity is Odd,
) in which w is the exponent of
However, in practice, there many approximation methods to accelerate the computation of optimal transport distance, among which the best known is the Sinkhorn's 's algorithm (Cuturi 2013). It is known have near-linear time complexity (Altschuler al. 2017). So for small datasets we can keep using the ECOS to get exact solution while for large datasets (e.g. Computers) we may use advanced approximation methods. Table we show the computation time for the curvatures with two 18-core CPUs. Note that this computation is only needed once for data pre-processing, and the values can be reused in various downstream tasks.
A.5 NECESSITY OF CURVATURE TRANSFORMATION
The usage of multi-channel MLP is essential in the success of using the curvature information. To illustrate this, in Table we report the performance of our model we directly use the curvature to weigh messages, i.c., Tay Kay for all layers. We call this baseline CuryGN-K.
Table 4: Performance on real-world benchmarks using curvature Kay directly to weigh messages.
Method
Cora
CiteSeer
PubMed
Coauthor CS
Coauthor Physics
Amazon Computer
Amazon Photo
CurvGN-K 29.8
52.7
71.2
69.6
87.3
45.8
70.2
We observe that curvature alone cannot provide the best reweighing scheme for graph convolution. Only learning from the data helps us determine how weights on different channels should be dependent on K. We observe weights of different channels changing very differently w.r.t. Key' some increasing w.r.t. Kay, others decreasing. ML.P is necessary in learning such dependence from data. Using MLP enhances the model flexibility and model capacity. But also note that curvature Kzg is the essential input that the MLP relies on.
15


Reviews:
[{"review_id": "r1lIrpy6YS", "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": "In this paper, the authors proposed a novel graph neural network (GNN).\nThe proposed model combines discrete Ricci curvature of graph edge with GNN. \nThe combination method is simple but effective, which is easy to implement and is compatible with existing GNN models like GCN. \nExperimental results show the potentials of the proposed model to node classification. \n\nMy main concerns include:\n1. The complexity of the proposed model should be discussed. For a graph with V nodes and E edges, it seems that the authors need to solve E linear programming problems. The scale of each problem is decided by the number of neighbors per node. For large-scale graphs with dense connections, the scalability of the proposed method will be a problem. When the GCN models are with adaptive pooling layers, the curvature will change with respect to the layers of the model, and the scalability problem may become more serious. \n2. For the graphs with isolated nodes, do we need to calculate the curvature associated with such nodes? If yes, how to calculate?\n3. The authors introduce additional parameters to model the weight tau_{xy} from the curvature kappa_{xy}, i.e., Eq. (3.4). I wonder whether we can use kappa_{xy} directly as the weight tau_{xy} or not. It would be nice if the authors can add an experiment for this variant. \n\nOverall, I think the idea of the proposed method is interesting. Introducing Ricci curvature to GCN is a potential method to take advantage of structural information beyond the adjacency matrix. However, the complexity of the proposed method should be analyzed in-depth.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxet-ByqH", "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": "Curvature graph network\n\nThis paper proposes a novel network architecture “curvature graph network” that incorporates the Ricci curvature to fully utilize the graph structure. The Ricci curvature can measure the connectivity around an edge. The higher Ricci curvature, the denser connections there. This is very important information especially for extracting hidden clusters in the graph. The proposed curvature driven graph convolution network shows good experimental results on theoretical synthetic data sets and real world benchmark data sets. \n\nI recommend “weak accept” to this paper since this paper proposes an interesting concept and it looks promising.\n\nPros. \n\nThe authors introduce a very useful metric “Ricci curvature” \n\nCurvGN-1 and CurvGN-2 outperforms existing graph convolution algorithms.\n\nCons.\n\nTo run the proposed algorithm, we have to compute the Ricci curvature values for all edges. This can increase the inference time significantly. The authors should discuss the inference time and check it with a proper experiment.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJl3FmwTtS", "reviewer": "AnonReviewer3", "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": "The work presents a graph neural network that incorporates graph curvature.  The proposed model is able to explore the neighborhood structure of each node, by using the curvature of edges in the proposed framework. Extensive experimental results show the efficacy of the proposed framework. I am not familiar with graph curvature. All I can say is the approach is intuitively appealing, the text is well written and easy to follow, even for an outsider. However, I do not know any related works or what to expect from the results. I could not find anything wrong with this paper, but also do not have any intelligent questions to ask.\n", "extra_scores": {"experience_assessment": "I do not know much about 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": {}}]

Author rebuttal:

Meta-review: The paper presents a novel graph convolutional network by integrating the curvature information (based on the concept of Ricci curvature). The key idea is well motivated and the paper is clearly written. Experimental results show that the proposed curvature graph network methods outperform existing graph convolution algorithms. One potential limitation is the computational cost of computing the Ricci curvature, which is discussed in the appendix. Overall, the concept of using curvature in graph convolutional networks seems like a novel and promising idea, and I also recommend acceptance.
Decision: Accept (Poster)