Subsampling in Large Graphs Using Ricci Curvature
Authors: Shushan Wu
Huimin Cheng
Jiazhang Cai
Ping Ma
Wenxuan Zhong
Venue: ICLR 2023 poster (2023)
Keywords: Graph subsampling
Ricci curvature

Abstract: In the past decades, many large graphs with millions of nodes have been collected/constructed. The high computational cost and significant visualization difficulty hinder the analysis of large graphs. To overcome the difficulties, researchers have developed many graph subsampling approaches to provide a rough sketch that preserves global properties. By selecting representative nodes, these graph subsampling methods can help researchers estimate the graph statistics, e.g., the number of communities, of the large graph from the subsample. However, the available subsampling methods, e.g., degree node sampler and random walk sampler, tend to leave out minority communities because nodes with high degrees are more likely to be sampled. To overcome the shortcomings of the existing methods, we are motivated to apply the community information hidden in the graph to the subsampling method. Though the community structure is unavailable, community structure information can be obtained by applying geometric methods to a graph. An analog of Ricci curvature in the manifold is defined for the graph, i.e., Ollivier Ricci curvature. Based on the asymptotic results about the within-community edge and between-community edge's OR curvature, we propose a subsampling algorithm based on our theoretical results, the Ollivier-Ricci curvature Gradient-based subsampling (ORG-sub) algorithm. The proposed ORG-sub algorithm has two main contributions: First, ORG-sub provides a rigorous theoretical guarantee that the probability of ORG-sub taking all communities into the final subgraph converges to one. Second, extensive experiments on synthetic and benchmark datasets demonstrate the advantages of our algorithm.

Published as a conference paper at ICLR 2023
SUBSAMPLING IN LARGE GRAPHS USING RICCI CUR- VATURE
Shushan Wu, Huimin Cheng, Jiazhang Cai, Ping Ma & Wenxuan Zhong
Department of Statistics
University of Georgia
Athens, GA 30605, USA
(Shushan. Wu, www.humiiihihhe. (122744,,pingee wenxuan) euga edu
ABSTRACT
In recent decades, an increasing number of large graphs with millions of nodes have been collected and constructed. Despite their urility, analyzing such graphs is hindered by high computational costs and visualization difficulties. To tackle these issues, researchers have developed graph subsampling approaches that extract representative nodes to provide a rough sketch the graph that preserves its global properties. By selecting representative nodes, these graph subsampling methods can help researchers estimate the graph statistics, e.g., the number of communities, of the large graph from the subsample. However, the available subsampling methods, such as degree node sampler and random walk sampler, tend to overlook minority communities, as they prioritize nodes with high degrees. To address this limitation, we propose leveraging community information hidden within the graph for subsampling. Although the community structure is typically unknown, geometric methods can reveal community structure information by defining an analog of Ricci curvature on the graph, known as the Ollivier Ricci curvature. We introduce new subsampling algorithm called the Ollivier Ricci curvature Gradient-based subsampling (ORG-sub) algorithm based on our asymptotic results regarding the
and detween-communitie edges' OR curvature. The ORG-sub algorithm makes two significant contributions: Firstly, it provides a rigorous theoretical guarantee that the probability of taking all communities into the final subgraph converges to one. Secondly, extensive experiments on synthetic and benchmark datasets demonstrate the advantages of our algorithm.
INTRODUCTION
As enter the big data unprecedented opportunities and challenges. For example, Wang et al. (201 presented Twitter social network, which has more than 190 million nodes (users) who generate more than 65 million edges (tweets) every day (Wang et al.) 2011). Such huge networks enable researchers to tackle more complex problems. However, they pose great challenges to storing, visualizing, and analyzing since their sheer volumes render many computational methods infeasible.
capacity access large graphs (a.k.a. networks) has provided
Graph subsampling. Graph subsampling is commonly used technique to address this scalability issue because of its simplicity and efficiency. Graph subsampling aims to take subgraph that preserves critical features of the full graph. Various graph subsampling methods that preserve different graph properties have been proposed, including node sampling (Mall et al. 2013 Zeng al. 2209), edge sampling (Krishnamurthy et al.] 2005), and exploration sampling (Goodman) 1961 Leskovec et al. 20055 Hübler et al.) [2088] Maiya & Berger- Wolf 2010). Researchers evaluate the graph subsampling approaches by measuring the similarity between the features of the original graph and those of the subgraph. The features include, e.g., degree distribution (Adamic et al. 2001).
minimum cut (Hu Lau 2013). and the number of triangles (Seshadhri et al. 2014).
An important graph feature that has received less attention is the number of communities (denoted by M), which plays crucial role in identifying the community structures. Network data often have natural communities, and the identification of these communities helps answer vital questions in

---

Published as a conference paper at ICLR 2023
variety of fields (Rohe et al., groups of people who share a similar interest, and communities in protein-proteii interaction networks could be regulatory modules of interacting proteins (Rohe et al.] 2011). In this paper, we focus on the setting where M is a fixed model parameter, and there is a ground truth about M. This setting is widely used in many models, e.g., stochastic block model (SBM) (Holland et al. 1983) and its variants such as degree-corrected SBM (DCBM) (Karrer & Newman] 20111) The SBM family is arguably the most widely-used generative model for community detection from a theoretical perspective. In fact, Vaca-Ramires & Peixoto (2022) performed a systematic analysis of the quality of fit of the SBM for 275 real networks and observed that "SBM is capable of providing an accurate description for the majority of networks considered". Indeed, there are other settings where the number of communities not fixed. For example, Olhede & Wolfe (2014) used SBM to approximate a nonparametric graphon model, under which case the number of communities is hyperparameter and is not fixed. The latter hyperparameter case is beyond the scope of this paper.
2011). For example, communities in social networks may represent
Under the setting where M is a model parameter, many community detection methods have been proposed, such as modularity maximization (Newman 2006 Good et al. 2010), spectral clustering (Von Luxburg 2007 Rohe et al., 2011 Liu et al. 2018)), and pseudo- likelihoodd based methods (Amini et al., 2013| Wang et al.j 2021). The theoretical properties of most community detection methods, such consistency and asymptotic distributions, are built based on the assumption that M is known (Ma et al. (021). In addition, M is usually required as an input for those community detection algorithms. However, in practice, we do not have the information of M, which significantly diminishes the usefulness of the aforementioned methods. Existing methods for estimating M are usually very expensive. For example, the cross-validation method proposed by Li et al. (2020) requires computational cost that is cubic in the number of nodes n. When there are thousands or millions of nodes, the computational cost unaffordable.
Thus, it is highly desirable for subsampling methods to yield subgraphs with ń << n nodes preserving the number of communities M, such that we can use it to get an accurate estimation while reducing the computational cost. Despite many successful applications, existing subsampling methods tend to leave out minority communitics (i.e., a community with a smaller number of nodes) because nodes with high degrees are more likely to be sampled into subgraphs. Consequently, these subsampling methods usually underestimate M, especially for graphs with imbalanced community structures.
To overcome the shortcomings of existing methods, we develop graph subsampling method that yields subgraphs that can be used to accurately estimate M. Achieving this goal is challenging since the community structure is hidden and unavailable. Fortunately, recent studies indicate that the community structure is a geometric phenomenon by considering a graph as a Riemannian geometric object (Ni al. 2015). Some insights into the community information can be obtained by applying some geometric methods to graph (Ni et al. 2015 2019 Sia et al. 2019).
Ollivier Ricci Curvature of Graph. In particular, graph can be regarded as a discrete version of a Riemannian manifold (Ni et al. 2019). A node of the graph is analogous to a point on a Riemannian manifold, and a pair of connected nodes in a graph is analogous two points connected by a geodesic on a manifold. The partition of a graph into communities is analogous to the geometric decomposition of Riemannian manifold (Ni et al. 2019). Ricei curvature is a key tool for the geometric decomposition of a Riemannian manifold. It measures how the Riemannian manifold deviates from the flat manifold. Recently, et al. (201I) defines an analog of Ricci curvature for the graph, i.e., the Ollivier Ricci (abbreviated OR) curvature. Previous empirical results have shown the OR curvature is related to the connectivity of the graphs (Ni et al. 2015; Gosztolai & Arnaudon 2021). However, the relationship between OR curvature and connectivity is insufficiently explored in theoretical evidence. In this paper, we theoretically show that the OR curvatures of edges within a densely connected community are asymptotically larger than those of edges between two sparsely connected communities, as the size of the graph increases.
Ollivier Ricci Curvature Gradient Based Graph Subsampling. Based our theoretical result, we propose an OR curvature gradient-based graph subsampling algorithm (abbreviated as ORG-sub). Specifically, ORG-sub randomly chooses one edge as the starting point of the subgraph and calculates the OR curvature of the selected edge. ORG-sub then gradually expands the subgraph by taking the next edge whose OR curvature shows the largest difference from the OR curvature of the previously taken edge. Here, we define the difference as the OR curvature gradient (ORG). We use the ORG to guide the expansion of ORG-sub, i.e., direct ORG-sub which edge to take next. All edges that
2

---

Published as a conference paper at ICLR 2023
ORG-sub took expand into the final subgraph. Our proposed ORG-sub enjoys two main advantages. First, ORG-sub has rigorous theoretical guarantee. In particular, under the SBM scenario, we prove that the probability of ORG-sub taking all communities into the final subgraph converges to one faster than the random walk algorithm, indicating that even nodes in the minority community are subsampled. More importantly, we theoretically show that the estimation of M by the subsampled graph converges to M of the full graph. Second, our extensive empirical experiments based on the simulated and real-world datasets show that the estimator based on ORG-sub subgraphs accurately estimates M while greatly reducing the computation cost.
PRELIMINARIES
2.1 NOTATIONS AND DEFINITIONS
A graph is made up of nodes that are connected by edges. Considering that directed graphs don't t approximate Riemannian manifolds in discrete form since geodesics are always bidirectional, we only focus on undirected graphs in this paper. Denote a graph as G = (V, E), where V is the node set and E' is the edge set. Operator | calculates the cardinality of the set. We then denote the cardinality of the node set in graph by [V] (V] n2), the number of edges in a graph by |E], and the neighborhood set of a node v by d(v) [w, w) E}. The degree of a node v is defined as the cardinality of its neighborhood: d, = (8(+)]. For a subset of V, S S V, the subgraph induced by the subset S is denoted by G[S] (S, Es), where the edge set Es- = {(rs,
E Elus E S, ws S}. The neighborhood of the node set S is defined by ((S) = Uves 8(r), and the neighboring edge
set of edge (u, v) is A(e) {(x,, y)(ær vu. y E 5(x)) (u, v}}. Let M (G(S)) denote the estimator of M, obtained by using the subgraph G[S) for estimation.
2.2 OLLIVIER RICCI CURVATURE OF GRAPHS
A Riemannian manifold (M,g) is defined as smooth manifold M equipped with met- ric 9 TM x TM - TR, where TM is the tangent space of .M (Lee) 2018).
Ricci curvature of Riemannian manifold measures the de- viation of the manifold from a flat manifold (Lee) 2006 Ni et al. 2015 Samal et al., 2018). The "flat" means the distance between two nodes is the same as the distance between the two local spaces centered around the nodes. In the discrete version, the space defined on the node is dis- cretely uniformly distributed in the node's 's neighborhood, then the distance between two spaces can be explained as the average distance between the neighborhoods of the
'hhe left one is a troe-structured graph corre- sponding to hyperbolic manifold with negative curvalure. The middle one is grid-stractn gridttstrntuued graph corresponding to Euclidean space with curvature. The right one complete graph Ke. which is embedded in a spherical surface with positive curvature.
Figure 1:
two nodes. Through such an analogy. the counterpart of Ricci curvature, Ollivier Ricci curvature (Lin et al., [201 is defined in graphs. Previous empirical results show that the OR curvature of graphs is related to the Ricci curvature of the underlying manifold: the graph with large (or small) OR curvature corresponds to the underlying manifold with large (or small)
Ricci curvature (Ni et al. 2015 Samal et al., 2018 Ni et al. 2019:; Gosztolai & Arnaudon, 2021). Theoretical results have shown the OR curvature of random geometric graphs converges to the Ricci curvature of the underlying Riemannian manifold (Boguna et al. 2021 van der Hoorn et al.) 2021). Here we use toy example to illustrate the relationship between the OR curvature of graphs and the corresponding underlying manifold. In Figure [ the hyperbolic space (with negative curvature) is especially suited for tree-structured graphs (Nickel & Kiela 2017), the Euclidean space (with zero curvature) is especially suited for grid-structured graphs, and the spherical space (with positive curvature) especially suited for complete graphs (Ni et al. (015).
We now introduce the definition of OR curvature of the graph. For a E [0, 1] and any node u with degree d,,, we first define the probability distribution of node by m
i
m
(1 0
if E 5(u) otherwise
(I)
3

---

Published as a conference paper at ICLR 2023
Here is to keep the probability mass of node itself and distribute the rest uniformly over the neighborhood. Following Ni et al. (2018); Ye et al. (2019). we set a = 0.5. This means that each node keeps 50% of the probability mass to itself. Let d( (u, 2) be the geodesic distance between nodes u and v, which is the shortest path between two nodes of a graph. We shall present the Wasserstein distance of two nodes in the graph, which is defined as the transportation distance between nodes' probability distributions ma and m..
Definition 2.1 (Wasserstein distance). Let X be the metric space with two probability distributions fl and #22 with mass I, respectively. transportation plan from bl to #2 is a mapping { X + [0. 1] satisfying E, E( v) = ji (x) and Σn E(x, v) (2(z). Substitute Yn and μ22 by probability distributions of nodes m. and m., the Wasserstein distance between two nodes is,
inf Σ E(u, v)d(u, (m m.)
(2)
u.eEV
The Wasserstein distance W (mm mg) can be computed by linear programming (Lin et al. 2011).
Then the OR curvature Ollivier 2007 Lin et al. 2011 over the edge (u, v) is defined as follows.
Definition 2.2 (Ollivier Ricci Curvature). Given the Wasserstein distance W (mm mg) and the geodesic distance d(u, v),, we can define the Ollivier Ricci curvature as:
k(u,e) v) = W(m mg) d(u, v)
3 OLLIVIER RICCI CURVATURE GRADIENT AND COMMUNITY STRUCTURE
The OR curvature of the graph reveals the properties of the underlying Riemannian manifold and provides insights into the community structure of graphs. Previous work has shown that the large (or small) curvature corresponds to the edge which is more (or less) connected than a grid (Ni et al. 2015 Samal et al. 2018 Ni et al. 2019) Gosztolai & Arnaudon 2021).
As shown in Figure the left is graph with five commu- nities, and the right one is graph with three communities generated by the stochastic block model. The warmer color indicates smaller curvature, and the colder color indicates a larger curvature. Previous empirical results and the above toy example have related the OR curvature of graphs to the community structure of the graph. How- ever, rigorous theoretical proofs that the OR curvature of the within- cothin-community edge is larger than the between- communities edge graph are not developed yet. In the Theorem 3.3 we theoretically prove the lower bound of the within-communic edges' OR curvatures are larger than the upper bound of the between-communittes edges' OR curvatures in stochastic block models (SBM).
Figure 2: The cold colooce edges have large OR curva- tures, and warn-colored edges have small cur- vatures. Nodes with different colors belong to different communities.
3.1 ASYMPTOTIC RESULTS OF OR CURVATURE GRADIENT IN SBM
Lemma 3.1 (Ollivier-Ricci curvature of random graphs generated by stochastic block mod- els). Consider a graph with M communities generated from a stochastic block model (SBM)
(4) B ((Pm)) J. .oout, (m1),")). where Pin represents the probability of an edge connecting nodes in the same community Bi Pout represents the probability of an edge connecting nodes from dif- ferent communitiess, and { are the sizes of each community in the SBM. We assume that, for (4) > Pouts and Ps converges to r:(1 > ri > 0), as n goes to infinity. Let n
M
Pin
any i 1,... M, Pin
M ny max {m and pv max { (
Pin J We denote the node x from the community B; by BB the edge (xB, yB,) where is from B, and y is from By, and the edge's OR curvature by R(BB, UB,)) ). The following statements hold for the OR curvature.
4

---

Published as a conference paper at ICLR 2023
1. If Pout <V (ni-1) and Pin + Pout(n - -n;) In ni, for the lower bound of wilhin-community OR curvature, we almost surely have
3
(8)²
K(IB..UB. (nu 2)P + (n (inn-rt)Poud :ta) 2
+ 0
Inn
(4)
Powi
(n, 1)pm + (n -
n4)Pouu (m=n)))Paw
(4)2 2. If Pin, T4 te++Pon Pout (n- nss) > 4 In n4, for the upper bound of within within-community OR curvature,
we almost surely have
K(IB, yB:) Pin O
(6)
Inng
(5)
(3ln /
(6) (n, + nz)) + n n, n2 for the upper bound of between-
3. If Pout
Pous
communities OR curvature, we almost surety have
Pout + n1 n, Dv + #0
Py Inn
K(
(6)
Pont
Lemma 3.2. Combining the conclusion of statement and statement in Lemma 3.1 for any (I' VB,)) E (((BB, VB, )), we have
almost surely,
Pout (Pin Pout)
O ( Poun
[<(#,, UB.) - n(1'B, V'B.
T4 24-1
n--; Pin + Pout
Statements 1 and in Lemma 3.1 together show that under certain conditions, the probability that the (1)
OR curvature of within-community edges falls in (m4-2)pp (2)
(ampp=="*(--))___.m ,Pnn goes to 1 as the graph (n. (00-))+p+((-00
size n goes to infinity. Statement 3 in Lemma 3.1 shows that under certain conditions, the probability
that the OR curvature of between-communities edges being no larger than --"-""' pout " pv
goes to I as goes to infinity. Thus, we can conclude Lemma 3.2 that the probability of the maximum
Pout (v (p..--- -Pout)
goes to infinity. Since the largest OR curvature difference two within-community edges can be bounded, we prove the difference is small enough to distinguish from the difference of K(xB, UB,) and <("",, VB,).
difference of two within vitmin-community edges' OR curvatures being
goes to
n- Pin +Pone
Theorem 3.3. Combining the conclusion of statement and statement 3 in Lemma 3.1 if
Pin metnyy
Pin Poun (n- mm(mmnettt)) and conditions given in the lemma 3.1 satisfied, almost surely. for (n (nn))))))
any (x), Vn,) E ((((n, Mn.)), we have
(x'2 Ve. (e we, [K(ZB, VB.) -x0)),, V/..1 < K(IB, VB.) <0 VB,))
max
The Theorem 3.3 shows the OR curvature of the within-community edge K(IB, VB.) larger than the OR curvature of the k(1',,
edge x(IB, VB,) v(, by the maximum of (( VB.)
The theorem holds under mild conditions. When Pout small enough, and pv is compared to Pout, the conditions can be satisfied. When the graph size large, e.g., thousands of or millions of nodes, the constraint of Pout and Pmn is loosened, and the inequality in Theorem 3.3 can be easily satisfied.
large
(8)
3.2 OR CURVATURE GRADIENT AND COMMUNITIES
We define the OR curvature gradient (ORG) as [x(2 y(d)) - (()((), ( where (1))))00)))
A A((2()) (()) ). It is the difference between the OR curvature of two adjacent edges. According the theoretical results, the within-community ORG [ (B,) ) - =((1 V/z ) is significantly smaller than the betweenn-ommmuittes ORG [ VB,) n(#",, v7, )l. this motivates us to propose a subsampling algorithm based on ORG, which extracts the community information with theoretical guarantee.
5

---

Published as a conference paper at ICLR 2023
4 OR CURVATURE GRADIENT BASED GRAPH SUBSAMPLING
The existing graph subsampling methods usually use degree information and random walk through the graph. However, the subsampled graph tends to leave minority communities (i.e., community with smaller number ) since they tend to sample nodes with high degrees. Due to the lack of taking advantage of the community structure information during the expansion, the available subsampling algorithms usually underestimate M. From the previous work, the community structure relates to the geometric phenomenon of the underlying Riemannian Manifold. Thus, we develop fast and efficient ORG-based subsampling algorithm that is able to traverse the communities of the graph instead of trapping in single community. We then prove the probability the proposed ORG-sub taking all communities of the full graph into the subsample converges to one as the subsample size increases. Consequently, the subsampled graph attained by the ORG-sub algorithm can get larger proportion of the minority communities than other subsampling algorithms and helps estimate M more accurately, as shown in Figure addition, we theoretically show the estimation of M by the subsampling algorithm converges to true M.
4.1 SUBSAMPLING ALGORITHM
The ORG carries the community structure information since it differentiates within-community edges and between-communite
edges with theoretical guarantees in Theorem 3.33 We can use ORG as a guide for expanding the subgraph in the direction of more communities. First, we randomly sample an edge (I. y) as the starting edge. The probabílity of obtaining an edge (z. y) at start P((x(), (²))
To take advantage of the theoretical properties the ORG, the ORG-based subsampler expands to the next edge whose OR curvature shows the greatest difference from the OR curvature of the previously taken edge. The edge subsampled in the i + 1-th step (z((+1), ()(+1))))))) given the edge subsampled in the i-th step (z()), (*) can be expressed by:
(i+1)),, (121),((+)) ((+1)) = arg max (a. ((z())))))))))) |M(I, v) ((x()),(()))
(9)
Since the difference between the ORG, the proposed subsampler will cxpand to another community instead of trapping in one commu- nity. After the subsampler stops expanding or the subsampling budget is used up, we get subsampled nodes. Then we can get the subgraph induced by the subsampled nodes. Details the algorithm are in Algorithm !
ORG is smaller than the
Algorithm 1
Input: Graph G; Number of nodes to be subsampled n;; OR curvature of the graph G calculated by parameter at the subsampled node S 0
Initialization: Randomly choose a node vo as the start of sampling. Here, = 0.
Cold Start: Among all neighbors of vo. randomly add t1 S. Here, t
While: |S| < n
Step 1: Given the edge e = (Vt-1, U1) selected in the f-th step, get the edge curvatures the
's neighboring edges A(ex).
Step 2: Select the edge et the edge set (ee)) that has the greatest OGR.
Step 3: Add nodes connecting the edge et+1 to the subsampled node set S.
t = - +
Output: Subsampled node set S and the induced subgraph G[S]
4.2 ORG-SUB FOR ESTIMATING M
Applying the proposed ORG-sub algorithm to the full graph, as shown in Figure 3 (A), we can get a subsample as shown in Figure 3 (B). Compared with the subsample obtained by the degree- based subsampler in Figure 3 (C), the proposed algorithm can subsample more nodes in minority communities. The toy example illustrates that the proposed ORG-sub algorithm preserves the community structure information better. Thus, the subsampled graph can help estimate M of the full graph.

---

Published as a conference paper at ICLR 2023
We take multiple subgraphs by applying ORG-sub times. For each subsampled graph G[S,] given the sample size n at i-th time, we get an estimation of M, (GG,)) then the mean of (S.)) is calculated as our final estimation of M. As for the choice of the estimation algorithm, we use the state-of-the-ard network cross-validation method (Li et al. 2020).
Compared with other methods (Wang & Bickel, 2017, Chen & Lei 2018), network cross-
validation more robust to complicated settings, ie., the number of communities is large or the community structure is not conspicuous.
IAI
Given the graph G generated by Theorem 3.3 we apply the ORG-sub algorithm to the graph G' and take graph subsamples with size v de-
Figure (A): graph generated by SBM with community size (650, 50, 50, 50). Pin = 0.8 and post = 1. (B): The subsampled graph by proposed ORG-sub algorithm. The proportion of subsam- pling is 10%. (C) The subsampled graph by degree based subsampling algorithm. The propotionn suhsampling 10%.
noted by G[S]. Let denote a node in G [S].
and P(v E B,) denote the probability of the subgraph G[S] carrying nodes in the community B,
Theorem 4.1 shows that the probability of the ORG-sub algorithm expanding to all communities
converges to one as the expanding steps increase.
Theorem 4.1 (Probability of the ORG-sub's Expansion Communities). Under the conditions in Theorem 3.3 as A + 1, we have P(v E B, v E G(S)) - 1.
In addition, based on Theorem 4.1 we prove the theoretical advantage of our method over a popular graph sampling method, i.e., random walk sampling (Lovász] 1996). Let G [[]] denote a sampled subgraph of ñ nodes, obtained by the ORG-sub method, and G nw [S] denote a sampled subgraph obtained by the random walk sampling method. Let URW denote a node in Grw [S]. Corollary shows that P(u E B; V E G[S]) is greater than P(URW~ E B; v E G(S]). This means the ORG-sub is more likely obtain a subgraph containing nodes from different communities.
Corollary 4.1.1 (Theoretical advantage over random walk). Under the assumptions in Theorem 4.7 for any community B; in graph G, we have P(unw E B, E G(S)) < P(v E B, E G(S)).
Theorem 4.1 theoretically guarantees each community in the full graph is subsampled with high prob- ability, thus, the convergence of the estimation of M by the ORG-sub algorithm can be theoretically guaranteed referring to Theorem 3 in (Li et al.] 2020). Since cross-validation methods tend not to M in SBMs (Li et al. 2020 Chen & Lei 2018). we can provide theoretical guarantee against under-estimation of the proposed ORG-sub-based estimator (GG)))))
give M >
áp_ Jo. where p is the edge density, the Corollary 4.1.2. If the subsample with size ñ satisfies ā
subsampling times r -> co, the probability the subsampled graph underestimates the true M is:
Pr(
M(G(S)) < M) 0
(10)
4.3 COMPUTATIONAL ANALYSIS OF ORG-SUB
Computational complexity of Algorithm I We analyze the time com- plexity of Algorithm step by step. The time complexity of querying the neighboring edges and their corresponding curvatures is of order (nd) by Nys-sink algorithm (Altschuler et al., 2019), given d is the average degree. The time complexity of the sorting step to attaining the most different curvature from the neighbors is Od log d). Thus, the time complexity of taking one step is of order O(nd). To sample ñ nodes, we need to run about ñ steps and get the induced subgraph from the sampled node set S. Since getting an induced subgraph of size ñ takes time complexity of order (īd)), the total complexity of the sampling procedure is (nnd)).
SBM
20 22
1.
S.tseping
DCBM
Higure 4: The function of the estima- tion of Af with respect sampling proportion for SRM and DCBM, respectively.
Choice of the subsample Size. When implementing our algorithm, we need to specify the size of the subsamples, which determines the performance and efficiency of the algorithm. Empirically, plot the estimation of M as the function of the subsampling proportion in Figure 4 and we can select the elbow where the estimation of M starts to converge in applications to save computational resources and stabilize the estimation results.
7

---

Published as a conference paper at ICLR 2023
5 EXPERIMENT
We evaluate the performance of our algorithm on both synthetic datasets and real-world datasets.
We use the metric, MAE= E M (G[s))) to evaluate the accuracy of subsampling based estimation. We compare the proposed method with (1) Degree-based Node sampler (DBN) (Adamic
et al. 2001), (2) Community Structure Expansion Sampler (CSE) (Maiya & Berger-Woo Woll 2010)
which is community structure preserved sampler, and six benchmark exploration
graph
subsampling methods, including (3) Metropolis Hasting Random Walk Sampler (MHRW) (Hübler
ct al. 2008). (4) Forest Fire Sampler (FFS) (Leskovec et al. 2005). (5) Snowball Sampler (Goodman
1961 (6) Random Walk Sampler (RW) (Gjoka et al. 2010), (7) Multi-dimensional Random Walk
Sampler (MDRW) (Ribeiro& & Towsley| 2010). As for other methods, we set the hyper-parameter as the default in package Little Ball of Fur (Rozemberczki al. (020b). We replicate the experiments 30 times under each setting and compare the performance in terms of MAE for all methods. All the experiments are conducted on machine with a 40-core NVIDIA Tesla V100 GPU (3.00 GHz).
5.1 DATASETS
Synthetic Dataset We generate synthetic datasets by the stochastic block models (SBM) and degree- corrected block models (DCBM), which can assign the community distribution to each node. We set the community proportion as (3/4 4, 1/10, 1/12, 1/15) with 900 nodes in total. The out-in-ratio (the ratio of between-communities edges over within-community edges) controls the ratio of the number of edges between the communitics and within a community. A higher ratio represents a noisier graph. The degree-corrected model corrects the node degree by power-law distribution. Given the probability of an edge within a community (pin. = 0.8), we vary the probability of an edge between communities (Pout) (f0.06, 0.08, 0.10, O. 0.]2)) and subsampling proportions (40.1, 0.12, 0.14, 0.16)) from low to high for both block models to observe how our method performs as the setting becomes more challenging compared with others. More details about the generation of the DCBM datasets are presented in section B.I. I.I. in Appendix.
Real-world Dataset We use five widely-used read-world graph datasets with labeled community structures to validate the performance of our method, including Polbooks, Facebook. Cora, Polblogs, and PubMed (Rossi & Ahmed| [015] |Rozemberzzki et al., 22200a; Sen et al. 2008). All these graphs are considered unweighted and undirected. Besides, all the self-loop edges and isolated nodes are removed. Table Table|A.4jn in the Appendix summarizes the network statistics of these datasets. As we can see, the number of nodes ranges from 105 to 19,717, and the network density ranges from 0,0001 to 0.04. Thus the networks we considered span wide range.
5.2 RESULTS OF SYNTHETIC DATASET
The subsampling time for estimating M is set as 3, which is enough to get a stable estimation result (Li et al. 2020). The results of SBM and DCBM datasets are reported in Figure 5 The error bar is the standard deviation of 30 replications. We the subsampling proportion (prop) as 0. when varying the probability of an edge between communities (pout) and set pout=0.06 when varying the prop. Our method can get more accurate estimation of M than other methods. More details about the table of results, including each combination of pout and prop values, are presented in Table A. and A.2 in Appendix. We also compare the computation time for estimating M by using the whole graph and the subgraph. turns out that the time for estimating the subgraph together with the time for subsampling still much shorter than the time for estimation the whole graph. It is consistent with our conclusion about the complexity of the algorithm. Details about computational time are presented in Section B.1.2 in Appendix.
IOOOOT
OUR DINRECY
Figure The function performance MAE respect to poul and prop for DCBM datuset.
8

---

Published as a conference paper at ICLR 2023
5.3 RESULTS OF REAL-WORLD DATASET
We compare the performance the proposed ORG-sub algorithm with subsamples generated by different algorithms by MAE defined above. Table records the average error of the estimation of M over 30 replications. Still, our algorithm outperforms other algorithms in most cases. Let Bi....y RM denote the number of nodes in M communities. Here, we calculate the normalized Shannon Entropy of ......, RM as a metric to measure the imbalance level, i.e., we calculate IM log Zi=1 log and higher IM value means that the communities are more imbalanced. Table|A.4] in the appendix summarizes the IM. As we can see, both PubMed and Polbooks are more imbalanced than Facebook. From Table we observe that the ORG-sub performances of PubMed and Polbooks the community of the graph is more imbalanced. The true M each dataset is recorded in the first column of Table We tested the performance of different algorithms with broader range of sampling proportions ranging from 0.5% to 30%. In particular, for small-sized networks Polbooks and Facebook, we consider sampling proportions 10%, 20%, and 30%. For medium-size networks Polblogs and Cora, we consider 5%, 10%, and 20%. For large-size network PubMed, we consider 0.5%, 2%, and 5%. In addition, the computation time on the subgraph (together with the subsampling time) is still much shorter than on the whole graph. Details about computational time are presented in Section B.2.2 in Appendix.
better than that of Facebook. This shows that ORG-sub performs better when
Table I: Comparison the performance on emor
subsampling
Dataset
Prop.
ORG-sub
MHRW
CSE
FFS
SnowBall
DBN
RW
MDRW
10%
0.00
1.20
0.62
2.68
0.48
0.60
0.33
0.00
Polbooks
20%
0.00
0.19
0.52
0.30
0.70
1.76
0.37
1.60
True: 3
30%
0.23
1.00
0.43
0.37
0.93
1.60
0.37
2.00
10%
5.27
6.83
7.97
6.87
8.77
7.57
5.77
10.00
Facebook
20%
5.67
5.13
5.93
6.93
7.20
4.23
5.50
9.90
True: 11
30%
5.90
6.20
8.97
7.13
8.77
7.27
8.97
10.00
5%
2.27
2.33
4.93
5.97
3.77
3.10
1.30
4.60
Cora
10%
3.40
1.53
4.97
3.40
3.00
3.37
3.87
5.80
True: 7
20%
2.53
2.97
5.00
3.90
4.80
4.80
2.73
5.47
5%
0.00
1.87
0.90
2.00
0.43
1.33
1.03
0.30
Polblogs
10%
0.00
0.40
0.33
0.20
0.03
0.03
0.07
0.87
True: 2
20%
0.00
1.87
0.90
2.00
0.43
1.33
1.03
0,30
0.5%
0.20
0.30
0.30
0.50
1.00
0.70
0.30
1,90
PubMed
2%
0.00
0.30
0.80
0.40
0.20
0.70
1.20
1.80
True: 3
5%
0.30
0.55
0.55
1.40
1.65
0.65
2.20
2.75
CONCLUSION
In this paper, propose novel Ollivier-Ricci Curvature Gradient-based graph subsampling (ORG- sub) method that samples a subgraph by maximizing OR curvature gradient. The contribution of the ORG-sub method to the graph subsampling research line is three-fold. First, the best of our knowledge, we are the first to utilize the graph's 's internal topological information to subsample large graph that preserves the number of communities. Second, the best of knowledge, are the first to bridge the gap in the consistency theory regarding subsampling algorithms for the number of community estimations SBMs. In particular, we theoretically show that ORG-sub effectively traverses different communities and avoids trapping in one community. In addition, we theoretically show the advantage of ORG-sub over a popular sampling method, random walk. Third, we empirically show that our method has superior performance over existing subsampling algorithms terms estimating the number communities. An interesting future direction we plan to investigate is to extend the theory of our method to SBM variants, including degree-correlated SBM, overlapping SBM, and multi-layer SBM. Another future direction to investigate other community-relateer statistics that method has preserved. In fact, have empirically observed some promising results in preserving the clustering coefficient (CC). Empirical results can found in Section E in Appendix. In the future, will investigate the consistency theory of CC.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Thanks to the partial support by NSF awards DMS-1903226, NIH grant RO1 GM1222080 We would like to thank the referees for their valuable comments and suggestions that helped to improve the quality of this paper. We appreciate the time and effort the referees put into the review process, and we are grateful for their contributions.
DMS-2124493, and
REFERENCES
Lada A Adamic, Rajan M Lukose, Amit R Puniyani, and Bernardo A Huberman. Search in power-law networks. Physical review E, 64(4):046135, 2001.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed Massively scalable sinkhorn distances via the nyström method. Advances in neural information processing systems, 32, 2019.
Arash A Amini, Aiyou Chen, Peter Bickel, and Elizaveta Levina. Pseudo-likelihodd methods for community detection in large sparse networks. The Annals of Statistics, 41(4):2097-2122, 2013.
Frank Bauer, Jürgen Jost, and Shiping Liu. Ollivier-ricci curvature and the spectrum of the normalized graph laplace operator. arXiv preprint
2011.
Marian Boguna, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M Serrano. Network geometry. Nature Reviews Physics, 14-135, 2021.
Kehui Chen and Jing Lei. Network cross-validation for determining the number of communities in network data. Journal of the American Statistical Association, 113(521):241-251, 2018.
Minas Gjoka, Macicj Kurant, Carter T Butts, and Athina Markopoulou. Walking in facebook: A case study of unbiased sampling of osns. In 2010 Proceedings IEEE Infocom, pp. 1-9. leee, 2010.
Benjamin H Good, -les-Alexandde De Montjoye, and Aaron Clauset. Performance of modularity maximization in practical contexts. Physical Review E, (1)):046606, 2010.
Leo A Goodman. Snowball sampling. The annals of mathematical statistics, pp. 148-170, 1961.
Adam Gosztolai and Alexis Arnaudon. Unfolding multiscale structure of networks with dynamical ollivier-ricci curvature. Nature Communications, 12(1):1-11, 2021.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Pili Hu and Wing Cheong Lau. A survey and taxonomy of graph sampling. arXiv preprint 1308. 5865, 2013.
Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In 2008 Eighth IEEE International Conference Data Mining, pp. 183-292. IEEE, 2008.
Jürgen Jost and Shiping Liu. Ollivier's ricci curvature, local clustering and curvature-dimensio inequalities on graphs. Discrete & Computational Geometry, 51(2):300-333 -2220000-222000 2014.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
Vaishnavi Krishnamurthy, Michalis Faloutsos, Marck Chrobak, Li Lao. J-H Cui, and Allon G Percus. Reducing large internet topologies for faster simulations. In International Conference on Research in Networking, pp. 328-341. Springer, 2005.
John M Lee. Riemannian manifolds: an introduction curvature, volume 176. Springer Science Business Media, 2006.
John M Lee. Introduction to Riemannian manifolds. Springer, 2018.
10

---

Published as a conference paper at ICLR 2023
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, Pp. 631-636, 2006.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 177-187, 2005.
Tianxi Li, Elizaveta Levina, and Ji Zhu. Network cross-validation by edge sampling, Biometrika, 107(2):257-276, 2020.
Yong Lin, Linyuan Lu, and Shing-Tung Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, 63(4):605-627, 2011.
Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder. Global spectral clustering in dynamic networks. Proceedings of the National Academy of Sciences, 115(5):227-933 2018.
Lászłó Lovász. Random walks graphs: survey in combinatorics. Bolyai Society Mathematical Studies, pp. 353-397, 1996.
Shujie Ma, Liangjun Su, and Yichong Zhang. Determining the number of communities in degree- corrected stochastic block models. Journal of machine learning research, 22(69), 2021.
Arun S Maiya and Tanya Y Berger-Wolf. Sampling community structure. In Proceedings of the 19th international conference on World wide web, pp. 701-710, 2010.
Raghvendra Mall, Rocco Langone, and Johan AK Suykens. Furs: Fast and unique representative subset selection retaining large-scale community structure. Social Network Analysis and Mining, (4):1075-1095, 2013.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006.
Chien-Chun Ni, Yu- Yao Lin, Jie Gao, Xianfeng David Gu, and Emil Saucan. Ricci curvature of the internet topology. In 2015 IEEE conference computer communications (INFOCOM), pp. 2758-2766. 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, Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific reports, 91):1-12, 2019.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations.
Advances in neural information processing systems, 30, 2017.
Sofia C Olhede and Patrick Wolfe. Network histograms and universality blockmodel approxima- tion. Proceedings of the National Academy of Sciences, 111(41):4422-11472, 2014.
Yann Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique, 345(11):643 646, 2007.
Davood Rafei. Effectively visualizing large networks through sampling. In VIS 05. IEEE Visualiza- tion, 2005., pp- 375-382, IEEE, 2005.
Bruno Ribeiro and Don Towsley. Estimating and sampling graphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM conference Internet measurement, pp- 390-403, 2010.
Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic stochat blockmodel. The Annals of Statistics, 39(4): 1815-1915, 2011.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. htt.:httpa./nnewworrkeeeeee tory.com
ptt.tpa:/nnetwwoe
11

---

Published as a conference paper at ICLR 2023
Benedek Rozemberezki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In Proceedings of the 29th ACM International Conference Information and Knowledge Management (CIKM 20), pp. 3125-3132. ACM, 2020a.
Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar. Little Ball of Fur: A Python Library for Graph Sampling. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM 20), pp. 3133-3140. ACM, 2020b.
Mostafa Salehi, Hamid R Rabiee, and Arezo Rajabi. Sampling from complex networks with high community structures. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(2):023126
2012.
Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of ricci curvature for complex networks. Scientific reports, 8(1):1-16, 2018.
Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93- 106, 2008
Seshadhri, Ali Pinar, and Tamara Kolda. Wedge sampling for computing clustering coefficients and triangle counts large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal, 7(4):294-307, 2014.
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-ricci curvature-based method to commu- nity detection in complex networks. Scientific reports, 1-1):1-12, 2019.
Felipe Maca-Ramírez and Tiago P Peixoto. Systematic assessment of the quality of fit of the stochastic block model for empirical networks. Physical Review E, 105(5):05431, 2022.
Pim van der Hoorn, William J Cunningham, Gabor Lippner, Carlo Trugenberger. and Dmitri Krioukov. Ollivier-ricci curvature convergence random geometric graphs. Physical Review Research, 3(1): 013211, 2021.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416 2007.
Jiangzhou Wang, Jingfei Zhang, Binghui Liu, Ji Zhu, and Jianhua Guo. Fast network community detection with profile-seudhe likelihood methods. Journal of the American Statistical Association, pp. 1-14, 2021.
Tianyi Wang. Yang Chen, Zengbin Zhang, Tianyin Xu, Long Jin, Pan Hui, Beixing Deng, and Xing Li. Understanding graph sampling algorithms for social network analysis. In 2011 31st international conference on distributed computing systems workshops, pp. 123-128. IEEE, 2011.
YX Rachel Wang and Peter J Bickel. saeeihoood-basel model selection for stochastic block models. The Annals of Statistics, 45(2):500-522 2017.
Yanhong Wu, Nan Cao, Daniel Archambault, Qiaomu Shen, Huamin Qu, and Weiwei Cui. Evaluation of graph sampling: A visualization perspective. IEEE transactions on visualization and computer graphics, 23(1 4011-4111. 2016.
Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, and Chao Chen. Curvature graph network. In International Conference on Learning Representations, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2019.
12

---

Published as a conference paper at ICLR 2023
Appendix for "Subsampling for Large Graphs Using Ricci Curvature"
The appendix shows the details of the proof, details of experiments, including the parameter settings of generating the synthetic datasets, a description of real-world datasets, and more experiment results on synthetic and real-world datasets.
A PROOF DETAILS
Lemma A.1 (Ollivier-Ricci curvature of random graphs generated by stochastic block mod- els). Consider a graph with M communities generated from a stochastic block model (SBM) B in the same community By, Pout represents the probability of an edge connecting nodes from dif- ferent communities, and {nz are the sizes of each community in the SBM. We assume that, for (i) any = L,..,,,, Pin > Pout- and The converges to TT(1 > T4 > 0). as n goes to infinity. Let my max {ms) and pv max { (Pirs Simi We denote the node x from the community By by xnd the edge (I YB,) where x is from B3 and y is from Bj, and the edge's OR curvature by s( yR.) The following statements hold the OR curvature.
(1) (Pnn {1 PPotts {mr)i=1), where Pin represents the probability of an edge connecting nodes -
(6) (
(6) 1. If Pout (m4-1)lan and Pin n4 + Pout - n;) In ni, for the lower bound of nIn.s
wothin-community OR curvature, we almost surely have
(n: 2)p,,n (1) (n Puu
O Inn Pown
(BB,.BB.)
(11)
(ny 1)p + (n n4)
(1) 2. If Pio. n Pout
+ (n nn) 4 no. for the upper bound of witthi--commniing OR curvature, we almost surely have
In:;
(LB,,,B,)) S 5P + O
(12)
3. If Pout (31mml)/ /
(6) (n: nz)) + n. n2 for the upper bound of between-
Pous
communities OR curvature, we almost surely have
K( UB,)
11
m1 Pout + ni m2 - 2
pv + +0(
Pv Inn
(13)
Pouth
We will Chernoff's inequality to prove the lemmas.
Lemma A.2. (Chernoff's 's inequality) Let X1, Xn be the independent random variables with
P(X, = 1) = P.. P(X: = 0) = 1
(14)
We consider the sum X Ei X,, with expectation F(X) -.TmP:
Ps. Then have
(Lowertail) S F(X) A) S xx//2E(X)
(15)
(Uppertail) Z E(X) x) X2/
(16)
WLOG, the proof of the theorem considers the situation when M = 2. The conclusion can be easily generated to any arbitrary M by setting one block as block B,, and the other blocks as another block B2. Before prove the theorem, need few lemmas.
13

---

Published as a conference paper at ICLR 2023
(4) Lemma A.3. Pin n4 Pout T1:) > In ni then the degree of all nodes in block B3 fall in the
range Pin (m. 1) Pout (n n1))
V 4(p m n, + Pout (n n4)) In PM (n, 1) + Poue(n
(6) n,) + V 6(pm ns + (n - n4)) In n:)
with probability at least 1 2/n4.
Proof. Without loss of generality, we just prove the first statement and the second statement can be proved in the same way.
For each vertex v in block B;, it is easy to show that the expected degree of vertex v is F(d Pin (m: - 1) + Pout - n;). Applying Chernoff's inequality with the lower tail V //(p (f n; + Pour(n (n - ni)) Inng we have
P P - (pin (ni - 1) + Pona(n mi)) S- -V
-V4(V/pp 14(p ns Pone (n - nz)) In
(17)
-Mp ny (oo
S e 20x (n 1) Po wil)
(18)
n
Applying Chernoff's s inequality with the upper tail X 66ppn (1) + Poucln n4)) Inn, we have
P(ce - (pin (n: - 1) - Poue (n mn)) 2 v 6(pmn n. + Doue - -ni) Inns)
(19)
oolo (8) (n m,,1 Inn;
I e 200 (1) u2122//33 ocr!"! Pour
<
1
(20)
n
In the last step, we used the assumption Pin n, + Pout
n₂)
8 In m4. The probabil-
3
(p (m4 - 1) + Poue(1 - n4))
ity that there is a vertex v in block B; so that dB & Pin
V 4(p.n (1), n, + Poue(n nz)) In n (1) (n, - 1) + Pout (n - ni) + v 66p Pout (n n2))) In ns
is at most ne
1 + m
2
The co-degree day of a pair of vertices (x, y) is the cardinality of the common neighborhood of a and y. Roughly speaking, when Pin and Pout is large, the co-degree follows the binomial distribution; when Pin and Pout is small, the co-degree follows the Poisson distribution. We can expect that all
(i)
co-degrees within a block and between blocks concentrated around a small interval.
(6)2 Lemma A.A. If Pin na + Poue -n,) > 4 ni, then with probability at least
(i)2
1/n, all co-degrees of pair of vertices in block B, fall in the range (Pmn (n:
(8) 2) + Dour?(n n4) V 6(p + Pn nz)) Inn,, Pin (n: 2) + Pout 2 ni) +
(1) V 9 ni Dout 2 n.)) In Inmi)
(3) PPn Pouttii + PoutP ny + Poat (n-
(8)
2 (n-nn;-)) - > 3 31 noy then with probability at least - 1/n all
co-degrees of pair of vertices in blocks B; and fall in the range Pin Pout (1, (11;-11+mp 11)+ (n (n-
(8) + Pin Pout (1) 6(p Po T4 + PoutD (6) in nj + Pout 2 (n - n4 - n2))) In my P Pous (n=-1) m1j In lnmy)
Pout 2 (n (n- -14) + Pén Pont (ng 1)+ / (9 Pontis + Ponttin n2 + Pont 2
(2)
(i)
Proof. For a pair of vertices x E B, and E B, the co-degree dz is the sum n 2 indepen- (6) dent random variables X1, X with expectation F(dd)n.)..) Pin (n: 2) + Pout (n nz).
14

---

Published as a conference paper at ICLR 2023
Applying Chernoff's 's inequality with the lower tail X = Vo(pin? ns + Pout - n2)) In ns, we have
(6)2 P d Bigh (win (n: 2) + Pout (n n;)) < - Volo ? + Pour n.)) n:)) Inns)
(21)
( ni Ipaut (n mz))ian
(1) (y 2) (a my)) 1
S 2irin
(22)
2
If Pin + Paus pn - ni) > 4lnn, we apply Chernoff's inequality with the upper tail À
2
(pin n, + Pout 2 -n;)) In In
P P(dze.ge, -vi: (n4 2)) + Pont (n (2)) V 9(pm
(1) ny + Poat ni)) Inn,)
(23)
aipi n4 Pout ((n-m;)) In:;
Se 2(plf)2 (o ()) olr "o (n-m,))
(24)
Now the number of pairs is at most nł /2. the sum of the probabilities of small events at most
2
For a pair of vertices x E B, and y E By, the co-degree d is the sum of 2 in-
dependent random variables XI, Xn- with expectation E(d,=.,")) Piu Pour 1) Pont" (n- - πj - nz) + Pen Poue (n, - 1). Applying Chernoff's inequality with the lower tail A V V6(p Pouets + Pouep!n ny + Pout (n n2 n2)) In nv. we have
P P(dze1y02 - Poue (n= 1) + Pout 2 ny - ns,) + Pin Pour - 1))
(25)
V 660 Po + PoutPin (6) ny + Pout (n ns n1)) Innw)
(26)
(elnny)(rff (9) Poueln - 1)t Pto tn (1))
269 (2) youtlng D) me Poue
<e
(27)
(8) If Pin Poutt + PoutPin n2 + Pout In n, n4) > 4 Inn we apply Chernoff's inequality with the
/ (p( Pounns + PoutPin (1),, n, + Pout?(r - n2, n2)) In ny.
upper tail
P (d Poul (n; + Pont 2n -nn 1 n.) Pin Pout Pour (ng 1))
(1)
(28)
V 1o Poutto + PoutPin (1) nj Pout 2n n4 nz)) In
(29)
Pauen + (9) P
(m- 2
< <e 26r Pout troee
(9) ny trout ( -n +2//)))22/////)/1 virl9 Pour Poutnit my tout (mn-n; -n)))
(30)
(31)
n 3
The number of pairs is at most ny the sum of the probabilities of small events is at most (nv") 2)
Referring to the lemma mentioned in Lin al. (201T), can construct the lower and upper bound of the Ricci curvature of graphs generated by the stochastic block model.
Lemma A.5. Suppose that á [(x)\N(y) > (N)) is an injective mapping. Then we have
<(x. v) 2 1 1 dy (e))
Σ
(())) +
1
3(d, dx))
d,
dg
15

---

Published as a conference paper at ICLR 2023
1
W (m mg)
dzy +1 d2
1
<(z,, y)
lim a-+1 1
+
dy
Lemma A.6. For the lower bound, we will construct matching M from (xx) as follows. Let Un = (()))N(())) and Vo = (()). Pick up a veriex un E Un. Reveal the neighborhood of u1 in Vo. Pick vertex the neighborhood, and denote it by vj. Let U1 Uo {u and V1 Ve and continue this process. The process ends when l( n V2 0. The probability that the maximum matching between Up and Vo at most is less than
[(y)
n Pout 1Vol < (1 Pout) Vol- V Inn
e Poue( -k) S no Poue((Vol-R))
p
Choose k [1Vol - (3 1/mn//p. With probability at least 1/n², there is matching M of size between ((r))N(v) and ((r).
Now we extend the matching M to an injective mapping ø (())\N()) - (V)) arbitrarily. Applying Lemmas A.6 with probability at least 4/n, we have
x(I,1)
dy Σ d(u,o(u)) + d
1
3(dy - dx)
dy
NET(x)) (W))
3(d, - de)
(k + 3(1Vol - k)) + dr
dy
dy
dzy 2(3 In n nn/Pur).
3(d, - dr)
dy
dy
dy
Proof. Given the range of the degrees and co-degrees, lower bound and upper bound of Ricci curvatures with respect to d and dzy, we can prove the remark of Lemma A.I as follows.
For vertex x E Bi E Br, given Pin n, + Pout (n - n4) > n,, we have
(6)
(0) + n222 + + (n n4) + 9 In (niv
(n: 2)p
k(ZB,, UB, <
(n: 1)p (3) + (n ni)pout v A(napto (1) + (n n Pone) lun;
(6)
O Iu
Pin
(8) For vertex Bi,y E Bi, given Pin n, Pout 2(n mi) > 4lm have
16

---

Published as a conference paper at ICLR 2023
(n: 2)pbn (6)
(1) + (n - na) -n)pout 2 - V ( (
+ (n- -
x(IB..BBL
(n: 1)pbn (n no)pout + 66 (i + (n ne Pous)
In n Pouu
(n: 11)p + nePout + In in (0) + (n ni)Pout)
6y ( 10 + (n - mn))oot)
(n. 1) + (n - nn)Pout + 44mn, (0) + (n T4 no)Pout) (
(n+ 2)p,n + (n n4 Pout 2
0 Inn Dout
Pin In Pont
(t)
)
(n, 1) 1)p (n nz)
(n+ (1)2
+ (n n: Pout
In n Poue
Pin P
(t) In ni
O
(n; 1)pm + (n na)Pout
Pon If Pout Pin
(ln,) alan." we have x(.)),yn))) (n. 2)p + (n- Pout
O(_Inm Inn Your
(n:- 12pl + (n-n,nnnn Pouu
(2) M
For vertex
Br. E By, let ny max {mr) and pv max {Pin
If Pout >
Si=1
(3lnnw/ /
Pin Pout
(n: + nz) + nn R2 we have
3 In ny [nn - 1)p (6) x(EB.V0,)
Pout + (n - ni - nn)Dbbt + (ng 1) Pout)
(n4 1)p:0 -ypoout 2/ In no (nop:n (2) + -ns,oou))
+ 1 + (n: 1)p Pout + (n- - n1; - 11 nn;Yoou + (ng 1) Pont
(n; - 1)p,00 + nyPout
2/ In no (nappin + nnsPout)
1
(ng -1)p( + -iPPout 2 Innv(rypp (1) + n:Poutt
3/ In nwl - 1)D Pout + (n ni 122) n2j)Pout + (ng 1)mh () Pout] +
(n 1) ///ppv Inn
+ (n: 1)p:n Pour + (n n2 n2 n2) + +nng - 1)p Pout
(n 1) 2/mpp Inn
(5) (v
(1)
+ +pin + Powt) In my + n4 + n2 - 2
Pv + n2 - n2 - n2
50(1
Pout
(n Pout
Lemma A.7. Combining the conclusion of statement 7 and statement in Lemma A.l almost surely, for any (A VL,)) E A ((x we have
Pout (p Pont)
|n(28, VB.) - k(x'g, Sn
+ o
(32)
n: Pmm + Pout
Ponene
Proof. We can prove the Lemma A.7 by the lower bound and upper bound of the within-community edges' OR curvature from Lemma A.1
17

---

Published as a conference paper at ICLR 2023
Theorem A.8. Combining the conclusion of statement 1 and statement 3 in Lemma A.1 if pv
Pin
(
Paus (n- (n)(nn++4))))) and conditions given in Lemma A.I almost surely, for any
Ret
Pin
n² ---1n, (1, +
(o UB,
E (((TB, (B.) )), we have
IN(a,,, - x/B < k(an,, k( (2'n, Vn, (EA((ER, (e,
max
(33)
Proof. We first get the lower bound of the OR curvature difference of within community edge k( (B. and between community edge k( VB,)). which can be obtained by the lower bound of n( yn,) and upper bound of k(2B,, MB,)) from the Lemma A.1
Given the upper bound the OR curvature difference of edges in the same community, we can prove under certain conditions, the upper bound is smaller than the lower bound we obtained in the last step. Denote ri ni/n and = nj/n.
K(2n,, B, vB,) (K(1,, un.) K(3'B, v/B,))
(34)
(n: -2pp (1)²
+ (n n: ni)Pont"
n T4i f2
71 11 - 2
Pout (Pin Pout)
(n: 1)pmn (n ni Pout
Pout
n pv)
(2)
no Pin Pout
(35)
(
TiPin + (1 - Po)Pout?
(1- Pouse (p -oou) riPin (4)
Pout (ri (ritrr)(p Pout)
+ +
TiP + (1 Po)p
(5)
+ (1 ri ri)Pout
(36)
TiPPn + 2(1 T:)Pout
(
(1 Poutt (1)
TiPin Pout (1 - Ti)Pout
(9)
(37)
(4) (1 P:)
rePmn
(r: +ryrrs(p - Pont 1m (r: + +;)((1 - r:)Pone - Pont) + 0 )
riPan + (1 rr))) Pout
(i)
m
(38)
(9) Pin (1 pu(r; + r,)) + Pout (Poue rr)( +ra pv (n 2r:)))
-
r:Pmn + (1 - -r:)Pout
(39)
+ 00 >0
(40)
Theorem A.9 (Probability of the ORG-sub's Expansion to Communities). Given the graph G generated by Theorem A.8 we apply the ORG-sub Algorithm 7 to the gruph G and take graph subsamples with size ñ denoted by G[S), Under the conditions in Theorem A.8 and if î/nn + 1, we can prove that, the probability of the final subgraph G(S) taken by ORG-sub containing nodes in the community B, is:
P(v E B, | E G(S)) +1
(41)
Proof. Without loss of generality, we show the theorem holds for two-block stochastic block model (SBM).
We assume the graph is generated from a two-block stochastic block model (SBM), where the probability of an edge within block is Pix. and the probability of an edge between the blocks is Pout- We denote the subsampled graph from the original graph G by G[S), where S is a subset of the full vertices set V of graph G, and G[S] is the subgraph induced by the subset S. Denote the probability matrix of generating the adjacency matrix A by P:
Pin 1 n: IT
Pout n1 IT
P =
Pout Ing 1
Pin Ing 1
(42)
P = p - diag {P*}.
18

---

Published as a conference paper at ICLR 2023
where the size of the first community is n1. the size of the second community is f2,, and the number of nodes of the graph is n = 71 + n2- The node set belonging to the community 1 is B1 = {UI,... Un, }- and the node set belonging to the community 2 is B2 +l..-t....... Denote each entry of the probability matrix P by Pij. then the observed A is generated from:
Aij Lid Bernouli(pry),
(43)
Define the block of the matrix as o = {ee = (v:: 12 v,)le, E Bo E Bug), where 01, Og E (1) and the neighboring edge set of edge (1,2). We denote the edge subsampled at the 1-th step by Cij eij by A(ei)).
For each step, the probability of subsampling an edge in a block is a constant. After subsampling one edge in each step, the nodes connected by the subsampled edges are subsampled into node set S. We denote the probability of adding node ü at the step belonging to community Bo, where E {1, 2]. by P( E B.). After steps, the probability of the obtained subsample G containing node from the node set B1 is:
P(ū E Bi U G[S)) =1 - P(( (00), ,,,,),,.. ,..,, -6m) & Bi)
=1 p(e ((c(f-2)
E 1
(x-3) E 2 P(e
(6-3) P(e(-3)
E 12 )
P(Cy) 11 E A
P(
(0)
E EA Pleg E
=1 - P() () A( () C -Aa²
P(A(e))) (0) C A ( E 22 P(c . E 2
(0)
=1 =1- - [(1 Pout) (1 (1 Pin)) nn2 2) n22
P(c
10 E 12
Analogously, the probability of subsampling node ē belonging to the node set B2 after steps is:
P(i E B2 u E G[S)) =1 =1 - P( 2(11) x((2)
B(m) ) $ B2)
=1 - P(e ()-) E 1 (8-2) E EA P(c))
(8-2)
E A E EA
P(C
(1) E P (0) EA .P(C) EAat)
=1 - P(D(C)) (5-3)) C A (f-4) C A
P(A(e))) (0)) C (1 EΛ'l). .P(c)
(0)
E EA'l)
=1 =1 - [(1 - Pout) "2 - -(1 - Pin)) ) -3)] R-2 P(e E "
(1= (1 (1- pim) ((1 Pout) (2 (1 Pin )²1) can be small when nı (n2) and ñ is large, the proposed ORG-sub subsampler can traverse to new communities with high probability. When Pout is small, that is, the edges density between communities is relatively small, the proposed ORG-sub needs more steps to expand to another community. As the traveling steps of the proposed subsampler ORG-sub increase, we can prove that the probability of the proposed ORG-sub algorithm taking all communities into the final subgraph converges to one under the two-stochastic-block model.
Since (1 Powt)
In general cases, the graph is generated by SBM with multiple communities, we can always think of the community that the subsampler has never been to as one block, and other communities as the other block. Given the conclusion under the two-stochastic-block model, the ORG-sub can gradually expand the subsampled graph to the block we have never been to. Thus, we can prove the ORG-sub model.
can expand to any community under multiple-stochasticeee
Corollary A.9.1 (Theoretical advantage over random walk). Under the assumptions in Theorem 4.1 for any community B, in graph G. we have
P(uRW E B, / E G(S)) P(u E B, U U G(S)).
(44)
A.9 has proved that after walking ñ steps, the probability of the obtained subsample G [S] by the proposed ORG-sub containing vertexes v from community
Proof. For the proposed method, Theorem A.9
19

---

Published as a conference paper at ICLR 2023
B, is:
P(e E Bi I u G[S]) =1 Pleyj ( P(c/--) 10 E A P(cj
E 1 (00)e1//44 A E A P(e,) (0) AAa)
(f-3)
P(ej) (1) P
(0)
=1 -1-1PP P(A(E)) (1-3) C A [((]) A(())-1)) ()) C A
)(
(0)) C. A laj A) P(eij A
(0)
(0)
After ñ steps, the probability of the obtained subsample Gaw [S] by the random walk subsampler containing vertexes in community B; is
P(URW& E B, u G[S]) =1 P(e ())) 1 (f-33) A P(e)) ((c/A-3) E 1 (8-))((-4) E -A00)...
P(c E A
(1)
(0)
EAT)
P(c)) (0) E 210))
=1 =1- - P(A (A-3))
A + 2 ( (1--1) C (A88)4
PIA(E)) (f-33)
C A
(/ (h-4)) C CA00)
PP(ACE))) (0))
\ + 0
(0)) C CA00)+
P(A(E)) (0)) C AA (0) E < P(ey) (0)
E EA39).
80 Corollary A.9.2. If the subsample with size ñ satisfies log ñ > s0, where p is the edge density, as the subsampling times r + 0o, the probability the subsampled graph underestimates the true M is:
Pr( Σ M[GGS)) < M) + 0.
(45)
Proof. From Theorem A.9 we know that, if we take enough steps for subsampling, the true number of communities ((G [S]) of subgraph G[S] is the same as the true number of communities M of the original graph G. Theorem 3 of et al. (2020) proves the one-sided consistency of estimating the number of communities of the stochastic block model under the following assumptions. First, the expected node degree A,. np has the order An To where is the number of nodes of the graph G. Second, there exists constant y such that ming n& 2 ?NN, where ny the size of the k-th community. Since our subsampled graph satisfies äp.
Tog 7 oo, we can easily verify that the subsampled subgraph satisfies the assumptions in Theorem 3 of al. (2020). The estimate of the number of communities MG(())) corresponding to S,, the i-th subsample, satisfies:
(G < M(G()))) + 0, (r(M)) < M) + 0.
(46)
As the replications of the subsamples increase, it's trivial to show:
Pr M(G[S.)) < M) - 0.
(47)
B DETAILS OF EXPERIMENTS
We evaluate the performance of our algorithm on both synthetic datasets and real-world datasets using the metrics presented in the main context. We also compare the proposed method with seven benchmark exploration based graph subsampling methods, including Metropolis Hasting Random Walk Sampler (MHRW), Forest Fire Sampler (FFS), Snowball Sampler, Community Structure Expansion Sampler (CSE), degree-based node sampler (DBN). Random Walk Sampler (RW) and Multi-dimensional Random Walk Sampler (MDRW). We set the hyper-parameters of the seven
20

---

Published as a conference paper at ICLR 2023
methods as the default in the package Little Ball Fur. The rejection constraint of the MHRW method is set as 1; the burning probability of FFS is 0.4; the bound on the degree of Snowball Sampler 0.5.
used to calculate the Ricci curvature of graphs is set The times of subsampling in A Algorithm 2 for estimation of the number of communíties set as 3, which is enough get stable estimation result. All the experiments conducted workstation with 40-core NVIDIA Tesla V100 GPU (3.00 GHz).
set 50. The tyyper-paaameee
B.1 EXPERIMENTS ON SYNTHETIC DATASETS
B.1.1 PARAMETERS SETTINGS
We stochastic block models (SBM), and degree corrected block models (DCBM), which assign the community distribution to each node. To create graphs with unbalanced communities, we set the community proportion as (3/4, 1/10, 1/12, 1/15) with 900 nodes. The out-in- out-in-ratio controls the ratio of an edge's probability of between-commmniitec and within-community A higher out-in- ratio represents noisier graph, i.e., harder distinguish the community from the graph. We the probability of an edge within a block as 0.8 and vary the probability of an edge between blocks (pout) for both SBM and DCBM (f0.06, 0.08, 0.10, 0.12)). The higher the pout value (higher the out-in-ratio) is, the noisier the subsampled graph is. We also change the subsampling proportion 00.1, 0.14, 0. 0.16)) from low high for both block models observe how our method performs compared with others the settings change. The degree corrected model corrects the node degree using a power-law distribution. More parameters need to set before generating the graphs following DCBM. We set the average node degree 40, with is consistent with the setting in Li et al. (2020), in which the assumptions our algorithm hold. The node degree follows power-law distribution with the lower bound as 1 and the scaling parameter 5.
B.1.2 ADDITIONAL RESULTS OF SYNTHETIC DATASETS
Table A.I: DCBM: Eror of the estimation the number of communitics for different subsampling methods under different settings.
Pout
Prop
ORG-sub
MHRW
CSE
FFS
SnowBall
DBN
RW
MDRW
0.10
1.50
2.83
2.83
2.73
1.53
2.60
2.77
3.00
0.06
0.12
1.40
2.77
2.77
2.60
1.90
2.63
2.73
3.00
0.14
1.57
2.53
2.73
2.33
1.80
2.57
2.57
3,00
0.16
1.63
2.50
2.80
2.23
1.80
2.30
2.53
3.00
0.10
1.30
2.97
2.83
2.70
1.53
2.77
2.80
3.00
0.08
0.12
1.57
2.77
2.83
2.77
1.80
2.53
2.53
3.00
0.14
1.57
2.90
2.83
2.70
1.80
2.40
2.67
3.00
0.16
1.63
2.77
2.63
2.53
1.80
2.40
2.53
3.00
0.10
0.93
2,83
2.93
2.83
1.37
2.63
2.80
3,00
0.10
0.12
1.63
2.90
2.87
2.60
1.83
2.50
2.73
3.00
0.14
1.53
2,80
2.77
2.70
1.93
2.47
2.77
3.00
0.16
1.73
2.83
2.77
2.57
1.70
2.57
2.63
3.00
0.10
0.93
2.93
2.90
2.73
1.6
2.77
2.93
3.00
0.12
0.12
1.40
3.00
2.77
2.73
1.60
2.73
2.80
3.00
0.14
1.57
2.93
2.73
2.47
1.80
2.73
2.77
3.00
0.16
1.60
2.90
2.67
2.50
1.87
2.60
2.67
3.00
We use synthetic datasets with hidden community structures to evaluate the performance of our method. We replicate the experiments 30 times under each setting and compare the performance of the еттоr of estimation of the number of communities and the computation time. The average of replications of each setting recorded in Table A. and Table A.2. these tables, Column Prop denotes the subsampling proportion, and column Pout denotes the probability of an edge between communities. The rest the columns are the results different subsampling methods. The performance of our algorithm is better than that of other methods. As for the results for SBM in Table A.2 the еттоr of estimating the number of communities decreases as the subsampling proportion increases, and the error increases the observed graphs noisier (pout increases). As for the computational time recorded in Table A.3 for SBM, we observe that the estimation time of the full sample is orders of magnitude larger than the time of subsampling and estimation. As the
21

---

Published as a conference paper at ICLR 2023
Table A.2: SBM: Eivor of the estimation of the number of communities for different sabsampling metheds under different settings.
Pout
Prop
ORG-sub
MHRW
CSE
FFS
SnowBall
DBN
RW
MDRW
0.10
0.47
1.70
1.93
2.00)
2.33
2.00
2.00
3.00
0.06
0.12
0.33
1.67
1.80
1.93
2.20
2.00
2.00
3.00
0.14
0.10
1.77
1.77
1.93
2.13
2.00
2.00
3,00
0. 16
0.00
1.73
1.30
1.97
2.07
2.00
2.00
3.00
0.10
0.63
1.77
1.60
1.87
2.23
2.00
2.00
3,00
0.08
0.12
0.37
1.73
1.70
1.83
2.17
2.00
2.00
3,00
0.14
0.03
1.87
1.53
1.80
2.07
2.00
2.00
3,00
0.16
0.07
1.83
1.67
1.83
2.03
2.00
2.00
3,00
0.10
0.80
1.77
1.73
1.93
2.20
2.00
1.97
3.00
0.10
0.12
0.33
1.73
1.67
2.00
2.17
2.00
1.93
3,00
0.14
0.13
1.80
1.63
1.90
2.03
2.00
1.93
3,00
0.16
0.03
1.73
1.60
1.97
2.03
2.00
1.93
3.00
0.10
0.73
1.67
1.83
1.87
2.07
2.00
2.00
3,00
0.12
0.12
0.53
1.60
1.57
1.93
2.03
2.00
2.00
3,00
0.14
0.33
1.63
1.53
1.93
2.00
2.00
2.00
3,00
0.16
0.20
1.63
1.40
1.97
2.00
2.00
2.00
3.00
subsampling proportion increases, the computational time of subsampling methods increases. Though method's computational time is slightly larger than other subsampling methods, our method has better accuracy.
Table A.3: SBM: Comparison of the computation time of the estimation of the number of communitics between using the full dataset and the sampled dataset for different subsampling methods under differentt settings (secunds).
Pout
Full
Prop
ORG-sub
MHRW
CSE
FFS
SnowBal
DBN
RW
MDRW
0.10
1.11
0.42
3.27
0.43
0.44
0.29
0.37
0.28
0.06
22.52
0.12
1.21
0.48
3.76
0.49
0.52
0.49
0.54
0.37
0.14
1.41
0.54
4.41
0.53
0.62
0.21
0.33
0.23
0.16
1.63
0.66
5.12
0.66
0.67
0.42
0.44
0.38
0.10
1.08
0.42
3.21
0.42
0.43
0.32
0.41
0.26
0.08
23.67
0.12
1.27
0.49
3.87
0.50
0.53
0.25
0.24
0.20
0.14
1.47
0.57
4.50
0.54
0.61
0.25
0.26
0.25
0.16
1.71
0.65
5.23
0.66
0.68
0.53
0.67
0.50
0.10
1.09
0.41
3.25
0.42
0.43
0.38
0.42
0.32
0.10
15.67
0.12
1.30
0,49
3.91
0.50
0.53
0.27
0.28
0.17
0.14
1.52
0.56
4.57
0.54
0.61
0.26
0.34
0.26
0.16
1.78
0.65
5,28
0.66
0.68
0.57
0.68
0.52
0.10
1.13
0.42
3.28
0.42
0.45
0.18
0.24
0.22
0.12
19.65
0.12
1.38
0.48
4.11
0.50
0.53
0.24
0.32
0.20
0.14
1.61
0.56
4.71
0.54
0.61
0.45
0.56
0.43
0.16
1.89
0.65
5.39
0.68
0.68
0.41
0.49
0.43
B.2
EXPERIMENTS ON REAL-WORLD DATASETS
B.2.1 DESCRIPTION OF THE DATASETS
We use five real-world datasets to evaluate the performance of our method as well. These datasets are widely used as benchmark datasets the study of community detection for graphs. They can be easily found at KONECT, UCI network data repository and Stanford Network Analysis Project Rossi Ahmed (2015): Rozemberczki et al. (2020a); Sen et al. (2008). All datasets are considered undirected and unweighted graphs, and all self-loop edges and isolated nodes are removed. More details about the datasets are as follow.
Polblogs: The political blogs network dataset was collected by Adamic and Glance in 2005. A network constructed among all the posts published by liberal or conservative bloggers (two communities). Each node represents one post. An edge connects nodes if one of them is cited by the other.
22

---

Published as a conference paper at ICLR 2023
Polbooks: This is network of books about US politics published around the 2004 presidential election and sold by online bookseller Amazon.com. com. All the books are divided into four communities by NI-LPA. Edges between books represent frequent co-purchasing of books by the same buyers.
Facebook:
This is an ego-network dataset of the "friend circles" of one anonymous user on Facebook. The network forms friend circles such as family members, high school friends or other friends that are "hand-labeled" by the user.
Cora: The Cora dataset describes the citation relationship among scientific publications classified into seven classes. After preprocessing, there remain 2,485 nodes and 5,069 links.
PubMed: The PubMed dataset describes the citation relationship among scientific publications classified into seven classes. After preprocessing, there remain 19,717 7 nodes and 44,338 links.
Table A.4 presents the summary statistics for those real networks used in this paper. As see, these datasets cover different levels of network size, density, number fo communities, clustering coefficient (CC), and imbalance. The degree distributions of all the datasets are presented in Figure
A.1
Table A.4: Key features real-world datasets. Node and Edge represent number nodes, edges, and communities of the graph, respectively, Density the edge deusity, calculated by the ratio of the number of edges in the actual and complete graphs. CC is the clustering coeflicient the whole graph. IM inbulance
Dataset
Node
Edge
Density
Community
CC
IM
Polblogs
1224
16718
0.0112
0.2260
0.72
Polbooks
105
441
0.0400
0.3484
0.89
Facebook
725
13030
0.0248
0,4576
0.71
Cora
2485
5069
0.0008
0,0900
0.94
PubMed
19717
44338
0.0001
0.0537
0.96
Dhn
8-
3-
85
9ggss
Figure A.1: The degree distribution of the datasets.
Table A.S: Comparison of the computation time (secrnds) of the estimation of the number of communities berween using the full dataset and the sampled dataset each datasct subsample method with different subsample size.
Dataset
Full
Ricci
Prop
ORG-sub
MHRW
CSE
FFS
SnowBall
DBN
RW
MDRW
10%
0.10
0.05
0.07
0.08
0.10
0.05
0.07
0.04
Polbooks
1.88
0.29
20%
0.13
0.10
0.11
0.11
0.11
0.06
0.11
0.06
30%
0.14
0.11
0.12
0.12
0.12
0.10
0.11
0.07
10%
0.65
0.50
0.74
0.51
0.53
0.47
0.49
0.47
Facebook
29.14
0.71
20%
1.01
0.75
1.41
0.78
0.83
0.71
0.71
0.71
30%
1.96
1.56
2.83
1.70
1.69
1.48
1.53
1.49
5%
0.34
0.23
0.49
0.24
0.22
0.22
0.22
0.29
Cora
191.06
0.79
10%
0.79
0.66
1.54
0.65
0.56
0.49
0.60
0.73
20%
2.30
1.88
4.83
1.90
1.79
1.65
1.93
2.21
5%
0.23
0.12
0.13
0.23
0.13
0.11
0.22
0.12
Polblogs
48.6
1.49
10%
0.56
0.27
0.30
0.67
0.29
0.35
0.42
0.31
20%
1.18
0.49
0.47
1.01
0.48
0.50
0.67
0.44
0.5%
1.03
0.64
1.23
0.57
0.53
0.79
0.59
0.61
PubMed
NA
41.59
2%
4.42
3.93
11.84
4.13
3.50
2.63
3.58
3.43
5%
8.92
8.61
43.36
8.94
8.24
6.62
8.83
7.85
23

---

Published as a conference paper at ICLR 2023
B.2.2 COMPUTATIONAL TIME
The comparisons of errors in estimating the number of communities are presented in the main context. The computation time is also obtained in A.S] Similar to the synthetic datasets, the estimation time of the full sample is two orders magnitude larger than the time of subsampling (including the time for computing OR curvature for each edge in the graph) and estimation.
The result also shows that the computation time for estimating the number communities using the subsampling method is much shorter than that using the full dataset. The complexity of all methods influenced by the size the graph, especially by the number of nodes. It is no wonder that the computation time of all methods in estimating the number of communities for dataset Cora is much longer than other datasets.
B.3 ADDITIONAL EMPIRICAL RESULTS
In this section, we provide additional empirical results. In real-world networks, the ground truth is not available. We used some data sets that are widely used for community detection tasks, where the communities are labeled with domain knowledge. The manually labeled community structures correspond to different underlying aspects the nodes. For example, in the Cora citation network (where node represents paper), the community label corresponds to the paper's subject (c.g.. neural network). We agree that the manually labeled number of communitics might not the ground truth, which is limitation for real networks.
To overcome this limitation, we also employ another evaluation metric to assess the performance of methods. In particular, do not compare estimation with the manually labeled number of communities. We compare our estimation with the estimation obtained from the full data. These comparison results be used evaluate whether the subsampled subgraph to carry out computations of interest for the full data. Table A.6 shows the estimation difference between the subsampled and full graphs for four datasets, i.e. Polbooks, Facebook, Cora, and Polblogs. Here we do not show the results for PubMed, since the estimation results of PubMed full graph are not available due to prohibitive computation. As we can see, using this new metric, our method ORG-sub still outperforms other subsampling methods.
be good surrogate
Table A.6: The estimation difference between sampling full.
Dataset
Prop.
ORG-sub
MHRW
CSE
FFS
SnowBal
DBN
RW
MDRW
10%
0.08
0.66
0.39
2.79
1.08
0.29
0.20
1.00
Polbooks
20%
0.29
0.46
0.34
0.59
0.37
0.57
0.28
0.61
30%
0.13
0.75
0.34
2.86
1.11
1.80
1.70
0.99
10%
1.36
2.90
3.90
2.96
4.66
3.86
1.67
6.00
Facebook
20%
1.31
2.84
3.73
2.24
3.09
2.87
1.44
5.94
30%
1.20
2.91
3.70
2.11
3.23
2.71
1.42
5.85
5%
0.27
0.87
0.60
2.37
1.13
0.63
2.03
0.83
Cora
10%
0.80
3.90
0.47
0.80
0.60
1.60
1.13
1.33
20%
0.27
0.90
2.00
0.03
1.40
1.77
1.27
2.20
5%
0.00
1.87
0.90
2.00
0.43
1.33
1.03
0.30
Polblogs 10%
0.00
0.40
0.33
0.20
0.03
0.03
0.07
0.87
20%
0.00
1.87
0.90
2.00
0.43
1.33
1.03
0.30
C DISCUSSION ON EDGE DENSITY
Indeed, the performance of our method depends on the edge density from both theory and empirical results. On one hand, Corollary 4.1.2 basically assumes that p > log(a) where ň is the number of sampled nodes, and p is the edge density. When 7. = 100, we require p >> 0.046, and when ñ = 1000, only require 0.007. As the subsample size becomes larger, the constraint imposed the edge density becomes weaker. On the other hand, we include additional simulation studies to show the empirical performance of our method with different network densities. Particularly.
the same SBM setting in Section 5.1 to generate synthetic data, except that we let Pin = 0.8À and Pout = 0.1A, where À E {0.2, 0.4, ... controls the edge density level. Here, fix the sampling proportion as
24

---

Published as a conference paper at ICLR 2023
10%, that is, sample 90 nodes. Table A.7 shows the edge density and average estimation error under different X. As we can see, an increasing edge density comes with a lower error.
Table A.7: SBM Estimation entor of the number of communities with different edge deusity under the SBM model.
A
0.2
0.4
0.6
0.8
1.0
Density
0.1018
0.2034
0.3053
0,4070
0,5085
Error 2.7
2.1
1.8
1.8
1.5
D RELATED WORK ON GRAPH SUBSAMPLING
Existing graph subsampling techniques can be categorized into three main groups: node-based, edge-based, and exploration-basse
Node-based sampling. Random Node (RN) sampling (Leskovec & Faloutsos 2006) and Degree- based Node sample (DBN) (Leskove& Faloutsos 2006) sampling are two most common node-base sampling methods. RN selects a set of nodes uniformly at random from the graph, while DBN selects node with a probability that is proportional to its degree. DBN has been shown to favor high-degree
nodes.
Edge-based sampling. Random Edge (RE) sampling (Leskovec & Faloutsos 2006) generates an induced subgraph by selecting edges uniformly at random. Some variants of RE have been proposed, such as Random Node-Edge (RNE) sampling (Ratiei 2005) that randomly selects a node and then randomly chooses adjacent edge. Previous studies (Leskovec & Faloutsos] 2006 have demonstrated that neither RE nor RNE preserves community structures because the resulting sampled graphs often sparsely connected. Meanwhile, both RE and REN slightly favor high-degree nodes because the probability of selecting a node increases with its degree.
Exploration-based sampling. SnowBall sampling (Goodman 1961) and Forest Fire sampling (FFS) (Leskovec et (005)) are two basic exploration- based sampling methods, selecting a fixed fraction of neighbors visited at each iteration. Random walk (RW) (Lovász 1996) is also popular exploration- based graph sampling method, which selects the next node at random from the neighbors of the currently selected node. One of the major limitations of RW is that RW is inherently biased towards visiting high-degree nodes. To overcome the drawback of RW, researchers proposed Metropolis Hasting Random Walk Sampler (MHRW) (Hübler et al.. 2008) and muntti-dimensional Random Walk Sampler (MDRW) (Ribeiro & Towsley 2010). Most of the aforementioned literature aims at getting a subgraph that preserves some network summary statistics, such as degree distribution. Only few works aim at obtaining subgraph that preserves the community information. (Maiya & Berger-Wolli 2010) proposed a local greedy search-based community structure expansion sampling (CSE) method to optimize the preservation of community structures.
Despite many successful applications of existing graph sampling methods. They all have various limitations. In particular, node- based and edge-based sampling methods sample nodes edges independently, ignoring the neighborhoods of seed nodes. They might obtain a disconnected subgraph from connected graph (Wu al. 2016). For RW and FF, it has been shown that they could get trapped inside the communities and leave other communities out of the sample entirely (Wu et al.) 2016). While the MHRW algorithm ensures that the subgraph preserves degree distribution, the performance of this algorithm is dependent on its sample acceptance ratio. It has been shown that the acceptance ratio of MHRW typically very low in real-world networks. Therefore, MHRW generally suffers from the sample rejection problem, which clearly degrades the performance of MHRW. For CSE, the selection procedure of the next node not based on mathematical framework and one cannot compute the probability of visiting sampled nodes in CSE (Salehi et al. 2012).
E EMPIRICAL INVESTIGATION OF FUTURE WORK
Theoretically, the OR curvature has been proven to be related some network summaries concerning communities, such as the eigenvalues of the graph Laplacian Bauer et al. (20IT) and the clustering coefficient (CC) & Liu (2014).
25

---

Published as a conference paper at ICLR 2023
Empirically, calculated the CC value of the full graph and that of the subsampled graph for two real datasets: Facebook and Cora. We set the subsampling proportion to 10%. We replicated the sampling procedure 100 times and thus obtained 100 subsamples. Using these subsamples, obtained the 95% confidence interval (CI) by calculating mean + 1.96*sd sd (standard deviation).
For Facebook data, the CI of the CC value is [0.420, 0.537], and the CC value obtained from the full graph 0.476. For Cora data, the CI is [0.234, 0.290], and the CC value of the full graph is 0.238. As we can see, the 95% CI covers the CC value of the full graph for both real data sets. These observations suggest that our subsampling algorithm could preserve CC to some extent. The consistency theory on CC using our method is under investigation, and the results will be reported in future publications.
26


Reviews:
[{"review_id": "k25qhpg8E1q", "reviewer": "Reviewer_yo3s", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "\nThe paper is about a novel subsampling technique for large graphs defined in such a way that an important macro feature of large graphs is preserved.  It is stated that one macro feature often not considered is the number of clusters/communities, especially those without 'central' (high-degree) nodes are often left out in prior subsampling techniques.  The main claim here is that the Ricci-Ollivier curvature can help provide a better estimate of the number of communities, especially the marginal communities, ie those without nodes with high enough degrees.  The theoretical basis of the proposed subsampling algorithm (ORG-Sub) is this result: \"the ORG-subsampling provides a rigorous theoretical guarantee that the probability of ORG-subsampling taking all communities into the final subgraph converges to one\".  This statement is proven and ORG-Sub is applied to some synthetic and real networks to show that it has lower estimation error than prior work.", "summary_of_the_review": "\nThe paper connects theory to practice via a subsampling method whose asymptotic performance for the SBM is correct as far as number of communities is concerned.  The writing needs to be more crisp and clear.  \n\nHowever, the fundamental notion here is that there is an exact number of communities in any graph -- the ground truth M -- which the proposed algorithm estimates better than other subsampling algorithms. This is debatable in other than limited instances, such as synthetic SBM graphs.  In other words for many real world examples, M, the number of communities is typically very vague so what does it mean for an algorithm to have 1% less error than another?\n\nLastly, the authors do not provide examples for real 'large graphs' with millions-billions of nodes where subsampling ratio has to be much less than 1%.", "strength_and_weaknesses": "\nStrengths\n\no The paper addresses subsampling of large graphs to better estimate number of communities.\n\no The proposed subsampling technique is proved to be asymptotically correct for stochastic block model (SBM) graphs.\n\nWeaknesses\n\no The number of communities for most graphs, large or small, is not a precise enough number whose accuracy could be measured the way the authors state/measure.\n\no The writing is not clear/crisp in many important places, some examples are shown below.\n\no I may have missed this but what is the subsampling ratio used (n~ in the notation of Algorithm 1 at the end of Section 4.1) in Section 5 for synthetic graphs used?  (This is stated to be 10% for real-world graphs which by the way is quite large for large graphs of 50M-1B nodes.)\n\no No evidence that SBM is representative of real graphs (Twitter, FB, etc)\n\nEnd of Section 1:\n> More importantly, we theoretically show that the estimation of M by the subsampled graph converges to true M. \n\nM, the number of communities in a graph, is not a precise concept in general and there is no ground truth for most graphs for M. So how does one even get a measure of accuracy for the proposed or any other technique in other than synthetic datasets (from the SBM where we start with a set number of communities a priori) and datasets from previous estimates whose accuracy is open to debate?\n\nEnd of Section 2.1\n> The number of communities of the graph G is denoted by M(G)\n\nWhat is the definition of M(G)?\n\nBeginning of Section 2:\n> Without loss of generality, we consider the undirected graph\n\nThere is a lot of generality lost if we only allow undirected graphs.  As a matter of fact directed graphs don't even approximate Riemannian manifolds in discrete form since geodesics are always bidirectional. So what generality is *not* lost by considering only undirected graphs?  Why not just say this paper is about undirected graphs only?\n\nEnd of Section 2:\n> In Lemma 3.1, we theoretically prove the lower bound of within-community edges’ OR curvatures are larger than the upper bound of the between-communities edges’ OR curvatures in stochastic block models (SBM).\n\nThis, middle of page 4, is the 1st time in the paper that a reference to SBM is given.  So yes, if we define a SBM then we know M exactly but the majority of graphs are not SBMs so the entire theory of this paper is about a special class of graphs. Why not just say so from the beginning?\n\nMiddle of Section 5.3\n> the community of the graph is more imbalanced.\n\nNo clear definition of this concept is provided in any part of this paper other than occasional references to communities with nodes with large degrees as opposed to those without nodes with large degrees.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YNwtdOp7UG", "reviewer": "Reviewer_Rvtn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "The paper proposes a graph sub-sampling procedure with the objective of preserving the number of communities M in the original (large) graph. This is based on Ollivier Ricci curvature (an extension of Ricci curvature for the setting of graphs). The paper notes that existing subsampling methods have a preference for sampling high degree nodes and as a consequence miss out on 'minority communities' (communities with a small number of low degree nodes) and hence underestimate the true number of communities. The algorithm is supported by theoretical guarantees and specifically that estimated M from the sampled subgraph (from their approach) converges to the true M of the large graph.", "summary_of_the_review": "Overall, a good contribution which can possibly be improved to widen the scope of the problem currently addressed in the paper and with some additional discussion along the lines mentioned under weaknesses above.", "strength_and_weaknesses": "Strengths: The paper is very well-written and tackles an important problem concerning modern network datasets which typically have a large number of nodes. The proposed algorithm is based on a clear mathematical framework and supported by theoretical guarantees. It clearly performs very well in practice as illustrated by application to 4 real data sets.\n\nWeaknesses: 1. The subsampling is achieved with a narrow objective of preserving the number of communities (rather than the content/quality of community structure which is possibly crucial to other global network summaries). A discussion on the latter and specifically the importance of the number of communities is currently not convincing. \n2. If the  observed graph is assumed to be generated from a stochastic blockmodel, then the true number of communities is fixed and the problem makes sense. However, this is an assumption and may not be valid in practice. In such cases, estimating communities is simply a way to approximate the more general network generating process (e.g. Olhede and Wolfe, 2014) and a range of possible values for M are feasible (to lead to a reasonable approximation). This must be clarified in the discussion/introduction. 3. I would expect the performance of the proposed approach to additionally depend on the edge density of the network. This is an important feature as real networks often get sparser with increase in the number of nodes. This not discussed in the paper - neither in the theoretical results nor in the implementation. 4. Based on the OR curvature theory, are there any other network summaries concerning communities that the sub sampling procedure may possibly preserve? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PT9_oTwb0w", "reviewer": "Reviewer_5vqt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper introduces Ollivier Ricci (OR) curvature to distinguish within-community edges and cross-community edges. OR curvature uses Wasserstein distance and geodesic distance, where the Wasserstein distance can be computed by Sinkhorn algorithms. Given the nice properties of OR curvature on stochastic block models (SBM), the paper proposes a sampling algorithm by incrementally selecting neiborhood edges with the highest OR curvature gradients. The sampling algorithm is guaranteed to preserve minor communities better, thus better estimating the total number of communities compared to existing methods, including random walk methods.", "summary_of_the_review": "This paper proposes a theoretically sound subsampling method for graphs using OR curvature gradient. From my point of view, the paper still has room to improve its theory and experiments.", "strength_and_weaknesses": "Strengths: \n1. This proposed method is based on a theoretically sound analysis of the gap between OR curvatures for within-community and cross-community edges.\n2. Empirical results demonstrate a superior performance of OR curvature gradient-based subsampling methods.\n3. Like random walk methods, we can pre-compute OR curvature statistics for fast sampling.\n\nWeaknesses: \n1. I'm not fully convinced that OR curvature-based method is suitable for massive graphs like Twitter since those graphs are highly sparse and exhibit significantly different properties than SBM.\n2. There is no theoretical evidence to show that the proposed OR curvature-based graph subsampling is better than previous methods.\n3. Empirical results are weak from my point of view (see Clarity part for details.)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1jXs8wuYEv", "reviewer": "Reviewer_FvBB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "Detailed considerations: \n\nMain concern. How to access curvature without knowing the full graph? It is not clear how to compute the LINEAR SINKHORN ALGORITHM. Should we compute the Wasserstein distance between any node in the graphs as stated in Algorithm-1? Please clarify this: \n\nPlease see \"Sinkhorn Distances: Lightspeed Computation of Optimal Transport\" where they state: \n\n\"For a general matrix M, the worst case complexity of computing that optimum scales in $O(d^3 \\log d)$” where d is the size of the matrix (graph). \n\n“In the particular case that the metric probability space of interest can be embedded in R n and n is small, computing or approximating optimal transport distances can become reasonably cheap. Indeed, when n = 1, their computation only requires O(d log d) operations. When n ≥ 2, embeddings of measures can be used to approximate them in linear time (Indyk and Thaper, 2003; Grauman and Darrell, 2004; Shirdhonkar and Jacobs, 2008) and network simplex solvers can be modified to run in quadratic time (Gudmundsson et al., 2007; Ling and Okada, 2007). However, the distortions of such embeddings (Naor and Schechtman, 2007) as well as the exponential increase of costs incurred by such modifications as n grows make these approaches inapplicable when n exceeds 4” where n is the embedding dimension\n\nAnd later: \nSuch algorithms include Sinkhorn’s celebrated fixed point iteration (1967), which is known to have a linear convergence (Franklin and Lorenz, 1989; Knight, 2008). Unlike other iterative simplex-like methods that need to cycle through complex conditional statements, the execution of Sinkhorn’s algorithm only relies on matrix-vector products\n\nIn section 4.3, it is argued that “Aside from the computation complexity of the OR curvature of the graph (which is near-linear by Sinkhorn’s algorithm) “. Even if this is true (I cannot infer that from the “Sinkhorn Distances paper”, the complexity is n|E| which means O($n^2$)  or O($n^3$) for a dense graph. \n\nIf this is correct,  cubic complexity is equivalent to eigenvalues/vector computation. An interesting conclusion is that by computing the Laplacian pseudo inverse we can have a similar algorithm based on the commute times or effective resistances (which also satisfy that they are smaller inside the community than between communities). In any case, for a large graph, an O($n^3$) complexity seems unavoidable. \n\nAlthough more details on “computational time” are placed in the Appendix, we can only find these statements “As for the computational time, we observe that the estimation time of the full sample is two orders of magnitude larger than the time of subsampling and estimation. As the subsampling proportion increases, the computational time of subsampling methods increases. Though our method’s computational time is slightly larger than our subsampling methods, our method has better accuracy.“ Please clarify, since knowing the averaged computational time is critical when dealing with large graphs as claimed when motivating the approach. \n\n\nSecond: The theory of Ricci Curvature is not novel, only the concept of gradient bounds for inter and intra-community edges. The convergence theorems are nice (use of Matrix Chernoff bounds for instance) and the simplicity of the SBM model contributes to finding interpretable bounds in terms of probabilities p_{in} and p_{out}\n\nThird: Results are ok for a limited set of datasets. ", "summary_of_the_review": "The paper is well-motivated and the theoretical background is sound. However, there is a weak argumentation regarding the computational complexity of the algorithm. I consider that this is a fundamental issue when dealing with very large graphs as suggested in the motivation. ", "strength_and_weaknesses": "* Strengths. The curvature idea is very nice and inspiring. It has been also used for quantifying bottlenecks in graphs and their impact in the performance of GNNs. The theorems are very nice given the relative simplicity of the SBM model. \n\n* Weaknesses. In the negative part, the claim that the complexity of the algorithm is close to O($|E|$) is not well documented. I followed the literature and I cannot find any statement about the linearity of the Sinkhorn algorithm unless a significant distortion of the embedding. Please give convincing arguments that computational time is not an issue herein. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster