Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the online bipartite unweighted matching problem with predicted degrees of offline vertices. The author proposes a simple algorithm MPD which matches the vertices with low degrees first to exploit the predicted degree. This algorithm has a sub-optimal 1/2 competitive ratio in the worst case. But it performs well on some real data set and CLV random graphs, as the experiments in this paper show. The author proves that this algorithm is optimal on CLV-B random graphs when the prediction is perfect. The author also estimates the lower bound of the competitive ratio of MPD on symmetry CLV-B random graphs through solutions of some derivative equations.
strengths_and_weaknesses: Strengths: 

1.	Online bipartite matching problems are very important and have many applications in the real world. The prediction model in the paper is simple and well-motivated. It’s reasonable that we can obtain predicted degrees in real-world applications.
2.	The experimental results are well done and detailed. The author compares MPD and Ranking on real-world data sets, symmetry CLV-B graph and known i.i.d setting. The MPD outperforms Ranking well. And it seems that even when the degrees are estimated very poor, MPD still outperforms Ranking on CLV-B random graphs.
3.	Though MPD is sub-optimal in the worst case, the author shows that it is optimal on CLV-B random graphs. This is a nice theoretical result.

Weakness:

1.	The theoretical results are not general enough. They only cover the CLV random graphs where the expected degrees obey zipf’s law. 
2.	Main result on the optimality of MPD assumes that the predictions are perfect. If “prediction” is the main motivation of this paper, the error of the prediction is an important factor to study. However, the paper does not discuss the performance under imperfect prediction thoroughly. This makes the contribution of the paper limited.  

questions: 1.	In the paragraph “On prediction error”, the author uses the quantity “the minimum number of offline nodes that needs to be deleted such that π and π_0 induce the same order on the remaining nodes” to measure the prediction error. But in Appendix D, the author uses the quantity “Largest Increasing Subsequence”. It seems that these two are the same thing, but it’s better to use the same expression to avoid confusing.
2.	The optimality result assume that the prediction is perfect in fact. But a “prediction” itself means it is not perfect. If all the theoretic results (except Appendix. D) assume that the prediction is perfect, then it might be better to consider the setting such as “xxx with known expected vertex degrees” but not “xxx with predicted degrees”. 

limitations: Yes. I don’t think there are potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work considers the online bipartite matching problem with an oracle that predicts the degrees of nodes in the graph. They proposed the MinPredictedDegree(MPD) algorithm, which matches each online node to the offline node with the minimum predicted degree. 

On a natural random graph model (CLV-B), the expected degrees of the offline nodes are known and used as predictions. They showed that this MPD algorithm stochastically dominates any other online algorithms. 

They analyze this algorithm on a natural random graph model (CLV-B) with power-law degree distribution. Using the expected degrees as the predictor in the algorithm, they show that the competitive ratio of this algorithm to the maximum offline matching is more than 0.94 for several model parameters. 

The experimental results on multiple random graph models and real-world graphs show that the performance of MinPredictedDegree exceeds state-of-the-art online algorithms.
strengths_and_weaknesses: Strengths:
Learning augmented algorithms is a popular and important topic. Online bipartite matching with degree predictors is a new and interesting setting. 

This work analyzed the MinPredictedDegree algorithm for this problem. They showed the optimality of the MPD algorithm on the CLV-B random graphs. The theoretical analysis of this algorithm on the random graph (CLV-B) model is also very interesting. On CLV-B random graphs with power-law degree distribution and many real-world datasets, they show that the MPD algorithm achieves a substantial improvement. 

This paper is well-written and easy to follow.

I reviewed this paper before, they improved the results by adding the optimality analysis. 
questions: 1. In the introduction and appendix D, you showed that the MDP is robust to the prediction error. I think your proof is the robustness of the MDP on the CLV-B graphs, right? I am confused about this proof where you used that the graph is a CLV-B random graph. Is a similar analysis of the robustness also hold for other graphs?
limitations: No
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the online bipartite matching problem. The graph edges are not known beforehand but arrive in a certain order. Given Graph G(U\cup V, E), U is known while the nodes in V arrive online. Once a node in V arrives, its incident edges are also known. The paper aims to find the maximum matching in CLV-B model graph. The CLV-B model assigns a probability value to each node, and an edge linking from one node in U and one node in V exists with probability that is the product of the probabilities of the two nodes.

The main contributions of the paper are new theories and proofs that show a classic MinPredictedDegree (MPD) based method can achieve optimum in the CLV-B model. It also further analyzes the lower-bounds of the competitive ratios in several special cases. 

Overall, the contributions look solid to me and the paper is well written.
strengths_and_weaknesses: S1. This paper shows a theoretical contribution on a classic problem -- online bipartite matching.

S2. This paper is in general well written.

S3. It also analyzes the bias when the degree predictor has some errors.

S4. It analyzes the lower-bounds of the competitor ratios in some special cases.

S5. It shows empirical competitive ratios.

W1. This paper assumes that there is an oracle that can predict the degree for any node in U. In CLV-B model, the expected degree is used. 

W2. The link of this problem to the community of Machine Learning should be made clearer. Is a pure theory conference better for this paper?
questions: Q1. In fig 2, why this is a fluctuation in 2007?

Q2. I cannot get the intuition behind Theorem 6.1 (Eq. 4). Please explain the results with more intuition.

Q3. Since the a CLB-V graph is a special case of a general graph, and there are results for the online bipartite matching for the general graphs already. I wonder how difficult are the proofs in addition to the known results. 
limitations: The results of this paper is very interesting. However, the link of the studied problem to the community of Machine Learning is not that clear. How is the online bipartite matching applied in some ML based applications? If the link not that strong, I am not sure NeurIPS is the best fit for this paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the problem of online bipartite matching. A new model called CLV-B is proposed under which the performance of the greedy algorithm is analyzed. For the general case, the paper proves that the greedy algorithm is optimal in terms of the success probability. For the special case, called symmetric CLV-B model, the paper analyzes the competitive ratio and the expected matching size, and further discusses the competitive ratio for power law and Erdos-Renyi graphs. Simulations are conducted to verify the practical performance of the proposed algorithm. 


strengths_and_weaknesses: Strengths
- S1: The considered algorithm is definitely a natural choice for the CLV-B.
- S2: The paper presents a comprehensive study regarding the considered problem, and the presented results seem to be technically sound.
- S3: The experimental studies are also comprehensive, with source code available. 

Weaknesses
- W1: The time and introduction suggest that the problem is solved using predicted variables, but the entire paper (module appendix D) focuses on the case where the exact expected degree is given. In this sense, the title, abstract, and introduction are somehow misleading, and could be improved to make it clear that this paper studies classic combinatorial optimization problems, without involving any machine learning or data-driven aspect. In this sense, the paper fits better with STOC/FOCS/SODA, even though NeurIPS has a wide scope. 

- W2: My main concern is that the significance of the technical contribution is not very clear. The paper provides a lot of theoretical analysis (15 pages of proofs in the appendix), but it is not clear how easy or hard the presented results can be derived based on the existing works. For theory papers, the presented proofs are often inspired by some existing proofs, instead of being completely new. Such information is crucial for evaluating the significance of a new paper. For example, since the symmetric CLV-B model is a special case of the known iid model, does the analysis of the known iid model apply directly? What are the fundamental challenges caused by the CLV-B model in analyzing the algorithms?

- W3: The paper could be better organized such that all the theoretical results are clearly stated in the main paper. Many results in the appendix are only mentioned in the introduction but not discussed in the rest of the paper, and I am wondering whether such results are significant. 

- W4: Some minors
	- In the case that q=1, it seems to be the case that the producers (not consumers) select their adjacent edges iid.
	- Instead of claiming that the competitive ratio exceeds 0.99 for power-law graphs, it would be better to simply state that the competitive ratio depends on the parameters of the power-law graph.
	- What does it mean by “the worst distribution for MPD”? It would be better to formally state the proposed conjecture.
	- P4, it would be better to give a formal definition of p(A, S). 



questions: To make the contribution clear, it is necessary for the paper to draw proper connections between the presented proofs and the existing proofs, or claim that the presented proofs are not inspired by any existing works.


limitations: - The paper does not discuss the limitations.
- One potential limitation is that some of the presented results can be easily acquired from existing papers.
review_title: null

Meta-review: metareview: The paper studies online bipartite matching problem under a random graph model, and shows that using the expected mean of the degrees could achieve certain optimal performance under their graph model. The authors complement the theoretical study with empirical evaluation, and demonstrates that estimating the degrees would result in good performance in online bipartite matching.

The reviewers agree that the paper contains good technical contributions to the problem, and is worth to be published. There is some concern on whether the paper is related to ML/AI or is a purely combinatorial optimization paper. In particular, the reviewers share the concern that the theoretical algorithm takes the expected degrees as the input, and not the predicted degrees as suggesting an estimation with errors. After some discussions among the reviewers, here is my conclusion and recommendation:

1. The technical algorithm is like a combinatorial optimization algorithm, but it has a strong indication that degree estimation could be helpful in algorithm design. This is further complemented by the empirical study of the paper. Therefore, the study fits into the data-driven optimization and algorithm design paradigm that would interest the ML/AI community. 

2. The use of the term "predicted degrees" in the title/abstract/intro is indeed misleading. It gives a strong impression that the algorithm is using a prediction (or estimation) that contains estimation error, but it actually does not use such predicted degrees, and instead using the expected degrees as input. Of course expected degrees are still not the actual random degrees but they are not in the normal sense the "prediction" result. I strongly suggest the authors to properly change the title/abstract/intro to more accurately reflect what they are doing and to reduce confusion (If 3 out of 4 reviewers raise this issue, plus I also has this concern, the authors should expect a significant confusion if they do not revise the presentation). The authors should clearly state that their theoretical algorithm is for expected degrees, and this may indicate that using predicted degrees may be helpful, but the latter is not part of the theoretical result. The following is my try on the title:

(Optimal) Online Bipartite Matching with Known Expected Degrees on Random Graphs --- A Theoretical Justification of the Effectiveness of Algorithms Based on Ordering of Predicted Degrees

It is certainly not elegant, but hopefully it suggests the authors to spend some effort to give a more accurate title/abstract/intro in their presentation. 

Also, in terms of their theoretical result, their Appendix D does provide some result regarding the noise in the prediction. But it looks like the presented result is not in the normal sense of the prediction error between the prediction and the ground truth. I also suggest the authors to substantiate this part and perhaps move it into the main text so that the paper indeed has some treatment on predicted degrees.

Overall, with the above comments and suggestions, I believe the paper has good contributions to be accepted at NeurIPS.
confidence: Certain
Decision: Accept