寻求Python实现的图匹配算法：无标签节点拓扑/属性匹配需求

Hey there, let's break down how to solve this graph matching problem in Python—since you know there's a one-to-one node mapping but no shared labels, we can leverage topology and node properties with these practical tools and approaches:

NetworkX has a battle-tested isomorphism submodule that lets you combine topological checks with custom node property matching. It's perfect if you want a no-fuss, well-documented solution.

Here's a working example tailored to your scenario:

import networkx as nx
from networkx.algorithms.isomorphism import GraphMatcher

# Build two sample graphs with unique node labels but matching properties/topology
G1 = nx.Graph()
G1.add_nodes_from([1, 2, 3], color=["red", "blue", "green"])
G1.add_edges_from([(1, 2), (2, 3)])

G2 = nx.Graph()
G2.add_nodes_from(["X", "Y", "Z"], color=["blue", "red", "green"])
G2.add_edges_from([("X", "Z"), ("Z", "Y")])

# Define a matcher that checks if node 'color' properties match
node_matcher = lambda n1_attr, n2_attr: n1_attr['color'] == n2_attr['color']

# Initialize the GraphMatcher with our node property rule
graph_matcher = GraphMatcher(G1, G2, node_match=node_matcher)

# Since you know a bijection exists, grab the first valid mapping
if graph_matcher.is_isomorphic():
    node_mapping = next(graph_matcher.isomorphisms_iter())
    print("Found node mapping:", node_mapping)
    # Output example: {1: 'Y', 2: 'X', 3: 'Z'}

If you need more advanced algorithms (like VF2, Ullman, or subgraph matching), GMatch4py is a dedicated library built for these tasks. It's lightweight and focuses specifically on graph matching logic.

Example usage:

import gmatch4py as gm
import networkx as nx

# Reuse our sample graphs from above
G1 = nx.Graph()
G1.add_nodes_from([1, 2, 3], color=[0, 1, 2])  # Use numerical properties for easier matching
G1.add_edges_from([(1, 2), (2, 3)])

G2 = nx.Graph()
G2.add_nodes_from(["X", "Y", "Z"], color=[1, 0, 2])
G2.add_edges_from([("X", "Z"), ("Z", "Y")])

# Initialize the VF2 algorithm with node attribute matching
vf2_matcher = gm.VF2()

# Check isomorphism and get the mapping
if vf2_matcher.is_isomorphic(G1, G2, node_attr=['color']):
    node_mapping = vf2_matcher.get_mapping(G1, G2, node_attr=['color'])
    print("Found node mapping:", node_mapping)

If you want to combine multiple features (like node degree, neighbor property distributions, or custom attributes), you can generate node embeddings and use the Hungarian algorithm to find the optimal bijection.

Here's a simplified approach:

import numpy as np
from scipy.optimize import linear_sum_assignment
import networkx as nx

def generate_node_features(graph):
    """Create a feature vector for each node: [degree, color_value]"""
    features = []
    for node, attrs in graph.nodes(data=True):
        degree = graph.degree(node)
        # Convert categorical color to numerical for distance calculation
        color_map = {"red": 0, "blue": 1, "green": 2}
        color_val = color_map[attrs['color']]
        features.append([degree, color_val])
    return np.array(features)

# Get features for both graphs
G1_features = generate_node_features(G1)
G2_features = generate_node_features(G2)

# Create a cost matrix where each entry is the distance between two node features
cost_matrix = np.linalg.norm(G1_features[:, np.newaxis] - G2_features, axis=2)

# Use Hungarian algorithm to find the minimal cost bijection
row_indices, col_indices = linear_sum_assignment(cost_matrix)

# Map nodes from G1 to G2
G1_nodes = list(G1.nodes())
G2_nodes = list(G2.nodes())
node_mapping = {G1_nodes[i]: G2_nodes[j] for i, j in zip(row_indices, col_indices)}
print("Found node mapping:", node_mapping)

Quick Notes: #

• If your node properties are categorical, convert them to numerical values (like in the custom example) before running matching algorithms.
• For large graphs, topology-only algorithms like VF2 might be slow—embedding-based methods (like the custom approach) scale better.
• Since you confirmed a one-to-one mapping exists, you don't have to handle cases where no isomorphism is found.

内容的提问来源于stack exchange，提问作者Targaryel