Aeon 1.0

[daemontus]

This PR migrates balm to the version 1.0 of biodivine_aeon. As part of the migration, several major changes are introduced:

• The dependency on PyEDA is completely removed, because we can now use symbolic representations in AEON. This mainly affects the Petri net translation and motif avoidant detection, where PyEDA BDDs were used extensively. To some extent, this also affects percolation, but not as dramatically.

  • In a few places, this change is a bit annoying because it means that, aside from the BDD, you also have to provide a proper "context" object through which the BDD is interpreted.
  • To help with this, each SuccessionDiagram now also maintains an AsynchronousGraph of the underlying BooleanNetwork. To avoid any unnecessary overhead, the SuccessionDiagram first removes any static constraints imposed by the influence graph, so this should really be only building the symbolic context and the function BDDs and nothing else.
  • With that said... For the Petri net translation, Aeon computes a ~10-20% smaller Petri net for the real world models in roughly the same time... or the same Petri net but 10x faster for very large N-K models (see petri_net_translation table below).
  • The size of the Petri net very positively impacts some of the real-world models, but this is relatively rare (see e.g. 146 and 159 in the bfs_full_expansion table). For other models, the impact is negligible, mostly because we are not bottlenecked by the solver very much (or the PN did not improve measurably).
  • For motif avoidant detection, this also helped quite a bit in cases where attractor detection was a bottleneck. For BBM models, we are up to 10x faster on many models that were previously "slow".

• For percolation, I observed that it's not particularly critical for performance on the real-world models, but it can be a bottleneck on the large random models. Here, the new implementation should be up to 2x faster than the old one, but we seem to be hitting other bottlenecks for those models as well, so the performance impact is not as drastic.

  • I separated the basic and strict percolations into separate methods to make them easier to optimize. For now, I am focusing on the basic percolation. Strict percolation does not seem to be used in performance critical code at the moment, so it should be fine.
  • After accounting for the new translation and percolation changes, we are 3% (BBM) and 15% (random) faster than the old implementation. But this weights every model equally, the difference tends to be much larger on the non-trivial models (see bfs_full_expansion table).

• I also did some non-trivial updates to the SCC expansion, mainly using new features in BN manipulation to avoid the bnet translations. In the end, the changes should not impact performance much, but the expansion is still faster compared to the previous result, probably for the same reasons full expansion is faster (See attractors_scc_expansion table)

Other miscellaneous changes:

• The type stubs are no longer necessary, since PyEDA is not used, and AEON now distributes its own type annotations.
• The fact that we no longer use PyEDA means we don't need to increase the recursion limit anymore.
• Added a Python script that can sample networks with random input valuations. Some of the AEON bindings to do this in Python were missing previously.
• Added a simple benchmark script to test Petri net translation in isolation to rule out any bottlenecks in that area and to be able to compare the PN sizes across implementations.
• Now that everything is generally faster, we can remove some of the limits we imposed on attractor detection in the original tests.
• BooleanNetwork now inherits from a RegulatoryGraph, hence type signatures that accepted both can be simplified to just RegulatoryGraph (for the most part).
• The caching of expressions/symbolic values is removed because most of it is now handled by the SymbolicContext and AsynchronousGraph instances that we pass around.

petri_net_translation.xlsx bfs_full_expansion.xlsx attractors_scc_expansion.xlsx

[github-actions[bot]]

Coverage Report

File	Stmts	Miss	Cover	Missing
balm
SuccessionDiagram.py	211	42	80%	6, 126–133, 139–146, 159, 166, 173, 181, 184, 190–221, 308, 448–450, 456, 582
control.py	123	14	89%	48, 57, 61, 67, 81, 90–106, 329, 332, 345
interaction_graph_utils.py	54	5	91%	6–8, 47, 165–166
motif_avoidant.py	152	2	99%	24, 120
petri_net_translation.py	117	10	91%	17–19, 49, 85, 133–134, 158–159, 168, 272
space_utils.py	129	4	97%	24–26, 251, 277
symbolic_utils.py	26	3	88%	10–12, 44
trappist_core.py	187	26	86%	10–12, 40, 42, 82, 128, 193, 195, 197, 232–234, 254–260, 318, 320, 350, 390, 392, 423, 452
balm/_sd_algorithms
compute_attractor_seeds.py	30	1	97%	8
expand_attractor_seeds.py	51	5	90%	6, 42, 95–100
expand_bfs.py	28	1	96%	6
expand_dfs.py	30	1	97%	6
expand_minimal_spaces.py	37	2	95%	6, 31
expand_source_SCCs.py	163	5	97%	20, 90, 100, 142, 285
expand_to_target.py	31	3	90%	6, 38, 43
TOTAL	1398	124	91%

Tests	Skipped	Failures	Errors	Time
363	0 :zzz:	0 :x:	0 :fire:	48.723s :stopwatch:

[jcrozum]

This is great! While you're overhauling the SCC expansion, watch out for the import cycle. Maybe with the new approach, there will be a nicer way to resolve it. Basically, the SuccessionDiagram.py needs to import the methods in expand_source_SCC.py file to get the expansion method for the SuccessionDiagram class, but those methods construct a new SuccessionDiagram. This is causing problems for the automatic documentation. My solution on that branch was to import the SuccessionDiagram class from within the expansion methods at runtime, but hopefully there is a better way. On slightly a related note, we should rename the files to conform to PEP8 standars (all files should be written_like_this.py).

[jcrozum]

I just pushed some formatting changes to this PR. We should probably add black to our CI pipeline. I also added a # type: ignore to a type error that I got locally but which our CI seemed to miss for some reason.

[daemontus]

Ok, I don't know what happened exactly, maybe I screwed up something during testing (I was experimenting with the percolation when I did the preliminary tests for SCC expansion), but the latest commit is actually faster on SCC expansion than the original version, roughly in line with the improvements we got for the "full" expansion. So I guess that issue is closed.

Furthermore, I tested control: Anything that was able to finish under 10 minutes on the new version was slower on the older version. So I think we should be fine in terms of performance.

I'll be merging this, and we can solve the rest as we go.