MAGNOLIA:
Matching Algorithms via GNNs for Online Value-to-go Approximation

Alexandre Hayderi 1 Amin Saberi 1 Ellen Vitercik 1 Anders Wikum 1

Abstract

offline nodes. Matching occurs in rounds, with one online node arriving with known probability in each round.
The goal is to compute a high-weight matching despite notknowing which online nodes will arrive a priori.

Online Bayesian bipartite matching is a central
problem in digital marketplaces and exchanges,
including advertising, crowdsourcing, ridesharing, and kidney donor matching. We introduce agraph neural network (GNN) approach that acts as
a continuous approximation to the intractable optimal online algorithm, which selects actions (e.g.,which nodes to match) by computing each action’svalue-to-go (VTG)—the expected weight of thematching if the algorithm takes that action, thenacts optimally in the future. We train a GNN to estimate VTG and show empirically that our method
returns high-weight matchings across a variety oftasks. Moreover, we identify a common familyof graph distributions in spatial crowdsourcing
applications, such as rideshare, under which VTG
can be efficiently approximated by aggregating
information locally within graphs. This structure
matches the local behavior of GNNs, providing
theoretical justification for our approach.

The online optimal algorithm for OBBM, OPTon , only has
access to the distribution over online node arrivals. Upon
the arrival of an online node, OPTon takes the action (i.e.,the choice of the matching edge or the decision to skip)
that maximizes the weight of the final matching in expectation over future arrivals. This can be formulated as an
exponential-sized dynamic programming routine which, ineach timestep, computes the value-to-go (VTG) of eachaction—the expected final matching weight if OPTon takesthat action and then acts optimally in the future.
1.1. Our contributions
We present a continuous approximation to OPTon that uses
a graph neural network (GNN) to estimate the VTG ofactions. Moreover, we provide theoretical guarantees thatjustify this architecture’s suitability for the OBBM problem.
Key challenges. The primary obstacle we face is the sheer
complexity of OBBM: for some constant α < 1, it is
PSPACE-hard to approximate the value of OPTon within afactor of α [Papadimitriou et al., 2021]. Nonetheless, ourapproach competes with OPTon across many tasks empirically, and while deep learning architectures are notoriously
difficult to analyze, we prove a correspondence between thefunctions computable by GNNs and the VTG function.

1. Introduction
Online matching is a central problem in many digital marketplaces. In advertising, website visitors are matched toads [Mehta et al., 2013], and on crowdsourcing platforms,
crowdworkers are matched to appropriate tasks [Tong et al.,2020]. The rideshare industry faces the complex task ofmatching riders with drivers [Zhao et al., 2019], while inmedical fields such as kidney exchange, donors must be efficiently matched to patients [Ezra et al., 2020]. The challenge
is that irrevocable matching decisions must be made online
without precise knowledge of how demand will evolve.

Theoretical guarantees. We prove that VTG can be efficiently approximated by a “local” function in bipartite
random geometric graphs (b-RGGs). Edges in b-RGGs rely
on node similarity within a latent space, so b-RGGs often
arise in spatial crowdsourcing tasks like ridesharing, which
necessitates physical proximity between drivers and riders.

In the Online Bayesian Bipartite Matching (OBBM) problem, there is a weighted bipartite graph with online and1
Stanford University, CA, USA. Correspondence to: Anders
Wikum <wikum@stanford.edu>.

Empirical analysis. We present M AGNOLIA, a GNNbased framework for online matching that mimics OPTonby using predictions of VTG. While M AGNOLIA is only
trained on small graphs for which VTG is computable, it
still beats state-of-the-art baselines across a range of inputs.

Published at the 2 nd Differentiable Almost Everything Workshop
at the 41 st International Conference on Machine Learning, Vienna, Austria. July 2024. Copyright 2024 by the author(s).

1

MAGNOLIA

where VG (S, t, u) = wtu + VG (S \ {u}, t + 1) is the utilityof adding the edge (t, u) to the matching and making uunavailable. We will refer to V(G) := VG (L(G), 1) as thefull value-to-go computation on the input graph G.

1.2. Related work
Online Bayesian bipartite matching. OBBM is connected to the literature on online Bayesian selection problems, where a seminal result by Krengel and Sucheston[1978] implies that no algorithm can provide better than a
0.5-approximation to the offline optimal in hindsight. However, better approximation ratios are possible when competing with the optimal online algorithm OPTon [Papadimitriou et al., 2021, Braverman et al., 2022, Naor et al., 2023].

2.2. Graph neural networks(0)

Let G = (V, E, X ) be a graph with node attributes hv ∈X . A Graph Neural Network (GNN) of depth k iteratively(1)(k)
computes a sequence of embeddings hv , . . . , hv for eachnode v ∈ V . In layer i, the GNN first computes a message
(i)
(i−1)
mv for each node v from its previous embedding hv.
(i)Then, the next embedding hv is computed by aggregating(i)the messages mu from each of v’s neighbors:


(i)
m(i)
h(i−1)
for all v ∈ V
v = MSG
v


(i)
(i)
(i)
:
h(i)
=
AGGREGATE
m
,
{m
u
∈
N
(v)}
.
v
v
u

ML for combinatorial optimization. There has been significant recent interest in integrating ML with combinatorial
optimization (see, e.g., the survey by Bengio et al. [2021]).
Applications of ML to online NP-hard problems have primarily aimed to learn algorithms with good worst-case guarantees e.g. [Kong et al., 2018, Zuzic et al., 2020, Du et al.,2022]. Recent work by Alomrani et al. [2022] has considered average-case performance but is entirely empirical.

Note that a GNN can act on graphs with any number of(k)nodes, and that the embedding hv is a function only of theembeddings within a k-hop neighborhood of node v.

2. Notation and background
Let G = (L, R, E) be a bipartite graph on a set L of n
offline nodes and a set R = {1, . . . , m} of m online nodes,
with undirected edges E ⊆ L × R. Further, let N = m + n
and NG (t) denote the neighbors of online node t in G.

3. Theoretical guarantees
In this section, we identify conditions on the generating
parameters of bipartite random geometric graphs (b-RGGs)
for which VTG can be approximated by aggregating information over local neighborhoods. This result aligns with
the inherent processing capabilities of GNNs.

2.1. Online Bayesian bipartite matching (OBBM)
An input to the OBBM problem is a bipartite graph G attributed with edge weights {wij }(i,j)∈E and online node
arrival probabilities {pt }t∈R . Matching in G occurs overm timesteps. At time t ∈ [m], online node t appears independently with probability pt . If node t appears, one must
decide to match t with an unmatched neighbor or skip t.
The goal is to maximize the weight of the final matching.

3.1. Local graph decomposition
We begin by showing that, under certain conditions, b-RGGs
admit a local decomposition. Informally, this means that:
1. (Decomposable) b-RGGs can be partitioned into subgraphs such that few edges cross between subgraphs.

An algorithm for OBBM knows the input graph G but does
not know a priori which online nodes will arrive. Thus, intimestep t, if online node t arrives and S ⊆ L is the set of offline nodes that have not yet been matched, the algorithm’s
choice of which node to match t to—or whether to skip
t—is a function of S, t, and G. The optimal online algorithm OPTon computes the value-to-go function VG (S, t) to
inform its decisions. This is the maximum expected matching weight achievable in G over arrivals {t, . . . , m}, withmatchings restricted to the set of remaining offline nodes S.
Additional matches require available nodes, so VG (∅, t) = 0
for all t ∈ R and VG (S, m + 1) = 0 for all S ⊆ L. Further,
the values of VG (·) are related by the recurrence
VG (S, t) = (1 − pt ) · VG (S, t + 1)(
+ pt · max VG (S, t + 1),

maxu∈NG (t)∩S

VG (S, t, u)

2. (Local) Under mild assumptions, the number of nodes
in each resulting subgraph is relatively small.
Bipartite random geometric graphs. In b-RGGs, nodes
are connected when their embeddings are sufficiently closein some metric. Our results generalize to any p-norm.
Definition 3.1. Given a distribution D over [0, 1]d , a bipartite random geometric graph G(m, n, D, ∆) is a distribution over graphs on m online and n offline nodes where
each node has an embedding xi ∼ D. There is an edge
between online node i and offline node j if and only if∥xi − xj ∥∞ ≤ ∆.
A partition π of [0, 1]d induces a partition of b-RGGs into
subgraphs: let G(π) be formed by removing edges (i, j) inG with embeddings xi and xj in different cells of π. We
can map properties of the partition π to properties of G(π).

)
2MAGNOLIA

Random k-partitions. We introduce a random partitioning scheme that splits [0, 1]d into cells of equal volume andapplies a random “shift” to these cells in each dimension.
Definition 3.2. For k ∈ Z≥1 , a (k, s)-partition of [0, 1]d isthe partition si + {0, k1 , . . . , k−1k } along each dimension i,where si ∈ [0, k1 ].

Definition 3.8. A function f on graphs is (r, ε, δ)-locallyapproximable over a random graph family G if there is an
r-local, polynomial time-computable function h such that|f (G) − h(G)| ≤ εf (G) with probability 1 − δ over G ∼ G
and any randomness in h.
Local approximation for b-RGGs. The VTG of an
OBBM instance can only decrease after removing edges
to form G(π). Moreover, because each edge of G exists
ε⌉-partitions π,in G(π) for a 1 − ε fraction of random ⌈ 2d∆
V(G(π)) is at least (1 − ε)V(G) in expectation.

b-RGG decomposition. Let Πk denote a uniform distribution over (k, s)-partitions with s ∼ U (0, 1/k)d and callπ ∼ Πk a random k-partition. For carefully chosen k,
nearby vectors are likely to lie in the same cell of π. So,edges in G are unlikely to be removed when forming G(π).
ε
Lemma 3.3. Let x1 , . . . , xN ∈ [0, 1]d , ε > 0, ∆ ≤ 2d,ε
and k = ⌈ 2d∆ ⌉. If ∥xi − xj ∥∞ ≤ ∆, then with probability
at most ε over π ∼ Πk , xi and xj lie in different cells of π.

Lemma 3.9. For G ∈ supp(G(m,n, D, ∆)), ε > 0, andε⌉, V(G) ≥ Eπ∼Πk V(G(π)) ≥ (1 − ε)V(G).
k = ⌈ 2d∆While Ṽ(G) = Eπ∼Πk V(G(π)) can approximate V(G)to high accuracy over b-RGGs, it may not be r-local forsmall r. This requires the connected components of G(π) to
be of size at most r under all partitions π ∈ supp(Πk ). Unlike Ṽ(·), a random function that outputs a sample estimate
Pℓ1
i=1 V(G(πi )) achieves r-locality when the connectedℓcomponents of G(π1 ), . . . , G(πℓ ) are of size at most r.

Moreover, the number of b-RGG latent embeddings in any
cell of a random k-partition with Ω(N ) cells is likely to be
sublinear in N . We avoid the pathological case where D isa point mass using a concept from smoothed analysis.
Definition 3.4 (Haghtalab et al. [2022]). A distribution over[0, 1]d with density function f is β-smooth if sup f (x) ≤ β.

Lemma 3.10. Let D be β-smooth and ∆ = O(N −1/d ) forε
N sufficiently large. For ε ∈ (0, 1/2], let k = ⌈ 2d∆⌉. Withprobability 1 − δ over the draw of G ∼ G(m, n, D, ∆) andℓ ≥ ε22 log 4δ partitions π1 , . . . , πℓ ∼ Πk , each V(G(πi ))can be computed by a O(β log N )-local function andNow, treat sampling N vectors from D as a balls-into-binsprocess: balls are vectors, and bins are cells of a k-partition.
Corollary 3.5. Suppose N vectors are sampled from a βsmooth distribution over [0, 1]d . For all π ∈ supp(Πk )where k d = Ω(N ), every cell of π contains O(β log N )vectors with probability 1 − O( N1 ) for N sufficiently large.

ℓ1X
V(G(πi )) ≥ (1 − ε) E [V(G(π))].
π∼Πk
ℓ i=1

Lemma 3.3 and Corollary 3.5 give the following theorem.
Theorem 3.6. Let D be a β-smooth distribution, ∆ =εO(N −1/d ), ε > 0, and k = ⌈ 2d∆⌉. Then,

Finally, we give our main theorem.
Theorem 3.11. Given a β-smooth distribution D over[0, 1]d and ∆ = O(N −1/d ), for sufficiently large N , theVTG function V is O(β log N , ε, δ)-locally approximableover G(m, n, D, ∆) for all ε ∈ (0, 21 ] and δ ∈ (0, 1].

1. (Decomposable) For any G ∈ supp(G(m, n, D, ∆)),
each edge e ∈ E(G) appears in G(π) with probability
at least 1 − ε over the draw of π ∼ Πk .
2. (Local) For any π ∈ supp(Πk ) and N sufficiently
large, the connected components of G(π) are of sizeO(β log N ) with probability 1 − O(1/N ) over the
draw of G ∼ G(m, n, D, ∆).

4. Experiments
Additional details on our setup can be found in Appendix B,
with comprehensive experimental results in Appendix B.8.

3.2. Local approximation of value-to-go

4.1. Experimental setup

This section shows that the local decomposability of bRGGs means VTG can be approximated using local graphfunctions, which are computed on small substructures.
Definition 3.7 (Tahmasebi et al. [2023]). A function fover graphs is r-local if there is a function φ such thatf (G) = φ({Nr (v)}v∈V (G) ) where Nr (v) is the r-hop
neighborhood of node v in G.

Learned matching model. M AGNOLIA replaces the VTG
computations in OPTon with predictions from a GNN (seeFigure 1). To start, the matching state is encoded as an
attributed graph consisting of the graph G, arriving online
node t, and set of available offline nodes S. This attributedgraph is fed into a GNN, which predicts the VTG associatedwith each feasible action. The decision with the highest
predicted VTG is chosen, and the process repeats until noonline nodes remain. The GNN is trained using supervised
learning with teacher forcing on the decisions of OPTon .

We prove that with high probability, VTG is approximatedby a O(β log N )-local function, formalized as follows.
3

MAGNOLIA

0.24

0.87
0

ER, p=0.5

1.0

b-RGG, q=0.25

0.96
0.8

MAGNOLIA
greedygreedy-t
LP-rounding

0.94
0.6

0.92
0.4
0.90
0.2
0.88

0.86
0.0

Average competitive ratio

Average competitive ratio

Figure 1. M AGNOLIA’s GNN-based matching subroutine. Blue edges are in the matching at time t, the arriving node is highlighted green,
and the green edge shows M AGNOLIA’s selected action. A virtual node with zero utility (colored black) is added to allow skipping.

0.0 500.4
100 0.2
150 200 250

0.6 100 1500.8 200 250 1.0
50

Total number of nodes N

Figure 2. Evolution of average CR over ER and b-RGG graphs ofincreasing size with a 2:1 ratio of online to offline nodes.

Rideshare, Fremont

MAGNOLIA
greedygreedy-t
LP-rounding

0.8

0.95

0.6

0.90
0.4
0.2

0.85

0.0

0.0
0.5

0.2 2.0 2.5
0.4
1.0 1.5

0.50.6 1.0 1.5 0.82.0 2.5 1.0|R| / |L| regime

Figure 3. Average CR for different regimes of ER and OSMNX
graphs. |L| = 16 is fixed and |R| varies from 8 to 45 online nodes.

Instance generation. Training and testing are done on
synthetic and semi-synthetic weighted bipartite graphs witharrival probabilities pt ∼ U (0, 1). Synthetic inputs are
drawn from the Erdős-Rényi (ER) [Erdős and Rényi, 1960],
Barabási-Albert (BA) [Albert and Barabási, 2002], and geometric (b-RGG) random graph families. We generate semisynthetic graphs from OSMnx [Boeing, 2017], a library that
encodes road networks used in ride-sharing applications,and the gMission dataset [Chen et al., 2014], whose basegraph comes from crowdsourcing data for assigning workers to tasks. We say a bipartite graph has shape (|L|×|R|) if
it has |L| offline nodes and |R| online nodes.

4.2. Results
We train M AGNOLIA’s GNN on 2000 OBBM instancesfrom 3 graph configurations, then evaluate performance on
6000 unseen instances from a broader set of 12 configurations. A key characteristic of GNNs trained for combinatorial tasks is the extent to which they generalize to graphsof larger size. Despite being trained on 16-node graphs,
we see in Figure 2 that M AGNOLIA’s performance remains
consistent even for inputs up to 20 times larger.
Further, we observe that the ratio of online to offline nodes
in an input has a big impact on the performance of OBBM
algorithms. In light of this, we replace M AGNOLIA’s GNN
with a meta-model that selects between two GNNs—one
trained on graphs of size (10×6) and the other (6×10)—on
an instance-by-instance basis. Figure 3 gives generalization
results for M AGNOLIA with this meta-model. It consistently
outperforms greedy baselines and performs especially well
for ratios where LP-rounding is worst.

Baselines. We compare M AGNOLIA to several strong
baselines using average competitive ratio (CR):CR(M ) =ER, p=0.5

1.0
1.00

ℓ
k
1 X X M (Gi , aij ).
k · ℓ i=1 j=1 OPT(Gi , aij )M (G, a) is the matching weight returned by method M ongraph G with realized online node arrivals a, OPT(G, a) is
the max matching weight in G based on a priori knowledgeof a, and we average over k graphs with ℓ realizations of
the online node arrivals per graph.

5. Conclusions
In this paper, we studied Online Bayesian Bipartite Matching, a central problem in digital marketplaces. We introduced M AGNOLIA, a novel approximation to the intractable
optimal online algorithm. Theoretically, we showed thatvalue-to-go can be efficiently approximated in random geometric graphs using local functions—a process well-suited
to GNNs. Empirically, M AGNOLIA beats state-of-the-art
baselines, showing strong out-of-distribution generalization.

When an online node arrives, greedy picks the maximum
weight available edge. To trade off between short and longterm rewards, greedy-t [Alomrani et al., 2022], makes
the same decision as greedy if the edge weight is abovesome learned threshold t, and skips otherwise. Finally,
LP-rounding is a 0.632-approximation to OPTon by
Braverman et al. [2022], which is strong in practice.
4

MAGNOLIA

References

Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching:prophet inequality for vertex and edge arrival models. In
ACM Conference on Economics and Computation (EC),pages 769–787, 2020. 1

Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru
Ohta, and Masanori Koyama. Optuna: A next-generation
hyperparameter optimization framework. In International
Conference on Knowledge Discovery and Data Mining(KDD), page 2623–2631, 2019. B.6

Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. CoRR,
abs/1903.02428, 2019. B.4

Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics,
2002. 4.1, B.2.1

Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.
Smoothed analysis with adaptive adversaries. In Symposium on Foundations of Computer Science (FOCS), pages
942–953. IEEE, 2022. 3.4

Mohammad Ali Alomrani, Reza Moravej, and Elias Boutros
Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. Transactions on Machine
Learning Research (TMLR), 2022. 1.2, 4.1, B.2.2

Weiwei Kong, Christopher Liaw, Aranyak Mehta, andD Sivakumar. A new dog learns old tricks: RL finds
classic optimization algorithms. In Proceedings of theInternational Conference on Learning Representations(ICLR), 2018. 1.2

Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational
Research, 290(2):405–421, 2021. 1.2

Ulrich Krengel and Louis Sucheston. On semiamarts,
amarts, and processes with finite value. Probability on
Banach Spaces, 4:197–266, 1978. 1.2

Geoff Boeing. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65:
126–139, 2017. 4.1, B.2.2

Guohao Li, Chenxin Xiong, Ali K. Thabet, and Bernard
Ghanem. DeeperGCN: All you need to train deeper
GCNs. CoRR, abs/2006.07739, 2020. B.4, B.7

Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. An experimental study of algorithms for online bipartite matching. Journal of Experimental Algorithmics(JEA), 2020. B.2.1

Aranyak Mehta et al. Online matching and ad allocation.
Foundations and Trends® in Theoretical Computer Science, 8(4):265–368, 2013. 1

Mark Braverman, Mahsa Derakhshan, and Antonio
Molina Lovett. Max-weight online stochastic matching: Improved approximations against the online benchmark. In ACM Conference on Economics and Computation (EC), page 967–985, 2022. 1.2, 4.1

Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. A

Shaked Brody, Uri Alon, and Eran Yahav. How attentive
are graph attention networks? In Proceedings of theInternational Conference on Learning Representations(ICLR), 2022. B.7

Christopher Morris, Martin Ritzert, Matthias Fey, William L.
Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin
Grohe. Weisfeiler and leman go neural: Higher-ordergraph neural networks. In AAAI Conference on Artificial
Intelligence, 2019. B.7

Zhao Chen, Rui Fu, Ziyuan Zhao, Zheng Liu, Leihao Xia,
Lei Chen, Peng Cheng, Caleb Chen Cao, Yongxin Tong,
and Chen Jason Zhang. gmission: A general spatial
crowdsourcing platform. Proceedings of the VLDB Endowment, 7(13):1629–1632, 2014. 4.1

Joseph Naor, Aravind Srinivasan, and David Wajc. Online
dependent rounding schemes. ArXiv, abs/2301.08680,
2023. 1.2

Bingqian Du, Zhiyi Huang, and Chuan Wu. Adversarial deep learning for online resource allocation. ACM
Transactions on Modeling and Performance Evaluationof Computing Systems, 6(4):1–25, 2022. 1.2

Christos Papadimitriou, Tristan Pollner, Amin Saberi, andDavid Wajc. Online stochastic max-weight bipartite
matching: Beyond prophet inequalities. In ACM Conference on Economics and Computation (EC), page763–764, 2021. 1.1, 1.2

Paul Erdős and Alfréd Rényi. On the evolution of randomgraphs. Publications of the Mathematical Institute of the
Hungarian Academy of Sciences, 5:17–61, 1960. 4.1,
B.2.1

Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian optimization of machine learning algorithms.
In Conference on Neural Information Processing Systems(NeurIPS), pages 2951–2959, 2012. B.6
5

MAGNOLIA

Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The
power of recursion in graph neural networks for counting substructures. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 11023–
11042, 2023. 3.7
Yongxin Tong, Zimu Zhou, Yuxiang Zeng, Lei Chen, andCyrus Shahabi. Spatial crowdsourcing: a survey. The
VLDB Journal, 29:217–250, 2020. 1
Boming Zhao, Pan Xu, Yexuan Shi, Yongxin Tong, Zimu
Zhou, and Yuxiang Zeng. Preference-aware task assignment in on-demand taxi dispatching: An online stablematching approach. In AAAI Conference on Artificial
Intelligence, volume 33, pages 2245–2252, 2019. 1
Goran Zuzic, Di Wang, Aranyak Mehta, and D Sivakumar. Learning robust algorithms for online allocation
problems using adversarial training. arXiv preprint
arXiv:2010.08418, 2020. 1.2

6

MAGNOLIA

A. ProofsεεLemma 3.3. Let x1 , . . . , xN ∈ [0, 1]d , ε > 0, ∆ ≤ 2d
, and k = ⌈ 2d∆⌉. If ∥xi − xj ∥∞ ≤ ∆, then with probability at
most ε over π ∼ Πk , xi and xj lie in different cells of π.

Proof. Consider π ∼ Πk , and let πℓ be the boundaries of π along dimension ℓ for ℓ ∈ [d]. For i, j ∈ [N ] such that||xi − xj ||∞ ≤ ∆, notice that xi and xj lie in different cells of π precisely when in at least one dimension ℓ, some pointin πℓ falls in the interval [(xi )ℓ , (xj )ℓ ]. By symmetry, the probability that this occurs is equal to the length of the interval|(x ) −(x ) |[(xi )ℓ , (xj )ℓ ] over the measure of possible shifts 1/k. Moreover, i ℓ1/k j ℓ ≤ k∆, so
Pr [xi and xj lie in different cells of π] ≤ 1 − (1 − k∆)

d

π∼Πk

 !d
ε
≤1− 1−
+1 ∆
2d∆
d

ε
≤1− 1−d≤ 1 − (1 − ε)= ε.

Lemma A.1. For β ≥ 1, when N balls are dropped independently into K = Ω(N ) bins and the probability a particularβln N1ball lands in each bin is at most K, the probability the maximum load is more than 3βln ln N is O( N ) for N sufficiently large.

Proof. Let c be a constant such that K ≥ cN for N sufficiently large. Following Lemma 5.1 from [Mitzenmacher andUpfal, 2005], the probability that at least M balls are dropped in bin 1 is at most


N
M



β
K

M


N
by a union bound over the probability of each subset of M balls being dropped in bin 1. In particular, there are M
possibleM
subsets of balls, and the probability of selecting bin 1 for each of M chosen balls is bounded above by β/K . By anotherunion bound over the K bins, the probability that any bin has a load of at least M balls is at most


N
K
M
N
We use the fact that f (x) = x M  β M
x



β
K

M

.

is decreasing for x > 0 and the inequalities


N
M



1
N

M

≤

1
≤
M!



e
M

M

to conclude that

K



N
M



β
K

M

≤ cN



N
M



β
cN

M

= cN
7

 M     M

M
1
β
N
βe
·
≤ cN
.
M
c
N
cM

MAGNOLIA

For M ≥ 3β ln N/ ln ln N , the probability that any bin receives more than M balls in bounded above by
cN



βe
cM

M

3β ln N/ ln ln Ne ln ln N≤ cN
3c ln N3β ln N/ ln ln N
ln ln N≤ cN
c ln N3β ln N/ ln ln N= eln c+ln N eln ln ln N −ln ln N −ln c= eln c+(1−3β) ln N +3β ln N (for N sufficiently large.

≤ ce−2 ln N +3β ln N (c≤N= O 1/Nln ln ln N −ln c
ln ln Nln ln ln N −ln c
ln ln N))

Corollary 3.5. Suppose N vectors are sampled from a β-smooth distribution over [0, 1]d . For all π ∈ supp(Πk ) wherek d = Ω(N ), every cell of π contains O(β log N ) vectors with probability 1 − O( N1 ) for N sufficiently large.
Proof. There are k d = Ω(N ) cells of π, each of volume k1d . Since D is β-smooth, the total density of D in each cell is at
most kβd . Treating the sampling of vectors from D as a balls-into-bins process where balls are the N vectors, and bins arethe Ω(N ) cells of π, the result follows from Lemma A. We note that logloglogNN = O(log N ).
εTheorem 3.6. Let D be a β-smooth distribution, ∆ = O(N −1/d ), ε > 0, and k = ⌈ 2d∆⌉. Then,

1. (Decomposable) For any G ∈ supp(G(m, n, D, ∆)), each edge e ∈ E(G) appears in G(π) with probability at least1 − ε over the draw of π ∼ Πk .
2. (Local) For any π ∈ supp(Πk ) and N sufficiently large, the connected components of G(π) are of size O(β log N )with probability 1 − O(1/N ) over the draw of G ∼ G(m, n, D, ∆).
Proof. (1) The definition of a b-RGG ensures that for G ∈ support(G(m, n, D, ∆)) an edge (i, j) can only exist if||xi − xj ||∞ ≤ ∆. By Lemma 3.3, xi and xj belong to the same cell of π ∼ Πk with probability at least 1 − ε.
Equivalently, i and j belong to the same subgraph of G(π) with probability at least 1 − ε.
(2) Corollary 3.5 implies that for π ∈ support(Πk ), the maximum number of latent embeddings of G ∼ G(m, n, D, ∆) inany cell of π is O(β log N ) with probability at least 1 − O(1/N ). The result follows from the observation that nodes in thesame subgraph of G(π) must have latent embeddings in the same cell of π.
εLemma 3.9. For G ∈ supp(G(m, n, D, ∆)), ε > 0, and k = ⌈ 2d∆⌉, V(G) ≥ Eπ∼Πk V(G(π)) ≥ (1 − ε)V(G).
Proof. For the upper bound, we will use an inductive argument on the number of online nodes in G. It is clear that
V(G(π)) = V(G) = 0 for any partition π when G has no online nodes since there is nothing to match. Now, assume that
V(G(π)) ≤ V(G) for all graphs G ∈ support(G(m, n, D, ∆)) with at most t − 1 online nodes for some t ≥ 1 and for all
8

MAGNOLIA

partitions π. Let G ∈ support(G(m, n, D, ∆)) be a graph on t online nodes and let π be any hypercube partition. Then,
V(G) = VG (L, 1)()= (1 − p1 ) · VG (L, 2) + p1 · max VG (L, 2), max {w1u + VG (L \ {u}, 2)}u∈NG (1)()≥ (1 − p1 ) · VG(π) (L, 2) + p1 · max VG(π) (L, 2), max {w1u + VG(π) (L \ {u}, 2)}u∈NG (1)(≥ (1 − p1 ) · VG(π) (L, 2) + p1 · max VG(π) (L, 2),

maxu∈NG(π) (1)){w1u + VG(π) (L \ {u}, 2)}= VG(π) (L, 1)= V(G(π)).

The first inequality is an application of the inductive hypothesis, since VG (L, 2) and VG (L \ {u}, 2) are both full value-to-go
computations on a subgraph of G with t − 1 nodes. The second follows from the fact that NG(π) (1) ⊆ NG (1), as G(π) isformed from G by removing edges.
For the lower bound, it is helpful to first decompose the value-to-go V(G) into a contribution from each edge e ∈ E(G). To
do so, we make use of the fact that V(G) is the expected value of the matching returned by OPTon . In greater detail, leta ∈ {0, 1}m represent an arrival sequence of online nodes where node t arrives if at = 1 and does not arrive if at = 0. The
likelihood of observing different arrival sequences is governed by the arrival probability vector p. Namely, for a ∈ {0, 1}m ,Pr[a] =mY
pt · at + (1 − pt ) · (1 − at ) .

t=1

Notice that all randomness in the output of OPTon comes from the random arrivals, so given a fixed arrival sequence a,
OPTon returns a deterministic matching M (a). Then, we can write

V(G) =

Xa∈{0,1}m

Pr[a] ·Xe∈M (a)

we  =Xe∈E(G)

X

we · 

a∈{0,1}m : e∈M (a)Pr[a] =X

αe we ,e∈E(G)

where
X

αe =

Pr[a].

a∈{0,1}m : e∈M (a)Crucially, notice that for any partition π,
V(G(π)) ≥X

e∈E(G)

αe we · 1{e ∈ E(G(π))}.

The right-hand side is the expected value of the matching returned by an online algorithm on G(π) which, for any arrival
sequence a, outputs M (a) ∩ E(G(π)). The left-hand side is the expected value of the matching returned by OPTon on
G(π). It follows immediately from these facts and Lemma 3.3 that

E

π∼Πk





V(G(π)) ≥



E 

π∼Πk

X

e∈E(G)

αe we · 1{e ∈ E(G(π))} ≥ (1 − ε)9Xe∈E(G)

αe we = (1 − ε) · V(G).

MAGNOLIAε
Lemma 3.10. Let D be β-smooth and ∆ = O(N −1/d ) for N sufficiently large. For ε ∈ (0, 1/2], let k = ⌈ 2d∆⌉. With4
2
probability 1 − δ over the draw of G ∼ G(m, n, D, ∆) and ℓ ≥ ε2 log δ partitions π1 , . . . , πℓ ∼ Πk , each V(G(πi )) can
be computed by a O(β log N )-local function andℓ1X
V(G(πi )) ≥ (1 − ε) E [V(G(π))].
π∼Πk
ℓ i=1
Proof. To simplify notation, we refer to the sample mean 1ℓ

Pℓ

E [V(G(π))] as Sℓ and E[Sℓ ],i=1 V(G(πi )) and true mean π∼Πkrespectively. Also let π = {π1 , . . . , πℓ } be shorthand for an i.i.d. sample of ℓ partitions from Πk , and let G be shorthand forG(m, n, D, ∆).
Consider the following events. For G ∈ support(G) and π ∈ support(Πk ),• A(G, π) is the event that the approximation (1 − ε) · E[Sℓ ] ≤ Sℓ ≤ (1 + ε) · E[Sℓ ] holds on G for partitions π.
• B(G, π) is the event the connected components of G(πi ) are of size O(β log N ) for each partition πi ∈ π. When
this is the case, V(G(πi )) can be computed exactly by a O(β log N )-local function that simply computes VTG over aO(β log N )-hop neighborhood.
We need to show that for N sufficiently large, the event A(G, π) ∧ B(G, π) occurs with probability at least 1 − δ over the
random draws of G ∼ G and π ∼ Πk . Toward that end, notice thatPr

G∼G,π∼ΠkhA(G, π)∁ ∨ B(G, π)∁G∼G,π∼Πkhi≥1−PrA(G, π)∁ −PrA(G, π) ∧ B(G, π) = 1 −Pr

G∼G,π∼ΠkiG∼G,π∼Πkhi
B(G, π)∁ .

We have from the tower property of conditional expectation that
Pr

h

Pr

h

G∼G,π∼ΠkiA(G, π)∁ = E
Pr [A(G, π)∁ | G]
G∼G

π∼Πk

and
G∼G,π∼Πk

B(G, π)

∁

i

=

E

π∼Πk



∁



Pr [B(G, π) | π] .

G∼G

By Theorem 3.6 and a union bound over the ℓ drawn partitions, we have thathi
Pr B(G, π)∁ | π ≤ O(ℓ/N ) ≤ δ/2
G∼G

for N sufficiently large.

To bound Pr [A(G, π)∁ | G], first notice that for fixed G ∈ support(G) and π ∼ Πk , the V(G(πi ))’s are i.i.d. randomπ∼Πkvariables which take values in the interval [0, V(G)] by Lemma 3.9. Applying a standard Hoeffding bound, for ℓ ≥ ε22 log( 4δ )sampled partitions the probability of a bad approximation isiihhLemma 3.9
Pr Sℓ − E[Sℓ ] ≥ εE[Sℓ ] ≤ Pr Sℓ − E[Sℓ ] ≥ ε(1 − ε)V(G)]!
2ε2 (1 − ε)2 V(G)2≤ 2 exp −ℓ · V(G)2 /ℓ2≤ 2 exp −ℓε2 /2≤ δ/2.

10

MAGNOLIA

Thus for sufficiently large N , we’ve shown thatPr

G∼G,π∼Πk



A(G, π) ∧ B(G, π) ≥ 1 − E

G∼G

≥1− E

G∼G

= 1 − δ.




∁



Pr [A(G, π) | G] − E
π∼Πk



δ/2 − E δ/2]
π∼Πk



∁

Pr [B(G, π) | π]

G∼G



π∼Πk

Theorem 3.11. Given a β-smooth distribution D over [0, 1]d and ∆ = O(N −1/d ), for sufficiently large N , the VTG
function V is O(β log N , ε, δ)-locally approximable over G(m, n, D, ∆) for all ε ∈ (0, 12 ] and δ ∈ (0, 1].

√ε⌉ and let ε′ = 1 − 1 − ε so that (1 − ε′ )2 = 1 − ε. By Lemma 3.9 with ε = ε′ , we have that
Proof. Let k = ⌈ 2d∆Eπ∼Πk [V(G(π))] ≥ (1 − ε′ ) · V(G) for all G ∈ supp(G(m, n, D, ∆).PNow, consider the random function h(G) which1
samples ℓ = ε2′2 log( 4δ ) partitions π1 , . . . , πℓ from Πk then outputs |I|i∈I V(G(πi )), where I ⊆ [ℓ] is the set of indicesfor which V(G(πi )) is O(β log N )-local. For sufficiently large N , it follows from Lemma 3.10 for ε = ε′ that withprobability 1 − δ over the draw of G from G(m, n, D, ∆) and the randomness of h, bothℓ1X
V(G(πi )) ≥ (1 − ε′ ) E [V(G(π))] ≥ (1 − ε) · V(G)
π∼Πk
ℓ i=1
and h(G) = 1ℓPℓ

i=1 V(G(πi )).

B. Experimental Details
B.1. Value-to-go computation
We provide pseudo-code for computing value-to-go:
Algorithm 1 V(S, t)
Input: Unmatched offline node set S, timestep t, map M for memoizing intermediate computation, probability vector p
if |S| = 0 or t = m + 1 thenreturn 0
end ifif (S, t + 1) ∈/ M then
M [(S, t + 1)] = V(S, t + 1)
for u ∈ N (t) ∩ S do
if (S \ {u}, t + 1) ∈/ M then
M [(S \ {u}, t + 1)] = V(S \ {u}, t + 1)
end ifend forend ifvmax = maxu∈N (t)∩S M [(S \ {u}, t + 1)]
return (1 − pt ) · M [(S, t + 1)] + pt · max{M [(S, t + 1)], vmax }B.2. Graph generation
B.2.1. R ANDOM GRAPH FAMILIES
Erdős-Rényi (ER) [Erdős and Rényi, 1960]. Given parameters (m, n, p), we generate a bipartite graph G on m online
and n offline nodes where the edge between each (online, offline) node pair appears independently with probability p. Edgeweights are sampled from the uniform distribution U (0, 1).
11

MAGNOLIA

Barabási-Albert (BA) [Albert and Barabási, 2002]. We use a process similar to the one described in [Borodin et al.,2020] to generate scale-free bipartite graphs. Given parameters (m, n, b), we generate a bipartite graph G on m online andn offline nodes via a preferential attachment scheme:
1. Start with all n offline nodes.
2. For each online node, attach it to b offline nodes sampled without replacement, where the probability of selecting
offline node u is proportional todegree(u).
Pr[u] = P′u′ degree(u )Similarly, to ER, edge weights are sampled from the uniform distribution U (0, 1).

Geometric (b-RGG). Given parameters (m, n, q) with q ∈ [0, 1], we generate a bipartite graph G on m online and n by
doing the following:
1. Assign each online and offline node u to a uniform random position pu in [0, 1]2 .
2. Connect online node v to offline node w such thatwvw ∝ −∥pv − pw ∥2 .
3. Only keep the q fraction of edges with the largest weight.
B.2.2. S EMI - SYNTHETIC AND REAL - WORD GRAPHS
OSMnx rideshare (Rideshare). We generate a semi-synthetic ridesharing dataset using the OSMnx library [Boeing,
2017]. This dataset generation process is very similar to the one for b-RGG. To make it closer to a real-world application,
we replace distances between random points with the time to drive between intersections in a city.
For a given city and parameters (m, n, t), we uniformly sample intersections from a street map layout to generate locations
for n drivers and m riders. There is an edge between driver i and rider j if the drive time from i to j is below some thresholdt (in practice, t is set to 15 minutes). Approximate drive times are computed using the OSMnx library. Finally, edge weights
wij are generated such thatwij ∝ −(drive time from i to j).
This dataset can be thought of as a simple ridesharing application in a city. Drivers are idling, waiting to be matched to riders
who arrive online at known locations.
P The application’s goal is to minimize the sum travel time between all driver-rider
pairs or, equivalently, to maximize e∈M we where M is the online matching created by the algorithm. The threshold t is
set to avoid riders having to wait too long for a car.
In practice, we use cities of varying sizes, from several thousands of inhabitants (e.g. Piedmont, California) to several
hundreds of thousands of inhabitants (e.g. Fremont, California).
gMission. gMission is a spatial crowdsourcing dataset where offline workers are matched to tasks that arrive online. Thereis an edge between a worker u and a task v if the worker can perform that task. The associated weight wuv is the expected
payoff the worker will get from that task, computed based on some distance metric between the task’s and the worker’s
feature vectors. We note that this setting is very similar to the Random Geometric Graphs we prove results for. Inputs are
random node-induced subgraphs of the gMission base graph, which is made available by Alomrani et al. [2022].
B.3. Node, edge, and graph features
We augment our graphs with several node-level and graph-level features that the GNN can leverage to improve its predictions.
12

MAGNOLIA

Node features. On a particular instance, the GNN underlying M AGNOLIA makes a decision for each arrival of a new
online node. As the current “matching state” evolves over time, some node features remain unchanged while others are
dynamic. Static node features include a positional encoder for the nodes, a one-hot encoding for the skip node, and a binary
mask for the offline nodes. In this way, the GNN can (1) differentiate each node from all others, (2) recognize the skip
node as being different from other offline nodes, and (3) discriminate online from offline nodes. Dynamic node features
include a one-hot encoding for the node the GNN is currently matching, and an arrival probability vector that is updated to 1
(respectively, 0) for nodes that have already arrived (respectively, not arrived) in the run of the algorithm.
Edge features.

The weight wij of each edge (i, j) is encoded as a 1-dimensional edge feature.

Graph features. We use a single graph-level feature: the ratio of remaining unmatched online nodes to offline nodes.
Intuitively, an algorithm for online bipartite matching should get more greedy as this ratio goes down since greedy decisions
are unlikely to lead to later conflicts.
B.4. Architecture
The convolutional layers of our GNN follow a GENConv architecture [Li et al., 2020] and its implementation in PyTorch
Geometric [Fey and Lenssen, 2019]. The embedding update rule for this architecture mirrors the functional form of the
dynamic program representation of value-to-go:h(k)v = MLPh(k−1)+vmaxu∈N (v)n

ReLU(hu(k−1) + wvu )

o

!

.

We compare different GNN architectures for VTG approximation in Appendix B.7.
B.5. Training error and model accuracy
We train our model using mean squared error. On each training sample, the model is given a graph instance and the current
online node t. It then tries to predict the value-to-go of all nodes in the graph. The only valid actions on step t are to either
match t to one of its neighbors or not to match t which is represented by matching t to the skip node. Hence, the model’s
prediction is masked to only consider the neighbors of t (which include the skip node) and we compute the mean squared
error between those predictions and the actual value-to-go values given by the online optimal algorithm.
Model accuracy is used for hyperparameter tuning and is a good metric for the empirical performance of the GNN whenused as an online matching algorithm. It is simply computed as the percentage of times the GNN chooses the same action
as the online optimal algorithm. Here, choosing the same action could either mean matching to the same offline node orskipping the online node.
B.6. Hyperparameter tuning
We perform hyperparameter tuning using a validation set of size 300. We perform around 1000 trials, tuning the parameters
as described in Table 1. Each trial is evaluated by its validation set accuracy. The hyperparameters are tuned with Bayesian
search [Snoek et al., 2012] and pruning from the Optuna library [Akiba et al., 2019] to stop unpromising runs early. Similarly
to the training setup, the hyperparameter tuning is done on small graphs (10×6) and (6×10) even though the eventual testing
may be on larger graphs. All the training was done on an NVIDIA GeForce GTX Titan X.
B.7. M AGNOLIA using different architectures
One of M AGNOLIA’s strengths is that it is a modular pipeline that can accept any GNN architecture as a VTG approximator.
In Figure 4, we validate the choice of the GENConv architecture by including a comparison with various state-of-the-art
GNN models [Li et al., 2020, Morris et al., 2019, Brody et al., 2022]. Note that GENConv and DeeperGCN have the sameunderlying GNN but use different layers and aggregation functions. We observe that all models achieve similar competitive
ratios, with GENConv and DeeperGCN performing slightly better.
13

MAGNOLIA

Competitive Ratio

Training

GNN

Table 1. Hyperparameter ranges

ER, p=0.5

1.0

1.00

Hyperparameter# of message passing layers# of MLP layers
Hidden dimension size
Dropout
Batch size
EpochsLearning rateb-RGG, q=0.25

Values{1, . . . , 6}
{1, . . . , 5}
{2i | i ∈ {1, . . . , 6}}[0, 0.5]i{2 | i ∈ {1, . . . , 6}}{2i | i ∈ {1, . . . , 8}}[1e − 5, 1e − 10]

Rideshare, FremontgMission

0.8

0.95

GENConv
DeeperGCN
GATv2Conv
GraphConv

0.6

0.90
0.4

0.85
0.2

0.80
0.0

0.0

0.2

0.4

0.6

0.8

1.0

Figure 4. Boxplot showing the distribution of competitive ratios for M AGNOLIA with different underlying GNN architectures across graphconfigurations. All graphs are of size (10×20).

B.8. Complete results for Section 4.2
For the results in Appendices B.8.1 to B.8.3, the GNN underlying M AGNOLIA is trained on a set of 2000 instances ofgraphs from ER with p = 0.75, BA with b = 4, and GEOM with q = 0.25 of size (6×10). Reported results are distributions
and averages of competitive ratios from 6000 OBBM unseen instances of size (10×30) across 12 graph configurations. In
particular, we elected to train on a subset of graph configurations since this considerably improves training time, and in our
experience, leads to similar results.
The results in Appendix B.8.4 come from a GNN-based meta model which is given as input two GNNs trained on graphs ofsize (6×10) and (10×6), respectively. The meta-GNN is trained on the competitive ratios achieved by each GNN on 2000
instances of graphs from ER with p = 0.75, BA with b = 4, and GEOM with q = 0.25, each across graph sizes (10×6),(8×8), and (6×10). Whereas the GNN-based model selects a GNN to run each instance on using predicted competitive ratios,
the threshold-based meta algorithm simply runs on one GNN if the ratio of online nodes to offline nodes exceeds a fixed
threshold t. Empirically, we found that t = 1.5 performs well. Evaluation for both models once again happens over 6000
instances from the 12 graph configurations.
Finally, in Appendix B.8.5, we train M AGNOLIA with a different GNN on each possible noise level ρ. The training andevaluation specifications for each of these noise-dependent GNNs are the same as those from Appendix B.8.1.

14

MAGNOLIA

B.8.1. M AGNOLIA MAKES GOOD DECISIONS
Table 2. Average competitive ratio by graph configuration with node ratio (10×20).

ER

BA

GEOM
RIDESHAREGMISSION

Parameterp = 0.25
p = 0.5
p = 0.75
b=4
b=6
b=8
q = 0.15
q = 0.25
q = 0.5
city = Piedmont
city = Fremont
-

GNN
0.945
0.943
0.949
0.937
0.944
0.955
0.978
0.961
0.950
0.957
0.957
0.951

15

Greedy
0.881
0.883
0.905
0.857
0.885
0.911
0.938
0.922
0.924
0.935
0.929
0.929

Threshold Greedy
0.887
0.897
0.914
0.875
0.896
0.922
0.938
0.922
0.924
0.939
0.933
0.802

LP
0.929
0.917
0.915
0.921
0.916
0.921
0.958
0.939
0.921
0.936
0.930
0.951

MAGNOLIA

B.8.2. M AGNOLIA SHOWS SIZE GENERALIZATION

1.0

ER, p=0.25

ER, p=0.5

ER, p=0.75

BA, b=4

BA, b=6

BA, b=8

0.95
0.90
0.85
0.80
0.8

0.95

Average competitive ratio

0.90
0.85
0.6

MAGNOLIA
greedygreedy-t
LP-rounding

0.80

b-RGG, q=0.15

b-RGG, q=0.25

b-RGG, q=0.5

Rideshare, Piedmont

Rideshare, FremontgMission

0.95

0.4
0.90
0.85
0.80

0.2
0.95
0.90
0.85
0.80

0.0 50
0.0

100

150

200 2500.2

50
0.4 100150

200 0.6
250

Total number of nodes N

50100
0.8 150200

250 1.0

Figure 5. Evolution of competitive ratio over graphs of increasing size for a GNN trained on graphs of size (6×10). All test graphs have a
2:1 ratio of online to offline nodes.

16

MAGNOLIA

B.8.3. R EQUIREMENTS FOR SIZE GENERALIZATION
One of the advantages of our approach is that it performs well when trained on small graphs. Indeed, Appendix B.8.2 showsthat M AGNOLIA exhibits size generalization. Two questions remain:
1. Would we observe better performance if M AGNOLIA was trained on larger graphs?
2. How small can the training graphs be while still exhibiting size generalization?

Average competitive ratio

To address these questions, we compare the size generalization of M AGNOLIA when trained on graphs of varying size.
We see in Figure 6 that M AGNOLIA shows strong generalization to graph size, even when trained on very small graphs.
We observe that, surprisingly, the GNN trained on the smallest graphs (5×3) performs the best on gMission. This can be
explained by the fact that (5×3) graphs are more likely to be sparse, making them similar to the very sparse gMission inputs.

ER, p=0.5

1.0

0.975

b-RGG, q=0.25

Rideshare, FremontgMission

0.8
0.950

(3×5)
(6×10)(9×15)(12×20)

0.6
0.925

0.900
0.4
0.875
0.2
0.850

0.0

0.0 50100 150 200 2500.2

0.4 250
50 100 150 200

50 1000.6 150 200 250

Total number of nodes N

0.850

100 150 200 250 1.0

Figure 6. Evolution of competitive ratio over graphs of increasing size for GNNs trained on graphs of different sizes with the same (6:10)
ratio. All test graphs have a 1:2 ratio of offline to online nodes.

17

MAGNOLIA

B.8.4. M ETA - MODEL IMPROVES REGIME GENERALIZATION
1.0

1.00

ER, p=0.25

ER, p=0.5

ER, p=0.75

BA, b=4

BA, b=6

BA, b=8

0.95
0.90
0.85
0.80

0.8

1.00
0.95

Average competitive ratio

0.90
0.85
0.6
0.80

1.00

b-RGG, q=0.15

b-RGG, q=0.25

b-RGG, q=0.5

Rideshare, Piedmont

Rideshare, FremontgMission

MAGNOLIA (meta)
greedygreedy-t
LP-rounding

0.95
0.4

0.90
0.85
0.80

1.00
0.2
0.95
0.90
0.85
0.80
0.0

0.00.5

1.0

1.5

0.2
2.0

2.5

0.5 0.4 1.0

1.5

2.0

|R| / |L| regime

0.6
2.5

0.5

1.00.8 1.5

2.0

2.5

1.0

Figure 7. Evolution of competitive ratio over regimes for M AGNOLIA enabled with a meta-GNN. For evaluation, |L| is kept fixed at 16
offline nodes, and |R| varies from 8 to 64 online nodes

18

MAGNOLIA

ER, p=0.25

ER, p=0.5

ER, p=0.75

BA, b=4

BA, b=6

BA, b=8b-RGG, q=0.15

b-RGG, q=0.25

b-RGG, q=0.5

Rideshare, Piedmont

Rideshare, FremontgMission

1.0
1.00

0.98
0.96
0.94
0.92
0.90

0.8

1.00
0.98

Average competitive ratio

0.96
0.94
0.6

0.92
0.90

1.00

MAGNOLIA (meta)
threshold (meta)

0.98
0.4
0.96

0.94
0.92
0.90

1.00

0.2

0.98
0.96
0.94
0.92
0.90
0.0

0.0

1

2

0.2
3

4

0.41

2

3

|R| / |L| regime

0.6

4

1

0.8

2

3

41.0

Figure 8. Evolution of competitive ratio over regimes for M AGNOLIA enabled with a meta-GNN against simple threshold model. For
evaluation, |L| is kept fixed at 16 offline nodes, and |R| varies from 8 to 64 online nodes

19

MAGNOLIA

B.8.5. M AGNOLIA IS ROBUST TO NOISY INPUTS

1.0

ER, p=0.25

ER, p=0.5

ER, p=0.75

BA, b=4

BA, b=6

BA, b=8

0.9
0.8
0.7
0.6
0.5

0.8
0.4
0.9

Average competitive ratio

0.8
0.7

0.6
0.6
0.5
0.4

b-RGG, q=0.15

b-RGG, q=0.25

b-RGG, q=0.5

Rideshare, Piedmont

Rideshare, FremontgMission

MAGNOLIA
greedygreedy-t
LP-rounding

0.9
0.8
0.4
0.7
0.6
0.5
0.4

0.2
0.9
0.8
0.7
0.6
0.5
0.4
0.0
0.00.00.2

0.4

0.60.2 0.8

1.0

0.0 0.4
0.2

0.4

0.6

0.8
0.6 1.0

Noise standard deviation

0.0

0.2 0.80.4

0.6

0.8

1.0
1.0

Figure 9. Evolution of competitive ratio as a function of noise level ρ for graphs of size (10×30). A N (0, ρ2 ) noise is added independently
to each edge weight and arrival probability.

20