API reference

Public API

gasm.match(G1, G2, *, platform='GPU', attributes=None, vertex_matrices=None, edge_matrices=None, structure=True, complement=True, lap='auto', noise=1e-10, convergence='adaptive', tol=1e-06, patience=2, max_iterations=None, normalize=True, match_on='vertices', return_scores=False, seed=None)[source]

Match two graphs with the GASM algorithm.

Parameters:

  • G1 – The two graphs to match, as networkx.Graph or networkx.DiGraph. Both must share the same directedness.

  • G2 – The two graphs to match, as networkx.Graph or networkx.DiGraph. Both must share the same directedness.

  • platform (str) – 'GPU' (default) runs on OpenCL, falling back to the CPU with a warning when no device is available; 'CPU' forces the reference implementation.

  • attributes – None for a purely structural matching, or a list of gasm.Attribute (or equivalent dicts) describing the vertex and edge attributes to use, each with its uncertainty rho.

  • vertex_matrices – Optional precomputed vertex similarity matrix of shape (nA, nB), or a sequence of such matrices, injected directly as extra Hadamard factors of the vertex distance matrix V (eq. 9). Rows follow the G1 node order, columns the G2 node order. Values must lie in [0, 1] and are clipped otherwise.

  • edge_matrices – Optional precomputed edge similarity matrix of shape (mA, mB), or a sequence of such matrices, injected directly as extra Hadamard factors of the edge distance matrix E (eq. 10). Rows follow the G1 edge order, columns the G2 edge order. Values must lie in [0, 1] and are clipped otherwise.

  • structure (bool) – When False, ignore the graph structure and match on attributes only.

  • complement (bool) – Allow the complement procedure (eq. 18 / 26) for dense graphs. False always uses the original incidence matrices.

  • lap (str) – Linear assignment solver: 'auto', 'jv' (Jonker-Volgenant) or 'auction'.

  • noise (float) – Amplitude eta of the symmetry-lifting noise (eq. 11). 0 disables it.

  • convergence (str) – 'adaptive' (early stopping) or 'diameter' (fixed number of iterations, eq. 30).

  • tol (float) – Parameters of the adaptive convergence criterion.

  • patience (int) – Parameters of the adaptive convergence criterion.

  • max_iterations (int | None) – Hard cap on the number of iterations; defaults to min(diam_A, diam_B) (eq. 30).

  • normalize (bool) – Apply the approximate normalization fx = 4 dA dB + 1 (eq. S2).

  • match_on (str) – 'vertices' (match on the vertex score matrix X) or 'edges' (match on the edge score matrix Y).

  • return_scores (bool) – For the GPU platform, transfer the score matrix immediately instead of lazily. Ignored on the CPU, where scores are always available.

  • seed (int | None) – Seed for the noise generator, for reproducible matchings.

Returns:

The matching result.

Return type:

Matching

class gasm.Matching(labels_a, labels_b, rows, cols, match_on='vertices', score_matrix=None, score_loader=None)[source]

Result of a graph matching.

A matching associates vertices (or edges) of graph A with vertices (or edges) of graph B. The full score matrix is transferred from the GPU lazily: accessing score, scores or score_matrix triggers a single device-to-host transfer that is then cached.

Parameters:

  • labels_a – Ordered labels of the matched elements of each graph (vertices or edges), indexed by the internal integer indices.

  • labels_b – Ordered labels of the matched elements of each graph (vertices or edges), indexed by the internal integer indices.

  • rows – Assignment index arrays: internal index rows[k] of A is matched with internal index cols[k] of B.

  • cols – Assignment index arrays: internal index rows[k] of A is matched with internal index cols[k] of B.

  • match_on (str) – 'vertices' or 'edges'.

  • score_matrix (np.ndarray | None) – The dense score matrix, if already available on the host (CPU path).

  • score_loader (Callable[[], np.ndarray] | None) – Callable returning the dense score matrix, used for lazy GPU transfer.

property matchups: list[tuple]

List of (a, b) matched pairs using original labels.

matchup_A(nodes=None)[source]

Matchups keyed by elements of A.

Parameters:

nodes – If None, return the full {a: b} dict. If a single label, return its match. If an iterable of labels, return the list of matches.

matchup_B(nodes=None)[source]

Matchups keyed by elements of B (see matchup_A()).

property score_matrix: ndarray

The full dense score matrix (lazily transferred from the device).

property scores: ndarray

Per-matchup scores as a NumPy array (lazily transferred).

property score: float

Global matching score (sum of per-matchup scores, lazily transferred).

accuracy(ground_truth)[source]

Accuracy gamma against a ground truth (see gasm.accuracy()).

Return type:

float

structural_quality(G1, G2)[source]

Structural quality qS (see gasm.structural_quality()).

Return type:

float

class gasm.Attribute(name, on, kind='measurable', rho='auto')[source]

Specification of a graph attribute used for matching.

Parameters:

  • name (str) – Key under which the attribute is stored in the networkx node or edge data dictionaries.

  • on (Literal['vertex', 'edge']) – 'vertex' or 'edge'.

  • kind (Literal['measurable', 'categorical']) – 'measurable' (a distance can be defined, eq. 8) or 'categorical' (only equality is meaningful, eq. 6-7).

  • rho (float | str) – Uncertainty over the attribute values. A non-negative float, or 'auto' to use the standard deviation of all pairwise comparisons as a safe upper bound.

gasm.accuracy(matching, ground_truth)[source]

Accuracy gamma of a matching against a ground truth (Section 2.2).

Parameters:

  • matching – A gasm.matching.Matching, or any iterable of (a, b) pairs.

  • ground_truth – Mapping {a: b} of the true correspondence, or an iterable of (a, b) pairs.

Returns:

Proportion of matched pairs that agree with the ground truth.

Return type:

float

gasm.structural_quality(G1, G2, matching)[source]

Structural quality qS of a matching (eq. 3).

Parameters:

  • G1 – The two networkx graphs that were matched.

  • G2 – The two networkx graphs that were matched.

  • matching – A gasm.matching.Matching, or any iterable of (a, b) pairs.

Returns:

qS in [0, 1]; higher is a better structural match. Returns 0 when both graphs have no edge.

Return type:

float

Graphs

Internal graph representation for GASM.

Converts a networkx.Graph or networkx.DiGraph into the sparse incidence structures used by the iterative procedure, following the notations of Candelier, Graph Matching Based on Similarities in Structure and Attributes, JGAA 29(1) 289-320 (2025).

Notations

  • Undirected graphs use the unoriented incidence matrix R (eq. 14), of shape n x m: each column is an edge with two non-zero entries (one for a self-loop).

  • Directed graphs use the source-edge matrix S and terminus-edge matrix T (eq. 24-25), both of shape n x m.

class gasm.graph.Graph(nodes, directed, n, m, mu, edges, adjacency, degree, isolated, R=None, S=None, T=None, _node_index=None, _raw_node_data=None, _raw_edge_data=None)[source]

Sparse, GASM-ready view of a networkx graph.

Parameters:
nodes

Ordered list of the original networkx node labels. The position in this list is the internal integer index used by all matrices.

Type:

list

directed

Whether the graph is directed.

Type:

bool

n, m, mu

Number of vertices, edges and self-loops.

edges

Ordered list of (u, v) edges (original labels), one per column of the incidence matrices.

Type:

list

R

Unoriented incidence matrix (n x m), CSR. None for directed graphs.

Type:

scipy.sparse._csr.csr_matrix | None

S, T

Source-edge and terminus-edge matrices (n x m), CSR. None for undirected graphs.

adjacency

Sparse adjacency matrix Lambda (n x n), CSR.

Type:

scipy.sparse._csr.csr_matrix

degree

Vertex degree (out-degree for directed graphs), as a dense vector.

Type:

numpy.ndarray

isolated

Boolean mask of isolated vertices (degree 0, ignoring self-loops).

Type:

numpy.ndarray

property node_index: dict

Mapping from original node label to internal integer index.

property mean_degree: float

Average degree (out-degree for directed graphs).

complement_incidence()[source]

Return the incidence matrices of the complement graph.

For undirected graphs returns (R_bar, None, None); for directed graphs returns (None, S_bar, T_bar). Self-loops are complemented as well (a vertex without a self-loop in G has one in G_bar).

gasm.graph.from_networkx(graph)[source]

Build a Graph from a networkx graph.

Parameters:

graph (Graph) – A networkx.Graph or networkx.DiGraph. Multigraphs are not supported.

Return type:

Graph

gasm.graph.diameter(graph)[source]

Return the graph diameter as the largest finite shortest-path distance.

This robustly handles disconnected graphs by ignoring unreachable pairs, and directed graphs by using directed shortest paths (eq. 30).

Parameters:

graph (Graph)

Return type:

int

gasm.graph.use_complement(ga, gb)[source]

Decide whether to use graph complements (eq. 18 / eq. 26).

Undirected: complement when 4(mA + mB) > nA(nA+1) + nB(nB+1). Directed: complement when 2(mA + mB) > nA^2 + nB^2.

Parameters:
Return type:

bool

Attributes

Attribute handling for GASM (Section 3.2 of the reference article).

Builds the vertex distance matrix V (eq. 9) and edge distance matrix E (eq. 10) from user-specified attributes, each with an uncertainty parameter rho. Categorical attributes use eq. (6)-(7); measurable attributes use eq. (8).

gasm.attributes.build_matrices(specs, ga, gb, vertex_matrices=None, edge_matrices=None)[source]

Build the vertex (V) and edge (E) distance matrices.

Parameters:

  • specs – Iterable of Attribute or dict specifications, or None.

  • ga (Graph) – The two graphs being matched.

  • gb (Graph) – The two graphs being matched.

  • vertex_matrices – Optional precomputed vertex similarity matrix of shape (nA, nB), or a sequence of such matrices, injected directly as extra Hadamard factors of V (eq. 9). Rows follow the ga node order, columns the gb node order. Values must lie in [0, 1] and are clipped otherwise.

  • edge_matrices – Optional precomputed edge similarity matrix of shape (mA, mB), or a sequence of such matrices, injected directly as extra Hadamard factors of E (eq. 10). Rows follow the ga edge order, columns the gb edge order. Values must lie in [0, 1] and are clipped otherwise.

Returns:

  • V – Vertex distance matrix of shape (nA, nB) (eq. 9). All-ones when no vertex attribute is specified.

  • E – Edge distance matrix of shape (mA, mB) (eq. 10). All-ones when no edge attribute is specified.

Metrics

Matching quality and accuracy metrics (Section 2 of the reference article).

gasm.metrics.structural_quality(G1, G2, matching)[source]

Structural quality qS of a matching (eq. 3).

Parameters:

  • G1 – The two networkx graphs that were matched.

  • G2 – The two networkx graphs that were matched.

  • matching – A gasm.matching.Matching, or any iterable of (a, b) pairs.

Returns:

qS in [0, 1]; higher is a better structural match. Returns 0 when both graphs have no edge.

Return type:

float

gasm.metrics.accuracy(matching, ground_truth)[source]

Accuracy gamma of a matching against a ground truth (Section 2.2).

Parameters:

  • matching – A gasm.matching.Matching, or any iterable of (a, b) pairs.

  • ground_truth – Mapping {a: b} of the true correspondence, or an iterable of (a, b) pairs.

Returns:

Proportion of matched pairs that agree with the ground truth.

Return type:

float

Convergence

Convergence criteria for the GASM iterative procedure.

The reference article (eq. 30) fixes the number of iterations to k_tilde = min(diam_A, diam_B). Supp. Fig. S3 shows the accuracy usually plateaus well before that bound, so this module also provides an adaptive early-stop criterion that monitors the stabilisation of the row-wise argmax assignment – a cheap surrogate for the final LAP that avoids running the LAP at every iteration – capped by the diameter for safety.

class gasm.convergence.ConvergenceMonitor(mode='adaptive', diameter_cap=1, max_iterations=None, tol=1e-06, patience=2, floor=2)[source]

Track convergence of the vertex score matrix across iterations.

Parameters:

  • mode (str) – 'adaptive' (default) for early stopping, or 'diameter' to reproduce the fixed-iteration behaviour of the article.

  • diameter_cap (int) – Hard upper bound on the number of iterations k_tilde (eq. 30).

  • max_iterations (int | None) – Optional manual override of the hard cap.

  • tol (float) – Relative Frobenius-norm tolerance for the early-stop criterion.

  • patience (int) – Number of consecutive iterations with an unchanged argmax assignment required to declare convergence.

  • floor (int) – Minimum number of iterations before early stopping is allowed.

property max_steps: int

Maximum number of update iterations that will be performed.

update(k, X)[source]

Register iteration k and return True if iteration should stop.

Parameters:

  • k (int) – Current iteration index (>= 1).

  • X (ndarray) – Current vertex score matrix.

Return type:

bool

Linear assignment solvers

Linear Assignment Problem (LAP) solver registry.

GASM ends with a LAP on the converged vertex (or edge) score matrix, searching for a maximum-score assignment. Solvers are registered by name so that new ones can be added without touching the rest of the code base. The lap argument of gasm.match() selects one of them, 'auto' picking the best available solver for the active platform.

Currently available:

  • 'jv': Jonker-Volgenant, via scipy.optimize.linear_sum_assignment() (CPU).

  • 'auction': Bertsekas auction algorithm with epsilon-scaling (native GPU implementation; falls back to a NumPy reference on CPU).

gasm.lap.register_cpu_solver(name, func)[source]

Register a CPU LAP solver under name.

Parameters:
Return type:

None

gasm.lap.get_cpu_solver(name)[source]

Return the CPU LAP solver registered under name.

'auto' resolves to the Jonker-Volgenant solver.

Parameters:

name (str)

Return type:

Callable

gasm.lap.available()[source]

List the registered CPU LAP solver names.

Return type:

list[str]

Jonker-Volgenant LAP solver (CPU), via SciPy.

scipy.optimize.linear_sum_assignment() implements the rectangular shortest-augmenting-path algorithm of Crouse (2016), a Jonker-Volgenant variant, in polynomial time.

gasm.lap.jv.solve(score)[source]

Return a maximum-score assignment of rows to columns.

Parameters:

score (ndarray) – Dense score matrix of shape (nA, nB); higher is better.

Returns:

Index arrays such that row rows[k] is assigned to column cols[k]. The assignment has size min(nA, nB).

Return type:

rows, cols

Bertsekas auction algorithm with epsilon-scaling (CPU reference).

This is a NumPy reference implementation, used as a CPU fallback and to validate the native OpenCL auction kernel. With epsilon-scaling the auction converges to an optimal assignment (identical total score to Jonker-Volgenant); the GASM noise term lifts ties so both solvers return the same matching. For production CPU use prefer the 'jv' solver, which is considerably faster in pure Python.

gasm.lap.auction.solve(score)[source]

Return a maximum-score assignment of rows to columns.

Parameters:

score (ndarray) – Dense score matrix of shape (nA, nB); higher is better.

Returns:

Index arrays of the assignment, of size min(nA, nB).

Return type:

rows, cols

CPU back-end

CPU implementation of the GASM iterative procedure (eq. 15-31).

This is the reference implementation, faithful to Candelier (JGAA 29(1), 2025). It uses dense NumPy score matrices with sparse incidence multiplications and is the platform used when platform='CPU' or when no OpenCL device is available.

gasm.cpu.core.run(ga, gb, V, E, *, structure=True, complement=True, noise=1e-10, convergence='adaptive', tol=1e-06, patience=2, max_iterations=None, normalize=True, match_on='vertices', seed=None)[source]

Run the GASM iterations on the CPU.

Returns:

  • score_matrix – The converged score matrix the LAP should be run on: the vertex score matrix X (match_on='vertices') or the edge score matrix Y (match_on='edges').

  • labels_a, labels_b – Labels of the rows and columns of score_matrix (node labels for vertices, (u, v) edge tuples for edges).

  • iterations – Number of iterations actually performed.

Parameters:

GPU back-end

GPU (OpenCL/pyopencl) implementation of the GASM iterations.

The expensive part of GASM is the repeated sparse-times-dense products of the iteration equations (eq. 16-17 / 28-29). This back-end runs them on the device in single precision, using CSR incidence matrices and the kernels in kernels/gasm.cl. Initialization, isolated-vertex restoration (eq. 31) and the final LAP are performed on the host.

Importing this module requires pyopencl and at least one usable OpenCL device; otherwise an exception is raised and gasm.match() falls back to the CPU back-end.

gasm.gpu.core.run(ga, gb, V, E, *, lap='auto', return_scores=False, structure=True, complement=True, noise=1e-10, convergence='adaptive', tol=1e-06, patience=2, max_iterations=None, normalize=True, match_on='vertices', seed=None)[source]

Run the GASM iterations on the GPU.

Returns the converged vertex score matrix on the host (float64), the row and column labels, the number of iterations performed, and None (no lazy device loader is used in this version; the score matrix is materialised for the host LAP).

Warnings

Internal utilities: warnings and validation helpers for GASM.

exception gasm.utils.GASMWarning[source]

Base class for all warnings emitted by GASM.

exception gasm.utils.PlatformWarning[source]

Emitted when the requested compute platform is unavailable.

exception gasm.utils.AttributeWarning[source]

Emitted when attribute specifications are inconsistent with the graphs.

exception gasm.utils.ConvergenceWarning[source]

Emitted when the iterative procedure may not have converged.

gasm.utils.warn(message, category=<class 'gasm.utils.GASMWarning'>)[source]

Emit a GASM warning with a controlled stack level.

Parameters:
Return type:

None