  Network Embeddings (NEs) map the nodes of a given network into
$d$-dimensional Euclidean space $\mathbb{R}^d$. Ideally, this mapping is such
that `similar' nodes are mapped onto nearby points, such that the NE can be
used for purposes such as link prediction (if `similar' means being `more
likely to be connected') or classification (if `similar' means `being more
likely to have the same label'). In recent years various methods for NE have
been introduced, all following a similar strategy: defining a notion of
similarity between nodes (typically some distance measure within the network),
a distance measure in the embedding space, and a loss function that penalizes
large distances for similar nodes and small distances for dissimilar nodes.
  A difficulty faced by existing methods is that certain networks are
fundamentally hard to embed due to their structural properties: (approximate)
multipartiteness, certain degree distributions, assortativity, etc. To overcome
this, we introduce a conceptual innovation to the NE literature and propose to
create \emph{Conditional Network Embeddings} (CNEs); embeddings that maximally
add information with respect to given structural properties (e.g. node degrees,
block densities, etc.). We use a simple Bayesian approach to achieve this, and
propose a block stochastic gradient descent algorithm for fitting it
efficiently. We demonstrate that CNEs are superior for link prediction and
multi-label classification when compared to state-of-the-art methods, and this
without adding significant mathematical or computational complexity. Finally,
we illustrate the potential of CNE for network visualization.
