Support two-stage parameter grid search

[agitter]

A common pathway reconstruction workflow is to start with an initial grid of parameter combinations, inspect the output pathways by applying heuristics, and filter the output pathways that do not fall within the desirable heuristic ranges. An optional final step could be to refine the initial grid of parameter combinations to remove those that produced undesirable outputs and provide more granular step sizes around parameter values that produced desirable outputs.

SPRAS could directly support this with a few new features:

• Expanding the graph properties (heuristics) computed in the summary table. This could include graph statistics like clustering coefficient, etc.
• Allow a user to specify ranges of graph properties (heuristics) they find tolerable in the config file
• Filter output pathways based on tolerable ranges
• Rewrite a new config file with the parameter combinations that produced those tolerable ranges so the user can use it as a template for a second run

An example of filtering from https://journals.plos.org/plospathogens/article?id=10.1371/journal.ppat.1011492:

After generating subnetworks for each parameter combination, we discarded: any empty networks; networks that did not have a connected component with at least 25 vertices; networks in which one vertex was connected to 10% or more of the total vertices (which indicates a dominant hub node); and networks that contained a chain of more than 8 vertices without any nonzero prizes. An additional filter for networks whose vertices were not at least half prize nodes did not affect any of the networks.

[tristan-f-r]

I'm curious about the initial grid parameter combination: this seems like something good to start with for supporting parameter grid searching. Something like adding an attribute to algorithm parameters of the min/max ranges recommended for pathway reconstruction (or attached functions which take in an interactome and provide an encompassing range of the recommended low/high values for these parameters.)

[ntalluri]

I'm curious about the initial grid parameter combination: this seems like something good to start with for supporting parameter grid searching. Something like adding an attribute to algorithm parameters of the min/max ranges recommended for pathway reconstruction (or attached functions which take in an interactome and provide an encompassing range of the recommended low/high values for these parameters.)

Most likely will be adding a way to filter by using heuristics that we use for parameter tuning analysis we set up. The pink picture goes through the process for parameter tuning and the white picture shows the heuristics to use for parameter tuning.

The grids will need to be tuned in both phases and we will create new configs based on the hueristics that will be updated or recreated based on the tuning.

[tristan-f-r]

I think in that comment I was mainly curious about just the first step: how will the grid be generated in the first place (before further filtering)?

[ntalluri]

I will be predefining the first coarse grid, but I'm still deciding what that grid should be. I'm assuming I can figure it out when I do the performance testing of the parameters, otherwise I will set a grid per algorithm based on my knowledge of the parameters.

[ntalluri]

Two-Stage Semi Automated Parameter Tuning

General approach for parameter tuning

GRID SEARCH: STAGE ONE
We begin with a coarse grid of parameter values that can be applied uniformly across all algorithms. This grid will be predefined by Neha for the paper and is designed to be broadly applicable to any dataset. Before tuning begins, the user defines general heuristics, not tied to specific algorithms, that describe the desired properties of the outputs. Neha will also define these heuristics for the paper.
For each dataset (treated as a whole, rather than broken into subdatasets such as individual pathways or cancer cell lines), SPRAS refines the coarse grid for each algorithm according to the heuristics, retaining only parameter combinations that meet those criteria. During this process, SPRAS will generate an updated configuration file that captures the refined grids per algorithm and consolidates them into a single new config file for the dataset. The user then reruns SPRAS with this updated config that includes the new grids, optionally adding new parameter combinations per algorithm and applying the same or revised heuristics to guide further refinement.

Config for Dataset coarse grids per algorithm -> new config with new coarse grids per algorithm

Stage 1 continues until the user decides that the coarse grids are sufficiently tuned, at which point they proceed to Stage 2.

GRID SEARCH: STAGE TWO

In Stage 2, refinement shifts from the dataset level to the subdataset level (e.g. pathways, cancer cell lines). Using the refined coarse grid config file from Stage 1 as the starting point, the user indicates that they want to begin Stage 2. At this point, SPRAS automatically generates a separate configuration file for each subdataset, initializing it with the coarse grids refined per algorithm during Stage 1.

Stage 1 (coarse grids per algorithm) -> Stage 2 (configs split into subdatasets, with each algorithm having Stage 1 coarse grids))

From here, SPRAS refines the grids per subdataset to create fine-tuned grids. The user decides which heuristics to apply, either reusing the Stage 1 heuristics or defining new ones. They may also choose to keep the existing parameter grids as-is or add new parameter combinations per algorithm. SPRAS again refines the grids according to the heuristics, retaining only parameter sets that meet the desired criteria. Updated configuration files are generated for each subdataset, consolidating the refined grids into a new config file per subdataset.

Stage 2 continues until the user determines that the subdataset level grids are sufficiently fine tuned per algorithm, at which point they move on to the final step: parameter selection and evaluation.

This was one prototype on how this process could look

PARAMETER SELECTION

Parameter selection is handled in the evaluation code, which supports multiple strategies such as ensemble selection, PCA-based selection, or using the grids directly with no parameter selection. This functionality is already implemented for nodes, and work is underway to extend it to edges.

It is important to note that during grid search and refinement (Stages 1 and 2), no evaluation should be performed to determine which grid spaces to keep. At that stage, users must rely solely on heuristics to guide refinement.

Once the grid space search is complete for each subdataset, the user can enable evaluation (by setting evaluation: true) and run the parameter selection code. At this point, SPRAS applies the chosen evaluation/parameter selection strategy to finalize parameter sets.

PCA-Based Parameter Selection
The Principal Component Analysis (PCA) approach selects an optimal parameter setting for each pathway reconstruction algorithm. Parameter settings are used to generate pathway outputs, which are then projected into algorithm-specific PCA spaces. Within each space, a centroid is calculated to represent the average position of the algorithm’s outputs. The output closest to this centroid, based on Euclidean distance, is identified as the most representative. The corresponding parameter setting is then selected as most representative, ensuring that the chosen pathway is most characteristic of the algorithm’s overall reconstruction space. We plot precision and recall plots per algorithm per dataset and precision and recall plots per dataset.

Ensemble Network-Based Parameter Selection
The ensemble network–based approach uses edge frequency analysis to aggregate outputs across all parameter settings for each pathway reconstruction algorithm. All the generated pathway outputs are aggregated into algorithm-specific ensemble networks. In these networks, edge weights reflect the average frequency of each interaction across outputs. The resulting consensus networks capture the core structure of each algorithm’s outputs without overfitting to any single parameter setting. Rather than selecting one optimal pathway/parameter setting, this approach offers a holistic view of each algorithm’s reconstruction behavior. We generate a pr-curve per algorithm per dataset and a pr-curve per dataset.

Ground Truth-Based Evaluation Without Parameter Selection
The no parameter selection approach evaluates all possible parameter combinations for each algorithm, comparing each resulting algorithm-specific output against a ground-truth dataset. By generating precision and recall plots for each algorithm per output pathway, it provides an unbiased measure of how effectively an algorithm reconstructs biologically relevant networks. We plot precision and recall plots per algorithm per dataset and precision and recall plots per dataset.

HUERISTICS

For the first pass of implementing semi automated parameter tuning, we will use heuristics based on summary statistics and Jaccard similarity to guide refinement. These are already implemented into SPRAS.

Additional heuristics, such as incorporating nondeterministic runs to capture outliers or accounting for time constraints of algorithms, are more complex to implement for the first pass. For now, I please skip these and focus only on summary statistics and Jaccard similarity. We can revisit and incorporate the more advanced heuristics later (if they’re needed).

Heuristics used for parameter tuning grid spaces

[tristan-f-r]

My current broad impl plan is to generate the entire configuration for both the initial grid search and all of its finer grid searches beforehand, and add conditionals that allow a run to execute when a list of runs does not fail. [I'll more rigorously define conditionals in a separate issue]

Other than implementing conditionals, this would also require some error handling refactoring, where:

• We allow runs to fail if certain heuristics (from your parameter tuning PRs) fail.
• We [optionally, probably true by default] allow for containers to fail without breaking the entire workflow (Algorithms don't fail gracefully #21)

[ntalluri]

@tristan-f-r What do you mean by the heuristics from my parameter tuning PRs?

Also what are the conditionals that need to be in a separate issue? Is there a way you can explain it in this issue?

[tristan-f-r]

I worded 'heuristics' badly - I meant the desired properties we want the output graphs from each dataset (and subdataset for the second stage) to have

From my understanding of paramater tuning, while it is two stages, there's a common pattern that can be used to simplify the workflow: if runs A, B, ... Z match our desired graph properties, then we want to run some other parameter combination.

Unless there's a lot of human intervention between the two parameter tuning stages (which, to my understanding, there is some, but not a lot), we can actually generate a single large configuration file (or split into multiple configurations that can be merged for readability purposes), where the second stage runs "depend" on the results of the first stage runs.

The config-based definition of conditionals can be something like:

# This isn't the exact format I actually want in the config,
# especially since the property info is declared per-run.
# There is likely a nicer way to express this, but this will do for a rough example.

run1:
  include: true
  # run1 will 'fail' if the output graph doesn't have the desired properties.
  must_have_properties: 
    centrality: ...
  ...
...
run3:
  include: true
  # if run1 and run2 don't fail, do run3
  if: [run1, run2]
  params:
    alpha: 100
    ...

I would like to generate the entire configuration file in one go (or at least generate multiple configs + merge them before putting them into Snakemake) that way we get parallelization benefits, and can have Snakemake run parts of the 'stage two' parameter tuning while longer algorithms in 'stage one' are still going.

[tristan-f-r]

This implementation proposal describes a general outline of the parameter tuning implementation, along with details that (I/we) aren't sure about yet.

Some of this is just a summary of the parameter tuning document.

First grid search

We need a way to be able to:

1. Attach range and step information to parameters: each parameter should have a (coarse) range of parameters that works for datasets in general. feat!: typed PRA#run #329 gives us the ability to attach metadata to individual algorithm parameters. (We will need a follow-up PR to enable range metadata)
2. Have a list of graph heuristics
   • We'll look ahead here and allow graph heuristics to be specified per dataset category for the second grid search (using categories feat: Dataset#category #406), but graph heuristics can also be specified in general for all datasets. This will be its own PR that allows runs to fail (as clarified in (4)) when they don't meet their dataset's category's graph heuristics
3. Generate a parameter config using the ranges from (1):
   • This will be done with the SPRAS CLI (feat: cli #332), where we input our datasets (which also happen to contain our general graph heuristics from (2))
   • We need to make sure that per-dataset-category graph heuristics are strictly stronger than the general graph heuristics.
   • This will parse the internal ranges with feat!: typed PRA#run #329, after making a PR building on top of it that adds range union support.
4. Get a list of parameter combinations that 'succeeded'
   • We say that a run fails if it doesn't meet the graph heuristic criteria. This allows us to dump all of the errors we get (dataset incompatibility errors, internal SPRAS errors, and our new graph heuristic errors) all in the same place, and make our grid search more tolerant of errors in general. We can also better classify them (see refactor: add MissingDataError #394) to make it easier on the user to spot issues with SPRAS/their configuration/actual graph heuristic problems

We can dump some file (as suggested by @ntalluri) in logs of all of the jobs and if they had errors or not (i.e. a report.json that can later be formatted as proposed in #380.). I've proposed an alternative to this under the separator in this issue (at the bottom of this issue).

Second grid search

Using the information in the report.json file, we can generate a new configuration file (again with the SPRAS CLI), containing all of the parameters 'in between' of our successful runs (this seems like something that we can figure out when we get there: especially with dependent parameter combinations, this seems like it has too many smaller edge cases to address in the overall plan. For now, we can assume that this bridge between the first and second grid search exists).

We'll use our per-category graph heuristics at this level, and set certain parameter combinations to only run on certain dataset categories (superseding the original plan of having multiple long HTCondor runs: multiple long HTCondor runs is somewhat simpler for a SPRAS implementation, but monitoring multiple HTCondor long run jobs seems like a pain when HTCondor already has the tools to monitor one. Especially given that the HTCondor code would be quite difficult for SPRAS to put on CI, I would like to minimize it when possible.)

From here, we move to evaluation of all of our parameter runs, where, under my impression, this part has already been mostly implemented.

---

I would like to have the entire configuration (both the first coarse grid and the second grid with intermediary values) be generated in one configuration file, instead of splitting it into two, for:

• Convenient determinism
• There are very few scenarios where I can imagine that people would want to manually look through the coarse grid by hand over using graph heuristics
• Opportunity for Snakemake parallelization

We should have a system that allows us to say that a run X will go after some other runs Y succeed (this is what I meant by 'conditionals') to encode all of parameter tuning into one single config generated by the SPRAS CLI.

[ntalluri]

This document currently contains the new conceptual idea for two stage parameter tuning:

https://docs.google.com/document/d/1PJFGeNkE63RkopGdRIkEJYOJ2yPFKkxeIMtqXANep6U/edit?usp=sharing