[Python] Python Generators and Multiprocessing Pool.map: Inconsistent Results with NetworkX...

I'm working with a large NetworkX graph (71,590 nodes, 178,463 edges) and need to identify potential links between subgraphs based on the similarity of names stored as node attributes.

My initial graph is quickly constructed, and each node has an identifier and a list of names. I aim to analyze subgraphs grouped by country, searching for edges between subgraphs where the similarity of names (using a partial_match function) exceeds 92%. If a match is found, I want to create an edge between the first nodes of the two subgraphs.

My first implementation used itertools.product and set to compare names directly, which worked correctly but became memory-intensive for larger graphs. To address this, I switched to generators to process the names, hoping to reduce memory usage.

Original code :

def multiprocess_sub_graphs(graph):
countries = set(node[1] for node in graph.nodes())
tasks = []

for country in countries:
nodes_of_country = [node for node in graph.nodes() if node[1] == country]
sub_graphs_names = [graph.subgraph(c).copy() for c in
sorted(connected_components(graph.subgraph(nodes_of_country)), key=len)]
subgraph_combinations = combinations(sub_graphs_names, 2)

for combo in subgraph_combinations:
tasks.append((combo[0], combo[1]))

with Pool() as pool:
result_edges = pool.map(process_sub_graphs, tasks)

return [x for x in result_edges if x is not None]


And :

def process_sub_graphs(args):
subgraph1, subgraph2 = args

names_a = set()
nodes_1 = [node for node in subgraph1.nodes(data=True)]
for node1 in nodes_1:
names_a.update(node1[1]['all_names'])

names_b = set()
nodes_2 = [node for node in subgraph2.nodes(data=True)]
for node2 in nodes_2:
names_b.update(node2[1]['all_names'])

for first_name, second_name in itertools.product(names_a, names_b):
if partial_match(first_name, second_name) > 92:
node_source = list(subgraph1.nodes())[0]
node_dist = list(subgraph2.nodes())[0]
# Return an edge between the first nodes of each subgraph
return (node_source, node_dist)

return None


Code with Generators :

def extract_names_with_generator(subgraph):
for node, attributes in subgraph.nodes(data=True):
all_names = attributes.get('all_names', [])
for name in all_names:
yield name


def process_sub_graphs_with_generator(args):
subgraph1, subgraph2 = args

names_a = extract_names_with_generator(subgraph1)
names_b = extract_names_with_generator(subgraph2)

node_source = next(iter(subgraph1.nodes()))
node_dest = next(iter(subgraph2.nodes()))

for first_name in names_a:
for second_name in names_b:
score = partial_match(first_name, second_name)
if score > 92:
print(f"Match: {first_name} vs {second_name} ({score})")
return (node_source, node_dest)

return None


However, I'm observing inconsistent results: the number of new edges detected varies between executions, even with the same input graph.

My questions are:

How do Python generators behave when used within a multiprocessing Pool.map function? Could the inconsistent results be related to how generators are handled in this context?

Are there any other optimization strategies I could consider to improve performance and ensure consistent results, particularly for very large graphs?

Continue reading...