Localized Curvature-based Combinatorial Subgraph Sampling for Large-scale Graphs
Authors: Dong Wook Shu
Youjin Kim
Junseok Kwon
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Combinatorial subgraph sampling
Ollivier-Ricci curvatures

Abstract: This paper introduces a subgraph sampling method based on curvature to train large-scale graphs via mini-batch training. Owing to the difficulty in sampling globally optimal subgraphs from large graphs, we sample the subgraphs to minimize the distributional metric with combinatorial sampling. In particular, we define a combinatorial metric that distributionally measures the similarity between an original graph and all possible node and edge combinations of the subgraphs. Further, we prove that the subgraphs sampled using the probability model proportional to the discrete Ricci curvature (i.e., Ollivier-Ricci curvatures) of the edges can minimize the proposed metric. Moreover, as accurate calculation of the curvature on a large graph is challenging, we propose to use a localized curvature considering only 3-cycles on the graph, suggesting that this is a sufficiently approximated curvature on a sparse graph. In addition, we show that the probability models of conventional sampling methods are related to coarsely approximated curvatures with no cycles, implying that the curvature is closely related to subgraph sampling. The experimental results confirm the feasibility of integrating the proposed curvature-based sampling method into existing graph neural networks to improve performance.

Localized Curvature-based Combinatorial Subgraph Sampling for Large-scale Graphs
Anonymous Author(s)
Affiliation
Address
email
Abstract
This paper introduces a subgraph sampling method based on curvature to train large-scale graphs via mini-batch training. Owing to the difficulty in sampling glob- ally optimal subgraphs from large graphs, we sample the subgraphs to minimize the distributional metric with combinatorial sampling. particular, define com- binatorial metric that distributionally measures the similarity between an original graph and all possible node and edge combinations of the subgraphs. Further, we prove that the subgraphs sampled using the probability model proportional the discrete Ricci curvature (i.e., Ollivier-Riie curvatures) of the edges can minimize the proposed metrie. Moreover, as accurate calculation graph is challenging, 3-cycles on the graph, suggesting that this is a sufficiently approximated curvature on sparse graph. addition, we show that the probability models of conventional sampling methods are related to coarsely approximated curvatures with no cycles, implying that the curvature is closely related to subgraph sampling. The experi- mental results confirm the feasibility of integrating the proposed curvature-based sampling method into existing graph neural networks to improve performance.
3
8
9
curvature on large propose to use localized curvature considering only
11
14
Introduction
17
Most graph data that represent real-worke information tend to be large scale, with many nodes and edges. However, the training of such large-scale graphs with finite computational resources is challenging, owing the rapid increase in complexity because of the expanding neighbors. Thus, large graph must be transformed into smaller subgraphs to facilitate the use of various graph neural 22 models, regardless of the size of the graph. However, inevitable eиrоrs are induced by unsampled nodes and edges when the original large-scale graph divided into independent subgraphs. In general, graph neural models aggregate neighbor node features along with graph structures. Because subgraphs 25 are composed of partial nodes and edges, they have sparse structures that aggregate only portion of the adjacent nodes.
this paper, we argue that informative subgraphs can made similar to original graph using only partial nodes and edges. Consequently, present distributional metric that measures the accuracy of subgraph when approximating the distribution defined in the original grapb. In addition, 30 we present a combinatorial distributional metric that measures the similarity (as an expected value) between all the subgraphs sampled from the probability model and the original graph. This allows 32 to recognize distributional differences using only sampling probability models, thus eliminating the need for actual subgraph samples.
Submitted 36th Conference Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

(Parameters Saving) The first approach involves reducing parameters of GNNs. In general, the accuracy of GNNs is not lincarly proportional to the size of parameters. Thus, in [39], the lincar 49 activated swallow GNN learned the feature space that approximates deep non-linear activated GNNs. In [11]. the parameters of the GNN model were parallelized. However, because these methods are 34 We find that sampling the edges with large curvatures is equivalent to reducing the proposed distribu- tional difference. Curvature is geometric property that represents the local structure of space. In 36 particular, the discrete Ricci curvature (Ollivier- Rievie curvature) can be defined in the graph structure. Thus, many studies have suggested that the structural information of graphs can be employed via the curvature. In context of these studies, we suggest that curvature can also be utilized for subgraph 39 sampling in the course of mini-batch training of large graphs. Consequently, through suitable experi- CaattureeLoCCur--baee subgraph sampling
ments, we demonstrate that the proposed Localized method improves the performance of various graphs and graph neural models.
2 Related Work
Graph neural networks (GNNs) have been proposed for learning useful information from graph 44 data. However, in the process of aggregating connected adjacent nodes, computational costs tend to increase rapidly with increase in the size of the graph. Thus, the following approaches are introduced to efficiently learn large-scale graphs.
51 based on specific models, they cannot be easily combined with various GNNs.
(Computation Saving) The second approach involves dynamic selection of the nodes to be con- 53 sidered for each layer. To realize this, the neighbor sampling method with historical activation was proposed [4], and the variance was reduced via neighbor sampling-based training. Further, the iid node importance sampling by Monte-Carlo approach was proposed to prevent recursive neighbor-
56 hood expansion [5]. These methods approximated the mini-batch gradients. In [17], the conditional probability model for each layer was learned, and the nodes computed in the next layer were sampled according to the probabilities. However, these methods are not model-free methods.
(Input Saving) The third approach involves sampling relatively small subgraphs inputs train networks. The subgraph sampling methods include graph coarsening, graph partitioning, and graph covering. For example, graphs were filtered through spectral coarsening [33, 9], and adaptive edge masks were used to drop connections [15]. However, these methods sampled the edges to render sparse graphs [43], wherein the number of nodes were not reduced but only edges were removed. In [18. 3], linked nodes were merged into a hyper node reduce the size of the subgraph. However, this method encountered difficulties in solving node classification problems, which needs to classify each 86 node. In contrast, the following method obtained a subgraph using only structure information without node features. These methods are applicable large graphs because they sample the subgraphs via combinatorial node and edge samplings. In [14], a subgraph was obtained by sampling the neighborhoods of the seed nodes. [45], subgraph sampling methods were proposed based on node degrees, edge weights, and random walks. In [7]. subset of clusters used as subgraph through
61
63
69
71 graph clustering. In [1], personalized page rank scores were used to sample nodes in a subgraph.
(Curvature on Graphs) The graph-structured data is a dependent object, in which nodes are 73 connected along edges. In addition, the curvature is defined based on structural information. The Ollivier-Ricci curvature was proposed [28] considering with the Markov chain and the I-Wasserstein transportation distance to compute the distance between 76 the probability measures. Another method of capturing the topological structure of the graph is presented [10] and compared in [3]]. The curvature on graphs has been studied in many applications such as finding communities [26], curvature attentive networks [42, 40, 38), over-squashing alleviation
sesloomwalk-bbasee probability measures
70 [36], preventing distortion of graph embedding [29], and generating graphs [23]. In previous studies, the results have shown the existence of a significant relationship between the curvature of the graph
81 and the informative geometric properties. In this paper, we present that curvature-bass input saving
82 approach helps to approximate the original graph to a sparse subgraph.

---

3 Metric for Combinatorial Subgraphs
83
84
Let g = (V,E) be a graph with the combinatorial structure of nodes V and edges E. We can sample 85 subgraphs (V, E) with sizes |6] < [V] from G. However, numerous subgraphs can be obtained from the graph G. Therefore, the criteria for determining good subgraphs must be defined according to the purpose of sampling. Please note that the subgraphs are sampled to train large-scale graph by dividing them into mini-batches { because training the large graph at once is difficult. Therefore, for unbiased training through mimi-batchhr the subgraphs should be sampled to be similar 60
to the original graph. In graph theory, the traditional metrics for the similarity between two different graphs can be defined in various manner.
(Conventional Metric) The graph edit distance (GED) is measure of matching two different graphs by calculating the editing cost to obtain one graph from another, i.e., dGED 9) = min (x Σ c(ex), where c(e.) denotes the cost of cach edit operation, including vertex insertion, vertex deletion, edge insertion, and edge deletion. (g 9) denotes the set of edit paths. A single path comprises several edit operations (c1, ez,... ex) used to modify ğ to match amother graph G. In contrast to the exact graph matching problem that solves graph isomorphism, the graph edit distance measures the similarity between two different graphs (i.e., error-tolerant graph matching). Thus, it calculates the minimum error in matching one graph to another. The lincar p-norm also be defined as d9 9) ||4 Al|e- where the A and Á denote the adjacency matrices of G and G. respectively. However, the GED measures the distance dGED(G, (9, 9) between the original graph and subgraph, only one edit path is obtained. This is similar to the addition of the cost of the number of nodes to the lincar distance, (9 9). Therefore, the metric GED and the lincar norm do not reflect the structure of the graph. In contrast, the spectral norm measures the norm of the eigenvalues, d' (G, 9) E || X However, it requires eigendecompossiton of the original graph and subgraph, the application of which to large graphs is challenging.
96
96
99
100
101
102
100
104
105
106
107
DDitributionall Metrie) To overcome the problems of conventional metrics, we define the distribu- tional metric, i.e., the distance between the probability measures defined on the unweighted graph. Let (V.d) d) be metric space on the connected graph, where d(xz, y) is the distance between the nodes and y. We define the probability measures for each node to represent the local structure around the nodes. Then, the metric (9, 9) between the original graph G and the subgraph ς is defined.
108
109
110
111
Definition 1 (Metric for Deterministic Subgraph) Let μ and P be probability measures for original 112
and sampled subgraphs, respectively. d(x, y) the distance of the geodesic path between nodes 114 x and y. and Híp, TT) denotes the set of all couplings between two measures, and J.. Then, the distance (9, 9) is defined as the distributional distance between and īt.
113
115
dm (m(9))
-inf
pEll((..) J..vevv d(x,y) ()(,,,))
(1)
116
Using Definition 1, we can represent the distance between the original graph and the deterministic subgraph. However, because various subgraphs can be obtained from one graph, we extend the metric presented in Definition I to the metric for nondeetemiiiistic subgraphs. as follows:
117
118
119
Definition 2 (Metric for Non-deterministic Subgraph) A subgraph can be considered as set of sampled nodes and edges derived from combinatorial sampling. Therefore, the distributional metric can be redefined as the combination of node-wise metrics or edge-wise metrics. Then, the probubility measure of the non-deterministic subgraph is represented as the expected value of node-wise measures. Exev p(=) where by is a probability measure for the node x. Here, Pa can be decomposed as edge wise measures along the edges, EveN( plylx)o where ply (z) is the probability that y is sampled to be connected to and 6, = =1y- We can define the combinatorial metric between the original graph and the probabilistic sampled subgraph, as the upper bound of 1.
120
121
122
123
124
125
126
d9, 9) Σ (m.)ddmGG. Gz) (G.
E((x) ZED
plul=)ddm(Gn (Gn, (Grn (EN(())
Σ
(2)
V

---

where metric (9, 9) is upperbounded by the weighted average distances between the local structural graph G.. and each node "/y. Although the weighted sum of distances for components is the upper bound, this method enables the determination of the better subgraph sampling model, using only probability models instead of actual subgraph samples. For example, a random edge sampler samples the subgraphs with an approximation of ΣrEy [ ΣyeN((x) (N(x)) " (Ga, Myy, because it
127
129
130
131
132
a uniform sampling. However, if a sampler has sampling probability model p(z)p(y(z)) x an (...))) that inversely proportional to the distributional difference of each edge. can considered better subgraph sampler because it more probable to obtain subgraphs that approximate the original graph.
133
Curvature-based Local Structural Approximation
135
Positively Curved Edges
Tp - dm (9, 9p) +
In dm (9, )n)
g
Negatively Curved Edges
Figure Curvature-based distributional difference. If the graph not in the form a regular grid, its edges have different distributional distances depending on the structure of the graph. Then, the subgraph S consisting of positively curved edges (blue) are more similar to the original graph than the subgraph Φn consisting of negatively curved edges (red).
We introduce the discrete Ricci curvature Kry in (4), which is defined the ratio of the distance of probability measures to the distance of nodes. We show that subgraph sampling that maximizes the curvature amounts to minimizing the distributional difference between the original graph and subgraph. Intuitively, dm is determined by the local structure around two nodes, because it can be defined as the cost of moving from adjacent nodes of one node to adjacent nodes of another node. Thus, subgraph sampling maximize the curvature enables local structural approximation because it minimizes the distribution metric between the original graph and the subgraph.
137
138
139
140
141
142
RilivvierRRicii Curvature) Let G (V,E) be graph with nodes V and edges E. ((x)) denotes adjacent nodes of node x E V and d is the degree of node æ. Assume that m, is the probability measure node æ by the random walk kernel m along Markov chain. Then, the metric measure space can be defined (V, d, m). The discrete probability measure m., for each node y is defined as follows.
148
144
145
147
(1(()) de (V(
d 0, d > 0.
(.)
(3)
With the probability measures mg: My for nodes ı, y E V of the graph, the transport plan between the two probabilities, mv))) and (V), is represented as the coupling measure y, where II myy) is the of measures projecting my to my. Distance d(x y) defined as the length the shortest path between nodes y for the 1-gcodesic distance. This is the optimal transport problem between sets of nodes A (z: and A (y). Then, the W-Wasserstein distance W1 is defined as the minimal cost for transportation between two measures, i.e., (m my)) yeI(m.,mm)
149
150
152
153
inf J Su,evvy d(u, v)dy(u v)).
154
there is at least one path for nodes x, y, we can define the Ollivier-Ricci curvature Kay of the edge (I, y) in the metric measure space (V, d, m), follows:
155
Wi Wm my)
Kxy
(4)
d(x, v)

---

156
(Local Structural Approximation) The Ollivier-Ricd curvature defined on metric measure space (V. d, m) for graphs, in which the large curvature Kay indicates the small distance Wi (mz, my) between the probability measures my for two nodes Because the probability measure is defined through random-walk kernel, the distribution distributed uniformly 1-hop neighbor- ing nodes in the unweighted graph. Then it effectively represents the local structural information. Therefore, the proposed subgraph sampling proportional to the curvature reduces the distributional difference dm (92. Gz), while also approximating the local structure of the graph. As shown in Fig.3, even if the number of edges are sampled equally based on the node, subgraph Gp with positively curved edges can be more distributionally and structurally similar to the original graph than subgraph
157
158
159
160
161
162
168
164
Go with negatively curved edges.
165
166
Proposition 1 Let (V, d, m)) be the metric space with the random walk Then, my is the probability measure defined in 3 for the local structure G and is the probability measure defined as
167
w Eeev x by. where EveN(es) Ply 1 and by = ly for the local structure Gz. The distributional difference of probabilistic sampled subgraphs is bounded by curvatures, as follows:
168
189
dm G2) 22
Σ (EN())
p(ylx)Rey
(5)
170
where Kay denotes the Ollivier-Ricci curvature of edge (z, y). Proposition 1 shows that the distri- butional difference around node x of the probabilistic sampled subgraphs is inversely proportional to the expected value of the curvatures of the edges linked to This implies that the distributional difference between the sampled subgraph and original graph decreases with the increase in the expected value of the curvature; that is, the probability model, which frequently samples edges with large curvatures, can obtain more structurally approximated subgraphs. Please note that the upper bound of the distributional difference in Proposition 1 can be extended to n-hop to capture a wider scope of local structure near the node. Thus, we also present the upper bound of the distributional difference between the n- n-hop diffused probability measure m and the probability measure wz of the probabilistic sampled subgraphs, as follows:
171
172
173
174
175
176
177
178
179
180
Corollary 1.1 n denotes the probubility measure of restep random walks on Markov chain. It can be considered as the state of n-hop propagation in the original graph. Suppose that the graph Gp = (V. E) is composed of posilively curved edges such as Kay 2 K. >> 0 for any pair of nodes x. y 182
161
183
in V. Then, the upper bound of distributional difference between m and w. is bounded as follows.
1 (2) xxx (1 x) d (S..
K
104
Corollary 1.1 shows that the distributional difference between the n-hop local structure 9:" and sampled local structure G.p also bounded in relation the 1-hop local distributional difference in Proposition 1. Subsequently, we suggest that subgraphs consisting of edges with large curvatures have generalization effects, which can be advantagcous for learning the model.
105
186
107
188
(I+ vo, U2, -., Un y4) and P, (z, up. UI.... Uo, =n 3yy be the geodesic paths for any shortest path of (Ii, and vj), respectively. The distance for each edge is defined as (111) d(uu, u141). Then, if the curvatures of the paths P.,P, satisfy the inequalities Kuguess 2 Kugur for any edge (v,, vi+1) and (u, 14+1) in the paths, the following inequality holds for the gradients between starting and ending nodes in the paths:
Proposition 2 Let
189
190
191
192
V.. (f Af) V.,y, (f Af)
193
for any #Liiscchit,functinn f.
194
Proposition 2 implies that the two paths have the same length but can yield different gradients. The gradient is proportional to the sum of the edge curvatures in the path. Therefore, if it is possible walk along the edges with large curvatures, the distance of node features in the starting and ending nodes of the path can close, even for the same length walks. Thus, propagation by edges with
195
196
197

---

198
a large curvature can smoothen the feature space, And this can give a generalization effect. The locally smoothed feature space can be defined fl fyll < for any pair of nodes (z, v) with d(x y) I π. The small gradient Vay in the n-bound indicates that smooth feature space is obtained even with relatively distant nodes. In Section 3, we conduct experiments on the generalization effect to demonstrate the accuracy with which all nodes can be predicted through learning with only small
199
200
201
202
203
partial nodes.
204
5
Localized Curvature-based Combinatorial Sampling
205
Subgraph sampling is used sample mini-batches for large-scale graph. However, sampling the optimal subgraphs by considering the whole structure of the large graph is challenging. Therefore, the previous section shows that local structural approximation of subgraph using curvature is possible instead. However, it is still difficult calculate the exact curvatures of the edges due the high computational cost of solving the optimal transport problem. Thus, we obtain subgraphs through combinatorial sampling proportional to the approximated curvatures of the Definition 3 using the localized structure of the graph with 3-cycles. We show that the approximated curvatures exhibit sufficiently small errors in local structures of sparse graphs.
206
207
208
209
210
212
213
Definition 3 ([191, Localized Curvature with 3-cycles) dı and dy denote the degree of nodes x and respectively. Ap(z, v) represents the number of triangles (3-cycles) including the edge (x,y). v). The operations d₂ A dy and dz V dy denote min [dz, [dz.dy] and max (dz. respectively. (++ is defined
214
215
216
max [-, 0). Then, the localized curvature Kay for the edge (z, y) has the following lower bound.
1
d d dy )
Az(z,y)
1
1
Ag(a, v)
d V dyy )
Ag(s,v)
Kay
(8)
d
d dd,
217
The lower bound of Kay in (8) can be considered the localized curvature for ((4) and 2ig 2A) in the 1-hop local structures (z))N(()) As this local-
218
Kiry
Kary
Ki g
219
1/
220
221
ized curvature only considers adjacent neighbors, it is not accurate. However, the localized curvature with 3-cycles Figure 2: Approximated curvatures in the local structure.
With n-cycles
With 3-cycles
C. Withoutt cycle
222
223
224
(8) and Fig.2B) is within the tolerance range of the exact curvature for sparse graphs. We also present that other conventional subgraph sampling methods are related to more approximated curvatures with no cycles ((9) and Fig. and argue that curvature is closely related to subgraph sampling. cycle Az y) = O in the local structure of the graph even if there are cycles. Therefore, the lower bound of the curvature without cycles [24] is defined as follows.
225
226
227 It assumes that there
228
Kay 2 2 21
-,
(9)
229 where de and dy denote degrees of nodes x, y edge (I, y), respectively. Conventional combina- torial subgraph sampling methods are related to this localized curvature without a cycle, as Table 1.
230
Table 1: Conventional methods can be interpreted as sampling related to the coarse curvature.
Sampler
Probability model
With curvature
Edge[45]
p(ezy) x d2
p(exy) x Nzy+2
2
Node[45]
p(x) x (Eynz de
1)2 p(x) (E d
Kay
1)2
you
p(x) Eyne (May +2)
Cluster[7]
p(x) x c(x)
231
3d-1
232 We show that the local structure ((x) (y) of the graph does not have the shortest path beyond
238
5-cycles, thus the localized curvature with 3-cycles has very small errors in the sparse large graph.

---

Proposition 3 (Error bound localized curvature) Let (n. p) the ER-gruy graph (Erdös-Rényl model) with n > 4 nodes and edges connected by the probability 0 p S. 1. Then, the degrees dus dy of nodes z, are expected as dg = dy = (n 1)p. Let Ay(2, y) be the number of 3-cycles, [x, y) be the number of 4-cycles, Of (a, y) be the number of 5-cycles. In the local structure, the shortest distance between nodes can be obtained by considering only S-cycles or less, there is a
234
235
236
237
238
239
small error in the approximated curvature Rey with 3-cycles for sparse large graphs:
2 |aa Rzyll S ((..)) of(,, v) S 2dp 2d'p
(10)
0 p(p())
Dar Cornttre--aae www.uee-baeedd.oo proda
p(r(()
Compute localized
Sample initial nodes S
curvature-based probabilities
Figure 3: Curvature-based subgraph sampling. First, we sample the initial nodes S, then the probabilities P(x[S) is computed based on the curvatures. With the proposed method, we can sample nodes (bluc) to maximize the curvatures in subgraph.
240
(Proposed Method) We propose a localized curvature- based sampling method to sample the sub- graphs from large graphs. There studies [8, 30, 34, 2] that solve optimization problems sample the subgraphs. However, because they have difficulty in dealing with large graphs, we present a combinatoria approach that samples nodes and edges as like [14, 45, 7, 1J. Furthermore, while conventional methods have been described through variance reduction node degree, show that they can be interpreted by using the coarse curvature (9) in Table 1. Therefore, we propose al algorithm that locally approximates optimal subgraph by finding the subgraph with large curvatures in Definition 3.
241
242
243
245
246
The curvature Kry is defined for edges (I, y). in which the sampling probability for each edge is defined as pzy) o Kay in Definition 2. However, because p(y)zz) is bounded in the local structure, it can be defined via normalization, i.e., p(y]z) EveN(e) K..." Alternatively, the probability for each 250
248
6xz
edge can be defined directly to the structural normalized curvature, i.e., p(y) x) x Auz d,
251
252
Using the above probability model, we extend local optimal subgraphs instead of finding global optimal subgraph. In the beginning, there are no sampled node, so initial nodes zg E So are sampled by (V) x Lye.N(=)). p(roly). After sampling the initial nodes, linked nodes #4+1 E (S,) have sampling probabilities p(=++1|S; (S:) x EgeN(ay :) se p( 1 ily). Our method starts at the initill nodes S,, then extends the connected nodes S1 to maximize the sum of curvatures of edges in the subgraph ② = Sp S. U... S, If we sample n subgraphs with the size of m in steps, the whole pipeline of the proposed method Algorithum Further details can found Appendix E,
253
254
255
257
258
Algorithm Localized Curvature- -aseed Sampling (LoCur)
Inputs: G (V, E), iters n, sample size m, steps / Output: sampled subgraphs G
V()[V) x Eyna.vev p(xly)
compute localized curvature-based probabilities
for k to n do
So Poo Vi,... |m//a]} p(xlV)
>> sample initial nodes
for i = to
1 do
p(=[S,) x EpEN(s).vEs p(x v)
compute localized curvature-based probabilities sample extended nodes
S S, U luo, "., [m/a]] ~ p(x(S.)
end for
G2 S
end for

---

Experiments
259
260
Our method proposes sample the subgraphs that maximize the curvature more directly compared to conventional methods. T'herefore, although our method cannot calculate the exact Ollivier-Rii curvature for the large-scale graphs, can present the exact curvature calculated by [27] for small graphs (Cora graph [25] with 2708 nodes and 5429 edges, Citeseer graph [12] with 3312 nodes and 4732 edges, and the Pubmed graph [32] with 19717 nodes and 44338 edges). The following experiment Table was evaluated for 1000 subgraphs with about 10% (200/2708, 300/3327, 2000/19717) partial nodes.
261
262
263
264
Table 2: Comparison of Ollivier-Ries curvature using the Cora, Citeseer, Pubmed graphs.
Ollivier-Ricii
random walk
multi
LoCur
original
random
neighbor
node
edge
PPR
Curvature
clusters
(Ours)
graph
Cora -0.08
-0.06
-0.09
-0.07
-0.02
-0.08
+0.00
-0.07
Citescer -0.05
-0.06
-0.09
-0.06
-0.06
-0.01
-0.07
+0.02
-0.06
Pubmed
-0.08
-0.07
-0.05
-0.07
-0.07
-0.07
-0.08
-0.05
-0.08
266
We also show sampled subgraphs for the karate club graph [44] with 34 nodes and 78 edges, which is
268
a very small graph, and presenl results for one of the REDDIT-BINARY graphs [13] with 400 nodes and 460 edges. With this experiment. we can examine structure sampled by the subgraph. As shown in Fig.4, our method samples the subgraphs to include representative structures without bias compared to other methods.
269
271
Figure 4: Subgraph examples for Karate club and REDDIT-BINARY graphs. This figure show the subgraphs of random, edge, cluster, and LoCur(ours) sampling from left to right. Additional results can found in Appendix
272
These sampled subgraphs are typically evaluated by the tasks such as node classification and graph classification. However, the case of semi-supervised node classification, evaluation can be af- fected by train, valid, and test ratios of nodes within sampled subgraphs. Therefore, we present a labeling task that evaluates the entire nodes (100%) by learning only one sampled subgraph of the specific proportions (1 %6, 5%, 10%) in 100 experiments. Table shows that method induces the generalization effect, which yields good performance even with very few nodes.
274
275
276
277
278
Our subgraph sampling method can train large-scale graphs, such as mini- training, by sampling approximated subgraphs, which are used only for training and the entire graph is used for evaluation. Because each graph has different size, the size of subgraphs all experiments can be reproduced using common random seed. The sampling costs are negligible because the subgraphs are shuffled and reused to configure the batches following the initial sampling. The proposed method was evaluated based on the highest valid accuracy without any methods, such as carly stop or regularization. Consequently, the average accuracy and standard deviation of the training results were obtained for 100 subgraphs by performing the experiment times.
279
280
different for each graph. In addition,
262
284
285

---

Table 3: Comparison of labeling task using the ogbn-arxiv, ogbn-mag graphs.
Labeling
arxiv-1 (%)
mxxi--((%)
arxiv-10 (%)
mag-1 (%)
mag-5 (%)
mag-10 10 (%)
random
57.02:42.55
63.78:0071
68. 08.16:1.31
29.93=0049
29.25=0.21
30.94=0.15
neighbor
58. 18.13
66.28+0.44
68.73=0.30
24.95=0.45
30.42=0.18
32.66=0.13
node
58.5511133
67.12.10.39
69.51-1.23
25.03=0.45
30.42_0.16
32.10-0.111
edge
60.42.10.88
67.1010.33
69.3111.222
25.67_0.41
30.5510.18
32.47:1.113
random walk
59.37+0.84
66.66+0033
68.90=0.23
25.49=0.35
30.47=0.16
32.46=0.13
cluster
53.09:+1800
64.54:0.54
67.63=0.33
22.03=0.65
29.14=0.22
31.78=0.19
ppr
56.74:1:3446
13:10.77
08.35=0.43
0.30
30.41=0:20
32.54
LoCur (Ours)
62.01110.72
68.0910..29
0.19
25.69
30.78
32.86
286
The ogbn-arxiv graph [16] in Table 4 comprises 169, 143 nodes and 1, 166, 243 edges, which is directed graph representing citations. We trained the graph neural models with undirected normaliza- tion and sampled 100 subgraphs with the size of 1, 700(1%) to construct sampling method uses only the structural information of the graph, it does not directly improves the accuracy of the node classification task. Nevertheless, our method produced competitive results.
287
208
Because our
269
290
281
The ogbn-mag graph [16] in Table 4 consists of 736, 389 nodes and 10, 792, 672 edges. We sampled 100 subgraphs with the size of 7, 000 to construct mini-hatches, and performed the mini-batch traniigg using the sampled subgraphs. The evaluation of the compared methods was conducted using the entire graph. In the case of the GCNII method and ogbn-mag dataset, inferring the original graph difficult; thus, the results are not available. The accuracy of the sampling methods depends on the characteristics of the graph because subgraph sampling methods use only the graph structural information without feature information. In the case of the ogbn-mag graph, aggregating the feature points of nearby nodes, for examplc, clustering, induced good results.
292
293
294
295
298
297
298
289
Tables and 4, and additional results' show that the proposed method produced competitive results for various graphs and GNNs. Our method can efficiently train GNNs using only subgraphs with partial nodes (1%) compared to the GNNs trained for the entire graph.
300
301
Table 4: Comparison of node classification using the ogbn-arxiv and oghn-mag graphs.
Node
anXivGCC
anio/GraptsAGG
mag/GCN
mag/GaapESAGG
Classification
Valid acc (1)
Test acc (%)
Valid acc (9)
Test aco (%)
Valid ace (%)
Test acc (%)
Valid acc (8)
Test acc (9))
madoo
65.60.1122 1.21
61.4311006
67.1510.33
66.5110.63
28. 08.79.10.80
30.02:0099
30.89...55
31.8710.47
neightor
70.49=0.22
60.00+0.5 59
21. 12:0010116
70:11=0.23
32. 12.6000.62
33.14=0.80 80
32 02.3300000
33 64-66--777
node
68.441.0.24
67.5610.37
65.32.10.15
64.20.10.25
28. 15.0.42
29.35
26.7210.53
28. 03.06110.5
edgo
69.97:00227
53:10.111
69.23:0.30
30.83-t0.00 46
31,41=0.45
70:00:3333
66::660111
walk
70.39:00.19
29.01:229
70.78:0017
69.55=0.226
31. 18
$2.48:00.29
32.08:0.47
32
claster
20.58-0.35
69.3511.62
70.56110.19
69.0920.39
33.93:10.37
34.82-0.33 39
34.4110448
35.09110:51
Ppc
67.70+0.55
66
71. 11.10+0.23
70.04-0.62
29.67++0.57
30.85-0.68
31. 31.51+0.552
32 02.0440.63
LoCur (Ours)
0..91:0.24
69.53:0.57
71.29:00:15
0.315:00311
34.54:00.44
0.77
34.69::0.55
35.32:00.6
original graph
73.15:10.08
71.97.10.3
73.08.10.21
71.65:00446
36.54.10.18
36.74.10.26
36.5510.40
36.69.10.35
7
Conclusion
302
303
To learn large graph by dividing it into subgraphs, the subgraphs should be sampled to represent the original graph. While finding substructures using curvature in large graphs has been widely studied,
304
905
we propose that the coarse Ollivier-Rica curvature bounded by the local structure closely related method performs local
306
to conventional combinatorial subgraph sampling methods. Therefore, optimization search to maximize the curvature of the subgraph based on the localized curvature. Consequently, our method can obtain the combinatorial subgraphs to approximate the original graph by the distribution metric. The experimental results show that subgraphs with the edges of large curvature are suitable for representing the original graph.
307
308
309
310
Please refer to Appendix for additional experiments.

---

References
911
312
[1] Aleksandar Bojchevski, Johannes Kliepera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Güanemann. Sealing graph neural networks with approximate pagerank. In ACM SIGKDD, 2020.
313
314
315
[2] Francesco Bonchi, David Garcfa-Soriano, Atsushi Miyauchi, and Charalampos E Tsourakakis. Finding densest k-connected subgraphs. Discrete Applied Mathematics. 305:34-47, 2021.
316
317
[3] Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with ncural networks. In JCL,R, 2021.
318 [4] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv: 1050.006688 2017.
319
320
[5] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:180. 10247, 2018.
321
822
[6] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolu- tional networks. In ICML, 2020.
828
324
[7] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD, 2019.
325
326
[8] Alessio Conte, Andrea Marino, Roberto Grossi, Takeaki Uno, and Luca Versari. Proximity search for maximal subgraph enumeration. arXiv preprint arXiv:1912.13446 2019.
327
328
[9]
Michael Defferrard, Xavier Bresson, and Pierre Vandergheynsi. Convolutional neural networks on graphs with fast localized spectral filtering. NIPS, 2016.
329
330
[10] Robin Forman. Bochner's method for cell complexes and combinatorial ricci curvature. Discrete and Computational Geometry, 29333333,377, 2003.
331
332
[1I] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. 11198, 2020.
333
334
[12] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
335
336
[13] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation leamiing large graphs. Advances neural information processing systems, 30, 2017.
337
338
[14] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
339
340
[15] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayaman, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In ICML, 2020.
341
342
348
[16] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiso Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benehmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00655 2020.
344
345
346
[17] Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. arXiv preprint arXiv:1809.05:: 2018.
347
[18] Yu Jin, Andreas Loukas, and Joseph Jala. Graph coarsening with preserved spectral properties. In AISTATS, 2020.
349
350
[19 Jürgen Jost and Shiping Liu. Ollivier's s ricci curvature, local clustering and curvature-dimension incqualities on graphs. Discrete & Computational Geometry, 51(2):000-322 2014.
351
352
20 Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint Nttt:1609.02999 2016.
353
354
22 Johannes Kliepera. Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint 181.09181. 2018
355
956
[22] Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In NeurlPS, 2019.
357
10

---

358
[23] Jianxin Li, Xingcheng Fu, Qingyun Sun. Cheng Ji, Jiajun Tan, Jia Wu, and Hao Peng. Curvature graph generative adversarial networks. In www, 2022.
359
360
[24] Yong Lin and Shing- Tung Yau. Ricci curvature and eigenvalue estimate on locally finite graphs, Mathe- matical research letters, ISSN 1073-2780, Vol. 17, N" 2-3, 2010, pags. 343-356, 17, 03 2010.
362
255
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construc- tion internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
363
364
[6] Chien-Chun Ni, Yu- Yao Lin, Feng Luo, and Jie Gao. Commmniit detection on networks with ricci flow.
365
Scientific reports, 911::112, 2019.
366
[27] Chien-Chun Ni, Yu- Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific reports. 9(1):111,, 2019.
367
368
[28] Yann Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, 256(3):810 864, 2009.
369
370
[29] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Chuaxu Zhang, and Bo Yang. Curvature regular- ization to prevent distortion in graph embedding. arXiv preprint arXiv:2011 14211, 2020.
371
372
[30] Daniel Rehfeldt, Henriette Franz, and Thorsten Koch, Optimal connected subgraphs: Formulations and algorithms. 2020.
379
374
[31] Arcejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of risci curvature for complex networks. Scientific reports, 8(1):116,, 2018.
375
376
[32] Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Galligher, and Tina Rliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9) 93, 2008.
377
378
[33] Ming Shao, Xindong Wu, and Yun Fu. Scalable nearest neighhor sparse graph approximation by exploiting graph structure. IEEE transactions on big data, 2(4):365 380, 2016.
379
380
[34] Renata Sotirov. On solving the densest k-subgraph prohlem on large graphs. Optimization Methods and Software, (5(6):1660-11 2020.
381
382
35] Chuxiong Sun and Guoshi Wu. Adaptive graph diffusion networks with hop-wise attention. arXiv preprint arXiv:2012.1500 /5024, 2020.
383
384
36] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022.
385
386
377 Petar Vehčković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.
387
Graph attention networks. In ICLR, 2018.
388
338] Jinhuan Wang, Penglao Chen, Bin Ma, Jiajun Zhou, Zhongyuan Ruan, Guanrong Chen, and Qi Xuan. Sampling subgraph network with upplication to graph classification. IEEE Transactions on Network Science and Engineering, 8(4):3478-3490, 2021.
389
390
39] Felix Wu, Amauri Souza. Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In JCML, 2019.
392
393
40] Wei Wu, Guangmin Hu, and Fucai Yu. Ricci curvature-bused semi-supervised learning on an attributed network. Entropy, 23(3)2992, 2021.
384
295
[1] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabuyashi, and Stefanie Jegelka.
396
Representation leaming on graphs with jumping knowledge networks. In ICML, 2018.
397
42]
Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, and Chao Chen. Curvature graph network. In JCLR. 2020.
398
[43] Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon. Sampling subgraphs with
399
guaranteed treewidth for accurate and efficient graphical inference. In WSDM, 2020.
400
[44] Wayne W Zachary. An information flow model for conflict and fission in small groups Journal of anthrupological research, 33(4))452-473, 1977.
401
402
[45] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint:
403
Graph sampling based inductive learning method. arXiv preprint orKiv: 1907799973399 2019.

---

Checklist
404
405
1. For all authors...
406
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
407
408
(b) Did you describe the limitations of your work? [Yes]
409
+ In Section 5, our method focuses on finding the optimal subgraphs by combining local optimal structures instead of global optimal structures. Because the exact Ollivier- Ricci curvature is difficult to calculate, we propose probability model proportional to the locally approximated curvature.
410
411
412
413
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
414
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
415
416
2. If you are including theoretical results...
417
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
418
+ We presented the theoretical assumptions for (Definitions and 2: Proposition 1, 2, and 3; Corollary 1.1; and Table 1).
420
(b) Did you include complete proof's of all theoretical results? [Yes]
421
+ We proved the theoretical results in Appendix D.
422
3. you ran experiments...
423
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No]
424
425
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
426
427
+ We explained the experimental details in Appendix F.
428
(c) Did you report eтror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
420
430
+ We conducted the experiments (Tables 2,3, and 4) using a fixed common random seed, and also presented mean and standard deviation for many samples (100~1000), (d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
431
432
433
434
+ Environmental settings for the experiments were also presented in Appendix F.
435
you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
436
(a) If your work uses existing assets, did you cite the creators? [Yes]
437
+ We used those in [27] to compute the exact Ollivier-Ricci curvatures in Table 2. We
438
evaluated sampling methods using benchmark graphs [16].
439
(b) Did you mention the license of the assets? [N/A]
460
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
442
(d) Did you discuss whether and how consent was obtained from people whose data you'se using/curating? [N/A]
448
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
445
446
you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
468
449
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
450
451
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
452
12


Reviews:
[{"review_id": "wlXw2BZy1Z", "reviewer": "Reviewer_oc4B", "summary": "This paper introduces a subgraph sampling method based on curvature to train large-scale graphs via mini-batch training. They define a combinatorial metric that distributionally measures the similarity between an original graph and all possible node and edge combinations of the subgraphs. This metric is used as an evaluation metric for how good the sampling is. They found that sampling the edges with large curvatures is equivalent to reducing the distributional difference. ", "questions": "\n1. Since the sampling probability p_xy is proportional to k_xy, and k_xy can be negative, how can you get a negative probability? \n\n2. Proposition 3 shows the lower error bound of localized curvature. I am not sure whether this lower bound is small. Since the range of Ollivier Ricci curvature is usually between -1 and 1, the lower error bound between \\hat{k_xy} and k_xy should not be greater than 2. Please provide more statements about when the error bound is small, and when it is large, either in a theoretical way or an empirical experiment way. \n", "limitations": "It is not clear what are the drawbacks or challenges of existing network sampling methods and how the authors address them.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\npros:\n1. The motivation is well explained. It is true that the large graph is computationally infeasible, especially in GCN. Network sampling is in desperate need. \n 2. The proposed method for sampling is novel. \n 3. The writing and presentation are nice. \n\ncons: \nThis paper emphasizes too many selling points, such as proposing a  distribution metric, proposing a curvature-based sampling, proposing localized curvature calculation, and improving the accuracy of GCN. But I have two questions. (1) Regarding the distribution metric, I am confused about the innovation of this metric. As for me, this metric is the same as the definition of Gromov-Wasserstein distance. Please clarify the difference. (2) Regarding the localized curvature calculation, which basically uses the lower bound which is derived in [19]. What's the innovation in this paper?  \n\n\n\n\n\n\n\n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "opDziE1qWu5", "reviewer": "Reviewer_oyAc", "summary": "The paper introduces an approach to (large) graph subsampling based on positive Ollivier Ricci curvature preservation. This is motivated by theoretical analysis showing that local structure can be better preserved by sampling positively curved edges. Experiments are conducted to support the findings on tasks like node-classification.", "questions": "The more technical/theoretical/presentation questions are already listed in the section above.\n\nFurther questions:\n\n- How do you compare to the baseline in terms of complexity and time?\n", "limitations": "Limitations have not been addressed.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality and impact: \n\nAs far as I can tell, the core idea of leveraging directly the Ollivier curvature by relying on positively curved edges for sampling procedures is new. Some of the theoretical findings are in my opinion not that significant though.\n\n- Proposition 1 feels a lot like simply `shifting' the problem with the distance d_{m} that should be defined in terms of random walks Markov chains exactly as for the Ollivier curvature. Similarly, Proposition 3 states something relatively obvious that is for sparse graphs (where higher-order structures are in fact less frequent on average) neglecting higher order structures in the curvature computation would indeed be not that costly.\n- Partly connected to the first point, results like Proposition 2 and Proposition 3 feel more like `gap-filling' and less coherent with the narrative.\n\n\nQuality and soundness: \n\nThe presentation is poor and the general soundness is at points questionable. Some instances are listed below (but the actual list is longer):\n- Lines 102--104: the message should be better fleshed out here.\n- Is Definition 1 novel? This seems like OT distance definition yet there is no reference. Also line 110 `We define... around the nodes' is not clear.\n- Where is equation (2) derived? \n- The `local structural graph' used throughout the paper $\\mathcal{G}_{x}$ is never introduced -- I can only guess what that is.\n- I don't quite follow the first inequality in (23), could you elaborate?\n- What is $\\nabla_{x_{i}y_{i}}$ in (7)?\n- The sentence `The gradient is proportional.. in the path' at line 194 is unjustified.\n- In the proof of Proposition 2, how (30) derives from (29)? If $m$ is not supported in $y$, then we should have $(D^{-1}Af)(y)$ and not $f(y) + \\Delta f (y)$.\n- In (31) what is $\\nabla_{yx}$? \n- In (36) there should not be an equality since we are bounding (32) and (33) from above? \n- From the previous points, I am a doubtful about the correctness of Proposition 2.\n- I don't follow paragraph 272-277 and similarly the scenario for the node-classification task is not clear (see Questions section as well).\n- Appendices are not useful, mostly containing parts copied/reported by existing references and fail to further clarify and explain the paper.\n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_uqh6Dev8VS", "reviewer": "Reviewer_ybPg", "summary": "The paper proposes a curvature-based graph subsampling method that aims at sampling structurally representative subgraphs via Olliver's Ricci curvature.", "questions": "see above", "limitations": "see above", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strength*\nThe paper addresses an important topic with geometric tools that are not very well explored in this context. \n\n*Weaknesses*\n- The writing should be improved. In terms of clarity and presentation, I don't think that the paper in its current form meets the standards of NeurIPS. Examples: theoretical results are stated as propositions in the main text with no indication of whether and where proof can be found. The actual downstream tasks on which you benchmark your algorithm are not described in the main text and there are no clear references to the appendix. \n- It is not clear, whether your approach is computationally efficient and how its efficiency compares to the other methods you compare against. This should be reported in addition to a comparison of the achieved accuracy. \n- The literature review is not very extensive. Related work on applications of curvature in network analysis is only briefly mentioned in section 2; importantly, related methods on *curvature-based sampling* are only mentioned in the appendix. This should be moved to the main text.\n- The proposed theoretical guarantees for the curvature approximation are given for the Erdos-Renyi (ER) model only. This is not necessary a good model for real network data. In addition, the structure of ER graphs varies very significantly with the edge threshold, which is not even commented on. Do your results hold for all regimes? \n- What are the values in Tab. 1? How are they computed?\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W4Sv97WtfEs", "reviewer": "Reviewer_mCsD", "summary": "The paper presents a new method for picking samples consisting of relatively small subgraphs of a very large graph so that the selected subgraphs are representative of the large graph for learning and classification.  It is stated that this process improves tasks involving classification of the graph using the small samples, eg as in GNNs.  The sampling method is based on constructing distributions on nodes and edges of the graph which reflect their discrete Ricci curvatures.  Subsequently, several key observations about the localized curvature-based node/edge distributions are stated and proved. Numerical experiments are provided at the end which support the claim of representativeness of the samples for graph learning and classification.", "questions": "\nIt would be helpful if the authors could address each of the questions raised above:\n\n1) Why do sampled subgraphs used in feature learning need to be similar in any way to the larger graph? Would it not be better if these samples cover the spectrum of variations that subgraphs of a fixed size actually exhibit?  \n\n2) what actual graph classification tasks did the computational experiments solve?  More specifically, what are the classification/learning problems in ogbn-arxiv and ogbn-mag tasks which represent the problems set out to handle via small subgraph sampling?\n\n3) How does the proposed method compare with prior art?  The authors cite much prior work.  Are the rows labeled random, neighbor, node, edge, rw, cluster and ppr the best known prior sampling methods and if so could the authors remind the reader what classification learning tasks obgn consisted of?", "limitations": "\nNA", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe methodology presented is theory-based and is computationally manageable.   The theoretical results are discussed at some length in the supplementary material provided.  \n\nThree key weaknesses of this paper are 1) Why do sampled subgraphs (segments of the very large graph one wishes to learn) used in feature learning need to be similar in any way to the larger graph, the enormous discrepancy between their node/edge sizes notwithstanding, 2) what actual graph classification tasks did the computational experiments solve?  and 3) How does the proposed method compare with prior art? \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject