Possible incorporation of causal-graphs in networkx

[adam2392]

Hi,

I've become quite acquainted with the networkx API and recently began working with the pywhy/dowhy team on the discussion of how to enable a centralized API for causal-graph operations to enable i) structural learning algorithms and ii) causal ID from graphs and iii) other future pipelines.

Initially, we had a brief discussion on representing mixed-edge graphs. At a high level, I believe a networkx-like API is the best path forward considering networkx has cemented itself for "graph-related" things in Python. However, causal graphs have some issues in easily subclassing networkx. Therefore, we run into a dual problem of i) how to represent causal graphs robustly and ii) how to then leverage them to implement algorithms in causal inference algorithms.

Motivation for adding causal graphs in networkx

This would be an ideal centralized place since the API can then be consistent, and then pywhy / causal inference would not need to re-invent the wheel.

I understand that networkx is not interested in representing mixed-edge graphs currently because it would involve a large overhaul. However, I think that causal inference is growing so much that it could serve as a potentially interesting submodule within networkx that works with certain graph algorithms (e.g. d-separated), but not necessarily the others. Similar to how some algos work with undirected but not directed graphs (and vice versa).

This would then not only i) consolidate the causal graph API, but ii) also engage causal inference community into networkx.

Possible solution

In https://github.com/adam2392/causal-networkx, I've implemented my take on causal-graphs. I would specifically take a look at the files in graphs/ such as the ADMG.

The pywhy team and I were wondering if there is interest in taking causal-graph implementations directly in networkx?

Note I've implemented mixed edge graphs by representing different edges using different networkx graphs. Rather than use edge attributes because it seemed more natural and robust to me.

Misc.

DAGs work fine, but that only covers a small portion of causal inference, whereas to fully encompass the literature, we would need representations of ADMGs, CPDAGs and PAGs as well.

[rossbar]

Can this be accomplished without subclassing/adding new dedicated data structures? The existing graph classes are extremely flexible, and usually sufficient to represent different graph types. For example, NetworkX has a whole set of algorithms for working with bipartite graphs, but there is no BipartiteGraph data structure (similarly dags, etc.). This is (IMO) very convenient because users don't have to learn new interfaces - they can use the data structures they already know to represent their problem however they like!

I'm certainly not against adding more algorithms for causal inference! Personally I would prefer an approach similar to bipartite graphs; i.e. there can be a causal namespace, and within that namespace the algorithms can have expectations on otherwise flexible graph properties (for example - edges must have a "type" attribute). This would be much more inline with the existing NetworkX ethos - i.e. few interfaces, lots of functionality.

[darthtrevino]

Would it make sense to create a new package that encapsulates these ideas as they develop while we hash out incorporating directly into NetworkX? e.g. (pywhy-networkx-extensions)

[adam2392]

Re new package: @amit-sharma wdyt?

Re current proposal: @darthtrevino I think the basic idea of just m-separation and path finding algorithms for mixed-edge graphs is pretty set. Is there anything there that would help speed things up? I think the most crucial part that the causal-graph community lacks is a centralized API for graph manipulations. The idea of a MixedEdgeGraph sounds great to "base" things off of.

[amit-sharma]

From py-why's perspective, I'm open to creating a package where we can iterate on the graph structures and test them with the downstream causal algorithms we want to build.

However, it will be ideal if there is a common base from which we can build on. @adam2392 's proposal for a generic MixedEdgeGraph and (m-separation, path-finding) inside NetworkX is a good step in that direction, especially since we currently use networkx's d-separation function for DAGs.

[dschult]

It's likely a good idea to create a way to "play" with the different possible MixedGraph classes to see which structures work well and provide a good interface. We build many many versions of the NetworkX graph classes with major revisions before settling on something. I suspect that might be true here as well. And you might end up with more than one if some algorithms are better with one and other algorithms are better with the other.

[robertness]

We build many many versions of the NetworkX graph classes with major revisions before settling on something.

The mixed graphs @adam2392 mentions and the related base algorithms are quite established in the causal inference literature. While I think here would be some revisions at first, but I think we might settle on something fairly rapidly, and that it would have adoption by Python causal inference libraries beyond PyWhy.

[robertness]

In addition to Adam's work, I'd point out this implementation of mixed graphs in the causal learn package.

[adam2392]

Leaving some thoughts here from our last discussion:

• mixed-edge treatment: really like the first-class citizen treatment of edges, which could be more elegant for endpoint/middle-marking of edges (i.e. more exotic treatment of various edges)
• tradeoffs: ^ here edges may be extra "functional" since my proposal for representation uses a separate networkx graph per edge type. For me this is the major design tradeoff for trying to work w/ networkx, since I can imagine exotic edges emerging, but I think it can be handled w/ the multi-graph networkx abstraction
• efficiency: I think the underlying data structures as a List will run into many scalability issues during graph operations for structure learning, so that is why networkx is lovely.
• functionality: The classes are doing too much, so hard for me to parse beyond too much but the functionality looks promising if we can refactor. Most of the algos I can see being in pywhy vs networkx.

Awesome!

[adam2392]

@rossbar and @dschult in line with our discussion above, I have sketched out a basic API proposal that I think aims to have both the generality that networkx aims to have, as well as a concrete proposal for some core algorithm(s) for the networkx.causal submodule.

https://github.com/py-why/dowhy/wiki/Networkx-Proposals-for-Causal-graphs-and-causal-graph-operations

The goal for the pywhy team is to make sure networkx is kept in the loop, such that we don't waste any work and make sure the general interface is PRable to networkx and then pywhy can be responsible for the more nuanced causal-graph operations. Let us know your thoughts?

[dschult]

I've looked through the proposal you've put together -- and I understand it is (rightly) a rough view -- but I'm glad to see multiple function signatures, and APIs being fleshed out. I am encouraged by the direction you are taking. I have a few quick comments below. But they should not be considered complete. The discussion will continue for sure.

Comments:
Part of the proposal talks about an AdjacencyView which reports all types of edges. I just wanted to say that we have an example of a UnionAdjacency which takes a union of outgoing edges and incoming edges. I think it would be straightfoward to extend that to 3 adjacency dicts: outgoing, incoming and bidirectional.

Writing to a dot file should be straightfoward so long as you have a way to report all the nodes and all the edges with attributes. Actually, you may not need all the attributes. As for finding a minimal separating set, that sounds like a cut-set (which we have a way to get) but we'll have to check if they are the same thing.

I think your way to finesse bidirectional edges in m_separation using phantom nodes is slick.

[adam2392]

It sounds like this is the right direction at least. Then here's my proposed plan:

1. I will implement the MixedEdgeGraph proposal inside https://github.com/py-why/graphs, which serves as a "playground" for what we are proposing is PRed into networkx. The intention is that the code here will be pretty lightweight, so it's easier to PR into networkx.
2. In conjunction, I will leverage this generic implementation inside the causal graph implementations inside https://github.com/py-why/pywhy-graphs.
3. After this is up and running, I suppose we can circle back and link the two repos to have a more in-depth discussion? Slash I could also draft a PR at that point to merge the code inside graphs repo to networkx?

[adam2392]

Hi @dschult and @rossbar, some issues that came up on my end while implementing the MixedEdgeGraph: https://github.com/py-why/graphs/blob/main/graphs/classes/mixedgraph.py. I wanted to get the networkx dev thoughts.

If you skim the code, you'll see I basically try to replicate the nx.Graph API, so that it returns the same things more or less. Besides the functions that I mention below, the available API matches exactly that of nx.Graph.

1. Regarding *View return data structures for things like adj and subgraph, would it be best if I implement a set of MixedEdge*View objects? Or something else? I don't see a way to subclass / use the existing view data structures... but I'm also not that familiar w/ those.
2. Is this initial implementation along the lines of what you would expect and think is valuable for generic usage by networkx community?
3. the degree() function seems to be vital. My thoughts on including this function is just to treat all edges as the same, and compute degree that way. If someone subclasses, then they could implement in_degree() if they want to distinguish incoming edges from e.g. bidirected edges.

[adam2392]

Would it be better to add these to our fork of networkx? I just wanted to make sure this was a good start for inclusion before doing the work to make it play nicely in networkx.

[dschult]

Hi @adam2392, The approach you are using in the link above looks like a copy of the graph.py code with doc_strings and all and then some items have changed. It is really hard to tell what has changed and what hasn't. To go with this route, maybe it would be helpful to make a subclass of the Graph class so you can see what has changed and what hasn't. I didn't see much if any check that the nodes in each of the graphs are the same throughout. I think that would be just fine -- you can rely on the user to not mess up the data structure. But if you are going to do that, then you should probably build this without the machinery of EdgeViews and the rest. Just stick to G.nodes is a dict-of-dict and G.adj is a collection of dict-of-dict-of-dicts. Then worry about making thing read-only views later.

I am thinking that you are creating a collection of graphs -- one for each edge type. The node manipulations are applied uniformly to all the graphs. <Typo: add_nodes_from is currently doing an add_node on each graph instead of add_nodes_from>

The edge manipulations are not as clear to me. has_edge, add_edge, add_edges_from take a require edge_type to indicate which graph to update. So, perhaps the reporting of edges should also... Then you'd want a reporting option that includes all types of edges. Maybe the edges method should include a list of edge_types to report on -- and the edges function makes a long list of edges collected from all the different graphs.

Similarly with adj. Your proposal returns a dict of adj structures. Would you want a class which joins some or all of them together for certain operations. The most common would be for nbr in G.adj[node]: ... I guess now that would be:

for nbr in (nbr for edge_type, nbrs in G.adj.items() for nbr in nbrs if edge_type in requested_edge_type):
    ...

Should edges work that way too? G.edges returns a dict keyed by edge_type to the edges view from the corresponding graph?

for edge in (edge for edge_type, edges in G.edges.items() for edge in edges if edge_type in requested_edge_type):
    ...

I'm just thinking out loud -- so probably are issues with this you/we would need to work through.

I think the degree functions could be arranged similarly -- provide a requested_edge_types argument and then sum the degrees from the different graphs:

def degree(self, requested_edge_types, ...):
    for node in self:
        for edge_type in requested_edge_types:
            deg = sum(len(nbrs) for nbrs in G.adj[edge_type][node])
            yield node, deg

These examples don't provide all the bells and whistles of G.edges -- like whether it returns data, etc; and G.degree -- like weighted degree, etc. But that could be added later. And it avoids the whole view mess -- which makes the returned adjacencies read-only.

How are you going to denote the edge type when reporting the edge? (u, v, data, edge_type)?

I'm not sure this was what you were looking for, but it is some ideas based on what you've got so far about how we might handle reporting edges/adj/degree.

[dschult]

Adjacencies:
Currently, directed graphs store both the G.succ successors and G.pred predecessors and adjacency structures. There are methods G.predecessors() and G.successors() that return just the nodes with the dict structure. The G.adj and G.neighbors() features only provide successors -- so code like shortest_path can use them and get the successor info when the graph is directed.

To get both succ and pred we have a function nx.all_neighbors(G, node). And finally, there is a little used/little known about adjacency view nx.coreviews.UnionAdjacency which takes in two directed adjacencies and presents them as a single adjacency view. It currently only works with 2, but maybe more could be easily incorporated.

Tests:
I don't think you need to test the Graph features of the Mixed graph case. The important tests here are to make sure that selecting the type of edge works properly. (Maybe nodes should be tested to make sure they don't duplicate or get out of sync.) But you are directly using the Graph/DiGraph classes, so you don't need to test them again. Stated more generally, test the features of the interface you are developing, and rely on the other test suite to test the features of the classes you are building from.

Construction:
I like the idea of being general, but is it going to be too much trouble to support that? Maybe the best approach is to build it for the options you will need -- but don't restrict it to those options in case someone else want to write algorithms that have a different set of options.

[adam2392]

Adjacencies:
Things like shortest_path can still operate on mixed-edge-graph by just having the user call shortest_path(mixed_edge_G.get_graphs(edge_type='directed') as long as this "makes sense" to the user.

A modification to certain functions such as nx.all_neighbors seems simple enough with additional if/else clauses depending on if G.is_mixed() is True.

To create the new View objects for mixed-edge-graph, I think a generalization of UnionAdjacency and UnionAtlas is all that is needed and looks possible.

At this point, it seems the easiest thing to do is keep G.adj as is, with an extra layer of dictionaries representing the edge type. However, it seems in line with the rest of networkx Graphs, maybe it makes more sense to have G.adj and G.edges operate similarly to what nx.Graph does. Consolidate any edge regardless of edge type into this AdjacencyView.

Then, we can augment the MixedEdgeGraph class to have additional API for getting G.adj(edge_type), so it only returns an AdjacencyView for a certain edge type. The user can do something like the following if they want a dictionary of all edge types:

edge_dict = dict()
for edge_type in G.edge_types:
     edge_dict[edge_type] = G.adj(edge_type)

WDYT?

Tests:
Got it. Makes sense.

Construction:
If you're okay with the user having to pass in arbitrary strings, then I guess this is the most general I can think of making it. I suppose downstream subclasses of MixedEdgeGraph would be responsible for hard-coding the strings needed per edge type. E.g.

# the user of ADMG is not exposed to the need to specify the str at all..?
class ADMG(MixedEdgeGraph):
     def __init__(self, directed_edge, bidirected_edges, undirected_edges, **attr):
             internal_graphs = construct(directed_edges, bidirected_edges, undirected_edges)
             super().__init__(internal_graph, edge_types=['directed', 'bidirected', 'undirected'], **attr)

This buys MixedEdgeGraph some generality, but it does impose some restrictions on the functional API needed to support algorithms. For example, m-separation function would need the user to pass in explicitly the string representing the edge types for directed/bidirected edges. I'm okay with this if you are. Alternatively, m-separation can infer this if the string for directed/bidirected edges is hard-coded and MUST be part of an enumeration.

[dschult]

Adjacencies:

maybe it makes more sense to have G.adj and G.edges operate similarly to what nx.Graph does. Consolidate any edge regardless of edge type into this AdjacencyView.

How would you consolidate? Does a bidirected edge report as two directed edges? There would need to be some agreement on what kind of "usual graph" treatment these enhanced properties would provide.

Construction:
It seems that the user will have to use the right explicit string name for the edge types at some point. Typically I think that would happen at G.add_edge. For ADMG it looks like you are constructing starting from three edgelists. (why 3? shouldn't it just be directed and bidirected?) In that case, the ADMG could allow the user to override the edge_type strings if desired, but use those names as the default.

[adam2392]

Adjacencies:

How would you consolidate? Does a bidirected edge report as two directed edges? There would need to be some agreement on what kind of "usual graph" treatment these enhanced properties would provide.

Hmm that's true. Yeah nvm, I think I will just break the API for the MixedEdgeGraph and instead return a dictionary of AdjacencyViews, DegreeView, or EdgeViews keyed by edge type. Then there is an optional kwarg to specify the edge type as well.

This would then at least buy us the auto-error on algorithms that use the adj/edges/degree API, so it prevents users from passing in a mixed edge graph.

Construction: It seems that the user will have to use the right explicit string name for the edge types at some point. Typically I think that would happen at G.add_edge. For ADMG it looks like you are constructing starting from three edgelists. (why 3? shouldn't it just be directed and bidirected?) In that case, the ADMG could allow the user to override the edge_type strings if desired, but use those names as the default.

Yeah the undirected edges represent "selection bias". Sure yeah that makes sense to have an override possibility, but those are the default strings.

So I take it then, you agree with this direction? I think this is the best we can do for now, while keeping MixedEdgeGraph generic and the rest more specific.

[dschult]

Yes, this direction makes sense to me. :)

[dschult]

Your example is a good start to a tutorial as well. :}
It is still not clear that G behaves differently from G in specific intentional ways. So we should add a section about those differences. For example, G.adj requires an argument for which edge type (or will there be a default so that any algorithm can use that default without changing it's code?).

Another comment: We might consider G to be a multigraph since there can be multiple edges between the same nodes -- so long as they are of distinct types. I'm not sure what words should describe this... it's not really a multigraph or a graph.... maybe a mixededgegraph??? I guess the important restriction right now is that reduction to each type of edge produces a Graph or DiGraph. Maybe its too early to figure out how to distinguish between these labels. For example, I can envision someone wanting a multigraph for each of the directed and bidirected reductions. We'll know more when we get to the algorithms.

How would the d-separation algorithm take advantage of this structure?

[adam2392]

Hi @dschult just wanted to follow up in case this was missed. Lmk if you'll need some time tho.

Also to facilitate, I'm happy to jump on a call if needed.

[dschult]

I am confused and somehow thought there was already a PR into NetworkX with this code.
Are you aiming to include it in NX, or to house it in a separate library/package which builds on NX?

If the goal is to merge this code into the NX library itself, then a PR would be helpful. I'm sure there are decisions to be made as part of that (like where to put it). But it would be easier to answer those if we have an example that shows what we're dealing with. Can you easily make a PR to NetworkX?

[adam2392]

Ah I see! Yeah I made the code in a separate repo cuz I assumed it might be easier to show you all, but yeah I can make a PR branch and make this code networkx compatible for further discussion.

To clarify: yes the goal is to PR a general purpose mixed edge graph object.

[adam2392]

Kay I have started a PR in #5947 . We can migrate discussion there.

[adam2392]

Hi

Just wanted to do a light follow up to see if the PR is in the direction that we are aligned with? I realize it's a large PR, so if you have any thoughts on preferring it broken up then lmk.

[adam2392]

Hi @dschult just wanted to lightly ping here to follow up.