# Source code for dgl.sampling.negative

"""Negative sampling APIs"""

from numpy.polynomial import polynomial
from .._ffi.function import _init_api
from .. import backend as F
from .. import utils
from ..heterograph import DGLHeteroGraph

__all__ = [
'global_uniform_negative_sampling']

def _calc_redundancy(k_hat, num_edges, num_pairs, r=3): # pylint: disable=invalid-name
# pylint: disable=invalid-name
# Calculates the number of samples required based on a lower-bound
# of the expected number of negative samples, based on N draws from
# a binomial distribution.  Solves the following equation for N:
#
# k_hat = N*p_k - r * np.sqrt(N*p_k*(1-p_k))
#
# where p_k is the probability that a node pairing is a negative edge
# and r is the number of standard deviations to construct the lower bound
#
# Credits to @zjost
p_m = num_edges / num_pairs
p_k = 1 - p_m

a = p_k ** 2
b = -p_k * (2 * k_hat + r ** 2 * p_m)
c = k_hat ** 2

poly = polynomial.Polynomial([c, b, a])
N = poly.roots()[-1]
redundancy = N / k_hat - 1.
return redundancy

[docs]def global_uniform_negative_sampling(
g, num_samples, exclude_self_loops=True, replace=False, etype=None,
redundancy=None):
"""Performs negative sampling, which generate source-destination pairs such that
edges with the given type do not exist.

Specifically, this function takes in an edge type and a number of samples.  It
returns two tensors src and dst, the former in the range of [0, num_src)
and the latter in the range of [0, num_dst), where num_src and num_dst
represents the number of nodes with the source and destination node type respectively.
It guarantees that no edge will exist between the corresponding pairs of src
with the source node type and dst with the destination node type.

.. note::

This negative sampler will try to generate as many negative samples as possible, but
it may rarely return less than :attr:num_samples negative samples.
This is more likely to happen when a graph is so small or dense that not many
unique negative samples exist.

Parameters
----------
g : DGLGraph
The graph.
num_samples : int
The number of desired negative samples to generate.
exclude_self_loops : bool, optional
Whether to exclude self-loops from the negative samples.  Only impacts the
edge types whose source and destination node types are the same.

Default: True.
replace : bool, optional
Whether to sample with replacement.  Setting it to True will make things
faster.  (Default: False)
etype : str or tuple of str, optional
The edge type.  Can be omitted if the graph only has one edge type.
redundancy : float, optional
Indicates how much more negative samples to actually generate during rejection sampling
before finding the unique pairs.

Increasing it will increase the likelihood of getting :attr:num_samples negative
samples, but will also take more time and memory.

(Default: automatically determined by the density of graph)

Returns
-------
tuple[Tensor, Tensor]
The source and destination pairs.

Examples
--------
>>> g = dgl.graph(([0, 1, 2], [1, 2, 3]))
>>> dgl.sampling.global_uniform_negative_sampling(g, 3)
(tensor([0, 1, 3]), tensor([2, 0, 2]))
"""
if etype is None:
etype = g.etypes[0]
utype, _, vtype = g.to_canonical_etype(etype)
exclude_self_loops = exclude_self_loops and (utype == vtype)

redundancy = _calc_redundancy(
num_samples, g.num_edges(etype), g.num_nodes(utype) * g.num_nodes(vtype))

etype_id = g.get_etype_id(etype)
src, dst = _CAPI_DGLGlobalUniformNegativeSampling(
g._graph, etype_id, num_samples, 3, exclude_self_loops, replace, redundancy)
return F.from_dgl_nd(src), F.from_dgl_nd(dst)
DGLHeteroGraph.global_uniform_negative_sampling = utils.alias_func(
global_uniform_negative_sampling)

_init_api('dgl.sampling.negative', __name__)