1 Fundamental concepts

Graph matching refers to methods for identifying correspondences between elements of two graphs. These elements may include vertices, edges, or larger substructures such as paths, cycles, or neighborhoods. In many settings, the goal is to align one graph with another so that their structural organization is as similar as possible.

The field draws on ideas from discrete mathematics, optimization, and machine learning. It is used when data can be naturally represented as networks or relational structures, and when comparisons must account for both attribute information and connectivity patterns.

1.1 Graphs and graph representations

A graph is a mathematical structure consisting of vertices connected by edges. Depending on the application, graphs may be directed or undirected, weighted or unweighted, simple or multigraphs, and may carry labels or attributes on vertices and edges. These choices affect how matching is defined and computed.

Graphs can be represented in several ways, including adjacency matrices, incidence matrices, edge lists, and neighborhood lists. Matrix representations are especially useful for optimization and spectral methods, while list-based forms are often convenient for sparse graphs and algorithmic traversal.

1.2 Vertex, edge, and subgraph correspondence

Graph matching may focus on vertex-to-vertex correspondence, edge-to-edge correspondence, or the alignment of entire subgraphs. Vertex correspondence identifies which node in one graph corresponds to a node in another graph. Edge correspondence requires that relationships between matched vertices be preserved or approximately preserved.

Subgraph correspondence is useful when one graph contains a smaller pattern embedded within a larger structure. In such cases, the task may be to locate a coherent region that resembles a target graph, rather than to match every element exactly.

1.3 Similarity and dissimilarity measures

Matching depends on a measure of similarity or dissimilarity between graph elements. These measures may compare labels, geometric positions, connectivity patterns, degrees, or local neighborhoods. In weighted graphs, edge weights often contribute directly to similarity scores.

A similarity measure assigns higher values to more compatible elements, whereas a dissimilarity measure expresses cost or distance. Many algorithms convert one form into the other through simple transformations, then optimize for maximum similarity or minimum cost.

1.4 Exact versus approximate matching

Exact matching seeks a correspondence that satisfies strict structural constraints, such as identical adjacency relations. This includes classical graph isomorphism and subgraph isomorphism. Exact methods are valuable when structural preservation is essential, but they can be computationally demanding.

Approximate matching allows deviations from perfect correspondence. This is especially important in noisy data, incomplete observations, and real-world networks where perfect structural equality is rare. Approximate methods typically balance multiple criteria, such as preserving local neighborhoods while tolerating missing or extra vertices.

2 Mathematical formulation

Graph matching is commonly framed as an optimization problem. A candidate correspondence is represented in a formal way, and an objective function scores how well the match preserves structure and attributes. The result may be a discrete assignment or a relaxed continuous solution that is later rounded to a valid mapping.

2.1 Graph isomorphism

Graph isomorphism asks whether two graphs are identical up to relabeling of vertices. If such a relabeling exists, the graphs have the same structure even though their vertex names differ. This problem is central to exact graph matching and serves as a baseline for more flexible formulations.

In matrix terms, two graphs with adjacency matrices A and B are isomorphic if there exists a permutation matrix P such that A = PBPᵀ, or an equivalent relation depending on convention. The existence of such a matrix indicates a one-to-one structural correspondence.

2.2 Subgraph isomorphism

Subgraph isomorphism concerns whether one graph contains a subgraph that matches another graph exactly. Unlike full isomorphism, the smaller graph need not cover every vertex of the larger one. This makes the problem particularly relevant for motif detection, object recognition, and pattern retrieval.

Because the candidate subgraph may be embedded in many possible ways, subgraph isomorphism is typically more difficult than full graph isomorphism. Algorithms often rely on pruning rules, backtracking, or constraint propagation to reduce the search space.

2.3 Assignment and permutation matrices

A matching between two vertex sets is often encoded by an assignment matrix. Each entry indicates whether a vertex in one graph is matched to a vertex in the other graph. When the matching is one-to-one, the matrix is constrained so that each vertex is used at most once.

Permutation matrices are a special case in which every row and column contains exactly one selected entry. They provide a compact representation of exact relabelings and are widely used in formulations of graph isomorphism and quadratic assignment.

2.4 Objective functions

Objective functions quantify the quality of a proposed match. They may combine multiple terms that reward consistent structure, encourage similar node attributes, and impose penalties for violations of constraints. The precise balance depends on the task and the data.

Such objectives are often nonconvex and combinatorial, making them difficult to solve exactly for large graphs. As a result, many practical methods relax the original problem or use approximations to obtain usable solutions.

2.4.1 Edge consistency terms

Edge consistency terms measure whether matched vertices preserve adjacency relationships. If two vertices are matched, their neighboring vertices should ideally also match in a way that reflects corresponding edges. This term captures the structural coherence of the proposed alignment.

In weighted settings, edge consistency may compare edge weights or geometric distances. Strong consistency is especially important when the graph structure carries the main signal, as in shape matching or certain network alignment tasks.

2.4.2 Node similarity terms

Node similarity terms compare the attributes of candidate vertex pairs. Attributes can include labels, feature vectors, spatial coordinates, or semantic descriptors. These terms are useful when vertices have rich metadata that helps disambiguate correspondences.

In many applications, node similarity provides a strong initial cue that guides the structural matching process. It can also stabilize the solution when the graph topology alone is insufficient to determine a unique alignment.

2.4.3 Regularization and constraints

Regularization controls the complexity or smoothness of the matching solution. It may discourage overly dense assignments, unstable mappings, or extreme sensitivity to noise. Constraints ensure that the solution respects the intended type of correspondence, such as one-to-one matching or partial matching.

Common constraints include exclusivity conditions, cardinality limits, and consistency requirements across related matches. In relaxed formulations, penalties may replace hard constraints to make the optimization more tractable.

3 Types of graph matching

Graph matching can be classified according to the structure of the correspondence and the relationship between the graphs. Different problem types require different representations and algorithms, and the chosen type strongly influences computational difficulty.

3.1 One-to-one matching

One-to-one matching pairs each element of one graph with at most one element of the other graph. This is the most familiar form of correspondence and is closely related to permutation-based formulations. It is common when the graphs represent comparable objects of similar size.

This type of matching is used when a direct alignment is desired, such as matching two shapes or aligning two labeled networks. It is often easier to interpret than more flexible matching schemes.

3.2 One-to-many and many-to-many matching

One-to-many and many-to-many matching allow a single element in one graph to correspond to multiple elements in the other graph, or vice versa. These models are useful when the graphs have different granularities or when an object is naturally decomposed into parts and subparts.

Such correspondences are more flexible but also more ambiguous. They are often used in hierarchical matching, coarse-to-fine alignment, and applications where exact vertex identity is not meaningful.

3.3 Bipartite graph matching

Bipartite graph matching models the problem as matching vertices across two disjoint sets, with edges representing compatibility between candidate pairs. This formulation is common in assignment problems and can be solved or approximated using classical matching techniques in bipartite graphs.

The bipartite view is useful because it separates compatibility scoring from structural consistency. It often serves as a first stage before additional constraints are applied to enforce graph-level coherence.

3.4 Quadratic assignment formulations

Quadratic assignment formulations capture the fact that matching two vertices affects the compatibility of their incident edges. The objective therefore contains quadratic terms involving pairs of assignment variables, which makes the problem expressive but difficult to solve.

This framework is widely used for graph matching because it naturally encodes both node and edge relationships. Many later methods can be understood as different ways of approximating or optimizing the quadratic assignment problem.

4 Algorithms

Graph matching algorithms range from exhaustive exact search to heuristic approximations. The best choice depends on graph size, data quality, and whether the application demands exact structural agreement or only a good approximate alignment.

4.1 Exhaustive and brute-force methods

Exhaustive methods inspect all possible correspondences or a very large subset of them. They are conceptually straightforward and can guarantee exact answers for small graphs. However, their runtime grows rapidly with graph size, making them impractical for most real-world problems.

Brute-force approaches are mainly useful as theoretical baselines or for very small instances. They are often combined with pruning rules that eliminate clearly invalid candidates early in the search.

4.2 Spectral methods

Spectral methods use eigenvalues and eigenvectors of matrices associated with the graphs, such as adjacency or Laplacian matrices. The underlying idea is that global structural information is reflected in spectral signatures, which can guide correspondence estimation.

These methods are often fast and robust, especially when used as initialization for more refined optimization steps. They are particularly attractive for large sparse graphs.

4.2.1 Eigenvector-based matching

Eigenvector-based matching compares spectral coordinates derived from the graphs. Vertices with similar positions in the spectral embedding are treated as likely matches. This approach can capture global structure that is not apparent from local neighborhoods alone.

Because eigenvectors may be sensitive to symmetry and numerical instability, practical methods often use several components together rather than relying on a single vector. Additional normalization is also common.

4.2.2 Relaxation techniques

Relaxation techniques replace discrete constraints with continuous ones that are easier to optimize. After solving the relaxed problem, a rounding step converts the result into a valid discrete matching. This strategy trades exactness for computational efficiency.

Relaxations are widely used because the original matching problem is typically NP-hard. They provide a practical compromise between tractability and fidelity to the original objective.

4.3 Probabilistic methods

Probabilistic methods treat graph matching as inference under uncertainty. Instead of producing a single deterministic answer at the outset, they estimate the likelihood of different correspondences. This perspective is useful when observations are noisy or incomplete.

Such methods can incorporate prior knowledge about expected structures or matching patterns. They are often applied in settings where uncertainty quantification is important.

4.3.1 Bayesian approaches

Bayesian approaches model the matching problem using prior distributions and likelihood functions. The posterior distribution then describes the probability of each correspondence given the observed graphs. This framework naturally accommodates uncertainty and latent variables.

Bayesian graph matching can integrate heterogeneous evidence, such as structural consistency, label agreement, and measurement noise. The main challenge is computational, since posterior inference may be expensive.

4.3.2 Randomized algorithms

Randomized algorithms introduce stochastic choices to explore the space of possible matchings. They may be used to escape poor local optima, sample candidate correspondences, or estimate robust solutions through repeated trials. Randomization can improve practical performance when deterministic search is too rigid.

These methods are especially useful in large-scale settings where exact optimization is infeasible. They often provide good approximate answers with manageable computational cost.

4.4 Optimization-based methods

Optimization-based methods formulate graph matching as a mathematical program and then solve or approximate it using established optimization tools. The formulation may be linear, quadratic, or higher-order depending on the complexity of the structural constraints.

These methods are favored for their clear objective functions and flexibility in incorporating multiple sources of information. Their performance depends on the quality of the relaxation and the effectiveness of the solver.

4.4.1 Linear programming approaches

Linear programming approaches express the matching problem with linear constraints and a linear objective, often after relaxation of discrete variables. This can yield efficient optimization procedures and useful bounds on the optimal value. The solution may then be projected onto a valid assignment.

Linear programming is particularly effective when the graph matching task is augmented by additional constraints that preserve linearity. It also provides a foundation for branch-and-bound and cutting-plane strategies.

4.4.2 Semidefinite programming approaches

Semidefinite programming approaches relax the matching problem into a matrix optimization problem with semidefinite constraints. These relaxations can be stronger than simpler linear ones, offering improved approximation quality in some cases. They are mathematically elegant and often provide good theoretical guarantees.

The drawback is that semidefinite programs may be expensive to solve at large scale. Consequently, they are often used for moderate-sized instances or as part of a broader approximation framework.

4.4.3 Gradient-based methods

Gradient-based methods optimize a continuous surrogate objective using derivatives or subgradients. They are widely used in modern large-scale settings because they can exploit efficient numerical routines and hardware acceleration. The continuous solution is usually transformed into a discrete match afterward.

These methods work best when the objective is smooth or has been smoothed through relaxation. They can be combined with regularization and constraints to improve convergence behavior.

4.5 Heuristic and approximate algorithms

Heuristic algorithms aim for good practical solutions without guaranteeing optimality. They are often faster than exact methods and can handle graphs of substantial size. Their design typically reflects the structure of the target application.

Approximate methods are essential in many real data settings, where strict exactness is less important than speed and robustness. They often serve as initializers for more expensive refinement procedures.

4.5.1 Greedy matching

Greedy matching builds a correspondence step by step, selecting the locally best available pair at each stage. This approach is simple and efficient, and it may work well when similarity scores are informative and conflicts are limited.

Its main limitation is that early decisions can constrain later choices in suboptimal ways. For that reason, greedy matching is often paired with backtracking or local correction.

Local search begins with an initial correspondence and improves it through small modifications such as swaps, insertions, or reassignments. It can escape some of the weaknesses of greedy methods by revisiting earlier choices. The quality of the final result depends strongly on the starting point and neighborhood design.

Local search is popular because it is easy to implement and can yield strong results in practice. It is often combined with other heuristics or used as a polishing step after a coarse alignment.

4.5.3 Branch and bound

Branch and bound systematically explores the space of possible matchings while using bounds to eliminate regions that cannot contain an optimal solution. It is an exact method in principle, but its performance depends on the strength of the bounds and the structure of the instance.

For hard graph matching problems, branch and bound can still become expensive. Nevertheless, it remains valuable for small to medium-sized cases where exactness matters.

5 Applications

Graph matching appears in many fields where objects can be represented as relational structures. Its applications often involve comparing shapes, recognizing patterns, aligning biological networks, or identifying corresponding entities across datasets.

5.1 Computer vision and image analysis

In computer vision, graphs can represent parts of an image, keypoints, contours, or object components. Graph matching helps compare these structures across images despite changes in viewpoint, scale, or partial occlusion. It is a common tool in recognition and registration tasks.

The structural information encoded by graphs complements pixel-based methods. This makes graph matching useful when local appearance alone is not sufficient to identify an object or scene.

5.1.1 Object recognition

Object recognition uses graph matching to identify known objects by comparing observed feature relationships with stored templates. Vertices may correspond to detected landmarks, and edges may capture relative distances or angles. The method is effective when objects have distinctive internal structure.

This approach is especially valuable for objects that can appear in different poses or be partially hidden. Matching relationships among parts often provides stronger evidence than matching individual features independently.

5.1.2 Shape matching

Shape matching compares the structural form of two shapes, often represented by boundary graphs, skeletons, or landmark networks. The goal is to determine whether the shapes are similar under transformations such as rotation, translation, or deformation.

Graph-based methods are useful because they can encode both local geometry and global arrangement. They are commonly applied in recognition, retrieval, and registration of visual forms.

5.2 Pattern recognition and machine learning

Graph matching supports pattern recognition by providing a way to compare structured examples. In machine learning, it may be used for classification, clustering, prototype matching, and structured prediction. Graph representations are helpful when the relevant information lies in relationships rather than in fixed-length feature vectors.

The approach is particularly useful for irregular data, such as molecule structures, scene graphs, and relational observations. It can also be integrated with learned similarity measures or neural feature extractors.

5.3 Bioinformatics and cheminformatics

In bioinformatics, graphs may represent protein interaction networks, molecular structures, or biological pathways. Graph matching can help identify analogous substructures, compare interaction patterns, or align networks across organisms. In cheminformatics, molecular graphs are compared to detect similar compounds or functional groups.

These applications rely on both topology and node or edge labels, such as atom types or interaction strengths. The ability to handle partial similarity is especially important, since biologically relevant structures are often related but not identical.

5.4 Social and information networks

Graph matching is used to compare social or information networks, where vertices represent individuals, accounts, pages, or entities and edges represent relationships. It can assist in aligning different datasets, identifying common substructures, or tracking corresponding nodes across snapshots.

In information networks, matching may help compare citation graphs, hyperlink structures, or communication patterns. The emphasis is often on preserving relational patterns rather than exact identity.

5.5 Document and scene matching

Documents and scenes can be represented as graphs of layout elements, regions, or semantic components. Matching helps compare page structures, align scene descriptions, or locate corresponding objects in complex environments. This is useful in retrieval, document analysis, and multimodal interpretation.

Graph representations are advantageous when spatial arrangement and compositional relations are important. They can summarize structure more compactly than raw text or image data.

6 Evaluation and performance

Evaluating graph matching methods requires attention to both correspondence quality and computational cost. Different applications emphasize different aspects, such as exactness, stability under noise, or runtime on large instances.

6.1 Accuracy metrics

Accuracy may be measured by the number of correctly matched vertices, edge preservation rates, objective score, or overlap with a known ground truth. In partial matching tasks, precision and recall can be informative. Some applications also assess downstream performance, such as recognition accuracy.

The choice of metric should reflect the problem setting. A method that performs well on exact structural agreement may not be optimal when approximate similarity is the true goal.

6.2 Computational complexity

Graph matching problems are often computationally hard, with many formulations belonging to classes of problems that are difficult to solve exactly at scale. Complexity increases rapidly with graph size, density, and the number of allowable correspondences.

Because of this difficulty, many methods rely on approximation, relaxation, or heuristic search. Complexity analysis is therefore a central part of algorithm design and comparison.

6.3 Robustness to noise and missing data

Real-world graphs frequently contain errors, missing vertices, spurious edges, or imperfect labels. Robust graph matching methods aim to preserve useful correspondences despite such imperfections. This often requires tolerance to structural deviations and flexible scoring.

Robustness is especially important in applications such as biological networks, computer vision, and social data, where observations are rarely complete or exact. Methods that rely too heavily on strict equality may fail under these conditions.

6.4 Scalability considerations

Scalability refers to a method’s ability to handle larger graphs without prohibitive growth in runtime or memory use. Sparse representations, decomposition strategies, and approximate solvers are common tools for improving scalability.

In practice, a scalable method may sacrifice some optimality in exchange for faster execution. This trade-off is often acceptable when the graphs are large or when many matchings must be computed repeatedly.

7 Variants and extensions

Graph matching has many variants that extend the basic two-graph correspondence problem. These extensions reflect richer data, temporal change, higher-order relations, or the need to compare multiple graphs at once.

7.1 Attributed graph matching

Attributed graph matching incorporates node and edge attributes into the correspondence process. Attributes may include labels, colors, descriptors, or numeric features. These values help distinguish otherwise similar structural configurations.

This variant is widely used when the graph topology alone does not determine a unique alignment. By combining attributes with structure, it often improves both accuracy and interpretability.

7.2 Dynamic graph matching

Dynamic graph matching addresses graphs that change over time. The task may involve tracking correspondences across snapshots, following evolving communities, or comparing temporal patterns. Consistency over time is often as important as structural similarity at any single moment.

These problems arise in sequence analysis, video understanding, and evolving network data. Effective methods must account for both change and continuity.

7.3 Hypergraph matching

Hypergraph matching generalizes ordinary graph matching to hypergraphs, where a hyperedge can connect more than two vertices. This allows the representation of higher-order relationships that cannot be captured by pairwise edges alone. The added expressiveness is useful in vision, chemistry, and structured data analysis.

Because hyperedges increase the complexity of correspondence, hypergraph matching is usually more computationally demanding. Many algorithms therefore rely on relaxed or tensor-based formulations.

7.4 Multi-graph matching

Multi-graph matching seeks consistent correspondences across three or more graphs. Instead of aligning one pair at a time, the objective is to maintain global consistency across the entire collection. This is important when multiple observations of related objects are available.

The challenge is to avoid contradictions that can arise when pairwise matches are optimized independently. Global coordination often improves coherence but also increases computational complexity.

7.5 Graph edit distance

Graph edit distance measures the minimum cost required to transform one graph into another through operations such as insertion, deletion, and substitution of vertices or edges. It provides a flexible way to quantify similarity even when graphs differ in size or structure.

This concept is closely related to approximate graph matching, since a low edit distance indicates that two graphs are similar under a small number of changes. Computing the exact distance is often difficult, so approximations are common.

Graph matching is part of a broader family of methods for comparing structured data and optimizing discrete correspondences. Several related areas share algorithms, objectives, and applications, though they emphasize different aspects of similarity or alignment.

8.1 Graph similarity

Graph similarity is the broader notion of how alike two graphs are, regardless of whether an explicit correspondence is produced. Graph matching often serves as a mechanism for measuring similarity by constructing or optimizing a mapping between elements.

Similarity measures can be structural, attribute-based, or a combination of both. In practice, matching and similarity estimation are often tightly linked.

8.2 Network alignment

Network alignment focuses on finding correspondence between nodes in different networks, often with an emphasis on preserving functional or relational roles. It is common in biology, sociology, and information systems. The term is frequently used when the graphs represent large relational datasets rather than abstract mathematical objects.

Although closely related to graph matching, network alignment may place more emphasis on cross-network comparability and global structural consistency.

8.3 Pattern matching

Pattern matching is a general process of identifying occurrences of a template within data. Graph matching is a structured form of pattern matching in which the template and data are both relational. This link makes graph matching relevant to recognition and retrieval tasks across many domains.

The distinction becomes important when the pattern is defined by relationships among parts rather than by linear sequences or fixed feature arrays.

8.4 Combinatorial optimization

Combinatorial optimization studies problems in which the goal is to choose the best solution from a discrete set. Graph matching is a classic example, since candidate correspondences are combinatorial objects and the objective is typically nonconvex. Many techniques from this field, including relaxation, branch and bound, and heuristic search, are directly applicable.

The connection to combinatorial optimization explains much of the algorithmic complexity of graph matching and also accounts for the diversity of methods developed to address it.