Graph Matching with Topological Features

Practical Session 1.4: Enhanced Graph Matching Using Graph Embeddings

Introduction

In our previous session, we explored basic graph matching using spatial coordinates and the Hungarian Algorithm. While this approach provides a foundation for matching keypoints between images, it only considers geometric distances. In this session, we'll enhance our matching by incorporating topological features using node2vec and commute times embeddings.

Theoretical Background

Node2vec

Node2vec is an algorithmic framework for learning continuous feature representations for nodes in networks. It maps nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes. The key advantages are:

• Captures structural equivalence and homophily
• Flexible random walk strategy
• Scalable to large networks

Commute Times Embedding

The commute time between two nodes is the expected number of steps a random walker takes to go from one node to the other and return. Commute times embedding:

• Provides a robust measure of node similarity
• Is less sensitive to small perturbations in graph structure
• Captures global graph properties

Enhanced Matching Algorithm

We'll modify our previous approach by:

1. Computing node embeddings using both node2vec and commute times
2. Creating a combined similarity matrix using both spatial and topological features
3. Applying the Hungarian Algorithm to find optimal matches

Exercise 1: Implement Node2vec Embedding

import networkx as nx
from node2vec import Node2Vec
import numpy as np

def create_graph_from_keypoints(keypoints, adj_matrix):
    """
    Create a NetworkX graph from keypoints and adjacency matrix
    
    Args:
        keypoints: Array of shape (N, 2) containing keypoint coordinates
        adj_matrix: Binary adjacency matrix of shape (N, N)
    
    Returns:
        G: NetworkX graph with node attributes
    """
    G = nx.from_numpy_array(adj_matrix)
    
    # Add spatial coordinates as node attributes
    for i in range(len(keypoints)):
        G.nodes[i]['pos'] = keypoints[i]
    
    return G

def compute_node2vec_embeddings(G, dimensions=128, walk_length=30, num_walks=200):
    """
    Compute node2vec embeddings for the graph
    
    Args:
        G: NetworkX graph
        dimensions: Embedding dimension
        walk_length: Length of each random walk
        num_walks: Number of random walks per node
    
    Returns:
        embeddings: Dictionary mapping node IDs to their embeddings
    """
    # Initialize node2vec model
    node2vec = Node2Vec(
        G,
        dimensions=dimensions,
        walk_length=walk_length,
        num_walks=num_walks,
        workers=4
    )
    
    # Train the model
    model = node2vec.fit(window=10, min_count=1)
    
    # Get embeddings
    embeddings = {node: model.wv[str(node)] for node in G.nodes()}
    
    return embeddings

Exercise 2: Implement Commute Times Embedding

def compute_commute_times_embedding(adj_matrix, dim=128):
    """
    Compute commute times embedding
    
    Args:
        adj_matrix: Adjacency matrix
        dim: Number of dimensions for the embedding
    
    Returns:
        embedding: Matrix of shape (N, dim) containing node embeddings
    """
    # Compute the graph Laplacian
    D = np.diag(np.sum(adj_matrix, axis=1))
    L = D - adj_matrix
    
    # Compute eigenvalues and eigenvectors of the Laplacian
    eigenvals, eigenvecs = np.linalg.eigh(L)
    
    # Remove the first eigenvalue/eigenvector (corresponding to constant function)
    eigenvals = eigenvals[1:dim+1]
    eigenvecs = eigenvecs[:, 1:dim+1]
    
    # Scale eigenvectors by inverse square root of eigenvalues
    scaling = 1 / np.sqrt(eigenvals)
    embedding = eigenvecs * scaling
    
    return embedding

Exercise 3: Enhanced Graph Matching

def enhanced_spatial_matching(kpts1, kpts2, adj_matrix1, adj_matrix2):
    """
    Perform enhanced matching using both spatial and topological features
    
    Args:
        kpts1, kpts2: Arrays of keypoints
        adj_matrix1, adj_matrix2: Adjacency matrices
    
    Returns:
        matching: Binary matching matrix
    """
    # Create graphs
    G1 = create_graph_from_keypoints(kpts1, adj_matrix1)
    G2 = create_graph_from_keypoints(kpts2, adj_matrix2)
    
    # Compute embeddings
    node2vec_emb1 = compute_node2vec_embeddings(G1)
    node2vec_emb2 = compute_node2vec_embeddings(G2)
    
    commute_emb1 = compute_commute_times_embedding(adj_matrix1)
    commute_emb2 = compute_commute_times_embedding(adj_matrix2)
    
    # Create cost matrix combining different features
    n1, n2 = len(kpts1), len(kpts2)
    cost_matrix = np.zeros((n1, n2))
    
    for i in range(n1):
        for j in range(n2):
            # Spatial distance
            spatial_dist = np.linalg.norm(kpts1[i] - kpts2[j])
            
            # Node2vec similarity
            node2vec_dist = np.linalg.norm(
                node2vec_emb1[i] - node2vec_emb2[j]
            )
            
            # Commute times similarity
            commute_dist = np.linalg.norm(
                commute_emb1[i] - commute_emb2[j]
            )
            
            # Combine distances with weights
            cost_matrix[i,j] = (
                0.4 * spatial_dist +
                0.3 * node2vec_dist +
                0.3 * commute_dist
            )
    
    # Apply Hungarian algorithm
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    
    # Create matching matrix
    matching = np.zeros((n1, n2))
    matching[row_ind, col_ind] = 1
    
    return matching

Exercise 4: Evaluation and Comparison

Compare the results of the enhanced matching with the previous spatial-only matching:

def evaluate_matching_methods(image_pairs, categories):
    """
    Evaluate and compare different matching methods
    
    Args:
        image_pairs: List of image pair paths
        categories: List of category names
    
    Returns:
        results: DataFrame with evaluation metrics
    """
    results = []
    
    for category in categories:
        for img_pair in image_pairs[category]:
            # Load images and compute keypoints
            img1, img2, kpts1, kpts2 = load_and_preprocess_images(
                img_pair['img1'], 
                img_pair['img2'],
                img_pair['kpts1'],
                img_pair['kpts2']
            )
            
            # Compute adjacency matrices
            adj1 = delaunay_triangulation(kpts1)
            adj2 = delaunay_triangulation(kpts2)
            
            # Compute matchings
            spatial_matching = simple_spatial_matching(kpts1, kpts2)
            enhanced_matching = enhanced_spatial_matching(
                kpts1, kpts2, adj1, adj2
            )
            
            # Compute accuracies
            spatial_acc = compute_accuracy(spatial_matching, ground_truth)
            enhanced_acc = compute_accuracy(enhanced_matching, ground_truth)
            
            results.append({
                'Category': category,
                'Spatial_Accuracy': spatial_acc,
                'Enhanced_Accuracy': enhanced_acc
            })
    
    return pd.DataFrame(results)

Expected Outcomes

The enhanced matching should show improvements in several scenarios:

1. When objects have similar structure but different scales
2. When there are perspective transformations
3. When local appearance varies but global structure is preserved

Homework

1. Implement the enhanced matching algorithm using both node2vec and commute times embeddings
2. Compare the results with the previous spatial-only matching
3. Create visualizations showing the improvements
4. Write a brief report (max 2 pages) analyzing:
   • Accuracy improvements per category
   • Cases where topological features help most
   • Limitations of the enhanced approach

References

1. Grover, A., & Leskovec, J. (2016). node2vec: Scalable feature learning for networks
2. Lovász, L. (1993). Random walks on graphs: A survey
3. Kuhn, H. W. (1955). The Hungarian method for the assignment problem