@ntalluri is starting to work on incorporating directed edges, so we're talking about that at our meeting today. We realized there are a number of issues, so we wanted to start a conversation about them.
Some algorithms support directed edges, some don't. Issue #28 suggested that perhaps this isn't an algorithm-level decision (and shouldn't be in the CONFIG file as a user option), but we should decided on how each algorithm supports directed vs. undirected edges. @ntalluri is collecting information about each algorithm, which will be very helpful.
Directed vs. undirected edges is actually a data attribute (the interactome). Further, if a method supports either directed or undirected edges, then this information must be used in the generate_inputs() function to prepare the network files (unless it's passed directly to the algorithm as an argument). For example, if a network is undirected, then RWR should convert it to a bidirected graph before running. If it's directed, RWR doesn't need to convert it. (The decision that RWR runs on a bidirected network is one that we, the developers, made).
Maybe a general table like the one below will help us make these decisions for all algorithms?
It supports partially directed graphs, but the format is different from the way we are probably going to set up the input files with. The file format looks like this https://github.com/agitter/meo/blob/master/sampleEdges.txt. It uses a pp to represent undirected edges, and pd for directed edges.
The format works by adding a fourth column for directionality to the input network file. It will take a U for an undirected edge and a D for a directed edge from the first to second column
Omics Integrator 2
In omics integrator 2, it mentions in graph.py that “ # edges: a 2D int64 array. Each row (of length 2) specifies an undirected edge in the input graph. The nodes are labeled 0 to n-1, where n is the number of nodes. “
Based on this, it specified that each row of the array represents an undirected edge in the input graph, so I believe that it only takes undirected edges
MinCostFlow
Based on my research, OR Tools MCF is designed for directed graphs, not undirected. When we give it an input network, when an edge (arc) is added, it has a source node (which is the tail) and a target node (which is the head), so flow is only allowed to move from the source to the target
To use MCF on an undirected graph, we can convert the undirected edge into 2 directed edges, one in each direction. The capacity would remain the same and this would infact show the flow moving freely in both directions.
Relevant to the discussion of converting undirected graphs to directed graphs with duplicated directed edges
The version of Pathlinker that is wrapped in SPRAS works with directed edges that also have an associated weight. An edge is represented with a head and tail node in the current input network format, which indicates the direction of the interaction between two nodes. If we want to put an “undirected edge” - meaning an interaction that is bidirectional - Pathlinker would require for both paths to be put into the input network file (one for each direction of the interaction)
This is similar to how Min Cost Flow could take in the input after conversion
Relevant to the discussion of converting undirected graphs to directed graphs with duplicated directed edges
All Pairs Shortest Paths
The algorithm appears to be capable of accepting only undirected edges and allowing bidirectionally if an edge and its reverse are placed in the input network.
The code uses nx.read_weighted_edgelist() and nx.Graph() which both are used for undirected graphs
nx.shortest_path can work on both undirected and directed edges, but it seems by the rest of the code that it is creating an undirected graph
Domino
Based on the build_network function in domino, it created an undirected graph using nx.Graph() and the provided input file. The function will read the 1st and 3rd columns from the file (which are node pairs that make up the edge). Each of these edges will be added to the undirected graph with a score (if there is a unique node).
When it is run through the algorithm, it will see that bidirectional edges are equivalent. This means we can use bidirectional edges in the input.
RWR
From eric: Regarding the RWR (Random Walk with Restarts) process, it takes into account both directed and undirected edges in its execution. When encountering undirected edges, RWR converts them into two directed edges, one in each direction to represent the relationship between the nodes more accurately.
This explanation doesn’t seem to be right, based on the code I looked at. It seems to only be able to handle directional edges
Generate_graph is constructing a directing graph (nx.DiGraph()) using the nodes and edges provided to it from the other methods
In generate_nodes_and_edges, it seems that it is going line by line and adding what is in the provided edge file to the set of nodes and the array of edges without adding the reverse edge to the set of nodes and array of edges
It truly seems that the code expects the edges provided are already directed and are not converted to be bidirectional
TieDie
From Eric: TieDIE deals specifically with directed edges, which are represented in the format A -a> B where -a> stands for activation. While the TieDIE repository provides examples with various types of interactions, such as inhibitions, SPRAS focuses solely on considering activation interactions in the interactome. This limitation is due to TieDIE's requirement to discern the activating relationships between genes, which is crucial for its execution. As a result, undirected edges are not used in the TieDIE process.
parser.add_option("-n","--network",dest="network",action="store",default="superpathway.sif",help=".sif network file for the curated pathway to search. <(-a>,-a|,-t>,-t|,-component>)> ")
Based on <(-a>,-a|,-t>,-t|,-component>)> from the actual tiedie code, this takes in these interactions, but in tiedie.py in spras only allows for -a>, so we only allow for activated directed edges
Make directed edges into undirected (not bidirectional), keep undirected edges as is
Make undirected edges into bidirectional edges, keep directed edges as is
Ready to Run
Converting from Undirected to Directed graph:
by allowing for bidirectional edges, we aren't loosing too much information because most of the information will be inherently retained in the graph because the relationship is still preserved.
Converting from Directed to Undirected graph:
We would be directly converting a directed edge into an undirected edge, so we will loose any sense of directionality and the graph won't be inherently accurate, but the basic relationship between the two connected nodes will still remain intact.
the code will add a undirected column of directionality
Type 2:
A B 1 D
B C 1 U
this can be a mix of directionality
Second idea
we can keep the two file formats, but in the config file add a line where a user can mark true/false for directionality (overall) rather than per algorithm.
with this, we can do a series of checks. If marked true we assume there are 4 columns, and if not we give back an error. If false, then we assume 3 columns and no directionality. (however do we still assume the graph is undirected)
There is a similarity between completely directed algorithms and a similarity between completely undirected algorithms based on the existing algorithm formats.
Pathlinker, Min-Cost Flow, and RWR are all completely directed graphs with a similar structure. TieDie is likewise completely directed, but the only difference is that it contains a separator between each node (currently does this, the code may change?).
Both Omics Integrator 2, APSP, and Domino are completely undirected, with the only difference in format being a separator between each node in Domino.
fullyUndirectedConversion(universal_input, sep(?), directionality)we actually might not need this
A user will be able to call one of these functions with an optional separator, which will turn the universal input into the appropriate graph depending on the graph conversion logic from the table above and whether or not it includes a separator.
if three columns, then we need to know if directed or undirected to be able to pass it to the functions to let it know how much it will need to modify the df based on the conversion logic from the table above
if there are 4 columns then we will have to check between the direction marked and then convert to the form needed based on the conversion logic above.
At the moment there is no commonality between the algorithms that deal with mixed graphs; however, in the future there may be.
It is possible to build a function mixedConversion(universal_input, directed_sep, undirected_sep, col_loc(?), directionality) that will convert the universal input into the format MEO uses, or if the column location for the direction column is given, then it can be generalized to any algorithm that uses a format somewhat similar to MEO.
And for Omics Integrator 1, it uses the universal format straight away (there is a chance other algorithms in the future will too)
this will only work for 4 columns
however, if there are only 3 columns, then we will need to add that direction column of 'U' or 'D's based on the directionality marked in the config file
Future
This currently works for the algorithms in SPRAS; in the future, when new algorithms are added, we can evolve/add to the conversion functions.
Algorithm conversion Example
Pathlinker
Undirected 3 columns: check if undirected, if so send to fullyDirectedConversion where it will check to see the 3 columns and undirected and convert to bidirectional edges
Undirected 4 columns: check if undirected. If so, send to fullyDirectedConversion where it will check to see the 4 columns and undirected, remove the direction column and convert all to be bidirectional edges.
Directed 3 columns: check if directed and 3 columns, no conversions to be done, ready to be used
Directed 4 columns: check if directed and 4 columns, remove the direction column
Mixed 4 columns: check if mixed. If so, send to fullyDirectedConversion where it will check to see the 4 columns and mixed. It will go line by line and convert the undirected edges to be directed and leave the directed edges as is. It will also remove the direction column.
Omics Integrator 2:
Undirected 3 columns: check if undirected and 3 columns, no conversions to be done, ready to be used
Undirected 4 columns: check if undirected and 4 columns, remove the direction column
Directed 3 columns: check if directed and 3 columns, no conversions to be done (treat as an undirected graph), ready to be used
Directed 4 columns: check if directed and 4 columns, remove the direction column (treat as an undirected graph)
Mixed 4 columns: check if mixed and 4 columns, remove the direction column (treat as an undirected graph)
Meo:
everything will call mixedConversion:
Undirected 3 columns: check if undirected and 3 columns, add a column of direction using undirected_sep
Undirected 4 columns: check if undirected and 4 columns, remove the direction column, add a new column of direction using undirected_sep
Directed 3 columns: check if directed and 3 columns, add a column of direction using directed_sep
Directed 4 columns: check if directed and 4 columns, remove the direction column, add a new column of add a column of direction using directed_sep
Mixed 4 columns: check if mixed and 4 columns, go row by row using the direction column provided to create a new direction column using directed_sep and undirected_sep per row.
Omics Integrator 1:
Undirected 3 columns: check if undirected and 3 columns, add a column of direction using 'U'
Undirected 4 columns: check if undirected and 4 columns, ready to use
Directed 3 columns: check if directed and 3 columns, add a column of direction using 'D'
Directed 4 columns: check if directed and 4 columns, ready to use
Mixed 4 columns: check if mixed and 4 columns, ready to use
A df that is provided to these functions should be modified to the point where it can call these functions last, with the respected columns (if necessary) still present, so that the direction column can be included in the outputs.
For the fully directed and fully undirected algorithms, we can have two functions in util.py:
add_direction_column_directed(df)
this would take the df that is already being modified and add a new direction column of 'D's, returning the transformed df
add_direction_column_undirected(df)
this would take the df that is already being modified and add a new direction column of 'U's, returning the transformed df.
For the mixed algorithms, we can have 1 function
add_direction_column_mixed(df, directed_dlim, undirected_dlim, column_loc(?))
this takes the df and, and by using the directionality's column location, it adds a 'D' or 'U' per row dependent on the directed or undirected delimiter.
Config.yaml
We can put per dataset a graphtype: "mixed"/"undirected"/"directed"
We are able to allow a user to have the absence of the fourth column and add it in depending on the undirected/directed marking. This addresses the possibility that a user gives a dataset with no specification on the nature of the edges; rather than requiring the user to edit the original dataset, we enable the user to specify the type in the config and we can make that modification for them (if needed). By knowing the type overall will help with the graph conversion in generate inputs. If the user adds the fourth column of directionality, we can still check that it exists and then allow it to pass. (Do we want to check if the whole column is directed/undirected?)
If a graph has mixed directionality, the user must enter it manually. If "mixed" is selected, we can ensure and check that the network has four columns (Do we want to check that the column is a mix of only 'D' and 'U's). If there are three columns but "mixed" is selected, we can flag an error and notify them before executing the entire program.
Dataset.py
self.interactome = pd.read_table(os.path.join(data_loc,interactome_loc), header=None)
num_cols = self.interactome.shape[1]
if num_cols == 3:
# TODO: it may be easier for the generate_inputs implementations if this is always transformed to
# have a default Direction directed or undirected based on what is written in the config file
self.interactome.columns = ["Interactor1", "Interactor2", "Weight"]
elif num_cols == 4:
self.interactome.columns = ["Interactor1", "Interactor2", "Weight", "Direction"]
else:
raise ValueError(f'edge_files must have three or four columns but found {num_cols}')
Generate Inputs
To deal with the logic from the conversion table and what functions to call or columns to add, we need to know the kind of graph. By knowing the number of columns and the type of graph will allow for the correct functions to be called based on the table of graph conversion logic above.
Omics Integrator 2 can deal with fully undirected graphs
I looked at its code as well and agree it uses undirected graphs. It has NetworkX Graph objects, which are undirected, and uses pcst_fast solver, which supports undirected graphs.
Now that you have done all of this work, I suggest that your pull request include some of this information in the Class or generate_inputs docstrings of each method. For instance, we can document what you learned about the method's support for undirected, directed, and mixed graphs and the assumptions SPRAS makes when preparing input graphs. We could even document the expected raw input file format.
I agree with your updated table about the behavior for each type of algorithm on each type of graph.
We may want to put the helper functions for converting graphs in Dataset.py instead of util.py. util.py is already crowded. I see two types of operations needed:
one takes the existing graph and coverts edge types (e.g. undirected to pairs of directed or directed to undirected)
one organizes the node ordering and separators
I think it will help reusability and implementation to keep those separated. I'm imagining less algorithm-specific logic and suggest making the 3 vs. 4 column input file handling standardized when the file is first loaded by Dataset.py so by the time generate_inputs accesses the dataframe it will always have 4 columns.
In our last meeting we talked about using the config file to specify whether the 3 column format is all directed or undirected edges. That would be a nice feature. However, I propose keeping this simple at first and assuming the 3 column format is always undirected. If there is demand for this extra flexibility, we could easily add it later.
@annaritz we noticed that most of SPRAS currently works with undirected graphs, but PathLinker uses directed graphs. We are currently taking the input graph to SPRAS (which the user likely assumes is undirected) and then passing those edges to PathLinker, which interprets them as directed edges. That seems wrong to me.
@ntalluri's enhancements will fix this behavior, but the current PathLinker wrapper is not ideal in this respect.
Separately, we discussed that there isn't a practical need for a helper function to make a directed graph undirected. The algorithms that would use this instead can simply drop the fourth column with the directionality information.
The edges are dealt within for in the index, and the columns are the algorithms. The rest of the methods are not dependent on the edges/index (the first line of code for each method drops the index) so nothing has to change for them.
ml.py
add a UNDIR_CONST and DIR_CONST to replace the current NODE_SEP (since this assumes everything is undirected)
summarize_networks
when making the edge_tuples, now take into account the direction in the fourth column. Add the directionality constant accordingly.
ensemble_network
At the moment, it means across edges (axis 1) and returns the edge-pair and frequency. It then proceeds to divide the two nodes into Node1 and Node2. If I do this now, the txt file would lose all directionality unless I add a Direction column to each line rather than maintaining it in the edge-pair and frequency form, which already has the UNDIR_CONST and DIR_CONST, which sounds like random extra computations for the same benefit.
so I think my plan is to keep it in the edge-pair and frequency form and write that out
For networkx digraphs and graphs, it doesn't allow for multiple parallel edges. With that in mind, I need to test this on the algorithms to see which ones fail.
I've done it before, but I don't remember the outcome, so I'll create test cases to maintain testing.
example:
A B 1 U
B A 1 U
convert to directed
A B 1 D
B A 1 D
A B 1 D
B A 1 D
UPDATE:
through testing, we know the code won’t crash thus the algortihms can run with inputs of multiple parallel edges; however, for parallel edges, networkx digraph and graph will replace the edge with the most recent of the edges from the input when a parallel edge is encountered.
In summary.py, I think the approach is to work exclusively with undirected graphs:
Allowing mixed directionality could potentially inflate the actual number of nodes and edges if any conversions are done, leading to inaccuracies in our graph representation.
The majority of the operations we are interested in performing require the graph to be undirected. This makes me question the initial option to choose between directed and undirected graphs in the run function, especially when the summarize_networks function mandates an undirected graph.
As for the summarize_networks function, it was initially set up to create a weighted edge list, but those weights were never actually utilized in any calculations. To accommodate the "Direction" column in the edge list, my plan is to read the edge list as is (nx.read_edgelist) and rename the "rank" attribute to "weight." This way, if we ever decide to incorporate weights, we'll have that data readily available.
I'm still uncertain about the correct approach for this part of the code, but for the time being, focusing on undirected graphs appears to be the most straightforward and useful strategy.
ntalluri
commented
1 year ago 
agitter
annaritz
@ntalluri is starting to work on incorporating directed edges, so we're talking about that at our meeting today. We realized there are a number of issues, so we wanted to start a conversation about them.
generate_inputs()function to prepare the network files (unless it's passed directly to the algorithm as an argument). For example, if a network is undirected, thenRWRshould convert it to a bidirected graph before running. If it's directed,RWRdoesn't need to convert it. (The decision thatRWRruns on a bidirected network is one that we, the developers, made).