0.8pt

# Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses,
and Algorithms

Fanchen Bu
KAIST EE
Deajeon, Republic of Korea
<EMAIL_ADDRESS>
&Ruochen Yang, Paul Bogdan
USC ECE
CA, United States
<EMAIL_ADDRESS>
&Kijung Shin
KAIST AI & EE
Seoul, Republic of Korea
<EMAIL_ADDRESS>

###### Abstract

Desirable random graph models (RGMs) should (i) be tractable so that we can
compute and control graph statistics, and (ii) generate realistic structures
such as high clustering (i.e., high subgraph densities). A popular category of
RGMs (e.g., Erdős-Rényi and stochastic Kronecker) outputs edge probabilities,
and we need to realize (i.e., sample from) the edge probabilities to generate
graphs. Typically, each edge (in)existence is assumed to be determined
independently. However, with edge independency, RGMs theoretically cannot
produce high subgraph densities unless they “replicate” input graphs. In this
work, we explore realization beyond edge independence that can produce more
realistic structures while ensuring high tractability. Specifically, we
propose edge-dependent realization schemes called binding and derive closed-
form tractability results on subgraph (e.g., triangle) densities in graphs
generated with binding. We propose algorithms for graph generation with
binding and parameter fitting of binding. We empirically validate that binding
exhibits high tractability and generates realistic graphs with high
clustering, significantly improving upon existing RGMs assuming edge
independency.

##  1 Introduction

Random graph models (RGMs) help us understand and analyze real-world systems
(Drobyshevskiy & Turdakov, 2019), and are used as benchmarks (Murphy et al.,
2010) for graph algorithms. Desirable RGMs should allow us to control graph
statistics, and generate graphs with realistic patterns, such as high
clustering,111“High clustering” means high subgraph densities, as used by,
e.g., Newman (2003) and Pfeiffer et al. (2012). power-law degrees, and small
diameters (Chakrabarti & Faloutsos, 2006).

A large number of RGMs outputs individual edge probabilities and generate
graphs accordingly, e.g., the Erdős-Rényi model (Erdős & Rényi, 1959), the
Chung-Lu model (Chung & Lu, 2002), the stochastic block model (Holland et al.,
1983), and the stochastic Kronecker model (Leskovec et al., 2010). To generate
graphs from edge probabilities, we need realization (i.e., sampling), where
edge independency (i.e., the edge (in)existences are determined mutually
independently) is widely assumed for the sake of simplicity and tractability.
However, RGMs with edge independency empirically fail to preserve some
realistic patterns, especially high clustering (Moreno et al., 2018; Seshadhri
et al., 2013). Moreover, edge-independent RGMs are theoretically unable to
generate graphs with high triangle density, unless they replicate a whole
input graph (Chanpuriya et al., 2021).

Naturally, we ask the following question: Can we apply realization without
assuming edge independency so that we can improve upon such RGMs while still
ensuring high tractability? To address this question, in this work, we explore
edge probability graph models (EPGMs) beyond edge independency, from both
theoretical and practical perspectives. Our key message is a positive answer
to the question. Specifically, our novel contributions are four-fold:

  1. 1.

Concepts (Section 4): We formally define EPGMs with related concepts, and
theoretically show some basic properties of EPGMs, e.g., each EPGM, even with
edge dependency introduced, has the same variability in the generated graphs
as the corresponding edge-independent model.

  2. 2.

Analyses (Section 5): We propose realistic, tractable, and flexible
realization schemes called binding to construct EPGMs with different levels of
edge dependency, and derive tractability results on the closed-form subgraph
(e.g., triangle) densities.

  3. 3.

Algorithms (Section 5): We propose practical algorithms for graph generation
with binding, and for efficient parameter fitting to control the graph
statistics generated by EPGMs with binding.

  4. 4.

Experiments (Section 6): We use our binding and fitting algorithms to generate
graphs. Via experiments on real-world graphs, we show the power of edge
dependency to preserve realistic graph patterns and validate the correctness
of our theoretical analyses and practical algorithms.

Reproducibility.whiteReproducibility. The code and datasets are available in
the online appendix (Anonymous, 2024).

##  2 Preliminaries

Graphs.whiteGraphs. A node-labelled graph $G=(V,E)$ is defined by a node set
$V=V(G)$ and an edge set $E=E(G)\subseteq\binom{V}{2}$. 222In this work, we
consider undirected unweighted graphs without self-loops following common
settings for random graph models. See Section E.1 for discussions on more
general graphs. For a node $v\in V$, the neighbors of $v$ are the nodes $u$
such that $(u,v)\in E(G)$, denoted as $N(v;G)=\\{u\in V\colon(u,v)\in
E(G)\\}$. The degree $d(v;G)$ of $v$ is the number of its neighbors, i.e.,
$d(v;G)=\left|N(v;G)\right|$. Given $V^{\prime}\subseteq V$, the induced
subgraph of $G$ on $V^{\prime}$ is
$G[V^{\prime}]=(V^{\prime},E\cap\binom{V^{\prime}}{2})$.

Random graph models (RGMs).whiteRandom graph models (RGMs). Fix a node set
$V=[n]=\\{1,2,\ldots,n\\}$. Let $\mathcal{G}(V)=\\{G=(V,E)\colon
E\subseteq\binom{V}{2}\\}$ denote the set of all $2^{\binom{n}{2}}$ possible
node-labelled graphs on $V$.

######  Definition 2.1 (RGMs and edge probabilities).

Given a node set $V=[n]$ with $n\in\mathbb{N}$, a random graph model (RGM) is
defined as a probability distribution $f:\mathcal{G}(V)\to[0,1]$ with
$\sum_{G\in\mathcal{G}(V)}f(G)=1$. For each graph $G\in\mathcal{G}(V)$, $f(G)$
is the probability of $G$ being generated by the RGM $f$. For each node pair
$(u,v)$ with $u,v\in V$, the edge probability of $(u,v)$ under the RGM $f$ is
$\Pr_{f}[(u,v)]\coloneqq\sum_{G\in\mathcal{G}(V)}f(G)\mathbf{1}[(u,v)\in
E(G)]$, where $\mathbf{1}[\cdot]$ is the indicator function.

Edge independent graph models (EIGMs).whiteEdge independent graph models
(EIGMs). Given edge probabilities, edge independency is widely assumed in many
existing RGMs, resulting in the concept of EIGMs (also known as inhomogeneous
Erdős-Rényi graphs (Klopp et al., 2017)).

######  Definition 2.2 (EIGMs (Chanpuriya et al., 2021)).

Given $p\colon\binom{V}{2}\to[0,1]$, the edge independent graph model (EIGM)
w.r.t. $p$ is the RGM $f^{\text{EI}}_{p}$ defined by
$f^{\text{EI}}_{p}(G)=\prod_{(u,v)\in
E(G)}p(u,v)\prod_{(u^{\prime},v^{\prime})\notin
E(G)}(1-p(u^{\prime},v^{\prime})),\forall G\in\mathcal{G}(V)$.

##  3 Related work and background

###  3.1 Limitations of EIGMs

This work is motivated by the theoretical findings of Chanpuriya et al. (2021)
on the limitations of EIGMs. They defined the concept of overlap to measure
the variability of RGMs, where a high overlap value implies low variability.
Roughly speaking, the overlap of an RGM is the expected proportion of edges
co-existing in two graphs generated by the RGM.

######  Definition 3.1 (Overlap (Chanpuriya et al., 2021)).

Given an RGM $f:\mathcal{G}(V)\to[0,1]$, the overlap of $f$ is defined as
$\operatorname{Ov}(f)=\frac{\mathbb{E}_{f}\left|E(G^{\prime})\cap
E(G^{\prime\prime})\right|}{\mathbb{E}_{f}\left|E(G)\right|}$, where $G$,
$G^{\prime}$, and $G^{\prime\prime}$ are three mutually independent random
graphs generated by $f$.

######  Remark 3.2.

High variability (i.e., low overlap) is important for RGMs, since obtaining
almost identical graphs by simply duplicating input graphs is not meaningful.

Chanpuriya et al. (2021) showed that EIGMs are unable to generate graphs with
high triangle density (i.e., with many triangles) unless EIGMs memorize a
whole input graph (i.e., have high overlap).

######  Theorem 3.3 (EIGMs generate limited triangles (Chanpuriya et al.,
2021)).

For any $p\colon\binom{V}{2}\to[0,1]$,
$\mathbb{E}_{f^{\text{EI}}_{p}}[\triangle(G)]\leq\frac{\sqrt{2}}{3}\left(\operatorname{Ov}(f^{\text{EI}}_{p})\sum_{(u,v)\in\binom{V}{2}}p(u,v)\right)^{3/2}$,
where $\triangle(G)$ is the number of triangles in $G$.

Chanpuriya et al. (2023) recently extended their theoretical results, showing
triangle-density upper bounds w.r.t. overlap in different types of edge-
dependent RGMs.333In EPGMs, the overlap is constant yet we can have different
triangle densities. See Proposition 4.7. However, neither detailed
tractability results nor practical graph generation algorithms were
provided,444Their graph generation algorithm is not practical since it relies
on maximal clique enumeration, which is time-consuming (Eblen et al., 2012).
See Section E.2 for more discussions. while tractability results and practical
graph generation are our focus in this work.

There exist methods that shift edge probabilities by accept-reject (Mussmann
et al., 2015) or mixing different EIGMs (Kolda et al., 2014), in order to
improve upon existing EIGMs. Such methods are essentially still EIGMs, and by
Theorem 3.3, they inevitably have high overlap (i.e., low variability). See
Section F.6 for more discussion and empirical evaluation on such methods.

###  3.2 Edge dependency in RGMs

Edge dependency exists in various RGMs, including preferential attachment
models (Barabási & Albert, 1999), small-world graphs (Watts & Strogatz, 1998),
copying network models (Kleinberg et al., 1999), and exponential random graph
models (Lusher et al., 2013). Some models use additional mechanisms to
introduce edge dependency by, e.g., directly forming triangles (Pfeiffer et
al., 2012; Wegner & Olhede, 2021). Such models show the power of edge
dependency, especially in generating graphs with high clustering. However,
they are not based on edge probabilities, and obtaining tractability results
on them is often challenging (Drobyshevskiy & Turdakov, 2019).

##  4 Edge probability graph models (EPGMs): Concepts and basic properties

Given edge probabilities, EIGMs generate graphs assuming edge independency. In
contrast, we explore a broader class of edge probability graph models (EPGMs)
going beyond edge independency.

######  Definition 4.1 (EPGMs).

Given edge probabilities $p\colon\binom{V}{2}\to[0,1]$, the set of edge
probability graph models (EPGMs) w.r.t. $p$ is defined as
$\mathcal{F}(p)\coloneqq\\{f\colon\Pr_{f}[(u,v)]=p(u,v),\forall u,v\in V\\}$.

The concept of EPGMs decomposes each RGM into (F1) the marginal probability of
each edge and (F2) how the edge probabilities are realized (i.e., sampled),
and (F2) has been overlooked by EIGMs. Below, we show some basic properties of
EPGMs and discuss their meanings and implications.

######  Proposition 4.2.

EIGMs are special cases of EPGMs w.r.t. the same edge probabilities.

###### Proof.

See Appendix C for all the formal statements and proofs not covered in the
main text. ∎

######  Proposition 4.3.

Each RGM can be represented as an EPGM (w.r.t its marginal edge
probabilities).

Proposition 4.3 shows the generality of EPGMs, yet also implies the
impossibility of exploring all possible EPGMs, which motivates us to find good
subsets of EPGMs. Also, the generality of EPGMs is conditioned on individual
edge probabilities. What can we expect for given edge probabilities? We obtain
the upper bounds of expected subgraph densities in the graphs generated by
EPGMs.

######  Proposition 4.4 (Upper bound of edge-group probabilities in EPGMs).

For any $p\colon\binom{V}{2}\to[0,1]$ and any $P\subseteq\binom{V}{2}$,
$\Pr_{f}[P\subseteq E(G)]\leq\min_{(u,v)\in P}p(u,v),\forall
f\in\mathcal{F}(p)$.

######  Remark 4.5.

Later, we shall show that the upper bound in Proposition 4.4 is tight, i.e.,
we can find EPGMs achieving the upper bound (see Lemma 5.4).

Proposition 4.4 can be applied to obtain the upper bounds of the expected
number of specific subgraphs, e.g., cliques and cycles. Below is an example on
the number of triangles (i.e., $\triangle(G)$).

######  Corollary 4.6.

For any $p$,
$\mathbb{E}_{f}[\triangle(G)]\leq\sum_{\\{u,v,w\\}\in\binom{V}{3}}\min(p(u,v),p(u,w),p(v,w)),\forall
f\in\mathcal{F}(p)$.

######  Proposition 4.7 (EPGMs have constant expected degrees and overlap).

For any $p\colon\binom{V}{2}\to[0,1]$, the expected node degrees and overlap
(see Definition 3.1) of all the EPGMs w.r.t. $p$ are constant.

Proposition 4.7 implies that compared to EIGMs, considering more general EPGMs
neither changes expected degrees nor impairs the variability of the generated
graphs. As discussed in Remark 3.2, high variability is important and
desirable for random graphs.

In this work, we explore EPGMs from both theoretical and practical
perspectives, aiming to answer two research questions inspired by the basic
properties of EPGMs above:

  * •

(RQ1; Theory) How to find good subsets of EPGMs that are realistic, flexible,
and tractable?

  * •

(RQ2; Practice) How to generate graphs using such EPGMs and fit the parameters
of EPGMs?

##  5 Binding: Realistic, flexible, and tractable EPGMs

We aim to construct EPGMs that are realistic (i.e., high clustering) and
flexible (i.e., different levels of dependency), in a tractable (i.e.,
controllable graph statistics) way.

###  5.1 General binding: Realistic EPGMs with high subgraph densities

How to construct realistic EPGMs with high subgraph densities? We study
binding that introduces positive dependency among edges, where multiple edges’
(in)existences are determined together.

1 Input : (1) $p\colon\binom{V}{2}\to[0,1]$: edge probabilities; (2)
$\mathcal{P}$ s.t. $\binom{V}{2}=\bigcupdot_{P\in\mathcal{P}}P$: pair
partition  Output : $G$: generated graph 2 3$E\leftarrow\emptyset$ 4 for
_$P\in\mathcal{P}$_ do 5 $E\leftarrow E\cup\text{{{binding(}}{\emph{$p$,
$P$}}{{)}}}$ 6 7return _$G=(V,E)$_ 8Procedure  _binding(_$\hat{p}$ ,
$\hat{P}$_)_ 9 sample a random variable $s\sim\mathcal{U}(0,1)$ 10
$\hat{E}\leftarrow\emptyset$ 11 for  _$(u,v)\in\hat{P}$_ do 12 if
_$s\leq\hat{p}(u,v)$_ then 13 $\hat{E}\leftarrow\hat{E}\cup\\{(u,v)\\}$ 14 15
16 return _$\hat{E}$_ 17 Algorithm 1 General Binding

Formally, binding is the probabilistic process in Algorithm 1, where we have a
partition of all the pairs, and the node pairs in each group $P\in\mathcal{P}$
are bound together in that the (in)existences of the edges are determined
dependently. Note that, in our practical algorithms (Algorithms 2 and 3) to be
introduced later, we do not need to choose an explicit partition $\mathcal{P}$
beforehand.

There are two basic properties of binding: (i) binding is correct, i.e.,
generates EPGMs, and (ii) binding is realistic, i.e., improves subgraph
densities upon EIGMs.

######  Proposition 5.1.

Algorithm 1 with input $p$ (and any $\mathcal{P}$) produces an EPGM w.r.t.
$p$.

######  Proposition 5.2.

Binding produces higher or equal subgraph densities, compared to the
corresponding EIGMs.

######  Remark 5.3.

There are EPGMs with lower subgraph densities, which are against our
motivation to improve upon EIGMs w.r.t. subgraph densities and are out of this
work’s scope. That said, they may be useful in scenarios where dense subgraphs
are unwanted, e.g., disease control (Wong & Li, 2020).

With binding, we can construct EPGMs with different levels of edge dependency
by different ways of binding the node pairs. Let us first study two extreme
cases.

Minimal binding.whiteMinimal binding. EIGMs are the case with minimal binding,
i.e., without binding, where the partition contains only sets of a single
pair, i.e., $\mathcal{P}=\\{\\{(u,v)\\}\colon u,v\in V\\}$.

Maximal binding.whiteMaximal binding. Maximal binding corresponds to the case
with $\mathcal{P}=\\{\binom{V}{2}\\}$, i.e., all the pairs are bound together.
It achieves the upper bound of subgraph densities, i.e., the maximal edge-
group probabilities in Proposition 4.4, showing that the upper bound is tight,
as mentioned in Remark 4.5.

######  Lemma 5.4 (Maximal binding achieves maximum edge-group probabilities).

For any $p\colon\binom{V}{2}\to[0,1]$ and any edge-group
$P\subseteq\binom{V}{2}$,
$\Pr_{f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}}[P\subseteq E(G)]=\min_{(u,v)\in
P}p(u,v),\forall f\in\mathcal{F}(p)$, where $f^{\text{BD}}_{p;\mathcal{P}}$
denotes the RGM defined by
$f^{\text{BD}}_{p;\mathcal{P}}(G)=\Pr[\text{\lx@cref{creftype~refnum}{alg:binding_general}
outputs $G$ with inputs $p$ and $\mathcal{P}$}]$.

###  5.2 Local binding: Flexible and tractable spectrum between two extremes

Intuitively, the more pairs we bind together, the higher subgraph densities we
have. Between minimal binding (i.e., EIGMs) and maximal binding that achieves
the upper bound of subgraph densities, we can have a flexible spectrum.
However, the number of possible partitions of node pairs $\binom{V}{2}$ grows
exponentially w.r.t. $\left|V\right|$, which is hardly tractable. Hence, for
better tractability, we propose to introduce edge dependency without explicit
partitions. Specifically, we propose local binding, where we repeatedly sample
node groups,555We use independent node sampling (yet still with edge
dependency) which is simple, tractable, and works empirically well in our
experiments. See Section E.3 for more discussions. and bind pairs between each
sampled node group together. Pairs between the same node group are
structurally related, compared to pairs sharing no common nodes.

Real-world motivation.whiteReal-world motivation. In social networks, each
group “bound together” can represent a group interaction, e.g., an offline
social event (meeting, conference, party) or an online social event (group
chat, Internet forum, online game). In such social events, people gather
together, and the communications/relations between them likely co-occur. At
the same time, not all people in such events would necessarily communicate
with each other, e.g., some people are more familiar with each other. This is
the point of considering binding with various edge probabilities (instead of
just inserting cliques). See Section E.4 for more discussions.

Input : (1) $p\colon\binom{V}{2}\to[0,1]$: edge probabilities; (2) $g\colon
V\to[0,1]$: node-sampling probabilities; (3) $R$: maximum number of rounds for
binding  Output : $G$: generated graph
$\mathcal{P}\leftarrow\emptyset;i_{round}\leftarrow
0;P_{rem}\leftarrow\binom{V}{2}$ $\triangleright$ Initialization 1 while
_$P_{rem}\neq\emptyset$_ do 2 if  _$i_{round}=R$_ then break $\triangleright$
Reaching the round limit 3 4 $i_{round}\leftarrow i_{round}+1$ 5 sample
$V_{s}\subseteq V$ with $\Pr[v\in V_{s}]=g(v)$ independently  6
$P_{s}\leftarrow\binom{V_{s}}{2}\cap P_{rem}$ 7 if  _$P_{s}\neq\emptyset$_
then 8 $\mathcal{P}\leftarrow\mathcal{P}\cup\\{P_{s}\\}$ 9 $P_{rem}\leftarrow
P_{rem}\setminus P_{s}$ 10 11
12$\mathcal{P}\leftarrow\mathcal{P}\cup\\{\\{(u,v)\\}\colon(u,v)\in
P_{rem}\\}$ return _the output of Algorithm 1 with inputs $p$ and
$\mathcal{P}$ _ Algorithm 2 Local binding

In Algorithm 2, we repeatedly sample a subset of nodes (Algorithm 2) and group
the ungrouped pairs between the sampled nodes (Algorithm 2). We maintain
$P_{rem}$ to ensure disjoint partitions (Algorithms 2 and 2). For practical
usage, we consider a limited number (i.e., $R$) of rounds for binding
(Algorithms 2 and 2) otherwise it may take a long time to exhaust all the
pairs. Algorithm 2 is also a probabilistic process, and we use
$f^{\text{LB}}_{p;g,R}$ to denote the corresponding RGM, i.e.,
$f^{\text{LB}}_{p;g,R}(G)=\Pr[$Algorithm 2 outputs $G$ with inputs $p$, $g$,
and $R$]. As a special case of binding, local binding is also correct, i.e.,
generates EPGMs.

######  Proposition 5.5.

Algorithm 2 with input $p$ (and any $g$ and $R$) produces an EPGM w.r.t. $p$.

######  Remark 5.6.

We introduce node-sampling probabilities (i.e., $g$) to sample node groups
with better tractability, without explicit partitions. With higher node-
sampling probabilities, larger node groups are bound together, and the
generated graphs are expected to have higher subgraph densities. Specifically,
local binding forms a spectrum between the two extreme cases. When $g(v)\equiv
0$, local binding reduces to minimal binding, i.e., EIGMs. When $g(v)\equiv
1$, it reduces to maximal binding.

######  Theorem 5.7 (Time complexity of graph generation with local binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, $f^{\text{LB}}_{p;g,R}$ generates a graph in
$O(R\left(\sum_{v\in V}g(v)\right)^{2}+\left|V\right|^{2})$ time with high
probability,666That is, $\lim_{\left|V\right|\to\infty}\Pr[\text{it takes
$O(R\left(\sum_{v\in V}g(v)\right)^{2}+\left|V\right|^{2})$}]=1$. with the
worst case $O(R\left|V\right|^{2})$.

We derive tractability results of local binding on the closed-form expected
number of motifs (i.e., induced subgraphs; see Section 2). For this, we derive
the probabilities of all the possible motifs for each node group, then we can
compute the expected number of motifs by taking the summation over all
different node groups, which can be later used for parameter fitting (see
Section 5.4).

######  Theorem 5.8 (Tractable motif probabilities with local binding).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, $R\in\mathbb{N}$,
and $V^{\prime}=\\{u,v,w\\}\in\binom{V}{3}$, we can compute the closed-form
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}],\forall
E^{*}\subseteq\binom{V^{\prime}}{2}$, as a function w.r.t. $p$, $g$, and $R$
(the detailed formulae are in Section C.4).

###### Proof sketch.

We (1) consider all the sub-cases of how all the pairs are partitioned and
grouped, (2) compute the motif probabilities conditioned on each sub-case, and
(3) take the summation of motif probabilities in all the sub-cases. See
Appendix C.4 for the full proof and the detailed formulae. ∎

######  Remark 5.9.

Having closed-form formulae of motif probabilities allows us to estimate the
output and fit the parameters of RGMs (see Section 5.4). Theorem 5.8 can be
extended to larger $\left|V^{\prime}\right|$ with practical difficulties from
the increasing sub-cases as motif size increases. See Section C.4.

######  Theorem 5.10 (Time complexity of computing motif probabilities with
local binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, computing
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes
$O(\left|V\right|^{3})$ in total for all $E^{*}\subseteq\binom{V^{\prime}}{2}$
and $V^{\prime}\in\binom{V}{3}$.

###  5.3 Parallel binding: The parallelizable icing on the cake

In local binding, the sampling order matters, i.e., later rounds are affected
by earlier rounds. Specifically, if one pair is already determined in an early
round, even if it is sampled again in later rounds, its (in)existence cannot
be changed. This property hinders the parallelization of the binding process
and the derivation of tractability analyses. This property also implies that
each pair can only be bound together once, entailing less flexibility in the
group interactions.

We thus propose a more flexible and naturally parallelizable binding
algorithm, parallel binding. Specifically, we consider the probabilistic
process in Algorithm 3, and let $f^{\text{PB}}_{p;g,R}$ denote the
corresponding RGM defined by
$f^{\text{PB}}_{p;g,R}(G)=\Pr[\text{\lx@cref{creftype~refnum}{alg:iid_binding}
outputs $G$ with inputs $p$, $g$, and $R$}]$.

1

Input : (1) $p\colon\binom{V}{2}\to[0,1]$: edge probabilities;

(2) $g:V\to[0,1]$: node-sampling probabilities;

(3) $R$: the number of rounds for binding

Output : $G$: generated graph

2

$E\leftarrow\emptyset$ $\triangleright$ Initialization

3
$r(u,v)\leftarrow\min(\frac{1-\left(1-p(u,v)\right)^{1/R}}{g(u)g(v)},1),\forall
u,v\in V$

4 $p_{rem}(u,v)\leftarrow\max(1-\frac{1-p(u,v)}{(1-g(u)g(v))^{R}},0),\forall
u,v\in V$

5 for  _$i_{round}=1,2,\ldots,R$_ do

6 sample $V_{s}\subseteq V$ with $\Pr[v\in V_{s}]=g(v)$ independently

$E\leftarrow E\cup\text{{{binding(}}{\emph{$r$, $\binom{V_{s}}{2}$}}{{)}}}$
$\triangleright$ See Alg. 1

7

8for  _$(u,v)\in\binom{V}{2}$ s.t. $p_{rem}(u,v)>0$_ do

9 sample a random variable $s\sim\mathcal{U}(0,1)$

10 if  _$s\leq p_{rem}(u,v)$_ then

11 $E\leftarrow E\cup\\{(u,v)\\}$

12

13

14return _$G=(V,E)$_

Algorithm 3 Parallel binding

The high-level idea is to make each round of binding probabilistically
equivalent (see Lines 3 to 3). Specifically, in each round, we insert edges
with low probabilities (compared to the ones in $p$) while maintaining the
final individual edge probabilities, by the calculation of $r$ and $p_{rem}$
at Algorithms 3 and 3. We can straightforwardly parallelize the rounds by,
e.g., multi-threading.

Although parallel binding is algorithmically different from (local) binding
(e.g., no partition is used), it shares many theoretical properties with local
binding. Specifically, Proposition 5.5, Remark 5.6, Theorem 5.7, Theorem 5.8,
Remark 5.9, and Theorem 5.10 also apply to parallel binding. This implies that
we maintain (or even improve; see, e.g., Remark 5.11) correctness,
tractability, flexibility, and efficiency when using parallel binding instead
of local binding. See Section C.5 for the formal statements and proofs.

######  Remark 5.11.

We also derive tractability results of parallel binding on the expected number
of (non-)isolated nodes. It is much more challenging to derive such results
for local binding due to the properties mentioned above, i.e., later rounds
are affected by earlier rounds. Since our main focus is on subgraph densities,
see Appendix D for all the analysis regarding (non-)isolated nodes.

###  5.4 Efficient parameter fitting with node equivalence

Since our closed-form tractability results are functions involving only
arithmetic operations on the parameters, differentiable optimization
techniques (e.g., gradient descent) are possible for parameter fitting. The
fitting objective can be any function of $3$-motif probabilities. For example,
one can fit the (expected) number of triangles
($\mathbb{E}_{f^{\text{X}}_{p;g,R}}[\triangle(G)]$) to the ground-truth number
in an input graph ($\triangle(G_{input})$) by minimizing the “difference”
between them, e.g.,
$(1-\frac{\mathbb{E}_{f^{\text{X}}_{p;g,R}}[\triangle(G)]}{\triangle(G_{input})})^{2}$,
where
$\mathbb{E}_{f^{\text{X}}_{p;g,R}}[\triangle(G)]=\sum_{V^{\prime}\in\binom{V}{3}}\Pr_{f^{\text{X}}_{p;g,R}}[E(G[V^{\prime}])=\binom{V^{\prime}}{2}]$
are obtainable by the tractability results (Theorems 5.8 and C.4) with
$X\in\\{\text{LB},\text{PB}\\}$ indicating the binding scheme (LB represents
local binding and PB represents parallel binding).

Efficient evaluation of the fitting objective is important. A key challenge is
that the naive computation takes $O(\left|V\right|^{3})$ time in total by
considering all $O(\left|V\right|^{3})$ different possible node groups
$V^{\prime}$ (see Theorems 5.8 and C.4)). We aim to improve the speed of
computing the tractability results by considering node equivalence w.r.t.
motif probabilities in various edge-probability models. Equivalent nodes form
equivalent node groups, which reduces the number of distinct node groups to
calculate.

Erdős-Rényi (ER) model.whiteErdős-Rényi (ER) model. The ER model (Erdős &
Rényi, 1959) outputs uniform edge probabilities, and all the nodes are
equivalent. Hence, we set all the node-sampling probabilities identical, i.e.,
$g(v)=g_{0},\forall v\in V$ for a single parameter $g_{0}\in[0,1]$.

######  Lemma 5.12 (Reduced time complexity with ER).

For ER, the time complexities of computing $3$-motif probabilities can be
reduced from $O(\left|V\right|^{3})$ to $O(1)$.

Chung-Lu (CL) model.whiteChung-Lu (CL) model. The CL model (Chung & Lu, 2002)
outputs edge probabilities with expected degrees
$D=(d_{1},d_{2},\ldots,d_{n})$, and nodes with the same degree are equivalent.
We set node-sampling probabilities as a function of degree with $k_{deg}$
parameters, where
$k_{deg}\coloneqq\left|\\{d_{1},d_{2},\ldots,d_{n}\\}\right|$.

######  Lemma 5.13 (Reduced time complexity with CL).

For CL, the time complexities of computing $3$-motif probabilities can be
reduced from $O(\left|V\right|^{3})$ to $O(k^{3}_{deg})$.

Stochastic block (SB) modelwhiteStochastic block (SB) model The SB model
(Holland et al., 1983) outputs edge probabilities with each node assigned to a
block (i.e., a group), and nodes partitioned in the same block are equivalent.
Hence, we set the node-sampling probabilities as a function of the block
index, with the number of parameters equal to the number of blocks.

######  Lemma 5.14 (Reduced time complexity with SB).

For SB, the time complexities of computing $3$-motif probabilities can be
reduced from $O(\left|V\right|^{3})$ to $O(c^{3})$, where $c$ is the total
number of blocks.

Stochastic Kronecker (KR) modelwhiteStochastic Kronecker (KR) model With a
(commonly used $2$-by-$2$) seed matrix $\theta\in[0,1]^{2\times 2}$ and
$k_{KR}\in\mathbb{N}$, the KR model (Leskovec et al., 2010) outputs edge
probabilities as the $k_{KR}$-th Kronecker power of $\theta$. In KR, each node
$i\in[2^{k_{KR}}]$ is associated with a binary node label of length $k_{KR}$,
i.e., the binary representation of $i-1$. Nodes with the same number of ones
in their binary node labels are equivalent.777The equivalence in KR is
slightly weaker than that in the other three models. This is why the reduced
time complexity is $O(k^{7}_{KR})$ instead of $O(k^{3}_{KR})$. See Section
C.6.4 for more details. Hence, we set node-sampling probabilities as a
function of the number of ones in the binary representation, with $k_{KR}+1$
parameters.

######  Lemma 5.15 (Reduced time complexity with KR).

For KR, the time complexities of computing $3$-motif probabilities can be
reduced from $O(\left|V\right|^{3})$ to $O(k^{7}_{KR})$.

Note.whiteNote. See Section C.6 for more details about parameter fitting,
e.g., formal definitions of the models and the details of node equivalence.

##  6 Experiments

In this section, we empirically evaluate EGPMs with our binding schemes and
show the superiority of realization schemes beyond edge independency.
Specifically, we show the following two points:

  * •

(P1) When we use our tractability results to fit the parameters of EPGMs, we
improve upon EIGMs and reproduce high triangle densities, and thus produce
high clustering which is a realistic pattern; this also validates the
correctness of our tractability results and algorithms.

  * •

(P2) We can reproduce other realistic patterns, e.g., power-law degrees and
small diameters, especially when the corresponding EIGMs are able to do so;
this shows that improving EIGMs w.r.t. clustering by binding does not harm the
generation quality w.r.t. other realistic patterns.

###  6.1 Experimental settings

Datasets.whiteDatasets. We use six real-world datasets: (1) social networks
hamsterster (Hams) and facebook (Fcbk), (2) web graphs polblogs (Polb) and
spam (Spam), and (3) biological graphs CE-PG (Cepg) and SC-HT (Scht). See
Table 5 in Section F.1 for the statistics of the datasets.

Models.whiteModels. We consider the four edge-probability models analyzed in
Section 5.4: the Erdős-Rényi (ER) model, the Chung-Lu (CL) model, the
stochastic block (SB) model, and the stochastic Kronecker (KR) model. We
obtain edge probabilities from those models when given an input graph.

Realization methods.whiteRealization methods. We compare three realization
methods: EIGMs (EdgeInd), and EPGMs with local binding (LoclBdg) and with
parallel binding (ParaBdg).

Fitting.whiteFitting. Since our main focus is to improve triangle densities,
in our main experiments, we use the number of triangles as the objective of
the fitting algorithms. We use gradient descent for the optimization of
parameters. See Section F.1 for the detailed experimental settings.

###  6.2 P1: EPGMs reproduce high clustering (Table 1)

EPGMs with binding reproduce realistic high clustering. In Table 1, for each
dataset and each model, we compare three clustering-related metrics, the
number of triangles ($\triangle$), the global clustering coefficient (GCC),
and the average local clustering coefficient (ALCC), in the ground-truth
(GroundT) graph and the graphs generated with each realization method. For
each dataset and each model, we compute the ranking of each method according
to the absolute error w.r.t. each metric, and show the average rankings (ARs)
over datasets and models in Table 1. The statistics are averaged over $100$
generated graphs. See Section F.2 for the full results with standard
deviations.

The number of triangles, which is the objective of our fitting algorithms, can
be almost perfectly preserved by both LoclBdg and ParaBdg in most cases,
showing the correctness and effectiveness of our algorithms. Notably, as the
theoretical results (Theorem 3.3) imply, EIGMs fail to generate graphs with
enough triangles in most cases. GCC and ALCC are also significantly improved
(upon EIGMs) in most cases, while ParaBdg has noticeably higher ALCC than
LoclBdg. In some rare cases, ParaBdg generates graphs with exceedingly high
GCC and/or ALCC and have higher absolute errors compared to EIGMs.

Table 1:  The clustering metrics of generated graphs. The number of triangles
($\triangle$) is normalized. For each dataset and each model, the best result
is in bold and the second best is underlined. AR represents average ranking.
The statistics are averaged over 100 random trails. See Table 6 in Section F.2
for the full results with standard deviations. Our binding schemes (LoclBdg
and ParaBdg) are consistently and clearly beneficial for improving clustering,
and generating graphs with realistic clustering metrics.

dataset Hams Fcbk Polb Spam Cepg Scht AR over dataset  metric $\triangle$ gcc
alcc $\triangle$ gcc alcc $\triangle$ gcc alcc $\triangle$ gcc alcc
$\triangle$ gcc alcc $\triangle$ gcc alcc $\triangle$ gcc alcc model GroundT
1.00 0.23 0.54 1.00 0.52 0.61 1.00 0.23 0.32 1.00 0.14 0.29 1.00 0.32 0.45
1.00 0.38 0.35 N/A N/A N/A  ER EdgeInd 0.01 0.01 0.01 0.01 0.01 0.01 0.03 0.02
0.02 0.01 0.00 0.00 0.04 0.03 0.03 0.03 0.03 0.03 3.0 2.7 2.5 [t] LoclBdg 1.00
0.32 0.24 1.01 0.45 0.22 0.95 0.34 0.25 0.99 0.34 0.23 1.02 0.40 0.26 1.01
0.42 0.25 1.7 1.3 1.3 ParaBdg 0.99 0.39 0.64 1.00 0.57 0.81 1.02 0.41 0.66
0.99 0.40 0.66 0.97 0.51 0.75 0.99 0.56 0.79 1.3 2.0 2.2 [b] CL EdgeInd 0.30
0.07 0.06 0.12 0.06 0.06 0.79 0.18 0.17 0.50 0.07 0.06 0.68 0.23 0.22 0.64
0.24 0.23 3.0 3.0 2.5 [t] LoclBdg 0.99 0.17 0.26 1.03 0.26 0.30 1.00 0.21 0.34
1.03 0.12 0.26 1.00 0.29 0.43 1.04 0.32 0.47 1.7 1.8 1.5 ParaBdg 1.00 0.18
0.47 1.01 0.34 0.63 1.01 0.22 0.47 1.01 0.13 0.44 1.00 0.31 0.58 1.14 0.29
0.61 1.3 1.2 2.0 [b] SB EdgeInd 0.26 0.08 0.04 0.15 0.14 0.08 0.48 0.14 0.16
0.53 0.09 0.04 0.66 0.26 0.20 0.64 0.27 0.13 3.0 3.0 3.0 [t] LoclBdg 1.04 0.22
0.24 0.93 0.43 0.33 0.99 0.24 0.35 0.98 0.15 0.22 0.99 0.32 0.41 1.03 0.35
0.39 1.7 1.2 1.3 ParaBdg 0.99 0.24 0.52 1.03 0.53 0.56 1.01 0.18 0.25 0.99
0.16 0.36 1.05 0.33 0.36 0.97 0.34 0.44 1.3 1.8 1.7 [b] KR EdgeInd 0.18 0.04
0.06 0.05 0.04 0.04 0.10 0.04 0.07 0.06 0.01 0.03 0.13 0.07 0.12 0.03 0.03
0.05 3.0 3.0 3.0 [t] LoclBdg 1.09 0.15 0.23 0.93 0.24 0.27 1.06 0.14 0.23 0.94
0.12 0.19 0.99 0.17 0.31 1.44 0.18 0.28 2.0 2.0 1.7 ParaBdg 1.00 0.17 0.39
0.97 0.35 0.60 0.94 0.22 0.42 1.05 0.16 0.38 1.00 0.28 0.46 1.07 0.35 0.58 1.0
1.0 1.3 [b] AR over models EdgeInd 3.0 3.0 3.0 3.0 3.0 3.0 3.0 3.0 2.5 3.0 2.5
2.8 3.0 3.0 3.0 3.0 3.0 2.3 3.0 2.9 2.8 [t] LoclBdg 1.8 1.5 2.0 2.0 2.0 2.0
1.5 1.5 1.0 2.0 1.8 1.3 1.5 1.5 1.3 1.8 1.3 1.3 1.8 1.6 1.5 ParaBdg 1.3 1.5
1.0 1.0 1.0 1.0 1.5 1.5 2.5 1.0 1.8 2.0 1.5 1.5 1.8 1.3 1.8 2.5 1.3 1.5 1.8
[b]

Figure 1: The degree (left) and distance (right) distributions of generated
graphs. Each shaded area represents one standard deviation. The plots are in a
log-log scale. Our binding schemes (LoclBdg and ParaBdg) do not negatively
affect degree or distance distributions, and provide improvements sometimes
(e.g., for the ER model).

###  6.3 P2: EPGMs generate realistic degrees and distances (Figure 1)

EPGMs with binding (LoclBdg and ParaBdg) also reproduce other realistic
patterns. In Figure 1, for each dataset (each column) and each model (each
row), we compare the degree distributions and distance distributions in the
ground-truth graph and the graphs generated with each realization method.
Specifically, for each realization method, we count the number of nodes with
degree at least $k$ for each $k\in\mathbb{N}$ and count the number of pairs in
the largest connected component with distance at least $d$ for each
$d\in\mathbb{N}$ in each generated graph, and take the average number over
$100$ generated graphs. See Section F.3 for the formal definitions and full
results.

EPGMs with binding generate graphs with realistic patterns: power-law degrees
and small diameters (i.e., small distances). Both schemes (LoclBdg and
ParaBdg) perform comparably well while LoclBdg performs noticeably better with
ER and ParaBdg performs noticeably better with KR. Importantly, when the edge
probabilities output power-law expected degrees (e.g., CL and KR), the degree
distributions are well preserved with binding. Edge-independent ER cannot
generate power-law degrees (Bollobás & Riordan, 2003), and binding alleviates
this problem.

###  6.4 Graph generation speed (Table 2)

In Table 2, we compare the running time of graph generation (averaged over
$100$ random trials) using EdgeInd,888We use krongen in SNAP (Leskovec &
Sosič, 2016), which is parallelized and optimized for KR. LoclBdg, ParaBdg,
and serialized ParaBdg without parallelization (ParaBdg-s) with the stochastic
Kronecker (KR) model.

Table 2: The time (in seconds) for graph generation with different realization
methods.

Hams Fcbk EdgeInd 0.1 0.1 LoclBdg 4.7 49.0 ParaBdg 0.3 1.7 ParaBdg-s 3.2 12.6

Among the competitors, EdgeInd is the fastest with the simplest algorithmic
nature. Between the two binding schemes, ParaBdg is noticeably faster than
LoclBdg, and is even faster with parallelization. Fitting the same number of
triangles, ParaBdg usually requires lower node-sampling probabilities and thus
deals with fewer pairs in each round, and is thus faster even when serialized.
See Section F.4 for more discussions and the full results.

###  6.5 Joint optimization of edge probabilities
and node-sampling probabilities (Table 3)

In addition to optimizing node-sampling probabilities for given edge
probabilities, we can also jointly optimize both kinds of probabilities. In
Table 3, we compare the clustering of the ground-truth graph and the graphs
generated by EPGMs using three variants of parallel binding: (1) ParaBdg with
the number of triangles as the objective (the one used in Table 1), (2)
ParaBdg-w with the numbers of triangles and wedges as the objective (given
edge probabilities), (3) ParaBdg-jw jointly optimizing both kinds of
probabilities, with the numbers of triangles and wedges as the objective.

Table 3:  The clustering metrics of the graphs generated by three variants of
parallel binding. The number of triangles ($\triangle$) is normalized. For
each dataset and each model, the best result is in bold and the second best is
underlined. Joint optimization further enhances the power of our binding
scheme ParaBdg to reproduce realistic graph patterns.

dataset Hams Fcbk metric $\triangle$ GCC ALCC $\triangle$ GCC ALCC  GroundT
1.000 0.229 0.540 1.000 0.519 0.606  ParaBdg 0.997 0.165 0.394 0.971 0.347
0.605 [t] ParaBdg-w 0.964 0.176 0.260 1.021 0.408 0.458 ParaBdg-jw 0.999 0.230
0.448 1.018 0.521 0.644 [b]

On both Hams and Fcbk, ParaBdg and ParaBdg-w can well fit the number of
triangles but have noticeable errors w.r.t. the number of wedges (and thus
w.r.t. GCC), while ParaBdg-jw with joint optimization accurately fits both the
numbers of triangles and wedges. On the other datasets, the three variants
perform similarly well, because ParaBdg already preserves both the numbers of
triangles and wedges well and there is not much room for improvement. With
joint optimization, the degree and distance distributions are still well
preserved (see Appendix F.5).

###  6.6 Extra experimental results

As discussed in Section 3.1, some existing methods shift edge probabilities by
various mechanisms. Such methods are essentially EIGMs and inevitably trade
off between variability and the ability to generate high-clustering graphs (by
Theorem 3.3). Compared to such methods (specifically, BCL by Mussmann et al.
(2015) and BTER by Kolda et al. (2014)), we empirically validate that EPGMs
with binding achieve comparable or even better performance in generating high-
clustering graphs, with much higher variability (recall that high variability
is important for RGMs, since obtaining almost identical graphs is not
meaningful; see Remark 3.2). See Section F.6 for more details.

Due to the page limit, the full results are in Appendix F. Our fitting
algorithms also assign different node-sampling probabilities to different
nodes (See Section F.1). Moreover, as mentioned in Remark 5.11, for parallel
binding, we can fit and control the number of (non-)isolated nodes; see
Appendix D for the theoretical analyses and experimental results.

##  7 Conclusion and limitations

In this work, we show that realization beyond edge independence can produce
more realistic structures while ensuring high tractability. We formally define
EPGMs (Definition 4.1) and show their basic properties (Propositions 4.2-4.7).
We propose realistic, tractable, and flexible realization schemes called
binding (Algorithm 1) with two practical variants: local binding (Algorithm 2)
and parallel binding (Algorithm 3). We derive tractability results (Theorems
5.8 and C.4) on the closed-form subgraph densities, and propose efficient
parameter fitting (Section 5.4; Lemmas 5.12-5.15). We conduct extensive
experiments to show the empirical power of EPGMs with binding (Section 6).

A limitation of our methods is that EPGMs with binding generate more isolated
nodes than EIGMs due to higher variance. However, we can address the
limitation by fitting and controlling the number of (non-) isolated nodes with
the tractability results, as mentioned in Remark 5.11. More details are
provided in Appendix D. Moreover, as discussed in Remark 5.3, binding only
covers a subset of EPGMs, and we will explore the other types of EPGMs in the
future.

## References

  * Adamic & Glance (2005) Adamic, L. A. and Glance, N.  The political blogosphere and the 2004 us election: divided they blog.  In _LinkKDD workshop_ , 2005.
  * Ahmed et al. (2023) Ahmed, K., Zeng, Z., Niepert, M., and Broeck, G. V. d.  SIMPLE: A gradient estimator for $k$-subset sampling.  In _ICLR_ , 2023.
  * Anastassiou (2007) Anastassiou, D.  Computational analysis of the synergy among multiple interacting genes.  _Molecular systems biology_ , 3(1):83, 2007.
  * Anonymous (2024) Anonymous.  Exploring edge probability graph models beyond edge independency: Code and datasets.  https://anonymous.4open.science/r/epgm-7EBE, 2024.
  * Barabási & Albert (1999) Barabási, A.-L. and Albert, R.  Emergence of scaling in random networks.  _science_ , 286(5439):509–512, 1999.
  * Bell (1934) Bell, E. T.  Exponential numbers.  _The American Mathematical Monthly_ , 41(7):411–419, 1934.
  * Bollobás & Riordan (2003) Bollobás, B. and Riordan, O. M.  Mathematical results on scale-free random graphs.  _Handbook of graphs and networks: from the genome to the internet_ , pp. 1–34, 2003.
  * Brissette & Slota (2021) Brissette, C. and Slota, G. M.  Limitations of chung lu random graph generation.  In _International Workshop on Complex Networks and Their Applications_ , 2021.
  * Brissette et al. (2022) Brissette, C., Liu, D., and Slota, G. M.  Correcting output degree sequences in chung-lu random graph generation.  In _International Conference on Complex Networks and Their Applications_ , 2022.
  * Bu et al. (2023) Bu, F., Kang, S., and Shin, K.  Interplay between topology and edge weights in real-world graphs: concepts, patterns, and an algorithm.  _Data Mining and Knowledge Discovery_ , 37:2139 – 2191, 2023.
  * Castillo et al. (2008) Castillo, C., Chellapilla, K., and Denoyer, L.  Web spam challenge 2008.  In _AIRWeb workshop_ , 2008.
  * Chakrabarti & Faloutsos (2006) Chakrabarti, D. and Faloutsos, C.  Graph mining: Laws, generators, and algorithms.  _ACM computing surveys_ , 38(1):2–es, 2006.
  * Chanpuriya et al. (2021) Chanpuriya, S., Musco, C., Sotiropoulos, K., and Tsourakakis, C.  On the power of edge independent graph models.  In _NeurIPS_ , 2021.
  * Chanpuriya et al. (2023) Chanpuriya, S., Musco, C., Sotiropoulos, K., and Tsourakakis, C.  On the role of edge dependency in graph generative models.  _arXiv 2312.03691_ , 2023.
  * Cho et al. (2014) Cho, A., Shin, J., Hwang, S., Kim, C., Shim, H., Kim, H., Kim, H., and Lee, I.  Wormnet v3: a network-assisted hypothesis-generating server for caenorhabditis elegans.  _Nucleic acids research_ , 42(W1):W76–W82, 2014.
  * Chung & Lu (2002) Chung, F. and Lu, L.  Connected components in random graphs with given expected degree sequences.  _Annals of combinatorics_ , 6(2):125–145, 2002.
  * Chung et al. (2019) Chung, J., Pedigo, B. D., Bridgeford, E. W., Varjavand, B. K., Helm, H. S., and Vogelstein, J. T.  Graspy: Graph statistics in python.  _Journal of Machine Learning Research_ , 20:1–7, 2019.
  * Dagum & Menon (1998) Dagum, L. and Menon, R.  Openmp: an industry standard api for shared-memory programming.  _IEEE computational science and engineering_ , 5(1):46–55, 1998.
  * Drobyshevskiy & Turdakov (2019) Drobyshevskiy, M. and Turdakov, D.  Random graph modeling: A survey of the concepts.  _ACM computing surveys_ , 52(6):1–36, 2019.
  * Eblen et al. (2012) Eblen, J. D., Phillips, C. A., Rogers, G. L., and Langston, M. A.  The maximum clique enumeration problem: algorithms, applications, and implementations.  In _BMC bioinformatics_ , volume 13, pp. 1–11, 2012.
  * Erdős & Rényi (1959) Erdős, P. and Rényi, A.  On random graphs i.  _Publicationes Mathematicae Debrecen_ , 6:290–297, 1959.
  * Felmlee & Faris (2013) Felmlee, D. and Faris, R.  Interaction in social networks.  In _Handbook of social psychology_ , pp. 439–464. Springer, 2013.
  * Gottesman & Hanson (2005) Gottesman, I. I. and Hanson, D. R.  Human development: Biological and genetic processes.  _Annual review of psychology_ , 56:263–286, 2005.
  * (24) Hamsterster.  Hamsterster social network.  http://www.hamsterster.com.
  * Holland et al. (1983) Holland, P. W., Laskey, K. B., and Leinhardt, S.  Stochastic blockmodels: First steps.  _Social networks_ , 5(2):109–137, 1983.
  * Iacopini et al. (2022) Iacopini, I., Petri, G., Baronchelli, A., and Barrat, A.  Group interactions modulate critical mass dynamics in social convention.  _Communications Physics_ , 5(1):64, 2022.
  * Jang et al. (2016) Jang, H., Choe, S. P., Gunkel, S. N., Kang, S., and Song, J.  A system to analyze group socializing behaviors in social parties.  _IEEE Transactions on Human-Machine Systems_ , 47(6):801–813, 2016.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Kleinberg et al. (1999) Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. S.  The web as a graph: Measurements, models, and methods.  In _COCOON_ , 1999.
  * Klopp et al. (2017) Klopp, O., Tsybakov, A. B., and Verzelen, N.  Oracle inequalities for network models and sparse graphon estimation.  _Annals of Statistics_ , 45(1):316–354, 2017.
  * Kolda et al. (2014) Kolda, T. G., Pinar, A., Plantenga, T., and Seshadhri, C.  A scalable generative graph model with community structure.  _SIAM Journal on Scientific Computing_ , 36(5):C424–C452, 2014.
  * LaRock & Lambiotte (2023) LaRock, T. and Lambiotte, R.  Encapsulation structure and dynamics in hypergraphs.  _Journal of Physics: Complexity_ , 4(4):045007, 2023.
  * Lee et al. (2021) Lee, G., Choe, M., and Shin, K.  How do hyperedges overlap in real-world hypergraphs?-patterns, measures, and generators.  In _theWebConf (WWW)_ , 2021.
  * Leskovec & Krevl (2014) Leskovec, J. and Krevl, A.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * Leskovec & Mcauley (2012) Leskovec, J. and Mcauley, J.  Learning to discover social circles in ego networks.  In _NeurIPS_ , 2012.
  * Leskovec & Sosič (2016) Leskovec, J. and Sosič, R.  Snap: A general-purpose network analysis and graph-mining library.  _ACM Transactions on Intelligent Systems and Technology_ , 8(1):1–20, 2016.
  * Leskovec et al. (2010) Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C., and Ghahramani, Z.  Kronecker graphs: an approach to modeling networks.  _Journal of Machine Learning Research_ , 11(2), 2010.
  * Levorato (2014) Levorato, V.  Group measures and modeling for social networks.  _Journal of Complex Systems_ , 2014, 2014.
  * Li et al. (2020) Li, A., Zhou, L., Su, Q., Cornelius, S. P., Liu, Y.-Y., Wang, L., and Levin, S. A.  Evolution of cooperation on temporal networks.  _Nature communications_ , 11(1):2259, 2020.
  * Lusher et al. (2013) Lusher, D., Koskinen, J., and Robins, G.  _Exponential random graph models for social networks: Theory, methods, and applications_.  Cambridge University Press, 2013.
  * Mahdian & Xu (2007) Mahdian, M. and Xu, Y.  Stochastic kronecker graphs.  In _WAW_ , 2007.
  * Milo et al. (2002) Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., and Alon, U.  Network motifs: simple building blocks of complex networks.  _Science_ , 298(5594):824–827, 2002.
  * Moreno et al. (2018) Moreno, S., Neville, J., and Kirshner, S.  Tied kronecker product graph models to capture variance in network populations.  _ACM Transactions on Knowledge Discovery from Data_ , 12(3):1–40, 2018.
  * Murphy et al. (2010) Murphy, R. C., Wheeler, K. B., Barrett, B. W., and Ang, J. A.  Introducing the graph 500.  _Cray Users Group_ , 19:45–74, 2010.
  * Mussmann et al. (2015) Mussmann, S., Moore, J., Pfeiffer, J., and Neville, J.  Incorporating assortativity and degree dependence into scalable network models.  In _AAAI_ , 2015.
  * Naoumkina et al. (2010) Naoumkina, M. A., Modolo, L. V., Huhman, D. V., Urbanczyk-Wochniak, E., Tang, Y., Sumner, L. W., and Dixon, R. A.  Genomic and coexpression analyses predict multiple genes involved in triterpene saponin biosynthesis in medicago truncatula.  _The Plant Cell_ , 22(3):850–866, 2010.
  * Newman (2003) Newman, M. E.  Properties of highly clustered networks.  _Physical Review E_ , 68(2):026121, 2003.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.  Pytorch: An imperative style, high-performance deep learning library.  In _NeurIPS_ , 2019.
  * Pervez et al. (2023) Pervez, A., Lippe, P., and Gavves, E.  Scalable subset sampling with neural conditional poisson networks.  In _ICLR_ , 2023.
  * Pfeiffer et al. (2012) Pfeiffer, J. J., La Fond, T., Moreno, S., and Neville, J.  Fast generation of large scale social networks while incorporating transitive closures.  In _PASSAT-SocialCom_ , 2012.
  * Plomin (1990) Plomin, R.  The role of inheritance in behavior.  _Science_ , 248(4952):183–188, 1990.
  * Pritykin et al. (2015) Pritykin, Y., Ghersi, D., and Singh, M.  Genome-wide detection and analysis of multifunctional genes.  _PLoS computational biology_ , 11(10):e1004467, 2015.
  * Purushotham & Jay Kuo (2015) Purushotham, S. and Jay Kuo, C. C.  Modeling group dynamics for personalized group-event recommendation.  In _SBP_ , 2015.
  * Reynolds et al. (2009) Reynolds, D. A. et al.  Gaussian mixture models.  _Encyclopedia of biometrics_ , 741(659-663), 2009.
  * Rohe et al. (2011) Rohe, K., Chatterjee, S., and Yu, B.  Spectral clustering and the high-dimensional stochastic blockmodel.  _The Annals of Statistics_ , pp. 1878–1915, 2011.
  * Rossi & Ahmed (2015) Rossi, R. A. and Ahmed, N. K.  The network data repository with interactive graph analytics and visualization.  In _AAAI_ , 2015.
  * Seroussi & Ma (1983) Seroussi, G. and Ma, F.  On the arithmetic complexity of matrix kronecker powers.  _Information processing letters_ , 17(3):145–148, 1983.
  * Seshadhri et al. (2013) Seshadhri, C., Pinar, A., and Kolda, T. G.  An in-depth analysis of stochastic kronecker graphs.  _Journal of the ACM_ , 60(2):1–32, 2013.
  * Siek et al. (2001) Siek, J. G., Lee, L.-Q., and Lumsdaine, A.  _The Boost Graph Library: User Guide and Reference Manual_.  Pearson Education, 2001.
  * Sloane (2007) Sloane, N. J.  The on-line encyclopedia of integer sequences.  In _MKM-Calculemus_ , 2007.
  * Stamm et al. (2023) Stamm, F. I., Scholkemper, M., Strohmaier, M., and Schaub, M. T.  Neighborhood structure configuration models.  In _WWW_ , 2023.
  * Staudt et al. (2016) Staudt, C. L., Sazonovs, A., and Meyerhenke, H.  Networkit: A tool suite for large-scale complex network analysis.  _Network Science_ , 4(4):508–530, 2016.
  * Storey et al. (2007) Storey, J. D., Madeoy, J., Strout, J. L., Wurfel, M., Ronald, J., and Akey, J. M.  Gene-expression variation within and among human populations.  _The American Journal of Human Genetics_ , 80(3):502–509, 2007.
  * Sussman et al. (2012) Sussman, D. L., Tang, M., Fishkind, D. E., and Priebe, C. E.  A consistent adjacency spectral embedding for stochastic blockmodel graphs.  _Journal of the American Statistical Association_ , 107(499):1119–1128, 2012.
  * Sutter et al. (2023) Sutter, T. M., Ryser, A., Liebeskind, J., and Vogt, J. E.  Differentiable random partition models.  _arXiv 2305.16841_ , 2023.
  * Von Luxburg (2007) Von Luxburg, U.  A tutorial on spectral clustering.  _Statistics and computing_ , 17:395–416, 2007.
  * Watts & Strogatz (1998) Watts, D. J. and Strogatz, S. H.  Collective dynamics of small-world networks.  _nature_ , 393(6684):440–442, 1998.
  * Wegner & Olhede (2021) Wegner, A. E. and Olhede, S.  Atomic subgraphs and the statistical mechanics of networks.  _Physical Review E_ , 103(4):042311, 2021.
  * Wong & Li (2020) Wong, D. W. and Li, Y.  Spreading of covid-19: Density matters.  _Plos one_ , 15(12):e0242398, 2020.
  * Xie & Ermon (2019) Xie, S. M. and Ermon, S.  Reparameterizable subset sampling via continuous relaxations.  In _IJCAI_ , 2019.

##  Appendix A Potential broader impact

This paper presents work in the field of random graph models. There are many
potential societal consequences of our work, none of which we feel must be
specifically highlighted here.

##  Appendix B Flowchart

Below, we provide a flowchart of this work, summarizing the main ideas and
contents.

ptTarget: To find random graph models that have high tractability and generate
graphs with realistic patternsptBackground: EIGMs with edge-independent
realization methods have high tractabilitybut cannot generate graphs with high
triangle densitiesptIdea: To consider edge-dependent realization methodsptWe
define the concept of EPGMs (Section 4)but considering all the possible cases
is impracticalptIdea: To find sub-cases with meaningful realization methods,
specifically aiming to improve triangle densitiesptWe propose specific
realization schemes called bindingand derive the tractability results on motif
probabilities (Section 5)but we want to further improve the efficiency of
computing motif probabilities in practiceptIdea: To reduce the number of
distinct node groups for calculation by considering node equivalenceptWe
analyze the node equivalence in various edge-probabilities modelsand derive
the reduced time complexities for computing motif probabilities (Section 5.4)

##  Appendix C Proofs

In this section, we show the proofs of our theoretical results.

###  C.1 EPGMs

######  Proposition 4.2 (EIGMs are special EPGMs).

For any $p$, the EIGM w.r.t. $p$ is an EPGM w.r.t. $p$, i.e.,
$f^{\text{EI}}_{p}\in\mathcal{F}(p)$.

###### Proof.

By Definitions 2.1 and 2.2,

$\displaystyle~{}\Pr\nolimits_{f^{\text{EI}}_{p}}[(u,v)]$ $\displaystyle=~{}$
$\displaystyle\sum_{G\in\mathcal{G}(V)}f^{\text{EI}}_{p}(G)\mathbf{1}[(u,v)\in
G]$ $\displaystyle=~{}$ $\displaystyle\sum_{(u,v)\in
G\in\mathcal{G}(V)}f^{\text{EI}}_{p}(G)$ $\displaystyle=~{}$
$\displaystyle\sum_{(u,v)\in
G\in\mathcal{G}(V)}p(u,v)\prod_{(u,v)\neq(u^{+},v^{+})\in
G}p(u^{+},v^{+})\prod_{(u^{-},v^{-})\notin G}(1-p(u^{-},v^{-}))$
$\displaystyle=~{}$ $\displaystyle p(u,v),\forall u,v,$

completing the proof. ∎

######  Proposition 4.3 (EPGMs are general).

For any $f\colon\mathcal{G}(V)\to[0,1]$, there exists
$p\colon\binom{V}{2}\to[0,1]$ such that $f\in\mathcal{F}(p)$.

###### Proof.

Let $p\colon\binom{V}{2}\to[0,1]$ be that $p(u,v)=\Pr_{f}[(u,v)],\forall
u,v\in V$, then by Definition 4.1, $f\in\mathcal{F}(p)$. ∎

######  Proposition 4.4 (Upper bound of edge-group probabilities).

For any $p\colon\binom{V}{2}\to[0,1]$ and any edge group
$P\subseteq\binom{V}{2}$, $\Pr_{f}[P\subseteq E(G)]\leq\min_{(u,v)\in
P}p(u,v),\forall f\in\mathcal{F}(p)$.

###### Proof.

By definition, $\Pr_{f}[(u,v)]=p(u,v),\forall(u,v)$. Hence,

$\displaystyle\Pr\nolimits_{f}[P\subseteq E(G)]$
$\displaystyle=\Pr\nolimits_{f}[\bigwedge_{(u,v)\in P}(u,v)\in G]$
$\displaystyle\leq\min_{(u,v)\in P}\Pr\nolimits_{f}[(u,v)]$
$\displaystyle=\min_{(u,v)\in P}p(u,v),$

where we have used the fact that $\bigwedge_{(u,v)\in P}(u,v)\in G$ is a
subevent of $(u,v)\in G$ for any $(u,v)\in P$. ∎

######  Proposition 4.7 (EPGMs have constant expected degrees and overlap).

For any $p\colon\binom{V}{2}\to[0,1]$, the expected degree of each node and
the overlap of all the EPGMs w.r.t. $p$ are constant. Specifically,
$\mathbb{E}_{f}[d(v;G)]=\sum_{u\in V}p(u,v)$ and
$\operatorname{Ov}(f)=\frac{\sum_{u,v\in V}p^{2}(u,v)}{\sum_{u,v\in
V}p(u,v)},\forall f\in\mathcal{F}(p)$.

###### Proof.

By linearity of expectation,

$\displaystyle\mathbb{E}_{f}[d(v;G)]=\sum_{u\in V}\Pr[u\in N(v)]=\sum_{u\in
V}\Pr[(u,v)\in G]=\sum_{u\in V}p(u,v),$

which does not depend on anything else but $p$.

By Definition 3.1,

$\displaystyle~{}\operatorname{Ov}(f)$ $\displaystyle=~{}$
$\displaystyle\frac{\mathbb{E}_{G^{\prime},G^{\prime\prime}\sim
f}\left|E(G^{\prime})\cap
E(G^{\prime\prime})\right|}{\mathbb{E}_{f}\left|E(G)\right|}$
$\displaystyle=~{}$ $\displaystyle\frac{\sum_{u,v}\Pr[(u,v)\in
G^{\prime}\land(u,v)\in G^{\prime\prime}]}{\sum_{u,v}\Pr[(u,v)\in G]}$
$\displaystyle=~{}$ $\displaystyle\frac{\sum_{u,v}\Pr[(u,v)\in
G^{\prime}]\Pr[(u,v)\in G^{\prime\prime}]}{\sum_{u,v}\Pr[(u,v)\in G]}$
$\displaystyle=~{}$ $\displaystyle\frac{\sum_{u,v\in
V}p^{2}(u,v)}{\sum_{u,v\in V}p(u,v)},\forall f\in\mathcal{F}(p),$

where we have used linearity of expectation and the independence between
$G^{\prime}$ and $G^{\prime\prime}$, completing the proof. ∎

######  Corollary 4.6.

For any $p\colon\binom{V}{2}\to[0,1]$,
$\mathbb{E}_{f}[\triangle(G)]\leq\sum_{\\{u,v,w\\}\in\binom{V}{3}}\min(p(u,v),p(u,w),p(v,w)),\forall
f\in\mathcal{F}(p)$, where $\triangle(G)$ is the number of triangles in $G$.

###### Proof.

By linearity of expectation and Proposition 4.4,

$\displaystyle\mathbb{E}_{f}[\triangle(G)]$
$\displaystyle=\sum_{\\{u,v,w\\}\in\binom{V}{3}}\Pr\nolimits_{f}[\\{(u,v),(u,w),(v,w)\in
E(G)\\}]$
$\displaystyle\leq\sum_{\\{u,v,w\\}\in\binom{V}{3}}\min(p(u,v),p(u,w),p(v,w)).$

∎

###  C.2 General binding

######  Proposition 5.1 (Binding produces EPGMs).

For any $p\colon\binom{V}{2}\to[0,1]$ and any pair partition $\mathcal{P}$,
$f^{\text{BD}}_{p;\mathcal{P}}\in\mathcal{F}(p)$.

###### Proof.

For each pair $(u,v)$, the existence of the corresponding edge is determined
in the “binding” procedure on the group $P$ such that $(u,v)\in P$ (Algorithms
1 and 1), where $(u,v)$ is added into $\hat{E}$ and thus $E$ if and only if
$s\leq\hat{p}(u,v)=p(u,v)$ (Algorithm 1), which happens with probability
$p(u,v)$ since $s\sim\mathcal{U}(0,1)$. ∎

######  Proposition 5.2 (Binding produces higher edge-group probabilities).

For any $p\colon\binom{V}{2}\to[0,1]$, any pair partition $\mathcal{P}$, and
any $P\subseteq\binom{V}{2}$, $\Pr_{f^{\text{BD}}_{p;\mathcal{P}}}[P\subseteq
E(G)]\geq\Pr_{f^{\text{EI}}_{p}}[P\subseteq E(G)]$.

###### Proof.

Let $\mathcal{P}^{\prime}$ be a partition of $P$ such that
$\mathcal{P}^{\prime}\coloneqq\\{P_{0}\cap P\colon
P_{0}\in\mathcal{P},P_{0}\cap P\neq\emptyset\\}$. Then

$\displaystyle\Pr\nolimits_{f^{\text{BD}}_{p;\mathcal{P}}}[P\subseteq E(G)]$
$\displaystyle=\prod_{P^{\prime}\in\mathcal{P}^{\prime}}\min_{(u,v)\in
P^{\prime}}p(u,v)$ $\displaystyle=\prod_{(u,v)\in P\colon\exists
P^{\prime}\in\mathcal{P}^{\prime},(u,v)=\arg\min_{(u^{\prime},v^{\prime})\in
P^{\prime}}p(u,v)}p(u,v)$ $\displaystyle\geq\prod_{(u,v)\in P}p(u,v),$

since each $p(u,v)\leq 1$. ∎

###  C.3 Maximal binding

In order to prove Lemma 5.4, let us prove the following lemma first.

######  Lemma C.1 (The graph distribution with maximal binding).

For any $p\colon\binom{V}{2}\to[0,1]$, we sort the pairs in
$\binom{V}{2}=\\{(u_{1},v_{1}),(u_{2},v_{2}),\ldots,(u_{M},v_{M})\\}$ with
$M=\binom{\left|V\right|}{2}$ such that $p(u_{1},v_{1})\geq
p(u_{2},v_{2})\geq\cdots\geq p(u_{M},V_{M})$, then
$f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}(G=(V,\emptyset))=1-p(u_{1},v_{1})$,
$f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}(G=(V,\binom{V}{2}))=p(u_{M},v_{M})$,
$f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}(G=(V,\\{(u_{j},v_{j})\colon 1\leq j\leq
i\\}))=p(u_{i},v_{i})-p(u_{i+1},v_{i+1}),\forall i\in[M-1]$, and
$f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}(G)=0$ for any other $G$.

###### Proof.

With $\mathcal{P}=\\{\binom{V}{2}\\}$, all the edge existences are determined
by the same random variable $s$. Hence, if a pair $(u,v)$ exists, then all the
pairs $(u^{\prime},v^{\prime})$ with $p(u^{\prime},v^{\prime})\geq p(u,v)$
must exist. The possible outputs are either $G=(V,\emptyset)$ or
$G=(V,\\{(u_{j},v_{j})\colon 1\leq j\leq i\\})$ for some $i\in[M]$. The case
$G=(V,\emptyset)$ happens when $s>\max_{u,v\in V}p(u,v)=p(u_{1},v_{1})$ with
probability $1-p(u_{1},v_{1})$. The case $G=(V,\binom{V}{2})$ happens when
$s\leq\min_{u,v\in V}p(u,v)=p(u_{M},v_{M})$ with probability
$p(P_{\binom{\left|V\right|}{2}})$. For each remaining case
$G=(V,\\{(u_{j},v_{j})\colon 1\leq j\leq i\\}$ with $i\in[M-1]$, it happens
when $p(u_{i+1},v_{i+1})<s\leq p(u_{i},v_{i})$ with probability
$p(u_{i},v_{i})-p(u_{i+1},v_{i+1})$. ∎

######  Lemma 5.4 (Maximal binding achieves maximum edge-group probabilities).

For any $p\colon\binom{V}{2}\to[0,1]$ and any $P\subseteq\binom{V}{2}$,
$\Pr_{f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}}[P\subseteq E(G)]=\min_{(u,v)\in
P}p(u,v),\forall f\in\mathcal{F}(p)$.

###### Proof.

By Lemma C.1, in a graph $G$ generated by
$f^{\text{BD}}_{p;\\{\binom{V}{2}\\}}$, $P\subseteq E(G)$ if and only if
$\arg\min_{(u,v)\in P}p(u,v)\in G$., which happens with probability
$\min_{(u,v)\in P}p(u,v)$. ∎

###  C.4 Local binding

######  Proposition 5.5 (Local binding produces EPGMs).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$ and
$R\in\mathbb{N}$, $f^{\text{LB}}_{p;g,R}\in\mathcal{F}(p)$.

###### Proof.

For each pair $(u,v)$,
$\Pr_{f^{\text{LB}}_{p;g,R}}[(u,v)]=\sum_{\mathcal{P}}\Pr_{\mathcal{P}\sim
g}[\mathcal{P}]\Pr_{f^{\text{BD}}_{p;\mathcal{P}}}[(u,v)]$. By Proposition
5.1, $\Pr_{f^{\text{BD}}_{p;\mathcal{P}}}[(u,v)]=p(u,v),\forall\mathcal{P}$.
Hence,
$\Pr_{f^{\text{LB}}_{p;g,R}}[(u,v)]=\sum_{\mathcal{P}}\Pr_{\mathcal{P}\sim
g}[\mathcal{P}]p(u,v)=p(u,v)$. ∎

######  Theorem 5.7 (Time complexities of graph generation with local
binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, $f^{\text{LB}}_{p;g,R}$ generates a graph in
$O(R\left(\sum_{v\in V}g(v)\right)^{2}+\left|V\right|^{2})$ time with high
probability, with the worst case $O(R\left|V\right|^{2})$.

###### Proof.

We have at most $R$ rounds of sampling and binding, where each round samples
at most $\left|V\right|$ nodes and thus at most $\binom{\left|V\right|}{2}$
pairs. More specifically, the number of nodes sampled in each round is
$\sum_{v\in V}g(v)$ in expectation, and thus $O(\sum_{v\in V}g(v))$ with high
probability (e.g., you can use a Chernoff bound). Hence, it takes
$O(R\sum_{v\in V}g(v))$ time with high probability, and at most
$O(\binom{\left|V\right|}{2}R)$ time for the $R$ rounds. The number of
remaining pairs is at most $\binom{\left|V\right|}{2}$ so dealing with them
takes $O(\binom{\left|V\right|}{2})$ time. For the generation, we need to
enumerate all the node groups and each pair in each group. Since the partition
is disjoint, i.e., each pair is in exactly one group, each pair is visited
exactly once, which takes $O(\binom{\left|V\right|}{2})$ time. In conclusion,
generating a graph takes $O(R\sum_{v\in V}g(v)+\left|V\right|^{2})$ with high
probability, and $O(\binom{\left|V\right|}{2}R)$ time in the worst case. ∎

######  Theorem 5.8 (Tractable motif probabilities with local binding).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, $R\in\mathbb{N}$,
and $V^{\prime}=\\{u,v,w\\}\in\binom{V}{3}$, we can compute the closed-form
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}],\forall
E^{*}\subseteq\binom{V^{\prime}}{2}$ as a function w.r.t. $p$, $g$, and $R$.

###### Proof.

The overall idea is that we (1) consider all the sub-cases of how all the
pairs $\binom{V^{\prime}}{2}$ are partitioned and grouped during the whole
process, (2) compute the motif probabilities conditioned on each sub-case, and
(3) finally take the summation of the motif probabilities in all the sub-
cases.

We first consider all the cases of how all the pairs are sampled and grouped
until $\binom{V^{\prime}}{2}$ are fully determined. We divided the cases
w.r.t. how the pairs in $\binom{V^{\prime}}{2}$ are eventually grouped by the
sampled node sets. First let us define some “short-cut” variables:

  * •

the probability that among $V^{\prime}$, exactly $V^{*}$ is sampled together
in a round

$p_{g}(V^{*})\coloneqq\Pr\nolimits_{g}[\\{u,v,w\\}\cap
V_{s}=V^{*}]=\prod_{v\in V^{*}}g(v)\prod_{v^{\prime}\notin
V^{*}}(1-g(v)),\forall V^{*}\subseteq V^{\prime}$

  * •

the probability that among $V^{\prime}$, at least two nodes (and thus at least
one pair) are sampled together in a round

$\displaystyle p_{g}(\mathcal{V}_{\geq
2})\coloneqq\sum_{V^{*}\colon\left|V^{*}\right|\geq 2}p_{g}(V^{*})$
$\displaystyle=p_{g}(\\{u,v\\})+p_{g}(\\{u,w\\})+p_{g}(\\{v,w\\})+p_{g}(\\{u,v,w\\})$
$\displaystyle=g(u)g(v)(1-g(w))+g(u)g(w)(1-g(v))$
$\displaystyle~{}~{}~{}~{}+g(v)g(w)(1-g(u))+g(u)g(v)g(w)$

  * •

the probability that among $V^{\prime}$, at most one node (and thus no pair)
is sampled together in a round

$p_{g}(\mathcal{V}_{<2})\coloneqq 1-p_{g}(\mathcal{V}_{\geq 2})$

WLOG, we assume that $p(u,v)\geq p(u,w)\geq p(v,w)$.

$\\{u,v,w\\}$.white$\\{u,v,w\\}$. The first time any pair in
$\binom{V^{\prime}}{2}$ is sampled in the $R$ rounds is when $u$, $v$, and $w$
are sampled by $g$ together, which happens with probability

$\displaystyle q(\\{u,v,w\\})$
$\displaystyle=p_{g}(V^{\prime})+p_{g}(\mathcal{V}_{<2})p_{g}(V^{\prime})+p^{2}_{g}(\mathcal{V}_{<2})p_{g}(V^{\prime})+\cdots+p^{R-1}_{g}(\mathcal{V}_{<2})p_{g}(V^{\prime})$
$\displaystyle=\prod_{i=0}^{R-1}p^{i}_{g}(\mathcal{V}_{<2})p_{g}(V^{\prime})=\frac{1-p^{R}_{g}(\mathcal{V}_{<2})}{1-p_{g}(\mathcal{V}_{<2})}p_{g}(V^{\prime}),$

where each term $p^{i}_{g}(\mathcal{V}_{<2})p_{g}(V^{\prime})$ is the
probability that in the first $i$ rounds at most one node among $V^{\prime}$
is sampled and $V^{\prime}$ is sampled altogether in the $(i+1)$-th round.
Conditioned on that, it generates

  * •

$\\{(u,v),(u,w),(v,w)\\}$ with probability $p(v,w)$; when the random variable
$s$ in binding satisfies $s\leq p(v,w)$,

  * •

$\\{(u,v),(u,w)\\}$ with probability $p(u,w)-p(v,w)$; when $p(v,w)<s\leq
p(u,w)$,

  * •

$\\{(u,v)\\}$ with probability $p(u,v)-p(u,w)$; when $p(u,w)<s\leq p(u,v)$,
and

  * •

$\emptyset$ with probability $1-p(u,v)$; when $s>p(u,v)$.

$\\{u,v\\}\to\\{u,v,w\\}$.white$\\{u,v\\}\to\\{u,v,w\\}$. All the pairs in
$\binom{V^{\prime}}{2}$ are covered in twice in the $R$ rounds. At the first
time, $u$ and $v$ are sampled together by $g$ but not $w$. At the second time,
$u$, $v$, and $w$ are sampled together by $g$. This happens with probability

$\displaystyle q(\\{u,v\\}\to\\{u,v,w\\})$
$\displaystyle=p_{g}(V^{\prime})+\left(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\})\right)p_{g}(V^{\prime})+\cdots$
$\displaystyle~{}~{}~{}~{}+\left(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\})\right)^{R-1}p_{g}(V^{\prime})-q(\\{u,v,w\\})$
$\displaystyle=\sum_{i=0}^{R-1}\left(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\})\right)^{i}p_{g}(V^{\prime})-q(\\{u,v,w\\})$
$\displaystyle=\left(\frac{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\}))^{R}}{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\}))}-\frac{1-p^{R}_{g}(\mathcal{V}_{<2})}{1-p_{g}(\mathcal{V}_{<2})}\right)p_{g}(V^{\prime}),$

where
$\left(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,v\\})\right)^{i}p_{g}(V^{\prime})$
is the probability that in the first $i$ rounds we either sample no pair
between $V^{\prime}$ or just $(u,v)$, and we sample $V^{\prime}$ altogether in
the $(i+1)$-th round, and $q(\\{u,v,w\\})$ is subtracted to exclude the cases
where $(u,v)$ is not sampled in the first $i$ rounds. In such cases, when
$(u,v)$ is sampled for the first time, we decide the existence of $(u,v)$, and
then after that, when $V^{\prime}$ is sampled altogether for the first time,
we decide the existences of the remaining two pair $(u,w)$ and $(v,w)$. Hence,
conditioned on that, it generates

  * •

$\\{(u,v),(u,w),(v,w)\\}$ with probability $p(u,v)p(v,w)$; when $s_{1}\leq
p(u,v)$ in the round $(u,v)$ is sampled for the first time and $s_{2}\leq
p(v,w)$ in the round $V^{\prime}$ is sampled altogether for the first time,

  * •

$\\{(u,v),(u,w)\\}$ with probability $p(u,v)\left(p(u,w)-p(v,w)\right)$; when
$s_{1}\leq p(u,v)$ and $p(v,w)<s_{2}\leq p(u,w)$,

  * •

$\\{(u,v)\\}$ with probability $p(u,v)\left(1-p(u,w)\right)$; when $s_{1}\leq
p(u,v)$ and $s_{2}>p(u,w)$,

  * •

$\\{(u,w),(v,w)\\}$ with probability $\left(1-p(u,v)\right)p(v,w)$; when
$s_{1}>p(u,v)$ and $s_{2}\leq p(v,w)$,

  * •

$\\{(u,w)\\}$ with probability
$\left(1-p(u,v)\right)\left(p(u,w)-(v,w)\right)$; when $s_{1}>p(u,v)$ and
$p(v,w)<s_{2}\leq p(u,w)$, and

  * •

$\emptyset$ with probability $\left(1-p(u,v)\right)\left(1-p(u,w)\right)$;
when $s_{1}>p(u,v)$ and $s_{2}>p(u,w)$.

$\\{u,w\\}\to\\{u,v,w\\}$.white$\\{u,w\\}\to\\{u,v,w\\}$. Similarly, this
happens with probability

$q(\\{u,w\\}\to\\{u,v,w\\})=\left(\frac{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,w\\}))^{R}}{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{u,w\\}))}-\frac{1-p^{R}_{g}(\mathcal{V}_{<2})}{1-p_{g}(\mathcal{V}_{<2})}\right)p_{g}(V^{\prime})$

Conditioned on that, it generates

  * •

$\\{(u,v),(u,w),(v,w)\\}$ with probability $p(u,w)p(v,w)$; when $s_{1}\leq
p(u,w)$ and $s_{2}\leq p(v,w)$,

  * •

$\\{(u,v),(u,w)\\}$ with probability $p(u,w)\left(p(u,v)-p(v,w)\right)$; when
$s_{1}\leq p(u,w)$ and $p(v,w)<s_{2}\leq p(u,v)$,

  * •

$\\{(u,w)\\}$ with probability $p(u,w)\left(1-p(u,v)\right)$; when $s_{1}\leq
p(u,w)$ and $s_{2}>p(u,v)$,

  * •

$\\{(u,v),(v,w)\\}$ with probability $\left(1-p(u,w)\right)p(v,w)$; when
$s_{1}>p(u,w)$ and $s_{2}\leq p(v,w)$,

  * •

$\\{(u,v)\\}$ with probability
$\left(1-p(u,w)\right)\left(p(u,v)-(v,w)\right)$; when $s_{1}>p(u,w)$ and
$p(v,w)<s_{2}\leq p(u,v)$, and

  * •

$\emptyset$ with probability $\left(1-p(u,w)\right)\left(1-p(u,v)\right)$;
when $s_{1}>p(u,w)$ and $s_{2}>p(u,v)$.

$\\{v,w\\}\to\\{u,v,w\\}$.white$\\{v,w\\}\to\\{u,v,w\\}$. Similarly, this
happens with probability

$q(\\{v,w\\}\to\\{u,v,w\\})=\left(\frac{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{v,w\\}))^{R}}{1-(p_{g}(\mathcal{V}_{<2})+p_{g}(\\{v,w\\}))}-\frac{1-p^{R}_{g}(\mathcal{V}_{<2})}{1-p_{g}(\mathcal{V}_{<2})}\right)p_{g}(V^{\prime})$

Conditioned on that, it generates

  * •

$\\{(u,v),(u,w),(v,w)\\}$ with probability $p(v,w)p(u,w)$; when $s_{1}\leq
p(v,w)$ and $s_{2}\leq p(u,w)$,

  * •

$\\{(u,v),(v,w)\\}$ with probability $p(v,w)\left(p(u,v)-p(u,w)\right)$; when
$s_{1}\leq p(v,w)$ and $p(u,w)<s_{2}\leq p(u,v)$,

  * •

$\\{(v,w)\\}$ with probability $p(v,w)\left(1-p(u,v)\right)$; when $s_{1}\leq
p(v,w)$ and $s_{2}>p(u,v)$,

  * •

$\\{(u,v),(u,w)\\}$ with probability $\left(1-p(v,w)\right)p(u,w)$; when
$s_{1}>p(v,w)$ and $s_{2}\leq p(u,w)$,

  * •

$\\{(u,v)\\}$ with probability
$\left(1-p(v,w)\right)\left(p(u,v)-(u,w)\right)$; when $s_{1}>p(v,w)$ and
$p(u,w)<s_{2}\leq p(u,v)$, and

  * •

$\emptyset$ with probability $\left(1-p(v,w)\right)\left(1-p(u,v)\right)$;
when $s_{1}>p(v,w)$ and $s_{2}>p(u,v)$.

The remaining cases.whiteThe remaining cases. Three edges are determined
independently. This happens with the remaining probability

$q_{indep}=1-q(\\{u,v,w\\})-q(\\{u,v\\}\to\\{u,v,w\\})-q(\\{u,w\\}\to\\{u,v,w\\})-q(\\{v,w\\}\to\\{u,v,w\\})$

Conditioned on that, it generates each $E^{*}\subseteq\binom{V^{\prime}}{2}$
with probability

$\prod_{(x,y)\in
E^{*}}p(x,y)\prod_{(x^{\prime},y^{\prime})\in\binom{V^{\prime}}{2}\setminus
E^{*}}(1-p(x^{\prime},y^{\prime})).$

Taking the summation of all the sub-cases gives the results as follows.

$E^{*}=\\{(u,v),(u,w),(v,w)\\}$white$E^{*}=\\{(u,v),(u,w),(v,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(u,w),(v,w)\\}]=~{}$
$\displaystyle q(\\{u,v,w\\})p(v,w)+$ $\displaystyle
q(\\{u,v\\}\to\\{u,v,w\\})p(u,v)p(v,w)+$ $\displaystyle
q(\\{u,w\\}\to\\{u,v,w\\})p(u,w)p(v,w)+$ $\displaystyle
q(\\{v,w\\}\to\\{u,v,w\\})p(v,w)p(u,w)+$ $\displaystyle
q_{indep}p(u,v)p(u,w)p(v,w)$

$E^{*}=\\{(u,v),(u,w)\\}$white$E^{*}=\\{(u,v),(u,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(u,w)\\}]=~{}$
$\displaystyle q(\\{u,v,w\\})\left(p(u,w)-p(v,w)\right)+$ $\displaystyle
q(\\{u,v\\}\to\\{u,v,w\\})p(u,v)\left(p(u,w)-p(v,w)\right)+$ $\displaystyle
q(\\{u,w\\}\to\\{u,v,w\\})p(u,w)\left(p(u,v)-p(v,w)\right)+$ $\displaystyle
q(\\{v,w\\}\to\\{u,v,w\\})\left(1-p(v,w)\right)p(u,w)+$ $\displaystyle
q_{indep}p(u,v)p(u,w)\left(1-p(v,w)\right)$

$E^{*}=\\{(u,v),(v,w)\\}$white$E^{*}=\\{(u,v),(v,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(v,w)\\}]=~{}$
$\displaystyle q(\\{u,w\\}\to\\{u,v,w\\})\left(1-p(u,w)\right)p(v,w)+$
$\displaystyle q(\\{v,w\\}\to\\{u,v,w\\})p(v,w)\left(p(u,v)-p(u,w)\right)+$
$\displaystyle q_{indep}p(u,v)p(v,w)\left(1-p(u,w)\right)$

$E^{*}=\\{(u,w),(v,w)\\}$white$E^{*}=\\{(u,w),(v,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w),(v,w)\\}]=~{}$
$\displaystyle q(\\{u,v\\}\to\\{u,v,w\\})\left(1-p(u,v)\right)p(v,w)+$
$\displaystyle q_{indep}p(u,w)p(v,w)\left(1-p(u,v)\right)$

$E^{*}=\\{(u,v)\\}$white$E^{*}=\\{(u,v)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v)\\}]=~{}$
$\displaystyle q(\\{u,v,w\\})\left(p(u,v)-p(u,w)\right)+$ $\displaystyle
q(\\{u,v\\}\to\\{u,v,w\\})p(u,v)\left(1-p(u,w)\right)+$ $\displaystyle
q(\\{u,w\\}\to\\{u,v,w\\})\left(1-p(u,w)\right)\left(p(u,v)-p(v,w)\right)+$
$\displaystyle
q(\\{v,w\\}\to\\{u,v,w\\})\left(1-p(v,w)\right)\left(p(u,v)-p(u,w)\right)+$
$\displaystyle q_{indep}p(u,v)\left(1-p(u,w)\right)\left(1-p(v,w)\right)$

$E^{*}=\\{(u,w)\\}$white$E^{*}=\\{(u,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w)\\}]=~{}$
$\displaystyle
q(\\{u,v\\}\to\\{u,v,w\\})\left(1-p(u,v)\right)\left(p(u,w)-p(v,w)\right)+$
$\displaystyle q(\\{u,w\\}\to\\{u,v,w\\})p(u,w)\left(1-p(u,v)\right)+$
$\displaystyle q_{indep}p(u,w)\left(1-p(u,v)\right)\left(1-p(v,w)\right)$

$E^{*}=\\{(v,w)\\}$white$E^{*}=\\{(v,w)\\}$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w)\\}]=~{}$
$\displaystyle q(\\{v,w\\}\to\\{u,v,w\\})p(v,w)\left(1-p(u,v)\right)+$
$\displaystyle q_{indep}p(v,w)\left(1-p(u,v)\right)\left(1-p(u,w)\right)$

$E^{*}=\emptyset$white$E^{*}=\emptyset$

$\displaystyle\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w)\\}]=~{}$
$\displaystyle q(\\{u,v,w\\})\left(1-p(u,v)\right)+$ $\displaystyle
q(\\{u,v\\}\to\\{u,v,w\\})\left(1-p(u,v)\right)\left(1-p(u,w)\right)+$
$\displaystyle
q(\\{u,w\\}\to\\{u,v,w\\})\left(1-p(u,w)\right)\left(1-p(u,v)\right)+$
$\displaystyle
q(\\{v,w\\}\to\\{u,v,w\\})\left(1-p(v,w)\right)\left(1-p(u,v)\right)+$
$\displaystyle
q_{indep}\left(1-p(u,v)\right)\left(1-p(u,w)\right)\left(1-p(v,w)\right)$

∎

Discussion on higher orders.whiteDiscussion on higher orders. As mentioned in
Remark 5.9, the reasoning in the proof above can be extended to higher orders.
When the order of motifs increases, enumerating the cases of how all the pairs
are sampled and grouped becomes more and more challenging. When considering
$3$-motifs, we are essentially considering the possible partitions of three
pairs, and the number of possible cases is the Bell number (Bell, 1934)
$B_{3}=5$ as we have shown in the proof above. The high-level idea would be
similar, but the number increases exponentially:

  * •

for $4$-motifs, we need to consider up to $B_{4}=15$ cases

  * •

for $5$-motifs, we need to consider up to $B_{5}=52$ cases

  * •

for $6$-motifs, we need to consider up to $B_{6}=203$ cases, and so on

  * •

See sequence A000110 in the OEIS (Sloane, 2007)999https://oeis.org/A000110

In principle, we can also derive the variance of the number of $3$-motif by
considering the probabilities of $6$-motifs, since the co-existence of two
$3$-motifs involves motifs up to order $6$.

######  Theorem 5.10 (Time complexity of computing motif probabilities with
local binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, computing
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes
$O(\left|V\right|^{3})$ time in total for all
$E^{*}\subseteq\binom{V^{\prime}}{2}$ and $V^{\prime}\in\binom{V}{3}$.

###### Proof.

For computing motif probabilities, we need to enumerate all triplets
$V^{\prime}=\\{u,v,w\\}\in\binom{V}{3}$ and compute the motif probability for
each $3$-motif. For each motif, the calculation only involves arithmetic
operations, which takes $O(1)$ time since the formulae are fixed. In
conclusion, computing $3$-motif probabilities takes
$O(\binom{\left|V\right|}{3})$ time. ∎

###  C.5 Parallel binding

######  Proposition C.2 (Parallel binding produces EPGMs).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, $f^{\text{PB}}_{p;g,R}\in\mathcal{F}(p)$.

###### Proof.

For each pair $(u,v)$, if $\frac{1-\left(1-p(u,v)\right)^{1/R}}{g(u)g(v)}\leq
1$, i.e., $p(u,v)\leq 1-(1-g(u)g(v))^{R}$, then $p_{rem}(u,v)=0$ and

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[(u,v)]$
$\displaystyle=1-\Pr[\text{$(u,v)$ not inserted in the $R$
rounds}]\Pr[\text{$(u,v)$ not inserted when dealing with $p_{rem}$}]$
$\displaystyle=1-(1-g(u)g(v)r(u,v))^{R}(1-p_{rem})$
$\displaystyle=1-(1-p(u,v))$ $\displaystyle=p(u,v).$

Otherwise, if $p(u,v)>1-(1-g(u)g(v))^{R}$, then $r(u,v)=1$ and

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[(u,v)]$
$\displaystyle=1-\Pr[\text{$(u,v)$ not inserted in the $R$
rounds}]\Pr[\text{$(u,v)$ not inserted when dealing with $p_{rem}$}]$
$\displaystyle=1-(1-g(u)g(v)r(u,v))^{R}(1-p_{rem})$
$\displaystyle=1-(1-g(u)g(v))^{R}\frac{1-p(u,v)}{(1-g(u)g(v))^{R}}$
$\displaystyle=1-(1-p(u,v))$ $\displaystyle=p(u,v).$

∎

######  Theorem C.3 (Time complexities of graph generation with parallel
binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, $f^{\text{PB}}_{p;g,R}$ generates a graph in
$O(R\left(\sum_{v\in V}g(v)\right)^{2}+\left|V\right|^{2})$ time with high
probability, with the worst case $O(R\left|V\right|^{2})$.

###### Proof.

We have at most $R$ rounds of sampling and binding, where each round samples
at most $\left|V\right|$ nodes and thus at most $\binom{\left|V\right|}{2}$
pairs. More specifically, the number of nodes sampled in each round is
$\sum_{v\in V}g(v)$ in expectation, and thus $O(\sum_{v\in V}g(v))$ with high
probability (e.g., one can use a Chernoff bound). Hence, it takes
$O(R\sum_{v\in V}g(v))$ time with high probability, and at most
$O(\binom{\left|V\right|}{2}R)$ time for the $R$ rounds. The number of pairs
with $p_{rem}>0$ is at most $\binom{\left|V\right|}{2}$ so dealing with them
takes $O(\binom{\left|V\right|}{2})$ time. In conclusion, generating a graph
takes $O(R\sum_{v\in V}g(v)+\left|V\right|^{2})$ with high probability, and
$O(\binom{\left|V\right|}{2}R)$ time in the worst case. ∎

######  Theorem C.4 (Tractable motif probabilities with parallel binding).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, $R\in\mathbb{N}$,
and $V^{\prime}=\\{u,v,w\\}\in\binom{V}{3}$, we can compute the closed-form
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}],\forall
E^{*}\subseteq\binom{V^{\prime}}{2}$ as a function w.r.t. $p$, $g$, and $R$.

###### Proof.

The overall idea is that we (1) compute the probabilities of each subset of
$\binom{V^{\prime}}{2}$ being inserted in each round and (2) accumulate the
probabilities in $R$ rounds to obtain the final motif probabilities.

We first compute the probability of each subset of $\binom{V}{2}$ being
inserted in each round. We divide the cases w.r.t. different sets of sampled
nodes $V_{s}\cap V^{\prime}$. First, let us define some “short-cut” variables:

  * •

the probability that among $V^{\prime}$, exactly $V^{*}$ is sampled together
in a round

$p_{g}(V^{*})\coloneqq\Pr\nolimits_{g}[\\{u,v,w\\}\cap
V_{s}=V^{*}]=\prod_{v\in V^{*}}g(v)\prod_{v^{\prime}\notin
V^{*}}(1-g(v)),\forall V^{*}\subseteq V^{\prime}$

  * •

the probability that among $V^{\prime}$, at least two nodes (and thus at least
one pair) are sampled together in a round

$\displaystyle p_{g}(\mathcal{V}_{\geq
2})\coloneqq\sum_{V^{*}\colon\left|V^{*}\right|\geq 2}p_{g}(V^{*})$
$\displaystyle=p_{g}(\\{u,v\\})+p_{g}(\\{u,w\\})+p_{g}(\\{v,w\\})+p_{g}(\\{u,v,w\\})$
$\displaystyle=g(u)g(v)(1-g(w))+g(u)g(w)(1-g(v))+g(v)g(w)(1-g(u))$

  * •

the probability that among $V^{\prime}$, at most one node (and thus no pair)
is sampled together in a round

$p_{g}(\mathcal{V}_{<2})\coloneqq 1-p_{g}(\mathcal{V}_{\geq 2})$

  * •

the variables $r$ and $p_{rem}$ are defined as in Algorithm 3.

WLGO, we assume that $p(u,v)\geq p(u,w)\geq p(v,w)$.

$V_{s}=\\{u,v,w\\}$.white$V_{s}=\\{u,v,w\\}$. This happens with probability
$p_{g}(V^{\prime})$. Conditioned on that, it generates

  * •

$\\{(u,v),(u,w),(v,w)\\}$ with probability $r(v,w)$; when $s\leq r(v,w)$,

  * •

$\\{(u,v),(u,w)\\}$ with probability $r(u,w)-r(v,w)$; when $r(v,w)<s\leq
r(u,w)$,

  * •

$\\{(u,v)\\}$ with probability $r(u,v)-r(u,w)$; when $r(u,w)<s\leq r(u,v)$,
and

  * •

$\emptyset$ with probability $1-r(u,v)$; when $s>r(u,v)$.

$V_{s}=\\{u,v\\}$.white$V_{s}=\\{u,v\\}$. This happens with probability
$p_{g}(\\{u,v\\})$. Conditioned on that, it generates

  * •

$\\{(u,v)\\}$ with probability $r(u,v)$; when $s\leq r(u,v)$, and

  * •

$\emptyset$ with probability $1-r(u,v)$l when $s>r(u,v)$.

$V_{s}=\\{u,w\\}$.white$V_{s}=\\{u,w\\}$. This happens with probability
$p_{g}(\\{u,w\\})$. Conditioned on that, it generates

  * •

$\\{(u,w)\\}$ with probability $r(u,w)$; when $s\leq r(u,w)$,

  * •

$\emptyset$ with probability $1-r(u,w)$; when $s>r(u,w)$.

$V_{s}\\{v,w\\}$.white$V_{s}\\{v,w\\}$. This happens with probability
$p_{g}(\\{v,w\\})$. Conditioned on that, it generates

  * •

$\\{(v,w)\\}$ with probability $r(v,w)$; when $s\leq r(v,w)$,

  * •

$\emptyset$ with probability $1-r(v,w)$; when $s>r(v,w)$.

The remaining cases (i.e., $\left|V_{s}\cap V^{\prime}\right|\leq 1$).whiteThe
remaining cases (i.e., $\left|V_{s}\cap V^{\prime}\right|\leq 1$). This
happens with probability $p_{g}(\mathcal{V}_{<2})$. Conditioned on that, it
generates

  * •

$\emptyset$ with probability $1$.

Summary for each round.whiteSummary for each round. Let $p_{round}(E^{*})$
denote the probability of $E^{*}$ being generated in each round, for each
$E^{*}\subseteq\binom{V^{\prime}}{2}$. We have

  * •

$p_{round}(\\{(u,v),(u,w),(v,w)\\})=p_{g}(V^{\prime})r(v,w)$,

  * •

$p_{round}(\\{(u,v),(u,w)\\})=p_{g}(V^{\prime})(r(u,w)-r(v,w))$,

  * •

$p_{round}(\\{(u,v)\\})=p_{g}(V^{\prime})\left(r(u,v)-r(u,w)\right)+p_{g}(\\{u,v\\})r(u,v)$,

  * •

$p_{round}(\\{(u,w)\\})=p_{g}(\\{u,w\\})r(u,w)$,

  * •

$p_{round}(\\{(v,w)\\})=p_{g}(\\{v,w\\})r(v,w)$, and

  * •

$p_{round}(\emptyset)=1-p_{g}(V^{\prime})r(u,v)-p_{g}(\\{u,v\\})r(u,v)-p_{g}(\\{u,w\\})r(u,w)-p_{g}(\\{v,w\\})r(v,w)$.

We are now ready to compute the motif probabilities.

$E^{*}=\emptyset$.white$E^{*}=\emptyset$. This happens when $\emptyset$ is
generated in all $R$ rounds and for the remaining probabilities $p_{rem}$,
with probability

$\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\emptyset]=(p_{round}(\emptyset))^{R}(1-p_{rem}(u,v))(1-p_{rem}(u,w))(1-p_{rem}(v,w)).$

$E^{*}=\\{(u,v)\\}$.white$E^{*}=\\{(u,v)\\}$. This happens when either
$\emptyset$ or $\\{(u,v)\\}$ is generated in all $R$ rounds and for $p_{rem}$,
and $(u,v)$ is generated in at least one round, which has probability

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(u,v)(1-p_{rem}(u,w))(1-p_{rem}(v,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-(p_{round}(\emptyset))^{R})(1-p_{rem}(u,w))(1-p_{rem}(v,w)),$

where
$((p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-(p_{round}(\emptyset))^{R})$
is the probability that in the $R$ rounds, only $(u,v)$ is inserted.

$E^{*}=\\{(u,w)\\}$.white$E^{*}=\\{(u,w)\\}$. Similarly, this happens with
probability

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(u,w)(1-p_{rem}(u,v))(1-p_{rem}(v,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,w)\\}))^{R}-(p_{round}(\emptyset))^{R})(1-p_{rem}(u,v))(1-p_{rem}(v,w)).$

$E^{*}=\\{(v,w)\\}$.white$E^{*}=\\{(v,w)\\}$. Similarly, this happens with
probability

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[v^{\prime}])=\\{(u,w)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(v,w)(1-p_{rem}(u,v))(1-p_{rem}(u,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(v,w)\\}))^{R}-(p_{round}(\emptyset))^{R})(1-p_{rem}(u,v))(1-p_{rem}(u,w)).$

$E^{*}=\\{(u,v),(u,w)\\}$.white$E^{*}=\\{(u,v),(u,w)\\}$. This happens when
one among $\emptyset$, $\\{(u,v)\\}$, $\\{(u,w)\\}$, and $\\{(u,v),(u,w)\\}$
is generated in all $R$ rounds and for $R_{rem}$, while excluding the cases
ending up with $\emptyset$, $\\{(u,v)\\}$, or $\\{(u,w)\\}$. This happens with
probability

$\displaystyle\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(u,w)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(u,v)p_{rem}(u,w)(1-p_{rem}(v,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(u,w)(1-p_{rem}(v,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,w)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(u,v)(1-p_{rem}(v,w))+$
$\displaystyle\tilde{p}(\\{(u,v),(u,w)\\};R)(1-p_{rem}(v,w)),$

where

$\displaystyle\tilde{p}(\\{(u,v),(u,w)\\};R)$ $\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,v)\\})+p_{round}(\\{(u,w)\\})+p_{round}(\\{(u,v),(u,w)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,w)\\}))^{R}+$
$\displaystyle(p_{round}(\emptyset))^{R}$

is the probability that exactly $(u,v)$ and $(u,w)$ are inserted in the $R$
rounds, using the inclusion-exclusion principle.

$E^{*}=\\{(u,v),(v,w)\\}$.white$E^{*}=\\{(u,v),(v,w)\\}$. Similarly, this
happens with probability

$\displaystyle~{}\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(v,w)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(u,v)p_{rem}(v,w)(1-p_{rem}(u,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(v,w)(1-p_{rem}(u,w))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(v,w)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(u,v)(1-p_{rem}(u,w))+$
$\displaystyle\tilde{p}(\\{(u,v),(v,w)\\};R)(1-p_{rem}(u,w)),$

where

$\displaystyle\tilde{p}(\\{(u,v),(v,w)\\};R)=~{}$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,v)\\})+p_{round}(\\{(v,w)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,v)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(v,w)\\}))^{R}+$
$\displaystyle(p_{round}(\emptyset))^{R}.$

Note that $p_{round}(\\{(u,v),(v,w)\\})=0$.

$E^{*}=\\{(u,w),(v,w)\\}$.white$E^{*}=\\{(u,w),(v,w)\\}$. Similarly, this
happens with probability

$\displaystyle~{}\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w),(v,w)\\}]$
$\displaystyle=~{}$
$\displaystyle(p_{round}(\emptyset))^{R}p_{rem}(u,w)p_{rem}(v,w)(1-p_{rem}(u,v))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,w)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(v,w)(1-p_{rem}(u,v))+$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(v,w)\\}))^{R}-(p_{round}(\emptyset))^{R})p_{rem}(u,w)(1-p_{rem}(u,v))+$
$\displaystyle\tilde{p}(\\{(u,w),(v,w)\\};R)(1-p_{rem}(u,v)),$

where

$\displaystyle\tilde{p}(\\{(u,w),(v,w)\\};R)=~{}$
$\displaystyle((p_{round}(\emptyset)+p_{round}(\\{(u,w)\\})+p_{round}(\\{(v,w)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(u,w)\\}))^{R}-$
$\displaystyle(p_{round}(\emptyset)+p_{round}(\\{(v,w)\\}))^{R}+$
$\displaystyle(p_{round}(\emptyset))^{R})$

Note that $p_{round}(\\{(u,w),(v,w)\\})=0$.

$E^{*}=\\{(u,v),(u,w),(v,w)\\}$.white$E^{*}=\\{(u,v),(u,w),(v,w)\\}$. This
happens with the remaining probability, i.e.,

$\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(u,w),(v,w)\\}]=1-\sum_{E^{\prime}\subsetneq\binom{V^{\prime}}{2}}\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{\prime}].$

∎

Discussion on higher orders.whiteDiscussion on higher orders. Similar to the
counterpart for local binding, the reasoning in the proof above can be
extended to higher orders. When the order of motifs increases, both
considering the cases in each round and accumulating them in multiple rounds
become increasingly challenging. For the cases in each round, we first need to
consider more cases of $V_{s}$, i.e., all the subsets of $V^{\prime}$. For
accumulating the probabilities, for each $E^{*}$, we first need to consider
all the cases (i.e., all the subsets of $E^{*}$) in each round that can
accumulate to $E*$, and we need to use the inclusion-exclusion principle to
avoid counting some sub-motifs multiple times, where again all the subsets of
$E^{*}$ need to be considered. Hence, for motifs of order $k$, the number of
cases is at least $O(2^{\binom{k}{2}})$.

######  Theorem C.5 (Time complexity of computing motif probabilities with
parallel binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, computing
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes
$O(\left|V\right|^{3})$ time in total for all
$E^{*}\subseteq\binom{V^{\prime}}{2}$ and $V^{\prime}\in\binom{V}{3}$.

###### Proof.

For computing motif probabilities, we need to enumerate all triplets
$V^{\prime}=\\{u,v,w\\}\in\binom{V}{3}$ and compute the motif probability for
each $3$-motif. For each motif, the calculation only involves arithmetic
operations, which takes $O(1)$ time since the formulae are fixed. In
conclusion, computing $3$-motif probabilities takes
$O(\binom{\left|V\right|}{3})$ time. ∎

###  C.6 Fitting

####  C.6.1 The Erdős-Rényi (ER) model

Definition.whiteDefinition. The Erdős-Rényi (ER) model (Erdős & Rényi, 1959)
outputs edge probabilities with two parameters: $n_{0}$ and $p_{0}$, and the
output is $p^{ER}_{n_{0},p_{0}}$ with $p^{ER}_{n_{0},p_{0}}(u,v)=p_{0},\forall
u,v\in\binom{V}{2}$ with $V=[n_{0}]$. Given a graph $G=(V=[n],E)$, ER outputs
$n_{0}=n$ and $p_{0}=\frac{2\left|E\right|}{n(n-1)}$.

######  Lemma 5.12 (Reduced time complexity with ER).

Given $n_{0}\in\mathbb{N}$, $p_{0}\in[0,1]$, $g_{0}\in[0,1]$, and
$R\in\mathbb{N}$, computing both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes $O(1)$ times in
total for all $E^{*}\subseteq\binom{V^{\prime}}{2}$ and
$V^{\prime}\in\binom{V}{3}$ with $p=p^{ER}_{n_{0},p_{0}}$ and
$g(v)=g_{0},\forall v\in V=[n_{0}]$.

###### Proof.

When $p(u,v)\equiv v_{0}$ and $g(v)\equiv g_{0}$, both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ become the same
functions for all $V^{\prime}\in\binom{V}{3}$, which only involve arithmetic
operations on $p_{0}$ and $g_{0}$ and thus take $O(1)$ time for computation.
Since the functions are the same for all $V^{\prime}\in\binom{V}{3}$, we only
need to calculate for a single $V^{\prime}$. Hence, the total time complexity
is still $O(1)$. The detailed formulae are as follows.

Local binding.whiteLocal binding. Fix any $V^{\prime}\in\binom{V}{3}$, we have

$p_{g}(V^{*})=g^{\left|V^{*}\right|}_{0}(1-g_{0})^{3-\left|V^{*}\right|},\forall
V^{*}\subseteq V^{\prime},$ $p_{g}(\mathcal{V}_{\geq
2})=3g^{2}_{0}(1-g_{0})+g^{3}_{0},$

and

$p_{g}(\mathcal{V}_{<2})=3g_{0}(1-g_{0})^{2}+(1-g_{0})^{3}.$

Hence

$q(\\{u,v,w\\})=\frac{1-\left(3g_{0}(1-g_{0})^{2}+(1-g_{0})^{3}\right)^{R}}{3g^{2}_{0}(1-g_{0})+g^{3}_{0}}g^{3}_{0},$
$\displaystyle q_{2}$ $\displaystyle\coloneqq
q(\\{u,v\\}\to\\{u,v,w\\})=q(\\{u,w\\}\to\\{u,v,w\\})=q(\\{v,w\\}\to\\{u,v,w\\})$
$\displaystyle=\left(\frac{1-\left(3g_{0}(1-g_{0})^{2}+(1-g_{0})^{3}+g^{2}_{0}(1-g_{0})\right)^{R}}{2g^{2}_{0}(1-g_{0})+g^{3}_{0}}-\frac{1-\left(3g_{0}(1-g_{0})^{2}+(1-g_{0})^{3}\right)^{R}}{3g^{2}_{0}(1-g_{0})+g^{3}_{0}}\right),$

and

$q_{indep}=1-q(\\{u,v,w\\})-3q_{2}.$

$E^{*}=\\{(u,v),(u,w),(v,w)\\}$white$E^{*}=\\{(u,v),(u,w),(v,w)\\}$

$\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,v),(u,w),(v,w)\\}]=q(\\{u,v,w\\})p_{0}+3q_{2}p^{2}_{0}+q_{indep}p^{3}_{0}$

$\left|E^{*}\right|=2$white$\left|E^{*}\right|=2$

For each $E^{*}$ with $\left|E^{*}\right|=2$, i.e., $E^{*}=\\{(u,v),(u,w)\\}$
or $\\{(u,v),(v,w)\\}$ or $(u,w),(v,w)$, we have

$\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]=q_{2}p_{0}(1-p_{0})+q_{indep}p^{2}_{0}(1-p_{0})$

$\left|E^{*}\right|=1$white$\left|E^{*}\right|=1$

For each $E^{*}$ with $\left|E^{*}\right|=1$, i.e., $E^{*}=\\{(u,v)\\}$ or
$\\{(u,w)\\}$ or $(v,w)$, we have

$\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]=q_{2}p_{0}(1-p_{0})+q_{indep}p_{0}(1-p_{0})^{2}$

$E^{*}=\emptyset$white$E^{*}=\emptyset$

$\Pr\nolimits_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=\\{(u,w)\\}]=q(\\{u,v,w\\})(1-p_{0})+3q_{2}(1-p_{0})^{2}+q_{indep}(1-p_{0})^{3}$

∎

####  C.6.2 The Chung-Lu (CL) model

Definition.whiteDefinition. The Chung-Lu (CL) model (Chung & Lu, 2002) outputs
edge probabilities with a sequence of expected degrees
$D=(d_{1},d_{2},\ldots,d_{n})$, and the output is $p^{CL}_{D}$ with
$p^{CL}_{D}(u,v)=\min(\frac{d_{u}d_{v}}{\sum_{i=1}^{n}d_{i}},1),\forall
u,v\in\binom{V}{2}$ with $V=[n]$. Given a graph $G=(V=[n],E)$, CL outputs
$d_{i}=d(i;G)$ for each node $i\in V$.

######  Lemma 5.13 (Reduced time complexity with CL).

Given $D=(d_{1},d_{2},\ldots,d_{n})$, $g_{d}$ for
$d\in\\{d_{1},d_{2},\ldots,d_{n}\\}$, and $R\in\mathbb{N}$, computing both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ for all
$E^{*}\subseteq\binom{V^{\prime}}{2}$ and $V^{\prime}\in\binom{[n]}{3}$ takes
$O(k^{3}_{deg})$ times with $p=p^{CL}_{D}$ and $g(i)=g_{d_{i}},\forall
i\in[n]$.

###### Proof.

The key idea is that given $V^{\prime}=\\{i,j,k\\}\in\binom{V}{3}$, both the
three edge probabilities (i.e., $p(i,j)$, $p(i,k)$, and $p(j,k)$) and the
three node-sampling probabilities (i.e., $g(i)$, $g(j)$, and $g(k)$) are fully
determined by the degrees of the three nodes.

Hence, we only need to calculate motif probabilities for each degree
combination instead of each node combination. Since we have $k_{deg}$
different degrees, the total number of degree combinations of size $3$ is
$O(k^{3}_{deg})$, and the calculation for each combination takes $O(1)$ time
on arithmetic operations with fixed formulae. In conclusion, the total time
complexity is $O(k^{3}_{deg})$.

Some details are as follows. Let
$k_{deg}=\\{d_{1},d_{2},\ldots,d_{n}\\}=\\{\tilde{d}_{1},\tilde{d}_{2},\ldots,\tilde{d}_{k_{deg}}\\}$,
and let $n_{i}$ denote the number of nodes with degree $\tilde{d}_{i}$, for
$i\in[k_{deg}]$. Given three degrees $\tilde{d}_{i}$, $\tilde{d}_{j}$, and
$\tilde{d}_{k}$, we have

  * •

$n_{i}n_{j}n_{k}$ such combinations, when $i\neq j$, $i\neq k$, and $j\neq k$

  * •

$\binom{n_{i}}{2}n_{k}$ such combinations, when $i=j$ and $i\neq k$; similarly
for $i=k$ and $i\neq j$ or $j=k$ and $i\neq j$

  * •

$\binom{n_{i}}{3}$ such combinations, when $i=j=k$.

∎

####  C.6.3 The stochastic block (SB) model

Definition.whiteDefinition. Given a graph $G=(V=[n],E)$ and a node partition
$f_{B}\colon[n]\to[c]$ with $c\in\mathbb{N}$, let $V_{i}=\\{v\in V\colon
f_{B}(v)=i\\}$ denote the set of nodes partitioned in the $i$-th group for
$i\in[c]$. The fitting of the edge probabilities in the stochastic block (SB)
model gives $p_{B}\colon[c]\times[c]\to[0,1]$ with
$p_{B}(i,i)=\frac{\left|E(G[V_{i}])\right|}{\binom{\left|V_{i}\right|}{2}}$
and $p_{B}(i,j)=\frac{\left|E\cap\\{(v,v^{\prime})\colon v\in
V_{i},v^{\prime}\in V_{j}\\}\right|}{\left|V_{i}\right|\left|V_{j}\right|}$,
for $i\neq j\in[c]$.

######  Lemma 5.14 (Reduced time complexity with SB).

Given $f_{B}\colon[n_{0}]\to[c]$, $f_{B}\colon[n_{0}]\to[c]$, $g_{i}$ for
$i\in[c]$, and $R\in\mathbb{N}$, computing both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes $O(c^{3})$ times
in total for all $E^{*}\subseteq\binom{V^{\prime}}{2}$ and
$V^{\prime}\in\binom{[n]}{3}$ with $p=p^{SB}_{f_{B},p_{B}}$ and
$g(v)=g_{f_{B}(v)}$ for each $v\in V=[n]$.

###### Proof.

The key idea is that given $V^{\prime}=\\{i,j,k\\}\in\binom{V}{3}$, both the
three edge probabilities (i.e., $p(i,j)$, $p(i,k)$, and $p(j,k)$) and the
three node-sampling probabilities (i.e., $g(i)$, $g(j)$, and $g(k)$) are fully
determined by the membership the three nodes, i.e., $f_{B}(i)$, $f_{B}(j)$,
and $f_{B}(k)$.

Hence, we only need to calculate motif probabilities for each membership
combination instead of each node combination. Since we have $c$ different
groups, the total number of degree combinations of size $3$ is $O(c^{3})$, and
the calculation for each combination takes $O(1)$ time on arithmetic
operations with fixed formulae. In conclusion, the total time complexity is
$O(c^{3})$.

Some details are as follows. Let $n_{i}=\left|V_{i}\right|$ denote the number
of nodes in the $i$-th group. Given three group membership indicators $i$,
$j$, and $k$, we have

  * •

$n_{i}n_{j}n_{k}$ such combinations, when $i\neq j$, $i\neq k$, and $j\neq k$

  * •

$\binom{n_{i}}{2}n_{k}$ such combinations, when $i=j$ and $i\neq k$; similarly
for $i=k$ and $i\neq j$ or $j=k$ and $i\neq j$

  * •

$\binom{n_{i}}{3}$ such combinations, when $i=j=k$.

∎

####  C.6.4 The stochastic Kronecker (KR) model

######  Definition C.6 (Kronecker product and Kronecker power).

Given two matrices $A\in\mathbb{R}^{m\times n}$ and $B\in\mathbb{R}^{p\times
q}$, the Kronecker product between $A$ and $B$ is

${\mathbf{A}\otimes\mathbf{B}}=\begin{bmatrix}a_{11}b_{11}&a_{11}b_{12}&\cdots&a_{11}b_{1q}&\cdots&\cdots&a_{1n}b_{11}&a_{1n}b_{12}&\cdots&a_{1n}b_{1q}\\\
a_{11}b_{21}&a_{11}b_{22}&\cdots&a_{11}b_{2q}&\cdots&\cdots&a_{1n}b_{21}&a_{1n}b_{22}&\cdots&a_{1n}b_{2q}\\\
\vdots&\vdots&\ddots&\vdots&&&\vdots&\vdots&\ddots&\vdots\\\
a_{11}b_{p1}&a_{11}b_{p2}&\cdots&a_{11}b_{pq}&\cdots&\cdots&a_{1n}b_{p1}&a_{1n}b_{p2}&\cdots&a_{1n}b_{pq}\\\
\vdots&\vdots&&\vdots&\ddots&&\vdots&\vdots&&\vdots\\\
\vdots&\vdots&&\vdots&&\ddots&\vdots&\vdots&&\vdots\\\
a_{m1}b_{11}&a_{m1}b_{12}&\cdots&a_{m1}b_{1q}&\cdots&\cdots&a_{mn}b_{11}&a_{mn}b_{12}&\cdots&a_{mn}b_{1q}\\\
a_{m1}b_{21}&a_{m1}b_{22}&\cdots&a_{m1}b_{2q}&\cdots&\cdots&a_{mn}b_{21}&a_{mn}b_{22}&\cdots&a_{mn}b_{2q}\\\
\vdots&\vdots&\ddots&\vdots&&&\vdots&\vdots&\ddots&\vdots\\\
a_{m1}b_{p1}&a_{m1}b_{p2}&\cdots&a_{m1}b_{pq}&\cdots&\cdots&a_{mn}b_{p1}&a_{mn}b_{p2}&\cdots&a_{mn}b_{pq}.\end{bmatrix}$

Given $k\in\mathbb{N}$, the $k$ Kronecker power of $A$ is

$\underbrace{A\otimes(A\cdots(A\otimes(A\otimes A)))}_{\text{$k-1$ times of
Kronecker products}}.$

Definition.whiteDefinition. The stochastic Kronecker (KR) model (Leskovec et
al., 2010) outputs edge probabilities with a seed matrix
$\theta\in[0,1]^{2\times 2}$ and $k_{KR}\in\mathbb{N}$,101010We consider the
commonly used $2$-by-$2$ seed matrices., and the output
$p^{KR}_{\theta,k_{KR}}$ is the $k_{KR}$-th Kronecker power of $\theta$.

######  Lemma C.7 (Node equivalence in KR).

Given $\theta\in[0,1]^{2\times 2}$, $k_{KR}\in\mathbb{N}$, $g_{i}$ for $0\leq
i\leq k_{KR}$, and $R\in\mathbb{N}$, computing both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ takes $O(k^{7}_{KR})$
times in total for all $E^{*}\subseteq\binom{V^{\prime}}{2}$ and
$V^{\prime}\in\binom{[n]}{3}$ with $p=p^{KR}_{\theta,k_{KR}}$ and $g(v)=g_{i}$
with $i$ being the number of ones in the binary representation of $v-1$, for
each $v\in[2^{k_{KR}}]$.

###### Proof.

A square binary matrix $P\in\\{0,1\\}^{n\times n}$ for some $n\in\mathbb{N}$
is a permutation matrix if exactly one entry in each row or column of $P$ is
$1$, i.e., $\sum_{k}P_{ik}=\sum_{k}P_{kj}=1,\forall i,j\in[n]$.

With binary node labels, given two nodes

$u=(u_{1}u_{2}\cdots u_{k_{KR}})_{2}$

and

$v=(v_{1}v_{2}\cdots v_{k_{KR}})_{2},$

we have

$\theta^{(k_{KR})}_{uv}=\prod_{i=1}^{k_{KR}}\theta_{u_{i}v_{i}},$

which implies that for any permutation $\pi\in S_{k_{KR}}$,

$\theta^{(k_{KR})}_{uv}=\theta^{(k_{KR})}_{\pi(u)\pi(v)},\forall u,v,$

where with a slight abuse of notation,

$\pi(u)=(u_{\pi(1)}u_{\pi(2)}\cdots u_{\pi(k_{KR})})_{2}$

and

$\pi(v)=(v_{\pi(1)}v_{\pi(2)}\cdots v_{\pi(k_{KR})})_{2}.$

On the other hand, for any two nodes with the same number of ones in the
binary representations, we can find a permutation $\pi$ between the two binary
representations by seeing them as sequences. Let
$P=P_{\pi}\in\\{0,1\\}^{2^{k_{KR}}\times 2^{k_{KR}}}$ with $P_{ij}=1$ if and
only if $\pi$ converts the binary presentation of $i-1$ to that of $j-1$, and
we have $P^{\top}\theta^{(k_{KR})}_{uv}P=\theta^{(k_{KR})}_{uv}$. ∎

######  Remark C.8.

The equivalence in KR is slightly weaker than that in the other three models
(ER, CL, and SB). Specifically, in the other three models, “two nodes $i$ and
$j$ are equivalent” means that, when you swap $i$ and $j$ while keeping the
other nodes unchanged, the RGM is kept unchanged. For KR, the equivalence is
weaker in that you have to swap $i$ and $j$ together with all the other nodes
w.r.t. a permutation. This is also why the reduced time complexity is
$O(k^{7}_{KR})$ instead of $O(k^{3}_{KR})$ in Lemma 5.15.

Figure 2: The node combinations in KR.

######  Lemma 5.15 (Reduced time complexity with KR).

Given $\theta\in[0,1]^{2\times 2}$, $k_{KR}\in\mathbb{N}$, $g_{i}$ for $0\leq
i\leq k_{KR}$, and $R\in\mathbb{N}$, computing both
$\Pr_{f^{\text{LB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ and
$\Pr_{f^{\text{PB}}_{p;g,R}}[E(G[V^{\prime}])=E^{*}]$ for all
$E^{*}\subseteq\binom{V^{\prime}}{2}$ and $V^{\prime}\in\binom{[n]}{3}$ takes
$O(k^{7}_{KR})$ times with $p=p^{KR}_{\theta,k_{KR}}$ and $g(v)=g_{i}$ with
$i$ being the number of ones in the binary representation of $v-1$, for each
$v\in[2^{k_{KR}}]$.

###### Proof.

We divide node combinations w.r.t the binary node labels. As shown in the
proof of Lemma C.7, node combinations are equivalent with permutations on the
binary node labels. Hence, in each equivalent class of node combinations, we
can consider only the one with the form as shown in Figure 2, where each
number ($x_{0}$, $x_{1}$, $x_{00}$, etc.) represents the number of zeros and
ones. Here,

  * •

the first node $v_{1}$ (more precisely, its binary node representation) has
$x_{0}$ zeros first and then $x_{1}$ ones,

  * •

the second node $v_{2}$ has $x_{00}$ zeros, then $x_{01}$ ones, then $x_{10}$
zeros, and finally $x_{11}$ ones, and

  * •

the third node $v_{3}$ has $x_{000}$ zeros, then $x_{001}$ ones, then
$x_{010}$ zeros, then $x_{011}$ ones, then $x_{100}$ zeros, then $x_{101}$
ones, then $x_{110}$ zeros, and finally $x_{111}$ ones.

As indicated in the figure, we have

  * •

$x_{0}+x_{1}=k_{KR}$

  * •

$x_{00}+x_{01}=x_{0}$, $x_{10}+x_{11}=x_{1}$

  * •

$x_{000}+x_{001}=x_{00}$, $x_{010}+x_{011}=x_{01}$, $x_{100}+x_{101}=x_{10}$,
and $x_{110}+x_{111}=x_{11}$.

The number of different equivalent classes is upper-bounded by

$\displaystyle~{}\sum_{x_{0}=0}^{k_{KR}}\sum_{x_{00}=0}^{x_{0}}\sum_{x_{10}=0}^{k_{KR}-x_{0}}\sum_{x_{000}0}^{x_{0}0}\sum_{x_{010}=0}^{x_{0}-x_{0}0}\sum_{x_{100}=0}^{x_{10}}\sum_{x_{110}=0}^{k_{KR}-x_{0}-x_{10}}1$
$\displaystyle=~{}$
$\displaystyle\frac{(k_{KR}+1)(k_{KR}+2)(k_{KR}+3)(k_{KR}+4)(k_{KR}+5)(k_{KR}+6)(k_{KR}+7)}{5040}=O(k^{7}_{KR}).$

For each equivalent class, the calculation only involves arithmetic with a
fixed formula and thus takes $O(1)$ time. Note that the Kronecker power can be
computed beforehand with much lower time complexity, i.e., $o(k^{7}_{KR})$
(Seroussi & Ma, 1983). In conclusion, the total time complexity is
$O(k^{7}_{KR})$. ∎

##  Appendix D On (non-)isolated nodes

###  D.1 Tractable number of (non-)isolated nodes with parallel binding

######  Theorem D.1 (Tractable number of (non-)isolated nodes with parallel
binding).

For any $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, $R\in\mathbb{N}$,
we can compute the closed-form (w.r.t. $p$, $g$, and $R$)
$\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\left|\\{v\in G\colon d(v;G)\geq
1\\}\right|]$.

###### Proof.

By the linearity of expectation,

$\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\left|\\{v\in G\colon d(v;G)\geq
1\\}\right|]=\sum_{v\in V}\Pr\nolimits_{f^{\text{PB}}_{p;g,R}}[d(v;G)\geq 1].$

Hence, we only need to compute the probability of each node $v$ being
(non-)isolated. A node $v$ is isolated if and only if no edge incident to $v$
is inserted in each round. In each round, when $v$ is sampled, i.e., $v\in
V_{s}$, the probability that no edge incident to $v$ is inserted is
$1-\max_{u\in V_{s}}p(u,v)$. Let $p_{iso}(v)$ denote the aforementioned
probability and sort $V\setminus\\{v\\}=\\{u_{1},u_{2},\ldots,u_{n-1}\\}$ with
$n=\left|V\right|$ and $p(u_{1},v)\geq p(u_{2},v)\geq\cdots\geq p(u_{n-1},v)$.
We have

$p_{iso}(v)=(1-\Pr[v\in V_{s}])+\Pr[v\in
V_{s}](1-\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\max_{u\in
V_{s}}p(u,v)])=1-g(v)\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\max_{u\in
V_{s}}p(u,v)],$

where

$\displaystyle\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\max_{u\in V_{s}}p(u,v)]$
$\displaystyle=~{}$ $\displaystyle\Pr[u_{1}\in
V_{s}]p(u_{1},v)+\Pr[u_{1}\notin V_{s}\land u_{2}\in
V_{s}]p(u_{2},v)+\cdots+\Pr[(\bigwedge_{i=1}^{n-2}u_{i}\notin V_{s})\land
u_{n-1}\in V_{s}]p(u_{n-1},v)$ $\displaystyle=~{}$ $\displaystyle
g(u_{1})p(u_{1},v)+(1-g(u_{1}))g(u_{2})p(u_{2},v)+\cdots+\prod_{i=1}^{n-2}(1-g(u_{i}))g(u_{n-1})p(u_{n-1},v).$

Finally, the probability that $v$ is isolated after $R$ rounds and dealing
with $p_{rem}$ is

$\tilde{p}_{iso}(v)=(p_{iso}(v))^{R}(1-p_{rem}(v)),$

and thus the expected number of non-isolated nodes is

$\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\left|\\{v\in G\colon d(v;G)\geq
1\\}\right|]=\sum_{v\in V}(1-\tilde{p}_{iso}(v)).$

∎

The expected number of degree-$1$ nodeswhiteThe expected number of degree-$1$
nodes We can extend the reasoning above to compute the expected number of
degree-$1$ nodes. Fix a node $v$, for each node $u_{k}$, we shall compute the
probability that no other $(u_{k^{\prime}},v)$ with $k^{\prime}\neq k$ is
inserted, denoted by $p_{s}(v;u_{k})$, which is the probability of $v$ being
isolated plus the probability of $v$ being only adjacent to $u_{k}$. In other
words, we compute the probability of $v$ being isolated while ignoring
$u_{k}$. We have

$p_{s}(v;u_{k})=(1-g(v))+g(v)\tilde{p}_{s}(v;u_{k}),$

where

$\displaystyle\tilde{p}_{s}(v;u_{k})=~{}$ $\displaystyle
g(u_{1})(1-p(u_{1},v))+$
$\displaystyle(1-g(u_{1}))g(u_{2})(1-p(u_{2},v))+\cdots+$
$\displaystyle\prod_{i=1}^{k-2}(1-g(u_{i}))g(u_{k-1})(1-p(u_{k-1},v))+$
$\displaystyle\prod_{i=1}^{k-1}(1-g(u_{i}))g(u_{k})\hat{p}_{s}(v;u_{k})+$
$\displaystyle\prod_{i=1}^{k+1}(1-g(u_{i}))g(u_{k+1})(1-p(u_{k+1},v))+\cdots+$
$\displaystyle\prod_{i=1}^{n-2}(1-g(u_{i}))g(u_{n-1})p(u_{n-1},v)+$
$\displaystyle\prod_{i=1}^{n-1}(1-g(u_{i}))$

with

$\displaystyle\hat{p}_{s}(v;u_{k})=~{}$ $\displaystyle
g(u_{k+1})(1-p(u_{k+1},v))+$
$\displaystyle(1-g(u_{k+1}))g({u_{k+2}})(1-p(u_{k+2},v))+\cdots+$
$\displaystyle\prod_{i=k+1}^{n-2}(1-g(u_{i}))g({u_{n-1}})(1-p(u_{n-1},v))+$
$\displaystyle\prod_{i=k+1}^{n-1}(1-g(u_{i})).$

Finally, the probability of $v$ being degree-$1$ is

$\sum_{i=1}^{n-1}(p_{s}(v;u_{i})-p_{iso}(v)).$

######  Theorem D.2 (Time complexity of computing the expected number of
(non-)isolated nodes with parallel binding).

Given $p\colon\binom{V}{2}\to[0,1]$, $g\colon V\to[0,1]$, and
$R\in\mathbb{N}$, computing $\mathbb{E}_{f^{\text{PB}}_{p;g,R}}[\left|\\{v\in
G\colon d(v;G)\geq 1\\}\right|]$ takes
$O(\left|V\right|^{2}\log\left|V\right|)$ time.

###### Proof.

For computing the expected number of non-isolated nodes, for each node $v$, we
need to first sort the other nodes $u\in V\setminus\\{v\\}$ w.r.t. $p(u,v)$,
which takes $O(\left|V\right|\log\left|V\right|)$ times. After that, the
calculation only arithmetic operations, which takes $O(1)$ time since the
formulae are fixed. Hence, for each node $v$ it takes $O(\log\left|V\right|)$
times. In conclusion, for all the nodes in $V$, it takes
$O(\left|V\right|\log\left|V\right|)$ time in total. ∎

######  Remark D.3.

Considering node equivalence (see Section 5.4) can also be used to reduce the
time complexity of computing the number of (non-)isolated nodes.

Table 4: The number of non-isolated nodes and clustering metrics of graphs
generated by different realization methods. The number of non-isoalted nodes
$n_{ni}$ and the number of triangles ($\triangle$) are normalized. For each
dataset and each model, the best result is in bold and the second best is
underlined.

dataset Hams Fcbk Polb metric $n_{ni}$ $\triangle$ GCC ALCC $n_{ni}$
$\triangle$ GCC ALCC $n_{ni}$ $\triangle$ GCC ALCC model GroundT 1.000 1.000
0.229 0.540 1.000 1.000 0.519 0.606 1.000 1.000 0.226 0.320 ER EdgeInd 1.000
0.013 0.008 0.008 1.000 0.009 0.011 0.011 1.000 0.034 0.022 0.022 ParaBdg
0.812 0.988 0.385 0.640 0.555 1.002 0.574 0.815 0.801 1.025 0.412 0.659
ParaBdg-n 0.996 0.990 0.481 0.748 1.007 0.584 0.594 0.835 1.007 1.012 0.532
0.787 CL EdgeInd 0.964 0.299 0.067 0.058 0.988 0.124 0.064 0.063 0.944 0.792
0.183 0.173 ParaBdg 0.771 1.000 0.185 0.471 0.656 1.006 0.336 0.626 0.789
1.010 0.221 0.468 ParaBdg-n 0.959 0.257 0.027 0.069 0.969 1.098 0.125 0.151
0.935 0.794 0.135 0.219 SB EdgeInd 0.996 0.263 0.080 0.038 1.000 0.153 0.145
0.080 0.975 0.478 0.145 0.164 ParaBdg 0.719 0.993 0.241 0.521 0.608 1.035
0.529 0.557 0.899 1.010 0.183 0.251 ParaBdg-n 0.991 1.168 0.154 0.092 1.000
1.036 0.423 0.204 0.953 0.475 0.094 0.217 KR EdgeInd 0.996 0.185 0.039 0.060
1.014 0.052 0.035 0.042 1.598 0.101 0.040 0.075 ParaBdg 0.856 0.997 0.165
0.394 0.781 0.971 0.347 0.605 1.194 0.942 0.219 0.420 ParaBdg-n 0.996 0.301
0.028 0.099 1.000 0.953 0.254 0.262 0.987 0.976 0.268 0.368

dataset Spam Cepg Scht metric $n_{ni}$ $\triangle$ GCC ALCC $n_{ni}$
$\triangle$ GCC ALCC $n_{ni}$ $\triangle$ GCC ALCC  model GroundT 1.000 1.000
0.145 0.286 1.000 1.000 0.321 0.447 1.000 1.000 0.377 0.350  ER EdgeInd 1.000
0.005 0.003 0.003 1.000 0.037 0.033 0.033 1.000 0.027 0.029 0.029 [t] ParaBdg
0.783 0.993 0.401 0.663 0.688 0.968 0.508 0.750 0.617 0.991 0.559 0.794
ParaBdg-n 1.006 1.009 0.526 0.787 1.008 0.832 0.606 0.839 1.002 0.669 0.604
0.839 [b] CL EdgeInd 0.906 0.496 0.072 0.060 0.953 0.683 0.230 0.223 0.964
0.644 0.245 0.234 [t] ParaBdg 0.700 1.007 0.131 0.436 0.698 0.999 0.310 0.578
0.866 1.135 0.294 0.610 ParaBdg-n 0.908 0.445 0.033 0.071 0.927 0.725 0.198
0.334 0.932 0.639 0.200 0.347 [b] SB EdgeInd 0.982 0.528 0.094 0.036 0.994
0.662 0.258 0.200 0.992 0.644 0.272 0.128 [t] ParaBdg 0.685 0.994 0.158 0.356
0.911 1.047 0.333 0.363 0.792 0.975 0.340 0.437 ParaBdg-n 0.957 0.537 0.070
0.109 0.990 1.056 0.329 0.202 0.972 0.956 0.292 0.205 [b] KR EdgeInd 1.438
0.061 0.014 0.025 1.210 0.132 0.069 0.120 1.953 0.032 0.033 0.052 [t] ParaBdg
1.024 1.049 0.161 0.378 1.043 1.001 0.279 0.461 1.211 1.069 0.346 0.581
ParaBdg-n 0.995 0.981 0.161 0.385 0.996 1.118 0.296 0.478 0.997 1.030 0.370
0.640 [b]

###  D.2 Experimental results

Since we have the tractability results on the number of (non-)isolated nodes,
we can also fit and control the number of (non-)isolated nodes with our
binding schemes. Specifically, in our main experiments, the objective of
fitting is merely the number of triangles. Here, we further consider variants
with the fitting objective including both the number of triangles and the
number of (non-)isolated nodes, trying to preserve both numbers as the ground
truth.

In Table 4, for each dataset and each model, we compare the ground-truth
graph, the corresponding EIGM, and the following two variants of EPGMs:

  1. 1.

ParaBdg: parallel binding with the number of triangles as the objective

  2. 2.

ParaBdg-n: parallel binding with both the number of triangles and the number
of (non-)isolated nodes111111We only have tractability results with parallel
binding.

and report the following statistics of the generated graphs:

  1. 1.

$n_{ni}$: the number of non-isolated nodes

  2. 2.

$\triangle$: the number of triangles

  3. 3.

GCC: the global clustering coefficient

  4. 4.

ALCC: the average clustering coefficient

As in the main text, the statistics are averaged on $100$ random trials, i.e.,
$100$ generated graphs.

For ER, we relax both the number of total nodes and the uniform edge
probability, i.e., $n_{0}$ and $p_{0}$, for fitting. For the other three
models (CL, SB, and KR), we still use the edge probabilities obtained from the
original model and only add an additional term to the objective.

As shown in the results, in most cases, ParaBdg generates graphs with fewer
non-isolated nodes compared to the ground truth, and ParaBdg-n well fits the
number of non-isolated nodes while still improving clustering compared to
EIGMs. Notably, since the total number of nodes for KR can only be a power of
the seed-matrix size (i.e., a power of $2$ in our experiments), the
corresponding EIGM generates graphs with too many non-isolated nodes in many
cases, while ParaBdg-n generates graphs with a more similar number of non-
isolated nodes (i.e., closer to the ground truth). Moreover, it is also known
that even without binding, some models may suffer from the problem of isolated
nodes, e.g., CL (Brissette & Slota, 2021; Brissette et al., 2022) and KR
(Mahdian & Xu, 2007; Seshadhri et al., 2013).

Overall, the results validate that, our tractability results allow
practitioners to fit the number of non-isolated nodes (if that is one of their
main concerns) while improving other aspects, e.g., clustering.

##  Appendix E Additional discussions

###  E.1 General graphs

As mentioned in Section 2, we focus on undirected unweighted graphs without
self-loops following common settings for random graph models in the main text.
Below, we shall discuss different more general cases.

Directed edges and self-loops.whiteDirected edges and self-loops. In our
binding schemes (Algorithms 1, 2 and 3), if we consider directed edges and/or
self-loops, we can further consider them after sampling a group of nodes.
Regarding theoretical analysis, we can further consider subgraphs (motifs)
with directed edges and self-loops (Milo et al., 2002) and the high-level
ideas still apply.

Weighted edges.whiteWeighted edges. Our graph generation algorithms only
determine the (in)existence of edges and we may need additional schemes to
generate edge weights. For example, we can use algorithms that generate
realistic edge weights when given graph topology (Bu et al., 2023). Since in
our graph generation algorithms, nodes (and thus edges) can be sampled
multiple times, an alternative way to have edge weights is to allow each edge
to be inserted multiple times and use the times of repetition as edge weights.

###  E.2 Overlap-related triangle-density results

As mentioned in Section 3.1, Chanpuriya et al. (2023) have recently extended
their theoretical analysis to other categories of RGMs. In addition to EIGMs,
they further considered two other categories: node independent graph models
(NIGMs) and fully dependent graph models (FDGMs). Between the two, FDGMs means
any distribution of graphs, i.e., any RGM, is allowed.

They only discussed general overlap-related triangle-density upper bounds in
those categories of RGMs, without detailed tractability results for practical
graph generations. Specifically, their graph generation algorithm is based on
maximal clique enumeration (MCE). However, given a graph, MCE itself can take
exponential time (Eblen et al., 2012).

Also, what we focus on in this work, i.e., the category of binding-based
EPGMs, is a subset of EPGMs and are not “fully general” as FDGMs. On the other
hand, NIGMs are associated with node embeddings, where we have a node
embedding space (i.e., a distribution) $\mathcal{E}$ and a symmetric function
$e\colon\mathcal{E}\times\mathcal{E}\to[0,1]$, and each node $i$ has a node
embedding $\bm{x}_{i}$ sampled from $\mathcal{E}$ i.i.d., and each edge
$(i,j)$ exists with probability $e(\bm{x}_{i},\bm{x}_{j})$ independently. Our
binding-based EPGMs do not fall in this category either.

###  E.3 Subset sampling

As mentioned in Footnote 5 in Section 5.2, we use independent node sampling
(yet still with edge dependency) which is simple, tractable, and works well.
Specifically, independent node sampling allows us to easily compute the
marginal probability of each node binding sampled in each round, which is
involved in the derivation of our tractability results. Also, as shown in our
experiments, with binding schemes using independent node sampling, we still
achieve significant empirical improvement over EIGMs. In the most general
case, considering the sampling probabilities of all $2^{\left|V\right|}$
subsets would be intractable. Recently, a line of works has been proposed for
tractable and differentiable subset sampling (Xie & Ermon, 2019; Pervez et
al., 2023; Ahmed et al., 2023; Sutter et al., 2023), and exploring more
flexible node sampling schemes is an interesting future direction to be
explored.

###  E.4 Practical meaning of binding

As we mentioned in Section 5.2, local binding (and parallel binding as a
parallel version) binds node pairs locally among a group of nodes (instead of
some irrelevant node pairs). Such node pairs are structurally related, and are
expected to be meaningfully related in the corresponding real-world systems.
We shall discuss two specific real-world scenarios below.

Group interactions in social networks.whiteGroup interactions in social
networks. In typical social networks, nodes represent people, and edges
represent social communications/relations between people. Each group “bound
together” by our binding algorithms can represent a group interaction, e.g.,
an offline social event (meeting, conference, party) or an online social event
(group chat, Internet forum, online game). In such social events, people
gather together and the communications/relations between them likely co-occur.
Certainly, not necessarily all people in such events would communicate with
each other, e.g., some people are more familiar with each other. This is
exactly the point of considering binding with various edge probabilities
(instead of just inserting cliques).

Specifically, the random variable $s$ represents the overall “social power” of
an event, while individual edge probabilities $p(u,v)$’s represent some local
factors (e.g., their personal relationship) between each pair of people. A
line of research studies group interactions in social networks (Felmlee &
Faris, 2013; Levorato, 2014; Purushotham & Jay Kuo, 2015; Jang et al., 2016;
Li et al., 2020; Iacopini et al., 2022).

Gene functional associations in gene networks.whiteGene functional
associations in gene networks. In typical gene networks, nodes represent
genes, and edges represent gene functional associations, i.e., connections
between genes that contribute jointly to a biological function. Each group
“bound together” by our binding algorithms can represent a biological
function, since typically (1) a single biological function involves multiple
genes (Plomin, 1990; Anastassiou, 2007; Naoumkina et al., 2010) (represented
by a group of nodes bound together), and (2) the same biological function may
involve different genes in different cases (Gottesman & Hanson, 2005; Pritykin
et al., 2015; Storey et al., 2007) (represented by the probabilistic nature of
binding).

On parallel binding.whiteOn parallel binding. Specifically, as mentioned in
Section 5.3, compared to local binding where each pair can only participate in
a single group, parallel binding allows each pair to participate in multiple
groups (in different rounds). This is also true for real-world group
interactions, where different groups overlap and intersect with each other
(Lee et al., 2021; LaRock & Lambiotte, 2023).

##  Appendix F Additional details of the experiments

###  F.1 Experimental settings

Table 5: The basic statistics of the datasets. dataset | $|V|$ | $|E|$ | # triangles | GCC | ALCC
---|---|---|---|---|---
Hams | 2,000 | 16,097 | 157,953 | 0.229 | 0.540
Fcbk | 4,039 | 88,234 | 4,836,030 | 0.519 | 0.606
Polb | 1,222 | 16,717 | 303,129 | 0.226 | 0.320
Spam | 4,767 | 37,375 | 387,051 | 0.145 | 0.286
Cepg | 1,692 | 47,309 | 2,353,812 | 0.321 | 0.447
Scht | 2,077 | 63,023 | 4,192,980 | 0.377 | 0.350

Datasets.whiteDatasets. We use six real-world datasets from three different
domains: (1) social networks hamsterster (Hams) and facebook (Fcbk), (2) web
graphs polblogs (Polb) and spam (Spam), and (3) biological graphs CE-PG (Cepg)
and SC-HT (Scht).

The datasets are available online (Rossi & Ahmed, 2015; Leskovec & Krevl,
2014):

  * •

hamsterster (Hams) (Hamsterster, ) is available at
https://networkrepository.com/soc-hamsterster.php

  * •

facebook (Fcbk) (Leskovec & Mcauley, 2012) is available at
https://snap.stanford.edu/data/ego-Facebook.html

  * •

polblogs (Polb) (Adamic & Glance, 2005) is available at
https://networks.skewed.de/net/polblogs

  * •

spam (Spam) (Castillo et al., 2008) is available at
https://networkrepository.com/web-spam.php

  * •

CE-PG (Cepg) (Cho et al., 2014) is available at
https://networkrepository.com/bio-CE-PG.php

  * •

SC-HT (Scht) (Cho et al., 2014) is available at
https://networkrepository.com/bio-SC-HT.php

In Table 5, we show the basic statistics (e.g., the numbers of nodes and
edges) of the datasets.

We provide the formal definitions of some basic statistics below.

######  Definition F.1 (Clustering coefficients).

Given $G=(V,E)$, the number of wedges (i.e., open triangles) is
$n_{w}(G)=\sum_{v\in V}\binom{d(v)}{2}$. The global clustering coefficient
(GCC) of $G$ is defined as

$\text{GCC}(G)=\frac{3\triangle(G)}{n_{w}(G)},$

where $\triangle(G)$ is the number of triangles in $G$ and it is multiplied by
$3$ because each triangle corresponds to three wedges (consider three
different nodes as the center of the wedge). The average local clustering
coefficient (ALCC) of $G$ is defined as

$\text{ALCC}(G)=\sum_{v\colon d(v)\geq
2}\frac{\triangle(v;G)}{\binom{d(v)}{2}},$

where $\triangle(v;G)$ is the number of triangles involving $v$ in $G$.

Models.whiteModels. The Erdős-Rényi (ER) model outputs edge probabilities with
two parameters: $n_{0}$ and $p_{0}$, and the output is $p^{ER}_{n_{0},p_{0}}$
with $p^{ER}_{n_{0},p_{0}}(u,v)=p_{0},\forall u,v\in\binom{V}{2}$ with
$V=[n_{0}]$. Given a graph $G=(V=[n],E)$, the standard fitting of ER gives
$n_{0}=n$ and $p_{0}=\frac{\left|E\right|}{\binom{\left|V\right|}{2}}$.

The Chung-Lu (CL) model outputs edge probabilities with a sequence of expected
degrees $D=(d_{1},d_{2},\ldots,d_{n})$, and the output is $p^{CL}_{D}$ with
$p^{CL}_{D}(u,v)=\min(\frac{d_{u}d_{v}}{\sum_{i=1}^{n}d_{i}},1),\forall
u,v\in\binom{V}{2}$ with $V=[n]$. Given a graph $G=(V=[n],E)$, the standard
fitting of CL gives $d_{i}=d(i;G)$ for each node $i\in V$.

The stochastic block (SB) model outputs edge probabilities with (1) a
partition of nodes which can be represented by an assignment function
$f_{B}\colon[n_{0}]\to[c]$ with $n_{0}$ nodes and $c$ blocks and (2) the edge
probability between each pair of blocks (including between two identical
blocks), which can be represented by $p_{B}\colon[c]\times[c]\to[0,1]$, and
the output is $p^{SB}_{f_{B},p_{B}}$ with
$p^{SB}_{f_{B},p_{B}}(u,v)=p_{B}(f_{B}(u),f_{B}(v)),\forall u,v\in[n_{0}]$. In
our experiments, we use the Python library Graspologic (Chung et al., 2019)
which contains a fitting algorithm for SB. Specifically, it uses spectral
embedding (Von Luxburg, 2007; Sussman et al., 2012; Rohe et al., 2011) and a
Gaussian mixture model (Reynolds et al., 2009) to obtain node partitions.

The stochastic Kronecker (KR) model outputs edge probabilities with a seed
matrix $\theta\in[0,1]^{2\times 2}$ and a Kronecker power
$k_{KR}\in\mathbb{N}$, and the output is $p^{KR}_{\theta,k_{KR}}$ with
$p^{KR}_{\theta,k_{KR}}(u,v)=\theta^{(k_{KR})}_{uv},\forall
u,v\in\binom{V}{2}$ with $V=[2^{k_{KR}}]$, where
$\theta^{(k_{KR})}\in[0,1]^{2^{k_{KR}}\times 2^{k_{KR}}}$ is the $k_{KR}$-th
Kronecker power of $\theta$. In our experiments, we use kronfit (Leskovec et
al., 2010) proposed by the original authors of KR.

Fitting.whiteFitting. For fitting the parameters for our binding schemes, we
use the Adam optimizer (Kingma & Ba, 2015) with learning rate $\eta=0.001$ and
$n_{ep}=10,000$ epochs for training. In our experiments, we consistently use
$R=100,000$ rounds for both of our binding schemes. By default, the input edge
probabilities $p$ are provided and fixed as described above. By default, the
objective is the expected number of triangles. More specifically, it is

$(1-\frac{\mathbb{E}_{f^{\text{X}}_{p;g,R}}[\triangle(G)]}{\triangle(G_{input})})^{2}$

where

$\mathbb{E}_{f^{\text{X}}_{p;g,R}}[\triangle(G)]=\sum_{V^{\prime}\in\binom{V}{3}}\Pr_{f^{\text{X}}_{p;g,R}}[E(G[V^{\prime}])=\binom{V^{\prime}}{2}]$

is the expected number of triangles in a generated graph with
$X\in\\{\text{{LoclBdg}},\text{{ParaBdg}}\\}$ indicating the binding scheme,
and $\triangle(G_{input})$ is the ground-truth number of triangles in the
input graph.

Figure 3: The relations between node degrees and node-sampling probabilities.

We observe that our fitting algorithms assign different node-sampling
probabilities to different nodes, which implies that different nodes have
different levels of importance in binding. In Figure 3, for the CL model and
for each dataset, we show the relations between nodes’ degrees and their node-
sampling probabilities in LoclBdg and ParaBdg. For LoclBdg, we observe strong
positive correlations between node degrees and node-sampling probabilities.
For ParaBdg, similar trends are observed, but the patterns are quite
different. Also, we can observe that the node-sampling probabilities for
ParaBdg are overall lower than those for LoclBdg, as mentioned in Section 6.4.