(Optimal) Online Bipartite Matching with Degree Information
Authors: Anders Aamand
Justin Y Chen
Piotr Indyk
Venue: NeurIPS 2022 Accept (2022)
Keywords: online bipartite matching
learning-augmented algorithms
algorithms with predictions
online algorithms

Abstract: We propose a model for online graph problems where algorithms are given access to an oracle that predicts (e.g., based on modeling assumptions or past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDegree, which uses predictions of the degrees of offline nodes. For the bipartite version of a stochastic graph model due to Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDegree stochastically dominates any other online algorithm, i.e., it is optimal for graphs drawn from this model. Since the "symmetric" version of the model, where all online nodes are identical, is a special case of the well-studied "known i.i.d. model", it follows that the competitive ratio of MinPredictedDegree on such inputs is at least 0.7299. For the special case of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost as large as the true maximum matching on such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDegree compares favorably to state-of-the-art online algorithms for online matching.  

(Optimal) Online Bipartite Matching with Degree Information
Anders Aamand MIT
Justin Y. Chen MIT justc0mit. edu
Piotr Indyk MIT indyk0mit. edu
aamand@mit edu
Abstract
We propose model for online graph problems where algorithms are given access to an oracle that predicts (e.g., based on modeling assumptions or past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDeggee, which uses predictions of the degrees of offline nodes. For the bipartite version of stochastic graph model due Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDeggre stochastically dominates any other online algorithm, i.c., it is optimal for graphs drawn from this model. Since the "symmetric" version the model, where all online nodes identical, is special case of the well-studied "known i.i.d model", it follows that the competitive ratio of MinPredictedDeggree such inputs is at least 0.7299. For the special of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost large the true maximum matching such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDeegre compares favorably state-of-the-an online algorithms for online matching.
Introduction
Online algorithms are algorithms that process their inputs "on the fly", making irrevocable decisions based only on the data seen so far. Since they do not make any assumptions about the future, they are versatile and work even for adversarial inputs. Unfortunately, by focusing the worst case, their performance in "typical" cases can be sub-optimal. As result there has been a large body of research studying various relaxations of the worst-case model, where some extra information about the inputs, or the distribution they are selected from, is available [
Motivated by the developments in machine learning, over the last few years, many papers have studied online algorithms with predictions 47). Such algorithms are equipped with a predictor that, when invoked, provides (imperfect) prediction of some features of the future part of the input, which is then used by the algorithm to improve its performance. The specific information provided by such predictors problem-dependent. For graph problems studied in this paper, predictions could include: the list of edges incident to a given vertex [33] the weight of an edge adjacent to given node in an optimal solution or vertex weights that guide a proportional allocation scheme [36]
In this paper we focus on online graph problems, and propose a model where an algorithm is equipped with "degree predictor". i.e., oracle that, given any vertex, predicts the degree of that vertex in the full graph (containing yet-unseen edges). This predictor has multiple appealing features. First it is simple, natural, and easy interpret. Second, it is useful: vertex degree information is employed in many heuristic and approximation algorithms for graph optimization, for problems such maximum independent set ? maximum matching (53 Third (as demonstrated Section
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

such predictors can be easily obtained. Finally, degree prediction is closely related to the problem of estimating the frequencies of elements data se and frequency predictors have been already shown to improve the performance of algorithms for multiple data analysis problems 25 28 19
The specific graph problem studied in this paper is online bipartite matching, where we given a bipartite graph G = (U u V. E), and the goal is to find a maximum matching in G. In the online setting, the set U is known beforehand, while the vertices in V arrive online one by one. When a new vertex e arrives, the edges in G adjacent to t are provided as well. Online maximum bipartite matching is a classic question studied in the online algorithms literature, with many applications [4.. It is known that a randomized online greedy algorithm, called Ranking, computes a matching of size at least 1/e z 0.632 times the optimum (II, and that this bound is tight in the worst-case. A large body of work studied various relaxations of the problem, obtained by assuming that vertex arrivals are random [21 or that the graph itself is randomly generated from a given "known i.i.d. model" [20]. In this paper we extend the basic online model by assuming access to a predictor that, given any "offline" vertex u E U, returns an estimate of its degree. (Note that the degree of any vertex in V is known immediately upon its arrival.)
Our results We study the following simple greedy algorithm for bipartite matching: upon the arrival of vertex v. if the set of neighbors N(v) of in G contains any yet-unmatched vertex, the algorithm selects u E ((r) of minimum predicted degree in G and adds the edge (u, v) to the matching. This algorithm, which we call renrreeictedeerree (MPD), essentially identical to the algorithm proposed in [[ which in turn was inspired by the offline matching algorithm called MinGreedy [53). The intuition is that vertices with higher degree will have more chances to be matched in the future.
Our main contributions are follows. First, following in long line of work on the average- case analysis of matching algorithms initiated by [+0, we analyze MPD under a natural random bipartite graph model refer as CLVV-B a bipartite version of the Chung-Lu--V random graph model 12). CLV-B random graph is parameterized by = (0) m = [V]. and two weight vectors p = (p. P==1 [0, 1J"h and q mm E [o, 1|m For any u, U and vy V, the edge (w,, fy) appears in the graph with probability piq, and these events are mutually independent. This model corresponds the setting where consumers pick their edges with probabilities proportional to the vector p which describes the relative distribution over the producers.
Many natural families of random graphs can be described in the CLV-B model. Of particular interest is the case when = (1.....1) 1), corresponding to the consumers picking their edges i..d;; we will refer to this case as the symmetric CLV-B model. The symmetric version can be viewed as a special case of the well-studied known i.i.d. model of (20). If we further let p = (p.....)). then the CLV-B graph is an Erdös- Rényi random bipartite graph with edge probability p.
Theoretical Results For the CLV-B model and the MPD algorithm which uses the expected degrees as predictions, we make the following theoretical contributions:
We show that MPD stochastically dominates any other online algorithm, i.e., it optimal for graphs drawn from the CLV-B model (Section 5) Specifically, we show that for any degree distribution, any algorithm A and any integer f, the probability that A produces matching of size at least & is upper bounded by the analogous probability for MPD. Since symmetric CLV-B is a special case of the known i.i.d. model, it follows that the competitive ratio of MPD for this model is at least equal to the best competitive ratio of any algorithm that works for the known i..d. model. By the result of [I], this ratio is at least 0.7299.
We analyze MPD on symmetric CLV-B model with power law degree distribution (Section 6 Our theoretical predictions demonstrate that the competitive ratio achieved by our algorithm on such graphs is very high. In particular, for several different power law distributions, it exceeds 0.99.
We also analyze MPD Erdös-Rényi bipartite random graphs where all edges appear with the same probability (Appendix K). In particular, the competitive ratio of the algorithm on
I 'The degree a node is simply the number of times the node appears the union of all edges. 'The main differences are syntactic: the algorithm of [10] computes the degrees based on the given "type graph" (see Section D. while in this paper we allow arbitrary predictors.
2

---

such graphs is at least 0.831. Since in this case all expected degrees are equal, the prediction oracle is of no help. Thus, we conjecture that this is the worst distribution for MPD among all distributions in the CLV-B model class.
Finally, observe that the competitive ratio of MPD is 1/2 for worst case graphs, and that this bound is tight. In addition, we show that the worst-case competitive ratio of any algorithm with access to the offline degrees is at most 1 - 1/e, implying that degree predictions do not help in the worst-case though they prove to be useful the random model well as in practice. See Appendix E for details.
Experiments We complement our theoretical studies with an extensive empirical evaluation of MPD for multiple random graph models and real graph benchmarks in Section 7 Our experiments show that, on most benchmarks, MPD has the best performance among about a dozen state-of-the-ar online algorithms, even when compared to algorithms that use much more information about the input. These experimental results demonstrate that MPD performs well beyond the average-case instances we study theoretically.
Prediction Error For our theoretical results on the CLV-B graphs, MPD is given only the expected (as opposed to the actual) degrees. Although this models the uncertainty in the input, it is natural to ask how MPD performs when even the expected degrees are mispredicted. To this end, in Appendix D we suppose that the offline nodes are prioritized in an arbitrary order x' which may be different from the order и obtained by sorting the nodes according to their expected degrees. Letting A be the minimum number of offline nodes that needs to be deleted such that and x induce the same order on the remaining nodes, we prove that using noisy degree predictor which induces xe' instead of can shrink the size of the matching produced by MPD by at most A. We note that the number of mispredicted nodes is an upper bound on A, but in general A could be much smaller.
Importantly, we also note that the empirical performance of MPD shows its resilience to prediction error. Our experiments on real graphs use predictors which are noisy and which degrade over time but still find large matchings. Furthermore, on synthetic Zipfian data, we experiment with artifically adding noise and show gradual degradation of MPD's performance as error increases.
2 Preliminaries
CLV-B model CLVV- the bipartite version of the Chung-Lu-Ve model used in prior work 12 Given vectors p {p.} and q {9; 1 the edge {u, 2y } appears in the graph independently with probability p.gy- From the vectors p and q. we obtain the vector of offline expected degrees {p. ||q/l]]__ For our theoretical results within this model, our algorithm MinPredictedDeggre uses the degree predictor which returns the expected degree for each offline of
d = (d4 ]
node: (u;) d, (see Appendix D for extension to noisy predictors). The particular symmetric CLV-B where = 1.....,) corresponds to the case where consumers (online) pick their edges i.i.d. over producers (offline) and MPD has knowledge of the average preferences over producers.
Known i.idd. model In the known i.i.d. model of 200 algorithms are given access to a type graph G = UU E) and distribution P V + 10. The nodes in V and their incident edges represent "types" of online nodes. An input instance Ô (U U V, F.) is formed by picking online nodes ii.d. from V according to the probabilities described by P. Note that the symmetric CLV-B model defined earlier a special case of this model. In our experiments, the degree predictions are given by the expected degrees of the offline nodes.
3 Related Work
Online bipartite matching and its generalizations have been investigated extensively. The survey 41 and the recent paper
[ provide excellent overviews of this area. The state of the art competitive ratios are 1 1/e 0.632 in the worst case [31 and R 0.7299 for the known i.i.d. model [I]] See [9] for an extensive empirical study of the existing algorithms. Other algorithms examined in the
experimental section include [20 5 40
26 18 10)
3

---

Algorithm MinPredictedDegree
Input: Offline nodes U and degree predictor o U + 1200
Output: Matching M
Initialize M +-D 0.
while online node (v) & unmatched neighbors of
arrives do
if (w) > then
u² < arg N(U)) a(u) (ties broken arbitrarily)
MM + M U {(*",
end if end while
More generally, there has been lots of interest in online algorithms with predictions over the last
few years, for problems like caching [39
55
29), ski-rental and its generalizations 4
22
2
3
scheduling [5 35
matching 33
36 and learning
Other areas impacted by learning-basee
algorithms include combinatorial optimization
[ 15 similarity search [52] 35
27
54
[6]. data
structures B2 4E! and streaming/sampling algorithms of this area.
See 47 for excellent survey
4 Algorithm
Online Bipartite Matching The online bipartite matching problem defined as follows. Given a bipartite graph G (U,VE)), call U the "offline" side and V the "online" side of the bipartition. Let n = |U] and m = |V]. The nodes in U are known beforehand and the nodes in V arrive one at a time, along with their incident edges. An online bipartite matching algorithm maintains matching throughout the process, with the goal of maximizing the size of the matching. As each node e E V arrives, the algorithm can pick one of its neighboring edges to add to the matching.
MinPreedicedDeegre addition to knowing the offline nodes beforehand, MinPredictedDeggree (MPD) given a degree predictor
2 In practice, this predictor could be inferred from additional knowledge about the graph or from past data. When a node v E V arrives, MPD (see Algorithm [ uses this predictor to greedily select the minimum predicted degree neighbor u" of that is not already covered in the matching and then adds the edge {u", v} to the matching. If no such valid neighbor exists, MPD does nothing with Intuitively, low degree offline nodes should be matched as early as possible as they only appear few times while we will have many chances to match high degree offline nodes.
The MPD algorithm has similar structure to the worst-case optimal Ranking algorithm 31 which assigns random cost each offline node and at each step greedily matches with the lowest cost offline neighbor. Specifically, if the degree predictor is random, MPD and Ranking are equivalent. As we show in the later sections, if the predictor "good enough", MPD often performs much better than Ranking, both in theory and in practice.
5 Optimality of MPD on CLV-B graphs
In this section we show that the size of the matching found by the the MPD algorithm stochastically dominates the size of the matching found by any other algorithm. We start by providing some preliminaries for the analysis.
Preliminaries For E [0, 11"H and g E [0, 1JmHH let l. denote instance of CLV-B graph with n = =UU| offline nodes, m = VV] online nodes, and weight vectors and g, such that the probability that edge (u,, U2) exists equal to pıq, for any E [n). [m]] Assume with no loss of generality that p is ordered, Pi S p> < < p.. Note that the expected degree of the offline node u, is p p:llqlli, the weight pi-
i.., it is proportional
In the online setting, the nodes of arrive sequentially in the order U1,..., Um with the random neighborhood of Uy V being revealed at the arrival of Uy. When vy arrives, online bipartite

---

algorithm A can match v to any of its unmatched neighbors in U but cannot change its decision later. For any online bipartite matching algorithm A. let A(Ip.g) denote the size of the matching attained by A on the instance y..q. Let Ao be the MinereeiitedDDeere algorithm which matches node fy with neighhorhood
an unmatched node u, E S such that p; minimal, i.e. to an available node in S with minimal expected degree (ties broken arbitrarily but consistently, e.g. by sorted order of the offline node id's). Let p(A, S) be the resulting set of weights after algorithm A (potentially) chooses neighbor in S to match with.
Consider two ordered weight vectors p. p' both of length n. We say that p' dominates p. equivalently p/, if p: I p. for all E [n]. We are now ready to state our main result on the optimality of MPD.
Theorem 5.1. Let E [0, 1J" and q E [0, 10T. Let A be any online algorithm and let 2 0. Then,
P(AA(1 p.4) 2 t) S P(Ao(1p.g) 2t).
To prove the theorem, we will need two technical Lemmas. Informally, Lemma 5.2 states that for any S * 0, it is advantage for Ag if the neighborhood of the first arriving node is S rather than the empty set. Lemma 5.3 (the proof of which the main technical challenge) states that if i 1 p', then Ao (4p',o) stochastically dominates Ao (4p.9). Intuitively, Theorem 5.1 then follows from Lemma 5.3 by inducting on the number of online nodes m. For any algorithm A and non-empty subset S [ [2] if A matches V1 node in the neighborhood S. then p(A, S) N p(A,, S), and we can apply Lemma 5.3 together with the induction hypothesis with m 1 online nodes. We need Lemma 5.2 to handle the issue that A may not to match 1 even in the case that S non-empty. The proofs of the two lemmas and of Theorem 5. are postponed to Appendices A B and
Lemma 5.2. Let p E 1]" and q E [o, 1]"h be weight vectors. Letp" E [0, 1|m be obtained from p by removing its i I'th entry for some E [n]. For any t 2 0,
P(Ao(Tpa) 2 S P(Ao(Ip'.a) 2t 1 1).
Lemma 5.3. Let p.p [0, 1)" be ordered weight vectors and q E [0, 1)m Suppose that p 3 Pl- For any 2 0,
P(Au(Tp.g) 2) < P(Au(Te .))
While optimally only holds when the predicted degrees are the expected degrees (or at least induce the same ordering over the offline nodes), the performance of MPD cannot be much worse the predictions are slightly off. Formally, for an arbitrary degree predictor a, let p[a] be the array of CLV- offline weights ordered by and let LII(pp(a) be the size of the longest increasing subsequence in this array. We show (via a more general result) in Appendix D that MPD will match at most n - LIS()(a)) fewer nodes than when given the expected degrees as predictions.
6 Competitive ratio of MPD on symmetric CLV-B random graphs
Though we know that MPD is optimal within the CLV-B model, this result does not give explicit competitive ratios for MPD. In this section we analyze MPD under the symmetric CLV-B model, and derive a set of equations that give a lower bound on MPD's competitive ratio. To recap, the symmetric model is parameterized by 10% m [V], and vector d [d corresponding to the expected degrees of the offline nodes. Formally, for any u, E U and ny E V, the edge (us, 0ý) appears in the graph with probability d./m.
As in the previous section, we analyze MPD when the degree predictions are given by the expected degrees d. Our main results within this model are set of equations that describe the size of the matching produced by MPD as well as the size of the maximum matching.
Given a set of expected degrees d, Equation 4 models the behavior of MPD on symmetric CLV-B(d) graph. We extend these results to the asymptotic case in Appendix | giving the expected matching size as n, m > oo for given distribution of expected degrees.
Given a set of expected degrees i Appendix 1 we give an upper bound on the expected size of the maximum matching equivalent. Empirically, we find this upper bound to be close to the maximum matching size when d follows power law distribution.
symmetric CLV) graph, and in Appendix we give the asymptotic
5

---

Using these equations, we show that in expectation MPD returns matchings almost as large as the maximum when the expected degrees of the offline nodes follow power law distribution (see Table D and Figure 60. For both MPD and the maximum matching, we show that the matching sizes are concentrated about their expectations (Appendix and M. implying that on these graphs, MPD achieves large competitive ratio.
6.1 Competitive ratios power law graphs
CUTOFF
a = 0.5
a'
a 1.5
10
0.967
0.948
0.934
0,928
100
0.998
0.986
0.958
0.937
1000
1.000
0.995
0,966
0.940
10000
1.000
0.997
0.969
0.940
100000
1.000
0.998
0.970
0.940
Table 1: Lower bound the competitive ratio of MPD on symmetric CLV-B graphs with offline expected degrees following a power law with exponential cutoff distribution as n, m - oc. The fraction of offline nodes with expected degree d is proportional to d dd= -d/ for = 2..
In Table we show the competitive ratio of MPD on symmetric CLV-B graphs with expected offline degrees tollowing a power law with exponential cutoff distribution p 46 and with n, m 30. For d (1, 2,.,,..)) ...). the fraction of offline nodes with expected degree d proportional d' for exponent and cutoff X. Note that in the asymptotic case, as the sizes of MPD's matching and the maximum matching are concentrated about their expectations (Theorems of expectations is equivalent to the competitive ratio (cxpectation of ratio). When the exponent is small or the cutoff is large, MPD achieves a better competitive ratio, with the ratio exceeding 0.99 when both occur. When a 2, while MPD still achieves a competitive ratio of up to 0.94, the competitive ratio is not as affected by larger cutoff as with smaller exponents (the power law factor is already significantly limiting the fraction of offline nodes with large expected degree). The analysis we develop is general and can used to evaluate MPD on symmetric CLV-B graphs with different parameters than those we have considered.
M.Tp. the ratio
6.2 Differential equation analysis of MPD
Let Y be the number of offline nodes with expected degree d who are unmatched by MPD after seeing the tth online node. Within this random graph model, {Y J form a Markov chain with the following expected evolution:
B[ - Yil Y=]= = - (1-1((1dd/)))
II (1- mm-m d'd
(1)
The first term corresponds the probability that at least one unmatched offline node with expected degree is incident on the (I + 1 1st online node while the second term corresponds to the probability that this online node has no neighboring unmatched offline nodes with smaller expected degree (which would be prioritized).
Let his llog(1 d/ d/m). To simplify the analysis of MPD, it will be helpful to consider the random variables Z = k. * Yi where
B
z = =ka (1 23
II
4..
cd
Following the work of Kurtz and many subsequent researchers 34
show that the behavior of MPD as described by these Markov chains well approximated by the trajectory of the following system of differential equations for all unique expected degrees d in d:
57
43
38 48
dza(t) dl
kid (e-eza(t)
II e(((() ed
(3)

---

These functions zt(t) represent continuous-tima approximations of the Markov chains with their derivatives corresponding to expected change from Equation In Appendix G we give the solution to these differential equations. Relying on past work 38 we give the following theorem (see Appendix
H for proof).
Theorem 6.1. Let G be a symmetric CLV-B random graph with unique expected offline degrees {6r) Let Ja Xa n be the number of offline nodes with expected degree d. Then, the expected (over the randomness in G) size of the matching formed by MPD approaches
8 So: + 28, (m))
(4)
as n = m approach infinity, where 28, (1) for E {1...., form the solution to the system of differential equations in Equation
The solution to the system of differential equations gives us a closed form continuous time approxi- mation for expected performance of MPD in terms of d. In particular, in the asymptotic case, the equations give the exact expected performance and in the non-asymptotic case give an approximation on the number of unmatched offline nodes (and thus the matching size).
7 Experiments
In this section, we evaluate the empirical performance of MPD on real and synthetic data. For each dataset, report the empirical competitive ratio of MPD and a variety of baselines. In each case, the empirical competitive ratio is the average, over 100 trials, of the ratios of the sizes of the matchings outputted by given algorithm and the sizes of the maximum matching. In addition to the average ratio, we report one standard deviation of the ratio across the trials.
Datasets
We evaluate MPD on the following datasets.
Oregon: 9 graphs sampled over 3 months representing communication network of internet routers from the Stanford SNAP Repository [37] Each graph has ~ 10k nodes on each side of the bipartition and 40k edges. For MPD, the offline degree predictor a U - R is based on the first graph: if an offline node u (i.c. specific router) appeared in the first graph, (u is the degree of that graph. If an offline node u did not appear the first graph, ((u) the order of arrival of the online nodes is randomized.
For each trial,
CAIDA: 122 graphs² sampled approximately weekly over 4 years representing a communication network of internet routers from the Stanford SNAP Repository (37). Each graph has 20k nodes on each side of the bipartition and 100k edges. The degree predictor is the same as for the Oregon dataset (for each year, the first graph of the year is used to form the predictor). As seen in Figure X (see Appendix N). the degree distribution of the graphs for both the Oregon and Caida datasets are toigetailed and the error of the first graph predictor increases underlying graph evolves. For each trial, the order of arrival the online nodes randomized.
time the
Symmetric CLV-B random graph: We consider symmetric CLV-B model where the expected offline degrees are distributed according to Zipf's Law, popular power law distribution where In our experiments, we set size m 1000, set m/2, and vary the
d, = - exponent a.
46
Known i..d.:: Finally, we compare MPD to algorithms for the known i.i.d. model, copying the methodology of Borodin et al. [9] for synthetic power law graphs (Molloy Reed and Preferential Attachment) and real world graphs. In the Molloy Reed experiments, the type graph is sample from a family of random graphs with degrees distributed according to power law with exponential cutoff. In the Preferential Attachment experiments, the type graph is formed by the preferential attachment model in which edges are added sequentially with edges between high degree nodes being more likely. The Real World graphs are comprised a variety of graphs from the Network Repository 5T.. See Appendix N for more results on Real World graphs.
'The graphs the Oregon and CAIDA datasets are made bipartite following the bipartite double cover or duplicating method used in prior work [9) Given a graph G (V, E). the bipartite double cover of G is the graph G' = (U' U V E²) where U' and V are copies of V and there is an edge {ut, v/}} } E E² if and only if (us, U2} E E.
7

---

Baselines
We compare our algorithm to variety of baseline algorithms.
Ranking In experiments, we compare to the classic, worst-case optimal Ranking algorithm
MinDegree The MinDegree algorithm a version of MPD with a perfect oracle, i.e. (u) returns the true degree of u. In comparison with MPD, MinDegree shows the effect of prediction error on the performance of MPD.
Known i.i.d. baselines For the experiments in the known i.i.d. case, we also compare to the baselines in the extensive empirical study of [9- their paper for detailed descriptions of all algorithms. The code is distributed under the GPL license. Notably, the algorithms Category- Advice and 3-Pass are not strictly online algorithms: they take multiple passes over the data, using some limited information from previous passes to make better decisions in the next pass. It should also be noted that BegMenDegree is distinct from either the MPD or MinDegree algorithms we have described it does not use the type graph but rather maintains and updates an estimate of the degree of the offline nodes throughout the runtime of the algorithm.
greedy- they do not always match online node even if it has unmatched neighbors. [ evaluate greedy augmentations these algorithms (denoted by Aggorithm(g)) g)) which match
Most known i..d. baselines
arbitrary unmatched neighbor in these cases and generally show them to outperform their non-greedy counterparts. We additionally evaluate MPD augmented versions of these algorithms (denoted by Algorithm(MPD)) which applies the MPD rule in these cases using the expected degrees as predictions.
MinDegree
MinPredicteDDegree
Ranking
0.99
Compattive
0.98
0.97
0.96
0.95
6
8
Graph #
Figure 1: Comparison of empirical competitive ratios on the Oregon dataset. The first graph is used form predictions.
2004
2005
2006
2007
1.00
Compet balls
0.98
0.96
3
13
3
11
0
30
20
30
40
50
30
20
30
40
Graph
Graph
Graph #
Graph
Figure 2: Comparison of empirical competitive ratios the CAIDA dataset. For each subfigure, the first graph of the year is used to form predictions for the rest of the year.
Results Across the various datasets, MPD performs well compared to the baseline algorithms. For the Oregon, CAIDA, and symmetric CLV-B random graph datasets, MPD significantly outperforms Ranking, and for Oregon and CAIDA, the performance of the algorithm mildly declines as the degree predictions degrade. For the known i.i.d. datasets, MPD often outperforms all online baselines. despite making only limited use of the known i.i.d. model. Additionally, augmenting the known i.i.d. algorithms with the (MPD) rule often improves their performance over both the basc and the greedy (g) versions of the algorithms.
On the Oregon dataset, MPD achieves competitive ratio of ~ 0.99 across the graphs compared with competitive ratios ranging from 0.95 to 0.97 for
Oregon and CAIDA (Figures :

---

MinDegree
MinrroiiceDDegree
Ranking
- MisPrediceeDDegee Inskey)
Ranking
1.00
0.98
Compattive Ratio
Competiiee Ratto
0.95
0.94
0.90
0.92
0.85
0.90
0.2
0.4
0.6
0.8
1.0
1.2 Exporent
14
1.6
18
2.0
0.2
0.3
0.4
0.5
0.6
1.0
Fraction sunsampied
(a) Comparison across Zipf's Law exponents.
(b) Analysis of predictor noise (exponent
α = 1).
Comparison of empirical competitive ratios symmetric CLV-B random graphs with offline expected degrees following Zipf's s Law with exponent a. In (a), we vary a and MPD uses the expected degree as its predictor. In (b), the degree predictor is the offline degree in random subgraph using a (varying) fraction of the online nodes.
Figure 3:
tw0.5,
twO 5, kmd1
ke1
1w2. ko9f
Calagery
(Daya ee
Bahman (orrestiag
Eahnsst
Sutmansappe of
Hore Hordaad E44100
Harakes
Id btt
Meralad (112
In ()
Sirpaceest
Smp KCredd
Setmurttar
Dandng
Bahrsan
FulorastiA
Narttasidd
0.5
CorpetAnn
Compodiiee Rato
Corgetin
Figure 4: Comparison of empirical competitive ratios for Known i.i.d Molloy- Reed graphs. Algo- rithms depicted in gray are not online algorithms (they use extra information multiple passes). Algorithms in green are augmented with MPD.
Ranking. Compared with MinDegree, which uses knowledge of the true offline degrees, MPD's performance slowly degrades over time the graphs become less similar to Graph #1 (see Figure g in Appendix N for quantitative details).
Similarly, on the CAIDA dataset, MPD does significantly better than Ranking, achieving com- petitive ratios almost always greater than 0.98 compared ratios around 0.95, respectively. As the performance of the degree predictor degrades over time, the performance of MPD gradually declines (though it still significantly outperforms Ranking for both datasets).
Symmetric CLV-B random graph (Figure 3 For symmetric CLV-B random graphs with offline expected degrees following Zipf's Law, MPD outperforms Ranking across spectrum of exponents ranging from 0.2 to 2. For exponents less than 0.5 and greater than 1.5, MPD achieves competitive ratio close to 1 (greater than 0.995). All of the online algorithms have worse competitive ratios when the exponent is closer to one with MPD achieving ratio of 0.93 and Ranking achieving a ratio of ~ 0.86 when a 0.8. Though MPD does worst at a 0.8, it also achieves its greatest improvement over Ranking at this setting.
In Figure 3b we analyze the performance of MPD with a noisy degree predictor on Zipf's Law symmetric CLV-B random graphs with exponent 1. To introduce noise, the degree predictor (u) is given by the number of neighbors u has with a random subset of the online nodes V. As we decrease the fraction of V we subsample, thus increasing the variance of the predictor, the performance of MPD steadily declines. Even when the degree predictor only uses 10% or even 1% (the leftmost point on the graph) of the online nodes, it still outperforms Ranking.
Known i.i.d. (Figures 4 55: Across all of the experiments in the known i.i.d. model, MPD is among the top online algorithms, and is often the best performing online algorithm (note the algorithms in gray are not strictly online algorithms). Most of the algorithms (e.g. BahamiKapralov and ManshadiFtAl) rely heavily on the type graph, including precomputing an optimal matching on the type graph. By contrast, MPD only uses first-order information: it only looks at degrees

---

Treferntiall (=2.1)
Prefetencall (c-8.3)
Callas335
Bee288
Category
7415
bahrran 1P00
Manduae (0n)
Mintonal (lA
Pore
Categary
Brudoct (iiarr
indd
Stnck
Sintr chcul
Serpectr
Satmyri
0.5 0.5
1.0
Competitie Rate
Computiive Rablo
Competibe
Figure 5: Comparison of empirical competitive ratios on Known i.idd Preferential Attachment graphs and Real World graphs. Algorithms depicted in gray not online algorithms (they use extra information or multiple passes). Algorithms in green are augmented with MPD. See Appendix N for more Real World results.
and does not rely on any information about specific edges. Even so, most cases, it outperforms all of the other online algorithms. Additionally, the (MPD) augmented versions of the known i.i.d. algorithms always beat the base algorithms and often beat the greedy (g) versions, indicating the potential of predicted degrees to be integrated with other algorithms. Note that while the standard deviations are quite wide (the known i.i.d, model is inherently stochastic), as the results are summarized over 100 trials, relatively small differences in the average performance of these algorithms are statistically significant as the standard error is small.
Acknowledgements This research was supported in part by the NSF TRIPODS program (awards CCF-1740753 and DMS-20224483 NSF award CCF-2006798, Simons Investigator Award, NSF Graduate Research Fellowship under Grant No. 1745302, Math Engineering Fellowship, and DFF-Innermational Postdoc Grant 0164-00022B from the Independent Research Fund Denmark.
References
[1] Special Semester on Algorithms and Uncertainty, 2016. hntpps//ssmons: berkeley edu/
[2] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ml predictions for online algorithms. In International Conference Machine Learning, pages 303-313. PMLR, 2020.
[3] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online computation with untrusted advice. In 11th Innovations Theoretical Computer Science Conference (ITCS 2020), 2020.
[4] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In 34th Conference Neural Information Processing Systems, 2020.
[5] Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In European Symposium on Algorithms, pages 170-181. Springer, 2010.
[6] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International Conference Machine Learning, 2018.
[7] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit, Online learning with imperfect hints. In International Conference on Machine Learning, pages 822-831. PMLR, 2020.
[8] Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):0087 March 2008.
10

---

fuer [9] Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorihmmess (JEA), 25:1-37, 2020.
[10] Allan Borodin, Denis Pankratov, and Amirali Salehi-Abari. On conceptually simple algorithms for variants of online bipartite matching. Theory of Computing Systems, 638))1171111888 2019.
[11] Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. New al- gorithms, better bounds, and a novel model for online stochastic matching. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-LeiinizzZeeniie Informatik, 2016.
[12] Fan Chung, Linyuan Lu, and Van Vu. The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3):257-275, 2004.
[13] Hanjun Dai, Elias Khalil, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances Neural Information Processing Systems, pages 6351-6361, 2017.
2017.
[14] Ofer Dekel, Arthur Flajolet, Nika Haghtalab, and Patrick Jaillet. Online learning with hint. In NIPS, pages 5299-5308, 2017.
[15] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in Neural Information Processing Systems, 34, 2021.
[16] Yihe Dong, Piotr Indyk, Ilya nearest neighbor search. ICLR, 2020.
Razenshteyn, and Tal Wagner. Learning space partitions for
[17] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In International Conference on Machine Learning, 2021.
[18] Christoph Dür, Christian Konrad, and Marc Renault. On the power of advice and randomization for online bipartite matching. The 24th European Symposium on Algorithmss (ESA), 2016.
[19] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based support estimation in sublinear time. In International Conference on Learning Representations, 2021.
[20] Jon Feldman, Aranyak Mchta, Vahab Mirrokni, and Shan Muthukrishnan, Online stochastic matching: Beating 1-1/c. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117-126. IEEE, 2009.
[21] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pages 982-991,2000
[22] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2327. PMLR, 2019.
[23] Philip Hall. On representatives subsets. Journal of The London Mathematical Society-second Series, pages 26-30, 1935.
[24] Magnús M Halldórsson and Jaikumar Radhakrishnan. Greed is good: Approximating indepen- dent sets in sparse and bounded-degree graphs. Algorithumica, 18(1):145-163, 1997.
[25] Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- frequency estimation algorithms. In International Conference Learning Representations, 2019.
[26] Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations Research, 39(3)x224-646, 2014.
[27] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions pattern analysis and machine intelligence, 33(1):117-128, 2011.

---

[28] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P Woodruff. Learning augmented Learning-augmented data stream algorithms. ICLR, 2020.
[29] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming für Informatik, 2020.
(ICALP 2020). Schloss
[30] R. Karp and M. Sipser. Maximum matchings in sparse random graphs. In FOCS 1981, 1981.
[31] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358 1990.
[32] Tim Kraska, Alex Beutel, Ed Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD), pages 489-504 ACM, 2018.
[33] Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. 10th Innovations in Theoretical Computer Science, 2019.
[34] Thomas Kurtz. Approximations of Density Dependent Jump Markov Processes, pages 51-61. 1981.
[35] Silvio Lattanzi, Thomas Lavastida. Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[36] Thomas Lavastida, Benjamin Moseley, R Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing. arXiv preprint trXiv:2011.11443 2020.
[37] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap... stanforr.d.. edu/ June 2014.
[38] Michael Luby, Michael Mitzenmacher, M Amin Shokrollahi, and Daniel Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, (7(2):569-55)) 584, 2001.
[39] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages
PMLR, 2018.
[40] Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Matherattcss of Operations Research, 37(4):559-573, 2012.
[41] Aranyak Mchta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265-368, 2013.
[42] Raghu Meka, Prateek Jain, and Inderjit Dhillon. Matrix completion from power-law distributed samples. In Advances in Neural Information Processing Systems, volume 22, pages 1258-1266 Curran Associates, Inc., 2009.
[43] Michael Mitzenmacher.
Studying balanced allocations with differential equations. Combina- torics, Probability, and Computing. 8:473-482, 1997.
[44] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, 2018.
[45] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In ITCS, 2020.
[46] Michael Mitzenmacher and Eli Upfal. Probability and Computing. 01 2005.
[47] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.099 09123, 2020.
12

---

[48] Nathan Noiry, Vianney Perchet, and Flore Sentenac. Online matching in sparse random graphs: von-asymptotic performances of greedy algorithm. In 35th Conference on Neural Information Processing Systems, 2021.
[49] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661 1670, 2018
[50] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845, SIAM, 2020.
[51] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
[52] Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing, International Journal of Approximate Reasoning, 50(7)969--77,, 2009.
[53] Gottfried Tinhofer. A probabilistic analysis of some greedy cardinality matching algorithms. Annals of Operations Research, 1(3):239-23 254, 1984.
[54] Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data- survey. Proceedings of the IEEE, 104(1):34-57, 2016.
[55] Alexander Wei. Better and simpler ceamminng-uummeneee online caching. In Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/ANDOM 2020). Schloss Hagstuhl-Leibmiz-zentiee für Informatik, 2020.
[56] Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing, In Advances in neural information processing systems, pages 1753-1760, 2009.
[57] Nicholas C. Wormald. Differential equations for random processes and random graphs. Annals of Applied Probability, 5(4):1211113)) 1995.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See, for example, Appendix E
(c) Did you discuss any potential negative societal impacts of your work? [No] We did not include a discussion of this in the text of the paper as our paper is focused on fundamental research. That being said, online bipartite matching has wide variety of applications, developing and better understanding algorithms for this problem may have impact these diverse applications. In particular, metrics other than the competitive ratio of algorithms (such as certain notions of fairness) are important to consider in applications involving individuals and are being studied in other works.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen-
tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The experiments are relatively lightweight and the focus of this paper is not on computational resources (rather, we focus on the quality of the algorithms' output). That being said, MPD a very simple and computationally efficient algorithm (assuming accessing the degree predictor is not too expensive). The experiments were all run on a 2018 MacBook Pro.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] See code in supplement.
(d) Did you discuss whether and how consent obtained from people whose data you 're using/curating? [N/A] All data was gathered from open sources intended for research use.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] None of our data falls within this category.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "jRzLaMFgRP5", "reviewer": "Reviewer_FyN6", "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.\n\nThe 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. \n\nOverall, the contributions look solid to me and the paper is well written.", "questions": "Q1. In fig 2, why this is a fluctuation in 2007?\n\nQ2. I cannot get the intuition behind Theorem 6.1 (Eq. 4). Please explain the results with more intuition.\n\nQ3. 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. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1. This paper shows a theoretical contribution on a classic problem -- online bipartite matching.\n\nS2. This paper is in general well written.\n\nS3. It also analyzes the bias when the degree predictor has some errors.\n\nS4. It analyzes the lower-bounds of the competitor ratios in some special cases.\n\nS5. It shows empirical competitive ratios.\n\nW1. 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. \n\nW2. The link of this problem to the community of Machine Learning should be made clearer. Is a pure theory conference better for this paper?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cDpGBS32rSM", "reviewer": "Reviewer_Skmv", "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. \n\nOn 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. \n\nThey 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. \n\nThe experimental results on multiple random graph models and real-world graphs show that the performance of MinPredictedDegree exceeds state-of-the-art online algorithms.", "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", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nLearning augmented algorithms is a popular and important topic. Online bipartite matching with degree predictors is a new and interesting setting. \n\nThis 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. \n\nThis paper is well-written and easy to follow.\n\nI reviewed this paper before, they improved the results by adding the optimality analysis. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JekQ_HTzE2", "reviewer": "Reviewer_o3xo", "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.", "questions": "1.\tIn 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.\n2.\tThe 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”. \n", "limitations": "Yes. I don’t think there are potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1.\tOnline 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.\n2.\tThe 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.\n3.\tThough 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.\n\nWeakness:\n\n1.\tThe theoretical results are not general enough. They only cover the CLV random graphs where the expected degrees obey zipf’s law. \n2.\tMain 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.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1Ml73XGQI5u", "reviewer": "Reviewer_gW3G", "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. \n\n", "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.\n\n", "limitations": "- The paper does not discuss the limitations.\n- One potential limitation is that some of the presented results can be easily acquired from existing papers.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- S1: The considered algorithm is definitely a natural choice for the CLV-B.\n- S2: The paper presents a comprehensive study regarding the considered problem, and the presented results seem to be technically sound.\n- S3: The experimental studies are also comprehensive, with source code available. \n\nWeaknesses\n- 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. \n\n- 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?\n\n- 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. \n\n- W4: Some minors\n\t- In the case that q=1, it seems to be the case that the producers (not consumers) select their adjacent edges iid.\n\t- 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.\n\t- What does it mean by “the worst distribution for MPD”? It would be better to formally state the proposed conjecture.\n\t- P4, it would be better to give a formal definition of p(A, S). \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept