# A Random Graph Growth Model

Michael Farber  Queen Mary, University of London  Alexander Gnedin and Wajid
Mannan  Queen Mary, University of London

###### Abstract

A growing random graph is constructed by successively sampling without
replacement an element from the pool of virtual vertices and edges. At start
of the process the pool contains $N$ virtual vertices and no edges. Each time
a vertex is sampled and occupied, the edges linking the vertex to previously
occupied vertices are added to the pool of virtual elements. We focus on the
edge-counting at times when the graph has $n\leq N$ occupied vertices. Two
different Poisson limits are identified for $n\asymp N^{1/3}$ and $N-n\asymp
1$. For the bulk of the process, when $n\asymp N$, the scaled number of edges
is shown to fluctuate about a deterministic curve, with fluctuations being of
the order of $N^{3/2}$ and approximable by a Gaussian bridge.

##  1 The graph model

We consider a random graph growing according to simple rules. The idea is to
successively sample from a variable pool of virtual vertices and edges. The
sampled elements, called in the sequel occupied, comprise a graph. Each time a
new vertex is sampled the pool is topped up with virtual edges missing in the
current graph. The method creates a bias in the probabilities of edges in a
way that the vertices sampled earlier are more likely to get linked. Moreover,
the probabilities of new edges depend on the content of the pool. These
features distinguish our process from numerous random graph models studied in
the literature [2, 5, 6, 11, 12, 14]. Our interest to the new model is
motivated by the analogous construction of random simplicial complexes but we
leave this extension for future work and in this note only focus on the edge
counting.

In more detail, the process evolves as follows. At start there is a pool of
$N$ virtual vertices and no edges. At each subsequent step there is some
number $n\leq N$ of occupied vertices, which are linked by some number
$k\leq{n\choose 2}$ of occupied edges. The occupied vertices and edges
comprise a graph with ${n\choose 2}-k$ edges remaining virtual. The graph is
grown by selecting an element uniformly at random from the pool of
$N-n+{n\choose 2}-k$ virtual vertices and edges and changing status of the
sampled element from virtual to occupied. Eventually the complete graph on $N$
vertices is built.

We shall focus on the edge-counting in discrete time, while identifying the
whole hours $1,\ldots,N$ with the number of occupied vertices. The vertices
will be labelled $1,\ldots,N$ as they get sampled. The edges will be directed
as $i\leftarrow j$ for $1\leq i<j\leq N$. We define $G_{n}$ to be the graph on
$[n]:=\\{1,\dots,n\\}$ emerging as the $n$th vertex becomes occupied, when
also $n-1$ virtual edges $i\leftarrow n$ are added to the pool. Thus at time
$n$ the pool is comprised of some number of unoccupied edges between vertices
in $G_{n}$, and of $N-n$ virtual vertices. The events of occupying the edges
are viewed as intermediate steps that occur between the whole hours when the
clock rings and vertices get occupied. For the main part of the paper we shall
consider the process up to the time $N$, when the last vertex gets occupied
and the pool is left with some number of virtual edges.

For the late stages of the process, when a few virtual vertices remain, it is
more insightful to switch to a time reversal and vertex-counting.

The analytic tractability of the model relies upon exchangeability intrinsic
to the sampling process. Indeed, whenever the pool at some stage has $r$
elements, their all $r!$ relative orders in which the elements become occupied
are equally likely. Let $I_{n}(i,j)$ denote the indicator of the event that
$G_{n}$ has (occupied) edge $i\leftarrow j$, and let

$X_{n}=\sum_{\\{(i,j):~{}1\leq i<j<n\\}}I_{n}(i,j),~{}~{}~{}n=1,\dots,N$ (1)

be the number of edges in $G_{n}$. We have, by the exchangeability,

${\mathbb{P}}[I_{n}(i,j)=1]=\frac{n-j}{N-j+1},~{}~{}~{}1\leq i<j\leq n.$ (2)

The bias in edge probabilities is seen from this formula. For instance, at
times $n$ close to $N/2$ the edge $1\leftarrow 2$ is occupied with probability
about $1/2$, while the edge $1\leftarrow n$ is occupied with probability $0$.

The expected value of $X_{n}$ follows straight from (2):

$\displaystyle\mu_{n}:={\mathbb{E}}[X_{n}]$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1}\frac{(j-1)(n-j)}{N-j+1}$ (3) $\displaystyle=$
$\displaystyle{n\choose
2}+(n-1)(N-n)-N(N-n+1)\sum_{j=1}^{n-1}\frac{1}{N-j+1}\,.$

In what follows we shall work out formulas and asymptotics for the variance,
the latter being remarkably explicit. Our central results will capture more
delicate features of the edge-counting process $(X_{n})$, for $N$ large. These
include Poisson approximations for times close to the start and the end of the
process, a fluid limit and Gaussian fluctuations for the bulk of the process
suitably scaled. The following diagram illustrates the time scales in the
succession of ${N\choose 2}+N$ occupancy events that occur as the trivial
graph grows to the complete graph on $N$ vertices, with $\circ$ marking the
vertex occupancy and $\bullet$ the edge occupancy events

$\underbrace{\circ\cdots\circ\bullet\circ\cdots\circ}_{N^{1/3}-{\rm
scale,\,\bullet\,Poisson}}\underbrace{\bullet\bullet\bullet\bullet\cdots\bullet\bullet\bullet\bullet\circ\bullet\bullet\cdots\bullet\bullet\circ\bullet\bullet\bullet\cdots\bullet\bullet}_{N-{\rm
scale,\,\bullet\,Gaussian}}\underbrace{\circ\bullet\cdots\bullet\circ\bullet\cdots\bullet}_{N\log
N-{\rm scale,\,\circ\,Poisson}}$

In the first two regions the scaling refers to the whole hours marked $\circ$.
In the third region $\circ$ are rare, occuring at intervals of the order of
$N\log N$.

Notation: we shall denote $\stackrel{{\scriptstyle d}}{{\to}}$ the convergence
in distribution, $\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}$ the
convergence in probability, and $\Rightarrow$ the weak convergence in the
Skorokhod space of cadlag processes [1].

##  2 A dynamic urn model

The edge-counting can be thought of in terms of the following urn process. The
urn contains white and black balls. A ball is sampled uniformly at random and
its colour noticed. If it was a black ball, the ball is removed without
replacement. If it was the $n$th sampled white ball, it is removed and $n-1$
new black balls are replaced to the urn. Assuming that initially the urn had
$N$ white balls and zero black, $X_{n}$ can be identified with the number of
black balls removed from the urn before $n$ white balls are sampled.

It is clear from this representation that $(X_{n})$ is a Markov chain. Let

$\Delta X_{n}:=X_{n}-X_{n-1}$

denote the increment, where $X_{0}=0$. Given $X_{n}=k$, the increment $\Delta
X_{n+1}$ is the number of black balls sampled without replacement before a
white ball gets drawn from an urn containing ${n\choose 2}-k$ black and $N-n$
white balls. This number has a negative hypergeometric distribution

${\mathbb{P}}[\Delta X_{n+1}=\ell\,|\,X_{n}=k]=\frac{{M-\ell-1\choose
K-1}}{{M\choose K}},~{}~{}~{}~{}0\leq\ell\leq M-K,$ (4)

with moments

$\displaystyle{\mathbb{E}}[\Delta X_{n+1}\,|\,X_{n}=k]$ $\displaystyle=$
$\displaystyle\frac{M-K}{K+1},$ (5) $\displaystyle{\rm Var\,}[\Delta
X_{n+1}\,|\,X_{n}=k]$ $\displaystyle=$
$\displaystyle\frac{(M+1)(M-K)K}{(K+1)^{2}(K+2)},$ (6)

where for shorthand

$M=N-n+{n\choose 2}-k,~{}~{}~{}K=N-n.$

We note a particularly simple formula for the second difference

${\mathbb{E}}[\Delta_{n+1}-\Delta_{n}]=\mu_{n+1}-2\mu_{n}+\mu_{n-1}=\frac{n-1}{N-n+1}.$
(7)

This can be neatly explained in terms of a decomposition of the edge-counting
process. For $m<n$, the pool at time $n$ contains some of the aged virtual
edges missing in the graph $G_{m}$ and some of the recent virtual edges added
to the pool between times $m+1$ and $n$. The difference $X_{n}-X_{m}$
decomposes accordingly as

$X_{n}-X_{m}=A_{m,n}+R_{m,n}$ (8)

where $A_{m,n}$ is the number of aged edges occupied by time $n$. The
increments

$A_{m,m+1},A_{m,m+2}-A_{m,m+1},\ldots,A_{m,n}-A_{m,n-1}$

are exchangeable, with equal mean values. In particular, for $m=n-1$, the mean
contribution to $\Delta_{n}$ and $\Delta_{n+1}$ of the aged edges is the same,
so the increase in (7) occurs due to some of $n-1$ edges added to the pool at
time $n$ and occupied by time $n+1$.

##  3 Two martingales

Let $({\cal F}_{n}^{X})$ be the natural filtration associated with $(X_{n})$.
By the Markov property, (5) is equivalent to

${\mathbb{E}}\left[\Delta X_{n+1}|{\cal F}_{n}^{X}\right]=\frac{{n\choose
2}-X_{n}}{N-n+1}.$ (9)

The predictable process

$C_{n}:=\sum_{j=1}^{n-1}\frac{{j\choose 2}-X_{j}}{N-j+1}$ (10)

is the compensator involved in the Doob-Meyer decomposition of $(X_{n})$, i.e.
the sequence $(X_{n}-C_{n})$ is a martingale.

Taking expectation in (9) yields a recursion for the mean

$\mu_{n+1}-\mu_{n}=\frac{{n\choose 2}-\mu_{n}}{N-n+1},$ (11)

which could have been concluded directly from (3). Introduce the centered
process

$X_{n}^{\circ}:=X_{n}-\mu_{n}.$

Subtracting (11) from (9) we arrive at

${\mathbb{E}}\left[\frac{X_{n+1}^{\circ}}{N-n}{\bigg{|}}{\cal
F}_{n}^{X}\right]=\frac{X_{n}^{\circ}}{N-n+1},$ (12)

which says that the sequence $(N-n+1)^{-1}X_{n}^{\circ},~{}n=1,\ldots,N,$ is
also a martingale.

##  4 Asymptotics of the moments

To approximate the mean (3) for large $N$ consider the function

$\varphi(t):=2\int_{0}^{t}\frac{s(t-s)}{1-s}\,{\rm d}s=2(1-t)L+2t-t^{2},$

where and henceforth

$L:=\log(1-t).$

A counterpart of (11) is the differential equation

$\varphi^{\prime}(t)=\frac{t^{2}-\varphi(t)}{1-t},~{}~{}~{}~{}~{}\varphi(0)=0.$

From the second expression in (3) one readily derives the estimate

$\max_{1\leq n\leq
N}\left|\frac{2}{N^{2}}\,\,\mu_{n}-\varphi\left(\frac{n}{N}\right)\right|=O\left(\frac{1}{N}\log\left(\frac{N}{N-n+1}\right)\right).$
(13)

whichis uniform in $n$. This entails the convergence rate $O(N^{-1})$ for
$n/N$ bounded away from $1$, that is in the range $n/N<1-\delta$ for any given
$\delta\in(0,1)$.

We turn next to the variance

$\sigma_{n}^{2}:={\rm Var}[X_{n}].$

To derive a recursion, condition on ${\cal F}_{n}^{X}$ to decompose
$\sigma_{n+1}^{2}$ as

$\displaystyle\sigma_{n+1}^{2}$ $\displaystyle=$
$\displaystyle{\mathbb{E}}\\{{\rm Var}[X_{n+1}|{\cal F}_{n}^{X}]\\}+{\rm
Var}\\{{\mathbb{E}}[X_{n+1}|{\cal F}_{n}^{X}]\\}$ $\displaystyle=$
$\displaystyle{\mathbb{E}}\\{{\rm Var}[\Delta X_{n+1}|{\cal
F}_{n}^{X}]\\}+{\rm Var}\left[\frac{N-n}{N-n+1}X_{n}\right],$

where the second expression follows from (12). Now, from (6)

$\displaystyle{\mathbb{E}}\\{{\rm Var}[\Delta X_{n+1}|{\cal F}_{n}^{X}]\\}=$
$\displaystyle\frac{N-n}{(N-n+1)^{2}(N-n+2)}$
$\displaystyle\\!\\!\\!\\!\\!\\!\left[\sigma_{n}^{2}+\left({n\choose
2}-\mu_{n}\right)\left(N-n+1+{n\choose 2}-\mu_{n}\right)\right],$

and the second term is

${\rm
Var}\left[\frac{N-n}{N-n+1}X_{n}\right]=\left(\frac{N-n}{N-n+1}\right)^{2}\sigma_{n}^{2}.$

Adding up and appealing to (11) with a bit of algebra we arrive at the
recursion

$\sigma_{n+1}^{2}-\sigma_{n}^{2}=\frac{(N-n)(\mu_{n+1}-\mu_{n})(\mu_{n+1}-\mu_{n}+1)-2\sigma_{n}^{2}}{N-n+2}.$
(14)

Solving (14) gives

$\sigma_{n}^{2}=(N-n+1)(N-n+2)\sum_{j=1}^{n-1}\frac{(\mu_{j+1}-\mu_{j})(\mu_{j+1}-\mu_{j}+1)}{(N-j+1)(N-j+2)}.$
(15)

From (3) the difference of the mean values is

$\mu_{n+1}-\mu_{n}=\frac{-(n-1)(N-n)}{N-n+1}+N\sum_{i=1}^{n-1}\frac{1}{N-i+1}.$
(16)

Approximating the sum in (16) by an integral gives an upper bound

$\mu_{n+1}-\mu_{n}<N\log\left(\frac{N}{N-n+1}\right),$

which substituted in (15) readily gives $\sigma_{n}^{2}=O(N^{3})$ uniformly in
$n$. The latter does not capture the decay of the variance for $n/N$ close to
$1$. With some more work for the upper half of the range we obtained the
estimate

$\sigma_{n}^{2}<5(N-n+2)N^{2}\log^{2}\left(\frac{N}{N-n+1}\right)~{}~{}{\rm
for~{}}~{}n>N/2,$ (17)

which shows the right order of the variance (though the constant $5$ is not
optimal).

A continuous counterpart of (14) is the differential equation

$\psi^{\prime}(t)=-\frac{2\,\psi(t)}{1-t}+\frac{1}{4}(\varphi^{\prime}(t))^{2},~{}~{}~{}\psi(0)=0,$

whose solution is

$\psi(t)=(1-t)\\{(2-t)L^{2}+2(3-t)L+t(6-t)\\}.$ (18)

This approximates the variance in the sense that

$\max_{1\leq n\leq N}|N^{-3}\sigma_{n}^{2}-\psi(n/N)|\to
0,{\rm~{}~{}~{}as~{}}N\to\infty,$

where the approximation error is $O(N^{-1})$ for $n/N<1-\delta$. We have
$\psi(1)=0$ which neatly agrees with the $n=N$ instance of (17).

We note that the analogue of (15) is the integral representation

$\psi(t)=(1-t)^{2}\int_{0}^{t}\left(\frac{s+\log(1-s)}{1-s}\right)^{2}{\rm
d}s.$ (19)

Figure 1: $\varphi$ and $\psi$. Observe different scales!

It is instructive to arrive at the asymptotic variance (18) in a more direct
way, in order to emphasise the dependence among the edges in $G_{n}$. Consider
$a\leftarrow i$ and $b\leftarrow j$ with $i<j<n$. The edge $a\leftarrow i$ is
not occupied at time $n$ with probability $(N-n+1)/(N-i+1)$. Given this event,
the probability that the edge $b\leftarrow j$ is not occupied at time $n$
equals $(N-n+2)/(N-j+2)$, which is lower than the unconditional probability.
With this in mind, the second moment of the number of virtual edges ${n\choose
2}-X_{n}$ is given by

$\displaystyle{\mathbb{E}}\left[{n\choose 2}-X_{n}\right]^{2}$
$\displaystyle=$ $\displaystyle{n\choose 2}-\mu_{n}$ (20) $\displaystyle+$
$\displaystyle(N-n+1)(N-n+2)\sum_{i=1}^{n}\frac{(i-1)(i-2)}{(N-i+1)(N-i+2)}$
$\displaystyle+$ $\displaystyle 2(N-n+1)(N-n+2)\sum_{1\leq i<j\leq
n}\frac{(i-1)(j-1)}{(N-i+1)(N-j+2)}$

and subtracting the squared mean

$\displaystyle\left({\mathbb{E}}\left[{n\choose 2}-X_{n}\right]\right)^{2}$
$\displaystyle=$
$\displaystyle(N-n+1)^{2}\sum_{i=1}^{n}\left(\frac{i-1}{N-i+1}\right)^{2}$
$\displaystyle+$ $\displaystyle 2(N-n+1)^{2}\sum_{1\leq i<j\leq
n}\frac{(i-1)(j-1)}{(N-i+1)(N-j+1)}$

the variance

$\sigma_{n}^{2}={\rm Var}\left[{n\choose 2}-X_{n}\right]$

is given by

$\displaystyle\sigma_{n}^{2}={n\choose
2}-\mu_{n}-\sum_{i=1}^{n}(i-1)\left(\frac{N-n+1}{N-i+1}\right)^{2}+(N-n+1)\sum_{i=1}^{n}\frac{(i-1)(i-2)(n-i)}{(N-i+2)(N-i+1)^{2}}$
$\displaystyle 2(N-n+1)\sum_{1\leq i<j\leq
n}\frac{(i-1)(j-1)(n-j)}{(N-i+1)(N-j+1)(N-j+2)}$

For $N\to\infty$ the last term with a bivariate sum is of the dominating order
$O(N^{3})$. Letting $N\to\infty$, the scaled term becomes

$\displaystyle\psi(t)=2(1-t)\iint\limits_{0<x<y<t}\frac{xy(t-y)}{(1-x)(1-y)^{2}}{\rm
d}x{\rm d}y,$

which is yet another integral representation for $\psi$. We see that the
dominating contribution to the variability of $X_{n}$ is due to the edges with
different origins.

On summary, we obtained the asymptotics

$\mu_{n}\sim\frac{N^{2}}{2}\varphi(n/N),~{}~{}~{}\sigma_{n}^{2}\sim
N^{3}\psi(n/N),$ (21)

valid uniformly for $n/N<1-\delta$.

##  5 Poisson approximation for the early stages

For small $n$ the graph $G_{n}$ is likely to contain no edges. From the first
expression in (3) it is seen that

$\mu_{n}=O\left(\frac{n^{3}}{N}\right)$ (22)

uniformly in $n\leq N$, and that the order estimate is sharp. Borrowing the
terminology from [2], we can say that $N^{1/3}$ is a threshold function for
the existence of edges in $G_{n}$. To obtain a more precise result, let the
random variable

$\xi_{N}:=\min\\{n:X_{n}>0\\}$

be the first time when an edge becomes occupied. That is to say, the graph
$G_{n}$ for $n<\xi_{N}$ has no edges, while $G_{\xi_{N}}$ has exactly one.

###### Theorem 1

As $N\to\infty$

$N^{-1/3}\,\xi_{N}\stackrel{{\scriptstyle d}}{{\to}}\xi,$

where ${\mathbb{P}}[\xi>x]=e^{-x^{3}/6},~{}~{}~{}x>0$. Thus $\xi^{3}$ has
exponential distribution with mean $6$. The convergence holds with all
moments, that is for $\alpha\geq 0$

${\mathbb{E}}[N^{-\alpha/3}\xi_{N}^{\alpha}]\to{\mathbb{E}}[\xi^{\alpha}]=6^{\alpha/3}\,\Gamma\left(1+{\alpha}/{3}\right).$

Proof. Using (4)

${\mathbb{P}}[\xi_{N}>n]=\prod_{j=2}^{n-1}\frac{N-j}{{j\choose
2}+N-j}=\exp\left\\{-\sum_{j=2}^{n-1}\log\left(1+\frac{{j\choose
2}}{N-j}\right)\right\\}$

Splitting

$\frac{1}{N-j}=\frac{1}{N}+\frac{j}{N(N-j)}$

we have in the range $j<n<N^{2/5}$

$\frac{{j\choose 2}}{N-j}=\frac{{j\choose
2}}{N}+O\left(\frac{j^{3}}{N^{2}}\right),$

and so

$\log\left(1+\frac{{j\choose 2}}{N-j}\right)=\frac{{j\choose
2}}{N}+O\left(\frac{j^{4}}{N^{2}}\right),$

whence summing up

$\sum_{j=2}^{n-1}\log\left(1+\frac{{j\choose
2}}{N-j}\right)=\frac{n^{3}}{6N}+O\left(\frac{n^{2}}{N}\right)+O\left(\frac{n^{5}}{N^{2}}\right)$

uniformly in $n<N^{2/5}$. Letting $n\sim xN^{1/3}$ this converges to
$x^{3}/6$, thus

${\mathbb{P}}[N^{-1/3}\xi_{N}>x]\to e^{-x^{3}/6}$

and the convergence in distribution follows.

To prove convergence of the moments we need to check the uniform integrability
condition

$\limsup\limits_{N\to\infty}{\mathbb{E}}[N^{-\alpha/3}\xi_{N}^{\alpha}~{}1(N^{-1/3}\xi_{N}>A)]\to
0~{}~{}~{}{\rm as~{}}A\to\infty.$ (23)

The expectation involved is

$\displaystyle N^{-\alpha/3}\sum_{AN^{1/3}<n\leq
N}n^{\alpha}~{}{\mathbb{P}}[\xi_{N}=n],$ (24)

where

${\mathbb{P}}[\xi_{N}=n+1]=\frac{{n\choose 2}}{{n\choose
2}+N-n}~{}\prod_{j=2}^{n-1}\frac{N-j}{{j\choose 2}+N-j}$

For $n>N^{1/2}$ we estimate

$\displaystyle{\mathbb{P}}[\xi_{N}=n+1]<{\mathbb{P}}[\xi_{N}>n]<{\mathbb{P}}[\xi_{N}>N^{1/2}]=$
$\displaystyle\exp\left\\{-\sum_{1\leq j<N^{1/2}}\log\left(1+\frac{{j\choose
2}}{N-j}\right)\right\\}<e^{-cN^{1/2}}$

for some $c>0$. Splitting the sum (24) at $N^{1/2}$ for the upper part we have

$\sum_{N^{1/2}\leq n\leq
N}n^{\alpha}~{}{\mathbb{P}}[\xi_{N}=n]<\sum_{N^{1/2}\leq n\leq
N}n^{\alpha}e^{-cn^{1/2}}<N^{\alpha+1}e^{-cN^{1/2}}\to 0.$

For the lower part, using the bounds

$\frac{{j\choose 2}}{N-j}<2,~{}~{}~{}~{}~{}\log(1+x)>\frac{x}{2}~{}~{}{\rm
for~{}~{}}0<x<2,$

we estimate for large enough $N$

$\displaystyle\sum_{AN^{1/3}<n<N^{1/2}}n^{\alpha}~{}{\mathbb{P}}[\xi_{N}=n]$
$\displaystyle<$
$\displaystyle\sum_{AN^{1/3}<n<N^{1/2}}\frac{n^{\alpha+2}}{2N}\exp\left\\{-\sum_{j=1}^{n-1}\log\left(1+\frac{{j\choose
2}}{N-j}\right)\right\\}<$
$\displaystyle\sum_{AN^{1/3}<n<N^{1/2}}\frac{n^{\alpha+2}}{2N}\exp\left\\{-\sum_{j=1}^{n-1}\frac{{j\choose
2}}{2N}\right\\}$ $\displaystyle=$
$\displaystyle\sum_{AN^{1/3}<n<N^{1/2}}\frac{n^{\alpha+2}}{2N}\exp\left\\{-\frac{n(n-1)(n-2)}{6N}\right\\}<$
$\displaystyle\int\limits_{AN^{1/3}}^{\infty}\frac{x^{\alpha+2}}{N}~{}\exp\left(-\frac{x^{3}}{6N}\right)\,{\rm
d}x$ $\displaystyle=$ $\displaystyle
N^{\alpha/3}\int\limits_{A^{3}}^{\infty}\frac{y^{\alpha/3}}{3}~{}\exp\left(-\frac{y}{6}\right)\,{\rm
d}y.$

Multiplying by $N^{-\alpha/3}$ and sending $A\to\infty$, condition (23)
follows.

More informative is the following Poisson approximation on the $N^{1/3}$
scale, which actually implies the convergence in distribution in Theorem 1.

###### Theorem 2

As $N\to\infty$, the process $(X_{\lfloor tN^{1/3}\rfloor},~{}t\geq 0)$
converges weakly in the Skorohod space $D[0,\infty)$ to a nonhomogeneous
Poisson process with rate function $\lambda(t)=t^{2}/2,~{}t>0$.

Proof. We shall verify two conditions of Theorem 5 from [8], Ch. 5, Section 3.

Fix $T>0$. For each $i$, the probability that by time $TN^{1/3}$ there is an
occupied edge $\cdot\leftarrow i$ does not exceed $T^{2}N^{-1/3}$, and the
probability of at least two occupied edges (possibly with same origins) is
estimated as the square of this quantity. Summing over all pairs
$\cdot\leftarrow i,\cdot\leftarrow j$ in the bounds

$sN^{1/3}<i,j<tN^{1/3}$

we obtain

${\mathbb{P}}[X_{\lfloor tN^{1/3}\rfloor}-X_{\lfloor sN^{1/3}\rfloor}\geq
2]=O((t-s)^{2}),~{}~{}~{}0<s<t<T.$

That is to say, asymptotically the time-scaled process has no jumps bigger
than $1$. This is the first condition of the cited theorem.

The compensator of $(X_{n})$ is given by (10). For $n\leq tN^{1/3}$ and $N$
large we have the expansion

$C_{n}=\sum_{m=1}^{n-1}\frac{{m\choose
2}}{N}-\sum_{m=1}^{n-1}\frac{X_{m}}{N-m+1}+O\left(N^{-1/3}\right),$

where the second sum converges in probability to $0$, since from (22)

${\mathbb{E}}\left[\sum_{1\leq
m<tN^{1/3}}\frac{X_{m}}{N-m+1}\right]<\sum_{1\leq
m<tN^{1/3}}\frac{c\,m^{3}}{N(N-m+1)}=O(N^{-2/3}).$

Hence as $N\to\infty$ for each $t$

$C_{\lfloor
tN^{1/3}\rfloor}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\frac{t^{3}}{6}.$

Thus the time-scaled compensator converges to a deterministic function. This
is the second condition of the cited theorem.

##  6 The fluid limit

Fluid limits are functional laws of large numbers which assert convergence of
a process to a deterministic curve [4]. Comparison with the mean readily
implies a fluid limit for the scaled edge count.

###### Theorem 3

As $N\to\infty$,

$\sup_{t\in[0,1]}\left|\frac{2}{N^{2}}\,X_{\lfloor
tN\rfloor}-\varphi(t)\right|\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0.$
(25)

Proof. From the asymptotics (21)

${\rm Var}\left[\frac{2}{N^{2}}\,X_{\lfloor tN\rfloor}\right]\to 0,$

hence application of Chebyshev’s inequality yields

$\frac{2}{N^{2}}\,X_{\lfloor
tN\rfloor}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\varphi(t),$

for each fixed $t\in(0,1)$. But this implies the functional convergence in the
uniform metric, because $X_{n}$ is nondecreasing in $n$ and the function
$\varphi(t)$ is continuous (and monotone). The underlying fact is that the
pointwise convergence of nondecreasing functions on $[0,1]$ to a continuous
function ensures the uniform convergence.

##  7 Gaussian fluctuations

The typical magnitude of the difference in (25) is of the order of $N^{-1/2}$.
To capture such fluctuations we need to scale with factor $N^{1/2}$, with an
eye on the Central Limit Theorem

$\frac{X_{\lfloor
tN\rfloor}-\frac{N^{2}}{2}\varphi(t)}{\sqrt{\psi(t)N^{3}}}\stackrel{{\scriptstyle
d}}{{\to}}{\cal N}(0,1),$

for each fixed $t\in(0,1)$. This indeed holds true, but is not straightforward
since the indicators in the representation (1) are not independent.

A wider view is to consider the whole process

$\displaystyle Y_{N}(t):$ $\displaystyle=$
$\displaystyle\frac{\sqrt{N}}{2}\left(\frac{2}{N^{2}}X_{\lfloor
tN\rfloor}-\varphi(t)\right)$ (26) $\displaystyle=$
$\displaystyle\frac{X_{\lfloor
tN\rfloor}-\frac{N^{2}}{2}\varphi(t)}{N^{3/2}},~{}~{}~{}t\in[0,1]$

as a random element of the Skorohod space $D[0,1]$ of piecewise continuous
functions. We aim to show weak convergence to a Gaussian diffusion defined by
the stochastic integral

$Y(t)=(1-t)\int_{0}^{t}\frac{s+\log(1-s)}{1-s}{\rm\,d}B(s),~{}~{}~{}t\in[0,1],$

where $B(\cdot)$ is the Brownian motion. The process $Y(\cdot)$ can be
characterised as the unique (strong) solution to the stochastic differential
equation

${\rm d}Y(t)=-\frac{Y(t)}{1-t}{\rm d}t+(L+t){\rm d}B(t),~{}~{}~{}Y(0)=0.$ (27)

At the right endpoint the value is nonrandom, $Y(1)=0$. This process is a sort
of Gaussian bridge derived from suitably time-changed Brownian motion, as in
[7] (see second construction in Example 1).

Using Itô isometry the covariance function is computed as

$\displaystyle{\rm Cov}(Y(s),Y(t))$ $\displaystyle=$
$\displaystyle\frac{1-t}{1-s}\int_{0}^{s}\left(\frac{u+\log(1-u)}{1-u}\right)^{2}\,{\rm
d}u$ (28) $\displaystyle=$
$\displaystyle\frac{1-t}{1-s}\,\psi(s),~{}~{}~{}0\leq s\leq t\leq 1,$

which agrees and generalises the asymptotic variance formula (19) obtained
differently. Thus we may also characterise $Y(\cdot)$ as a continuous Gaussian
process on $[0,1]$ with zero mean and the covariance function (28).

###### Theorem 4

As $N\to\infty$

$(Y_{N}(t),~{}t\in[0,1])\Rightarrow(Y(t),~{}t\in[0,1]),$

where the weak convergence of processes holds in the Skorohod space $D[0,1]$.

Proof. Replacing centering in (26) by the mean $\mu_{n}$ makes no difference
asymptotically, by the virtue of (13). Thus consider the naturally centered
process

$Y^{\circ}_{N}(t):=\frac{X_{\lfloor tN\rfloor}-\mu_{\lfloor
tN\rfloor}}{N^{3/2}}=\frac{X_{\lfloor tN\rfloor}^{\circ}}{N^{3/2}}.$

The generator ${\cal L}_{N}$ of ${Y}_{N}^{\circ}(\cdot)$ acts on smooth
functions as

${\cal
L}_{N}f(t,x)=N\,{\mathbb{E}}[f(t+N^{-1},Y^{\circ}_{N}(t+N^{-1}))-f(t,Y^{\circ}_{N}(t))\,|\,Y^{\circ}_{N}(t)=x].$
(29)

Setting $t=n/N$, $\Delta X_{n}^{\circ}=X_{n}^{\circ}-X_{n-1}^{\circ}$ we have

$Y^{\circ}_{N}\left(t+N^{-1}\right)-Y^{\circ}_{N}(t)=\frac{\Delta
X_{n+1}^{\circ}}{N^{3/2}}.$ (30)

Given

$X_{n}=\mu_{n}+xN^{3/2}~{}~{}~{}~{}(\Longleftrightarrow Y^{\circ}_{N}(t)=x)$

for some admissible $x$, the distribution of increment $\Delta X_{n+1}$ is
negative hypergeometric with moments (5), (6). Recalling (11), the conditional
expectation of the increment (30) expands as

${\mathbb{E}}\left[\frac{\Delta
X_{n+1}^{\circ}}{N^{3/2}}\,{\bigg{|}}\,X_{n}=\mu_{n}+xN^{3/2}\right]=\frac{-x}{N-n+1}=\frac{-x}{1-t}N^{-1}+o\left(N^{-1}\right).$
(31)

This quantity squared is of the order $O(N^{-2})$, hence the second
conditional moment of the increment is approximable by the conditional
variance as

${\mathbb{E}}\left[\left(\frac{\Delta
X_{n+1}^{\circ}}{N^{3/2}}\right)^{2}\,{\bigg{|}}\,X_{n}=\mu_{n}+xN^{3/2}\right]={\rm
Var}\left[\frac{\Delta
X_{n+1}}{N^{3/2}}\,{\bigg{|}}\,X_{n}=\mu_{n}+xN^{3/2}\right]+o\left(N^{-1}\right).$

Manipulating (6), the asymptotics of the conditional variance becomes

$\frac{\left({n\choose
2}-\mu_{n}\right)^{2}}{(N-n)^{2}N^{3}}+o(N^{-1})=\frac{(t^{2}-\varphi(t))^{2}}{4(1-t)^{2}N}+o(N^{-1})=\frac{(t+L)^{2}}{N}+o(N^{-1}).$
(32)

Expanding the function in (29) in Taylor series, and applying (31) and (32),
we may write the generator (29) in the form

${\cal L}_{N}f(t,x)={\cal L}f(t,x)+o(1),~{}~{}N\to\infty,$

where ${\cal L}$ is the generator of the diffusion (27) acting as

${\cal
L}f(t,x)=f_{t}(t,x)+\frac{-x}{1-t}f_{x}(t,x)+\frac{1}{2}(t+L)^{2}f_{xx}(t,x).$

By some general theory ([13], Proposition 17.9 and Theorem 17.25), convergence
of generators on a rich enough class of test functions implies the functional
convergence of processes. This principle allows us to justify the weak
convergence $Y_{N}^{\circ}\Rightarrow Y$ for the processes restricted to
$[0,\,1-\delta],0<\delta<1$. Indeed, within the reduced time range the drift
and diffusion coefficients in (27) are Lipschitz-continuous, hence by [15]
(Theorem 3.17) the space of $C^{3}$-smooth functions vanishing with all
derivatives at infinity is an invariant core for the the semigroup associated
with (27).

At the right endpoint $t=1$ the drift and diffusion coefficients both explode.
To circumvent this nuisance we shall use the fact that the limit process has
the fixed right endpoint $Y(1)=0$, hence by the continuity for all positive
$x,\varepsilon$ there exists $\delta>0$ such that

${\mathbb{P}}\left[\sup_{1-\delta\leq t\leq 1}|Y(t)|>x\right]<\varepsilon$
(33)

(as is concluded from the tightness criterion in [1], Theorem 8.2). Obviously,
the inequality $\sup_{1-\delta\leq t\leq 1}|Y(t)|<x$ implies that the modulus
of continuity of $Y$ on $[1-\delta,1]$ does not exceed $x$. Therefore, with
the weak convergence in $D[0,\,1-\delta]$ in hand, tightness of the sequence
$Y_{N}^{\circ}$ in $D[0,1]$ will be shown if we could verify a counterpart of
(33) for $Y_{N}^{\circ}$ in order to bound the modulus of continuity, in line
with condition (15.9) from [1].

For the latter, we shall adopt the Chow maximal inequality [9] (Theorem 9.3):
for positive submartingale $(Z_{n})$ and nonincreasing sequence $(c_{n})$ it
holds that for $\lambda>0$

${\mathbb{P}}\left[\max_{1\leq k\leq
n}c_{k}Z_{k}>\lambda\right]\leq\frac{1}{\lambda}\left(\sum_{k=1}^{n-1}(c_{k}-c_{k+1}){\mathbb{E}}[Z_{k}]+c_{n}{\mathbb{E}}[Z_{n}]\right).$

Applying the inequality to the squared martingale (12),

$Z_{n}=\left(\frac{X_{n}^{\circ}}{N-n+1}\right)^{2},$

with constants $c_{n}=(N-n+1)^{2}$ and $\lambda=x^{2}N^{3}$ we obtain

$\displaystyle{\mathbb{P}}\left(\max_{N(1-\delta)\leq n\leq
N}|X_{n}^{\circ}|>xN^{3/2}\right)\leq\frac{1}{x^{2}N^{3}}\sum_{n=\lfloor
N(1-\delta)\rfloor}^{N}\frac{2N-2n+1}{(N-n+1)^{2}}\,\sigma_{n}^{2}<$
$\displaystyle\frac{4}{x^{2}N}\sum_{n=\lfloor
N(1-\delta)\rfloor}^{N}\log^{2}\left(\frac{N}{N-n+1}\right)\to\frac{4}{x^{2}}\,\delta\log^{2}\delta,$

as $N\to\infty$. Choosing $\delta$ small enough, this implies the analogue of
(33) for $Y_{N}^{\circ}$, hence the tightness in $D[0,1]$. Since weak
convergence in each $D[0,\,1-\delta]$ entails the convergence of finite-
dimensional distributions, the assertion now follows by application of
Prohorov’s theorem [1].

A similar technical difficulty caused by discontinuity of the drift
coefficient at $t=1$ is present also by a martingale approach to approximating
the empirical distributions by the Brownian bridge. In [10] (p. 561) this is
handled using the time reversibility, which is not available in our situation.

##  8 Construction by insertion

### The Pólya urn.

For $M$ balls, of which $K$ are white and $M-K$ are black, arrangement in a
sequence defines a weak composition of integer $M-K$ in $K+1$ parts. The white
balls appear in the role of delimeters between the parts. For instance

$\bullet\bullet\bullet\stackrel{{\scriptstyle
1}}{{\circ}}\bullet\bullet\bullet\,\bullet\stackrel{{\scriptstyle
2}}{{\circ}}\,\stackrel{{\scriptstyle
3}}{{\circ}}\bullet\bullet\bullet\bullet\bullet\stackrel{{\scriptstyle
4}}{{\circ}}\bullet$

represents the weak composition $(3,4,0,5,1)$ of integer $13=3+4+0+5+1$. We
speak of ‘weak’ composition to mean that zero parts are allowed.

Suppose $K$ white balls are arranged in sequence and a black ball is inserted
uniformly at random in any of $K+1$ possible positions, that is to the left,
to the right or between two balls of the existing configuration. Then another
black ball is inserted uniformly at random in any of $K+2$ possible positions.
Continuing so forth yields a sequence of random weak compositions, each with
uniform distribution over ${M\choose K}$ weak compositions in $K$ parts for
$M=K,K+1,\ldots$. Each part of the composition has a negative binomial
distribution as in (4), and as $M$ grows the whole composition behaves like a
$(K+1)$-component Pólya urn process (see [3] for a recent study). In
particular, as $M\to\infty$, the vector of parts scaled by $M-K$ converges
(almost surely) to a vector $(\xi_{1},\ldots,\xi_{K+1})$ with uniform
distribution over the $K$-dimensional simplex.

In application to our random graph, the Pólya process is directly relevant to
the analysis of the aged component $A_{m,n}$ in (8), and this connection will
be employed in the next Section. To represent the full edge counts $(X_{n})$ a
more sophisticated insertion procedure is needed.

### The insertion algorithm

Start with $N$ white balls arranged in a row and labelled $1,\ldots,N$. In
hours $1$ and $2$ do nothing. In hour $3$ insert a black ball uniformly at
random in any position to the right of the $2$nd white ball. By induction,
within hour $n=3,\ldots,N$ do one-by-one $n-2$ such random insertions of black
balls in the configuration to the right of $(n-1)$st white ball. For instance,
if $N=6$ the configuration

$\stackrel{{\scriptstyle 1}}{{\circ}}\,\stackrel{{\scriptstyle
2}}{{\circ}}\,\stackrel{{\scriptstyle
3}}{{\circ}}\bullet\,\bullet\stackrel{{\scriptstyle
4}}{{\circ}}\bullet\,\bullet\stackrel{{\scriptstyle
5}}{{\circ}}\bullet\stackrel{{\scriptstyle 6}}{{\circ}}$

may occur in hour $5$, when a black balls remains to be inserted to the right
of the $4$th while ball to complete the step, and there are $6$ equiprobable
ways to do this.

In this picture, the composition emerging by the end of hour $N$ has the same
distribution as $(\Delta X_{1},\ldots,\Delta X_{N})$. In terms of the graph
process, the difference with the urn model in Section 2 is that the virtual
elements become scheduled for future occupancy as soon as they are added to
the pool. Implicitly, the insertion algorithm has been used in our computation
of the moments of $X_{n}$.

##  9 Poisson approximation for the last stages

Finally, we seek for approximation of the edge-counting process when a few
vertices remain unoccupied. Complementing our notation, let

$\Delta X_{N+1}:={N\choose 2}-X_{N}$

be the number of edges missing in $G_{N}$. Interpreting $\Delta X_{N+1}$ as
the number of edges occupied after the last vertex becomes occupied, this
quantity is analogous to the number $\xi_{N}$ of vertices occupied before the
first edge becomes occupied.

To find the right scaling we shall inspect the moments of $\Delta X_{N+1}$.
For the mean we have from (3) a simple formula

${\mathbb{E}}[\Delta X_{N+1}]={N\choose
2}-\mu_{N}=N\sum_{j=1}^{N-1}\frac{1}{N-j+1}=N(h_{N}-1),$

where $h_{N}$ is the harmonic number. Thus as $N\to\infty$

${\mathbb{E}}[\Delta X_{N+1}]\sim N\log N.$ (34)

For the second noncentral moment (20) gives

$\displaystyle{\mathbb{E}}[\Delta X_{N+1}]^{2}={\mathbb{E}}[\Delta
X_{N+1}]+2\sum_{i=1}^{N}\frac{(i-1)(i-2)}{(N-i+1)(N-i+2)}+$ $\displaystyle
2\sum_{1\leq i<j\leq N}\frac{2(i-1)(j-1)}{(N-i+1)(N-j+2)}.$

Approximating the first sum by an integral gives

$2\sum_{i=1}^{N}\frac{(i-1)(i-2)}{(N-i+1)(N-i+2)}=O(N^{2}).$

We are left with assessing

$2\sum_{1\leq i<j\leq N}\frac{2(i-1)(j-1)}{(N-i+1)(N-j+2)}.$

Replacing in the denominator $1$ by $2$ will give a lower bound, and $2$ by
$1$ an upper bound; so let us stick with the denominator $(N-i+1)(N-j+1)$.
Then adding the same sum over $i>j$ and the diagonal part

$2\sum_{i=1}^{N}\frac{2(i-1)^{2}}{(N-i+1)^{2}}=O(N^{2}),$

the lower bound becomes

$\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{2(i-1)(j-1)}{(N-i+1)(N-j+1)}\sim
2\left(N\sum_{j=1}^{N-1}\frac{1}{N-j+1}\right)^{2}\sim 2(N\log N)^{2}.$

The upper bound has the same asymptotics, whence

${\mathbb{E}}[\Delta X_{N+1}]^{2}\sim 2(N\log N)^{2}.$

By the same token, for the third moment the leading term will be

${\mathbb{E}}[\Delta X_{N+1}]^{3}\sim 3!\sum_{1\leq i<j<k\leq
N}\frac{3!(i-1)(j-1)(k-1)}{(N-i+1)(N-j+2)(N-k+3)}\sim 3!(N\log N)^{3},$

and proceeding so forth we obtain

${\mathbb{E}}[\Delta X_{N+1}]^{r}\sim r!(N\log N)^{r}.$

Since $r!$ is the $r$th moment of the exponential distribution, we conclude
that

$\frac{\Delta X_{N+1}}{N\log N}\stackrel{{\scriptstyle d}}{{\to}}{\rm
Exponential}(1).$

Comparing the mean (34) with the number $N-1$ of edges added to the pool at
time $N$, we see that the latter has no impact on the limit law of $\Delta
X_{N+1}$. Similarly, for each fixed $m$, in the decomposition (8) of
$X_{N}-X_{N-m}$ the term $R_{N-m,N}$ counting the recent edges is
asymptotically negligible. This idea combined with exchangeability leads to
the following result.

###### Theorem 5

For each $m\geq 0$ the random vector

$\displaystyle\left(\frac{\Delta X_{N-m+1}}{N\log N},\,\frac{\Delta
X_{N-m}}{N\log N},\,\ldots,\,\frac{\Delta X_{N+1}}{N\log N}\right)$

converges in distribution, as $N\to\infty$, to a vector of $m+1$ i.i.d.
exponential random variables with mean one.

Proof. For $m>0$ we consider

${N\choose 2}-X_{N-m}=\Delta X_{N-m+1}+\cdots+\Delta X_{N+1},$

the number of edges in the complete graph minus the number of egdes in
$G_{N-m}$. This includes ${N-m\choose 2}-X_{N-m}$ aged edges and

${N\choose 2}-{N-m+1\choose 2}=(m+1)N-{m+2\choose 2}=O(N)$

recent edges, all relative to time $N-m$. From (3)

${\mathbb{E}}\left[{N-m\choose 2}-X_{N-m}\right]\sim(m+1)N\log N,$

hence with scaling by $N\log N$ we may ignore the recent ages.

From (20) for the second moment we get

$\displaystyle{\mathbb{E}}\left[{N-m\choose 2}-X_{N-m}\right]^{2}\sim
2(m+1)(m+2)\sum_{1\leq i<j\leq N-m}\frac{(i-1)(j-1)}{(N-i+1)(N-j+2)}\sim$
$\displaystyle(m+1)(m+2)(N\log N)^{2}.$

It is now easy to recognise and prove the asymptotics of higher moments:

${\mathbb{E}}\left[{N-m\choose 2}-X_{N-m}\right]^{r}\sim(m+1)\cdots(m+r)(N\log
N)^{r}.$

Recalling that $(m+1)_{r}=(m+1)\cdots(m+r)$ are moments of the gamma
distribution, we conclude that

$\frac{{N\choose 2}-X_{N-m}}{N\log N}\stackrel{{\scriptstyle d}}{{\to}}{\rm
Gamma}(m+1,1).$

This special case is also known as the Erlang distribution.

Appealing to the insertion construction in Section 8, given that ${N\choose
2}-X_{N-m}=M-m$ virtual edges are present at time $N-m$, the weak composition
corresponding to their occupancy schedule can be represented by the
$(m+1)$-component Pólya urn with $M-m$ black balls. Since for $N\to\infty$
also ${N\choose 2}-X_{N-m}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\infty$,
the proportions converge in distribution to random vector
$(\xi_{1},\ldots,\xi_{m+1})$ uniformly distributed over the $m$-dimensional
simplex. It follows that the vector (5) converges in distribution to
$(\gamma\xi_{1},\ldots,\gamma\xi_{m+1})$, where $\gamma\stackrel{{\scriptstyle
d}}{{=}}{\rm Gamma}(m+1,1)$ is independent of $(\xi_{1},\ldots,\xi_{m+1})$. By
Lucacs characterisation of the gamma distribution, such
$(\gamma\xi_{1},\ldots,\gamma\xi_{m+1})$ has i.i.d. Exponential$(1)$
components.

As an easy corollary of this result, for the time reversal of $(X_{n})$ we
obtain a counterpart of Theorem 2:

###### Theorem 6

As $N\to\infty$, the point process with atoms

$\frac{{N\choose 2}-X_{N}}{N\log N},\,\frac{{N\choose 2}-X_{N-1}}{N\log
N},\,\cdots$

converges weakly to a homogeneous Poisson process with unit rate.

In particular, for $x>0$, at the stage when the complete graph on $N$ points
falls short of $\lfloor xN\log N\rfloor$ elements (vertices and edges), the
distribution of the number of virtual vertices is close to Poisson$(x)$.

## References

  * [1] P. Billingsley, Convergence of probability measures, Wiley, 1968.
  * [2] B. Bollobás, Random graphs, Academic Press, 1985.
  * [3] K. Borovkov (2021), Gaussian process approximations for multicolor Pólya urn models, J. Appl. Probab. 58, 274–286.
  * [4] R. W. R. Darling (2002), Fluid limits of pure jump processes: a practical guide, arxiv.org
  * [5] R. Durrett, Random graph dynamics, CUP, 2009.
  * [6] A. Frieze and M. Karoński, Introduction to random graphs, CUP, 2015.
  * [7] D. Gasbarra, T. Sottinen and E. Valkeila, (2007). Gaussian Bridges. In: Benth, et al (eds) Stochastic Analysis and Applications. Abel Symposia, vol 2. Springer, 2007.
  * [8] I.I. Gihman and A.V. Skorohod, Stochastic differential equations and their applications, Kyiv, 1982.
  * [9] A. Gut, Probability: a graduate course, Springer, 2005.
  * [10] J. Jacod and A.N. Shiryaev, Limit theorems for stochastic processes, Springer, 2003.
  * [11] S. Janson, T. Luczak and A. Rucinski, Random graphs, Wiley, 2000.
  * [12] R. van der Hofstad, Random graphs and complex networks, vol. 1, CUP, 2016.
  * [13] O. Kallenberg, Foundations of modern probability, Springer, 1997.
  * [14] V. Kolchin, Random graphs, CUP, 1998.
  * [15] V.N. Kolokoltsov, Nonlinear Markov processes and kinetic equations, Cambridge University Press, 2010.


# DeepCFL: Deep Contextual Features Learning from a Single Image

Indra Deep Mastan and Shanmuganathan Raman
Indian Institute of Technology Gandhinagar
Gandhinagar, Gujarat, India
{indra.mastan<EMAIL_ADDRESS>
###### Abstract

Recently, there is a vast interest in developing image feature learning
methods that are independent of the training data, such as deep image prior
[35], InGAN [28, 29], SinGAN [27], and DCIL [8]. These methods perform various
tasks, such as image restoration, image editing, and image synthesis. In this
work, we proposed a new training data-independent framework, called Deep
Contextual Features Learning (DeepCFL), to perform image synthesis and image
restoration based on the semantics of the input image. The contextual features
are simply the high dimensional vectors representing the semantics of the
given image. DeepCFL is a single image GAN framework that learns the
distribution of the context vectors from the input image. We show the
performance of contextual learning in various challenging scenarios:
outpainting, inpainting, and restoration of randomly removed pixels. DeepCFL
is applicable when the input source image and the generated target image are
not aligned. We illustrate image synthesis using DeepCFL for the task of image
resizing.

##  1 Introduction

Recently, there has been a remarkable success for image restoration and image
synthesis methods that do not use training data [35, 30, 7, 28, 27, 31, 8] .
One of the major challenges for the deep feature learning methods above is the
limited contextual understanding in the absence of feature learning from
training samples [7]. Contextual learning is mostly studied for image
inpainting [25] and image transformation tasks [23], where many pairs of
source and target images are used to learn the image context.

(a) Original

(b) Corrupted

(c) DIP [35]

(d) DeepCFL

(e) Image synthesis using DeepCFL (input image in red color frame).

Figure 1: The figure show image restoration (first row) and image synthesis
(second row). Here, DIP [35] is a pixel-loss based setup. DeepCFL is a single
image GAN framework for contextual learning. DeepCFL could fill the masked
regions well for image restoration and also perform new object synthesis,
which could not be performed using the pixel-based comparison of DIP [35].

Figure 2: Contextual Features Learning (DeepCFL). The figure shows the
framework for the outpainting. The corrupted image $x$ is fed into the
generator $\mathcal{G}$. Here, $\mathcal{G}$ is an encoder-decoder network
which outputs an image $\mathcal{G}(x)=y$. Next, VGG19 ($\phi$) computes the
contextual features $\phi(x)$ of $x$ and $\phi(y)$ of $y$. Then we compute
contextual features loss (CFL) and reconstruction loss (RL) and minimize total
loss (TL). The main idea of DeepCFL is to synthesize new features by comparing
image statistics at contextual features space. Note that CFL compares the
context vectors $\phi(x)$ and $\phi(y)$ using CVL and CAL (see Fig. 9 for
above example).

Figure 3: The figure shows the context vectors comparison in the adversarial
framework. $\phi(x)$ and $\phi(y)$ are computed from the input image $x$ and
the restored image $\mathcal{G}(x)=y$. The masked regions of $x$ are restored
in $y$. For simplicity, we address restored regions in $y$ as masked regions
of $y$. Here, $\mathcal{D}^{real}$ and $\mathcal{D}^{fake}$ are the two
instances of $\mathcal{D}$ which share the network parameters.

Restoration of missing pixels in an image is a classical inverse problem [46,
18, 5, 33, 44, 4, 6, 10, 32]. It addresses various applications such as image
editing, restoration of damaged paintings, image completion, and image
outpainting. The image transformation model allows formulation for a variety
of tasks such as style transfer, single image animation, and domain transfer
[23].

Traditionally, image restoration is formulated as optimization problems, where
the objective function includes a loss term and an image prior term, e.g.,
sparse [1, 9] and low-rank [13] priors. The desired image is reconstructed by
finding the solution for the optimization problem. Deep learning models have
shown an ability to capture image priors implicitly by minimizing the loss
over the training samples [17, 25, 19, 43, 3, 38, 36, 37, 40]. However,
training data-based methods have their limitations, such as generalizability
to new images [35, 7].

Recently, there is a growing interest in developing methods that are
independent of training data to perform image restoration and image synthesis
tasks [35, 30, 7, 28, 27, 31, 8]. Ulyanov et al. proposed deep image prior
(DIP) [35], which shows that the handcrafted structure of the convolution
neural network (CNN) provides an implicit image prior [35]. However, image
prior learning using pixel-to-pixel loss in [35] is limited to the tasks which
have a spatial correspondence between the pixels of the source image and the
target image [23]. One approach would be to learn the internal patch
distribution from the input image when the source and the target images are
not aligned.

The single image GAN frameworks show applications where the spatial mapping
between the source and the target images is not well-defined [27, 28, 29, 30].
Shocher et al. proposed an internal learning (IL) framework to synthesize
realistic image patches using image-conditional GAN, called InGAN [28, 29].
Shaham et al. showed an unconditional generative model for image synthesis,
named SinGAN [27]. Mastan et al. have shown the single image GAN framework for
denoising-super resolution and image resizing [8].

The pixel-to-pixel loss framework in [35] and the internal patch distribution
learning frameworks in [27, 28, 29] do not perform image reconstruction by
considering the context of the objects. An image could be considered as a
collection of high dimensional context vectors [23]. These high dimensional
vectors are the image statistics captured at the intermediate layers of the
features extractor such as VGG19 network [23, 22]. An interesting question
would be that, given an incomplete image summary, can we synthesize new
context vectors and use them to reconstruct the image. The context of an image
is critical to perform image restoration and image synthesis tasks (Fig. 1 and
Fig. 8) [35, 7, 30, 28]. We present a single image GAN framework (DeepCFL)
which studies the contextual features in the image. The problem is _novel_ as
it aims to learn the distribution of the contextual features (contextual
learning) in the image instead of internal patch distribution, as in the case
of InGAN [28, 29] and SinGAN [27].

We have shown a pictorial representation of DeepCFL in Fig. 3. The aim is to
utilize the image features of the original image $I$, which are present in the
corrupted image $x$. We generate a restored image $y$ which utilizes image
features from $x$. We use an encoder-decoder network $\mathcal{G}$ to generate
$y$. Then, we iteratively minimize the total loss (TL) between the corrupted
image and the restored image. TL is a combination of contextual features loss
(CFL) and reconstruction loss (RL). Fig. 3 shows that CFL allows feature
learning using two different tools: contextual adversarial loss (CAL) and
context vectors loss (CVL). The detailed description of each component of the
framework and the formal definitions of the loss functions are described Sec.
3.

CAL performs distribution matching in the adversarial framework to synthesize
new context vectors for the corrupted image $x$. CVL computes the direct
difference between the context vectors extracted from the corrupted image $x$
and the restored image $y$. Therefore, in CFL, CAL generates new context
vectors and CVL improvises them. RL is a pixel-to-pixel loss (i.e., mean
squared error), which ensures the preservation of image features in the
restored images. Intuitively, the main idea is to generate new context vectors
using CFL and map them to the image features implicitly through pixel-based
comparison using RL.

We have studied the performance of DeepCFL for the following tasks: image
outpainting, inpainting of arbitrary holes, and restoration of $r\%$ pixels
missing in the corrupted image. We also show the applications in the presence
of non-aligned image data using image resizing. The key contributions of this
work are summarized below.

  * •

We propose a single image GAN framework for contextual features learning
(DeepCFL). The framework performs well on image outpainting tasks (Fig. 4 and
Table 1). We also illustrate that DeepCFL synthesizes new objects when
resizing the image (Fig. 6).

  * •

DeepCFL investigates image reconstruction considering the contextual features.
The contextual features learning is useful for the applications that use only
a single image as input. We show the generalizability of DeepCFL by performing
multiple applications (Sec. 4).

  * •

We provide a detailed analysis of contextual features learning by illustrating
reconstruction in various challenging setups such as arbitrary hole
inpainting, restoration of a high degree of corruption, restoration of images
with a word cloud, ablation studies, and limitations (Sec. 4 and Sec. 5).

##  2 Related work

Deep feature learning captures good image features by using the strong
internal data repetitions (self-similarity prior) [11, 15, 45, 30, 42], hand-
crafted structure [35, 7], and explicit regularizer [21]. DeepCFL is a single
image GAN setup, which is different from features learning frameworks proposed
earlier [37, 34, 39, 26, 19, 41, 24, 23]. Single image GAN frameworks performs
variety of tasks such as image editing [27], retargeting [29], denoising
super-resolution [8], and video inpainting [42, 16]. Our contextual learning
framework is somewhat related to [35, 7, 28, 8]. InGAN [29, 28] and SinGAN
[27] are single image GAN frameworks for learning the internal patch
distribution. DCIL leverage internal learning with the contextual loss [8].
DeepCFL is related to [35, 7, 28, 8] and does not employ a masked patch
discriminator for CAL [37]. It does not use a features expansion network and
relies on the features reconstruction capabilities of the encoder-decoder
network [37].

##  3 Our Framework

DeepCFL is a single image GAN framework to synthesize new context vectors that
are consistent with the semantics of the input source image. The task is to
extract features from the source image and synthesize a new target image. The
source image could be a clean or a corrupted image. The target image could be
of the same size as the source image or a different size. For example, in the
case of image restoration, we use a corrupted source image with missing pixel
values. The contextual features are used to fill the missing regions of the
corrupted image. For image synthesis, a clean image is used to synthesize new
images of different sizes. Below, we discuss image restoration and context
vectors before we describe the DeepCFL framework.

Let $\mathcal{I}$ denote the set of original images, $X$ denote the set of
corrupted images, and $Y$ denote the set of restored images. Let $x$ denotes a
corrupted image, i.e., $x\in X$. $x$ is computed by removing pixels from an
original image $I$ using a binary mask $m$ as follows: $x=I\odot m$, where
$\odot$ is the Hadamard product and $I\in\mathcal{I}$. The mask $m$ defines
the underlying image restoration application. For example, in image
outpainting of 20% pixels, the mask removes the 10% pixels each along the
right side and the left side of the image. For the restoration of $r\%$
pixels, the mask contains $r\%$ zeros at random locations. For image
inpainting, the mask contains arbitrary shapes. The objective is to restore
the image details in $x$, which were removed by $m$.

Image restoration procedure. The task is to generate a new image
$\mathcal{G}(x)=y$, which contains the restored pixels. Here, $\mathcal{G}$ is
the generator network which maps the corrupted image to a restored image $y$,
i.e., $y\in Y$. The corrupted image $x$ could be considered as a source image
as it contains the features from the original image $I$. The main intuition is
to estimate the context for masked regions of $y$ based on the image features
present at the unmasked regions of $x$ (Fig. 3). The image restoration process
iteratively minimizes the loss computed between $x$ and $y$.

What are context vectors? The context vectors of an image $I$ are the image
statistics present at intermediate layers of a feature extractor $\phi(I)$.
VGG19 has been widely used to extract image statistics. Formally, given an
image $I$, let $\phi(I)=\\{\phi_{l}(I)\\}_{l=1}^{N}$ denote the set of context
vectors extracted from $I$. Here, $\phi:\mathcal{I}\rightarrow CV$ is the pre-
trained VGG19 network [12] which maps image $I\in\mathcal{I}$ to its context
vectors $\phi(I)\in CV$. $\phi_{l}(\cdot)$ denotes the feature extracted from
the layer $l$ of $\phi(\cdot)$ and $N$ is the number of layers in $\phi$.

Why context vectors are important? Fig. 1 and Fig. 8 show that the contextual
learning framework would allow image restoration and image synthesis based on
the semantics of the input (refer Fig. 4 and Fig. 6 for more examples). For
example, in the case of restoration of missing pixels, the key observation is
to improve the masked regions in the restore image $y$ using the unmasked
regions in the corrupted image $x$. It is done by matching the distribution of
the contextual features of the corrupted image $\phi(x)$ and the contextual
features of the restored image $\phi(y)$ (Sec. 3.2).

DeepCFL. We now discuss the DeepCFL framework shown in Fig. 3. It consists of
a generator $\mathcal{G}$, a discriminator $\mathcal{D}$, and a features
extractor $\phi$. The corrupted image $x$ is fed into $\mathcal{G}$. The
generator outputs an image $y=\mathcal{G}(x)$. Next, we feed $x$ and $y$ into
$\phi(\cdot)$ to compute $\phi(x)$ and $\phi(y)$. Then we minimize the total
loss (TL) computed between $x$ and $y$ (Eq. 1). The two primary components of
TL are the contextual features loss (CFL) and the reconstruction loss (RL).
CFL synthesizes new context vectors for the masked regions in $\phi(y)$, where
the features learning procedure is assisted by contextual features in
$\phi(x)$. $\mathcal{D}$ is used for computing CFL. RL is computed between the
unmasked regions of $x$ and $y$ to provide image feature consistency in $y$.

###  3.1 Network Design

Generator. The generator $\mathcal{G}:X\rightarrow Y$ maps the source image
$x\in X$ to the target image $y\in Y$. $\mathcal{G}$ is a depth-5 encoder-
decoder network without skip connections (ED). The ED architecture works as
the implicit regularizer to stabilize the image feature learning [7, 35]. It
exploits the inherent self-similarity present in the source image. We use
context normalization [37] to maximize features learning. Intuitively, DeepCFL
is unsupervised in the sense that no training data are used to train the
generator network for any of the tasks. It is a single image GAN framework
which uses pre-trained VGG19 as the features extractor. VGG19 is widely used
in style transfer works for defining loss at VGG features space. The feature
extractor distills strong prior in the framework [8].

Discriminator. The discriminator $\mathcal{D}:CV\rightarrow\mathcal{M}$ maps
the context vectors to a discriminator map $\mu\in\mathcal{M}$, where each
entry in $\mu$ denotes the probability of the context vector coming from the
distribution of the contextual feature of the original image. Fig. 3
illustrates the discriminator task to distinguish context vectors $\phi(x)$
and $\phi(y)$. The generator $\mathcal{G}$ learns the context vectors through
its interaction with $\mathcal{D}$. We use a multi-scale discriminator (MSD),
where each output is a weighted average of the output from several
discriminators (we have illustrated $\mathcal{D}$ using a single CNN for
simplicity in Fig. 3 and Fig. 3). Note that the discriminators in MSD would
resize the context vectors.

###  3.2 Loss Function

(a) Original

(b) Corrupted

(c) DIP [35]

(d) MEDS [7]

(e) InGAN [28]

(f) DeepCFL

Figure 4: Image outpainting. The figure shows the restoration of 20% pixels in
the image. DIP [35] and MEDS [7] fill the missing regions but do not preserve
the structure of the objects. Internal learning of InGAN [28] performed
better, but the generated new image features are not very clear. DeepCFL
incorporates the contextual understanding and is observed to perform better
(Table 1).

The goal of the loss function is to maximize the feature learning from source
$x$ by comparing it with generated image $\mathcal{G}(x)=y$. The total loss
(TL) is defined in Eq. 1.

$\begin{split}\mathcal{L}_{tl}(x,y,\mathcal{G},\mathcal{D},\phi)=\lambda_{\mathcal{G}}\;\mathcal{L}_{cfl}(x,y,\mathcal{G},\mathcal{D},\phi)\\\
+\lambda_{\mathcal{R}}\;\mathcal{L}_{rl}(x,y,\mathcal{G})\end{split}$ (1)

Here, $\mathcal{L}_{cfl}$ denotes CFL and $\mathcal{L}_{rl}$ denotes RL. The
terms $\lambda_{\mathcal{G}}$ and $\lambda_{\mathcal{R}}$ are the coefficients
of CFL and RL. We have pictorially shown CFL and RL in Fig. 3. The total loss
described in Eq. 1 compares the image features in two ways: CFL and RL. CFL
provides new image features to $y$, which are consistent with the object
context of $x$. RL maximizes the likelihood of randomly initialized network
weights.

####  3.2.1 Contextual Features Loss (CFL)

The purpose of CFL is to learn the distribution of context vectors to
synthesize image features in $y$ based on the semantics of the input $x$. We
extract context vectors $\phi(x)$ and $\phi(y)$ and then minimize the loss
described in Eq. 2.

$\begin{split}\mathcal{L}_{cfl}(x,y,\mathcal{G},\mathcal{D},\phi)=\lambda_{cal}&\mathcal{L}_{cal}(\mathcal{G},\mathcal{D};\phi)\\\
&+\lambda_{cvl}\mathcal{L}_{cvl}(\phi(x),\phi(y))\end{split}$ (2)

Here, $\mathcal{L}_{cfl}$ denotes CFL, $\mathcal{L}_{cal}$ denotes CAL, and
$\mathcal{L}_{cvl}$ denotes CVL. $\lambda_{cal}$ and $\lambda_{cvl}$ are the
coefficients of CAL and CVL. Eq. 2 shows that CFL compares the context vectors
in two ways. (1) Context vector comparison in the adversarial framework using
CAL. (2) Contextual features comparison by computing cosine distance in CVL.
CAL is an adversarial loss computed using the generator $\mathcal{G}$ and the
discriminator $\mathcal{D}$. It is aimed to synthesize new contextual features
that are indistinguishable from the features of the source image. The CVL
computes the difference between contextually similar vectors to make the
synthesized features of $y$ similar to the features of $x$.

Context Adversarial Loss (CAL). We have used the LSGAN [20] variant of the
adversarial learning framework.

$\mathcal{G}^{*}=\min_{\mathcal{G}}\max_{\mathcal{D}}\mathcal{L}_{cal}(\mathcal{G},\mathcal{D};\phi)$
(3)

Here, $\mathcal{G}^{*}$ is the generator with optimal parameters. The loss
$\mathcal{L}_{cal}$ is defined in Eq. 4.

$\begin{split}\mathcal{L}_{cal}(\mathcal{G},\mathcal{D};\phi)=&\mathbb{E}_{x\sim
pdata(x)}[(\mathcal{D}(\phi(x))-1)^{2}]\\\ &+\mathbb{E}_{x\sim
pdata(x)}[\mathcal{D}(\phi(\mathcal{G}(x)))^{2}]\end{split}$ (4)

Eq. 4 shows the distribution matching of context vectors of the restored image
$\phi(y)=\phi(\mathcal{G}(x))$ and context vectors of the corrupted image
$\phi(x)$. The discriminator $\mathcal{D}$ tries to determine whether the
context vectors are from $x$ or $y$ (see Fig. 3 and Fig. 3). Intuitively, this
would help us to fill the context of the masked regions of $y=\mathcal{G}(x)$
by learning the context of the objects in unmasked areas in $x$. We have
described $\mathcal{G}$, $\mathcal{D}$, and $\phi$ in Sec. 3.1.

Context Vector Loss (CVL). The main purpose of CVL is to improve the quality
of contextual features in $\phi(y)$ learned by CAL.
$\mathcal{L}_{cvl}(\phi_{l}(x),\phi_{l}(y))$ is the sum of the contextual loss
[23] computed at each layer $l$ in $\phi$. We have defined CVL for layer $l$
in Eq. 5.

$\mathcal{L}_{cvl}(\phi_{l}(x),\phi_{l}(y),l)=-\log(CX(\phi_{l}(x),\phi_{l}(y)))$
(5)

Here, $CX$ is the contextual similarity defined using the cosine distance
between the features contained in $\phi_{l}(x)$ and $\phi_{l}(y)$. Note that
$CX$ is computed by finding for each feature $\phi_{l}(y)_{j}$, a feature
$\phi_{l}(x)_{i}$ that is most similar to it and then summed for all
$\phi_{l}(y)_{j}$. Fig. 3 illustrate the matched context vectors of
$\phi_{l}(x)_{i}$ and $\phi_{l}(y)_{j}$ by an arrow. Intuitively, the feature
matching performed between the context vectors of masked regions of $y$ and
the context vectors of unmasked regions of $x$ enables feature refinements for
the new context vectors created by CAL. We used $conv4\\_2$ layer of $\phi$ to
compute context vectors as the higher layers capture the high-level content in
terms of objects structure [12]. It is interesting to note that CVL is
different from perceptual loss $\|\phi_{l}(x)-\phi_{l}(y)\|$, which computes
features difference without using contextual similarity criterion.

####  3.2.2 Reconstruction Loss (RL).

RL is aimed to preserve image features and it is computed between corrupted
image $x$ and restored image $\mathcal{G}(x)=y$ (Fig. 3). Let
$\mathcal{L}_{rl}$ denotes RL. We define $\mathcal{L}_{rl}$ in Eq. 6.

$\mathcal{L}_{rl}(\mathcal{G},x,y)=\|\mathcal{G}(x)\odot m-x\|$ (6)

Eq. 6 shows the comparison between unmasked regions of $x$ with the unmasked
regions of $y$. The unmasked regions in $x$ contains image features from $I$
and masked regions in $x$ are corrupted due to mask, i.e., $x=I\odot m$. RL is
a pixel-wise loss and it imposes a strong self-similarity prior [35].

(a) Original image

(b) Corrupted

(c) DIP, 0.90

(d) MEDS, 0.89

(e) InGAN, 0.90

(f) DeepCFL, 0.91

Figure 5:  Inpainting. The figure shows the inpainting of arbitrary holes for
DIP [35], MEDS [7], InGAN [28], and DeepCFL (ours). DeepCFL minimize the
features spillover of trees and attains better perceptual quality.

##  4 Applications

Here, we discuss the following applications of DeepCFL. (1) Image outpainting:
extension of an image along the sides. (2) Image inpainting of irregular holes
in the image. (3) Content-aware image resizing: synthesis of new objects when
we resize an image. (4) Restoration in the presence of high degree of
corruption: $50\%$ pixels111We have used original implementations of DIP [35],
MEDS [7], and DCIL [8]. We implemented image restoration using the internal
learning of InGAN [28]. We have provided the implementation details in the
supplementary material..

###  4.1 Image Outpainting.

Image outpainting relates to image extension, which creates new features while
maintaining the semantics of the scene. Image extension uses training data to
learn image context and then generates the complete scene given partial
information [37, 34, 39, 25]. Our outpainting task does not use any training
samples and synthesize features using only the corrupted image. We address
outpainting as an image extension for convenience.

A good image outpainting approach would fill the image features based on the
semantics of the object present at the boundaries. The ability of the
generator to synthesize new contextual features over a large spatial extent
along the sides depends upon the contextual learning. Unlike pixel-to-pixel
loss, the context vectors based loss functions CFL (Eq. 2) aims to fill new
features in the masked regions of the restored image, which are semantically
similar to the unmasked regions of the corrupted image (refer Sec. 3).

In Fig. 4, we show outpainting of 20% missing pixels, where the corrupted
image is generated by removing 10% pixels along the right side and the left
side. DIP [35], MEDS [7], and InGAN [28] are contextual features learning
independent methods. Image outpainting is better achieved using the semantics
of the objects in the contextual learning-based DeepCFL framework. Table 1
shows the quantitative comparison on the standard datasets from [14], Set5 and
Set14 datasets [7]. It could be observed that DeepCFL outperforms the other
methods for outpainting. We have provided more details in the supplementary
material.

|  DIP [35] |  MEDS [7] |  InGAN [28] | DeepCFL
---|---|---|---|---
SD |  | 0.91
---
23.73
| 0.91
---
21.70
| 0.92
---
22.89
| 0.92
---
24.13
Set14 |  | 0.89
---
22.12
| 0.89
---
20.24
| 0.90
---
21.19
| 0.90
---
22.52
Set5 |  | 0.88
---
19.03
| 0.88
---
19.35
| 0.89
---
19.29
| 0.90
---
21.50

Table 1: Quantitative comparision using SSIM values (top) and PSNR values
(bottom) for image outpainting of 20% pixels on standard dataset (SD), Set5
and Set14 datasets.

(a) Input

(b) Seam Carving [2]

(c) InGAN [28]

(d) DCIL [8]

(e) DeepCFL (ours)

Figure 6: Image Resize. The figure shows the synthesis of small objects
(fruits) and large objects (building). Seam Carving (SC) [2] does not preserve
the structure well when resizing. For example, the shape of the fruits in
small object synthesis is deformed in SC output. InGAN [28] preserve the
structure for small objects but does not preserve for large object (building).
DCIL [8] synthesizes new objects when resizing. For example, object structure
is preserved well when scaling $2\times$ along the width of the building.
DeepCFL also preserves object structure when synthesizing new objects. It
could be observed that DeepCFL does not duplicate the objects along the
expended dimension. For example, DeepCFL synthesizes the fruits when resizing
(the images are best viewed after zooming).

(a) Original

(b) Corrupted

(c) DIP, 0.87

(d) MEDS, 0.92

(e) InGAN, 0.93

(f) DeepCFL, 0.93

Figure 7:  RestoreWC 50%. The figure shows restoration in the presence of a
word cloud. DeepCFL restore image features details comparable to DIP [35],
MEDS [7], and InGAN [28].

###  4.2 Image Inpainting.

The input image has non-uniform corrupted regions spread across the entire
image in the inpainting task. It is a natural way by which an image could get
corrupted [19, 26]. The critical property to perform inpainting without using
training data is to utilize the internal self-similarity property of the
natural images [35, 42]. The computation of the MSE between the generator
output and the corrupted image tends to capture strong self-similarity prior
[35]. DeepCFL leverages this learning by incorporating the context vectors
comparison. The features learning procedure for inpainting is similar to
outpainting described in Sec 4.1.

Fig. 5 shows the visual results for arbitrary hole inpainting. It could be
observed that the contextual learning of DeepCFL minimizes the features
spillover between different objects and fill the arbitrary holes considering
the semantics of the image. The quantitative comparison (SSIM) for inpainting
is as follows: DIP [35]: 0.90, MEDS [7]: 0.88, InGAN [29] 0.90, and DeepCFL
(ours): 0.91. We have provided more comparisons of generated images in the
supplementary material. DeepCFL performs comparably to other frameworks. The
estimation of the parameters from a single image is highly sensitive to the
hyper-parameters (e.g., learning rate) [35, 7]. We believe that the
restoration quality of our method and other methods could be improved further
using the hyper-parameter search.

(a) Input

(b) InGAN [29]

(c) DCIL [8]

(d) DeepCFL

Figure 8: The challenge is to synthesize a new object [29, 8]. DeepCFL
observed that object synthesis is achievable at a different scale, similar to
DCIL[8]. DeepCFL output image with better features near the elbow, but the
background is not clear.

###  4.3 Image Resize

We have discussed image outpainting, which is different from content-aware
image resize, where the task is to resize the image while preserving the
salient objects of the image [29]. DeepCFL is able to synthesize new objects
when resizing the input image (Fig. 6). The source image is scaled $2\times$
along the height and the width. Therefore, the pixel correspondence between
the source and the generated target images is not well defined. The image
resize is done by using the generator to scale the input and then computing
the adversarial loss in a cycle consistent way.

Fig. 8 show the challenging scenario of object synthesis for various single
image GAN frameworks. Inspired by InGAN [29], our framework DeepCFL studies
deep contextual features. DeepCFL is different from DCIL [8] as it uses the
adversarial framework on VGG features space for image outpainting. In
contrast, DCIL uses the adversarial framework on the image space for
Denoising-super resolution. We believe that the results of various single
image GAN framework in Fig. 8 could be improvised further.

###  4.4 Restoration of $50\%$ pixels.

To investigate contextual features leaning in the presence of a high degree of
corruption, we perform restoration of $50\%$ missing pixels spread across the
entire image uniformly at random. It is a different setup than outpainting and
inpainting, where one has to fill a missing region (i.e., a contiguous array
of pixels). We further increase the task difficulty by using the corrupted
image containing a word cloud. We denote the above setup as RestoreWC 50% (WC
denotes word-cloud). It is a challenging setup because the small font present
in the corrupted image would require to fill fine image features details.

We show image restoration in RestoreWC 50% setup in Fig. 7. The quantitative
comparison (SSIM) for RestoreWC 50% is as follows. DIP [35]: 0.92, MEDS [7]:
0.93, InGAN [29]: 0.92, and DeepCFL (ours): 0.92. It could be observed that
DeepCFL performs comparably to other frameworks. It might be because the image
features computed from the highly corrupted image might not be sufficient for
restoration in the single image GAN framework. Therefore, contextual learning
is a bit less effective. We believe that the pixel-based loss would not have
the object synthesis abilities of the single image GAN frameworks (Fig. 8).

(a) Original
image

(b) Corrupted
image

(c) DIP [35]

(d) DIP[35]
\+ CL

(e) DeepCFL

Figure 9: Ablation study (1). The figure shows the outpainting of 20% pixels.
DIP is a pixel-loss based setup. We integrated contextual loss (CL) with DIP
[35] in “DIP [35] \+ CL” to show image restoration using CL and without GAN
framework. DeepCFL is a GAN framework and it is observed to restore image
features well.

##  5 Ablation Studies and Limitations

We show the usefulness of contextual learning in the adversarial framework in
Fig. 9. The restored image features are highlighted in the cropped images. It
could be observed that the single image GAN framework (DeepCFL) synthesizes
image features for image restoration.

In Fig. 10, we show an ablation study to disentangle the reconstruction using
context vector loss (CVL), context adversarial loss (CAL), and contextual
features loss (CFL) as defined in Sec. 3.2. The CFL setup performs better as
it uses adversarial learning and context vector learning together.

Fig. 12 shows the restoration in the presence of two discriminator
architectures setup: single scale discriminator (SSD) and multiscale
discriminator (MSD). InGAN [29] shows that MSD improves the performance
significantly for image synthesis. We observed that higher model capacity did
not significantly improve image restoration, similar to [7] as the masked SSIM
for SSD setup is (0.971) is close to MSD setup (0.976). The visual performance
enhancement would be because MSD setup enforces image statistics consistency
at multiple levels, which is harder than solving at a single scale SSD setup.
Our intuition is that solving a hard problem would help to learn better image
features [7]. Moreover, quantitative enhancement is close. Our interpretation
of it is as follows. MSD in DeepCFL is operating on the context vectors. The
scaling of the context vectors in MSD of DeepCFL and scaling the image in [29,
27, 8] are completely different operations. The performance enhancement for
image restoration using the scaling of context vector might not be very
effective.

Fig. 13 shows the reconstruction when the information in the corrupted image
is not sufficient to fill the missing regions. The limitation is due to the
lack of feature learning from the training samples in the single image GAN
framework. A similar limitation has also been reported for image manipulation
tasks [27]. Restoration of an object which is partially present in the image
would also be exciting. However, it is not within the scope of this work.

Fig. 14 shows the the restoration of 90% pixels ($r=90$) using image features
learning from 10% pixels. It could be observed that it is difficult to
understand the semantics of the scene from 10% pixels. The experiment confirms
our observation that the adversarial learning of image context is less
effective for the high degree of corruption. We show more results in the
supplementary material.

(a) Original
image

(b) Masked
image

(c) CAL,
0.88

(d) CVL,
0.91

(e) CFL,
0.92

Figure 10: Ablation study (2). The input is the masked image, which contains
50% corrupted pixels. Here, the contextual feature loss CFL = CAL + CVL. It
could be observed that CAL and CVL together enhance the restoration quality in
CFL.

(a) Original

(b) Masked

(c) SSD

(d) MSD

Figure 12: Ablation study (3). The figure shows text removal in the presence
of single-scale discriminator (SSD) and multi-scale discriminators (MSD)
setups. SSD setup makes thin marks in the restored output, which are a bit
less detectable in the MSD setup.

(a) Original

(b) Masked

(c) DIP [35]

(d) DeepCFL

Figure 13: Limitation (1). The aim is to restore a partially present object in
the corrupted image (i.e., head). The features in the masked image is not
enough to restore head in the mirror. Therefore, we could observe that the
reconstruction using DIP [35] and DeepCFL is not performed well.

(a) Real
image

(b) Masked
image

(c) DIP
0.92

(d) MEDS
0.91

(e) InGAN
0.91

(f) DeepCFL 0.91

Figure 14: Limitation (2). The figure shows the restoration of 90% pixels.
DeepCFL preserves the image features comparable to DIP [35], MEDS [7], and
InGAN [28].

##  6 Discussion

DeepCFL is a single image GAN framework. The data-driven supervised feature
learning setups use paired examples of ground truth (GT) and corrupted images.
The corrupted images are fed into the network and generated outputs are
matched with the GT image. DeepCFL is not trained by showing training samples
of GT and corrupted images. DeepCFL can be fairly compared only with training
data-independent methods as they also do not use training samples. Training
based methods could synthesize image feature details that are not present in
the input image, which is not possible in the training data-independent setups
(Fig. 13 and Fig. 14). The feature extractor VGG-19 contains layers at
different scales, where each layer contains varying levels of abstractions. We
believe that combining features from various VGG-19 layers would be helpful.
Moreover, it would increase the model complexity. The scope of DeepCFL is
limited to the contextual features present in $conv4\\_2$ layer. We propose as
future work to perform studies on how to increase VGG19 layers for feature
comparison while minimizing the computational overhead.

##  7 Conclusion

We investigate deep contextual features learning (CFL) in the single image GAN
framework for image restoration and image synthesis. The main challenge to
accomplish the above tasks is when the information contained in the input
image is not sufficient for synthesizing the necessary image features. DeepCFL
synthesizes image features based on the semantics to perform outpainting,
inpainting, restoration of $r\%$ pixels, and image resizing. It would be
interesting to study the performance of the single image GAN framework in the
setting of videos similar to [42, 16].

Acknowledgments. Indra Deep Mastan was supported by Visvesvaraya Ph.D.
fellowship. Shanmuganathan Raman was supported by SERB Core Research Grant and
SERB MATRICS.

## References

  * [1] Michal Aharon, Michael Elad, Alfred Bruckstein, et al.  K-svd: An algorithm for designing overcomplete dictionaries for sparse representation.  IEEE Transactions on signal processing, 54(11):4311, 2006.
  * [2] Shai Avidan and Ariel Shamir.  Seam carving for content-aware image resizing.  In ACM Transactions on graphics (TOG), volume 26, page 10. ACM, 2007\.
  * [3] Siavash Arjomand Bigdeli and Matthias Zwicker.  Image restoration using autoencoding priors.  arXiv preprint arXiv:1703.09964, 2017.
  * [4] Antoni Buades, Bartomeu Coll, and J-M Morel.  A non-local algorithm for image denoising.  In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 2, pages 60–65. IEEE, 2005.
  * [5] Harold C Burger, Christian J Schuler, and Stefan Harmeling.  Image denoising: Can plain neural networks compete with bm3d?  In 2012 IEEE conference on computer vision and pattern recognition, pages 2392–2399. IEEE, 2012.
  * [6] Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian.  Image denoising by sparse 3-d transform-domain collaborative filtering.  IEEE Transactions on image processing, 16(8):2080–2095, 2007.
  * [7] Indra Deep Mastan and Shanmuganathan Raman.  Multi-level encoder-decoder architectures for image restoration.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 0–0, 2019.
  * [8] Indra Deep Mastan and Shanmuganathan Raman.  Dcil: Deep contextual internal learning for image restoration and image retargeting.  WACV, 2020.
  * [9] Weisheng Dong, Lei Zhang, Guangming Shi, and Xin Li.  Nonlocally centralized sparse representation for image restoration.  IEEE transactions on Image Processing, 22(4):1620–1630, 2012.
  * [10] Alexei A Efros and Thomas K Leung.  Texture synthesis by non-parametric sampling.  In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pages 1033–1038. IEEE, 1999.
  * [11] Michael Elad and Michal Aharon.  Image denoising via sparse and redundant representations over learned dictionaries.  IEEE Transactions on Image processing, 15(12):3736–3745, 2006.
  * [12] Leon A Gatys, Alexander S Ecker, and Matthias Bethge.  Image style transfer using convolutional neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2414–2423, 2016.
  * [13] Shuhang Gu, Qi Xie, Deyu Meng, Wangmeng Zuo, Xiangchu Feng, and Lei Zhang.  Weighted nuclear norm minimization and its applications to low level vision.  International journal of computer vision, 121(2):183–208, 2017\.
  * [14] Felix Heide, Wolfgang Heidrich, and Gordon Wetzstein.  Fast and flexible convolutional sparse coding.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5135–5143, 2015.
  * [15] Daniel Glasner Shai Bagon Michal Irani.  Super-resolution from a single image.  In Proceedings of the IEEE International Conference on Computer Vision, Kyoto, Japan, pages 349–356, 2009.
  * [16] Dahun Kim, Sanghyun Woo, Joon-Young Lee, and In So Kweon.  Deep video inpainting.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5792–5801, 2019.
  * [17] Christian Ledig, Lucas Theis, Ferenc Huszar, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, and Wenzhe Shi.  Photo-realistic single image super-resolution using a generative adversarial network.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [18] Anat Levin.  Blind motion deblurring using image statistics.  In Advances in Neural Information Processing Systems, pages 841–848, 2007.
  * [19] Guilin Liu, Fitsum A Reda, Kevin J Shih, Ting-Chun Wang, Andrew Tao, and Bryan Catanzaro.  Image inpainting for irregular holes using partial convolutions.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 85–100, 2018.
  * [20] Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley.  Least squares generative adversarial networks.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2794–2802, 2017.
  * [21] Gary Mataev, Peyman Milanfar, and Michael Elad.  Deepred: Deep image prior powered by red.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 0–0, 2019.
  * [22] Roey Mechrez, Itamar Talmi, Firas Shama, and Lihi Zelnik-Manor.  Learning to maintain natural image statistics.  arXiv preprint arXiv:1803.04626, 2018.
  * [23] Roey Mechrez, Itamar Talmi, and Lihi Zelnik-Manor.  The contextual loss for image transformation with non-aligned data.  European Conference on Computer Vision (ECCV), 2018.
  * [24] Kamyar Nazeri, Eric Ng, Tony Joseph, Faisal Z Qureshi, and Mehran Ebrahimi.  Edgeconnect: Generative image inpainting with adversarial edge learning.  arXiv preprint arXiv:1901.00212, 2019.
  * [25] Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros.  Context encoders: Feature learning by inpainting.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2536–2544, 2016.
  * [26] Yurui Ren, Xiaoming Yu, Ruonan Zhang, Thomas H Li, Shan Liu, and Ge Li.  Structureflow: Image inpainting via structure-aware appearance flow.  In Proceedings of the IEEE International Conference on Computer Vision, pages 181–190, 2019.
  * [27] Tamar Rott Shaham, Tali Dekel, and Tomer Michaeli.  Singan: Learning a generative model from a single natural image.  The IEEE International Conference on Computer Vision (ICCV), 2019\.
  * [28] Assaf Shocher, Shai Bagon, Phillip Isola, and Michal Irani.  Internal distribution matching for natural image retargeting.  arXiv preprint arXiv:1812.00231, 2018.
  * [29] Assaf Shocher, Shai Bagon, Phillip Isola, and Michal Irani.  Ingan: Capturing and remapping the “dna” of a natural image.  In International Conference on Computer Vision (ICCV), 2019.
  * [30] Assaf Shocher, Nadav Cohen, and Michal Irani.  “zero-shot” super-resolution using deep internal learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3118–3126, 2018.
  * [31] Oleksii Sidorov and Jon Yngve Hardeberg.  Deep hyperspectral prior: Single-image denoising, inpainting, super-resolution.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 0–0, 2019.
  * [32] Denis Simakov, Yaron Caspi, Eli Shechtman, and Michal Irani.  Summarizing visual data using bidirectional similarity.  In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2008.
  * [33] Jian Sun, Zongben Xu, and Heung-Yeung Shum.  Image super-resolution using gradient profile prior.  In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2008.
  * [34] Piotr Teterwak, Aaron Sarna, Dilip Krishnan, Aaron Maschinot, David Belanger, Ce Liu, and William T Freeman.  Boundless: Generative adversarial networks for image extension.  arXiv preprint arXiv:1908.07007, 2019.
  * [35] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Deep image prior.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [36] Ting-Chun Wang, Ming-Yu Liu, Jun-Yan Zhu, Andrew Tao, Jan Kautz, and Bryan Catanzaro.  High-resolution image synthesis and semantic manipulation with conditional gans.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [37] Yi Wang, Xin Tao, Xiaoyong Shen, and Jiaya Jia.  Wide-context semantic image extrapolation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1399–1408, 2019.
  * [38] Chao Yang, Xin Lu, Zhe Lin, Eli Shechtman, Oliver Wang, and Hao Li.  High-resolution image inpainting using multi-scale neural patch synthesis.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, page 3, 2017.
  * [39] Zongxin Yang, Jian Dong, Ping Liu, Yi Yang, and Shuicheng Yan.  Very long natural scenery image prediction by outpainting.  In Proceedings of the IEEE International Conference on Computer Vision, pages 10561–10570, 2019.
  * [40] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang.  Generative image inpainting with contextual attention.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5505–5514, 2018.
  * [41] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang.  Free-form image inpainting with gated convolution.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4471–4480, 2019.
  * [42] Haotian Zhang, Long Mai, Ning Xu, Zhaowen Wang, John Collomosse, and Hailin Jin.  An internal learning approach to video inpainting.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2720–2729, 2019.
  * [43] Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang.  Learning deep cnn denoiser prior for image restoration.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [44] Lei Zhang and Wangmeng Zuo.  Image restoration: From sparse and low-rank priors to deep priors [lecture notes].  IEEE Signal Processing Magazine, 34(5):172–179, 2017.
  * [45] Maria Zontak and Michal Irani.  Internal statistics of a single natural image.  In CVPR 2011, pages 977–984. IEEE, 2011.
  * [46] Daniel Zoran and Yair Weiss.  From learning models of natural image patches to whole image restoration.  In 2011 International Conference on Computer Vision, pages 479–486. IEEE, 2011.