[Discussion] Replace the randomnet horrorscape

[dglmoore]

This is a discussion question. Please comment with any thoughts you may have.

Using the randomnet submodule to produce random networks is kind of a nightmare. In an ideal world, what would the perfect API look like to you? Give an example of how you'd like to be able to perform the the following (vague) tasks:

1. Generate a random boolean network (RBN) of a particular size.
2. Generate an RBN with a particular mean degree.
3. Generate a random network with the same size and mean degree as another network.
4. Generate a random network with the same size, mean in-degree and number of canalyzing edges as another network.

Note: we aren't looking for implementations, just suggested API. For example, one possible response to 1 is

>>> net = WTNetwork.random(size=5)

or maybe

>>> from neet.boolean.conv import logic_to_wt
>>> logic_net = randomnet.rand(size=5)
>>> net = logic_to_wt(logic_net)

[hbsmith]

net = WTNetwork.random(size=5) # produces a random connected net with 5 nodes
net = WTNetwork.random(net=s_pombe_net) # produces a random network with the same size, mean in-degree and number of canalyzing edges as s_pombe

or maybe this would be better?

net = s_pombe_net.random(fix_mean_deg=False,fix_in_degree=False,fix_canalizing=True)

Or some combination? Just spitballing here.

[dglmoore]

@hbsmith That's exactly what I'm looking for. Thanks! Keep it coming folks!

[bcdaniels]

In my dream world, this would conform to our language about "constrained ensembles". Let's see if I can invent this in a way that would be implementable...

ens = ensemble( size=5, mean_deg=s_pombe_net.mean_deg() )
net = ens.sample()
netList = ens.sample(100) # a list of 100 networks from the ensemble

That is, ens is an ensemble object that represents the set of constraints, and we sample from that ensemble to get actual networks.

We would ideally want to be able to further constrain existing ensembles, but I imagine this is where the implementation gets hairy. E.g. this would produce the same ensemble as above

ens = ensemble( size=5 )  # some kind of `maximum entropy` ensemble
ens.constrain_mean_deg( s_pombe_net.mean_deg() )

Where this would really get cool (and tricky) is if we managed to make the following work (I'm looking at @siyuzhou):

ens = ensemble( size=5 )
ens.constrain_sensitivity(1.)

or maybe constrain to ranges if that's easier (?)

ens.constrain_sensitivity(min=0.9,max=1.1)

and of course all combinations (some of which would presumably produce errors or empty ensembles):

ens.constrain_structure(s_pombe_net.neighbors)
ens.constrain_bias(p=0.25)
ens.constrain_max_in_degree(3)
ens.constrain_canalizing_nodes([True,False,True,True,False])
ens.constrain_basin_entropy(4)
ens.constrain_num_attractors(16)

I suppose we could implement just a few constraints that we know how to do easily first, and we could have room to grow in case we managed to figure out the trickier ones.

We could also implement @hbsmith's version that starts with a network (which I like) for convenience; e.g. within a network object

def random(fix_mean_deg,fix_in_degree,fix_canalizing):
    ens = ensemble( size=self.size )
    if fix_mean_deg:
        ens.constrain_mean_deg(self.mean_deg())
    ...
    return ens.sample()

[dglmoore]

@bcdaniels This is great. I was thinking along the same lines, but had a different implementation of "composible constraints" in mind. I think you're API would be more intuitive for most folks.

Here are some of my thoughts:

Network Type

A sticking point of what you've proposed is the network type. Would ensemble only be able to generate LogicNetworks? Would we have to implement a different ensemble class go got along with each network type? This is inevitable to some extent, but hopefully we can come up with a design that minimizes the amount of effort necessary to create random network generators for new types. Honestly, this is probably not a major concern as I doubt most people will need to implement a custom network type. Still, something to keep in mind.

Implementing Constraints

We also have to think about how to compose constraints. The naive way to do that is to have a constraints list in ensemble and a generic, (un)biased network generator. When a network is generated we iterate through the constraints and discard the network if it fails to meet some constraint.

Advantages

One advantage to that is you could have something like

ens.constrain_custom(my_constraint)

which would apply any function with type my_constraint : Network → Bool. In other words, users could create their own constraints with essentially no effort.

Disadvantages

The biggest disadvantage is the cost; you'll end up generating a lot of networks that fail with no guarantee of success. What if two constraints are incompatible?

[hbsmith]

@dglmoore I was also thinking about the cost aspect when reading over @bcdaniels suggestions (which I think are all good ideas). Do we just create a non-constrained ensemble of random networks and then filter them? (returning an error if constraints end up being incompatible, and a warning if there are no random networks that fit them?) Do we use a "smart" way to create random ensembles with specific constraints? Do we reuse those if the constraints get relaxed? (possibly biasing the random ensemble) Just some thoughts that came to mind.

[dglmoore]

I took a look at the random network generators in randomnet, and it looks like we are already using a "try-try again" approach: https://github.com/ELIFE-ASU/Neet/blob/master/neet/boolean/randomnet.py#L243. They are all using very similar algorithms, share a lot of redundant code, and typically wait until the very end of each pass over the network to test the constraints. They also aren't horrendously inefficient, so I'm thinking there might be a slightly more general way to implement them if we decide not to do something more radical, i.e. interesting 😉.

@siyuzhou's approaches using genetic algorithms or neural networks to generate networks is great, but I have two concerns:

1. I don't imagine it is terribly efficient.
2. Can we be sure that the distribution over networks satisfying the desired constraints is unbiased? The entire point is to perfectly bias it toward those networks, but you don't want a bias between two networks which satisfy the constraints.

[dglmoore]

@hbsmith

Do we just create a non-constrained ensemble of random networks and then filter them?

This is the simplest approach. What we are currently doing is building certain types of networks, e.g networks with a given mean degree, using specialized algorithms and then testing against the additional constraints as we build a given network. For example, once we've created a given logic function for a node that was canalying in the original network, we test it to make sure it is canalying and try again if it isn't. This is a bit more efficient than constructing the entire network.

...(returning an error if constraints end up being incompatible...)

I'm not sure how you could test the collection of constraints for satisfiability. I'm fairly sure that's either undecidable or very hard. There might be a way for a small set of pre-defined constraints, but in general...? Either way, the best I think we could do is just throw an error if we try a bunch of times and fail.

Do we use a "smart" way to create random ensembles with specific constraints?

I think that's the best way to go if we decide try a "composable constraints" approach. We might consider the user's requested set of constraints to choose an optimized algorithm, and fall back to "try-try again" in other cases (or some kind of hybrid).

Do we reuse those if the constraints get relaxed?

That's an interesting idea. Relaxing constraints is hard because now you are potentially admitting new networks. However, strengthening constraints might be possible.

[dglmoore]

One more thought: there are different kinds of constraints we could impose. To name a few:

1. Node-Local/Edge-Local constraints (This node is canalyzing.)
2. Global constraints (The mean degree is 3.)
3. Landscape constriants, (The basin entropy is 2.31bits.)

The first one could be applied while a network is being built. The second could either be used to create a more efficient generation algorithm, or be checked after an unbiased network is built. The third can only be applied after the entire network is constructed.

Any thoughts?