Formerly at ]Massachusetts Institute of Technology, USA.

# Redatuming physical systems using symmetric autoencoders

Pawan Bharadwaj  [  Indian Institute of Science, CV Raman Rd, Bengaluru,
Karnataka 560012, India.  Matthew Li  Laurent Demanet  Massachusetts Institute
of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139, USA.

###### Abstract

This paper considers physical systems described by hidden states and
indirectly observed through repeated measurements corrupted by unmodeled
nuisance parameters. A network-based representation learns to disentangle the
coherent information (relative to the state) from the incoherent nuisance
information (relative to the sensing). Instead of physical models, the
representation uses symmetry and stochastic regularization to inform an
autoencoder architecture called SymAE. It enables redatuming, i.e., creating
virtual data instances where the nuisances are uniformized across
measurements.

††preprint: APS/123-QED

#### Introduction.

In contemporary sciences, there is increasing reliance on experimental designs
involving measurements that are corrupted by unmodelled and uncontrollable
_nuisance variations_. For example, in geophysics, specifically passive time-
lapse seismic monitoring, the recorded seismic data are generated by
uncontrollable sources related to tectonic stress changes in the subsurface
[1] or ocean-wave activity [2]. Similarly, in astronomy, the fluorescent
emissions which characterize the lunar surface’s chemical composition
fluctuate depending on unmodelled solar flares [3, 4]. Such designs introduce
ambiguity when determining whether changes in data represent _coherent
information_ , i.e., a signal indicating changes related to the underlying
physical state, or conversely represent _nuisance information_ , i.e.,
incidental variations due to noise inherent to the data acquisition.
Nevertheless, these uncontrollable experiments (along with others listed in
Tab. 1) remain the only feasible avenue to measure and study certain physical
phenomena. This motivates the development of algorithmic tools to reliably
disentangle the nuisance noise from coherent signals in these settings.

Figure 1:  Illustration of separation between two scales. The coherent
information (marker shape) related to the state varies on a much slower scale
compared to the nuisance information (marker distance from the baseline).
Here, each marker represents a measurement.

This paper focuses on a sub-class of such experiments where variations in the
measurements occur across two different scales: one in which the physical
processes affecting the coherent information occur, and the other scale
corresponding to noise processes that induce variations in the nuisance
information. We assume there exists a strong scale separation in which the
noise processes occur at a significantly faster rate than the former. This
assumption is crucial as it enables us to neglect variations in the coherent
information within a collection of closely-spaced measurements. We refer to
these closely-spaced (in scale) or repeated measurements as _instances_ , and
groups of instances altogether describe a _(physical) state_ ; the dichotomy
in scaling and its relation to instances and states is illustrated in Fig. 1.

We further assume that the experiments we consider abundantly produce
measurements describing the same physical state, albeit with different
nuisance variations. Examples of experiments that satisfy these conditions are
listed in Tab. 1. Critically, in principle, having access to a sufficiently
dissimilar collection of instances enables disentanglement of coherent
information from nuisance information without any reference to the underlying
physical model [5].

Our proposed approach to disentanglement decomposes each measurement into
separate _latent codes_ which are correlated, but typically not equivalent, to
the corresponding (unknown) parametric representations underlying each source
of information. These coherent and nuisance latent codes are determined from
an auto-encoding architecture with an encoder, which maps into the latent
space, and a decoder, which reconstructs the data in a near-lossless fashion.
Notably, this avoids explicit modeling of both the physics and the nuisances
by instead relying on data to inform these properties. This framework can be
seen as a vast generalization of multichannel blind deconvolution [6], where
neural networks replace the convolutional signal model, the coherent
information replaces the unknown source, and the nuisance variations
correspond to the unknown filters.

Table 1:  A representative list of experiments, where numerous instances are measured at each state that describes the physical phenomenon of interest. The instances exhibit dissimilarities due to the nuisance variations while sharing coherent information about the state.  |  |  | _components of information_
---
_in each instance_
| _experiment; goal is to_
---
_characterize the variation of $\cdots$_
| _measured instances_
---
_in each state comprise $\cdots$_
| _coherent information_
---
_describing the state_
| _nuisance_
---
_information_
| seismic time-lapse imaging;
---
subsurface with time [7, 8]
| waves propagating through
---
a given subsurface region,
but generated by different
uncontrollable sources
| mechanical properties
---
of the subsurface region
| source signature, location
---
and mechanism
| seismology;
---
source mechanism among
different earthquakes [9, 10]
| waves from an earthquake
---
measured at different receivers
| earthquake’s spectrum,
---
geology near
epicenter region, etc.
| multipathing in the
---
subsurface, Doppler effects
from rupture propagation, etc.
| lunar X-ray
---
fluorescence spectroscopy;
lunar geology with location [11, 4]
| fluorescence from regions
---
that share a given rock type
under different solar conditions
| elemental composition
---
of the rock type
| solar-flare
---
information
| asteroseismology [12, 13];
---
pulsating mechanism among
Rapidly oscillating Ap [14]
or Delta Scuti [15] stars
| brightness of a given star
---
measured in
different temporal windows
| physics that is symmetrical
---
under time translation,
e.g., star’s internal structure,
kappa opacity mechanism, etc.
| short-lived excitation
---
mechanisms, e.g.,
surface convection,
variable radial velocity, etc.

Disentanglement into coherent and incoherent latent variables enables a
reliable comparison of coherent information between instances collected from
different states. However, this relegates the analysis into a latent space
that is abstractly related to the physical system. To that end, we propose an
additional mechanism, called _redatuming_ , which converts from latent
coordinates back into the nominal data space representation with specifically
chosen properties. This involves combining coherent information from one
instance with the nuisance information from a reference instance in order to
synthesize a _virtual_ instance that is not originally measured (i.e., not
present in the dataset). The relevance of such virtual data instances is that
they can be engineered to share their nuisance information with another
(measured) data instance so that any remaining discrepancy can be solely
explained from differences in the underlying coherent physical states. This
entire process can be alternatively viewed as “swapping the physics” between
states. We conjecture that this new type of redatuming can help rethink how to
approach inverse problems with significant uncertainties in the forward model.

We illustrate redatuming using the example of time-lapse geophysical
subsurface monitoring cited in Tab. 1. Here, seismic surveys are conducted to
measure the subsurface properties (the coherent information) indirectly by
recording reflected and transmitted elastic waves generated by uncontrolled or
unreliably modeled mechanisms (the nuisance information). In this setting, it
is reasonable to assume that changes to the complex heterogeneous subsurface
occur on a significantly slower timescale (e.g., on the order of months) than
the variations in the uncontrollable seismic sources (on the order of hours or
days). As such, the variations in the subsurface mechanical properties, as
functions of the lateral scale dependent on distance $x$ and depth $z$, can be
safely neglected within each state. The goal is to detect and characterize
changes in subsurface between the states, e.g., to distinguish between “state
#1” and “state #2” along the abscissa of Fig. 2 111Note that the structural
complexities of the media result in multipath wave propagation, thereby
complicating the inverse problem..  In each state, the measured instances
constitute the time-dependent (indexed using $t$) wavefield recorded at a
given set of receivers (indexed using $r$) in the medium — plotted in Figs. 2a
and 2c.

In effect, the seismic sources are realized with randomized signatures and
locations, c.f., the nuisance variations visualized along the ordinate of Fig.
2. This confounds direct visual comparison between the measured instances Fig.
2a and 2c as it is unclear whether the localized changes (indicated by the
blue arrow) are to be attributed to changes in the medium or the source.
Redatuming overcomes this ambiguity by generating a _virtual_ instance,
plotted in Fig. 2d. This virtual instance is engineered by replacing the
subsurface information of Fig 2a with that of Fig 2c while retaining its
source/nuisance information. As a result, the virtual instance can be
subtracted from the reference instance (here 2a) to qualify or quantify
potential subsurface changes via standard imaging techniques. We emphasize
that redatuming enables domain experts to perform data analysis using
traditional tools without any reference to the implicit latent space.

These ideas are inspired by recent machine learning literature where
redatuming is instead referred to as _styling_ , or _deep-fakes_ , see e.g.,
[17, 18, 19], and the reliance on multiple instances is referred to as _weak
supervision_ [20, 5]. However, we note that these communities primarily apply
these tools to images with significant visual structure wherein nuisance
information relates to the “image style”, and the coherent information relates
to the “image content”. This letter instead introduces the idea of redatuming
to scientific signals, enabling us to quantify virtual-instance accuracy
against explicit synthetic models rigorously.

#### Our Contributions.

To achieve redatuming, we propose an unsupervised deep-learning architecture
called symmetric autoencoder (SymAE). Achieving the requisite disentangled
latent representation with SymAE requires two deliberate architectural design
choices:  1. The encoder for the coherent latent variables is constrained to
be symmetric with respect to the ordering of the instances indexed by nuisance
variations.  2. The remaining latent-code dimensions are encouraged to encode
independent information by stochastic regularization that promotes
dissimilarity among the instances 222In previous work, we used focusing
constraints [46] to maximize this dissimilarity and regularize blind
deconvolution.. Therefore, these remaining latent components are designed to
_not_ represent the coherent information and correspond only to the nuisance
variations.

Once the coherent and nuisance information are disentangled in the latent
space, redatuming is equivalent to decoding a hybrid latent code,
specifically, a hybridization of the coherent code from one state and the
nuisance code of an instance from another state.  We provide numerical
evidence that SymAE’s redatuming preserves and captures the salient features
of the underlying physical modeling operator, thus enabling the use of virtual
datapoints for subsequent downstream tasks such as parameter estimation.  We
numerically validate that the virtual instances generated without reference to
the physics satisfy the governing wave equation up to a low relative mean-
squared error. This indicates that SymAE redatuming is consistent with, or
preserves, the physics of wave propagation.

The concept of redatuming appears in the context of traditional seismic
inversion [22, 23, 24, 25, 26]. The major differences with our current
generalized approach, however, are:  1. the seismic-specific redatuming is
limited to swapping sources or receivers from one state to another — in
contrast, SymAE aims to swap any information that is coherent across the
instances;  2. seismic redatuming either requires prior knowledge about the
subsurface or uses physics-derived relations with convolutions or cross-
correlations— in contrast, SymAE derives the redatuming operators from the
recorded data in an unsupervised manner, unlocking processing for far more
general situations than cross-correlations allow.  We refer the reader to [27,
28, 29] for examples of analytical-based redatuming applied to specific
geophysical settings.

SymAE heavily relies on imposing symmetries in the encoder to separate the
latent code. This idea of using symmetry, or equivalently physical priors, to
promote structure in the neural networks has been proposed in various works,
for instance: [30] embedded even/odd symmetry of a function and energy
conservation into a neural network by adding special _hub_ layers; [31]
propose gauge equivariant CNN layers to capture rotational symmetry; [32]
structures their networks following a Hamiltonian in order to learn physically
conserved quantities and symmetries. The choice of symmetry is bespoke to each
application, and the identification of valid symmetries in our physical prior
is one of the contributions and insights of SymAE.

#### Datapoints and Notation.

In this section, we describe the training set $\\{X_{i}\\}_{i=1,\ldots,n_{X}}$
that SymAE encodes to produce a compressed and disentangled representation. We
re-iterate that we presume the scale separation illustrated in Fig. 1 in our
dataset. As such, each datapoint $X_{i}$ contains multiple instances that
repeatedly capture the same physical state $\epsilon_{i}$, but each instance
may differ on account of nuisance variations. We uniformly sample from $1$ to
$n_{\epsilon}$ to generate the state labels
$\\{\epsilon_{i}\\}_{i=1,\ldots,n_{X}}$ for our synthetic experiments — in
practice, the experimental conditions determine this sampling distribution. We
emphasize that knowledge of the state labels is _not_ necessary for either
training or testing since our framework is purely unsupervised. We index the
instances in datapoint as $X_{i}[\tau]$ for $\tau=1,\ldots,n_{\tau}$ such that
$X_{i}=[X_{i}[1];\ldots;X_{i}[n_{\tau}]]$. Each instance $X_{i}[\tau]$ is
represented as $k$-dimensional vectors, and the determination of $k$ is
specific to each experiment.  For the seismic experiment depicted in Fig 2a,
each instance is a source gather, where the dimension $k$ is the product of
the number of receivers and the length of the time series. Each $X_{i}$
comprises several sources that illuminate the same subsurface region.  In our
notation, $[A;\,B]$ denotes a vertical concatenation of two vectors $A$ and
$B$. Again, the collection of instances
$\\{X_{i}[\tau]\\}_{\tau=1,\ldots,n_{\tau}}$ for a fixed index $i$ shares the
same coherent information to the state $\epsilon_{i}$ but vary by
$\tau$-specific nuisance variations.

#### Architecture.

We refer the reader to [33] for an accessible tutorial on autoencoders 333 We
choose to use a deterministic autoencoding strategy for simplicity. It is
possible to formalize the ideas in this paper using the variational
autoencoding framework.. Functionally, autoencoders are comprised of two
components: an encoder $\mathtt{Enc}$ that maps each datapoint $X_{i}$ into
latent code $H_{i}=\mathtt{Enc}(X_{i})$, and a decoder $\mathtt{Dec}$ that
attempts reconstruct to $X_{i}$ from the code. Traditionally, both functions
$\mathtt{Enc}$ and $\mathtt{Dec}$ are determined by minimizing the
reconstruction loss

$\displaystyle\mathtt{Enc},\,\mathtt{Dec}=\operatorname*{arg\,min}_{\mathtt{Enc},\,\mathtt{Dec}}\sum_{i}\|X_{i}-\mathtt{Dec}(\mathtt{Enc}(X_{i}))\|^{2}$
(1)

over the training dataset. When non-linear parameterizations are used for both
$\mathtt{Enc}$ and $\mathtt{Dec}$, the latent representation no longer
describes the geometry of the datasets using linear subspaces [35]. However,
this representation can efficiently compress the information [36].

SymAE builds on non-linear autoencoders but requires additional modifications
as a direct application of traditional autoencoding ideas will not ensure that
the coherent and nuisance information are encoded into separate components
(dimensions) in the latent space. To achieve this separation, SymAE relies on
the unique encoder structure as depicted in Fig. 3 444We provide Tensorflow-
style [47] algorithms in the supplementary material that detail the
implementation of SymAE. Additionally, following the double-blind review
process, a link to a Github repository containing reproducible code will be
made available in this footnote.. The encoder structure can be mathematically
described by

$\displaystyle\mathtt{Enc}($ $\displaystyle X_{i}$ $\displaystyle)=$
$\displaystyle[\mathtt{CEnc}($ $\displaystyle X_{i}$
$\displaystyle);\,\mathtt{NEnc}(X_{i}[1]);\,\ldots;\,\mathtt{NEnc}(X_{i}[n_{\tau}])].$
(2)

This output corresponds to a latent code $H_{i}$ which is partitioned into
interpretable components. Specifically, each datapoint
$X_{i}=[X_{i}[1];\ldots;X_{i}[n_{\tau}]]$ is represented as a structured
latent code $H_{i}=[C_{i};\,N_{i}[1];\,\ldots;\,N_{i}[n_{\tau}]]$ in which the
sub-components $C_{i}=\mathtt{CEnc}(X_{i})$ contain coherent information in
$X_{i}$ while the remaining sub-components
$N_{i}[\tau]=\mathtt{NEnc}(X_{i}[\tau])$ encode the complementary instance-
specific nuisance information. Note the dimensions $l$ and $m$ of the latent
codes $C_{i}\in\mathbb{R}^{l}$ and $N_{i}[\cdot]\in\mathbb{R}^{m}$ are user-
specified hyperparameters which need not coincide.

Subsequently, SymAE’s decoder $\mathtt{Fuse}$ non-linearly combines code
$C_{i}$ with each instance-specific code $N_{i}[\cdot]$ to reconstruct the
original datapoint, instance-by-instance, viz.

$\displaystyle\hat{X_{i}}$ $\displaystyle=$
$\displaystyle\mathtt{Dec}(H_{i})=\mathtt{Dec}([C_{i};\,N_{i}[1];\,\ldots;\,N_{i}[n_{\tau}]])$
(3) $\displaystyle=$
$\displaystyle[\mathtt{Fuse}([C_{i};\,N_{i}[1]]);\,\ldots;\,\mathtt{Fuse}([C_{i};\,N_{i}[n_{\tau}]])].$

We do not enforce any constraints on $\mathtt{Fuse}$ in our experiments and
parametrize it with standard deep learning building blocks 555We provided more
architectural details in the supplementary material.

Figure 2:  Redatuming is equivalent to swapping the coherent and nuisance
information in SymAE’s latent space. Here, as SymAE learns to represent the
information on medium (coherent) and incoming plane-wave sources (nuisance)
separately, the recorded wavefield (a and c) in a seismic experiment (see Tab.
1) can be redatumed to generate virtual measurements (b and d). A low error
confirms that the redatuming operator captures salient features of the wave-
equation modeling despite a multipath propagation due to the complex medium
inhomogeneities.  Figure 3:  Architecture of symmetric autoencoder. The
information that is coherent across the instances of a datapoint can only
propagate through the network via solid arrows — notice the stochastic
regularization employed to prevent its propagation. We used colored arrows to
indicate the propagation of the remaining instance-specific nuisance
information — notice that a symmetric function, i.e., symmetric w.r.t. the
order of the instances, prevents its propagation. As a result, the autoencoder
disentangles the coherent information from the nuisance variations in the
latent space.  We omitted the subscript $i$ for $X$, $C$ and $N$.

We ensure that $\mathtt{CEnc}$, the _coherent encoder_ , encodes at most the
coherency or similarity among the instances in $X_{i}$ by enforcing invariance
with respect to permutations of the instances within the datapoint.
Mathematically, this condition requires that

$\displaystyle
C_{i}=\mathtt{CEnc}(X_{i})=\mathtt{CEnc}(X_{i}[\varPi(1{:}n_{\tau})])$ (4)

for all permutations $\varPi$ along the instance dimension the output. This
symmetry invokes the dichotomy of scale assumed in the data – since only
nuisance variations are assumed to vary along the “fast scale” $\tau$ and that
any coherent changes are negligible, this permutation invariance ensures that
nuisance information cannot be encoded using $\mathtt{CEnc}$ without
significant loss of information. It follows from the pigeonhole principle that
only coherent information can remain in $C_{i}$ if a low auto-encoding loss is
achieved.

SymAE’s coherent encoder explicitly achieves the invariance mentioned above
using permutation-invariant network architectures following [39] which provide
universal approximation guarantees for symmetric functions.  These
architectures use pooling functions such as the $\mathrm{mean}$ or the
$\mathrm{max}$ across the instances to ensure permutation invariance. We refer
to [40] for a review of alternative pooling functions, including attention-
based pooling. In our experiments, the data due to each source instance are
transformed using $\mathtt{CEnc}_{1}$ and summed along the instance dimension.
This output is then processed by $\mathtt{CEnc}_{2}$ resulting in

$\displaystyle
C_{i}=\mathtt{CEnc}_{2}\left(\frac{1}{n_{\tau}}\sum_{\tau=1}^{n_{\tau}}\mathtt{CEnc}_{1}(X_{i}[\tau])\right),$
(5)

yielding the network architecture of $\mathtt{CEnc}$. Intuitively,
$\mathtt{CEnc}_{1}$ extracts coherent information from each of the instances
while the summation encourages them to be aligned. This information is further
compressed using $\mathtt{CEnc}_{2}$. The functions $\mathtt{CEnc}_{1}$ and
$\mathtt{CEnc}_{2}$ are parametrized by compositions of fully connected layers
and convolutional layers. We emphasize that the key observation in eq. 5 is
that the summation of the _transformed instances_
$\mathtt{CEnc}_{1}(X_{i}[\tau])$ is symmetric with respect to the ordering of
instances. This ensures that the desired symmetry (eq. 4) is achieved.

In contrast, the purpose of $\mathtt{NEnc}$, the _nuisance encoder_ , is to
capture the nuisance information specific to each instance of a datapoint.
Critically, we do not want the decoder $\mathtt{Fuse}$ to ignore the $C_{i}$
component in favor of using purely $N_{i}[\cdot]$ information for
reconstruction. We desire disentanglement of the latent codes. Whereas
$\mathtt{CEnc}$ achieves this via symmetry, for the nuisance encoder this
separation is encouraged through the use of _stochastic regularization_ viz,

$\displaystyle N_{i}[\tau]=\mathtt{NEnc}(X_{i}[\tau])+\textrm{``strong
noise''}.$ (6)

Intuitively, this idea hinges on the assumption that coherent information does
not vary with the “fast scale” $\tau$ indexing each instance. As such,
obfuscating each element $N_{i}$ via noise introduces artificial
dissimilarities along this scale; this, therefore, encourages the decoder to
instead rely on the coherent code (held constant for each instance, c.f. eq.
(3)) to reconstruct the coherent information. Similarly, as before, it follows
from the pigeonhole principle that the nuisance codes $N_{i}$ must contain at
most information relevant to nuisance information if a low auto-encoding loss
is achieved.

In our experiments, we implement this noise using either Bernoulli dropout
regularization [41] with probability $p$ or Gaussian dropout with unit mean
and $p(1-p)$ variance [42, 43]. In either case, the strength of the noise is
proportional to $p$, which is a hyperparameter the user must tune. Critically,
however, each $N_{i}$ must still be expressive enough to encode nuisance-
specific information. The balance between regularization strength $p$ and the
dimension (i.e., expressivity) of the latent codes is user-determined on an
external validation set. The SymAE components $\mathtt{NEnc}$, $\mathtt{CEnc}$
and $\mathtt{Fuse}$ are trained concurrently by minimizing Eq. 1 with the
regularization mechanism just described.  We emphasize that the stochastic
regularization is not employed to reduce over-fitting and improve
generalization error in the conventional sense, see, e.g., [44] for a survey
on stochastic techniques used in neural network training. Instead, the
intention is to promote learning dissimilar representations across nuisance
codes. At test-time, the entirety of the $N_{i}$ code is sent unaltered and
unobfuscated into the decoder.

Finally, note that we only constrained the encoders to avoid “cross-talk”
while disentangling the coherent and nuisance information. Implicitly the
success of SymAE, therefore, requires a sufficiently large number of instances
with _dissimilar_ nuisance variations in order to achieve the desired
structure of the latent space. We leave an examination of characterizations of
physical models which are amenable to disentanglement to future work.

#### Redatuming into Virtual Instances.

A trained SymAE learns a representation with disentangled coherent and
nuisance information. Redatuming data becomes equivalent to manipulations in
the latent space — as illustrated in the Fig. 2, where virtual instances are
generated by swapping latent coordinates. In general, the coherent information
in the $\tau$-th instance of a datapoint $X_{i}$ can be swapped with that of
another datapoint $X_{j}$ using

$\displaystyle\hat{X}_{i\rightarrow
j}[\tau]=\mathtt{Fuse}([\mathtt{CEnc}(X_{j});\,\mathtt{NEnc}(X_{i}[\tau])]).$
(7)

Here, $X_{j}$ is an observation of a different state compared to $X_{i}$.
Notice that the nuisance information in the virtual datapoint
$\hat{X}_{i\rightarrow j}$ is identical to that of the original datapoint
$X_{i}$. Consequently, we attribute the difference between $X_{i}$ and
$\hat{X}_{i\rightarrow j}$ to the changes between the physical states. As a
demonstration, the observed and virtual instances from the seismic experiment
are embedded into the SymAE’s latent space in Fig. 2.

#### Experiments.

We now detail the application of SymAE towards experiments that monitor
subsurface changes using seismic waves. As noted earlier, the measurements
vary on two different (time) scales.  1. The slower time scale is associated
with the subsurface changes that typically occur in the order of months. As
such, the goal is to detect or determine variations in the coherent
(subsurface) information between seismic surveys (e.g., baseline and monitor).
2. The faster time is usually on the order of the duration of the seismic
survey, i.e., either hours or days; the variation in the coherent information
is negligible on this scale. During each survey, waves from numerous
uncontrollable sources, here taken to be the nuisance information, are
recorded as instances.  For our synthetic experiments, an instance is modeled
as the pressure wavefield $u(\mathbf{x},t)$ from a finite-difference solver
with absorbing boundary conditions for the acoustic wave equation:

$\displaystyle\frac{1}{c^{2}(\mathbf{x})}\frac{\partial^{2}u}{\partial
t^{2}}-\nabla\cdot\left(\nabla
u\right)=\delta(\mathbf{x}-\mathbf{x}_{s})w(t).$ (8)

Here, $\mathbf{x}=[x,z]$ denotes the Cartesian coordinate vector and $t$
denotes time. The medium is parameterized using the wave-velocity
$c(\mathbf{x})$. During the forward modeling, we vary $c$ at a slower rate
compared to source parameters, i.e., position $\mathbf{x}_{s}$ and signature
$w(t)$ that determine the nuisance variation in each modeled instance.

Figure 4:  Deep redatuming of waves recorded on $\partial\mathbb{D}$ due to
point sources in the dotted region. This experiment illustrates that SymAE can
isolate (coherent) information on the medium (Gaussian) perturbation in its
representation — however, the perturbation has to lie within
$\partial\mathbb{D}$. a) $X_{1}[1{:}4]$; original instances from the first
state with a homogeneous medium. b) $\hat{X}_{1\rightarrow 2}[1{:}4]$; virtual
instances generated after swapping code $C_{1}$ of the first state with code
$C_{2}$ of the second state. A high MSE in $\hat{X}_{1\rightarrow 2}[4]$
indicates that $C_{2}$ fails to represent the effects of the Gaussian
perturbation entirely. Note that this perturbation extends beyond
$\partial\mathbb{D}$. c) $\hat{X}_{1\rightarrow 3}[1{:}4]$; same as (b),
except a lower MSE, means that $C_{3}$ satisfactorily represents the medium
when the perturbations lie within $\partial\mathbb{D}$.

We justify that SymAE captures the salient features of the physics of wave
propagation using a simple illustration. Consider the wave-velocity of a
medium that varies in a $2\,\text{km}\times 2\,\text{km}$ region, shown in
Figs. 4a–c, across three states with $\epsilon_{i}\in\\{1,2,3\\}$ as described
in Tab. 2.

Table 2:

state $\epsilon$ |  medium perturbation11footnotemark: 1 |  MSE22footnotemark: 2 |  virtual MSE33footnotemark: 3
---|---|---|---
1 | none; homogeneous | $<0.01$ | -
2 |  not entirely inside $\partial\mathbb{D}$44footnotemark: 4 | $<0.01$ |  high ($>0.3$)
3 |  inside $\partial\mathbb{D}$44footnotemark: 4 | $<0.01$ |  low ($<0.1$)

11footnotemark: 1

Gaussian perturbation 22footnotemark: 2 normalized mean-squared error between
the true $X$ and reconstructed $\hat{X}$ datapoints for both training and
testing 33footnotemark: 3between virtual and synthetic instances after
redatuming 44footnotemark: 4receiver circle with center $[0,0]$ and radius
$600\,$m

Point sources at $\mathbf{x}_{s}=[R\,\cos(\theta),R\,\sin(\theta)]$ with
signature $w(t)$ are used for modeling instances. The random variables $R$ and
$\theta$ are uniformly distributed on $[0.8,1.0]\,$km and $[0,2\pi]$,
respectively. The random source wavelet $w(t)$ has a duration of $0.13\,$s, is
sampled from a standard normal distribution and is convolved with a 25 Hz
high-cut filter. After solving eq. 8, the acoustic wavefield is sampled at
$160$ time steps and $100$ evenly-distributed receiver locations on a circle
$\partial\mathbb{D}$ to form an instance of dimension $k$=16,000. We generated
8,000 instances per state and considered a total of 6,000 datapoints (with
$n_{\tau}$=$20$) for training and testing. It is important to note that the
distribution of the forcing term in eq. 8 is independent of the state
$\epsilon$ to facilitate disentanglement.

We have invariably used the same medium parameters during the forward modeling
of the instances in each state. Therefore, we hypothesize that:  1. the medium
parameters $c(\mathbf{x})$ characterize the coherent information represented
by the code $C_{i}$, i.e., $\mathtt{CEnc}$ encodes the information related to
the entire medium in each state;  2. the forcing term $w(t)$ and the source
position $\mathbf{x}_{s}$ characterize the nuisance information, represented
by $N_{i}$, of a given instance.  We test these hypotheses numerically and
show that $\mathtt{CEnc}$ does not encode the entire medium but only a portion
that is coherently illuminated by all the sources. After redatuming, we
compute relative MSE between the virtual instances (generated by deep
redatuming) and synthetic instances — a low MSE signifies that the virtual
instance satisfies the governing wave equation in eq. 8 with appropriate
medium and source parameters. We now redatum four sources, $X_{1}[1{:}4]$ as
in Fig. 4a, picked from the first state ($\epsilon=1$). First, we swapped
$C_{1}$ of these measurements with $C_{2}$ to include the physics of wave-
propagation related to the Gaussian perturbation in $\epsilon=2$. The virtual
instances $\hat{X}_{1\rightarrow 2}$ are plotted in Fig. 4b — it can be
observed that source information (position and signature) remained intact
during redatuming, confirming that $C_{2}$ does not represent any of the
source effects. Furthermore, notice that most of the virtual instances have
low MSE, for example, $\hat{X}_{1\rightarrow 2}[1{:}3]$, indicating that
$C_{2}$ captured a significant portion of the Gaussian perturbation. However,
the virtual instances with source locations close to that of
$\hat{X}_{1\rightarrow 2}[4]$, plotted in Fig. 4b, have high MSE. What is
unique about these sources? It is evident from the ray paths in Fig. 4a that
these high-MSE source locations illuminate the portion of the Gaussian
perturbation outside $\partial\mathbb{D}$. On the other hand, the region
inside $\partial\mathbb{D}$ is coherently illuminated irrespective of the
source position. We infer that SymAE’s coherent code only represents the
propagation effects of inhomogeneities inside $\partial\mathbb{D}$. In order
to further confirm this inference, we then generated virtual instances
corresponding to the state $\epsilon=3$, where the Gaussian perturbation is
entirely inside $\partial\mathbb{D}$ as depicted in Fig. 4c. We notice that
all the virtual instances have low MSE. Therefore, we conclude that SymAE
learned to differentiate the coherently-illuminated portion of the medium by
the waves without the need for physics. This means, for seismic monitoring
experiments, all the sources must coherently illuminate the time-lapse medium
changes of interest.

The experiment in Fig. 2 involves seismic-wave propagation in a complex 2-D
structural model, which is commonly known as the Marmousi model [45] in
exploration seismology. The structural complexities will lead to multipath
propagation. The P-wave velocity plots of this model for $\epsilon=1$ and
$\epsilon=2$, with source-reciever geometry, are in the Figs. 5a and 5b,
respectively. The forcing term represents a random plane-wave source input at
the bottom of the model. The source wavelet $w(t;\tau)$ is generated by
convolving a Ricker wavelet whose dominant frequency is sampled from
$\\{10,\\-12.5,\\-\ldots,20\\}$ Hz, with a random time series (of $0.4\,$s
duration) sampled from a standard normal distribution. In this case, the
change in the medium parameters from $\epsilon=1$ to $\epsilon=2$ is
coherently illuminated by all the plane-wave sources, similar to the
$\epsilon=3$ Gaussian perturbation of the previous example. Therefore, the
virtual measurements after redatuming are expected to have low MSE, as
confirmed by the results in Fig. 5.

Figure 5:  Seismic Marmousi experiment of Fig. 2 where incident plane waves on
the bottom of the medium undergo multipath propagation due to the complex
inhomogeneities — three original instances (solid arrows) from each state are
plotted reveal the complex wavefield. Each instance results from a planewave
with a unique source wavelet and angle of arrival. Virtual instances (dashed
arrows) generated after swapping the coherent code from (a) to (b) and vice
versa have a low error, showcasing the success of deep redatuming with SymAE.

#### Conclusions.

We propose an autoencoder architecture for poorly controlled scientific
experiments that produce an abundance of incompletely modeled measurements of
a physical system. The autoencoder learns a data representation that
disentangles the coherent information inherent to the physical state, from the
nuisance modifications inherent to the experimental configuration, in a model-
free fashion. Two ideas are critical:  1. leveraging symmetry under reordering
of the data instance in order to represent the coherent information in a first
encoder, and  2. stochastic regularization in order to prevent coherent
information from being represented by the second encoder.  As a result, the
architecture can perform redatuming, i.e., the swapping of physics in order to
create virtual measurements.

###### Acknowledgements.

The authors thank TotalEnergies SE for their support. PB is also funded via a
start-up research grant from the Indian Institute of Science. PB thanks Girish
from Indian Space Research Organisation and Shyama Narendranath from U R Rao
Satellite Center for valuable discussions.

##  I Appendixes

### Algorithms

These Tensorflow-style [47] algorithms provide further details on the
implementation of SymAE. $\mathtt{ConvA}$ and $\mathtt{Conv}$ denote
convolutional layers with and without $\mathtt{elu}$ activation, respectively.
We used $\mathtt{distribute}$ to apply the same layer to each of the
instances.

1:
$C\leftarrow\mathtt{distribute}(\mathtt{ConvA})(X);\,C\leftarrow\mathtt{distribute}(\mathtt{ConvA})(C);\,C\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(C)$
{$\mathtt{CEnc}_{1}$}

2:
$C\leftarrow\mathtt{distribute}(\mathtt{ConvA})(C);\,C\leftarrow\mathtt{distribute}(\mathtt{ConvA})(C);\,C\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(C)$
{$\mathtt{CEnc}_{1}$}

3: $C\leftarrow\mathtt{reduce\\_mean}(C,\text{axis}=1)$ {sum over instances}

4:
$C\leftarrow\mathtt{ConvA}(C);\,C\leftarrow\mathtt{ConvA}(C);\,C\leftarrow\mathtt{MaxPool}(C)$
{$\mathtt{CEnc}_{2}$}

5:
$C\leftarrow\mathtt{ConvA}(C);\,C\leftarrow\mathtt{ConvA}(C);\,C\leftarrow\mathtt{BatchNormalization}(C)$
{$\mathtt{CEnc}_{2}$}

6:
$C\leftarrow\mathtt{MaxPool}(C);\,C\leftarrow\mathtt{Flatten}(C);\,C\leftarrow\mathtt{Dense}(C,l)$
{$\mathtt{CEnc}_{2}$}

7: $\mathtt{CEnc}=\mathtt{Model}(X,C)$

Algorithm 1 Keras-style algorithm for preparing coherent encoder
$\mathtt{CEnc}$.

1:
$N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(X);\,N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(N)$

2:
$N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(N)$

3:
$N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(N)$

4:
$N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{ConvA})(N)$

5: $N\leftarrow\mathtt{distribute}(\mathtt{BatchNormalization})(N)$

6:
$N\leftarrow\mathtt{distribute}(\mathtt{MaxPool})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{Flatten})(N);\,N\leftarrow\mathtt{distribute}(\mathtt{Dense})(N,m)$

7: $\mathtt{NEnc}=\mathtt{Model}(X,N)$

Algorithm 2 Keras-style algorithm for preparing nuisance encoder
$\mathtt{NEnc}$.

1: $\hat{N}\leftarrow\mathtt{dropout}(N,\alpha)$ {stochastic regularization}

2:
$\hat{C}=\mathtt{RepeatVector}(n_{\tau})({C});\,\hat{X}\leftarrow\mathtt{concatenate}([\hat{C},\hat{N}],\text{axis}=2)$
{distribute coherent code to each instance}

3: $\hat{X}\leftarrow\mathtt{distribute}(\mathtt{Dense}(n_{r}\times
n_{t}))(\hat{X});\,\hat{X}\leftarrow\mathtt{distribute}(\mathtt{Reshape}(n_{r},n_{t},1))(\hat{X})$

4:
$\hat{X}\leftarrow\mathtt{distribute}(\mathtt{ConvA})(\hat{X});\,\hat{X}\leftarrow\mathtt{distribute}(\mathtt{ConvA})(\hat{X});\,\hat{X}\leftarrow\mathtt{distribute}(\mathtt{ConvA})(\hat{X})$

5:
$\hat{X}\leftarrow\mathtt{distribute}(\mathtt{BatchNormalization})(\hat{X});\,\hat{X}\leftarrow\mathtt{distribute}(\mathtt{ConvA})(\hat{X});$

6: $\hat{X}\leftarrow\mathtt{distribute}(\mathtt{Conv})(\hat{X});${output
datapoint}

Algorithm 3 Fuse latent codes $C$ and $N$.

### Hyperparameters

For a given application, the following hyperparameters need to be tuned:

  * •

filters and kernel sizes of the convolutional layers — results do not strongly
depend on these as long as the encoders and decoders have enough flexibility;

  * •

length of the coherent code $l$ — results do not strongly depend on this
parameter;

  * •

the number of instances in each datapoint $n_{\tau}$ — we typically chose
$n_{\tau}=20$ and observed that results do not depend on this parameter as
long as $n_{\tau}>10$;

  * •

length of nuisance code $m$ — determined by the number of nuisance parameters;

  * •

and the dropout rate or noise strength $p$ added to the nuisance code —
stronger noise will lead to slower training, and weaker noise will make the
coherent code dysfunctional.

Out of these, the parameters $m$ and $p$ are crucial. They determine the
balance between the noise and expressivity of the nuisance code. Increasing
$m$ proportional to the noise strength is essential as higher noise makes the
nuisance code less expressive. In our experiments, we typically chose $p=0.5$
and $m$ as twice the number of nuisance parameters.

## References

  * Aki and Richards [2002] K. Aki and P. G. Richards,  _Quantitative seismology_ (2002).
  * Montagner  _et al._ [2020] J.-P. Montagner, A. Mangeney, and E. Stutzmann, Seismology and environment (2020).
  * Tandberg-Hanssen and Emslie [1988] E. Tandberg-Hanssen and A. G. Emslie,  _The physics of solar flares_ , Vol. 14 (Cambridge University Press, 1988).
  * Narendranath  _et al._ [2011] S. Narendranath, P. Athiray, P. Sreekumar, B. Kellett, L. Alha, C. Howe, K. Joy, M. Grande, J. Huovelin, I. Crawford, _et al._ , Lunar x-ray fluorescence observations by the chandrayaan-1 x-ray spectrometer (c1xs): Results from the nearside southern highlands, Icarus 214, 53 (2011).
  * Locatello  _et al._ [2019] F. Locatello, S. Bauer, M. Lucic, G. Raetsch, S. Gelly, B. Schölkopf, and O. Bachem, Challenging common assumptions in the unsupervised learning of disentangled representations, in  _Proceedings of the 36th International Conference on Machine Learning_, Proceedings of Machine Learning Research, Vol. 97, edited by K. Chaudhuri and R. Salakhutdinov (PMLR, 2019) pp. 4115–4124.
  * Xu  _et al._ [1995] G. Xu, H. Liu, L. Tong, and T. Kailath, A least-squares approach to blind channel identification, IEEE Transactions on Signal Processing 43, 2982 (1995).
  * Verdon  _et al._ [2010] J. P. Verdon, J.-M. Kendall, D. J. White, D. A. Angus, Q. J. Fisher, and T. Urbancic, Passive seismic monitoring of carbon dioxide storage at weyburn, The Leading Edge 29, 200 (2010).
  * Kamei and Lumley [2014] R. Kamei and D. Lumley, Passive seismic imaging and velocity inversion using full wavefield methods, SEG Technical Program Expanded Abstracts 2014 , 2273 (2014).
  * Aki [1972] K. Aki, Scaling law of earthquake source time-function, Geophysical Journal International 31, 3 (1972).
  * Shearer  _et al._ [2006] P. M. Shearer, G. A. Prieto, and E. Hauksson, Comprehensive analysis of earthquake source spectra in southern california, Journal of Geophysical Research: Solid Earth 111 (2006).
  * Clark and Adler [1978] P. Clark and I. Adler, Utilization of independent solar flux measurements to eliminate nongeochemical variation in x-ray fluorescence data, in  _Lunar and Planetary Science Conference Proceedings_ , Vol. 9 (1978) pp. 3029–3036.
  * Aerts  _et al._ [2010] C. Aerts, J. Christensen-Dalsgaard, and D. W. Kurtz,  _Asteroseismology_ (Springer Science & Business Media, 2010).
  * Handler [2012] G. Handler, Asteroseismology, arXiv preprint arXiv:1205.6407 (2012).
  * Samus  _et al._ [2004] N. Samus, O. Durlevich, _et al._ , Vizier online data catalog: Combined general catalogue of variable stars (samus+ 2004), VizieR Online Data Catalog , II (2004).
  * Campbell and Wright [1900] W. W. Campbell and W. Wright, A list of nine stars whose velocities in the line of sight are variable., The Astrophysical Journal 12 (1900).
  * Note [1] Note that the structural complexities of the media result in multipath wave propagation, thereby complicating the inverse problem.
  * Mirsky  _et al._ [2019] Y. Mirsky, T. Mahler, I. Shelef, and Y. Elovici, Ct-gan: Malicious tampering of 3d medical imagery using deep learning, in  _28th USENIX Security Symposium (USENIX Security 19)_ (USENIX Association, Santa Clara, CA, 2019) pp. 461–478.
  * Suwajanakorn  _et al._ [2017] S. Suwajanakorn, S. M. Seitz, and I. Kemelmacher-Shlizerman, Synthesizing obama: Learning lip sync from audio, ACM Trans. Graph. 36, 10.1145/3072959.3073640 (2017).
  * Bregler  _et al._ [1997] C. Bregler, M. Covell, and M. Slaney, Video rewrite: Driving visual speech with audio, in  _Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques_, SIGGRAPH ’97 (ACM Press/Addison-Wesley Publishing Co., USA, 1997) p. 353–360.
  * Locatello  _et al._ [2020] F. Locatello, B. Poole, G. Raetsch, B. Schölkopf, O. Bachem, and M. Tschannen, Weakly-supervised disentanglement without compromises, in  _Proceedings of the 37th International Conference on Machine Learning_, Proceedings of Machine Learning Research, Vol. 119, edited by H. D. III and A. Singh (PMLR, 2020) pp. 6348–6359.
  * Note [2] In previous work, we used focusing constraints [46] to maximize this dissimilarity and regularize blind deconvolution.
  * Wapenaar [2004] K. Wapenaar, Retrieving the elastodynamic Green’s function of an arbitrary inhomogeneous medium by cross correlation, Physical Review Letters 93, 254301 (2004).
  * Schuster and Zhou [2006] G. T. Schuster and M. Zhou, A theoretical overview of model-based and correlation-based redatuming methods, Geophysics 71, SI103 (2006).
  * Schuster [2009] G. Schuster,  _Seismic Interferometry_, Vol. 9780521871 (Cambridge University Press Cambridge, 2009) pp. 1–260.
  * Mulder [2005] W. A. Mulder, Rigorous redatuming, Geophysical Journal International 161, 401 (2005).
  * Wapenaar  _et al._ [2014] K. Wapenaar, J. Thorbecke, J. Van Der Neut, F. Broggini, E. Slob, and R. Snieder, Marchenko imaging, Geophysics 79, WA39 (2014).
  * Mordret  _et al._ [2014] A. Mordret, N. M. Shapiro, and S. Singh, Seismic noise-based time-lapse monitoring of the Valhall overburden, Geophysical Research Letters 41, 4945 (2014).
  * De Ridder  _et al._ [2014] S. A. De Ridder, B. L. Biondi, and R. G. Clapp, Time-lapse seismic noise correlation tomography at Valhall, Geophysical Research Letters 41, 6116 (2014).
  * van der Neut and Wapenaar [2016] J. van der Neut and K. Wapenaar, Adaptive overburden elimination with the multidimensional Marchenko equation, Geophysics 81, T265 (2016).
  * Mattheakis  _et al._ [2019] M. Mattheakis, P. Protopapas, D. Sondak, M. Di Giovanni, and E. Kaxiras, Physical Symmetries Embedded in Neural Networks, arXiv:1904.08991 [physics] (2019), arXiv:1904.08991 .
  * Cohen  _et al._ [2019] T. S. Cohen, M. Weiler, B. Kicanaoglu, and M. Welling, Gauge equivariant convolutional networks and the icosahedral CNN, 36th International Conference on Machine Learning, ICML 2019 2019-June, 2357 (2019), arXiv:1902.04615 .
  * Greydanus  _et al._ [2019] S. Greydanus, M. Dzamba, and J. Yosinski, Hamiltonian Neural Networks, arXiv (2019), 1906.01563 .
  * Doersch [2016] C. Doersch, Tutorial on variational autoencoders, arXiv preprint arXiv:1606.05908 (2016).
  * Note [3] We choose to use a deterministic autoencoding strategy for simplicity. It is possible to formalize the ideas in this paper using the variational autoencoding framework.
  * Klys  _et al._ [2018] J. Klys, J. Snell, and R. Zemel, Learning latent subspaces in variational autoencoders, arXiv preprint arXiv:1812.06190 (2018).
  * Dai and Wipf [2019] B. Dai and D. Wipf, Diagnosing and enhancing VAE models, 7th International Conference on Learning Representations, ICLR 2019 , 1 (2019), arXiv:1903.05789 .
  * Note [4] We provide Tensorflow-style [47] algorithms in the supplementary material that detail the implementation of SymAE. Additionally, following the double-blind review process, a link to a Github repository containing reproducible code will be made available in this footnote.
  * Note [5] We provided more architectural details in the supplementary material.
  * Zaheer  _et al._ [2017] M. Zaheer, S. Kottur, S. Ravanbhakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola, Deep sets, Advances in Neural Information Processing Systems , 3392 (2017), arXiv:1703.06114 .
  * Ilse  _et al._ [2018] M. Ilse, J. M. Tomczak, and M. Welling, Attention-based deep multiple instance learning, 35th International Conference on Machine Learning, ICML 2018 5, 3376 (2018), arXiv:1802.04712 .
  * Srivastava  _et al._ [2014] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, Dropout: a simple way to prevent neural networks from overfitting, The journal of machine learning research 15, 1929 (2014).
  * Wang and Manning [2013] S. Wang and C. Manning, Fast dropout training, in  _international conference on machine learning_ (PMLR, 2013) pp. 118–126.
  * Kingma  _et al._ [2015] D. P. Kingma, T. Salimans, and M. Welling, Variational dropout and the local reparameterization trick, Advances in neural information processing systems 28, 2575 (2015).
  * [44] A. Labach, H. Salehinejad, and S. Valaee, Survey of dropout methods for deep neural networks. arxiv 2019, arXiv preprint arXiv:1904.13310 .
  * Brougois  _et al._ [1990] A. Brougois, M. Bourget, P. Lailly, M. Poulet, P. Ricarte, and R. Versteeg, Marmousi, model and data, in  _EAEG workshop-practical aspects of seismic data inversion_ (European Association of Geoscientists & Engineers, 1990) pp. cp–108.
  * Bharadwaj  _et al._ [2019] P. Bharadwaj, L. Demanet, and A. Fournier, Focused blind deconvolution, IEEE Transactions on Signal Processing 67, 3168 (2019).
  * Abadi  _et al._ [2016] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mane, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viegas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng,  _TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems_, Tech. Rep. (2016) arXiv:1603.04467 .


# Rank-$k$ random graphs and finite type branching processes

Suman Chakraborty  Department of Mathematics and Computer Science, Eindhoven
University of Technology, Eindhoven, Netherlands<EMAIL_ADDRESS>,
Kjell Raaijmakers  Department of Mathematics and Computer Science, Eindhoven
University of Technology, Eindhoven, Netherlands<EMAIL_ADDRESS>and  Remco van der Hofstad  Department of Mathematics and Computer Science,
Eindhoven University of Technology, Eindhoven, Netherlands
<EMAIL_ADDRESS>
###### Abstract.

In this note, we investigate fundamental relations between exploration
processes in random graphs, and branching processes. We formulate a class of
models that we call rank-$k$ random graphs, and that are special in that their
neighborhood explorations can be obtained by a thinning of multi-type
branching processes. We show that any rank-2 random graph can be described in
terms of thinning of a 2-type branching process, while for higher rank, it is
not clear how many types are needed.

###### Key words and phrases:

Random graphs, branching processes, percolation

###### 2020 Mathematics Subject Classification:

Primary: 05C80, 60J80, 82B43.

##  1\. Introduction

Let $A=(a_{ij})_{i,j=1}^{n}$ be an $n\times n$ symmetric matrix with non-
negative entries, and $\ell_{n}>0$ a parameter. consider the random graph
$G_{n}(A)$ with vertex set $[n]:=\\{1,2,\ldots,n\\}$, in which the edge
$(i,j)$ is present with probability $1-\exp{\left(-\ell_{n}a_{ij}\right)}$
independent of all other edges for $1\leq i\leq j\leq n$. (We allow self-loops
in $G_{n}(A)$.) Let us now roughly state two well-known facts (the formal
statements are given later): Fact 1: The distribution of the neighborhoods of
any vertex in the random graph $G_{n}(A)$ can be coupled with a thinned _$n$
-type_ branching process associated with the matrix $A$. Fact 2: If
$\text{rank}(A)=1$, then the distribution of the neighborhoods of any vertex
in the random graph can be coupled to a thinned one-type branching process
associated with $A$.

This paper started with the following question motivated by the two facts
mentioned above: If $\text{rank}(A)=2$, can we then couple the distribution of
the neighborhoods of the vertices in the random graph $G_{n}(A)$ with some
thinned multi-type branching process of at most $2$ types? In this article, we
answer this question in the affirmative, and encouraged by this, we
investigate two related questions: (a) if $\text{rank}(A)=k$ for some $k\geq
3$, can we couple the neighborhood distribution of any vertex in $G_{n}(A)$
with some branching process where the number of types depends on $k$, but not
on $n$? (b) what conditions on $A$ (other than the rank of $A$) will ensure
that $G_{n}(A)$ can be coupled with some multi-type branching process having a
small number of types (independent of $n$)?

If $A$ is an adjacency matrix of some simple graph, and it has rank $k$, then
we show that one can couple the distribution of the neighborhoods of the
vertices in the random graph $G_{n}(A)$ with some thinned multi-type branching
process of at most $O(2^{k/2})$ types. Let us point out that the relationship
between the rank of adjacency matrices and other graph properties such as
chromatic number has been extensively studied (see van Nuffelen [15], Alon-
Seymour [2], Nisan-Wigderson[13] etc.). Our work sheds light on percolation of
finite graphs whose adjacency matrix has rank $k$ (see Remark 1.6 below), and
the type space of its branching process approximation.

Next, to put our contributions in context, we briefly recap some of the
relevant random graph models from the literature and provide formal statements
of the facts that we mentioned earlier.

###  1.1. Inhomogeneous random graphs and branching processes

The systematic study of random graphs began with the seminal article by Erdős
and Rényi [7], who studied uniformly chosen graphs $G(n,M)$ with $n$ labelled
vertices and $M$ edges. Slightly before that, Gilbert [8] introduced a closely
related model $G_{n}(p)$, in which each edge is present independently with
probability $p$. Since then, these models of random graphs have been studied
extensively, and have become a source of wonderful mathematical problems.

A feature of $G_{n}(p)$ and $G(n,M)$ is that they are homogeneous, that is, in
their definitions, all the vertices play an equivalent role. On the other
hand, most real-world networks contain some degree of inhomogeneity. Several
studies were devoted to introducing and analyzing models of inhomogeneous
random graphs. A natural generalization of the $G_{n}(p)$ model is
$G_{n}(\\{p_{ij}\\}_{i,j=1}^{n})$, which is a random graphs on the vertex set
$[n]:=\\{1,2,\ldots,n\\}$, in which the edges are chosen independently. Here,
for $1\leq i\leq j\leq n$ the probability of $ij$ being an edge is equal to
$p_{ij}$. As pointed out in Bollobás, Janson, and Riordan [5], it seems
difficult to obtain results for this class of random graphs without imposing
some conditions on the edge probabilities $p_{ij}$’s. Having that said, a
remarkable result on connectivity of such graphs was obtained by Alon [1]
(this model is also mentioned in Bollobás [4, Chapter 2]). It is easy to see
that the $G_{n}(A)$ model is equivalent to the model
$G_{n}(\\{p_{ij}\\}_{i,j=1}^{n})$ if we allow the $a_{ij}$ parameters to take
the value $\infty$.

Bollobás, Janson, and Riordan [5] introduced a highly general class of
inhomogeneous random graphs. In these random graphs the average degree is
$\Theta(1)$, and one of the important examples considered by them is
$p_{ij}=\kappa(i/n,j/n)/n$, where $\kappa$ is an appropriate function on
$[0,1]^{2}$. A common strategy in the analysis of a random graph where the
average degree is $\Theta(1)$ is to relate the neighborhood distribution of
the random graph to an appropriate branching process. Then the branching
process is analysed to extract relevant information about the random graph. To
see this connection, first let us recall that one can always associate a
branching process to a non-negative symmetric matrix $A$.

### Non-negative matrices and an associated branching process

For a given symmetric matrix $A=(a_{ij})\in\mathbb{R}_{+}^{n\times n}$ and
$\ell_{n}\in\mathbb{R}_{+}$, it is possible to naturally associate an $n$-type
branching process ${\sf BP}(i_{0})$ as follows:

  * $\rhd$

The root of the branching process is of type $i_{0}$.

  * $\rhd$

If a particle in the branching process has the type $i$, then it gives birth
to $\text{Poi}\left(\ell_{n}a_{ij}\right)$ many offspring of type $j$,
independently for $j\in[n]$.

If the root $i_{0}$ is chosen uniformly at random from $[n]$, then we denote
the branching process by ${\sf BP}(i_{0})$.

#### Multi-type branching processes, marks and graphs.

Below, we will call types in $[n]$ marks, and think of them corresponding to
vertices in the random graph $G_{n}(A)$. This allows us to distinguish the
marks from the types in the multi-type branching process. To relate the
branching process to the random graph, we always need to keep the mark
information, leading us to study marked multi-type branching processes.

In terms of these marked branching processes, the neighborhoods in $G_{n}(A)$
can then be obtained by a thinning of this branching process, in the sense
that vertices that have already appeared are thinned, together with all their
descendants. This relates the neighborhoods in $G_{n}(A)$ to an $n$-dependent
branching process. While this is very interesting, the fact that the number of
types in the multi-type branching process depends on $n$ makes it difficult to
use this relation. In this paper, we investigate when the multi-type branching
process with $n$ types can be replaced by a marked multi-type branching
process with a number of types that does not depend on $n$.

#### Marked multi-type branching process notation.

Let us fix some notation. We consistently write ${\sf BP}(i_{0})$ and ${\sf
BP}$ for the branching process with $n$ types, where the marks and types are
the same, and $i_{0}$ is the mark (or type) of the root. When relating these
processes to multi-type processes with fewer types, we write ${\sf
BP}_{k}(i_{0})$ and ${\sf BP}_{k}$ to denote that there are $k$ types in our
branching process. We further write ${\sf MBP}_{k}$ for the marked $k$-type
branching process, where we think of the marks as corresponding to the
vertices of the random graphs under investigation. We then use $\widetilde{\sf
MBP}_{k}(i_{0})$ to denote the thinned version of ${\sf MBP}_{k}(i_{0})$,
where vertices having repeated marks are removed with all their descendants.
Thinning is the content of the next section.

###  1.2. Thinned processes

The thinned process $\widetilde{{\sf BP}}(i_{0})$ is constructed from ${\sf
BP}(i_{0})$ in the following way. Starting from $i_{0}$, ${\sf BP}(i_{0})$ is
explored in a breadth-first manner, that is, all the members of a generation
are explored before moving on to the next generation, and, whenever a particle
is found whose type appeared before in the search, the particle is deleted
along with all its descendants. The resulting process is then denoted by
$\widetilde{{\sf BP}}(i_{0})$.

Now, let us consider the random graph $G_{n}(A)$. Then, for a vertex $i_{0}$,
its neighborhood shells $\mathcal{N}_{k}(i_{0})$ are defined as follows:

  * $\rhd$

$\mathcal{N}_{0}(i_{0})=i_{0}$.

  * $\rhd$

$\mathcal{N}_{k+1}(i_{0})=\left\\{j\in\left(\bigcup_{l=0}^{k}\mathcal{N}_{l}(i_{0})\right)^{c}:j\leftrightarrow\mathcal{N}_{k}(i_{0})\right\\}$.

Here, for two subsets of vertices $A$ and $B$, $A\leftrightarrow B$ means that
there is an edge between $A$ and $B$. Note that ${\sf BP}(i_{0})$ is a
branching process with $n$-types. Then the following proposition is the formal
statement of our Fact 1:

######  Proposition 1.1 (Graph exploration is thinned branching process).

Let $\widetilde{\mathcal{T}}_{k}$ be the set of the marks of the particles
that appeared in the $k$-th generation of the multi-type branching process
$\widetilde{{\sf BP}}(i_{0})$ with $n$ types. Then, the sequence of sets
$\\{\widetilde{\mathcal{T}}_{k}\\}_{k\geq 0}$ has the same distribution as
$\\{\mathcal{N}_{k}(i_{0})\\}_{k\geq 0}$.

With Proposition 1.1 in hand, we can focus our attention on marked branching
processes, where the thinning will allow us to return to the random graph
using Proposition 1.1. Thinning, in turn, requires marks, which thus naturally
lead us to study marked branching processes. The aim is to reduce the graph
exploration to a thinning of a marked $k$-type branching process with $k$ as
small as possible. To understand this branching process, in turn, we may
ignore the marks and focus only on the types. That reduces the complexity of
the branching process considerably.

The proof of Proposition 1.1 is a modification of an argument in [14], and we
postpone it to Section 6. Interestingly, when $\text{rank}{(A)}=1$, that is,
when $A=\mathbf{a}\mathbf{a}^{\prime}$ for some
$\mathbf{a}\in\mathbb{R}_{+}^{n\times 1}$, the branching process ${\sf
BP}(i_{0})$ has the same distribution as a one-type marked branching process,
denoted by ${\sf BP}_{1}(i_{0})$, where

  * $\rhd$

the root of the branching process ${\sf BP}_{1}(i_{0})$ receives the mark
$i_{0}$.

  * $\rhd$

a particle with mark $i$ gives birth to
$\text{Poi}\left(a_{i}\ell_{n}\sum_{i=1}^{n}a_{i}\right)$ many offspring.

  * $\rhd$

each offspring of a particle receives mark $j$ with probability
$\tfrac{a_{j}}{\sum_{i=1}^{n}a_{i}}$.

We can construct an $n$-type branching process from ${\sf BP}_{1}(i_{0})$ by
calling a particle with mark $i$ in ${\sf BP}_{1}(i_{0})$ to be of type $i$.
In line with our general notation, let us denote this by ${\sf
MBP}_{1}(i_{0})$, which we next show has the same distribution as ${\sf
BP}(i_{0})$:

######  Theorem 1.2 (Marked 1-type BP is $n$-type BP).

${\sf MBP}_{1}(i_{0})$ has the same distribution as ${\sf BP}(i_{0})$.

######  Remark 1.3 (General structure).

The equality in distribution in Theorem 1.2, where a marked multi-type
branching process with few types has the same law as an $n$-type branching
process, will be the recurring theme of this paper.

As the careful reader might already have noted, Propositions 1.1 and 1.2
provide us with a prescription to obtain the neighborhood shells of $G_{n}(A)$
from an $1$-type branching process when $A$ has rank $1$, by thinning of
vertices with the same marks. More precisely, one can consider the one-type
branching process ${\sf BP}_{1}(i_{0})$, then using Proposition 1.2, by
calling a mark $i$ particle to be of type $i$ we obtain a branching process
that has the same distribution as ${\sf BP}(i_{0})$. Finally, using the
thinning procedure described in Section 1.2, the neighborhood shells of
$G_{n}(A)$ can be constructed using Proposition 1.1.

###  1.3. Finite rank random graphs

We introduce a class of undirected inhomogeneous random graph models on the
vertex set $[n]:=\\{1,2,\ldots,n\\}$. These graphs may have self loops but may
_not_ have multiple edges. Let $\mathbb{R}_{+}$ denotes the set of all non-
negative real numbers, and $\mathbb{N}$ the set of all positive integers.

######  Definition 1.4 (Rank-$k$ random graphs).

Let $n\in\mathbb{N}$. For a given symmetric matrix
$A=(a_{ij})\in\mathbb{R}_{+}^{n\times n}$ and $\ell_{n}\in\mathbb{R}_{+}$,
$G_{n}(A)$ is called a rank-$k$ random graph on the vertex set $[n]$, if the
edges in $G_{n}(A)$ are present independently, and the probability that the
edge $(i,j)$ is present is given by

$p_{ij}=1-\exp{\left(-\ell_{n}a_{ij}\right)}\quad\forall(i,j)\in[n]\times[n],$
(1.1)

where the matrix $A$ has rank $k$.

######  Remark 1.5 (Global sparsity parameter).

In Definition 1.4, $\ell_{n}$ can be interpreted as the global sparsity
parameter for the model. Indeed, when $\ell_{n}$ is a positive number
independent of $n$, then the expected number of edges in $G_{n}(A)$ is of the
order $n^{2}$, and if $\ell_{n}\to 0$ as $n\to\infty$, then using Taylor’s
expansion it is easily seen that the expected number of edges is of order
$\ell_{n}n^{2}$.

######  Remark 1.6 (Bond percolation models as a special case).

Note that if the entries of $A$ are either $0$ or $1$, then $A$ becomes an
adjacency matrix of some graph $G$ on $n$ vertices, and (1.1) simply becomes
the bond percolation model on the ground graph $G$, that is, every edge in $G$
is kept independently with probability $1-\exp{\left(-\ell_{n}\right)}$.

######  Remark 1.7 (Graphs and marked branching processes).

Recall Proposition 1.1, which states that graph neighborhoods have the same
distribution as thinned marked branching processes. This relation allows us to
study rank-$k$ random graphs by only considering their marked multi-type
branching process approximation. Thus, from now on, we will mainly work with
branching processes, and only discuss random graphs when necessary.

#### Main results of this paper.

With Definition 1.4 in hand, we can now explain the main results of this
paper. We prove that ${\sf BP}(i_{0})$ has the same distribution as a specific
marked two-type branching process when $\text{rank}(A)=2$. When
$\text{rank}(A)=k>2$, on the other hand, the situation is not so clear and we
need to make further assumptions. When $A$ has random dot product structure,
${\sf BP}(i_{0})$ has the same distribution as a marked $k$-type branching
process. When, instead, $A$ has a Kotlov-Lovász structure, ${\sf BP}(i_{0})$
has the same distribution as a marked $f_{k}$-type branching process where
$f_{k}\leq O(2^{k/2})$.

#### Organisation of this paper.

In Section 2, we start by treating the illustrative example of the random dot-
product graphs, where we prove that it can be related to a $k$-type branching
process. In Remark 2.3, we also show that we can think of this model as a
rank-1 model on $kn$ vertices, where blocks of $k$ vertices are collapsed to
1. We use these resulte in Section 3 to show that any rank-2 random graph can
be related to a 2-type branching process through its spectral decomposition.
In Section 4, we describe the Kotlov-Lovázs setting, which can be seen as
rank-1 percolation on a graph having a finite number of vertex types. In
Section 6, we prove Proposition 1.1. In Section 5, we discuss a model related
to that of the random dot-product random graph in Section 2, where we allow
also for negative contributions. We close in Section 7 with discussion and
open problems.

##  2\. A special case: random dot-product setting

In this section we show that if $A$ is the sum of dot-products of vectors with
non-negative entries, then we can couple ${\sf BP}(i_{0})$ to a finite type
branching process. This means that we assume that $A$ admits a decomposition
of the form

$A=\mathbf{v}_{1}\mathbf{v}_{1}^{\prime}+\mathbf{v}_{2}\mathbf{v}_{2}^{\prime}+\ldots+\mathbf{v}_{k}\mathbf{v}_{k}^{\prime},$
(2.1)

for some column vectors
$\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{k}\in\mathbb{R}_{+}^{n}$. We
start with this example, since it nicely illustrates our main results, and
also because the rank-2 setting in the next section can be reduced to it.

######  Remark 2.1 (Relation to random dot product graphs).

If $A$ is of the form (2.1), then $G_{n}(A)$ is similar to the random dot-
product model [3] when $\ell_{n}\to 0$. Indeed, in the random dot-product
model, $p_{ij}=\ell_{n}a_{ij}$ with $A$ as in (2.1). By [10], our model is
asymptotically equivalent to the random dot-product random graph when

$\sum_{1\leq i<j\leq n}(\ell_{n}a_{ij})^{3}=o(1),$ (2.2)

which amounts to a mild sparsity condition.

Let $\mathbf{v}_{l}=(v_{l1},\ldots,v_{ln})^{\prime}$ for $l\in[n]$, and note
that $a_{ij}=\sum_{l=1}^{k}v_{li}v_{lj}$. Consider a $k$-type marked branching
process, where the set of types is $\\{t_{1},t_{2},\ldots,t_{k}\\}$, and the
set of marks is $[n]$. Then the marked $k$-type branching process is denoted
by ${\sf MBP}_{k}(i_{0})$, and is defined as follows:

  * $\rhd$

The root is marked with $i_{0}$.

  * $\rhd$

A particle with mark $i$ gives birth to
$\text{Poi}(\ell_{n}v_{li}\sum_{j=1}^{n}v_{lj})$ many particles of type
$t_{l}$ independently for $l=1,2,\ldots,k$.

  * $\rhd$

The $l$ type children of a particle independently receive a mark $j$ with
probability $\frac{v_{lj}}{\sum_{j=1}^{n}v_{lj}}$.

We can obtain an $n$-type branching process from ${\sf MBP}_{k}(i_{0})$ by
calling a particle with mark $j$ to be of type $j$. Let us denote this
$n$-type branching process by ${\sf BP}(i_{0})$. The next proposition shows
that it has the same distribution as ${\sf MBP}(i_{0})$:

######  Theorem 2.2 (Marked $k$-type BP is $n$-type BP).

${\sf BP}(i_{0})$ has the same distribution as ${\sf MBP}_{k}(i_{0})$.

Theorem 2.2 is another example of the general principle in Remark 1.3.

###### Proof.

The root of both the branching processes are marked by $i_{0}$, and therefore
they trivially have the same distribution. Let the distribution of ${\sf
BP}(i_{0})$ and ${\sf MBP}_{k}(i_{0})$ be equal up to generation $l$. Now we
show that, conditionally on generation $l$, the distributions of these
processes are equal up to generation $l+1$. Consider a particle in generation
$l$ in ${\sf MBP}_{k}(i_{0})$, and suppose that it has mark $i$, which, in
${\sf BP}(i_{0})$, means that the particle had mark $i$. Then the number of
children of this particle that are of type $t_{l}$ and receive the mark $j$
has distribution

$\text{Poi}(\ell_{n}v_{li}\sum_{j=1}^{n}v_{lj}\frac{v_{lj}}{\sum_{j=1}^{n}v_{lj}})=\text{Poi}(\ell_{n}v_{li}v_{lj})$
(2.3)

independently for $l\in[k]$. Therefore, the distribution of the total number
of children with mark $j$ has distribution

$\text{Poi}(\ell_{n}\sum_{l=1}^{k}v_{li}v_{lj})=\text{Poi}(\ell_{n}a_{ij}).$
(2.4)

Now, since the distribution of the marks are also independent, the particle
gives birth to $\text{Poi}(\ell_{n}a_{ij})$ many particle of mark $j$
independently for $j\in[n]$. Since in ${\sf MBP}_{k}(i_{0})$ a particle with
mark $j$ in ${\sf BP}(i_{0})$ is called type $j$, the distributions of ${\sf
MBP}_{k}(i_{0})$ and ${\sf BP}(i_{0})$ are equal. ∎

Let us close this section by relating our results, in the random graph
context, to collapsing of a rank-1 model on a larger vertex set:

######  Remark 2.3 (Rank-$k$ random graphs obtained through collapsing
rank-$1$ models).

Note that the structure of $A$ in (2) ensures that the rank of $A$ is at most
$k$. It is possible to also obtain $G_{n}(A)$ using $k$ independent rank-$1$
random graphs. Indeed, let
$\text{Explode}_{i}:=\\{i_{1},i_{2},\ldots,i_{k}\\}$ for $i\in[n]$. On the
vertex set $V_{j}:=\\{i_{j}\colon i\in[n]\\}$, we construct the following
random graph: for $h,l\in[n]$, there is an edge between $h_{j}$ and $l_{j}$
with probability $1-\exp(-\ell_{n}v_{jh}v_{jl})$ independently of each other
and everything else. We collapse the set $\text{Explode}_{h}$ to a single
vertex $h$, so that there is an edge between $h$ and $l$ precisely when there
was an edge between $\text{Explode}_{h}$ and $\text{Explode}_{l}$. From the
construction, it is easy to see that the probability that there is an edge
between $h$ and $l$ is equal to
$1-\exp(-\ell_{n}\sum_{j=1}^{k}v_{jh}v_{jl})=1-\mathrm{e}^{-\ell_{n}a_{ij}}$.

##  3\. Rank-2 branching processes

In this section we consider the case $\text{rank}(A)=2$, and show that has the
same distribution as a two-type branching process. Here, we make crucial use
of the results for the random dot-product case (in Case II below), to which we
reduce our proof. Using the spectral decomposition of $A$ we can write

$A=\lambda_{1}\mathbf{v}_{1}\mathbf{v}_{1}^{\prime}+\lambda_{2}\mathbf{v}_{2}\mathbf{v}_{2}^{\prime},$
(3.1)

where $\lambda_{1}\geq\lambda_{2}$ are the non-zero eigenvalues of $A$, and
$\mathbf{v}_{1}$ and $\mathbf{v}_{2}$ are the corresponding eigenvectors. By
the Perron-Frobenius theorem, all entries of $\mathbf{v}_{1}$ are non-
negative, and $\lambda_{1}\geq|\lambda_{2}|$. We distinguish two cases:

#### Case I of $\lambda_{2}<0$.

We start with a few observations. Firstly, we have that
$a_{ij}=\lambda_{1}v_{1i}v_{1j}+\lambda_{2}v_{2i}v_{2j}$ for $i,j\in[n]$, and
since $a_{ii}$ are non-negative for all $i\in[n]$, we get
$\lambda_{1}v_{1i}^{2}+\lambda_{2}v_{2i}^{2}\geq 0$. Now using
$\lambda_{2}<0$, we can write
$\lambda_{1}v_{1i}^{2}\geq|\lambda_{2}|v_{2i}^{2}$. Therefore,
$\sqrt{\lambda_{1}}v_{1i}\geq\sqrt{|\lambda_{2}|}|v_{2i}|$, which in turn
gives $\sqrt{\lambda_{1}}v_{1i}-\sqrt{|\lambda_{2}|}v_{2i}\geq 0$ and
$\sqrt{\lambda_{1}}v_{1i}+\sqrt{|\lambda_{2}|}v_{2i}\geq 0$ for all $i\in[n]$.

Denote
$s_{+}:=\tfrac{1}{\sqrt{2}}\sum_{i=1}^{n}(\sqrt{\lambda_{1}}v_{1i}+\sqrt{|\lambda_{2}|}v_{2i})$,
and
$s_{-}:=\tfrac{1}{\sqrt{2}}\sum_{i=1}^{n}(\sqrt{\lambda_{1}}v_{1i}-\sqrt{|\lambda_{2}|}v_{2i})$.

We define a marked two-type branching process with marks $[n]$, and types
$t_{1}$ and $t_{2}$. The process is denoted by ${\sf MBP}_{2}(i_{0})$, where

  * $\rhd$

the root is marked with $i_{0}$;

  * $\rhd$

a particle marked with $i$ gives birth to
$\text{Poi}\left(\tfrac{\ell_{n}}{\sqrt{2}}(\sqrt{\lambda_{1}}v_{1i}-\sqrt{|\lambda_{2}|}v_{2i})s_{+}\right)$
many children of type $t_{1}$, and
$\text{Poi}\left(\tfrac{\ell_{n}}{\sqrt{2}}(\sqrt{\lambda_{1}}v_{1i}+\sqrt{|\lambda_{2}}|v_{2i})s_{-}\right)$
many children of type $t_{2}$;

  * $\rhd$

the $t_{1}$ type children of a particle independently receive a mark $j$ with
probability
$\tfrac{1}{\sqrt{2}s_{+}}(\sqrt{\lambda_{1}}v_{1i}+\sqrt{|\lambda_{2}|}v_{2i})$,
and the $t_{2}$ type children of a particle independently receive a mark $j$
with probability
$\tfrac{1}{\sqrt{2}s_{-}}(\sqrt{\lambda_{1}}v_{1i}-\sqrt{|\lambda_{2}|}v_{2i})$.

The next proposition shows that ${\sf MBP}_{2}(i_{0})$ has the same
distribution as ${\sf BP}(i_{0})$:

######  Theorem 3.1 ($n$-type branching process is marked two-type branching
process).

${\sf MBP}_{2}(i_{0})$ has the same distribution as ${\sf BP}(i_{0})$.

###### Proof.

The root of both the branching processes are marked by $i_{0}$, and therefore
they trivially have the same distribution. Let the distribution of ${\sf
BP}(i_{0})$ and ${\sf MBP}_{2}(i_{0})$ be equal up to generation $l$. Now we
show that, conditionally on generation $l$, the distributions of these
processes are equal up to generation $l+1$. Consider a particle in generation
$l$ in ${\sf MBP}_{2}(i_{0})$, and suppose that the particle had mark $i$.
Then the number of children of this particle that are of type $t_{1}$, and
receive the mark $j$ is

$\text{Poi}\left(\tfrac{\ell_{n}}{\sqrt{2}}(\sqrt{\lambda_{1}}v_{1i}-\sqrt{|\lambda_{2}|}v_{2i})s_{+}\tfrac{1}{\sqrt{2}s_{+}}(\sqrt{\lambda_{1}}v_{1j}+\sqrt{|\lambda_{2}|}v_{2j})\right),$
(3.2)

and similarly the number of children of this particle that is of type $t_{2}$
and receives the mark $j$ is

$\text{Poi}\left(\tfrac{\ell_{n}}{\sqrt{2}}(\sqrt{\lambda_{1}}v_{1i}+\sqrt{|\lambda_{2}|}v_{2i})s_{-}\tfrac{1}{\sqrt{2}s_{-}}(\sqrt{\lambda_{1}}v_{1j}-\sqrt{|\lambda_{2}|}v_{2j})\right),$
(3.3)

Therefore, using (3.2) and (3.3), the distribution of the total number of
children with mark $j$ is

$\text{Poi}\left(\ell_{n}(\lambda_{1}v_{1i}v_{1j}-|\lambda_{2}|v_{2i}v_{2j})\right)=\text{Poi}\left(\ell_{n}(\lambda_{1}v_{1i}v_{1j}-|\lambda_{2}|v_{2i}v_{2j})\right)\stackrel{{\scriptstyle
d}}{{=}}\text{Poi}\left(\ell_{n}a_{ij}\right).$ (3.4)

Since the marks are also independent, the particle gives birth to
$\text{Poi}(\ell_{n}a_{ij})$ many particle of mark $j$ independently for
$j\in[n]$. Since in ${\sf MBP}_{2}(i_{0})$ a particle with mark $j$ has type
$j$ in ${\sf BP}(i_{0})$, the distribution of ${\sf MBP}_{2}(i_{0})$ and ${\sf
BP}(i_{0})$ are therefore equal. ∎

#### Case II: $\lambda_{2}>0$.

In this case, $A$ is positive definite, and our aim is to show that here the
problem boils down to a particular case of (2.1). More precisely, we prove the
following proposition that shows that this case can be reduced to the random
dot-product case, the proof of which involves basic linear algebra and plane
geometry:

######  Theorem 3.2 (Positive-definite matrices and random dot-products).

Let $A$ be a symmetric positive-definite $n\times n$ matrix with non-negative
entries and $\text{rank}{(A)}=2$. Then there exists two non-negative vectors
$\mathbf{w}_{1}$ and $\mathbf{w}_{2}$ such that

$A=\mathbf{w}_{1}\mathbf{w}^{\prime}_{1}+\mathbf{w}_{2}\mathbf{w}^{\prime}_{2}.$
(3.5)

Note that we can write
$a_{ij}=\lambda_{1}v_{1i}v_{1j}+\lambda_{2}v_{2i}v_{2j}$, for $i,j\in[n]$,
which in turn can be written as

$a_{ij}=\begin{pmatrix}\sqrt{\lambda_{1}}v_{1i},&\sqrt{\lambda_{2}}v_{2i}\end{pmatrix}\begin{pmatrix}\sqrt{\lambda_{1}}v_{1j}\\\
\sqrt{\lambda_{2}}v_{2j}\end{pmatrix}:=x_{i}^{\prime}x_{j},$ (3.6)

where $x_{i}=(x_{1i},x_{2i})^{\prime}$. We show that the model can be
transformed into a model for which $A$ admits a random dot-product
decomposition as in (2.1) with $k=2$.

First note that in (3.6) if we replace $x_{i}$ by $Wx_{i}$, where $W$ is an
orthogonal matrix then the model remains the same. Moreover, since $a_{ij}\geq
0$, we we have $x^{\prime}_{i}x_{j}\geq 0$ for all $i,j\in[n]$.

######  Lemma 3.3 (Rotating vectors to non-negative cone).

Let $x_{1},x_{2},\ldots,x_{n}\in\mathbb{R}^{2}$ be points on the plane such
that $x^{\prime}_{i}x_{j}\geq 0$ for all $i,j\in[n]$. Then there is an
orthogonal transformation such that the entries of $Wx_{i}$’s are non-negative
for all $i\in[n]$.

###### Proof.

Note that $x^{\prime}_{i}x_{j}\geq 0$ implies that
$0\leq\theta_{ij}\leq\frac{\pi}{2}$, where $\theta_{ij}$ is the angle between
the vectors $x_{i}$ and $x_{j}$. Now starting from $x_{1}$, we search for all
the next vector that are anticlockwise located within an angle $\pi/2$, and
call the vector with largest (anticlockwise) angle with $x_{1}$ to be $x_{L}$.
Similarly, we consider all the vectors within angle $\pi/2$, and call $x_{R}$
the vector with largest (clockwise) angle with $x_{1}$. Note that all vectors
lie in between these two vectors. Also the angle between $x_{L}$ and $x_{R}$
(anticlockwise from $x_{R}$) is less than or equal to $\pi/2$. Therefore ,we
can rotate all the points using a transformation $W$, say, that puts all
vectors $x_{1},x_{2},\ldots,x_{n}$ in the positive orthant, as required. ∎

With Lemma 3.3 in hand, we are ready to prove Theorem 3.2:

###### Proof of Theorem 3.2.

Using Lemma 3.3, and (3.6), we get that $a_{ij}=(Wx_{i})^{\prime}Wx_{j}$ for
all $i,j\in[n]$, and that the entries of $Wx_{i}$ are non-negative. Let
$Wx_{i}=(w_{1i},w_{2i})^{\prime}$, and
$\mathbf{w}_{i}=(w_{i1},w_{i2},\ldots,w_{i2})^{\prime}$, for $i=1,2$. It is
now easy to check that
$A=\mathbf{w}_{1}\mathbf{w}^{\prime}_{1}+\mathbf{w}_{2}\mathbf{w}^{\prime}_{2}$.
∎

##  4\. Rank $k$: Kotlov-Lovász model

In this section, we discuss a model that can be considered a rank-1
percolation on a finite graph. We start by describing the set up.

###  4.1. Adjacency matrix set up

In this section we start by considering the case when the entries of $A$ are
either $0$ or $1$, and all the diagonals are $0$. The results in this section
crucially rely on a beautiful theorem by Kotlov and Lovász [11], and, inspired
by this, we call $G_{n}(A)$ to be $k$-Kotlov-Lovász model when $A$ has $0-1$
entries with diagonals equal to zero and $\text{rank}(A)=k$.

We first recall a result from Kotlov and Lovász [11] that will be essential in
our analysis. A pair of non-adjacent vertices in a graph with the same
neighbors is called a pair of twin points. The following is the main result in
[11]:

######  Theorem 4.1 (Rank adjacency matrix of twin-free graph).

Let $G$ be a twin-free simple and undirected graph, and let $k$ the rank of
its adjacency matrix. Then

$\\#\text{vertices of }G\leq O(2^{k/2}):=f_{k}.$ (4.1)

Theorem 4.1 has the following corollary that will be useful for our purposes:

######  Corollary 4.2 (Partitioning of graph with rank-$k$ adjacency matrix).

Let $G$ be a simple and undirected graph on $n$ vertices, and let $k$ be the
rank of its adjacency matrix. Then the vertices of $G$ can be partitioned into
at most $f_{k}=O(2^{k/2})$ parts such that all the vertices in a class have
identical neighbors.

###### Proof.

The relation that a pair of vertices are twin is an equivalence relation.
Therefore we can always partition the vertex set into say, $M_{n}$ parts where
each class is an independent set, and all the vertices in a class have
identical neighbors. We can form a subgraph by taking one vertex from each of
these $M_{n}$ classes, and the adjacency matrix of that subgraph must have
rank less than or equal to $k$. Since the subgraph is twin-free as well, using
Theorem 4.1 we get that $M_{n}\leq f_{k}$. ∎

######  Remark 4.3 (Edge structure Kotlov-Lovász partition).

Note that if we consider the vertex partition as in Corollary 4.2, then
between each pairs of vertex classes either all edges are present or no edge
is present. We call this a _canonical partition_ , and label the classes by
$P_{1},P_{2},\ldots,P_{f_{k}}$. Moreover, we construct an $f_{k}\times f_{k}$
proxy adjacency matrix $\tilde{A}=(\tilde{a}_{ij})_{i,j=1}^{f_{k}}$ such that
$\tilde{a}_{ij}=1$ if all edges are present between vertex class $i$ and $j$,
and set $\tilde{a}_{ij}=0$ otherwise.

If we have a symmetric matrix $A$ with entries in {0,1} such that
$\text{rank}(A)\leq k$, then using the observations in Remark 4.3, we can
partition the rows of the matrix in at most $f_{k}$ classes. Let us label the
rows of $A$ by $[n]$, and denote the above-mentioned partition by
$P_{1},P_{2},\ldots,P_{f_{k}}$. Also let the number of rows in the class
$P_{i}$ be $n_{i}$ for $i\in[f_{k}]$. Define the function
$\mathcal{P}\colon[n]\to[f_{k}]$, such that $\mathcal{P}(i)=j$ if row $i$
belongs to class $P_{j}$. We now define an $f_{k}$-type marked branching
process ${\sf MBP}_{f_{k}}(i_{0})$ as follows:

  * $\rhd$

The root has mark $i_{0}$;

  * $\rhd$

If a particle has mark $i$, then it gives birth to
$\text{Poi}(n_{j}\ell_{n}\tilde{a}_{\mathcal{P}(i)j})$ many children of type
$j$ for $j\in[f_{k}]$;

  * $\rhd$

All the type $j$ children of a particle are marked with a number from $P_{j}$
independently and uniformly with probability $1/n_{j}$.

######  Theorem 4.4 (Marked $f_{k}$-type BP is $n$-type BP).

${\sf MBP}_{f_{k}}(i_{0})$ has the same distribution as ${\sf BP}(i_{0})$.

###  4.2. A rank-1 perturbation

Using a rank-$1$ perturbation, we can generalize the $k$-Kotlov-Lovász model
to the case where the entries of $A$ are not necessarily in $\\{0,1\\}$, as
follows: Suppose that $A$ is a $\\{0,1\\}$ matrix of rank $k$, and all the
diagonal entries are equal to zero. Then consider the perturbed version of
$A$, that is, the new matrix

$B:=\operatorname{diag}(a_{1},\ldots,a_{n})A\operatorname{diag}(a_{1},\ldots,a_{n}),$

where $\operatorname{diag}(a_{1},\ldots,a_{n})$ is a diagonal matrix with
entries $a_{1},a_{2},\ldots,a_{n}\geq 0$. Denote
$\mathbf{a}=(a_{1},\ldots,a_{n})^{\prime}$. Let us now define a marked
$f_{k}$-type branching process ${\sf MBP}_{f_{k}}(i_{0})$ as follows:

  * •

The root has mark $i_{0}$;

  * •

If a particle has mark $i$, then it gives birth to
$\text{Poi}\left(\ell_{n}a_{i}\tilde{a}_{\mathcal{P}(i)j}\sum_{i\in
P_{j}}a_{i}\right)$ many children of type $j$ for $j\in[f_{k}]$;

  * •

All type $j$ children of a particle receive a mark, say, $m$, from $P_{j}$
independently with probability $a_{m}/\sum_{i\in P_{j}}a_{i}$.

######  Theorem 4.5 (Marked $f_{k}$-type BP is $n$-type BP).

${\sf MBP}_{f_{k}}(i_{0})$ has the same distribution as ${\sf BP}(i_{0})$.

###### Proof of Theorem 4.4 & 4.5.

The proof follows from the construction of ${\sf MBP}_{f_{k}}(i_{0})$. We omit
the details. ∎

##  5\. Rank-$k$: a special case

In this section we consider a case that is similar to the case considered in
Section 2 but our assumptions are different. Firstly, we assume that $A$
admits the decomposition

$A=\mathbf{v}_{1}\mathbf{v}_{1}^{\prime}+\mathbf{v}_{2}\mathbf{v}_{2}^{\prime}+\ldots+\mathbf{v}_{k}\mathbf{v}_{k}^{\prime}.$
(5.1)

This is identical to the random dot-product case in (2.1), aside from the fact
that we no longer assume that the vectors $\mathbf{v}_{i}$ are non-negative.
Then we have $a_{ij}=\sum_{l=1}^{k}v_{li}v_{lj}$, and we assume that
$a_{ij}\geq 0$ for all $i,j\in[n]$. Contrary to the random dot-product setting
in Section 2, we show that we can relate the $n$-type branching process to a
multi-type branching process with $2^{k-1}$ types. We make the following
assumption:

#### Non-negative decomposition

We assume that (5.1) satisfies

$v_{1i}\geq\sum_{l=1}^{k}|v_{li}|\qquad\text{for all}\qquad i\in[n].$ (5.2)

With a slight abuse of notations, let us define the types

$t_{i}(l):=v_{1i}\pm v_{2i}\pm\cdots\pm v_{li},$ (5.3)

for $i\in[n]$, and where $l$ runs over $2^{k-1}$ possible distinct
configurations of $+$’s and $-$’s. The condition (5.2) ensures that
$t_{i}(l)\geq 0$ for all $i$ and $l$. Now we are well equipped to define a
$2^{k-1}$-type marked branching process ${\sf MBP}_{2^{k-1}}(i_{0})$ as
follows:

  * •

The root is marked with $i_{0}$;

  * •

A particle with mark $i$ gives birth to
$\text{Poi}(\ell_{n}t_{i}(l)\sum_{j=1}^{k}t_{i}(l))$ many particles of type
$t_{l}$ independently for $l\in[2^{k-1}]$;

  * •

The $l$ type children of a particle independently receive a mark $j\in[n]$
with probability $\frac{t_{j}(l)}{\sum_{j=1}^{n}t_{j}(l)}$.

We again see that ${\sf MBP}_{2^{k-1}}(i_{0})$ has the same law as ${\sf
BP}(i_{0})$:

######  Theorem 5.1 (Marked $2^{k-1}$-type BP is $n$-type BP).

${\sf MBP}_{2^{k-1}}(i_{0})$ has the same distribution as ${\sf BP}(i_{0})$.

###### Proof.

Consider a particle in ${\sf MBP}_{2^{k-1}}(i_{0})$, and suppose that it is of
type $i$, that is, in ${\sf BP}(i_{0})$ the particle had mark $i$. Then the
number of children of this particle that are of type $t_{l}$, and receive the
mark $j$, is
$\text{Poi}\left(\tfrac{1}{2^{k-1}}\ell_{n}t_{i}(l)\sum_{i=1}^{2^{k-1}}t_{i}(l)\frac{t_{j}(l)}{\sum_{j=1}^{n}t_{j}(l)}\right)$
disatributed, that is a $\text{Poi}(\ell_{n}t_{i}(l)t_{j}(l))$ distribution
independently for $l\in[k]$. Therefore, the distribution of the total number
of children with mark $j$ is a
$\text{Poi}\left(\tfrac{1}{2^{k-1}}\ell_{n}\sum_{l=1}^{2^{k-1}}t_{i}(l)t_{j}(l)\right)$.
A simple calculation, that we state in Lemma 5.2, shows that this is equal to
a $\text{Poi}(\ell_{n}a_{ij})$ distribution (since
$\sum_{l=1}^{2^{k-1}}t_{i}(l)t_{j}(l)=\sum_{l=1}^{k}v_{li}v_{lj}$). Now, since
the distribution of the marks are also independent, the particle gives birth
to $\text{Poi}(\ell_{n}a_{ij})$ many particle of mark $j$ independently for
$j\in[n]$. The rest of the proof follows from an induction argument similar to
the proof of Theorem 2.2. ∎

Let us now state the technical lemma that we have used in the proof of Theorem
5.1. It can be proved using induction and we omit further details.

######  Lemma 5.2 (Alternating sums).

For any two vectors $\mathbf{a},\mathbf{b}\in\mathbb{R}^{k}$, $k\geq 1$ let

$\displaystyle S_{k}(\mathbf{a},\mathbf{b})$
$\displaystyle:=(a_{1}+a_{2}+\cdots+a_{k})(b_{1}+b_{2}+\cdots+b_{k})+(a_{1}-a_{2}+\cdots+a_{k})(b_{1}-b_{2}+\cdots+b_{k})$
$\displaystyle+\cdots+(a_{1}-a_{2}-\cdots-a_{k})(b_{1}-b_{2}-\cdots-b_{k}),$

where the sum is over all $\pm$ coefficients of
$(a_{2},b_{2}),\ldots,(a_{k},b_{k})$. Then

$S_{k}(\mathbf{a},\mathbf{b})=2^{k-1}(a_{1}b_{1}+\cdots+a_{k}b_{k}).$

##  6\. Random graphs as thinned branching processes: Proof of Proposition 1.1

Note that $\widetilde{{\sf BP}}(i_{0})$ has type-$i$ root, and
$\mathcal{N}_{0}(i_{0})=i_{0}$. Therefore, the proposition is true for $k=0$.
Now suppose that the proposition is true up to generation $k$. Pick a particle
from generation $k$ in $\widetilde{{\sf BP}}(i_{0})$, and suppose the particle
is of type $i$. Then it has at least one child of type $j$ with probability
$1-\exp{\left(-\ell_{n}a_{ij}\right)}$ independently for all $j\in[n]$. If
$j$-type children already appeared in $\widetilde{{\sf BP}}(i_{0})$ within
generation $k$ then we delete all the $j$ type children from generation $k+1$.
If $j$-type children have not appeared in $\widetilde{{\sf BP}}(i_{0})$ within
generation $k$, and we get multiple $j$-type children then we just keep one of
them. On the other hand, in the graph we consider the vertex $i$ in
$\mathcal{N}_{k}(i_{0})$. Then it has a neighbor $j$ in
$\mathcal{N}_{k+1}(i_{0})$ with probability
$1-\exp{\left(-\ell_{n}a_{ij}\right)}$ independently for each $j$ only if the
vertex $j$ has not appeared in $\cup_{\ell=0}^{k}\mathcal{N}_{\ell}(i_{0})$.
This proves that the proposition is true up to generation $k+1$. Therefore the
proposition is proved using induction. ∎

##  7\. Conclusion, discussion and open problems

In this section, we discuss our results and state some further open problems.

#### Linking two fundamental notions

The rank of a matrix is a fundamental property of that matrix. In turn, the
branching process limit of a random graph is a fundamental property of the
random graph. Our paper nicely links these two fundamental notions, in a
quantitative manner. One can expect that such a relation has deep
consequences, and below we discuss a few of them.

#### Local limits and giants of dot-product random graphs

Bollobás, Janson and Riordan [5] prove general convergence results of local
neighborhoods in inhomogeneous random graphs to branching processes, and, as a
result of this, identify when there is a giant (a component of size order of
$n$), and if so, how large it is. Consider the model in (2.1) for $k=2$. Then
the largest eigenvalue of $A$ is

$\lambda_{1}(A):=\tfrac{1}{2}(\sum_{i=1}^{n}v_{1i}^{2}+\sum_{i=1}^{n}v_{2i}^{2})+\tfrac{1}{2}\sqrt{(\sum_{i=1}^{n}v_{1i}^{2}-\sum_{i=1}^{n}v_{2i}^{2})^{2}+2(\sum_{i=1}^{n}v_{1i}v_{2i})^{2}}.$
(7.1)

When (2.2) is satisfied, the results in [5, 10], give that if
$\ell_{n}>1/\lambda_{1}(A)$, there is a giant in $G_{n}(A)$ with high
probability, assuming that the empirical distributions of
$(v_{1i},v_{2i})_{i\in[n]}$ are sufficiently regular. Our result describes the
local neighborhoods of $G_{n}(A)$ in terms of a $2$-type marked branching
process (as opposed to a branching process with arbitrarily many types in
[5]).

#### Coupling beyond the sparse regime

The above shows that our results have important consequences in the sparse
setting. However, the beauty of the result is that the connection to finite-
type branching processes holds irrespective of the edge density. One can
imagine that stochastic domination by an explicit finite-type branching
process is useful far beyond the sparse setting. For example, for the
connectivity of random graphs, the typical threshold occurs in general
inhomogeneous random graphs when the average degree is of order $\log{n}$, see
[6] and the references therein.

#### Critical behavior of rank-$k$ random graphs

The general structure in Bollobás, Janson and Riordan [5] allows one to
identify exactly when there is a giant or not, as well as several other
properties of the random graphs involved. However, this set-up is likely not
suitable to decide what the precise critical behavior is. Already in the
rank-1 case, there are several universality classes (see [9, Chapter 4] and
the reference therein for an extensive overview), and one can expect that this
only becomes more tricky when the rank is higher. For example, in the dot-
product setting, is the heaviest weight deciding the universality class, or is
there some collaboration between the various weights? Recall (7.1), and note
that when $v_{1i}$’s and $v_{1i}$’ are i.i.d. samples from random variables
$V_{1}$ and $V_{2}$ with finite second moment, then $\lambda_{1}(A)/n$
converges to
$\tfrac{1}{2}(\mathbb{E}(V_{1}^{2})+\mathbb{E}(V_{2}^{2}))+\tfrac{1}{2}\sqrt{(\mathbb{E}(V_{1}^{2})-\mathbb{E}(V_{2}^{2}))^{2}+2(\mathbb{E}(V_{1}V_{2}))^{2}}$.
In the light of [9, Chapter 4], it appears that the moments of $V_{1}$ and
$V_{2}$ will play a role to describe the critical behavior of $G_{n}(A)$. See
[12] for a nice description how critical multi-type branching processes can be
explored in terms of 1-type branching processes. Such an approach has the
potential to be extended to the random graph setting when the description is
in terms of multi-type branching processes with finitely many types
independent of $n$. This may give a starting point for the analysis of the
critical behavior of rank-$k$ random graphs.

#### Ranks of random graphs and branching processes: optimality

Obviously, our results are not sharp for rank-$k$ random graphs when $k\geq
3$. It is unclear to us whether the rank really determines how many types the
multi-type branching process description needs, and we see several different
cases: For the random dot-product setting, $k$ suffices, for the Kotlov-Lovász
setting, $f_{k}=O(2^{k/2})$ suffices, while in the setting in (5.1), we need
$2^{k-1}$ types. It will be interesting to see in more detail what the minimal
number is, and how this depends on the precise structure of $A$.

#### Acknowledgement.

The work of SC and RvdH is supported in part by the Netherlands Organisation
for Scientific Research (NWO) through the Gravitation Networks grant
024.002.003.

## References

  * [1] Noga Alon.  A note on network reliability.  In Discrete probability and algorithms (Minneapolis, MN, 1993), volume 72 of IMA Vol. Math. Appl., pages 11–14. Springer, New York, 1995.
  * [2] Noga Alon and Paul D Seymour.  A counterexample to the rank-coloring conjecture.  Journal of Graph Theory, 13(4):523–525, 1989.
  * [3] Avanti Athreya, Donniell E. Fishkind, Minh Tang, Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, Keith Levin, Vince Lyzinski, Yichen Qin, and Daniel L. Sussman.  Statistical inference on random dot product graphs: a survey.  J. Mach. Learn. Res., 18:Paper No. 226, 92, 2017.
  * [4] Béla Bollobás.  Random graphs.  In Modern graph theory, pages 215–252. Springer, 1998.
  * [5] Béla Bollobás, Svante Janson, and Oliver Riordan.  The phase transition in inhomogeneous random graphs.  Random Structures Algorithms, 31(1):3–122, 2007.
  * [6] Luc Devroye and Nicolas Fraiman.  Connectivity of inhomogeneous random graphs.  Random Structures Algorithms, 45(3):408–420, (2014).
  * [7] Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
  * [8] E. N. Gilbert.  Random graphs.  Ann. Math. Statist., 30:1141–1144, 1959.
  * [9] R. van der Hofstad.  Stochastic processes on random graphs.  2023+.  In preparation, see
http://www.win.tue.nl/$\sim$rhofstad/SaintFlour_SPoRG.pdf.

  * [10] S. Janson.  Asymptotic equivalence and contiguity of some random graphs.  Random Structures Algorithms, 36(1):26–45, 2010.
  * [11] Andrew Kotlov and László Lovász.  The rank and size of graphs.  J. Graph Theory, 23(2):185–189, 1996.
  * [12] G. Miermont.  Invariance principles for spatial multitype Galton-Watson trees.  Ann. Inst. Henri Poincaré Probab. Stat., 44(6):1128–1161, (2008).
  * [13] Noam Nisan and Avi Wigderson.  On rank vs. communication complexity.  Combinatorica, 15(4):557–565, 1995.
  * [14] Ilkka Norros and Hannu Reittu.  On a conditionally Poissonian graph process.  Adv. in Appl. Probab., 38(1):59–75, 2006.
  * [15] Cyriel van Nuffelen.  A bound for the chromatic number of a graph.  The American Mathematical Monthly, 83(4):265–266, 1976.