Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the performance of a greedy algorithm for online bipartite matching under the configuration model. In this model the vertex degrees of the input graph adhere to a fixed distribution. The authors estimate the competitive ratio of the greedy algorithm and show that in this model the greedy algorithm achieves better performance guarantees than related methods.
main_review: Originality/Significance: The authors present an interesting result in the area of online matching under a stochastic model. It has to be said that I am not an expert in this area, but it seems both the result and the proof technique are original and should be of interest to the community.

Quality/Clarity: The paper is mostly clear. At times the authors use terminology that could be improved, such as:
- "subGaussian" (line 113) -- What do you mean by that?
- "half-edges" -- requires definition
- "multiple edges" (line 158) -- Should be replaced by "parallel edges" (the standard terminology)
- The statement in Proposition 1 should be formalized.

I did not have time to check the proof of the main claim.

From a presentation point of view the paper should meet the bar of acceptance, given the authors improve on the issues pointed out above.

Typos:
- $N$ instead of $n$ (line 164)
- *reason (line 69)
- "worst" -> "worse" (line 214)

limitations_and_societal_impact: No societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the online bipartite matching problem with capacities in random graphs that are generated by a stochastic process called the configuration model. The configuration model generates random graphs whose degree distributions are sub-Gaussian. The main contribution of the paper is an analysis of the competitive ratio achieved by the well-studied Greedy algorithm for online bipartite matching. The main result relates the competitive ratio to the solution of a certain ODE. The ODE can either be solved in closed form for some special cases of interest or it can be solved numerically to obtain estimates of the competitive ratio. As a corollary of the main result, the paper derives competitive ratios for several special cases, including random d-regular graphs and Erdos-Renyi graphs.

main_review: Significance: The paper addresses a fundamental problem in online algorithms, which is well studied and has applications in online advertising. The Greedy algorithm is also a well-studied algorithm in both the adversarial setting as well as stochastic settings. The current paper contributes to this line of work by analyzing Greedy in a more general random graph models, and relating its competitive ratio by relating it to an ODE that can be solved either numerically or in closed form in some settings. The questions addressed are mathematically interesting. 

On the negative side, the paper does not discuss how the mathematical results presented can benefit the machine learning community. The paper does not connect the random graph model considered to real-world instances. Overall, the paper seems to be a better fit for a TCS or Mathematics venue.

Novelty/originality: The result appears to be novel and the approach could potentially lead to explicit competitive ratios for more general random instances.

Clarity: The content in the main body is reasonably clear. I have not checked the correctness of the proofs included in the appendix.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors investigate bipartite matching in an online setting were the graph edges are generated via the configuration model (i.e. from a chosen degree distribution). They bound the estimation error, measured via the expected ratio between the online matching obtained by Greedy and the hindsight-optimal matching. This allows them to compare the performance guarantee for Greedy versus the state-of-the-art Ranking algorithm. The authors prove that surprisingly, there exist problem instances (including simple and natural ones) where Greedy outperforms Ranking.
main_review: REVIEW
The main result, which is a bound on the estimation error of Greedy for configuration graphs, is of theoretical interest. It is also interesting that this result permits a convenient comparison of Greedy's performance on different configuration graphs. Finally, I agree with the authors that it is interesting that Greedy outperforms Ranking on simple/natural graphs, such as 2-regular graphs. Obtaining these results is nontrivial. I see this not as a breakthrough theoretical result, but rather as an interesting step forward in a relevant area that requires nontrivial analysis.

In terms of style, the paper is generally well-written. However, typical NeurIPS papers make better use of subheadings throughout and offer brief exposition/high-level intuitions around each section. This paper is written more like a math journal paper. More structure and more high-level exposition would improve the writeup.

The experimental results figures are in general very difficult to parse and have some issues: They are missing labels on the axes; linetypes (dashes/dots) are not used to distinguish the lines; points are not used to show the actual points of comparison; I infer that (for example) the 4 panels in Appendix Fig. 5 and 6 are used to plot d=2,4,10,20 (this should be stated), but there are no titles on the figures, so is the top right plot d=4 or the bottom left plot d=4?

Also, in the figures shown in the paper's text (Fig. 1), we are shown results for d=[2,3,4,6,10], and we are told results are nearly instantaneous. Given that computation is not a limiting factor, why not show us more results (in a different type of plot)? In general, for a NeurIPS paper I would expect a greater effort to articulate and display experimental results---improving this will improve the paper. Also, one of the last sentences of the paper mentions that you expect Greedy will outperform Ranking in various other scenarios---this is a tantalizing opportunity for a broader experimental approach (either for this or another paper).

I will consider revising my review based on the authors' response.

Minor suggestions for improving the writing, figures, etc.:

- References are all lacking numbers in the References section. This makes it very difficult to check your references.

-Line 69 states "The main is that " --> maybe there is a missing word such as 'main limitation'?

-Convention suggests that your introduction should have subsections. It is a well-written introduction, but we only learn about your main result in the penultimate paragraph. You might consider highlighting it under a "Main contribution" substitle or bold paragraph heading.

- The Algorithm \ref in line 129 is undefined.

- Multiple instances of the word GREEDY have a missing space after. If this is a macro, try a \ (slash) between GREEDY and any non-punctuation letters/words.

- Missing 's' in 'situations' on line 308

- Line 212: folline -> offline
limitations_and_societal_impact: The limitations are addressed. Societal impact is not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes the performance of the GREEDY algorithm for online matching on random bipartite graphs generated by the configuration model with given degree distributions.
The analysis is based the differential equation method, a stochastic approximation using an ODE to represent the time evolution of matching size under the GREEDY algorithm with overwhelming probability.
The paper reports the following main results:
- A proof that the matching size of the GREEDY algorithm is the solution to an ODE.
- Competitive ratios of the GREEDY algorithm in different graph models (d-regular graphs, Erdos-Reny graphs).
- A proof that GREEDY beats RAKNING on 2-regular graph, with experimental evidence suggesting that the same holds for higher degrees.
main_review: - Very readable, great writing, though typos are noticeable.
- Main idea is to consider the random process of graph generation in the configuration model together with the time evolution of GREEDY matching, which is interesting.
- The main result generalizes or complements some known results on special graph families.
- The paper is easy to follow.

Some nitpicks:
- Typo: line 19, Page 1, second paragraph of Introduction, Internal advertising should be Internet advertising.
- Typo: Algorithm ??, Page 4, line 129.
- Great introduction on online matching and its variants (weighted, configuration model).
limitations_and_societal_impact: This paper only studies theoretical performance and does not mention societal impacts.
review_title: null

Meta-review: The reviewers generally thought this was an interesting paper on stochastic matchings. Novel ideas and analysis are presented.  The criticism is the fit for the community. 
Decision: Accept (Poster)