Skip to main content
`Ctrl`+`K`

# NXEP 4 — Default random interface

Author:

  Ross Barnowski (rossbar@berkeley.edu)

Status:

  Draft

Type:

  Standards Track

Created:

  2022-02-24

## Abstract

Pseudo-random numbers play an important role in many graph and network analysis algorithms in NetworkX. NetworkX provides a standard interface to random number generators that includes support for `numpy.random` and the Python built-in `random` module. `numpy.random` is used extensively within NetworkX and in several cases is the preferred package for random number generation. NumPy introduced a new interface in the `numpy.random` package in NumPy version 1.17. According to NEP19, the new interface based on `numpy.random.Generator` is recommended over the legacy `numpy.random.RandomState` as the former has better statistical properties, more features, and improved performance. This NXEP proposes a strategy for adopting `numpy.random.Generator` as the default interface for random number generation within NetworkX.

## Motivation and Scope

The primary motivation for adopting `numpy.random.Generator` as the default random number generation engine in NetworkX is to allow users to benefit from the improvements in `numpy.random.Generator`, including: - Advances in statistical quality of modern pRNG’s - Improved performance - Additional features

The `numpy.random.Generator` API is very similar to the `numpy.random.RandomState` API, so users can benefit from these improvements without any additional changes [1] to their existing NetworkX code.

In principle this change would impact NetworkX users that use any of the functions decorated by `np_random_state` or `py_random_state` (when the `random_state` argument involves `numpy`). See the next section for details.

[1]

See note about the compatibility layer in the Implementation section

## Usage and Impact

In NetworkX, random number generators are typically created via a decorator:

    from networkx.utils import np_random_state

    @np_random_state("seed")  # Or could be the arg position, i.e. 0
    def foo(seed=None):
        return seed

The decorator is responsible for mapping various different inputs into an instance of a random number generator within the function. Currently, the random number generator instance that is returned is a `numpy.random.RandomState` object:

    >>> type(foo(None))
    numpy.random.mtrand.RandomState
    >>> type(foo(12345))
    numpy.random.mtrand.RandomState

The only way to get a `numpy.random.Generator` instance from the random state decorators is to pass the instance in directly:

    >>> import numpy as np
    >>> rng = np.random.default_rng()
    >>> type(foo(rng))
    numpy.random._generator.Generator

This NXEP proposes to change the behavior so that when e.g. and integer or `None` is given for the `seed` parameter, a `numpy.random.Generator` instance is returned instead, i.e.:

    >>> type(foo(None))
    numpy.random._generator.Generator
    >>> type(foo(12345))
    numpy.random._generator.Generator

`numpy.random.RandomState` instances can still be used as `seed`, but they must be explicitly passed in:

    >>> rs = np.random.RandomState(12345)
    >>> type(foo(rs))
    numpy.random.mtrand.RandomState

## Backward compatibility

There are three main concerns:

1. The `Generator` interface is not stream-compatible with `RandomState`, thus the results of the `Generator` methods will not be exactly the same as the corresponding `RandomState` methods.

2. There are a few slight differences in method names and availability between the `RandomState` and `Generator` APIs.

3. There is no global `Generator` instance internal to `numpy.random` as is the case for `numpy.random.RandomState`.

The `numpy.random.Generator` interface breaks the stream-compatibility guarantee that `numpy.random.RandomState` upheld of exact reproducibility of values. Switching the default random number generator from `RandomState` to `Generator` would mean functions decorated with `np_random_state` would produce different results when a value other than an instantiated rng is used as the seed. For example, let’s take the following function:

    @np_random_state("seed")
    def bar(num, seed=None):
        """Return an array of `num` uniform random numbers."""
        return seed.random(num)

With the current implementation of `np_random_state`, a user can pass in an integer value to `seed` which will be used to seed a new `RandomState` instance. Using the same seed value guarantees the output is always exactly reproducible:

    >>> bar(10, seed=12345)
    array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
           0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])
    >>> bar(10, seed=12345)
    array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
           0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])

However, after changing the default rng returned by `np_random_state` to a `Generator` instance, the values produced by the decorated `bar` function for integer seeds would no longer be identical:

    >>> bar(10, seed=12345)
    array([0.22733602, 0.31675834, 0.79736546, 0.67625467, 0.39110955,
           0.33281393, 0.59830875, 0.18673419, 0.67275604, 0.94180287])

In order to recover exact reproducibility of the original results, a seeded `RandomState` instance would need to be explicitly created and passed in via `seed`:

    >>> import numpy as np
    >>> rng = np.random.RandomState(12345)
    >>> bar(10, seed=rng)
    array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
           0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])

Because the streams would no longer be compatible, it is proposed in this NXEP that switching the default random number generator only be considered for a major release, e.g. the transition from NetworkX 2.X to NetworkX 3.0.

The second point is only a concern for users who are using `create_random_state` and the corresponding decorator `np_random_state` in their own libraries. For example, the `numpy.random.RandomState.randint` method has been replaced by `numpy.random.Generator.integers`. Thus any code that uses `create_random_state` or `create_py_random_state` and relies on the `randint` method of the returned rng would result in an `AttributeError`. This can be addressed with a compatibility class similar to the `networkx.utils.misc.PythonRandomInterface` class, which provides a compatibility layer between `random` and `numpy.random.RandomState`.

`create_random_state` currently returns the global `numpy.random.mtrand._rand` `RandomState` instance when the input is `None` or the `numpy.random` module. By switching to `numpy.random.Generator`, this will no longer be possible as there is no global, internal `Generator` instance in the `numpy.random` module. This should have no effect on users, as `seed=None` currently does not guarantee reproducible results.

## Detailed description

This NXEP proposes to change the default random number generator produced by the `create_random_state` function (and the related decorator `np_random_state`) from a `numpy.random.RandomState` instance to a `numpy.random.Generator` instance when the input to the function is either an integer or `None`.

## Related Work

Scikit-learn has a similar pattern for imposing determinism on functions that depend on randomness. For example, many functions in `scikit-learn` have a `random_state` argument that functions similarly to how `seed` behaves in many NetworkX function signatures. One difference between `scikit-learn` and `networkx` is that scikit-learn only supports `RandomState` via the `random_state` keyword argument, whereas NetworkX implicitly supports both the built-in `random` module, as well as both the numpy `RandomState` and `Generator` instances (depending on the type of `seed`). This is reflected in the name of the keyword argument as `random_state` (used by scikit-learn) is les ambiguous than `seed` (used by NetworkX).

There are multiple relevant discussions in the scikit-learn community about potential approaches to supporting the new NumPy random interface:

- scikit-learn/scikit-learn#16988 covers strategies and concerns related to enabling users to use the `Generator`-based random number generators.

- scikit-learn/scikit-learn#14042 is a higher-level discussion that includes additional information about the design considerations and constraints related to scikit-learn’s `random_state`.

- There is also a related SLEP.

## Implementation

The implementation itself is quite simple. The logic that determines how inputs are mapped to random number generators is encapsulated in the `create_random_state` function (and the related `create_py_random_state`). Currently (i.e. NetworkX <= 2.X), this function maps inputs like `None`, `numpy.random`, and integers to `RandomState` instances:

    def create_random_state(random_state=None):
        if random_state is None or random_state is np.random:
            return np.random.mtrand._rand
        if isinstance(random_state, np.random.RandomState):
            return random_state
        if isinstance(random_state, int):
            return np.random.RandomState(random_state)
        if isinstance(random_state, np.random.Generator):
            return random_state
        msg = (
            f"{random_state} cannot be used to create a numpy.random.RandomState or\n"
            "numpy.random.Generator instance"
        )
        raise ValueError(msg)

This NXEP proposes to modify the function to produce `Generator` instances for these inputs. An example implementation might look something like:

    def create_random_state(random_state=None):
        if random_state is None or random_state is np.random:
            return np.random.default_rng()
        if isinstance(random_state, (np.random.RandomState, np.random.Generator)):
            return random_state
        if isinstance(random_state, int):
            return np.random.default_rng(random_state)
        msg = (
            f"{random_state} cannot be used to create a numpy.random.RandomState or\n"
            "numpy.random.Generator instance"
        )
        raise ValueError(msg)

The above captures the essential change in logic, though implementation details may differ. Most of the work related implementing this change will be associated with improved/reorganized tests; including adding tests rng-stream reproducibility.

## Alternatives

The status quo, i.e. using `RandomState` by default, is a completely acceptable alternative. `RandomState` is not deprecated, and is expected to maintain its stream-compatibility guarantee in perpetuity.

Another possible alternative would be to provide a package-level toggle that users could use to switch the behavior the `seed` kwarg for all functions decorated by `np_random_state` or `py_random_state`. To illustrate (ignoring implementation details):

    >>> import networkx as nx
    >>> from networkx.utils.misc import create_random_state

    # NetworkX 2.X behavior: RandomState by default

    >>> type(create_random_state(12345))
    numpy.random.mtrand.RandomState

    # Change random backend by setting pkg attr

    >>> nx._random_backend = "Generator"

    >>> type(create_random_state(12345))
    numpy.random._generator.Generator

## Discussion

This NXEP has been discussed at several community meetings, see e.g. these meeting notes.

The main concern that has surfaced during these discussions is that the NumPy `Generator` interface does not make the same strict stream-compatibility guarantees as the older `RandomState`. Therefore, if this NXEP were implemented as proposed, code that relies on seeded random numbers could in principle return different results with some future NumPy version due to changes in the default `BitGenerator` or `Generator` methods.

Many NetworkX functions are quite sensitive to the random seed. For example, changing the seed for the default `spring_layout` function can yield a vastly different (but equally valid) layout for a network. Stream-compatibility is important for reproducibility in these contexts.

Thus we have concluded through various discussions not to implement the changes proposed in this NXEP. `RandomState` will remain the default random number generator for the `random_state` decorator in an effort to support strict backward compatibility for all NetworkX user code that relies on `random_state`. The `Generator` interface is supported in the `random_state` decorator, and users are encouraged to use `Generator` instances in new code where stream-compatibility is not a priority.