Hubbry Logo
Graph matchingGraph matchingMain
Open search
Graph matching
Community hub
Graph matching
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Graph matching
Graph matching
Graph matching
View on Wikipedia
from Wikipedia

Graph matching is the problem of finding a similarity between graphs.[1]

Graphs are commonly used to encode structural information in many fields, including computer vision and pattern recognition, and graph matching is an important tool in these areas.[2] In these areas it is commonly assumed that the comparison is between the data graph and the model graph.

The case of exact graph matching is known as the graph isomorphism problem.[1] The problem of exact matching of a graph to a part of another graph is called subgraph isomorphism problem.

Inexact graph matching refers to matching problems when exact matching is impossible, e.g., when the number of vertices in the two graphs are different. In this case it is required to find the best possible match. For example, in image recognition applications, the results of image segmentation in image processing typically produces data graphs with the numbers of vertices much larger than in the model graphs data expected to match against. In the case of attributed graphs, even if the numbers of vertices and edges are the same, the matching still may be only inexact.[1]

Two categories of search methods are the ones based on identification of possible and impossible pairings of vertices between the two graphs and methods that formulate graph matching as an optimization problem.[3] Graph edit distance is one of similarity measures suggested for graph matching.[4][5] The class of algorithms is called error-tolerant graph matching.[5]

See also

[edit]
Wikimedia Commons has media related to matching.

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Graph matching

View on Grokipedia
from Grokipedia
In , a matching is a set of edges in an undirected graph that have no vertices in common, also known as an independent edge set. That is, no two edges in the set are adjacent. A matching is called maximal if it cannot be extended by adding another edge, and maximum if it has the largest possible number of edges among all matchings in the graph. A is one in which every vertex is incident to exactly one edge in the matching. The problem of finding maximum matchings is central to and can be solved in polynomial time, though the complexity varies between bipartite and general graphs. In bipartite graphs, algorithms such as the or the efficiently compute maximum matchings, with applications to assignment problems like job scheduling and the stable marriage problem. For general graphs, Edmonds' blossom algorithm provides a solution. Matchings also arise in network flow problems and , with extensions to weighted graphs where the goal is to maximize total edge weights.

Basic Concepts

Definition of a Matching

Graph matching involves finding a correspondence between the vertices of two graphs G=(VG,EG)G = (V_G, E_G) and H=(VH,EH)H = (V_H, E_H) that preserves their structural properties, such as adjacency, to the greatest extent possible. A matching MM is typically represented as an injective mapping ϕ:S⊆VG→VH\phi: S \subseteq V_G \to V_H, where SS is the set of matched vertices in GG, such that for edges in GG, the images under ϕ\phi are edges in HH (for exact matching) or approximately so (for inexact matching). Exact graph matching requires a preserving all adjacencies, equivalent to when ∣VG∣=∣VH∣|V_G| = |V_H|. Inexact matching allows partial mappings or tolerances for errors, often formulated to minimize a cost function measuring structural disagreements. A vertex v∈VGv \in V_G is said to be matched (or saturated) by the matching MM if there exists ϕ(v)∈VH\phi(v) \in V_H; otherwise, it is unmatched (or exposed). The matched vertices in HH are the images under ϕ\phi, while unmatched vertices in either graph remain without correspondence. For example, consider two identical path graphs P3P_3 with vertices {a,b,c}\{a, b, c\} and edges {ab,bc}\{ab, bc\} for both GG and HH. A ϕ={a↦a′,b↦b′,c↦c′}\phi = \{a \mapsto a', b \mapsto b', c \mapsto c'\} (preserving labels for simplicity) saturates all vertices and preserves structure exactly. In contrast, for G=P3G = P_3 and HH a cycle C4C_4 with vertices {1,2,3,4}\{1,2,3,4\} and edges {12,23,34,41}\{12,23,34,41\}, a partial matching ϕ={a↦1,b↦2}\phi = \{a \mapsto 1, b \mapsto 2\} might match the path segment, leaving cc and vertices 3,4 unmatched, illustrating inexact or partial alignment. Standard notation denotes a graph matching by MM, with ∣M∣|M| representing its size, the number of vertex correspondences. The problem often arises in attributed graphs, where node/edge labels add similarity constraints.

Size and Cardinality

The cardinality of a graph matching MM between graphs GG and HH is the number of vertex correspondences, denoted ∣M∣|M|. This measures the extent of alignment between the graphs. A matching is maximum if it has the largest possible cardinality among all matchings, preserving structure as much as possible; the size of such a maximum matching is denoted ν(G,H)\nu(G, H). A perfect matching is a bijective correspondence that saturates every vertex in VGV_G and VHV_H (requiring ∣VG∣=∣VH∣|V_G| = |V_H|), fully preserving adjacency relations—equivalent to graph isomorphism. In this case, ν(G,H)=∣VG∣\nu(G, H) = |V_G|. If no perfect matching exists, a maximum matching may leave some vertices unmatched. For graphs of equal size with odd ∣VG∣|V_G|, perfect matchings are impossible, but near-perfect matchings may exist, leaving exactly one vertex unmatched in each graph. The deficiency of graphs GG and HH, denoted def(G,H)\mathrm{def}(G, H), is the total number of unmatched vertices in a maximum matching, given by def(G,H)=∣VG∣+∣VH∣−2ν(G,H)\mathrm{def}(G, H) = |V_G| + |V_H| - 2\nu(G, H) (assuming possible equal sizes). Thus, def(G,H)=0\mathrm{def}(G, H) = 0 a perfect matching exists. For example, consider two identical cycle graphs C4C_4 with vertices labeled 1-2-3-4-1; a ϕ\phi mapping vertices correspondingly has ∣M∣=4=ν(C4,C4′)|M| = 4 = \nu(C_4, C_4') and def(C4,C4′)=0\mathrm{def}(C_4, C_4') = 0. In contrast, for G=C3G = C_3 ( 1-2-3-1) and H=C3′H = C_3', a maximum matching might align two vertices and one edge, with ν(C3,C3′)=2\nu(C_3, C_3') = 2, def(C3,C3′)=2\mathrm{def}(C_3, C_3') = 2, leaving one vertex unmatched in each due to structural limits in approximate settings.

Bipartite Matching

Maximum Bipartite Matching

In a G=(U∪W,E)G = (U \cup W, E), the vertex set is partitioned into two disjoint independent sets UU and WW, such that every edge in EE connects a vertex from UU to a vertex from WW, with no edges incident to vertices within the same partition. The maximum bipartite matching problem involves finding a matching M⊆EM \subseteq E of maximum ∣M∣|M|, which saturates the largest possible number of vertices in GG while ensuring no two edges in MM share a common vertex. This problem is central to understanding the structural properties of bipartite graphs, as the size of such a maximum matching ν(G)\nu(G) quantifies the extent to which the graph can pair elements across the partitions without overlap. A key result characterizing the existence of a —a maximum matching that saturates every vertex in the smaller partition—is . Assuming ∣U∣≤∣W∣|U| \leq |W|, the GG admits a matching that covers all vertices in UU if and only if, for every S⊆US \subseteq U, the neighborhood N(S)N(S) (the set of vertices in WW adjacent to at least one vertex in SS) satisfies ∣N(S)∣≥∣S∣|N(S)| \geq |S|. This condition ensures that no of UU is "overloaded" relative to its connections in WW, providing a combinatorial criterion for perfect matchings. For illustration, consider a with partitions U={u1,u2,u3}U = \{u_1, u_2, u_3\} and W={w1,w2,w3}W = \{w_1, w_2, w_3\}, and edges u1−w1u_1-w_1, u1−w2u_1-w_2, u2−w2u_2-w_2, u3−w3u_3-w_3. Here, for every S⊆US \subseteq U, ∣N(S)∣≥∣S∣|N(S)| \geq |S| holds (e.g., S={u1,u2}S = \{u_1, u_2\} has N(S)={w1,w2}N(S) = \{w_1, w_2\}), allowing a of size 3, such as {u1−w1,u2−w2,u3−w3}\{u_1-w_1, u_2-w_2, u_3-w_3\}. In contrast, if the edges are u1−w1u_1-w_1, u2−w1u_2-w_1, u3−w2u_3-w_2, then for S={u1,u2}S = \{u_1, u_2\}, N(S)={w1}N(S) = \{w_1\} with ∣N(S)∣=1<2=∣S∣|N(S)| = 1 < 2 = |S|, violating Hall's condition; the maximum matching has size 2 (e.g., {u1−w1,u3−w2}\{u_1-w_1, u_3-w_2\}), leaving one vertex in UU unsaturated. In bipartite graphs, the size of the maximum matching ν(G)\nu(G) equals the size of the minimum vertex cover τ(G)\tau(G), a duality that underscores the balanced structure of these graphs and foreshadows deeper min-max theorems. This equality holds specifically for bipartite graphs, distinguishing them from general graphs where computing maximum matchings is more complex.

König's Theorem

König's theorem states that in a bipartite graph GG, the size of a maximum matching equals the size of a minimum vertex cover, denoted ν(G)=τ(G)\nu(G) = \tau(G), where ν(G)\nu(G) is the matching number and τ(G)\tau(G) is the vertex cover number. This min-max relation holds specifically for bipartite graphs, providing a duality between these two combinatorial structures. The theorem was proved by Hungarian mathematician Dénes Kőnig in 1931 as part of his foundational work on graph theory, building on earlier combinatorial insights into matrices and graphs. Kőnig's result, published in his paper "Graphs and matrices," established this equality and influenced subsequent developments in matching theory. A high-level proof proceeds by first noting that for any graph, ν(G)≤τ(G)\nu(G) \leq \tau(G), since each edge in a matching requires at least one distinct vertex in a cover. Equality in bipartite graphs is shown constructively: given a maximum matching MM, consider the directed graph where edges in MM point from one partite set to the other, and non-matching edges point oppositely. The vertices reachable from unmatched vertices in the first partite set via alternating paths (with respect to MM) form a set ZZ; then, the minimum vertex cover is (U∖Z)∪(V∩Z)(U \setminus Z) \cup (V \cap Z), where UU and VV are the partite sets, and its size equals ∣M∣|M|. This construction relies on the absence of augmenting paths in a maximum matching, ensuring no larger matching exists. This theorem implies that maximum matchings and minimum vertex covers in bipartite graphs can be computed in polynomial time, often via reductions to linear programming duality or network flows, highlighting the structural simplicity of bipartite graphs compared to general ones. For example, consider a bipartite graph with partite sets {a1,a2}\{a_1, a_2\} and {b1,b2,b3}\{b_1, b_2, b_3\}, and edges a1−b1a_1-b_1, a2−b2a_2-b_2. The maximum matching has size 2, covering both a1a_1 and a2a_2. A minimum vertex cover is {a1,a2}\{a_1, a_2\}, also of size 2, as selecting both aa vertices covers all edges, and no smaller set suffices.

General Graph Matching

Maximum Matching in General Graphs

In general undirected graphs G=(V,E)G = (V, E), which may contain odd-length cycles, a maximum matching is a set of edges without common vertices of largest possible cardinality ν(G)\nu(G). This formulation extends the bipartite case but encounters greater structural challenges, as potential augmenting paths relative to a current matching can form blossoms—odd cycles that complicate the search for larger matchings. Despite this added intricacy, computing a maximum matching in general graphs is solvable in polynomial time, as established by Edmonds' seminal algorithm running in O(∣V∣4)O(|V|^4) time (with subsequent improvements achieving O(∣V∣3)O(|V|^3)). In bipartite graphs, the problem admits simpler flow-based methods, but general graphs require handling non-trivial cycles to ensure optimality. A key theoretical result characterizing perfect matchings (where ν(G)=∣V∣/2\nu(G) = |V|/2) is Tutte's theorem: a graph GG has a perfect matching if and only if, for every subset S⊆VS \subseteq V, the number of odd components o(G−S)o(G - S) in the subgraph induced by V∖SV \setminus S satisfies o(G−S)≤∣S∣o(G - S) \leq |S|. This condition highlights barriers to perfect matchings arising from odd components after vertex removals, a phenomenon absent in bipartite graphs where Hall's theorem suffices. The size of a maximum matching admits a min-max structural description via the Berge-Tutte formula: \nu(G) = \frac{1}{2} \min_{S \subseteq V} \bigl( |V| + |S| - o(G - S) \bigr). $$ This formula generalizes Tutte's theorem by quantifying the deficiency caused by odd components, providing an exact cardinality without enumeration. For illustration, the Petersen graph—a 3-regular non-bipartite graph with 10 vertices—has $\nu(G) = 5$, admitting a [perfect matching](/page/Perfect_matching) that covers all vertices.[](https://mathworld.wolfram.com/PetersenGraph.html) In contrast, the triangle graph $K_3$ (3 vertices forming an odd cycle) violates Tutte's condition with $S = \emptyset$ since $o(G - S) = 1 > 0$, yielding $\nu(G) = 1$ with no perfect matching. ### [Edmonds' Blossom Algorithm](/page/Blossom_algorithm) Edmonds' Blossom Algorithm, developed by [Jack Edmonds](/page/Jack_Edmonds) in 1965, provides the first polynomial-time method for computing a [maximum cardinality matching](/page/Maximum_cardinality_matching) in general undirected graphs, addressing the challenges posed by odd cycles that prevent direct application of bipartite techniques. The algorithm builds on the concept of augmenting paths, similar to those in bipartite matching, but introduces a mechanism to handle "blossoms"—odd-length alternating cycles—by contracting them into supernodes during the search process. This allows the algorithm to find augmenting paths in the contracted graph, after which the contractions are reversed to update the original matching. The original implementation runs in $O(|V|^4)$ time, where $|V|$ is the number of vertices, while refined versions achieve $O(|V|^3)$.[](https://math.nist.gov/~JBernal/p_t_f.pdf)[](https://web.eecs.umich.edu/~pettie/matching/Blum-noblossoms-2015.pdf) The core innovation lies in the blossom structure and contraction: a blossom is an odd-length cycle in the graph consisting of alternating matched and unmatched edges relative to the current matching $M$, with exactly one vertex (the "tip" or base) connected to the rest of the search structure via an unmatched edge. When such a cycle is detected during the path search—typically via an edge linking two vertices already in the same alternating tree branch—the entire cycle is shrunk into a single supernode, preserving the alternating property and eliminating the cycle's interference. The search then proceeds in this reduced graph, treating the supernode as a single entity with combined incident edges. If an augmenting path is found involving the supernode, the blossom is later expanded by inserting the even-length alternating path from the blossom's base to its tip into the overall path.[](https://math.nist.gov/~JBernal/p_t_f.pdf)[](https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf) Key steps of the algorithm proceed iteratively as follows: begin with an arbitrary (possibly empty) matching $M$; while an unmatched vertex $u$ exists, construct an alternating [tree](/page/Tree) rooted at $u$ using breadth-first or [depth-first search](/page/Depth-first_search), labeling vertices as even or odd levels based on their distance in unmatched/matched edges and tracking parent pointers. During this growth, scan for edges to previously labeled vertices: an edge to an even-level vertex may form a blossom, which is immediately contracted; an edge to an odd-level vertex in a different tree branch may reveal an augmenting path. If no augmenting path or new blossoms are found after exhausting possibilities from $u$, declare the current $M$ maximum; otherwise, augment $M$ by [symmetric difference](/page/Symmetric_difference) with the path (flipping matched/unmatched edges along it), increasing $|M|$ by 1, and repeat. Each augmentation requires $O(|V|^2)$ time for the search in the worst case, leading to the overall complexity since there are at most $|V|/2$ augmentations.[](https://math.nist.gov/~JBernal/p_t_f.pdf)[](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f18/www/scribes/lecture06.pdf) In high-level pseudocode, the process can be outlined as: ``` function BlossomAlgorithm(G): M = empty matching while exists free vertex u in G relative to M: contracted_G, labels, blossoms = initialize_search(u, M) if find_augmenting_path_in_contracted(contracted_G, labels): augment M along expanded path else: break // No more augmenting paths return M function find_augmenting_path_in_contracted(G', labels): // Use BFS/DFS to grow alternating [forest](/page/Forest) // Detect and contract blossoms on-the-fly // Return path if free vertex reached, else null ``` This framework ensures termination with a maximum matching by Berge's lemma, as the absence of augmenting paths (even after blossom handling) certifies optimality.[](https://math.nist.gov/~JBernal/p_t_f.pdf)[](https://users.soe.ucsc.edu/~sesh/Teaching/2021/CSE202/Slides/lec2-blossom.pdf) For its foundational role in solving the maximum matching problem in general graphs—previously open beyond bipartite cases—the algorithm earned Edmonds the 1985 [John von Neumann Theory Prize](/page/John_von_Neumann_Theory_Prize) from the [Institute for Operations Research and the Management Sciences](/page/Institute_for_Operations_Research_and_the_Management_Sciences) (INFORMS).[](https://www.informs.org/Recognizing-Excellence/Award-Recipients/Jack-Edmonds) ## Weighted Graph Matching ### Weighted Bipartite Matching Weighted bipartite matching extends the unweighted case by assigning weights to edges, seeking a matching that maximizes the sum of these weights. Formally, given a [bipartite graph](/page/Bipartite_graph) $G = (U \cup V, E)$ with a weight function $w: E \to \mathbb{R}_{\geq 0}$, the objective is to find a matching $M \subseteq E$ that maximizes $\sum_{e \in M} w(e)$. This formulation assumes non-negative weights and is commonly known as the [assignment problem](/page/Assignment_problem) when $G$ is complete bipartite with $|U| = |V|$.[](https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109) The [Hungarian algorithm](/page/Hungarian_algorithm), introduced by [Harold W. Kuhn](/page/Harold_W._Kuhn) in 1955, solves this problem in $O(|V|^3)$ time. It operates through a primal-dual approach, iteratively constructing feasible labelings on vertices (dual variables or potentials) to ensure reduced costs are non-negative, identifying augmenting paths via shortest paths in a residual graph, and updating potentials to maintain feasibility while increasing the matching size until optimality. A variant, the Kuhn-Munkres algorithm refined in 1957, emphasizes potential adjustments for complete bipartite graphs, guaranteeing a perfect matching when possible by repeatedly finding minimum-cost augmenting paths.[](https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf)[](https://www.math.ucdavis.edu/~saito/data/emd/munkres.pdf) The problem admits a [linear programming](/page/Linear_programming) formulation whose relaxation yields [integer](/page/Integer) solutions due to the total unimodularity of the bipartite [incidence matrix](/page/Incidence_matrix). Specifically, the assignment [polytope](/page/Polytope), defined by degree constraints $\sum_{j} x_{ij} = 1$ for each $i \in U$, $\sum_{i} x_{ij} = 1$ for each $j \in V$, and $x_{ij} \geq 0$, has integral vertices, as established by the Hoffman-Kruskal theorem on totally unimodular matrices. Thus, solving the [LP](/page/Linear_programming) directly provides the optimal [integer](/page/Integer) matching. For illustration, consider a [complete bipartite graph](/page/Complete_bipartite_graph) $K_{3,3}$ with parts $A = \{a_1, a_2, a_3\}$ and $B = \{b_1, b_2, b_3\}$, and the following edge weights (to maximize): | | $b_1$ | $b_2$ | $b_3$ | |-----|---------|---------|---------| | $a_1$ | 5 | 3 | 4 | | $a_2$ | 2 | 6 | 5 | | $a_3$ | 4 | 4 | 4 | The optimal matching is $a_1$-$b_1$ (weight 5), $a_2$-$b_2$ (weight 6), $a_3$-$b_3$ (weight 4), with total weight 15. A suboptimal matching, such as $a_1$-$b_2$ (3), $a_2$-$b_3$ (5), $a_3$-$b_1$ (4), yields total weight 12. A special case is the bottleneck assignment problem, which seeks a [perfect matching](/page/Perfect_matching) maximizing the minimum edge weight in the matching (max-min objective). This variant can be solved in polynomial time using modifications to the [Hungarian algorithm](/page/Hungarian_algorithm), such as binary search over possible bottleneck values combined with feasibility checks via maximum matching.[](https://link.springer.com/article/10.1007/BF00933089) ### Weighted General Matching The weighted general matching problem seeks to find a matching $M$ in an undirected graph $G = (V, E)$ with edge weights $w: E \to \mathbb{R}$ that maximizes the total weight $\sum_{e \in M} w(e)$, where no two edges in $M$ share a vertex.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) This formulation generalizes the unweighted case (where all $w(e) = 1$) to arbitrary real weights, including negative values, though negative weights may lead to optimal matchings that exclude such edges unless they enable higher-weight alternatives.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) The problem is well-defined for general graphs, which may contain odd cycles, unlike the bipartite case. Jack Edmonds developed the foundational algorithm for this problem in 1965 as an extension of his [blossom algorithm](/page/Blossom_algorithm) for [maximum cardinality matching](/page/Maximum_cardinality_matching), incorporating dual variables (potentials) assigned to vertices to compute reduced costs for edges and guide the search for augmenting paths.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) The approach iteratively augments the matching by finding weighted alternating paths, shrinking blossoms (odd cycles in the auxiliary graph) when encountered, and adjusting vertex potentials to maintain non-negativity of reduced costs and ensure progress toward optimality.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) During blossom shrinking, potentials are updated to reflect the minimum reduced-weight path through the cycle, preventing negative-weight cycles from disrupting the augmentation process.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) From a polyhedral perspective, the weighted general matching problem corresponds to optimizing a linear function over the matching polytope, whose vertices are the incidence vectors of matchings and facets are described by non-negativity constraints, degree constraints ($\sum_{e \ni v} x_e \leq 1$ for each vertex $v$), and blossom inequalities ($\sum_{e \in E(S)} x_e \leq \frac{|S|-1}{2}$ for every odd-sized subset $S \subseteq V$ with $|S| \geq 3$).[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) This characterization, also due to Edmonds in 1965, proves the integrality of the polytope and enables linear programming-based solutions, with the primal-dual algorithm providing an implicit separation oracle for the inequalities.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) Consider a small general graph with vertices $A, B, C$ forming a [triangle](/page/Triangle) and an additional vertex $D$ connected to $B$, with edge weights $w(AB) = 1$, $w(BC) = -2$, $w(CA) = 3$, and $w(BD) = 4$. The optimal weighted matching is $\{CA, BD\}$ with total weight 7, as including the negative-weight edge $BC$ would reduce the value, and the [blossom](/page/Blossom) formed by the odd cycle $A$-$B$-$C$ is shrunk during augmentation to prioritize higher-weight paths.[](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf) The problem is solvable in [polynomial](/page/Polynomial) time, with practical implementations of Edmonds' [algorithm](/page/The_Algorithm) achieving $O(|V|^3)$ [time complexity](/page/Time_complexity) through efficient data structures for finding augmenting paths and updating duals.[](https://pub.ista.ac.at/~vnk/papers/blossom5.pdf) This is higher in constant factors than unweighted matching due to the need for weighted shortest-path computations in the auxiliary graph during each augmentation phase.[](https://pub.ista.ac.at/~vnk/papers/blossom5.pdf) ## Applications and Extensions ### In Combinatorial Optimization Graph matching, as the problem of aligning vertices and edges between two graphs to preserve structural properties, is itself a core combinatorial optimization challenge. It is frequently formulated as the quadratic assignment problem (QAP), where the objective is to find a bijection (or partial matching) that maximizes an affinity score based on node attributes and edge similarities, subject to permutation constraints. This NP-hard problem generalizes linear assignment by incorporating quadratic terms for pairwise relations, making it computationally intensive for large graphs.[](https://jscholarship.library.jhu.edu/bitstreams/7e30e6e0-0e87-438a-bf8d-acdda14bd809/download) In practice, graph matching optimizes alignments in scenarios with relational constraints, such as molecular structure comparison in cheminformatics or network reconfiguration for [resource allocation](/page/Resource_allocation), where edge preservation ensures functional equivalence. Approximate solutions often relax the discrete QAP to continuous optimizations, solvable via [spectral](/page/Spectral) methods or graduated assignment.[](https://arxiv.org/abs/1911.11308) Recent advances as of 2024 integrate [machine learning](/page/Machine_learning) for scalable approximations. For example, [deep reinforcement learning](/page/Deep_reinforcement_learning) approaches, like the Reinforcement Graph Matching (RGM) method, sequentially assign nodes to maximize affinity while handling outliers through revocable actions and regularization. These techniques achieve high accuracy on benchmarks, solving up to 75% of instances near-optimally.[](https://arxiv.org/abs/2012.08950) Graph neural networks further enhance this by learning embeddings that inform the optimization objective.[](https://arxiv.org/abs/2404.06492) ### In Network Flow Problems Graph matching problems can be modeled using network flow techniques, particularly in approximate or partial matching scenarios where correspondences resemble assignments. For bipartite graphs or node-focused alignments, the problem reduces to a minimum-cost flow, with nodes in one graph as sources, the other as sinks, and flow capacities reflecting similarity weights; edge constraints are incorporated via layered [networks](/page/List_of_television_stations_in_Brazil) or multi-commodity flows.[](https://arxiv.org/abs/1706.08482) A key application is in multi-object tracking, where detections across frames form temporal graphs, and matching trajectories is solved as a min-cost flow to minimize association costs while respecting motion constraints. The flow value corresponds to the matching size, with integer flows yielding discrete alignments via the integrality theorem. As of 2017, deep network flow methods extended this by learning cost functions end-to-end, improving robustness to occlusions.[](https://arxiv.org/abs/1706.08482) For general graphs, extensions use successive shortest paths in residual graphs to approximate the QAP relaxation, balancing structural [fidelity](/page/Fidelity) with computational efficiency. These flow-based solvers are polynomial-time for the linear case but [heuristic](/page/Heuristic) for quadratic extensions, enabling applications in dynamic network alignment, such as social media user de-anonymization.[](https://arxiv.org/abs/2303.15414)
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.