marten

Uniform Edge Sampling from Complete k-Partite Graphs

This week I implemented my own version of graph2gauss, a deep learning model for node embeddings, in PyTorch. At its core is a loss function with the following structure.

i=0nj,ksp(i,j)<sp(i,k)f(i,j,k)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} \sum_{i = 0}^n \sum_{\scriptstyle j, k \atop\scriptstyle \sp(i, j) < \sp(i, k)} f(i, j, k)

Here the inner sum iterates over all possible pairs of nodes that have a different shortest-path distance to the node i\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} i. In the paper, the authors derive the Monte-Carlo approximation

i=0nEj1,,jKNi,1,,Ni,K1k,lKk<lNi,jkNi,jlf(i,jk,jl)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} \sum_{i = 0}^n \mathbb{E}_{j_1, \dots, j_K \sim N_{i, 1}, \dots, N_{i, K}} \sum_{\scriptstyle 1 \le k, l \le K \atop\scriptstyle k < l} \left| N_{i, j_k} \right| \cdot \left| N_{i, j_l} \right| \cdot f(i, j_k, j_l)

which leverages the runtime efficiency of independent, uniform sampling from node subsets but is a bit unwieldy as far as I am concerned. I would much rather write it as

i=0nNiEj,kf(i,j,k)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} \sum_{i = 0}^n \left|N_i\right| \cdot \mathbb{E}_{j, k}\, f(i, j, k)

where Ni={(j,k)sp(i,j)<sp(i,k)}\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} N_i = \{ (j, k) \mid \sp(i, j) < \sp(i, k) \} is the set of all admissible pairs and the expected value considers a uniform distribution over Ni\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} N_i. At a first glance sampling from Ni\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} N_i might be a problem because Ni\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} |N_i| grows quadratically in the number of reachable nodes from i\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} i. On second thought Ni\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} N_i can be seen as the edge set of a complete multi-partite graph of all neighbors of i\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} i where the nodes are partitioned on sp(i,j)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} \sp(i, j). So the set actually has a simple form and uniform sampling should be possible without enumerating the set.

Now let G=(E,V)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} G = (E, V) be a complete, undirected, k\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} k-partite graph with a set of nodes V\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} V that are partitioned into subsets V1,,Vk\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} V_1, \dots, V_k with cardinalities n1,,nk\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} n_1, \dots, n_k and edges

E={(u,v)uVa,vVb,ab}.\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} E = \{ (u, v) \mid u \in V_a, v \in V_b, a \ne b \}.

So every node is connected to every other except the ones from its own partition. At first I thought that uniformly sampling uVa\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} u \in V_a from V\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} V and then v\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} v from VVa\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} V \setminus V_a could work because the probabilities might cancel out just right but the following example shows that that is not the case.

Uniform node sampling leads to non-uniform edge probabilities in this complete 3-partitioned graph

We see that edges between high-degree nodes receive too little probability weight. Therefore, a strategy that samples edges uniformly needs to assign higher probability to nodes that participate in many edges. Let du\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} d_u be the out-degree of node u\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} u. In a graph such as G\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} G, du=nna\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} d_u = n - n_a where n=i=1kni\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} n = \sum_{i = 1}^k n_i and uVa\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} u \in V_a. Choose the first node proportional to its out-degree and the second one uniformly from all nodes that share an edge with the first one, i.e.

p(u)duandp(vu)=1du.\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(u) \propto d_u \quad \textrm{and} \quad p(v \mid u) = \frac{1}{d_u}.

This leads to a uniform distribution over ordered pairs of nodes (u,v)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} (u, v)

p((u,v))=p(u)p(vu)=duC1du=1C\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p((u, v)) = p(u) \cdot p(v \mid u) = \frac{d_u}{C} \cdot \frac{1}{d_u} = \frac{1}{C}

where C\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} C is the normalization constant of p(u)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(u). But G\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} G is undirected and (u,v)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} (u, v) is the same edge as (v,u)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} (v, u). Hence the probability of an edge e=(u,v)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} e = (u, v) is

p(e)=p((u,v))+p((v,u))=2C.\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(e) = p((u, v)) + p((v, u)) = \frac{2}{C}.

Since p(e)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(e) is independent of e\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} e, p(e)\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(e) must of course be the uniform distribution but just to double-check we will compute C\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} C. C=jVdj\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} C = \sum_{j \in V} d_j is the sum of all out-degrees which would just be the number of edges in a directed version of G\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} G. But G\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} G is undirected so C\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} C counts every edge twice. Therefore C=2E\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} C = 2|E| and p(e)=1E\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} p(e) = \frac{1}{|E|}.

The sampling method described in this post allowed me fine-grained control over the accuracy-performance trade-off in my implementation of graph2gauss. It is however generally applicable to any problem that can be modelled as sampling from a complete k\newcommand{\nth}[2]{#1^{\left(#2\right)}} \newcommand{\el}[2]{#1_{#2}} \newcommand{\col}[2]{#1_{:,#2}} \newcommand{\row}[2]{#1_{#2,:}} \renewcommand{\v}[1]{{\bm{#1}}} \newcommand{\m}[1]{{\bm{#1}}} \newcommand{\s}[1]{{\mathcal{#1}}} \newcommand{\set}[1]{{\left\{#1\right\}}} % Symbols \def\d{{\mathrm{d}}} \def\R{{\mathbb{R}}} \def\Rplus{{\pos{\R}}} \def\N{{\mathcal{N}}} % Operators \def\E{\operatorname*{\mathbb{E}}} \def\T{^{\intercal}} \def\inv{^{-1}} % Functions \def\sign{\operatorname{sign}} \def\Tr{\operatorname{Tr}} \def\ceil#1{\lceil #1 \rceil} \def\floor#1{\lfloor #1 \rfloor} \def\sp{\operatorname{sp}} k-partite graph.

Want to comment or get in touch? @martenlienen or email me