Networkx-integration for graph API

[adam2392]

Discussion thread for the graph API. The proposed API is here.

[petergtz]

Hey @adam2392, thanks for writing all this down. I really like it. The only part I don't quite understand, what is the added benefit of:

class CPDAG(MixedEdgeGraph):
    def __init__(self, directed_data, undirected_data):
        super().__init__([directed_data, undirected_data], edge_types=['directed', 'undirected'])

    # API layer for users to work with the specific types of edges
    def add_undirected_edge(self, u, v):
        super().add_edge(u, v, edge_type='undirected')
...

class PAG(MixedEdgeGraph):
    def __init__(self, directed_data, undirected_data, circular_data):
        super().__init__([directed_data, undirected_data, circular_data], edge_types=['directed', 'undirected', 'circle'])

    # API layer for users to work with the specific types of edges
    def add_circle_endpoint(self, u, v):
        super().add_edge(u, v, edge_type='circle')

Is it really just the "customized" edge addition methods? FWIW, I think G.add_egge("X", "Y", edge_type='circle') is quite fine. And NetworkX folks have been quite vocal that they try to keep the number of different graph classes low, and that types of graphs (such as PAG, CPDAG, etc.) should be defined by their edge properties (just like a DAG is a DiGraph with no cycles, not a DiAcyclicGraph). So it seems you can model PAG, CPDAG, etc. all using your MixedEdgeGraph.

If you still think that there are use cases that cannot be satisfied by MixedEdgeGraph, I'd be very curious to see those :-).

Unrelated to this, what does check_G_is_mixed_edge_graph do? Just check that the type of G is some kind of MixedEdgeGraph (via isinstance or similar)?

And finally curious what "converting all bidirected edges to unobserved confounders" in

# convert G to a DAG by converting all bidirected edges to unobserved confounders
dag_G = mixed_edge_to_dag(G)

concretely means. Thanks.

[adam2392]

Hey Peter, thanks for the look.

Is it really just the "customized" edge addition methods? FWIW, I think G.add_egge("X", "Y", edge_type='circle') is quite fine. And NetworkX folks have been quite vocal that they try to keep the number of different graph classes low, and that types of graphs (such as PAG, CPDAG, etc.) should be defined by their edge properties (just like a DAG is a DiGraph with no cycles, not a DiAcyclicGraph). So it seems you can model PAG, CPDAG, etc. all using your MixedEdgeGraph.

If you still think that there are use cases that cannot be satisfied by MixedEdgeGraph, I'd be very curious to see those :-).

So I think the networkx API is not fully complete since it lacks a lot of helper functions that would make things like structure learning API simpler. For example (this list is not exhaustive):

• do(): intervention to create a new graph
• soft_do(): soft intervention
• error checking: DAG, CPDAG, PAGs all only have one edge per pair of variables. Therefore you cannot add an undirected edge and a directed edge between the same two variables.
• accessing the c-components: C-components in ADMGs are crucial for causal ID, that it would be weird to need to run nx.connected_components(graph.bidirected_edges) rather then accessing a property graph.c_components
• class separation: for the PC algorithm, it should return a CPDAG explicitly, and the FCI should return a PAG, rather than a MixedEdgeGraph object.
• potential parents in PAG/CPDAG: rather then query over specific edge types in a MixedEdgeGraph, a user should just be able to query say the graph.possible_parents property and expect the correct answer

Basically, I see the explicit implementations of the causal graphs like CPDAG, and PAG as subclasses of MixedEdgeGraphs that enhance the general networks-like API for causal notions for each specific graph class. This will be useful for causality users doing structure learning, ID, etc. I see this as similar to what scikit-learn does, where they have something like a BaseEstimator and then specific implementations of that for each model: LinearRegression, RandomForest, etc. The goal is to make user life easier while simultaneously not adding too many LOC.

In summary: I think relying on a network-like base class buys us the robustness and consistency we should expect from using networkx. But subclassing it to explicitly provide an API-layer for different common causal graphs is good for a variety of reasons.

I've added some additional details on how this might be implemented in the writeup.

Unrelated to this, what does check_G_is_mixed_edge_graph do? Just check that the type of G is some kind of MixedEdgeGraph (via isinstance or similar)?

Yeah basically and check that the edge types are present with the expected "name" associated with each networkx graph (i.e. bidirected edges and directed edges).

And finally curious what "converting all bidirected edges to unobserved confounders" in

# convert G to a DAG by converting all bidirected edges to unobserved confounders
dag_G = mixed_edge_to_dag(G)

concretely means. Thanks.

This would just be taking all bidirected edges and adding nodes with the attribute observed='no' and then adding edges from this latent node to the nodes connected by the bidirected edges. Then run networkx.d_separated on the corresponding graph. This is the easiest way I can see to implement "m-separation". See the updated wiki.

[petergtz]

Hey @adam2392, thanks for your response. It helped me a lot to understand where you're coming from. I'd like to lay out a bit of the thought process we had when designing the GCM-based inference API you can find in dowhy.gcm (and it seems to be similar to the principles networkx follows). I'm not saying this is the holy grail, but I'd love it if you'd give it a thought.

The GCM API offers many features like interventions, attributing distribution changes, outlier analysis, counterfactuals, influences, etc. We decided not to introduce methods for these on the StructuralCausalModel class, for the following reasons:

• You could make everything a method, but that doesn't scale. You'd add more and more methods to that class every time you discover new scientific methods. The class would become really bloated. And at what point does it not belong to the class anymore and should be a function? It's a bit like with the String class. Is capitalize part of the core feature set of a String class or should it be part of a string utility module? It's certainly not as frequently used as replace. Making everything a function makes this consistent. That's what we decided for.
• Free functions also avoid a distinction between core features added by the library itself and third-party libraries building on top of our StructuralCausalModels. Everything is consistent.
• Building hierarchies of classes will make things less composable, because you'll be restricted to an inheritance tree. By keeping the classes independent from certain features/functions/algorithms, you can make algorithms available for all types where it makes sense.

So in that sense, I don't think that "nx.connected_components(graph.bidirected_edges) rather then accessing a property graph.c_components" would be weird. If you want to make it a bit more convenient, you could introduce a:

def c_components(G):
    return nx.connected_components(G.bidirected_edges)

In fact, this is what we've done e.g. for is_root_node.

I realize you don't get the syntactic sugar you get from a method (i.e. instance.f(...) vs. f(instance, ...)), but I think it's worth the scalability, flexibility, and consistency.

BTW, exactly for those reasons, modern languages like Kotlin or Rust have introduced syntactic sugar to extend existing classes with method-lie syntax without actually adding methods to the class.

So, to close the loop with graphs, I do think that keeping all methods you listed, as separate functions, taking the graph as a first argument would be a preferred design. And then I believe you wouldn't need additional classes, MixedEdgeGraph would be sufficient (please correct me if there's actually a use case that is not possible with that approach). A nice benefit would obviously be that NetworkX folks have already expressed willingness to include such a class natively in NetworkX, whereas they were not in favor of adding many new graph types.

[adam2392]

Hi @petergtz ah I see. Yes your points make a lot of sense. To add to this discussion, here are some thoughts.

My modified proposal summary:

My leaning is to half agree w/ you there.

1. We should have a very lightweight set of classes for causal graphs: DAG, ADMG, PAG, CPDAG, etc.
2. Most of the mixed edge graph algorithms tho should be functions themselves.

Re class method vs function: I agree that overloading a class with class methods is not ideal and can make things rather clunky. In networkx, they do take this approach. E.g. many of the relevant "graph" property algorithms are functions, rather than class methods. However, they still have class methods and such. For example, adding/deleting/querying nodes/edges are part of the graph class, rather than a method. On the other hand, querying if a graph is acyclic is a function, or checking if the graph is bipartite is a function.

Something like c_components is a fundamental component of the ADMG data structure. Requiring users to do something like nx.connected_components(mixed_graph.get_sub_edges('bidirected')) seems very peculiar. If everything is a function, we also bloat the import statements -> every user every time they want to do something simple with a graph has to import 10+ functions.

An explicit example would be children. In the MixedEdgeGraph, there is no notion of children. It is not possible because it tries to serve as a robust base class for handling the problem of storing mixed edges. So then if we follow the function design: children() would either i) require a user to have high cognitive load to get the children using a very specific line of code, or ii) require the user to import from pywhy-graphs import get_children. Imo neither are desirable because children is a fundamental part of a mixed edge causal graph that should be exposed to all users. It is probably a sub-routine in ALL causal algorithms.

On the other hand, agreed that there is a fine line to separate the two. For example, I have compute_all_v_structures() as a function, rather than class method. Not everyone always needs to compute v structures for all graphs. It is a sub-routine for some algorithms. In my head, what should be a class method has to do with a basic API layer of the underlying data structure. Functions should then be anything else that wants to do more complex logic based on data inside the data structure.

Re extend MixedEdgeGraph, or not: With that in mind, the basic issue is that a MixedEdgeGraph is meant to be a very general class to store mixed edge graph data. These edges can be named whatever, and can also correspond to whatever. However, the fundamental causal graphs: ADMG, CPDAG, PAG have considerably more structure than just arbitrary mixed edge graph data. The edges and absence of edges mean something very specific. The MixedEdgeGraph is too loose of an abstraction imo. It's good as a base class to enable future research of causal graphs that would allow for arbitrary mixed edge graphs.

To be explicit, here is a list of things that I still believe would not work / scale well with making everything a function of MixedEdgeGraphs:

1. Runtime errors and mistakes due to misnaming causal graphs: graph = MixedEdgeGraph(edge_list, edge_type_names=['bi-directed']). Completely valid in networkx, but invalid for any causal algorithms.
2. Checking with mypy: You mean to pass the ADMG, but instead passed say a PAG: graph = MixedEdgeGraph(edge_list, edge_type_names=['circle']) and then admg_function(graph). There can end up being a silent runtime error that you can't check with mypy, or any other method.
3. Error checking the modification of a graph: Say someone constructs a PAG in their own script using MixedEdgeGraph semantics. When they pass in this "PAG" to pag_functions(graph), the PAG needs to double check all edges and the structure of the PAG every single time to ensure that the PAG is a valid PAG. On the other hand, a PAG class can have cheap conditionals that check only once the validity of the PAG. Then when you pass this PAG class to any valid PAG functions, you can be sure the answer is sound.

You could make everything a method, but that doesn't scale. You'd add more and more methods to that class every time you discover new scientific methods.

I want to clarify I definitely am not advaocating for adding everything into the class. I think our principle should just follow something along the lines of "separation of responsibility".

The class should be strict exposure of the underlying data structure that i) limits user cognitive load and ii) limits bugs / mistakes. I think functions should be everything else. With that being said, requiring users to write: graph.add_edge('x', 'y', 'bidirected') is in my experience very error-prone compared to graph.add_bidirected_edge('x', 'y'). Presumably graph.add_edge('x', 'y', 'bidirectedd') will work w/o a runtime error, and then so will graph.add_edge('x', 'y', 'bi-directed').

A nice benefit would obviously be that NetworkX folks have already expressed willingness to include such a class natively in NetworkX, whereas they were not in favor of adding many new graph types.

Yes we will definitely add MixedEdgeGraph if networkx takes it, regardless of whether or not we provide explicit class implementations of the causal graphs.

Sorry that this message is so long. Heh. I think the topic is simple, but definitely the design choices have intricate complexities/tradeoffs for future work.

[adam2392]

I guess another thing I thought of is the idea of Linear models. Something that should be in there by default are weights. This technically can be done w/ the MixedEdgeGraph API, but to require a user to keep track of those things seems unnecessary.

I agree this design idea can't be incorporated into something like networkx, which AIMS to be sort of a generic platform. But for us, we are aiming to be a causal-specific-graph platform, so it makes sense to explicitly support certain causal graph abstractions. While of course keeping in mind that we should not over bloat the classes.

[petergtz]

@adam2392 Let me give you a more thorough response when I've got more time, but overall, your proposal is reasonable. No serious concerns anymore. Let me unblock you here, so you can more forward 👍.