# Matching Algorithms in the Sparse Stochastic Block Model

Anna Brandenberger  Byron Chin  Nathan S. Sheffield and Divya Shyamal

(August 2023)

###### Abstract

The stochastic block model (SBM) is a generalization of the Erdős–Rényi model
of random graphs that describes the interaction of a finite number of distinct
communities. In sparse Erdős–Rényi graphs, it is known that a linear-time
algorithm of Karp and Sipser achieves near-optimal matching sizes
asymptotically almost surely, giving a law-of-large numbers for the matching
sizes of such graphs in terms of solutions to an ODE [10]. We provide an
extension of this analysis, identifying broad ranges of stochastic block model
parameters for which the Karp–Sipser algorithm achieves near-optimal matching
sizes, but demonstrating that it cannot perform optimally on general SBM
instances.

We also consider the problem of constructing a matching online, in which the
vertices of one half of a bipartite stochastic block model arrive one-at-a-
time, and must be matched as they arrive. We show that the competitive ratio
lower bound of 0.837 found by Mastin and Jaillet for the Erdős–Rényi case [16]
is tight whenever the expected degrees in all communities are equal. We
propose several linear-time algorithms for online matching in the general
stochastic block model, but prove that despite very good experimental
performance, none of these achieve online asymptotic optimality.

Stochastic Block Model, Matching Algorithms, Online Matching

## 1\. Introduction

A number of real-life allocation problems – from organ donation to ridesharing
or internet dating – can be framed as matching problems. In many settings it
is necessary to assign these matches very quickly without knowledge of future
requests. This is particularly the case for the display of ads in search
engine results: determining which ads to associate with the searched keywords
must be done nearly-instantaneously. This problem has inspired a substantial
line of research investigating the problem of online matching in random
graphs.

Most prior work on this problem assumes the vertices on one side of a
bipartite graph are drawn i.i.d. from an adversarially-chosen distribution. In
that setting, upper bounds on the competitive ratio are known [15]. However,
in Erdős–Rényi graphs, it is possible to exceed these bounds [16]. One might
therefore hope that graphs arising in nature tend to permit better online
matching algorithms than adversarial distributions. In this work, we consider
matching problems in the stochastic block model, in which vertices belong to a
constant number of “classes”, and the probability of an edge between two
vertices depends only on their classes. This is a broad class of structured
distributions on graphs, which includes the Erdős–Rényi model as a special
case.

In stochastic block models, neither the optimal online matching algorithm nor
the true matching number are known. We make progress towards both of these
questions, finding expressions for the matching number in a number of regimes,
and proposing and analyzing several heuristics for online matching.

### 1.1. Preliminaries

The idea of a population divided into a fixed number of distinct but
internally-homogeneous groups is captured by the stochastic block model, first
proposed by Holland et. al. to model social networks [7].

######  Definition 1.1 (Stochastic block model).

Consider $k$ disjoint sets of vertices (classes) $S_{1},\dots,S_{k}$, and a
symmetric probability matrix associating a value $p_{ij}$ to each pair $i,j$
of classes. Given these parameters, the stochastic block model (SBM) is the
distribution over graphs obtained by adding each edge $(u,v)$ independently
with probability $p_{\sigma_{u}\sigma_{v}}$, where $\sigma_{u}$ and
$\sigma_{v}$ are the classes to which $u$ and $v$ respectively belong (the
“labels” of $u$ and $v$).

If $k=1$, we recover the Erdős–Rényi graph $G(n,p)$ on $n$ vertices with edge
probability $p$. If $k=2$, where each class has $n$ vertices, and $p_{12}=p$,
$p_{11}=p_{22}=0$, we recover the bipartite Erdős–Rényi graph $G(n,n,p)$.

We are interested in the size of a maximum-cardinality matching on a graph
drawn from this distribution.

######  Definition 1.2 (Matching).

A matching of a graph is a subgraph $M$ such that no two edges in $M$ contain
the same vertex; in other words, every vertex is matched with at most one
other vertex via an edge. The matching number of a graph $G$ is defined as the
size of the largest matching of $G$. A matching $M$ is called perfect if
$|M|=|G|$.

We are also interested in the problem of constructing a matching online.

######  Definition 1.3 (Online bipartite matching problem).

Suppose we have a bipartite instance of the stochastic block model, where
there are $n$ “left” vertices and $n$ “right” vertices, the classes on the
left have zero connection probability to the other left classes, and likewise
the right classes have no connection probability to each other. In addition,
classes are contained entirely within either the left or right. An “online”
algorithm is given the labels of all the right vertices, and knows a
distribution over the left classes. For each of $n$ time-steps, a new left-
node is revealed (a left label is drawn from the distribution, and coins are
flipped to determine which edges it has to the right vertices) – the algorithm
then decides which if any of these edges to add to $M$. Once it has made this
decision and moved on, it is never allowed to revisit that vertex.

The most interesting range of stochastic block model parameters turns out to
be the sparse regime, when all probabilities $p_{ij}$ are $\Theta(1/n)$. The
reason for this is because when $p_{ij}$ grows faster than $1/{n}$, as $n$
grows to infinity the graph becomes dense enough that with high probability,
there is a near perfect matching between $S_{i}$ and $S_{j}$. On the other
hand, when $p_{ij}$ grows slower than ${1}/{n}$, the graph becomes so sparse
that we can include almost every edge in $M$. So, we consider the regime in
which $p_{ij}=c_{ij}/n$ for some constants $c_{ij}$.

### 1.2. Background

In 1981, Karp and Sipser demonstrated that a simple linear-time heuristic
achieves matchings within $o(n)$ of the true matching number of Erdős–Rényi
graphs [10]. By associating the performance of that algorithm with a
deterministic procedure, they were able to prove a law of large numbers on the
matching number of such graphs. That paper has prompted continued
investigation into their algorithm. In 1998, Frieze, Pittel, and Aronson
improved the error estimate of the Karp–Sipser algorithm in Erdős–Rényi graphs
from $o(n)$ to $n^{1/5+o(1)}$ [1]. In 2011, Bohman and Frieze extended
analysis of the Karp–Sipser algorithm to the model of graphs drawn uniformly
over a fixed degree sequence, showing that a log concavity condition is
sufficient for the algorithm to find near-perfect matchings in such graphs
[2]. Because of its simplicity, the Karp–Sipser algorithm has also received
attention as a practical method for data reduction; some recent work
investigates efficient implementations [12, 14].

The online bipartite matching problem was first introduced by Karp, Vazirani
and Vazirani in 1990; they showed that a tight $1-{1}/{e}$ competitive ratio
is achievable on worst-case inputs [11]. In 2009, Feldman et. al. showed that
in the model where the left vertices are instead drawn from an arbitrary known
distribution, with integral expected arrival rates, it is possible to get a
competitive ratio strictly better than $1-{1}/{e}$ [6]. The problem of online
matching in the known distribution model has since seen considerable attention
because of applications in internet ad allocation. For arbitrary distributions
(with arbitrary arrival rates), the best known algorithm achieves competitive
ratio 0.716, and there is a known upper bound of 0.823 [9, 15]. There has also
been work considering algorithms for specific left vertex distributions.
Mastin and Jaillet found that in $G(n,n,p)$, the random bipartite graph where
all edges are independent and equally likely to exist, all greedy algorithms
achieve competitive ratio at least 0.837 [16]. Sentenac et. al. studied the
problem in the 1-dimensional geometric model, where they found expressions for
both the true matching size and the performance of a particular online
heuristic [18]. To the best of our knowledge, the only previous work that
considers the stochastic block model is by Soprano-Loto et. al., who consider
the regime where the graph is dense (i.e. all probabilities are constants not
depending on $n$), and characterize when it is possible to achieve an
asymptotically near-perfect matching [19].

### 1.3. Main Contributions

We show that the Karp–Sipser algorithm achieves near-optimal matchings for
probability matrices $p_{ij}$ satisfying any of the following list of
conditions. However, the algorithm does not achieve near-optimal matchings in
general stochastic block models.

  * $\bullet$

Equitable: For every $i$,
$\sum_{j}{p_{ij}|S_{j}|}=\sum_{j}{c_{ij}|S_{j}|}/{n}=c$ for some constant $c$,
i.e., each vertex has the same expected degree, we are in the “equitable”
case. Here, we show that the asymptotic matching number for any such graph is
$\alpha n+o(n)$ where $\alpha$ is an explicit constant. See Theorem 2.8 for
the full statement.

This result was previously known for the sparse Erdős–Rényi graph $G(n,c/n)$
[10]. Equitable block models capture in particular the standard symmetric
$p_{in}$-$p_{out}$ model, in which the population is divided into equal-sized
groups, and there are distinct probabilities for connecting within-group as
opposed to across-group.

  * $\bullet$

Sub-Critical: When $\sum_{j}c_{ij}|S_{j}|/n<e$ for all $i$, we show that the
model is in a sub-critical regime similar to the one found for Erdős–Rényi
graphs. We show that the asymptotic matching number converges to the solution
of an explicit ODE, see Theorem 2.12.

  * $\bullet$

Bipartite Erdős–Rényi: We also determine, in terms of the solution of an
explicit ODE, the asymptotic matching number of $G(kn,n,c/n)$, the bipartite
graph with part sizes $kn$ and $n$ and independent edge probability $c/n$; see
Lemma 2.16. This case is of interest particularly as a simple example for
which usual arguments about the Karp–Sipser algorithm fail.

As a special case, these results imply that Mastin and Jaillet’s upper bound
on the matching number of $G(n,n,p)$ is tight, and so their 0.837 competitive
ratio lower bound for the online version is also tight. We propose a
modification of the Karp–Sipser algorithm that we conjecture to be
asymptotically optimal in general, but observe that known approaches do not
suffice to prove optimality.

With regards to the online matching problem, we analyze the following
heuristics:

  * $\bullet$

GREEDY: When a match is possible, match to a uniform random neighbour.

  * $\bullet$

DEGREEDY: Match to the available class with the lowest expected degree.

  * $\bullet$

SHORTSIGHTED: Match to the available class that maximizes the probability of
being able to match on the next step.

  * $\bullet$

BRUTE-FORCE: Precompute the expected final matching size of every possible
state, and then always match to the available class that maximizes the
expected size (this gives optimal performance among all online algorithms, but
is very inefficient).

In the equitable case, we find that all of these algorithms achieve the same
tight 0.837 competitive ratio as in $G(n,n,p)$. In the general setting, we
show that only BRUTE-FORCE achieves optimal asymptotic performance.

## 2\. Analysis of the Karp–Sipser Algorithm for Offline Matching

In 1981, Karp and Sipser proposed an algorithm for approximating the matching
number of graphs, and proved that it achieves near-optimal matching sizes on
Erdős–Rényi graphs [10]. By extending the analysis of their algorithm to the
stochastic block model case, we show a law of large numbers on the matching
size of a more general class of graph.

### 2.1. Karp–Sipser Algorithm and Outline of Analysis

The form of the Karp–Sipser algorithm we study is as follows:

Algorithm 1 Karp–Sipser

1:$M\leftarrow\emptyset$

2:$V\leftarrow V(G)$

3:while $E(G\cap V)\neq\emptyset$ do

4: if exists $v\in V$ of degree 1 – that is, such that exactly one $u\in V$
has $(uv)\in E(G)$ then

5: Choose such a $v$ uniformly at random over all degree 1 vertices

6: $M\leftarrow M\cup\\{(uv)\\}$

7: $V\leftarrow V\setminus\\{u,v\\}$

8: else

9: Choose an edge $(uv)$ uniformly randomly over all $u,v\in V$, $(uv)\in
E(G)$

10: $M\leftarrow M\cup\\{(uv)\\}$

11: $V\leftarrow V\setminus\\{u,v\\}$

12:Return $M$.

In other words, whenever there exists a vertex of degree 1 in the graph,
choose one randomly, add its edge to the matching, and remove both endpoints.
When there are no degree 1 vertices, repeatedly choose an edge at random to
add to the matching. When there exist degree 1 vertices it’s always “safe” to
add their edges in the sense that there always exists an optimal matching
which does so, and so any “mistakes” the algorithm makes can only happen after
the first time it reaches 0 degree 1 vertices (we call the steps before this
“Phase 1”, and the steps after this “Phase 2”). The analysis of this algorithm
in the Erdős–Rényi graph setting proceeds as follows [10, 1]:

  1. i)

Conditioned on the state of a Markov process on small tuples of integers, the
graph maintains a simple distribution law even after several steps of the
algorithm.

  2. ii)

Use estimates of the degree distribution of the graph to determine transition
probabilities for the Markov process.

  3. iii)

Appeal to known approximation theorems to conclude that the Markov process
stays close to the solution of a corresponding ODE as $n\to\infty$ with high
probability.

  4. iv)

Observe that, in Phase 2 of the algorithm, it is very likely that the
algorithm finds a near perfect matching on the remaining graph. Since the
algorithm makes only optimal decisions in Phase 1, this means that overall it
finds within $o(n)$ vertices of the true optimal value, and so the matching
number of the graph is described by solutions to the ODE from step (iii).

We apply steps analogous to (i)-(iii) in the general stochastic block model.
On the other hand, step (iv) of the analysis is not true in general; although
we list some interesting cases in which it is.

### 2.2. Transition Probabilities of the Karp–Sipser Algorithm in
Configuration Models

For analytical purposes, we instead consider the Karp–Sipser algorithm on
multigraphs drawn from a configuration model.

######  Definition 2.1 (Blocked configuration model).

Let $G$ be a graph drawn from a stochastic block model. For each pair of
labels $i,j$, let $m_{ij}$ denote the total number of edges between vertices
of label $i$ and vertices of label $j$ in $G$. Construct a random multigraph
as follows: if $i\neq j$, distribute $m_{ij}$ half-edges among the $i$
vertices and $m_{ij}$ half-edges among the $j$ vertices uniformly at random (à
la balls-in-bins), then define edges by a uniform random pairing between the
half edges on the $i$ and $j$ sides. If $i=j$, instead distribute $2m_{ii}$
half-edges within class $i$, then choose a uniform random pairing among those
$2m_{ii}$ half-edges. This process defines a distribution over multigraphs,
because in the process of “reshuffling” the half-edges of $G$ we introduce the
possibility of multiple edges and self-loops.

Equivalently, once the $m_{ij}$ are determined, the process chooses, uniformly
at random for each $i,j$, an ordered list of $m_{i,j}$ many edges from $i$ to
$j$ (with possible duplicates). We show in Section A.1 that any result which
holds with high probability in the blocked configuration model also holds with
high probability for the stochastic block model.

As we run the Karp–Sipser algorithm on a random multigraph, the distribution
changes, since the earlier steps of the algorithm have produced some effects
conditional on the previous states of the graph. Fortunately, it turns out
that these effects have a simple description.

######  Lemma 2.2.

Suppose we generate a graph from the blocked configuration model and run the
Karp–Sipser algorithm for an arbitrary number of steps. Then conditioned on
the following, the resulting graph is still distributed according to the
blocked configuration model.

  * $\bullet$

For each pair of $(i,k)$ of block model labels, the number $E_{ij}$ of edges
between label class $i$ and $j$ (when $i=j$, we let $E_{ij}$ denote _twice_
the number of edges lying within class $i=j$, so that $E_{ij}$ always refers
to the number of $j$-type half-edges attached to label-$i$ vertices).

  * $\bullet$

For each label class $i$, the number $T_{i}$ of label-$i$ vertices of degree
exactly 1 (the “thin” vertices).

  * $\bullet$

For each label class $i$, the number $F_{i}$ of label-$i$ vertices of degree
at least 2 (the “fat” vertices).

Thus, if we collect all of these values into a tuple $Y=(E_{ij},T_{i},F_{i})$,
the algorithm’s progress can be described by a Markov chain on $Y$.

A proof of Lemma 2.2 is given in Section A.2. In order to determine transition
probabilities of this Markov process, we note the following straightforward
lemma about the degree distribution, justified in Section A.3:

######  Lemma 2.3.

Fix a description tuple $Y$. Let $nY$ be the tuple obtained by scaling every
element of $Y$ by $n$, and let $G_{n}$ be a multigraph drawn from a blocked
configuration model conditional on tuple $nY$. Choose a uniform half-edge
incident to class $i$, and let $v$ be its incident vertex. In the limit as
$n\rightarrow\infty$, the degree of $v$ converges in distribution to

$\mathbb{P}[d(v)=k]=\begin{cases}\frac{T_{i}}{\sum_{l}E_{il}}&\text{ for
$k=1$}\\\
\frac{\left(\sum_{l}E_{il}\right)-T_{i}}{\sum_{l}E_{il}}\cdot\frac{\lambda^{k-1}}{(k-1)!e^{\lambda}\left(1-e^{-\lambda}\right)}&\text{
for $k>1$},\end{cases}$

where $\lambda$ is a solution to

$\frac{\lambda
e^{\lambda}-\lambda}{e^{\lambda}-1-\lambda}=\frac{\left(\sum_{l}E_{il}\right)-T_{i}}{F_{i}}.$

This allows us to determine the probability that a random edge is adjacent to
a degree 2 vertex, which is important for understanding the evolution of the
algorithm.

######  Corollary 2.4.

In particular, as $n\rightarrow\infty$, the probability that a random edge
into class $i$ connects to a vertex of degree exactly 2 tends to
$\frac{\left(\sum_{l}E_{il}\right)-T_{i}}{\left(\sum_{l}E_{il}\right)}\cdot\frac{\lambda}{e^{\lambda}-1}$.

The above Lemma also allows us to determine the label distribution in the
neighborhood of a randomly chosen edge.

######  Corollary 2.5.

Let $uv$ be a randomly chosen edge where $u$ has label $i$ and $v$ has label
$j$. As $n\rightarrow\infty$, the number of neighbors of $u$ with label $k$
tends to
$\frac{\left(\sum_{l}E_{il}\right)-T_{i}}{\sum_{l}E_{il}}\cdot\frac{\lambda}{1-e^{-\lambda}}\cdot\frac{E_{ik}}{\left(\sum_{l}E_{il}\right)}$.

###### Proof.

The above degree estimates tell us that there are
$\frac{\left(\sum_{l}E_{il}\right)-T_{i}}{\sum_{l}E_{il}}\cdot\frac{\lambda}{1-e^{-\lambda}}$
other edges out of $u$ in expectation. Because half-edges of all types are
distributed interchangeably, the fraction of them that go to label $k$ is
$\frac{E_{ik}}{\left(\sum_{l}E_{il}\right)}$. ∎

From these degree distribution estimates, we produce estimates on the
transition probabilities of the Markov process. On each step of the algorithm,
if there exist degree 1 vertices, the algorithm chooses one of them and
removes it and its neighbour. So, the graph loses one edge from between class
$i$ and $j$ whenever that degree 1 vertex has its edge between $i$ and $j$.
When the neighbour vertex is in class $i$, the graph also loses edges equal to
however many neighbours it had in class $j$. Similar accounting can be made
for the number of fat or thin vertices in a class: the graph loses a fat
vertex either by having it as the neighbour of the degree 1 vertex we removed,
or by having it initially have degree 2 and appear as the neighbour of a
removed neighbour, so that it’s then reduced to degree 1. A thin vertex is
lost whenever its the removed degree 1 vertex, whenever its the neighbour of
the removed vertex, or whenever its a neighbour of the neighbour of a removed
vertex, but gain one whenever a degree 2 vertex is a neighbour-of-the-
neighbour. To make these expressions explicit, we define the notation:

  * $\bullet$

Let $h_{i}$ denote the total number of half-edges in class $i$,

$h_{i}=\sum_{l}E_{il}.$

  * $\bullet$

Let $\omega_{ij}$ denote the probability that a randomly selected degree-1
vertex is in class $i$ and has its neighbour in class $j$,

$\omega_{ij}=\frac{T_{i}}{\sum_{l}T_{l}}\cdot\frac{E_{ij}}{h_{i}}.$

  * $\bullet$

Let $\delta_{ij}$ denote expected number of other $j$-type half-edges attached
to the vertex a random half-edge in class $i$ is attached to. If $\lambda$ is
a solution to
$\frac{\lambda(e^{\lambda}-1)}{e^{\lambda}-1-\lambda}=\frac{h_{i}-T_{i}}{F_{i}}$,
then, by our degree estimates,

$\delta_{ij}=\frac{h_{i}-T_{i}}{h_{i}}\cdot\frac{\lambda}{1-e^{-\lambda}}\cdot\frac{E_{ij}}{h_{i}}.$

  * $\bullet$

Let $\theta_{i}$ denote the probability that a random half-edge attached to
class $i$ is attached to a degree 2 vertex. Again, letting
$\frac{\lambda(e^{\lambda}-1)}{e^{\lambda}-1-\lambda}=\frac{h_{i}-T_{i}}{F_{i}}$,
we have

$\theta_{i}=\frac{h_{i}-T_{i}}{h_{i}}\cdot\frac{\lambda}{e^{\lambda}-1}.$

Now, while there are degree-1 vertices remaining in the graph, we can write
the expected change in the description tuple after one step of the algorithm
as

$\displaystyle\mathbb{E}[\Delta E_{ij}]$
$\displaystyle=-\omega_{ij}-\omega_{ji}-\sum_{l}\omega_{li}\delta_{ij}-\sum_{l}\omega_{lj}\delta_{ji}$
$\displaystyle\mathbb{E}[\Delta F_{i}]$
$\displaystyle=-\left(\sum_{l}\omega_{li}\right)\left(\frac{h_{i}-T_{i}}{h_{i}}\right)-\sum_{j}\sum_{l}\omega_{jl}\delta_{li}\theta_{i}$
$\displaystyle\mathbb{E}[\Delta T_{i}]$
$\displaystyle=-\left(\sum_{l}\omega_{il}\right)-\left(\sum_{l}\omega_{li}\right)\left(\frac{T_{i}}{h_{i}}\right)-\sum_{j}\sum_{l}\omega_{jl}\delta_{li}\left(\frac{T_{i}}{h_{i}}-\theta_{i}\right).$

On the other hand, when there are no degree 1 vertices remaining, we choose an
edge uniformly at random, so, by similar reasoning,

$\displaystyle\mathbb{E}[\Delta E_{ij}]$
$\displaystyle=-\left(\frac{2E_{ij}}{\sum_{k}h_{k}}\right)-\left(\frac{2h_{i}}{\sum_{k}h_{k}}\right)\delta_{ij}-\left(\frac{2h_{j}}{\sum_{k}h_{k}}\right)\delta_{ji}$
$\displaystyle\mathbb{E}[\Delta F_{i}]$
$\displaystyle=-\left(\frac{2h_{i}}{\sum_{k}h_{k}}\right)-\sum_{l}\left(\frac{2h_{l}}{\sum_{k}h_{k}}\right)\delta_{li}\theta_{i}$
$\displaystyle\mathbb{E}[\Delta T_{i}]$
$\displaystyle=\sum_{l}\left(\frac{2h_{l}}{\sum_{k}h_{k}}\right)\delta_{li}\theta_{i}.$

We now argue that the evolution of Phase 1 of the algorithm stays close to the
solution of an ODE.

### 2.3. Convergence to Continuous Approximation

Associating Markov processes on graphs to differential equations is a very
useful tool, and there have been a variety of versions of this argument with
varying levels of generality and probability bound guarantees [13, 5]. Here,
we justify the passage to differential equations by Wormald’s theorem [21],
although we relegate the verification of the technical conditions of the
theorem to Appendix D. The important thing to note is that the expected
transitions above are “scale-invariant”, meaning that they remain the same
upon re-scaling all entries in $Y$ by the same amount. So, letting
$\bar{E}_{ij}={E_{ij}}/{n}$, $\bar{T}_{i}={T_{i}}/{n}$,
$\bar{F}_{i}={F_{i}}/{n}$, we can write (for Phase 1):

$\displaystyle\mathbb{E}[\Delta\bar{E}_{ij}]$
$\displaystyle=\frac{-\omega_{ij}-\omega_{ji}-\sum_{l}\omega_{li}\delta_{ij}-\sum_{l}\omega_{lj}\delta_{ji}}{n}$
$\displaystyle\mathbb{E}[\Delta\bar{F}_{i}]$
$\displaystyle=-\frac{\left(\sum_{l}\omega_{li}\right)\left(\frac{\bar{h}_{i}-\bar{T}_{i}}{\bar{h}_{i}}\right)-\sum_{j}\sum_{l}\omega_{jl}\delta_{li}\theta_{i}}{n}$
$\displaystyle\mathbb{E}[\Delta\bar{T}_{i}]$
$\displaystyle=-\frac{\left(\sum_{l}\omega_{il}\right)-\left(\sum_{l}\omega_{li}\right)\left(\frac{\bar{T}_{i}}{\bar{h}_{i}}\right)-\sum_{j}\sum_{l}\omega_{jl}\delta_{li}\left(\frac{\bar{T}_{i}}{\bar{h}_{i}}-\theta_{i}\right)}{n}.$

This is a process that takes order $n$ time steps, and where the expected
change at each time step scales like $\frac{1}{n}$. Informally, we can observe
that in the limit of $n$, the many small steps should average out and produce
a process evolving according to their expectations; this suggests looking at
the following system of equations:

$\displaystyle\frac{d}{dt}\bar{E}_{ij}(t)$
$\displaystyle=-\omega_{ij}(t)-\omega_{ji}(t)-\sum_{l}\omega_{li}(t)\delta_{ij}(t)-\sum_{l}\omega_{lj}(t)\delta_{ji}(t)$
$\displaystyle\frac{d}{dt}\bar{F}_{i}(t)$
$\displaystyle=-\left(\sum_{l}\omega_{li}(t)\right)\left(\frac{\bar{h}_{i}(t)-\bar{T}_{i}(t)}{\bar{h}_{i}(t)}\right)-\sum_{j}\sum_{l}\omega_{jl}(t)\delta_{li}(t)\theta_{i}(t)$
$\displaystyle\frac{d}{dt}\bar{T}_{i}(t)$
$\displaystyle=-\left(\sum_{l}\omega_{il}(t)\right)-\left(\sum_{l}\omega_{li}(t)\right)\left(\frac{\bar{T}_{i}(t)}{\bar{h}_{i}(t)}\right)-\sum_{j}\sum_{l}\omega_{jl}(t)\delta_{li}(t)\left(\frac{\bar{T}_{i}(t)}{\bar{h}_{i}(t)}-\theta_{i}(t)\right)$

with initial conditions

$\bar{E}_{ij}(0)=c_{ij}\bar{S}_{i}\bar{S}_{j},\ \
\bar{F}_{i}(0)=1-\Big{(}1+\sum_{j}c_{ij}\bar{S}_{j}\Big{)}e^{-\sum_{j}c_{ij}\bar{S}_{j}}\
\text{ and }\
\bar{T}_{i}(0)=\Big{(}\sum_{j}c_{ij}\bar{S}_{j}\Big{)}e^{-\sum_{j}c_{ij}\bar{S}_{j}},$

where $c_{ij}$ and $\bar{S}_{i}={|S_{i}|}/{n}$ are the connection
probabilities and label class sizes, respectively, of the stochastic block
model instance. Wormald’s theorem guarantees that, in the limit of $n$, the
evolution of Phase 1 stays close to the unique solution of this ODE with
probability approaching 1 (this is formally justified in Appendix D). This
implies the following:

######  Lemma 2.6.

If
$\mathcal{Y}(t)=\\{\mathcal{\bar{E}}_{ij},\mathcal{\bar{F}}_{i},\mathcal{\bar{T}}_{i}\\}$
is a solution to the above ODE, with high probability, the total number of
unmatched isolated vertices created in Phase 1 of the Karp–Sipser algorithm is
$n\left(1-\tau-\mathcal{\bar{F}}_{i}(\tau)\right)+o(n)$, where $\tau$ is the
first time such that $\mathcal{\bar{T}}_{i}(\tau)=0$ for all $i$.

These equations don’t seem to have a simple analytical solution in general,
but they can be effectively numerically evaluated for any specific stochastic
block model instance. In the Erdős–Rényi case, studying Phase 2 of the
Karp–Sipser algorithm reveals that with high probability at most $o(n)$
unmatched isolated vertices are created, meaning that the algorithm is
asymptotically optimal, and that the true matching size is
$n\left(\tau+\mathcal{\bar{F}}_{i}(\tau)\right)+o(n)$ with high probability.
However, this analysis turns out not to work for general stochastic block
model instances. We first illustrate a few examples (namely the equitable and
sub-critical cases) where, with a little bit of work, we can prove similar
results; then, we examine where the algorithm fails.

### 2.4. Equitable Case

The first, and most important success story we show for the Karp–Sipser
algorithm happens in a case we denote “equitable”:

######  Definition 2.7.

We call stochastic block model parameters equitable if there is some constant
$c$ such that for all classes $i$,

$\sum_{j}\frac{c_{ij}|S_{j}|}{n}=c.$

In other words, although the edge density in some parts of the graph may be
higher than other parts, the expected degree of every vertex is $c$ regardless
of what label class it belongs to. In these cases, we show that not only does
the Karp–Sipser algorithm construct an asymptotically-optimal matching, but
that the matching size it constructs is asymptotically the same as the
matching number of the Erdős–Rényi graph $G(n,c/n)$. The intuition behind this
claim is that, despite the nontrivial correlation between the edges of the
graph, we expect the degree distributions to look the same everywhere. So,
since our estimates of transition probabilities were functions of the degree
distributions, they should evolve similarly to the Erdős–Rényi case. The
crucial point we need to justify to make this intuition precise is that the
degree distributions necessarily remain close to equal across classes, given
that they start that way.

######  Theorem 2.8.

With high probability, the matching number of an equitable stochastic block
model is

$\left(1-\frac{x+ce^{-x}+xce^{-x}}{2c}\right)n+o(n),$

where $x$ is the smallest solution to $x=ce^{-ce^{-x}}$, and the Karp–Sipser
algorithm achieves within $o(n)$ of this value.

The theorem is proven with the help of the following two lemmas.

######  Lemma 2.9.

Given an equitable stochastic block model, after Phase 1 of the Karp–Sipser
algorithm, with high probability for every $i$, $F_{i}$ (number of vertices)
and $h_{i}$ (total number of incident edges) differ by at most $o(n)$ from the
corresponding values in $G(n,\frac{c}{n})$.

###### Proof.

This follows directly from our application of Wormald’s theorem. We know that
initially all ${\bar{T}_{i}}/{\bar{S}_{i}}$, ${\bar{F}_{i}}/{\bar{S}_{i}}$’s
and ${\bar{h}_{i}}/{\bar{S}_{i}}$’s are equal; now observe that if that
equality holds at some time $t$, we have

$\displaystyle\frac{d}{dt}\bar{h}_{i}(t)$
$\displaystyle=\sum_{j}\frac{d}{dt}\bar{E}_{ij}(t)=\sum_{j}\left(-\omega_{ij}(t)-\omega_{ji}(t)-\sum_{l}\omega_{li}(t)\delta_{ij}(t)-\sum_{l}\omega_{lj}(t)\delta_{ji}(t)\right)=\bar{S}_{i}\left(-2-2\delta\right)$
$\displaystyle\frac{d}{dt}\bar{F}_{i}(t)$
$\displaystyle=-\left(\sum_{l}\omega_{li}(t)\right)\left(\frac{\bar{h}_{i}(t)-\bar{T}_{i}(t)}{\bar{h}_{i}(t)}\right)-\sum_{j}\sum_{l}\omega_{jl}(t)\delta_{li}(t)\theta_{i}(t)=\bar{S}_{i}\left(\frac{\bar{h}-\bar{T}}{\bar{h}}-\delta\theta\right)$
$\displaystyle\frac{d}{dt}\bar{T}_{i}(t)$
$\displaystyle=-\left(\sum_{l}\omega_{il}(t)\right)-\left(\sum_{l}\omega_{li}(t)\right)\left(\frac{\bar{T}_{i}(t)}{\bar{h}_{i}(t)}\right)-\sum_{j}\sum_{l}\omega_{jl}(t)\delta_{li}(t)\left(\frac{\bar{T}_{i}(t)}{\bar{h}_{i}(t)}-\theta_{i}(t)\right)=\bar{S_{i}}\left(\frac{\bar{T}}{\bar{h}}-\delta\left(\frac{\bar{T}}{\bar{h}}-\theta\right)\right),$

where $\bar{h}={\bar{h}_{i}}/{\bar{S}_{i}}$,
$\bar{T}={\bar{T}_{i}}/{\bar{S}_{i}}$, $\delta$ is our estimate on the
expected degree - 1 of the vertex attached to a random half-edge, and $\theta$
is our estimate on the probability the degree of the vertex attached to a
random half-edge is exactly 2 (it can be seen from our estimates that these
values are the same across classes). Note that these values evolve the same
way in every class, just scaled by the size of the class.

So, in a solution to these equations, the values of
${\bar{T}_{i}}/{\bar{S}_{i}}$, ${\bar{F}_{i}}/{\bar{S}_{i}}$ and
${\bar{h}_{i}}/{\bar{S}_{i}}$ remain equal across classes for all time, and
the evolution of the total number of edges, thin vertices, and fat vertices
follows the same trajectory as it would in $G(n,c/n)$. Since Wormald’s theorem
guarantees that with high probability Phase 1 differs by at most $o(n)$ from a
solution to this equation, we have the desired statement. ∎

######  Lemma 2.10.

At the start of Phase 2 of the Karp–Sipser algorithm, if the values of
${F_{i}}/{\bar{S}_{i}}$ and ${h_{i}}/{\bar{S}_{i}}$ each differ by at most
$o(n)$ between classes, then with high probability, at most $o(n)$ isolated
vertices are produced in Phase 2.

###### Proof.

Fix some constant $\epsilon>0$. We want to show that for any such $\epsilon$,
the probability of isolating more than $\epsilon n$ vertices over the course
of Phase 2 tends to 0 as $n\to\infty$. We divide our analysis into two parts:

  1. i)

First, we consider the case where the average degree
${h_{i}}/{F_{i}}>2+\epsilon$ for all classes $i$. In this regime, we argue
that the number of steps between the times when the graph is free of thin
vertices is small, so we can again control the evolution by an ODE. The
following is a rough sketch of the argument (a more detailed justification of
these points involving Wormald’s theorem is given in Appendix D):

When we first remove a random edge, this may create some vertices of degree 1.
In removing those, we may create more vertices of degree 1. In general, the
expected number of new degree-1 vertices created when a degree-1 vertex of
class $i$ is removed is
$\sum_{j}\frac{E_{ij}}{h_{i}}\delta_{i}\theta_{j}\leq\left(\max_{i}\delta_{i}\right)\left(\max_{j}\theta_{j}\right)$.
Now, when we have that the average degree in each class is at least
$2+\epsilon$, and we know that the difference in average degree between any
pair of classes $i$ and $j$ is very small (say, less than $\gamma$), then we
know
$\delta_{i}\theta_{j}=\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{j}}{e^{\lambda_{j}}-1}<1-\eta$
for any pair $i$, $j$ of classes, where $\eta$ depends on $\gamma$ and
$\epsilon$ (the existence of some $\gamma>0$, $\eta>0$ in terms of $\epsilon$
with this property is guaranteed by a continuity argument). So, the expected
number of degree-1 vertices created for each degree-1 vertex removed is at
most a constant, $1-\eta$, that is less than 1. The size of a subcritical
Galton–Watson tree with $1-\eta$ expected offspring is very unlikely to exceed
a bound in terms of $\eta$. Thus, while we are within the region where average
degrees are $\gamma$-close and greater than $2+\epsilon$, the duration of a
”run” of degree-1 stripping is unlikely to be much more than a constant
independent of $n$. Since the length of each run is small, we can appeal to
the law of large numbers and claim the process evolves like its expectation.
Whenever the average degree is the same in all classes, the expected change in
the number of edges of a given type is proportional to the number of edges
currently of that type (all edges in the graph are equally likely to be chosen
as the first edge removed, equally likely to be the edge chosen one step into
the run, etc). So, since average degrees start out $o(1)$ away from each
other, we expect them to remain that way up until one of them drops below
$2+\epsilon$. Also, for a run of constant length we expect to create $o(1)$
isolated vertices, so the total number created while we’re in this regime is
$o(n)$ with high probability.

  2. ii)

Once we’ve left that region and the average degree in some class has dropped
below $2+\epsilon$, by the above analysis the average degree in every class is
$o(1)$ away from $2+\epsilon$. If we perform another run of the algorithm,
we’re no longer guaranteed that the expected change in number of degree-1
vertices is bounded away from 1 – we do know, however, that the only way to
remove a thin vertex and create more than one in its place is to have its
neighbour have degree greater than 2. Since no class has average degree more
than $2+2\epsilon$, we know that the entire graph has at most $2n\epsilon$
edges associated with vertices of degree greater than 2. Those edges are the
only places we can branch out and create more degree-1 things than we consume,
so, throughout the course of the rest of the algorithm, there can never be
more than $2n\epsilon$ thin vertices in the graph at once.

Now, note that the rate of creation of isolated vertices on a given step is
always proportional to the fraction of thin vertices in the graph: when we
remove a vertex (the neighbour of a thin vertex), it has $\delta_{i}<2$ other
neighbours in expectation, and by our Markov property we know that those
neighbour edges are equally likely to be any of the edges leaving the class.
So, the number of vertices isolated at each step is in expectation at most
$\frac{2}{v}$ times the total number of degree-1 vertices, where $v$ is the
total number of vertices in the graph. By another law-of-large-numbers
argument, when we perform $\Theta(n)$ such steps, the probability of being a
total of $\Theta(n)$ above this expected bound is $o(1)$. So, we can upper
bound the number of isolated vertices by

$2\epsilon n+\int_{2\epsilon n}^{n}\frac{2}{v}2\epsilon ndv=2\epsilon
n\left(1-2\log(2\epsilon)\right).$

We can make this arbitrarily small by choice of $\epsilon$; so, with high
probability the total number of vertices isolated in Phase 2 is $o(n)$. ∎

###### Proof of Theorem 2.8.

This follows directly from Lemmas 2.9 and 2.10. In Phase 1, the Karp–Sipser
algorithm is guaranteed to perform optimally, and in Phase 2, with high
probability, it isolates only $o(n)$ vertices, so the algorithm is within
$o(n)$ of optimal. Since the ODE determining the evolution of Phase 1 evolves
the same as in an Erdős–Rényi graph with parameter $c/n$, the total number of
lost vertices must be within $o(n)$ of the number lost in the Erdős–Rényi
case. Since the above expression is known to be the matching number in the
Erdős–Rényi case [10, 1], it must therefore also be here. ∎

### 2.5. Sub-Critical case

In the Erdős–Rényi case, Karp and Sipser proved that the number of unmatched
non-isolated vertices remaining in the graph after Phase 1 (which we follow
recent literature in calling the “Karp–Sipser core” [3]) is $o(n)$ with high
probability if $c<e$, and $\Theta(n)$ with high probability if $c>e$ [10]. We
have seen that, even when we allow some correlation into the graph in terms of
different classes, so long as the expected degree into all vertices is the
same across classes, the progress of the algorithm is the same as if the graph
was Erdős–Rényi. This implies that any equitable stochastic block model also
follows this critical transition at $c=e$. In this section, we examine
criticality in the non-equitable case – can we describe a similar phase
transition in terms of the expected degrees of a general block model? We might
initially expect a statement of the following form:

######  Claim 2.11 (False).

The Karp–Sipser core of a graph drawn from a stochastic block model is $o(n)$
with high probability (that is, Phase 1 strips away all but a sublinear number
of vertices) if and only if the expected degree $\sum_{j}c_{ij}\bar{S_{j}}$ is
less than $e$ for all classes $i$.

We prove the “if” direction of this claim. However, the “only if” direction
turns out not to be true – in fact, it appears to be possible for the model to
be subcritical even when $\sum_{j}c_{ij}\bar{S_{j}}>e$ for all $i$. A complete
characterization of the critical boundary is left as an open question.

######  Theorem 2.12.

If $\sum_{j}c_{ij}\bar{S_{j}}<e$ for all classes $i$, then the size of the
Karp–Sipser core is $o(n)$.

In principle, analysis of the criticality of the Karp–Sipser algorithm could
be done by analysis of the ODE from Section 2.3; however, instead of trying to
understand that system in general, we follow the methodology of Karp and
Sipser’s original paper in associating the probability of removing a vertex in
the graph with the probability of removing the root of a random tree [10]. We
note the following facts:

######  Fact 2.13 (Karp and Sipser [10]).

The set of vertices removed by Phase 1 is fixed, regardless of the order in
which degree-1 vertices are stripped. So, if there exists some valid sequence
of degree-1 strippings that removes a given vertex $v$ from the graph (either
matching or isolating it), that vertex is not in the Karp–Sipser core.

######  Fact 2.14 (Implied by a result of Mossel, Neeman and Sly [17] for 2
classes; Sly and Chin [4] for greater than 2 classes).

For any constant $d$, in the limit of $n$ the $d$-neighbourhood of any vertex
of $G$ (i.e., the subgraph obtained by a BFS of depth $d$ from the vertex)
converges in distribution to the first $d$ levels of a multitype branching
process, where nodes of type $i$ have independently Pois($c_{ij}\bar{S_{j}}$)
children of type $j$, and the root class corresponds to the class of the
vertex in $G$.

If we can show that, under certain conditions, with probability tending to $1$
with $d$, there exists a sequence of valid Karp–Sipser vertex removals in this
tree, all of which are at depth at most $d$, and which result in the root
being removed, this then implies that the Karp–Sipser algorithm is
subcritical. This is because we know that, in the limit of $n$, any structure
that appears in the first $d$ levels of the tree is equally likely to appear
in the $d$-neighbourhood of a given vertex in $G$; so, if with probability at
least 1 - $\epsilon$ there is a way to remove the root of such a tree for any
root class, the expected number of vertices remaining in $G$ after Phase 1 is
at most $\epsilon n$. The following characterizes these conditions:

######  Lemma 2.15.

The probability of removing the root of this branching process tends to $1$ in
the limit of $d$ whenever the following system has no more than one solution
$(x_{1},\dots,x_{q})$ in $[0,1]^{q}$:

$x_{i}=e^{-\left(\sum_{j}c_{ij}\bar{S}_{j}e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)}.$

The proof of Lemma 2.15 is given in Appendix B, where it is derived as a
corollary of results about winning probabilities of games on multitype
branching processes (those results are an extension of work of Holroyd and
Martin on Galton–Watson trees [8], and may be of independent interest). We now
prove the forward (true) direction of our claim.

###### Proof of Theorem 2.12.

By the above analysis, it suffices to show that whenever
$\sum_{j}c_{ij}\bar{S_{j}}<e$ for all classes $i$, the function

$\begin{bmatrix}x_{1}\\\ \dots\\\
x_{q}\end{bmatrix}\mapsto\begin{bmatrix}e^{-\left(\sum_{j}c_{1j}\bar{S}_{j}e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)}\\\
\dots\\\
e^{-\left(\sum_{j}c_{qj}\bar{S}_{j}e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)}\end{bmatrix}-\begin{bmatrix}x_{1}\\\
\dots\\\ x_{q}\end{bmatrix}$

has only one root on $[0,1]^{q}$. Denoting
$e^{-\left(\sum_{j}c_{ij}\bar{S}_{j}e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)}$
as $f_{i}$, the Jacobian of this function looks like

$\begin{bmatrix}f_{1}\left(\sum_{j}\left(c_{1j}\bar{S}_{j}\right)\left(c_{j1}\bar{S}_{1}\right)e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)-1&\dots&f_{1}\left(\sum_{j}\left(c_{1j}\bar{S}_{j}\right)\left(c_{jq}\bar{S}_{q}\right)e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)\\\
\dots&\dots&\dots\\\
f_{q}\left(\sum_{j}\left(c_{qj}\bar{S}_{j}\right)\left(c_{j1}\bar{S}_{1}\right)e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)&\dots&f_{q}\left(\sum_{j}\left(c_{qj}\bar{S}_{j}\right)\left(c_{jq}\bar{S}_{q}\right)e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\right)-1\\\
\end{bmatrix}.$

The sum of the entries in the $i$th row of this matrix is

$f_{i}\left(\sum_{j}\left(c_{ij}\bar{S}_{j}e^{-\left(\sum_{k}c_{jk}\bar{S}_{k}x_{k}\right)}\cdot\sum_{l}\left(c_{jl}\bar{S}_{l}\right)\right)\right)-1.$

By assumption, we know $\sum_{l}\left(c_{jl}\bar{S}_{l}\right)<e$. So, the
above expression is strictly less than

$ef_{i}\log f_{i}-1.$

For any value of $f_{i}$, $ef_{i}\log f_{i}$ is at most 1 (taking the
derivative, we find a unique maximum at $f_{i}={1}/{e}$). So, we have shown
that the sum of every row of the Jacobian is negative everywhere. Now, suppose
that this function has two distinct roots, $x=(x_{1},\dots,x_{q})$ and
$y=(y_{1},\dots,y_{q})$. Let $i$ be the index where $y_{i}-x_{i}$ is maximal.
We have increased $x_{i}$ by $(y_{i}-x_{i})$, and increased all the other
coordinates of $x$ by at most $(y_{i}-x_{i})$. We know that the directional
derivative of the $i$th coordinate in the $[1,\dots,1]^{\top}$ direction is
negative, and that the partial derivative with respect to every $j\neq i$ is
positive; this implies that the $i$th coordinate of the function at $y$ must
be smaller than the $i$th coordinate of the function at $x$, so they cannot
both be roots. ∎

As a consequence of this, since the Karp–Sipser algorithm is guaranteed to be
optimal in Phase 1, we know the Karp–Sipser algorithm gives a near-optimal
matching whenever $\sum_{j}c_{ij}\bar{S_{j}}<e$ for all $i$. By examining the
system given in Lemma 2.15, however, we find that this is not a necessary
condition for subcriticality. In fact, it is possible to achieve
subcriticality even when every class has expected degree more than $e$. In
Figure 1, we give a plot demonstrating this for the two-class model where one
class has internal edge probability $\frac{5.6}{n}$ and external edge
probability $\frac{5.6}{n}$, and the other class has no internal edge
probability. Note that in this case, the expected degree of a vertex in the
first class is $5.6>2e$, and the expected degree of a vertex in the second
class is $2.8>e$. If we removed either the across edges or the internal edges,
the model would be supercritical; however, both edge sets together cancel out
and become subcritical again.

Figure 1: A plot showing that for $c_{11}=5.6$, $c_{12}=5.6$, $c_{22}=0$, the
system has only 1 fixed point, and so we are subcritical. Here the horizontal
axis is $x_{1}$ and the vertical axis is $x_{2}$; the green line is the set of
points fixing $x_{1}$ and the yellow line is the set of points fixing $x_{2}$.
Note that they have only a single intersection.

The values of $5.6$, $5.6$, $0$ were chosen above to make the single fixed
point easily visible in the plot; it is possible to make these parameters
larger. When there are 2 classes, we find that it’s possible to make $c_{11}$
as high as $33.5$ while still maintaining criticality (by setting
$c_{12}=2e+0.0514$, $c_{22}=0$), but it is not possible to make it higher than
$34$.

Qualitatively, the reason for this behaviour is that, when there are no
internal edges in the second class, there is a back-and-forth thinning that
can happen. That is, once we strip off all the degree-1 vertices lying
entirely within the first class, the number of vertices in the first class
becomes lower, so the average degree of vertices in the second class has now
been decreased. Removing all the vertices of degree 1 in the second class in
turn thins the first class, and it becomes possible to remove almost all the
vertices in the graph, even though either of the two edge sets on their own
wouldn’t have been possible to remove.

### 2.6. Failure of the Karp–Sipser algorithm

In the previous sections we gave two instances where we can guarantee that the
Karp–Sipser algorithm achieves a near-optimal matching, both which use
essentially the same framework as the Erdős–Rényi case (i.e., showing that it
can achieve within $o(n)$ of a perfect matching during Phase 2, either because
all degrees are close to 2 in the equitable case, or because the entire
remaining graph has $o(n)$ vertices in the subcritical case). However, the
algorithm does not return a near-optimal matching in general, and even when it
does, this analytical framework does not always work.

For example, consider a stochastic block model with 4 classes, all of size
$n/4$, and the following probability matrix:

$\begin{bmatrix}0&\frac{100}{n}&0&0\\\ \frac{100}{n}&0&\frac{10000}{n}&0\\\
0&\frac{10000}{n}&0&\frac{100}{n}\\\ 0&0&\frac{100}{n}&0\end{bmatrix},$

see Figure 2 for an illustration. Here, we expect the true matching size to be
very close to perfect. Even if we ignore all of the edges between classes 2
and 3 entirely, we are left with two copies of $G(n/4,n/4,p)$, for which we
know the matching number (as it is equitable) – asymptotically, we can match

However, when we analyze the performance of the Karp–Sipser algorithm, we find
a different story. Phase 1 finishes very quickly, because the graph is dense
enough that very few degree 1 vertices are created. Then, in Phase 2, for a
long time we are in the regime of short runs as described in our analysis of
the equitable case; in this regime, the algorithm chooses many of its edges
uniformly at random, and so likely choose many of them from between classes 2
and 3. Every edge choosen between classes 2 and 3, however, effectively
decreases the matching number by 1. Formalizing this argument reveals that the
Karp–Sipser algorithm on this graph finds a matching containing only slightly
more than 50% of the vertices.

(a) Karp–Sipser

(b) Optimal

Figure 2: An example on which the Karp–Sipser algorithm performs suboptimally.

This suggests the need for a modified version of the Karp–Sipser algorithm
that is given the stochastic block model parameters, and takes into account
the label classes of the vertices. We propose one such algorithm here:

Algorithm 2 Label-Aware Karp–Sipser

1:$M\leftarrow\emptyset$

2:$V\leftarrow V(G)$

3:while $E(G\cap V)\neq\emptyset$ do

4: if exists $v\in V$ of degree 1 – that is, such that exactly one $u\in V$
has $(uv)\in E(G)$ then

5: Choose such a $v$ uniformly at random over all degree 1 vertices

6: $M\leftarrow M\cup\\{(uv)\\}$

7: $V\leftarrow V\setminus\\{u,v\\}$

8: else

9: $\text{Badness}(i)\leftarrow\sum_{j}\theta_{j}\delta_{ij}$ for each class
$i$

10: $i,j\leftarrow\min_{i,j\text{ such that }\exists u\in S_{i},v\in
S_{j},(uv)\in E(G\cap V)}\text{Badness}(i)+\text{Badness}(j)$

11: Choose an edge $(uv)$ uniformly randomly over all $u\in S_{i}\cap V$,
$v\in S_{j}\cap V$, $(uv)\in E(G)$

12: $M\leftarrow M\cup\\{(uv)\\}$

13: $V\leftarrow V\setminus\\{u,v\\}$

14:Return $M$

Among all edge types that exist in the current graph, when this algorithm has
to make a random choice, it chooses from the edge type that we estimate will
create the fewest degree-1 vertices on this step. This algorithm performed
well in our experimental simulations for a range of block model parameters; it
remains open whether asymptotically, it performs near-optimally. Part of the
reason for the difficulty of analysis lies in the fact that we no longer
expect a perfect matching to be possible in Phase 2 – the following section
illustrates this with a simple example.

### 2.7. Bipartite Erdős–Rényi case

The bipartite graph $G(n,n,c/n)$ with equal part sizes and i.i.d. edges
corresponds to an equitable stochastic block model: each vertex on the left
and each vertex on the right has $c$ expected neighbours. So, with high
probability, the Karp–Sipser algorithm performs optimally and returns a
matching the same size as that of $G(2n,{c}/{2n})$. However, the asymmetric
case $G(kn,n,c/n)$ where $k\neq 1$ is not equitable, because left vertices
have $c$ expected neighbours while right vertices have $kc$ of them. It is
this case that we analyze in this section. Note that, as before, the algorithm
is guaranteed to be optimal for Phase 1; we need to show that it’s also near
optimal for Phase 2. However, now even the optimal algorithm on Phase 2 is not
guaranteed to find a near-perfect matching. Consider a graph with very unequal
part sizes, and very high $c$; for example, $G(n,10n,{1000}/{n})$. This graph
is dense enough that we expect at least $5n$ vertices to remain on the right
after Phase 1, however we know that the matching number of this graph is at
most $n$ – so, we can’t actually expect Phase 2 to find a near-perfect
matching. Thus, this is an example where the typical analytical framework does
not apply [10, 1]. However, the usual Karp–Sipser algorithm does behave
optimally in this case, and there exists a simple proof. We sketch the
argument.

######  Lemma 2.16.

Let $F_{l}$, $F_{r}$ and $E$ denote the number of non-isolated unmatched
vertices on the left, non-isolated unmatched vertices on the right, and edges
in the graph at the start of Phase 2. With high probability the Karp–Sipser
algorithm finds a matching of size $\min(F_{l},F_{r})-o(n)$ on this graph. As
a consequence, the asymptotic behavior of the matching numbers bipartite
Erdős–Rényi graphs can be determined from solutions to the ODEs described in
Section 2.3.

###### Proof.

Assume without loss of generality that $F_{l}<KF_{r}$ for some $K>0$ (if
$F_{l}=F_{r}+o(n)$, we know the algorithm performs optimally by our equitable
case analysis). First, we argue that with probability going to 1 in $n$, over
the course of Phase 2 the number of non-isolated unmatched vertices on the
right is always higher than the number on the left. To show this, note that at
a given step of the algorithm, the action with the highest expected loss on
the right compared to the left is removing a degree-1 vertex on the right.
This removes 1 vertex on the left and 1 on the right, but creates
$\delta_{L}\theta_{R}$ vertices of degree 1 on the right that might later be
lost. Clearly, the expected loss would be bigger if instead of reducing those
vertices to degree 1, we just isolated them immediately, so the right size can
overall be decreasing at a rate of at most $\delta_{L}\theta_{R}$ faster than
the left side. But now, note that whenever almost all vertices are of degree 2
and there are $K$ times as many vertices on the right, $\delta_{L}$ can be at
most $K$ times as large as $\delta_{R}$; since we know
$\delta_{R}\theta_{R}<1$, this means $\delta_{L}\theta_{R}<K$. Continuing an
argument along these lines by bounding with an ODE would allow us to show that
with probability going to 1, the right side can never get meaningfully smaller
than the left side.

From that point, we simply note that
$\delta_{R}\theta_{L}\leq\delta_{L}\theta_{L}<1$, so the rate of creation of
degree 1 vertices on the left is always less than 1, meaning that with high
probability there are never more than $o(n)$ degree 1 vertices on the left.
That in turn means that with high probability we do not isolate more than
$o(n)$ degree 1 vertices on the left; so, we find a matching of size
$F_{l}-o(n)$. ∎

The first phase of the algorithm is optimal, and then once the second phase is
reached the matching number is clearly bounded by $\min(F_{l},F_{r})$, so this
implies that the Karp–Sipser algorithm is near-optimal on $G(kn,n,c/n)$. This
analysis works because, even though we the Karp–Sipser core does not admit a
perfect matching, we have an upper bound on its true matching number that we
can show is nearly achieved by the algorithm. This suggests a natural approach
to analyzing Label-Aware Karp–Sipser in other block models would be to try to
find similar bounds on the matching number of the core. (A simple case we note
as an open direction is the bipartite setting where there is only one class on
the left – i.e., parameters where the probability matrix graph is “star
shaped”. On such graphs, Label-Aware Karp–Sipser simplifies to “prefer edges
to the available right class with minimum average degree”.) For now, however,
we move on to analyze a more restrictive type of matching algorithm.

## 3\. Analysis of Online Matching Heuristics

In this section, we consider the problem of online matching in bipartite
stochastic block models. In the situation we’re concerned with, the left and
right parts each have $q$ classes. We assume that vertices are assigned
classes uniformly and independently at random, with classes of the right
vertices known to the algorithm ahead of time, and vertices on the left (along
with all the edges incident to them) arriving one-at-a-time. Uniformity of the
class distribution is roughly without loss of generality; variations could be
approximated by further subdividing the classes.

We propose four different heuristic algorithms for this problem, presented in
increasing order of complexity. The first, called GREEDY, simply chooses an
available edge uniformly at random at each step. We show GREEDY is optimal in
the equitable case. The second, DEGREEDY, prefers matching to vertex classes
with low expected degree. The third, SHORTSIGHTED, maximizes the probability
of being able to find a match on the subsequent step. Finally, BRUTE-FORCE
finds the optimal online matching strategy by dynamic programming - at each
step, it prefers the class which maximizes the expected size of the matching
of the remaining graph. While BRUTE-FORCE is optimal, it’s runtime is
$\Theta(n^{q+1})$ while the first three algorithms require only constant time
for each match. Unfortunately, we show that each of the others is
asymptotically sub-optimal in some instances.

We identify for each of these algorithms a family of instances on which it
outperforms the previous algorithm, demonstrating in particular that only
BRUTE-FORCE is optimal in general. We use the following notation:

  * $\bullet$

$R^{(t)}$: set of remaining (i.e., unmatched) right vertices at time $t$

  * $\bullet$

$R_{i}^{(t)}$: set of remaining right vertices of class $i$ at time $t$,
$i=1,2\ldots q$

  * $\bullet$

$\text{deg}(\cdot)$: expected degree of a vertex in given class

  * $\bullet$

$c(\cdot)$: class of a given vertex

  * $\bullet$

$v^{(t)}$: the left vertex revealed at time $t$

  * $\bullet$

$A^{(t)}=\\{w\in R^{(t)}|(v^{(t)},w)\in E\\}$: available right vertices at
time $t$

  * $\bullet$

$C^{(t)}=\\{l\in[q]|A^{(t)}\cap R_{l}^{(t)}\neq\emptyset\\}$: available right
classes at time $t$

Before considering these algorithms, we recall the simpler setting of
$G(n,n,c/n)$. First note that any online algorithm that chooses not to match a
left vertex when it is adjacent to at least one available right vertex is sub-
optimal. Since, in this setting, all right vertices are indistinguishable, any
online algorithm that always matches when possible is optimal. This gives the
following:

######  Fact 3.1 (Mastin and Jaillet [16]).

In the online setting, the expected size of a matching in $G(n,n,c/n)$
produced by an optimal online algorithm is given by

$\left(1-\frac{\ln(2-e^{-c})}{c}\right)n.$

The stochastic block model setting allows for more nuance; designing optimal
algorithms is nontrivial in general.

### 3.1. GREEDY

First, consider the simplest possible matching heuristic. For each left vertex
that arrives, GREEDY chooses uniformly at random one of the available edges
adjacent to that vertex to add to the matching. While GREEDY is sub-optimal in
general, we can show that it returns an asymptotically optimal matching in any
equitable block model.

Algorithm 3 GREEDY

1:$M\leftarrow\emptyset$

2:for $t$ in $\\{1,2\ldots n\\}$ do $\triangleright$ vertex $v^{(t)}$ revealed

3: if $|A^{(t)}|>0$ then

4: Choose an element uniformly at random from $A^{(t)}$, denoted by $u$

5: $M\leftarrow M\cup\\{(u,v)\\}$

6:Return $M$

######  Lemma 3.2.

In the equitable case, i.e., when all of the vertices have the same average
degree, GREEDY returns an expected matching size equal to that in the
bipartite Erdős-Rényi case ($G(n,n,c/n)$) with
$c=\frac{1}{n}\sum_{j}c_{ij}|R_{j}|=\frac{1}{q}\sum_{i}c_{ij}$ .

###### Proof.

Let $X_{j}^{(t)}$ denote the number of unmatched vertices of class $R_{j}$ at
time $t$. We have that $X_{j}^{(0)}=|R_{j}|$ and

$\mathbb{P}\left(X_{j}^{(t+1)}=x_{j}-1|X_{j}^{(t)}=x_{j}\right)=\sum_{i=1}^{q}\frac{1}{k}\left(1-\prod_{l=1}^{q}(1-p_{il})^{X_{l}^{(t)}}\right)\frac{p_{ij}x_{j}}{\sum_{l=1}^{q}p_{il}X_{l}^{(t)}},$

where we approximate the probability of choosing a vertex of $R_{j}$ as
$\frac{p_{ij}x_{j}}{\sum_{l=1}^{q}p_{il}x_{l}}$ given that there is at least
one available edge. Therefore, if we let $u_{j}$ denote the evolution of the
number of unmatched vertices of $R_{j}$ divided by $|R_{j}|n$, we have the
following system of differential equations (from Wormald’s Theorem) describing
the evolution of unmatched vertices in each class:

$u_{j}^{\prime}=-\frac{1}{|R_{j}|}\sum_{i=1}^{q}\frac{1}{q}\left(1-e^{-\sum_{l=1}^{q}c_{il}|R_{l}|u_{l}}\right)\frac{p_{ij}|R_{j}|u_{j}}{\sum_{l=1}^{q}p_{il}|R_{l}|u_{l}}\qquad
j\in\\{1,2,\ldots q\\}.$ (1)

Note that $u_{j}(0)=\frac{1}{n}$ for all $j$, i.e.,the $u_{j}$’s start out
equal. Assume $u_{j}(t)=u(t)$ for some function $u$, for all $j$. Then we have

$u^{\prime}=-\sum_{i=1}^{q}\frac{1}{q}\left(1-e^{-\sum_{l=1}^{q}c_{il}|R_{l}|u}\right)\frac{p_{ij}}{\sum_{l=1}^{q}p_{il}|R_{l}|}=-\sum_{i=1}^{q}\frac{1}{q}\left(1-e^{-ncu}\right)\frac{c_{ij}}{nc}=-\frac{1}{n}(1-e^{-ncu}).$
(2)

Recall that the evolution of the fraction of unmatched vertices $x$ in the
bipartite Erdős-Rényi case is the solution to by $x^{\prime}=e^{-cx}-1$. Note
that $u=\frac{x}{n}$ is a solution to (2) (so $u_{j}=u$ is a solution to (1)),
therefore the total number of unmatched vertices at time $t$ is

$\sum_{j=1}^{n}|R_{j}|n\cdot u(t)=n^{2}u(t)=nx(t),$

as desired. ∎

We also note that this is tight; i.e., that no algorithm can do asymptotically
better than GREEDY on an equitable block model. The justification for this
comes from the following fact:

######  Lemma 3.3.

In an equitable stochastic block model, if there are a total of $|R^{(t)}|$
unmatched vertices on the right, the probability of matching on the next step
is maximized when those $|R^{(t)}|$ vertices are equally distributed among all
classes (that is, each right type $r$ has $|R_{r}^{(t)}|=\frac{|R^{(t)}|}{q}$
unmatched vertices).

###### Proof.

Let $\rho_{r}=\frac{|R_{r}^{(t)}|}{|R^{(t)}|}$ denote the fraction of
unmatched right vertices belonging to type $r$. The probability of there being
an available edge in the next step of the algorithm is (as $n\to\infty$)

$\frac{1}{q}\sum_{l}e^{-\sum_{r}c_{lr}\rho_{r}}.$

By AM-GM inequality, this is at most

$\left(\prod_{l}e^{-\sum_{r}c_{lr}\rho_{r}}\right)^{1/q}=e^{-\sum_{l}\frac{1}{q}\sum_{r}c_{lr}\rho_{r}}=e^{-\sum_{r}\frac{1}{q}\left(\sum_{l}c_{lr}\right)\rho_{r}}=e^{-c},$

which is precisely the value obtained by setting all $\rho_{r}=\frac{1}{q}$ ∎

From this fact, we see that no algorithm can do asymptotically better than
GREEDY.

######  Theorem 3.4.

The optimal competitive ratio for any online algorithm in an equitable
stochastic block model is

$\frac{c-\ln(2-e^{-c})}{\left(2c-x+ce^{-x}+xce^{-x}\right)},$

where $x$ is the smallest solution of $x=ce^{-ce^{-x}}$.

###### Proof.

First, note that this value is precisely what we’ve shown for the competitive
ratio of GREEDY; this can be found by dividing the asymptotic matching size we
proved in that case by the offline matching size we proved in Theorem 2.8.
Therefore, it is left to establish that no algorithm can do better than
GREEDY. We proceed by contradiction - assume there is a better algorithm, and
consider the expected values of $\rho_{i}$ as in Lemma 3.3 in this algorithm.
If the $\rho_{i}$’s stay within $o(1)$ of equal over all time, then the
algorithm looks asymptotically identical to GREEDY. If at some point they
become unequal, then at that time the algorithm must fall behind GREEDY and
never catch up, by Lemma 3.3. ∎

Note that this value is exactly the same as the competitive ratio lower bound
conjectured by Mastin and Jaillet to be tight for Erdős–Rényi graphs; as a
special case, we have shown that conjecture [16].

Throughout the rest of the paper, we examine non-equitable block models,
providing specific instances where one algorithm beats another. Our pictorial
notation includes nodes, which represent classes, and edges with a number $c$,
which represents an edge probability between the corresponding classes of
$\frac{c}{n}$. The absence of an edge represents $0$ probability of edges
between classes.

### 3.2. DEGREEDY

GREEDY does not perform optimally in some cases. Consider the following block
model with one left class and two right classes:

$L_{0}$$R_{0}$$R_{1}$$100$$1$ Figure 3: DEGREEDY beats GREEDY. $|L_{0}|=n$,
$|R_{0}|=|R_{1}|=\frac{n}{2}$

In such a scenario, it seems sensible to match $R_{1}$ vertices as they are
available, because it is much less likely they will be available again as
opposed to $R_{0}$ vertices (due to the average degree of $R_{1}$ vertices
being lower than that of $R_{0}$ vertices). However, GREEDY will naturally
miss out on available $R_{1}$ vertices as simply choosing available edges at
random heavily favors $R_{0}$ (the edge probability is $100$ times higher).
This leads us to consider the following algorithm: DEGREEDY, which prioritizes
matching right vertices with the lowest average degrees. We introduce the
algorithm below – DEGREEDY and all following algorithms choose which class to
match to and then randomly choose an available edge from that class at each
step.

At each step, DEGREEDY identifies the available class (i.e., a right class
with at least one available edge) with the lowest average degree - if there is
a tie, choose at random one of the lowest-average-degree classes. It then
uniformly chooses an available edge at random from this class.

Algorithm 4 DEGREEDY

1:$M\leftarrow\emptyset$

2:for $t$ in $\\{1,2\ldots n\\}$ do $\triangleright$ vertex $v^{(t)}$ revealed

3: if $|A^{(t)}|>0$ then

4: $C=\underset{j\in C^{(t)}}{\mathrm{argmin}}$ $\text{deg}(R_{j})$

5: Choose an element uniformly at random from $C$, denoted by $c$.

6: Choose a vertex uniformly at random from $R_{c}^{(t)}$, denoted by $u$

7: $M\leftarrow M\cup\\{(u,v)\\}$

8:Return $M$

While DEGREEDY often outperforms GREEDY, it is prone to over-correct when
there is a very slight difference in average degree between right classes.
Consider the following block model:

$L_{0}$$L_{1}$$R_{0}$$R_{1}$$100$$99$$200$ Figure 4: SHORTSIGHTED beats
DEGREEDY. All classes of size $\frac{n}{2}$

In this model, DEGREEDY will always match to $R_{0}$ while it is available.
Simply matching $L_{0}$ vertices to $R_{0}$ vertices and $L_{1}$ vertices to
$R_{1}$ vertices gives an expected matching size of

$\frac{n}{2}\left(1-\frac{\log(2-e^{-50})}{50}+1-\frac{\log(2-e^{-100})}{100}\right)\approx.9896n.$

However, DEGREEDY will match $L_{1}$ vertices to an $R_{0}$ vertex if one is
available - for each occurrence of this, we are “blocking off” an $L_{0}$
vertex, and reducing the size of our potential matching by $1$. The number of
times an $L_{1}$ vertex arrives and has an available edge to $R_{0}$ is much
greater than $.02n$, and therefore DEGREEDY performs worse than simply always
matching within class. We would like a heuristic that somewhat prefers
vertices of low expected degree, but not to such an extreme level.

### 3.3. SHORTSIGHTED

The idea of SHORTSIGHTED is to, at each step, minimize the probability of
being unable to match the next vertex (i.e., the probability that the next
left vertex to arrive has no available edges). Let $u_{i}^{(t)}$ denote the
number of unmatched vertices of $R_{i}$ at time $t$. The class(es) we choose
to take an edge from at time $t$ is given by

$S^{(t)}=\underset{l\in
C^{(t)}}{\mathrm{argmin}}\sum_{i=1}^{q}\frac{1}{q}\prod_{j=1}^{q}\left(1-p_{ij}\right)^{u_{j}^{(t)}-\mathbbm{1}\\{l=j\\}},$

where the expression in the $\mathrm{argmin}$ is the probability that the next
vertex has no available edges.

Algorithm 5 SHORTSIGHTED

1:$M\leftarrow\emptyset$

2:$u_{i}\leftarrow|R_{i}|,i\in[q]$

3:for $t$ in $\\{1,2\ldots n\\}$ do $\triangleright$ vertex $v^{(t)}$ revealed

4: if $|A^{(t)}|>0$ then

5: Compute $S^{(t)}$ per the formula above, using the current values of $u$

6: Choose an element uniformly at random from $S^{(t)}$, denoted by $c$

7: Choose a vertex uniformly at random from $R_{c}^{(t)}$, denoted by $w$

8: $M\leftarrow M\cup\\{(w,v)\\}$

9: $u_{c}\leftarrow u_{c}-1$

10:Return $M$

In Appendix C, we provide formal analysis of the behaviour of this algorithm
in a broad range of settings. One might hope that looking a single step into
the future is sufficient to determine the optimal class to match to, and so
SHORTSIGHTED is an asymptotically optimal approach. However, this turns out
not to be the case.

$L_{0}$$L_{1}$$R_{0}$$R_{1}$$5$$1$$1$ Figure 5: BRUTE-FORCE beats
SHORTSIGHTED. All classes of size $\frac{n}{2}$

In the above model, SHORTSIGHTED prefers class $0$ when the number of
unmatched vertices of class $R_{0}$ is at least $\frac{2\ln 2}{5}n$. Carrying
out the analysis as described in Appendix C, we obtain that the expected size
of the matching is $\approx 0.574946n$. To show this is suboptimal, consider
the following algorithm: prefer class $R_{0}$ until $.88n$ vertices have
arrived, then thereafter prefer $R_{1}$. With essentially the same
differential equation analysis as above, we find that the expected size of the
matching is $\approx 0.575597n$. This algorithm out-performs SHORTSIGHTED by a
linear factor in $n$ (albeit small, $\approx.0006n$), implying that
SHORTSIGHTED is asymptotically sub-optimal.

### 3.4. BRUTE-FORCE

Note that it is not difficult to describe an optimal algorithm. BRUTE-FORCE
precomputes, for every possible state of the algorithm (i.e., number of left
vertices remaining and number of right vertices remaining in each class), the
maximum expected matching size any strategy achieves from that state, and then
always makes decisions to maximize this value. This gives the optimal expected
matching size by definition. It is possible to do this precomputation in time
$\mathcal{O}(n^{q+1})$ by dynamic programming.

Algorithm 6 BRUTE-FORCE

1:$D\leftarrow$ empty table

2:$D[0][i_{1},\dots,i_{q}]\leftarrow 0$ for all $i_{1},\dots,i_{q}\in[n]$

3:for $l\in[n]$ do

4: for $i_{1},\dots,i_{q}\in[n]$ do

5: $p_{j}\leftarrow\Pr\Big{[}\text{random left vertex matches class $j$,
$\not\exists k$: $D[l-1][i_{1},\dots,i_{k}-1,\dots
i_{q}]>D[l-1][i_{1},\dots,i_{j}-1,\dots i_{q}]$}\Big{]}$

6:$\triangleright$ Can compute these probabilities explicitly and efficiently

7: $D[l][i_{1},\dots,i_{q}]\leftarrow\Pr[\text{no
matches}]\Big{(}D[l-1][i_{1},\dots
i_{q}]\Big{)}+\sum_{j\in[q]}p_{j}\Big{(}D[l-1][i_{1},\dots,i_{j}-1,\dots
i_{q}]+1\Big{)}$

8:

9:$i_{j}\leftarrow\text{number of right vertices in class $j$}$, $l\leftarrow
n$

10:for $t\in[n]$, as vertices arrive do $\triangleright$ vertex $v^{(t)}$
revealed

11: if available match then

12: Match to available class $j$ that maximizes
$D[l-1][i_{1},\dots,i_{j}-1,\dots i_{q}]$

13: $i_{j}\leftarrow i_{j}-1$

14: $l\leftarrow l-1$

We conjecture based on simulations of BRUTE-FORCE that there should exist a
simple, efficient algorithm that is also asymptotically optimal, however we
have not found such a description. Plots of simulation of BRUTE-FORCE on the
model in Figure 5 are included below.

Figure 6: Behavior of SHORTSIGHTED and BRUTE-FORCE for plot in Figure 5,
$n=300$. Yellow indicates SHORTSIGHTED’s preference for class $0$, green for
class $1$. The red curve is the average of the SHORTSIGHTED’s path on $10,000$
instances of the model. Magenta shows BRUTE-FORCE’s path.

Figure 7: Preferences of BRUTE-FORCE for the model in Figure 5 varying over
time. Yellow represents a preference for class $0$, green for class $1$. The
number of vertices remaining for each plot are $200,150,100,50,20,$ and $2$
from left to right. Portions of the plot that are uncolored represent
infeasible states at the given time.

## 4\. Conclusion

In Erdős–Rényi graphs, the structure looks uniform everywhere, and the
performance of simple linear-time matching heuristics, both in the offline and
online settings, is well understood. In this paper, we explored what happens
when we reduce those uniformity assumptions, requiring edges to be
indistinguishable on a local level but allowing large-scale global density
differences (a model motivated by more realistic examples of graphs arising in
nature). We showed that, so long as no class of vertices is expected to have
noticeably different degrees from the others, these global density differences
have no asymptotic effect on the performances of either those simple online or
offline algorithms. When some vertices are allowed to be biased towards higher
degree than others, however, we find that the situation becomes much more
complex. There is ample ground for further work on this subject. In the
offline setting, we would be interested to see classes of graphs on which the
Label-Aware Karp–Sipser algorithm finds near optimal matchings even though
oblivious Karp–Sipser does not. In the online setting, it would be valuable
either to find a more efficient means of calculating the optimal that BRUTE-
FORCE finds, or else to prove that SHORTSIGHTED (or some other reasonable
alternative) always achieves a very similar competitive ratio.

## 5\. Acknowledgements

This project was conducted as a part of the 2023 Summer Program for
Undergraduate Research at MIT. We’re grateful to all the organizers of the
program for facilitating it, to Professor Elchanan Mossel for suggesting the
topic, and to Professor David Jerison in particular for his helpful feedback.

## References

  * [1] Jonathan Aronson, Alan M. Frieze, and Boris G. Pittel.  Maximum matchings in sparse random graphs: Karp-sipser revisited.  Random Struct. Algorithms, 12:111–177, 1998.
  * [2] Tom Bohman and Alan M. Frieze.  Karp–sipser on random graphs with a fixed degree sequence.  Combinatorics, Probability and Computing, 20:721 – 741, 2011.
  * [3] Thomas Budzinski, Alice Contat, and Nicolas Curien.  The critical Karp–Sipser core of random graphs, 2022.
  * [4] Byron Chin and Allan Sly.  Optimal reconstruction of general sparse stochastic block models, 2021.
  * [5] R.W.R. Darling and J.R. Norris.  Differential equation approximations for Markov chains.  Probability Surveys, 5(none):37 – 79, 2008.
  * [6] Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan.  Online stochastic matching: Beating 1-1/e.  CoRR, abs/0905.4100, 2009.
  * [7] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  Social Networks, 5(2):109–137, 1983.
  * [8] Alexander E. Holroyd and James B. Martin.  Galton–watson games.  Random Structures & Algorithms, 59(4):495–521, 2021.
  * [9] Zhiyi Huang, Xinkai Shu, and Shuyi Yan.  The power of multiple choices in online stochastic matching, 2022.
  * [10] R. M. Karp and M. Sipser.  Maximum matching in sparse random graphs.  In 22nd Annual Symposium on Foundations of Computer Science (SFCS 1981), pages 364–375, 1981.
  * [11] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani.  An optimal algorithm for on-line bipartite matching.  In Symposium on the Theory of Computing, 1990.
  * [12] Kamer Kaya, Johannes Langguth, Ioannis Panagiotas, and Bora Uçar.  Karp-Sipser based kernels for bipartite graph matching, pages 134–145.  12 2020.
  * [13] Thomas G. Kurtz.  Solutions of ordinary differential equations as limits of pure jump markov processes.  Journal of Applied Probability, 7(1):49–58, 1970.
  * [14] Johannes Langguth, Ioannis Panagiotas, and Bora Uçar.  Shared-memory implementation of the karp-sipser kernelization process.  In 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 71–80, 2021.
  * [15] Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi.  Online stochastic matching: Online actions based on offline statistics, 2011.
  * [16] Andrew Mastin and Patrick Jaillet.  Greedy online bipartite matching on random graphs.  CoRR, abs/1307.2536, 2013.
  * [17] Elchanan Mossel, Joe Neeman, and Allan Sly.  A proof of the block model threshold conjecture.  Combinatorica, 38(3):665–708, 2018.
  * [18] Flore Sentenac, Nathan Noiry, Matthieu Lerasle, Laurent Ménard, and Vianney Perchet.  Online matching in geometric random graphs, 2023.
  * [19] Nahuel Soprano-Loto, Matthieu Jonckheere, and Pascal Moyal.  Online matching for the multiclass stochastic block model, 2023.
  * [20] Alfred Tarski.  A lattice-theoretical fixpoint theorem and its applications.  Pacific Journal of Mathematics, 5(2):285 – 309, 1955.
  * [21] Nicholas C. Wormald.  Differential Equations for Random Processes and Random Graphs.  The Annals of Applied Probability, 5(4):1217 – 1235, 1995.

##  Appendix A Justifications of Transition Probabilities

### A.1. Blocked Configuration Model

######  Lemma A.1.

Conditional on the output being simple (no multiple edges or self-loops), this
corresponding blocked configuration model gives the same distribution as the
original stochastic block model.

###### Proof.

If the output is simple, then for each pair of classes the size $m_{ij}$ of
the edge set is distributed the same as the stochastic block model, and all
edge sets of that size are equally likely (since there are exactly $m_{ij}!$
possible ordered lists of edges that produce that edge set, and all of those
are equally likely). As in the stochastic block model, the values of $m_{ij}$
and the distribution of edges within those are independent for all pairs $i$
and $j$. So, this is the same distribution. ∎

######  Lemma A.2.

If all label classes are of size $\Theta(n)$ and each pair of labels has
$\mathcal{O}(n)$ edges between them, then with probability bounded away from
zero the blocked configuration model produces a simple graph.

###### Proof.

It suffices to show that with probability bounded away from zero the graph
between any given pair of labels is simple, because the pairs are independent
and there are only constantly many of them. Denote the set of vertices with
label $i$ as $S_{i}$. Within a given label class $i$, the probability of being
simple is [1],

$\left(1-\frac{1}{|S_{i}|}\right)^{m_{ii}}\cdot\prod_{j=0}^{m_{ii}-1}\left(1-\frac{j}{\binom{|S_{i}|}{2}}\right)\geq
e^{-\frac{m_{ii}}{2|S_{i}|}-\frac{m_{ii}^{2}}{4|S_{i}|^{2}}}=\Theta(1).$

Between two different label classes $i$ and $j$, the probability of being
simple is

$\prod_{k=0}^{m_{ij}-1}\left(1-\frac{k}{|S_{i}|\cdot|S_{j}|}\right)\geq
e^{-\frac{m_{ij}}{|S_{i}||S_{j}|}}=\Theta(1).$

So, the entire multigraph is simple with probability bounded away from 0. ∎

Thus, any result which holds with high probability in the blocked
configuration model also holds with high probability for the stochastic block
model.

### A.2. Proof of Markov Property

In this section we give the proof of Lemma 2.2.

###### Proof.

We proceed by induction. First, note that we start with a blocked
configuration model with the given edge counts – once we discard multigraphs
where the number of thin and fat vertices don’t fit $T_{i}$, $F_{i}$, we will
still be uniform over the remaining multigraphs. Now, suppose that,
conditional on the value of its tuple $Y_{i}$, the distribution of multigraphs
after $i$ steps of the algorithm follows the blocked configuration model
conditioned on number of thin and fat vertices. We would like to show that
after $i+1$ steps, conditional on any fixed $Y_{i+1}$, the distribution still
follows blocked configuration model. To do so, we let $Y_{i+1}$ be arbitrary,
and let $G_{1},G_{2}$ be outputs of the blocked configuration model (that is,
ordered lists of edges for each pair of labels) that correspond to multigraphs
with tuple $Y_{i+1}$ – we will argue that the probability of reaching $G_{1}$
after $i+1$ steps is the same as the probability of reaching $G_{2}$, meaning
that all such multigraphs are equally likely (this is what it means to follow
blocked configuration model distribution). The way to show this is a
straightforward counting argument: enumerate all the ways to reach $G_{1}$ or
$G_{2}$ from a multigraph in the previous step, then appeal to the inductive
hypothesis to argue that the equality of these counts implies equal
probabilities. To lay out this argument explicitly, start with either $G_{1}$
or $G_{2}$ and imagine performing the following ”undoing” process:

  1. i)

First, choose a value for the tuple $Y_{i}$ of the multigraph preceding $G$.
Of course, for some choices of $Y_{i}$ there are no ways to yield $G$ on the
next step (for instance, if $Y_{i}$ has fewer total edges than $Y_{i+1}$,
there is no way to choose a graph with tuple $Y_{i}$ and get a multigraph with
tuple $Y_{i+1}$ after a step of Karp–Sipser) – the goal is just to show that
the number of ways to yield $G_{1}$ is always the same as the number of ways
to yield $G_{2}$.

  2. ii)

Next, choose which two label classes $a$ and $b$ the $i+1$st step of the
algorithm chose an edge between. (Again, it is possible that some of these
choices won’t correspond to any valid predecessor states.)

  3. iii)

When the algorithm chooses an edge for the matching, it removes all edges
adjacent to the endpoints from the multigraph. So, the edge chosen on step
$i+1$ must have been between two vertices that are now degree 0 in $G$. The
number of degree-0 vertices in a given class $j$ is equal to the total number
of vertices in that class minus $F_{j}+T_{j}$, so the number of ways to choose
one degree-0 $a$-vertex and one degree-0 $b$-vertex is the same for either
$G_{1}$ or $G_{2}$. We choose one such pair $(x,y)$ to be the edge chosen in
step $i+1$ of the algorithm.

  4. iv)

Once we fix which $(x,y)$ was chosen, determining the multigraph state prior
to step $i+1$ just entails choosing what neighbour multisets $x$ and $y$ had.
We have the following constraints on what vertices we can choose for these
edges sets:

     * $\bullet$

$Y_{i}$ encodes the number of degree-1 vertices in the preceding graph – if
this number is greater than 0, then the edge chosen by the Karp–Sipser
algorithm must involve such a thin vertex, and so either $x$ or $y$ must have
no additional edges, so we now choose which one.

     * $\bullet$

Because we know $Y_{i}$ and $Y_{i+1}$, we know for each pair of classes
exactly how many edges the $i+1$st step removed between that pair. So, we have
to ensure that the number of edges we add of each type exactly equals these
values.

     * $\bullet$

Similarly, the difference between $Y_{i}$ and $Y_{i+1}$ tells us for each
class $j$ the change in the number of thin and fat vertices in that class. A
valid choice of edge set must, for each class $j$, add an edge to exactly
$-\Delta F_{j}-\Delta T_{j}$ degree-0 vertices of class $j$; the number of
ways to choose those vertices is $\binom{\text{initial size of class
$j$}-(F_{j})_{i}-(T_{j})_{i}}{-\Delta F_{j}-\Delta T_{j}}$. Then, we have to
add edges to exactly $-\Delta F_{j}$ degree-1 vertices of class $j$; there are
$\binom{(T_{j})_{i}-\Delta F_{j}-\Delta T_{j}}{-\Delta F_{j}}$ ways to choose
those. Any remaining edges must be distributed over vertices of degree at
least 2.

  5. v)

Finally, once we fix which edges to add, we can choose any indices within the
ordered edge-lists to add them.

The crucial point of this is that the number of options available as we
progress from one step to the next in the procedure is always the same
regardless of whether we’re considering $G_{1}$ or $G_{2}$ – the restrictions
on edge sets depend only on the number of edges between each pair of classes,
and the number of thin/fat vertices in each class, all of which is the same
for both $G_{1}$ and $G_{2}$ because we’re conditioning on them having the
same tuple. So, we find that for any given predecessor tuple $Y_{i}$, the
number of ways to choose a multigraph of tuple $Y_{i}$, remove a valid edge,
and reach $G_{1}$ is exactly the same as the number of ways to choose a
multigraph of tuple $Y_{i}$, remove a valid edge, and reach $G_{2}$. By the
inductive hypothesis, all ordered edge-lists with the same $Y$-tuple are
equally likely on step $i$. The number of valid edges to remove from an
ordered edge-list just depends on how many edges there are and whether there
are thin vertices, both of which are captured in the tuple. So, all ways to
choose a multigraph of tuple $Y_{i}$ and remove an edge are equally likely to
have occurred on step $i+1$ of the algorithm, meaning that the resulting
multigraph is equally likely to be $G_{1}$ or $G_{2}$. ∎

### A.3. Degree Distribution

Here we prove Lemma 2.3.

###### Proof.

First of all, we are conditioning on exactly how many degree 1 vertices there
are in $G_{n}$, and so we know that the probability of a random half-edge
being incident to one of them is exactly the number of degree-1 vertices
divided by the total number of half-edges. Among the remaining vertices, note
that in our model all half-edges are treated indistinguishably regardless of
the label of the other half. So, the question of the degree of the vertex
attached to a random half-edge, conditional on that vertex having degree at
least 2, is equivalent to asking “Suppose I throw
${\left((\sum_{l}E_{il})-T_{i}\right)}/{F_{i}}$ balls (the total number of
half-edges associated to the fat vertices) into $F_{i}$ bins. If I condition
on all bins having at least 2 balls, how many balls are in the bin the first
ball landed in?”. Note that the bin the first ball ends up in is a uniform
random bin independent of the other balls, so the probability that it ends up
with $k$ balls in it converges to the probability that a randomly selected bin
has $k-1$ balls. We claim that this distribution converges to the above
truncated Poisson distribution; a proof of this is given by Aronson, Frieze,
and Pittel by showing that a sum of truncated Poissons is highly concentrated
around its mean, which allows us to ignore the conditioning on all the other
bins [1]. ∎

######  Remark A.3.

Another point we note here is that the probability that a given vertex is
attached to any self-loops or multiple edges is negligible, so long as the
average degrees in each class remain bounded by a constant. In this case, we
know that with high probability the maximum degree in the graph is
$\mathcal{O}(\frac{\log n}{\log\log n})$. If a vertex $v$ has
$\mathcal{O}(\frac{\log n}{\log\log n})$ edges to class $j$, and class $j$ has
at least $n^{0.01}$ vertices (otherwise we can safely ignore all effects of
class $j$), then the probability that two of those edges are to the same
vertex tends to 0 in $n$. Since average degree will indeed stay bounded by a
constant, this justifies not worrying about multiple edges.

##  Appendix B Games on Multitype Branching Processes

This appendix concerns games played on multitype branching processes. The
setting and results are the same as those considered by Holroyd and Martin
with regards to the normal game on GW trees, but extended slightly to cover
the multitype case [8]. At the end of this section, we will explain the
connection to our claim about criticality of the Karp–Sipser core.

### B.1. Definitions

######  Definition B.1.

A game on a (possibly infinite) game tree is played as follows: Both players
know the full structure of the tree. On a player’s turn, they choose one child
of the current node to walk down to, and the next player starts at that node.
A player loses when there are no valid moves (i.e., when they start their turn
on a leaf node). We denote by $\mathcal{N}_{d}$ the set of states from which
an optimal player can force a win within $d$ turns of the game,
$\mathcal{P}_{d}$ the set of states from which a player is guaranteed to lose
within $d$ steps if their opponent plays optimally, and $\mathcal{D}_{d}$ to
be the set of states in neither $\mathcal{N}_{d}$ nor $\mathcal{P}_{d}$ (i.e.,
the set of states in which either player can force the game to continue for
$d$ steps if the other is unwilling to lose).

We will consider games played on a random game tree drawn from a multitype
branching process. Although for the purposes of the results in the paper we
only need to understand the case where the offspring distributions are
independent Poissons in each type, we will do our proofs here for arbitrary
offspring distributions.

######  Definition B.2.

Consider a multitype branching process with types $1\dots q$, where the
probability of a node of type $i$ having offspring set containing exactly
$o_{j}$ offspring of each type $j$ is $p_{i}(o_{1},\dots,o_{q})$. The
offspring generating function for this process is the polynomial function

$G:[0,1]^{q}\rightarrow[0,1]^{q}$ $\begin{bmatrix}x_{1}\\\ \dots\\\ x_{q}\\\
\end{bmatrix}\mapsto\sum_{o_{1}=0}^{\infty}\dots\sum_{o_{q}=0}^{\infty}\left(\prod_{j}x_{j}^{o_{j}}\cdot\begin{bmatrix}p_{1}(o_{1},\dots,o_{q})\\\
\dots\\\ p_{q}(o_{1},\dots,o_{q})\\\ \end{bmatrix}\right)$

For fixed offspring distributions, we are interested in the values of
$N_{d},P_{d},D_{d}\in[0,1]^{q}$, where the $i$th entry of $N_{d}$ is the
probability that the root of this branching process is an $\mathcal{N}_{d}$
node, given that it is of class $i$ (likewise $P_{d}$ and $D_{d}$ are the
probabilities the root is in $\mathcal{P}_{d}$ or $\mathcal{D}_{d}$,
respectively).

### B.2. Convergence

We can calculate the values for $N_{d}$, $P_{d}$, and $D_{d}$ recursively.
Note the following:

  * $\bullet$

A vertex is in $\mathcal{N}_{d}$ if and only if it has at least one child in
$\mathcal{P}_{d-1}$

  * $\bullet$

A vertex is in $\mathcal{P}_{d}$ if and only if all of its children are in
$\mathcal{N}_{d-1}$

  * $\bullet$

A vertex is in $\mathcal{D}_{d}$ when neither of the above conditions are true
(and, in particular, when $d=0$)

We can consider each of the root’s children to be independent multitype
branching processes, with roots of their given types. This yields the
following recursions for these values in terms of the offspring generating
function:

$N_{d}=\mathbf{1}-G(\mathbf{1}-P_{d-1}),\ P_{d}=G(N_{d-1})\ \text{ and }\
D_{d}=\mathbf{1}-N_{d}-P_{d}.$

Letting $F(x)=\mathbf{1}-G(\mathbf{1}-G(x))$, these recurrences become

$N_{d+2}=F(N_{d})\ \text{ and }\ \mathbf{1}-P_{d+2}=F(\mathbf{1}-P_{d}).$

Note that for any $k$, $N_{2k}=N_{2k+1}$, $P_{2k}=P_{2k+1}$, and
$D_{2k}=D_{2k+1}$; this is because the player starting from the root will make
all the odd moves of the game, so they can force the other player to get stuck
in the first $2k+1$ steps if and only if they can force a them to get stuck in
the first $2k$ steps. So, to understand the behaviour of these values for
large $d$, it suffices to show that the even values of both $N_{d}$ and
$P_{d}$ converge to fixed points. That is, we want to describe the eventual
behavior of $F\circ F\circ\dots\circ F(\mathbf{0})$ and $F\circ
F\circ\dots\circ F(\mathbf{1})$ – if we can show that these converge to fixed
values, $N_{d}$ and $1-P_{d}$ also converge to those values, respectively.
This fact is implied by the following lemma:

######  Lemma B.3.

If a function $F:[0,1]^{q}\rightarrow[0,1]^{q}$ has every output coordinate
continuous and non-decreasing in every input coordinate, then there exists a
minimal fixed point $x$ of $F$; that is, a fixed point of $F$ such that for
all $i$, the $i$th coordinate of $x$ is minimal among all the $i$th
coordinates of fixed points of $F$; iterating $F$ starting from $\mathbf{0}$
will reach this point. Similarly, there exists a maximal fixed point of $F$;
iterating $F$ starting from $\mathbf{1}$ will reach that point.

###### Proof.

This statement is directly implied by Tarski’s fixed point theorem, applied on
the complete lattice obtained by coordinate-wise ordering on $[0,1]^{q}$ (that
is, $x\leq y$ if and only if $x_{i}\leq y_{i}$ for all $i$) [20]. ∎

Thus, we have that $\lim_{d\rightarrow\infty}N_{d}$ is equal to the minimum
fixed point of $F$, $\lim_{d\rightarrow\infty}P_{d}$ is equal to $\mathbf{1}$
minus the maximum fixed point of $F$ and $\lim_{d\rightarrow\infty}D_{d}$ is
equal to the maximum fixed point of $F$ minus the minimum fixed point of $F$.

In particular, the probability of neither player having a winning strategy
within $d$ steps tends to 0 in the limit of $d$ for all root types if and only
if $F$ has exactly one fixed point on $[0,1]^{q}$.

### B.3. Implications for Karp–Sipser core

The connection between this analysis of games and our analysis of the
Karp–Sipser algorithm comes from the following fact:

######  Lemma B.4.

If the root of a tree is in $\mathcal{N}_{d}$ or $\mathcal{P}_{d}$, there
exists a sequence of removals that the Karp–Sipser algorithm can make within
depth $d$ that result in the removal of the root.

###### Proof.

This fact is shown in Karp and Sipser’s original paper [10]; the proof is a
straightforward induction ($\mathcal{P}$ nodes correspond to vertices that can
remove their parent, $\mathcal{N}$ nodes correspond to vertices that can be
removed by one of their children). ∎

So, we find that as long as $D_{d}\rightarrow 0$, the root of the tree is
removed with probability approaching 1; by the above analysis, this occurs
whenever $F$ has only one fixed point. Plugging in the case of the process
where nodes of type $i$ have independently Pois($c_{ij}\bar{S_{j}}$) children
of type $j$ yields the result we use as Lemma 2.15 in the paper.

##  Appendix C Analysis of SHORTSIGHTED with two classes

We restrict our attention to the case where $q=2$, where the classes are
indexed by $0$ and $1$. In this case, $S^{(t)}$ can be computed generally,
facilitating the analysis of SHORTSIGHTED. We consider states of the form
$(i,j,r)$, analogous to $(u_{0}^{(t)},u_{1}^{(t)},n-t)$. The first coordinate
represents the number of unmatched vertices in $R_{0}$, the second is the
number of unmatched vertices in $R_{1}$, and $r$ indicates the number of
vertices left to arrive. The initial state is $(|R_{0}|,|R_{1}|,n)$.

Below we compute for which states $(i,j,r)$ SHORTSIGHTED prefers class $R_{0}$
over $R_{1}$. If either $i$ or $j$ is $0$, there is no choice to be made, so
we consider cases where $i,j>0$. SHORTSIGHTED prefers $R_{0}$ when

$\frac{1}{2}\left(1-p_{0,0}\right)^{i-1}\left(1-p_{0,1}\right)^{j}+\frac{1}{2}\left(1-p_{1,0}\right)^{i-1}\left(1-p_{1,1}\right)^{j}\leq\frac{1}{2}\left(1-p_{0,0}\right)^{i}\left(1-p_{0,1}\right)^{j-1}+\frac{1}{2}\left(1-p_{1,0}\right)^{i}\left(1-p_{1,1}\right)^{j-1}.$

Rearranging, we have

$\left(1-p_{0,0}\right)^{i-1}\left(1-p_{0,1}\right)^{j-1}\left(p_{0,0}-p_{0,1}\right)\leq\left(p_{1,1}-p_{1,0}\right)\left(1-p_{1,0}\right)^{i-1}\left(1-p_{1,1}\right)^{j-1}.$

Now we take the following cases:

  1. i)

$p_{0,0}-p_{0,1}\leq 0$, $p_{1,1}-p_{1,0}\geq 0$: the inequality is always
true, so SHORTSIGHTED prefers class $0$ where $i,j>0$,

  2. ii)

$p_{0,0}-p_{0,1}\geq 0$, $p_{1,1}-p_{1,0}\leq 0$: the inequality is always
false, so SHORTSIGHTED prefers class $1$ where $i,j>0$,

  3. iii)

$p_{0,0}-p_{0,1},p_{1,1}-p_{1,0}>0$: the states where SHORTSIGHTED will prefer
class $0$ are such that

$(i-1)\ln\left(\frac{1-p_{0,0}}{1-p_{1,0}}\right)+(j-1)\ln\left(\frac{1-p_{0,1}}{1-p_{1,1}}\right)\leq\ln\left(\frac{p_{1,1}-p_{1,0}}{p_{0,0}-p_{0,1}}\right),$

  4. iv)

$p_{0,0}-p_{0,1},p_{1,1}-p_{1,0}<0$: the states where SHORTSIGHTED will prefer
class $0$ are such that

$(i-1)\ln\left(\frac{1-p_{0,0}}{1-p_{1,0}}\right)+(j-1)\ln\left(\frac{1-p_{0,1}}{1-p_{1,1}}\right)\geq\ln\left(\frac{p_{1,1}-p_{1,0}}{p_{0,0}-p_{0,1}}\right).$

We define the boundary as the line on the $x-y$ plane that separates states
where class $R_{0}$ is preferred and states where class $R_{1}$ is preferred.
Taking $n\rightarrow\infty$, the boundary is given by

$y=\frac{c_{1,0}-c_{0,0}}{c_{0,1}-c_{1,1}}x+\frac{\ln\left(\frac{c_{0,0}-c_{0,1}}{c_{1,1}-c_{1,0}}\right)}{c_{0,1}-c_{1,1}}n$

In our analysis below, it proves useful to rescale $x$ and $y$ by a factor of
$\frac{1}{n}$. Our new boundary is given by

$y=\frac{c_{1,0}-c_{0,0}}{c_{0,1}-c_{1,1}}x+\frac{\ln\left(\frac{c_{0,0}-c_{0,1}}{c_{1,1}-c_{1,0}}\right)}{c_{0,1}-c_{1,1}}$
(3)

Note that the condition for preferring class $R_{0}$ is given by a linear
inequality and is independent of the number of remaining vertices. This
independence in time is crucial in being able to analyze SHORTSIGHTED in some
cases. We refer to $P_{c}$ the set of $(x,y)$ where class $c$ is preferred.

######  Lemma C.1.

If the boundary does not intersect the rectangle defined by the possible range
of $x$ and $y$ ($x\in[0,|R_{0}|/n],y\in[0,|R_{1}|/n]$) or if the slope of the
boundary is non-positive, then SHORTSIGHTED is of the following form for some
$c$ and $T$ (where $T$ may be $n$): we prefer class $R_{c}$ up until there are
$T$ vertices left to arrive; thereafter we prefer the opposite class,
$R_{1-c}$. In these cases, we can numerically compute the expected size of
matching that SHORTSIGHTED produces by the following process:

  1. i)

Determine which class (i.e., $c$) is preferred at the point
$(|R_{0}|,|R_{1}|)$, the starting state.

  2. ii)

If $c=0$, solve the following system of differential equations with initial
conditions $(a(0),b(0))=\left(\frac{|R_{0}|}{n},\frac{|R_{1}|}{n}\right)$:

$a^{\prime}(t)=-\frac{1}{2}\left(2-e^{-c_{0,0}a(t)}-e^{-c_{1,0}a(t)}\right)$
$b^{\prime}(t)=-\frac{1}{2}\left(e^{-c_{0,0}a(t)}(1-e^{-c_{0,1}b(t)})+e^{-c_{1,0}a(t)}(1-e^{-c_{1,1}b(t)})\right)$

Otherwise, if $c=1$, solve the system below:

$a^{\prime}(t)=-\frac{1}{2}\left(e^{-c_{0,1}b(t)}(1-e^{-c_{0,0}a(t)})+e^{-c_{1,1}b(t)}(1-e^{-c_{1,0}a(t)})\right)$
$b^{\prime}(t)=-\frac{1}{2}\left(2-e^{-c_{0,1}b(t)}-e^{-c_{1,1}b(t)}\right)$

Let $(a(t),b(t))$ be the solution to this system. If $(a(1),b(1))\in P_{c}$,
then the expected size of the matching is simply $n(1-a(1)-b(1))$.
Otherwise, if $(a(1),b(1))\notin P_{c}$, solve for $T$ such that $(a(T),b(T))$
lies on the boundary. Then solve the other system of equations above (i.e.,
solve the system corresponding to $1-c$), with initial conditions at $t=0$
being $(a(T),b(T))$. Denote the solution $(f,g)$. The expected matching size
is given by $n(1-f(1-T)-g(1-T))$.

###### Proof.

If the boundary does not intersect the feasible region for $(x,y)$ (i.e.,
$x\in[0,|R_{0}|/n]$, $y\in[0,|R_{1}|/n]$), then SHORTSIGHTED will simply
prefer one class at all times. Note that any possible ”path” of the algorithm
may only move down and left (as the number of unmatched vertices in each class
can only decreasing over time). Therefore, if the boundary intersects the
feasible region but has negative slope, any possible ”path” can only intersect
the boundary at most once at some time, where before this time the path will
live in $P_{c}$ and after it will live in $P_{1-c}$ for some $c$. In both
cases, the number of unmatched vertices can be represented by a Markov Chain
(or two), and we can use Wormald’s theorem to describe its behavior through
the systems of differential equations given above. We discuss the specifics of
our use of Wormald’s theorem in Appendix D. ∎

The case where the slope of the boundary is positive is more tricky because we
cannot guarantee that the path of the algorithm only crosses the boundary at
most once (though in practice, SHORTSIGHTED seems well-behaved). Nevertheless,
the above lemma covers $2/3$ of the simplex of values of $p_{i,j}$.

##  Appendix D Conditions of Wormald’s Theorem

We on several occasions in this paper claim that particular Markov processes
remain close to a limiting system of differential equations. In this section,
we step through for each of those instances the justification of those claims.
The key tool is a theorem of Wormald, restated in its general form below.
Here, $n$ indexes a family of discrete time random processes, each of which
has “history” sequence $H_{n}\in S_{n}^{+}$. The notation $Y_{t}$ is shorthand
for $y(H_{t})$.

######  Theorem D.1 (Wormald [21]).

Let $a$ be fixed. For $1\leq l\leq a$, let
$y^{(l)}:\bigcup_{n}S_{n}^{+}\rightarrow\mathbb{R}$ and
$f_{l}:\mathbb{R}^{a+1}\rightarrow\mathbb{R}$, such that for some constant $C$
and all $l$, $|y^{(l)}(h_{t})|<Cn$ for all $h_{t}\in S_{n}^{+}$ for all $n$.
Suppose also that for some function $m=m(n)$:

  1. i)

for some functions $w=w(n)$ and $\lambda=\lambda(n)$ with $\lambda^{4}\log
n<w<n^{2/3}/\lambda$ and $\lambda\rightarrow\infty$ as $n\rightarrow\infty$,
for all $l$ and uniformly for all $t<m$,

$\mathbb{P}\left[|Y^{(l)}_{t+1}-Y^{(l)}_{t}|>\frac{\sqrt{w}}{\lambda^{2}\sqrt{\log
n}}\Big{|}H_{t}\right]=o(n^{-3});$

  2. ii)

for all $l$ and uniformly over all $t<m$, we always have

$\mathbb{E}(Y^{(l)}_{t+1}-Y^{(l)}_{t}|H_{t})=f_{l}(t/n,Y_{t}^{(1)}/n,\dots,Y^{(a)}_{t}/n)+o(1);$

  3. iii)

for each $l$, the function $f_{l}$ is continuous and satisfies a Lipschitz
condition on $D$, where $D$ is some bounded connected open set containing the
intersection of $\\{(t,z^{(1)},\dots,z^{(a)}):t\geq 0\\}$ with some
neighbourhood of
$\\{(0,z^{(1)},\dots,z^{(a)}):\mathbb{P}(Y^{(l)}_{0}=z^{(l)}n,1\leq l\leq
a)\neq 0$ for some $n\\}$.

Then,

  1. i)

For $(0,\hat{z}^{(1)},\dots,\hat{z}^{(a)})\in D$, the system of differential
equations

$\frac{dz_{l}}{ds}=f_{l}(s,z_{1},\dots,z_{a}),\hskip 40.0ptl=1,\dots,a,$

has a unique solution in $D$ for $z_{l}:\mathbb{R}\rightarrow\mathbb{R}$
passing through

$z_{l}(0)=\hat{z}^{(l)},\hskip 40.0pt1\leq l\leq a$

and which extends to points arbitrarily close to the boundary of $D$.

  2. ii)

Almost surely,

$Y^{l}_{t}=nz_{l}(t/n)+o(n)$

uniformly for $0\leq t\leq\min\\{\sigma n,m\\}$ and for each $l$, where
$z_{l}(t)$ is the solution in (i) with $\hat{z}^{(l)}=Y^{(l)}_{0}/n$, and
$\sigma=\sigma(n)$ is the supremum of those $s$ to which a solution can be
extended.

### D.1. Phase 1 of the Karp–Sipser algorithm

The first time we make use of this differential equations method is in the
analysis of the first phase of the Karp–Sipser algorithm. We will outline how
to apply Wormald’s theorem in this case. Here, we take $Y$ as we defined it,
$f$ as the derivative we wrote down for the corresponding ODE, and note that
with high probability, $y^{(l)}(h_{t})<100(\max_{ij}c_{ij})n$ for all
sufficiently large $n$ (the $F_{i}$ and $T_{i}$ components of $y^{(l)}(h_{t})$
are clearly bounded by $n$; whp the edge counts are all initially within a
factor of 100 of their expectations, and once they start that way they never
increase). We take the stopping time $m$ to be the first time all of the
$T_{i}$ entries of $Y$ drop below $n^{0.01}$. Now,

  1. i)

Take for instance $w=n^{0.5}$ and $\lambda=\log n$. The probability that any
vertex in the initial graph has degree polynomial in $n$ decays exponentially
in $n$, and it can be observed that the magnitude of a transition is bounded
by twice the maximum degree, so we certainly have the desired condition.

  2. ii)

This convergence of expected transition size of the Markov process to $f$ is
precisely what is guaranteed by the convergence of our degree estimates. Note
that this convergence holds as the total number of thin vertices, fat
vertices, and edges is going to infinity, so taking our stopping time to be
$m$ prevents border cases once these values drop down to constant sizes.

  3. iii)

To show that $f$ is Lipschitz in the neighbourhood of solutions, it suffices
to show that solutions to $z^{\prime}(t)=f(t,z)$ always maintain constant
average degree in each label class. To do so, note that with high probability
the initial average degrees are at most $100(\max_{ij}c_{ij})$ in each class,
and then observe from the equations that whenever the average degree in a
given class $i$ is more than 100 at some time $t$,
$-\sum_{j}\mathcal{\bar{E}}_{ij}^{\prime}(t)>\mathcal{\bar{F}}_{i}^{\prime}(t)+\mathcal{\bar{T}}_{i}^{\prime}(t)$.

Note that we have only shown that the conditions of the theorem hold with high
probability over initial graph configurations; clearly, this is sufficient for
our desired result.

### D.2. Phase 2 of the Karp–Sipser algorithm (equitable case)

We also use Wormald’s theorem to justify our analysis of the second phase of
the algorithm in the equitable case. Here, $Y_{i}$ is the state of the tuple
after the $i$th run of the algorithm – i.e., the $i$th time where there are no
thin vertices. We define $f_{l}$ to be the expected change in the tuple that
one of these runs would incur if the transition probability estimates from
Section 2.5 held exactly and did not change throughout the run.

In order for this process to have the desired Lipschitz properties, we will
need to define a more restricted domain than the entire possible space of
tuples. In particular, we will fix some constants $\gamma$ and $\epsilon$, and
consider the domain of $Y$ to consist only of tuples where the average degree
into each class differs by at most $\gamma$, and is at least $2+\epsilon$. The
value of $\epsilon$ is chosen in the analysis; to determine $\gamma$, we
observe the following:

  * $\bullet$

$\lambda_{i}$ is defined such that
$\frac{\lambda_{i}(e^{\lambda_{i}}-1)}{e^{\lambda}_{i}-1-\lambda_{i}}$ is
equal to the average degree of class $i$. This is monotonically increasing in
the average degree of class $i$; so there is some constant $\lambda>0$ such
that if the average degree in class $i$ is at least $2+\epsilon$, then
$\lambda_{i}>\lambda$.

  * $\bullet$

The function
$\delta_{i}\theta_{i}=\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{i}}{e^{\lambda_{i}}-1}$
is bounded above by 1 and monotonically decreasing for $\lambda_{i}>0$. So,
there exists some constant $\eta>0$ such that
$\frac{\lambda}{1-e^{-\lambda}}\cdot\frac{\lambda}{e^{\lambda}-1}<1-2\eta$.

  * $\bullet$

$\lambda_{i},\lambda_{j}\mapsto\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{j}}{e^{\lambda_{j}}-1}$
is uniformly continuous, so there exists some constant $\kappa$ such that
$|\lambda_{i}-\lambda_{j}|<\kappa$ implies that
$|\left(\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{j}}{e^{\lambda_{j}}-1}\right)-\left(\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{i}}{e^{\lambda_{i}}-1}\right)|<\eta$
– which, if $\lambda_{i}>2+\epsilon$, implies
$\left(\frac{\lambda_{i}}{1-e^{-\lambda_{i}}}\cdot\frac{\lambda_{j}}{e^{\lambda_{j}}-1}\right)<1-\eta$.

  * $\bullet$

When defined on the domain $[2+\epsilon,\infty)$, $\lambda_{i}$ is uniformly
continuous as a function of the average degree of $i$. So, we can define
$\gamma$ such that $|\text{average degree in class $i$}-\text{average degree
in class $j$}|<\gamma$ implies $|\lambda_{i}-\lambda_{j}|<\kappa$ whenever
average degrees are greater than $2+\epsilon$.

We will define the stopping time $m$ of the process to be the first time it
leaves this domain. Note that, as in Phase 1, the value of $|Y|$ is bounded by
$100c_{\max}n$ with probability $1-o(1)$, since it is initially and can only
decrease. We’re now ready to verify the criteria of Wormald’s theorem.

  1. i)

Take again $w=n^{0.5}$ and $\lambda=\log n$. We can describe a single run of
the algorithm as a branching process: each degree-1 vertex created by the
algorithm corresponds to a node that has children according to the number of
degree-2 vertices adjacent to its neighbour; this corresponds to expected
offspring number of $\delta_{i}\theta_{j}<1-\eta$. After each removal we are
uniform over graphs with the remaining statistics; so, as long as the
branching process size is $o(n)$, we can treat the treat these offspring
distributions roughly independently for each node (in particular, as long as
the branching process is $o(n)$ with high probability, all offspring
distributions have expectation at most $1-\frac{\eta}{2}$ regardless of the
values for the other nodes). To prove that
$\mathbb{P}\left[|Y^{(l)}_{t+1}-Y^{(l)}_{t}|>\frac{\sqrt{w}}{\lambda^{2}\sqrt{\log
n}}\Big{|}H_{t}\right]=o(n^{-3})$, we therefore just need to show that the
probability that a Galton–Watson tree with $\mu<1-\frac{\eta}{2}$ reaches size
$\frac{n^{0.25}}{(\log n)^{5/2}}$ is $o\left(\frac{1}{n^{3}}\right)$; this
follows from a standard Chernoff bound.

  2. ii)

The fact that
$\mathbb{E}(Y^{(l)}_{t+1}-Y^{(l)}_{t}|H_{t})=f_{l}(t/n,Y_{t}^{(1)}/n,\dots,Y^{(a)}_{t}/n)+o(1)$
holds is because we expect a constant run duration, and we know our initial
degree estimates will hold with small error terms when we remove a constant
portion of the graph.

  3. iii)

Continuity of $f_{l}$ is clear from continuity of our degree estimates and the
fact that small changes in the edge densities of the graph can’t bias the
branching process too heavily. Similar justification that it’s Lipschitz on
the given domain can be found by examining the degree estimate functions.

Since $Y_{0}/n$ is with high probability $o(1)$ from having equal average
degrees, and this ODE keeps equal average degrees equal, with high probability
the degrees stay within $o(1)$ of equal until the stopping time.

### D.3. Analysis of SHORTSIGHTED

Define the 2-D Markov Chain $Z_{t}$, where the first coordinate represented
the number of unmatched $R_{0}$ vertices while the second coordinate
represents the number of unmatched $R_{1}$ vertices at time $t$ during a run
of SHORTSIGHTED. We have that $Z_{0}=(|R_{0}|,|R_{1}|)$. If we are in the
regime where we prefer class $0$, we have transition probabilities as follows:

$\displaystyle\mathbb{P}(Z_{t+1}=(x-1,y)|Z_{t}=(x,y))=\frac{1}{2}\left(1-\left(1-p_{0,0}\right)^{x}\right)+\frac{1}{2}\left(1-\left(1-p_{1,0}\right)^{x}\right)\rightarrow\frac{1}{2}\left(1-e^{-c_{0,0}x/n}\right)+\frac{1}{2}\left(1-e^{-c_{1,0}x/n}\right)$
$\displaystyle\mathbb{P}(Z_{t+1}=(x,y-1)|Z_{t}=(x,y))=\frac{1}{2}\left(1-p_{0,0}\right)^{x}\left(1-\left(1-p_{0,1}\right)^{y}\right)+\frac{1}{2}\left(1-p_{1,0}\right)^{x}\left(1-\left(1-p_{1,1}\right)^{y}\right)$
$\displaystyle\rightarrow\frac{1}{2}e^{-c_{0,0}x/n}\left(1-e^{-c_{0,1}y/n}\right)+\frac{1}{2}e^{-c_{1,0}x/n}\left(1-e^{-c_{1,1}y/n}\right)$
$\displaystyle\mathbb{P}(Z_{t+1}=(x,y)|Z_{t}=(x,y))$
$\displaystyle=\frac{1}{2}\left(1-p_{0,0}\right)^{x}\left(1-p_{0,1}\right)^{y}+\frac{1}{2}\left(1-p_{1,0}\right)^{x}\left(1-p_{1,1}\right)^{y}$
$\displaystyle\rightarrow\frac{1}{2}e^{-c_{0,0}x/n}e^{-c_{0,1}y/n}+\frac{1}{2}e^{-c_{1,0}x/n}e^{-c_{1,1}y/n}$

We now verify the three conditions of Wormald’s:

  1. i)

This simply comes from the fact that at each time step, each coordinate of
$Z_{t}$ can change by at most $1$.

  2. ii)

We use the following fact from [16]: for $n>0$, $c\leq n/2$, and $x\in[0,1]$,
we have

$\biggr{\rvert}e^{-cx}-\left(1-\frac{c}{n}\right)^{nx}\biggr{\rvert}\leq\frac{c}{ne}$

We can apply this term-wise to each of our probabilities, giving us the
desired condition.

  3. iii)

$e^{x}$ is Lipschitz continuous on $[0,1]$, therefore we have the third
condition as well.

An essentially identical proof follows for the Markov chain where we prefer
class $1$. Therefore we may apply Wormald’s theorem to obtain the differential
equations stated in the lemma. The second system of differential equations
follows as well, because the initial conditions hold almost surely (within
$o(n)$).
We have also applied Wormald’s in the analysis of GREEDY in the equitable
case. Due to the similar structure of transition probabilities between GREEDY
and SHORTSIGHTED, the verification of the conditions of Wormald’s is also very
similar.