Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
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.

Weaknesses: 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. 
2. 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? 


clarity,_quality,_novelty_and_reproducibility: The paper is clear and proposes a novel solution to an important problem; appears to be of high quality. 
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Detailed considerations: 

Main 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: 

Please see "Sinkhorn Distances: Lightspeed Computation of Optimal Transport" where they state: 

"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). 

“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

And later: 
Such 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

In 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. 

If 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. 

Although 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. 


Second: 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}

Third: Results are ok for a limited set of datasets. 
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. 

* 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. 
clarity,_quality,_novelty_and_reproducibility: Clarity. The paper is clear (of course the proofs are less clear due to the algebraic complexity even for a simple SBM model". 
Quality. High quality provided that convincing arguments about efficiency are clearly exposed in the discussion. 
Novelty. Same as quality. In addition, this is comparable to greedy community detectors but more principled. 
Reproducibility. Code not yet been released. Please do. 
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strengths: 
1. This proposed method is based on a theoretically sound analysis of the gap between OR curvatures for within-community and cross-community edges.
2. Empirical results demonstrate a superior performance of OR curvature gradient-based subsampling methods.
3. Like random walk methods, we can pre-compute OR curvature statistics for fast sampling.

Weaknesses: 
1. 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.
2. There is no theoretical evidence to show that the proposed OR curvature-based graph subsampling is better than previous methods.
3. Empirical results are weak from my point of view (see Clarity part for details.)
clarity,_quality,_novelty_and_reproducibility: 1. It would be clearer if you could make a table to compare the time complexity between ORG-sub and other methods.
2. Empirical results could be more persuasive if you include the following:
  (i) Dataset statistics (# nodes, # edges, degree distribution, etc.).
  (ii) How you select hyper-parameters, e.g., alpha.
  (iii) A broader range in the proportion of data you use and the scaling of computation cost.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 
The 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.
strength_and_weaknesses: 
Strengths

o The paper addresses subsampling of large graphs to better estimate number of communities.

o The proposed subsampling technique is proved to be asymptotically correct for stochastic block model (SBM) graphs.

Weaknesses

o 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.

o The writing is not clear/crisp in many important places, some examples are shown below.

o 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.)

o No evidence that SBM is representative of real graphs (Twitter, FB, etc)

End of Section 1:
> More importantly, we theoretically show that the estimation of M by the subsampled graph converges to true M. 

M, 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?

End of Section 2.1
> The number of communities of the graph G is denoted by M(G)

What is the definition of M(G)?

Beginning of Section 2:
> Without loss of generality, we consider the undirected graph

There 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?

End of Section 2:
> 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).

This, 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?

Middle of Section 5.3
> the community of the graph is more imbalanced.

No 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.
clarity,_quality,_novelty_and_reproducibility: 
This paper needs to be written more clearly with assumptions stated more prominently and earlier. The idea of basing a subsampling algorithm on theory is good but again what is important is to state what the key assumptions are and then possibly leave the details to an appendix.  The methodology followed is good and there is novelty in using the notions of discrete graph curvature as a guide for what nodes/edges to select for subsampling.  Reproducibility is unclear to this reviewer.
summary_of_the_review: 
The 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.  

However, 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?

Lastly, 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%.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a new method for sampling subgraphs to obtain a good representation of the network. The main idea behind the results is that classic subsampling strategies(based on node degrees or random walks) fail to capture the structure of small network. To cope with this limitation they present a new sampling strategy based on Ricci curvature.

The authors show the effectiveness of their method both theoretically(by analyzing the SBM model) and empirically.

Overall, the ideas presented in the paper are interesting so it will be a nice contribution to the conference program.
justification_for_why_not_higher_score: The idea of using Ricci curvature for sampling is interesting. The paper presents both theory and experiments to support their claims.
justification_for_why_not_lower_score: The experimental results are not particularly convincing, expecially because the analyzed dataset are quite small
Decision: Accept: poster