DOCSEARCHbyAlgolia
Submit Docs

pygmtools (Python Graph Matching Tools)

repository·main·Indexed 43 days ago

https://github.com/thinklab-sjtu/pygmtools

A backend-agnostic toolkit for graph matching solvers, ranging from traditional combinatorial methods to deep learning-based approaches. It supports multiple numerical backends including NumPy, PyTorch, Jittor, PaddlePaddle, TensorFlow, and MindSpore. The library provides a unified API for two-graph matching (linear and quadratic assignment), multi-graph matching, and neural graph matching solvers such as NGM, PCA-GM, and GENN-A*.

Tokens
53K
Snippets
194
Records
226
Agent score
49%

What's inside pygmtools

  1. Overview of pygmtools modules

    main

    The pygmtools library is organized into several specialized modules for graph matching tasks:

    • linear_solvers: Solvers based on linear programming or linear algebraic approaches.
    • classic_solvers: Traditional graph matching algorithms.
    • multi_graph_solvers: Solvers designed for matching across multiple graphs.
    • neural_solvers: Deep learning-based graph matching solvers.
    • utils: General utility functions.
    • benchmark: Tools for evaluating graph matching performance.
    • dataset: Utilities for handling graph matching datasets.

  2. Perform Multi-Graph Matching

    main

    Multi-graph matching involves jointly matching more than two graphs. This example demonstrates how to use the numpy backend to perform this task using classic solvers.

    Available solvers mentioned in this context include:

    • pygmtools.classic_solvers.rrwm (classic solver)
    • pygmtools.multi_graph_solvers.cao (classic solver)
    • pygmtools.multi_graph_solvers.mgm_floyd (classic solver)

  3. Understand the Graph Matching Benchmark module

    main

    The Benchmark module in pygmtools provides a unified data interface and an evaluating platform to compare deep graph matching algorithms across different datasets and experimental settings. It handles data fetching from processed JSON files and provides tools for evaluating prediction results using standard metrics.

    Key components include:

    • dataset.py: Contains dataset classes for automatic downloading, processing into JSON, and splitting into training/testing sets.
    • benchmark.py: Contains the Benchmark class for data retrieval and evaluation.
    • dataset_config.py: Stores default settings such as dataset paths and class definitions.

  4. Calculate matching consistency

    main

    Consistency in multi-graph matching refers to the property that matching results between multiple graphs should be transitive. For a set of matching matrices $X$ of shape $(m, m, n, n)$, the consistency of a pair $(i, j)$ is calculated by comparing the direct match $X_{ij}$ with the composition of matches through all other intermediate graphs $k$: $X_{ik}X_{kj}$.

    Users can use get_batch_pc_opt(X) to compute a consistency matrix of shape $(m, m)$ for all pairs in a batch efficiently using batch matrix multiplication (bmm).

    # X is a tensor of shape (m, m, n, n)
# Returns a consistency matrix of shape (m, m)
pair_con = get_batch_pc_opt(X)

  5. Understand the Graph Matching Pipeline

    main

    A standard graph matching problem is formulated as a Quadratic Assignment Problem (QAP). Solving a real-world problem typically involves three distinct parts:

    1. Feature Extraction: Extract node and edge features from the input graphs. These features are used to measure similarity.
    2. Affinity Matrix Construction: Build an affinity matrix $\mathbf{K}$ from the extracted features. This matrix encodes both node-wise affinities (diagonal elements) and edge-wise affinities (off-diagonal elements).
    3. QAP Problem Solving: Solve the resulting QAP using a Graph Matching (GM) solver to find the permutation matrix $\mathbf{X}$, which encodes the node-to-node correspondence.

    pygmtools is designed to handle Part 2 (Affinity Matrix Construction) and Part 3 (QAP Problem Solving).

  6. Calculate accuracy, consistency, and affinity for graph matching

    main

    When evaluating graph matching results, three primary metrics are used:

    1. Accuracy: Measures how close the predicted matching matrix is to the ground truth matching matrix. It is calculated by comparing the predicted and ground truth matrices, often accounting for outliers.
    2. Consistency (Pairwise Consistency): Measures how well the matching results across different pairs of graphs satisfy the transitivity property (i.e., if $A$ matches $B$ and $B$ matches $C$, then $A$ should match $C$).
    3. Affinity: Measures the quadratic affinity score of the predicted matching $X$ relative to the ground truth affinity $X_{gt}$ and the affinity matrix $K$.

    Functions used for these calculations include cal_accuracy, cal_consistency, and cal_affinity.

    # Evaluating matching results
# mat: predicted matching matrices (m, m, n, n)
# gt_mat: ground truth matching matrices (m, m, n, n)
# affinity_mat: the affinity matrix K used for the problem
# m: number of graphs
# n: number of nodes

acc, src, con = eval(mat, gt_mat, affinity_mat, m, n)

  7. Available Backends for pygmtools

    main

    The library supports multiple backends with a consistent API. While numpy is the default (CPU only), deep learning backends provide GPU support and are designed to be gradient-friendly and support batched operations.

    Supported backends:

    • Numpy (Default, CPU)
    • PyTorch (GPU, Deep Learning friendly)
    • Jittor (GPU, JIT support)
    • PaddlePaddle (GPU, Deep Learning friendly)
    • Tensorflow (GPU, Deep Learning friendly)
    • MindSpore (GPU, Deep Learning friendly)

    To use a specific backend, you must install it following its official instructions.

  8. Build graph structures from keypoints using Delaunay triangulation

    main

    In deep graph matching, graph structures are often built based on the geometric arrangement of keypoints. A common method is using Delaunay triangulation to define edges between keypoints.

    To implement this, you can use scipy.spatial.Delaunay to find simplices and then construct an adjacency matrix A where A[i, j] = 1 if keypoints i and j share an edge in the triangulation.

    import torch
import scipy.spatial as spa
import itertools

def delaunay_triangulation(kpt):
    # kpt shape: [2, N]
    d = spa.Delaunay(kpt.numpy().transpose())
    A = torch.zeros(len(kpt[0]), len(kpt[0]))
    for simplex in d.simplices:
        for pair in itertools.permutations(simplex, 2):
            A[pair] = 1
    return A

A1 = delaunay_triangulation(kpts1)
A2 = delaunay_triangulation(kpts2)

  9. Calculate accuracy, consistency, and affinity for matching results

    main

    When evaluating multi-graph matching results, three metrics are commonly used:

    1. Accuracy (cal_accuracy): Measures how close the predicted matching matrix is to the ground truth matching matrix, often accounting for outliers.
    2. Consistency (cal_consistency): Measures the transitivity of the matching. For a set of matchings $X$, it checks if the composition of matchings $X_{ik}$ and $X_{kj}$ is consistent with the direct matching $X_{ij}$.
    3. Affinity (cal_affinity): Measures the quadratic assignment score of the predicted matching relative to the ground truth matching using the affinity matrix $K$.

    These metrics help quantify both the correctness of individual pairs and the global coherence of the multi-graph matching set.

  10. Fuse models based on matching results

    main

    Once a matching solution (permutation matrix) is obtained, you can fuse two networks by aligning the weights of the first network to match the second, and then performing a weighted average.

    Fusion Proportion: The fusion_proportion parameter determines the contribution of the second model.

    • fused_model = (1 - fusion_proportion) * aligned_model1 + fusion_proportion * model2
    • Example: fusion_proportion=0.2 results in 80% model1 and 20% model2.

    Alignment Logic:

    • For Convolutional layers (4D tensors): The weights are permuted using the matching matrix to align channels.
    • For Linear/Bias layers (2D/1D tensors): The weights are multiplied by the permutation matrix.
    • The alignment must account for the specific shape of the weights (e.g., permuting dimensions in (out_channels, in_channels, h, w) for convolutions).
    def align(solution, fusion_proportion, networks: list, params: list):
    # ... (logic to permute aligned_wt_0 using 'solution' permutation matrix) ...
    
    averaged_weights = []
    for idx, parameter in enumerate(networks[1].parameters()):
        # Weighted average of aligned model 1 and model 2
        averaged_weights.append((1 - fusion_proportion) * aligned_wt_0[idx] + fusion_proportion * parameter)
    return averaged_weights

  11. Build affinity matrices for Multi-Graph Matching

    main

    In multi-graph matching, the first step is to construct an affinity matrix $\mathbf{K}$ for every pair of graphs in the set. This matrix represents the compatibility between nodes of graph $i$ and graph $j$. The provided example demonstrates a formulation based on the Quadratic Assignment Problem (QAP), where affinity is derived from geometric features (edge lengths and angles) and adjacency information.

    To implement this, you typically:

    1. Extract features (e.g., get_feature) for each graph.
    2. Compute pairwise affinities (e.g., get_pair_affinity) between all pairs $(i, j)$ using these features.
    3. Aggregate these into a large affinity tensor (e.g., generate_affinity_matrix) that can be passed to solvers.
    # Conceptual workflow for building affinity matrices
# 1. Generate features for each graph
# 2. Compute pairwise affinity for all graph pairs (i, j)
# 3. Reshape into a format suitable for solvers (e.g., (m, m, n*n, n*n))

affinity_mat = generate_affinity_matrix(n_kpts_list, kpts_list, adj_list)

  12. Evaluate Multi-Graph Matching results

    main

    When performing multi-graph matching, you can evaluate the quality of the matching matrices using three metrics: Accuracy, Affinity, and Consistency.

    • Accuracy: Measures how close the predicted matching matrix is to the ground truth matrix, typically by comparing elements after accounting for outliers.
    • Affinity: Measures the objective function value (the QAP score) achieved by the matching compared to the ground truth.
    • Consistency: Measures how well the matching results across different pairs of graphs satisfy the transitivity property (i.e., if $X_{ij}$ is the match between $i$ and $j$, then $X_{ij} \approx X_{ik}X_{kj}$).

    In the provided example, these are computed via an eval(mat, gt_mat, affinity, m, n) function which aggregates these metrics across all $m^2$ pairs.