Problems with Networkx optimal_edit_paths (graph edit distance)

I'm using Networkx to find the graph edit distance (GED) between two directed acyclic graphs (DAGs) via the Reconcile method shown below, for the purpose of tree reconciliation. I map nodes and edges by their labels, which are (as shown) just their IDs.

In the test case below, I copy a graph g1 to g2 and add n new nodes/edges to g2 then remove m nodes/edges. Even in the case of n = several hundred, the Reconcile method is very fast when m = 0. However, my problem is that it becomes very slow if I remove more than 2 or 3 nodes that would otherwise be common to both graphs.

import networkx as nx

class MyGraph(nx.DiGraph):

    @classmethod
    def Reconcile(cls, a1, a2):

    # ---------------------------------------------------------------------
    # STAGE 1: MAP NODES/EDGES B/T THE TWO GRAPHSS

    # Equality here means having same labels

        def return_eq(item1, item2):

            label1 = item1['label']
            label2 = item2['label']

            _eq = label1 == label2

            if _eq:
                print('Mapped ', label1, 'to ', label2)

            return _eq


        # ---------------------------------------------------------------------
        # STAGE 2: FIND EDIT PATHS

        paths, cost_nx = nx.optimal_edit_paths(a1, a2, node_match = return_eq, edge_match = return_eq)
        paths = paths[0]

        node_edits = [el for el in paths[0] if el[0] != el[1]]
        edge_edits = [el for el in paths[1] if el[0] != el[1]]
        cost = len(node_edits) + len(edge_edits)

        print('Node edits: {}\nEdge edits: {}\nTotal cost (Networkx): {}\nTotal cost (no. of edits): {}'.format(
            node_edits, edge_edits, cost_nx, cost))
        print('No. of node edits: ', len(node_edits))
        print('No. of edge edits: ', len(edge_edits))

        return paths, cost_nx, cost, node_edits, edge_edits

#######################################################

g1 = MyGraph()

p = 10
edges = [('root', edge) for edge in range(p)]
g1.add_edges_from(edges) # Add root and some nodes + edges

g2 = g1.copy()

n = 10
for edge in range(n):
    node = 100*(edge+10)
    print('Edge added: ', edge)
    g2.add_edge('root2', node) # Add some more edges + nodes not present in g1

m = 2 # When m > 2, code slows massively
for node in list(g1.nodes)[-m:]: # Any will do!
    print('Node/edge removed:', node)
    g2.remove_node(node)

for g in [g1,g2]:
    for node in g.nodes:
        g.nodes[node]['label'] = node
    for edge in g.edges:
        g.edges[edge]['label'] = edge

paths, cost_nx, cost, node_edits, edge_edits = MyGraph.Reconcile(g1,g2)

I may be missing something here, and it may be that the problem is simply a computational one: I realise it's a hard problem and I'm absolutely not suggesting there's a bug in Networkx. However, any help or insight would be much appreciated, for example by preconditioning the graphs in some way before attemping to reconcile them.