Uniform Edge Sampling from Complete k-Partite Graphs
Aug 29, 2019
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 = 0 n ∑ j , k sp ( 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}}}
\renewcommand{\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) i = 0 ∑ n sp ( i , j ) < sp ( i , k ) j , 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}}}
\renewcommand{\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 i . In the paper , the authors derive the
Monte-Carlo approximation
∑ i = 0 n E j 1 , … , j K ∼ N i , 1 , … , N i , K ∑ 1 ≤ k , l ≤ K k < l ∣ N i , j k ∣ ⋅ ∣ N i , j l ∣ ⋅ f ( i , j k , j l ) \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}}}
\renewcommand{\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) i = 0 ∑ n E j 1 , … , j K ∼ N i , 1 , … , N i , K k < l 1 ≤ k , l ≤ K ∑ ∣ N i , j k ∣ ⋅ ∣ N i , j l ∣ ⋅ 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 = 0 n ∣ N i ∣ ⋅ E j , 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}}}
\renewcommand{\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) i = 0 ∑ n ∣ N i ∣ ⋅ E j , k f ( i , j , k ) where N i = { ( 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}}}
\renewcommand{\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) \} N i = {( j , k ) ∣ sp ( i , j ) < sp ( i , k )} is the set of all admissible
pairs and the expected value considers a uniform distribution over N 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}}}
\renewcommand{\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 N i . At a first
glance sampling from N 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}}}
\renewcommand{\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 N i might be a problem because ∣ N 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}}}
\renewcommand{\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| ∣ 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}}}
\renewcommand{\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 i . On second thought
N 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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) 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}}}
\renewcommand{\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) 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 V that are partitioned into subsets V 1 , … , V 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}}}
\renewcommand{\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 V 1 , … , V k with
cardinalities n 1 , … , n 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}}}
\renewcommand{\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 n 1 , … , n k and edges
E = { ( u , v ) ∣ u ∈ V a , v ∈ V b , a ≠ b } . \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}}}
\renewcommand{\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 \}. E = {( u , v ) ∣ u ∈ V a , v ∈ V b , a = b } . So every node is connected to every other except the ones from its own partition. At first
I thought that uniformly sampling u ∈ V a \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}}}
\renewcommand{\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 u ∈ 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 v from
V ∖ V a \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}}}
\renewcommand{\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 V ∖ V a could work because the probabilities might cancel out just right
but the following example shows that that is not the case.
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 d 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 G , d u = n − n a \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}}}
\renewcommand{\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 d u = n − n a where n = ∑ i = 1 k n 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}}}
\renewcommand{\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 n = ∑ i = 1 k n i
and u ∈ V a \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}}}
\renewcommand{\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 u ∈ 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 ) ∝ d u and p ( v ∣ u ) = 1 d 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}}}
\renewcommand{\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}. p ( u ) ∝ d u and p ( v ∣ u ) = d u 1 . 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}}}
\renewcommand{\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) ( u , v )
p ( ( u , v ) ) = p ( u ) ⋅ p ( v ∣ u ) = d u C ⋅ 1 d u = 1 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}}}
\renewcommand{\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} p (( u , v )) = p ( u ) ⋅ p ( v ∣ u ) = C d u ⋅ d u 1 = C 1 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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) 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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) ( 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}}}
\renewcommand{\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) ( 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}}}
\renewcommand{\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) e = ( u , v ) is
p ( e ) = p ( ( u , v ) ) + p ( ( v , u ) ) = 2 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}}}
\renewcommand{\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}. p ( e ) = p (( u , v )) + p (( v , u )) = C 2 . 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}}}
\renewcommand{\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 ( 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 ( 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}}}
\renewcommand{\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 . C = ∑ j ∈ V d 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}}}
\renewcommand{\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 C = ∑ j ∈ 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 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}}}
\renewcommand{\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 counts every edge twice.
Therefore C = 2 ∣ 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}}}
\renewcommand{\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| C = 2∣ E ∣ and p ( e ) = 1 ∣ 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}}}
\renewcommand{\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|} p ( e ) = ∣ E ∣ 1 .
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}}}
\renewcommand{\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 k -partite graph.