Community hub
0 subscribers8 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Graph edit distance.
Nothing was collected or created yet.
Graph edit distance
View on Wikipediafrom Wikipedia
In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs. The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983.[1] A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning.[2]
The graph edit distance between two graphs is related to the string edit distance between strings. With the interpretation of strings as connected, directed acyclic graphs of maximum degree one, classical definitions of edit distance such as Levenshtein distance,[3][4] Hamming distance[5] and Jaro–Winkler distance may be interpreted as graph edit distances between suitably constrained graphs. Likewise, graph edit distance is also a generalization of tree edit distance between rooted trees.[6][7][8][9][10]
Formal definitions and properties
[edit]The mathematical definition of graph edit distance is dependent upon the definitions of the graphs over which it is defined, i.e. whether and how the vertices and edges of the graph are labeled and whether the edges are directed. Generally, given a set of graph edit operations (also known as elementary graph operations), the graph edit distance between two graphs and , written as can be defined as
where denotes the set of edit paths transforming into (a graph isomorphic to) and is the cost of each graph edit operation .
The set of elementary graph edit operators typically includes:
- vertex insertion to introduce a single new labeled vertex to a graph.
- vertex deletion to remove a single (often disconnected) vertex from a graph.
- vertex substitution to change the label (or color) of a given vertex.
- edge insertion to introduce a new colored edge between a pair of vertices.
- edge deletion to remove a single edge between a pair of vertices.
- edge substitution to change the label (or color) of a given edge.
Additional, but less common operators, include operations such as edge splitting that introduces a new vertex into an edge (also creating a new edge), and edge contraction that eliminates vertices of degree two between edges (of the same color). Although such complex edit operators can be defined in terms of more elementary transformations, their use allows finer parameterization of the cost function when the operator is cheaper than the sum of its constituents.
A deep analysis of the elementary graph edit operators is presented in [11][12][13]
And some methods have been presented to automatically deduce these elementary graph edit operators.[14][15][16][17][18] And some algorithms learn these costs online:[19]
Applications
[edit]Graph edit distance finds applications in handwriting recognition,[20] fingerprint recognition[21] and cheminformatics.[22]
Algorithms and complexity
[edit]Exact algorithms for computing the graph edit distance between a pair of graphs typically transform the problem into one of finding the minimum cost edit path between the two graphs. The computation of the optimal edit path is cast as a pathfinding search or shortest path problem, often implemented as an A* search algorithm.
In addition to exact algorithms, a number of efficient approximation algorithms are also known. Most of them have cubic computational time [23][24] [25] [26] [27]
Moreover, there is an algorithm that deduces an approximation of the GED in linear time [28]
Despite the above algorithms sometimes working well in practice, in general the problem of computing graph edit distance is NP-hard (for a proof that's available online, see Section 2 of Zeng et al.), and is even hard to approximate (formally, it is APX-hard[29]).
References
[edit]- ^ Sanfeliu, Alberto; Fu, King-Sun (1983). "A distance measure between attributed relational graphs for pattern recognition". IEEE Transactions on Systems, Man, and Cybernetics. 13 (3): 353–363. doi:10.1109/TSMC.1983.6313167. S2CID 1087693.
- ^ Gao, Xinbo; Xiao, Bing; Tao, Dacheng; Li, Xuelong (2010). "A survey of graph edit distance". Pattern Analysis and Applications. 13: 113–129. doi:10.1007/s10044-008-0141-y.
- ^ Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академий Наук СССР (in Russian). 163 (4): 845–848.
- ^ Levenshtein, Vladimir I. (February 1966). "Binary codes capable of correcting deletions, insertions, and reversals". Soviet Physics Doklady. 10 (8): 707–710. Bibcode:1966SPhD...10..707L.
- ^ Hamming, Richard W. (1950). "Error detecting and error correcting codes" (PDF). Bell System Technical Journal. 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. hdl:10945/46756. MR 0035935. S2CID 61141773. Archived from the original on 2006-05-25.
{{cite journal}}: CS1 maint: bot: original URL status unknown (link) - ^ Shasha, D; Zhang, K (1989). "Simple fast algorithms for the editing distance between trees and related problems". SIAM J. Comput. 18 (6): 1245–1262. CiteSeerX 10.1.1.460.5601. doi:10.1137/0218082. S2CID 10970317.
- ^ Zhang, K (1996). "A constrained edit distance between unordered labeled trees". Algorithmica. 15 (3): 205–222. doi:10.1007/BF01975866. S2CID 20043881.
- ^ Bille, P (2005). "A survey on tree edit distance and related problems". Theor. Comput. Sci. 337 (1–3): 22–34. CiteSeerX 10.1.1.100.2577. doi:10.1016/j.tcs.2004.12.030.
- ^ Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010). "An optimal decomposition algorithm for tree edit distance". ACM Transactions on Algorithms. 6 (1): A2. arXiv:cs/0604037. CiteSeerX 10.1.1.163.6937. doi:10.1145/1644015.1644017. MR 2654906. S2CID 7878119.
- ^ Fan, Dayi; Lee, Rubao; Zhang, Xiaodong (2024). "X-TED: Massive Parallelization of Tree Edit Distance" (PDF). Proceedings of the VLDB Endowment. 17 (7): 1683–1696. doi:10.14778/3654621.3654634.
- ^ Serratosa, Francesc (2021). Redefining the Graph Edit Distance. S. N. Computer Science, pp: 2-438.
- ^ Serratosa, Francesc (2019). Graph edit distance: Restrictions to be a metric. Pattern Recognition, 90, pp: 250-256.
- ^ Serratosa, Francesc; Cortés, Xavier (2015). Graph Edit Distance: moving from global to local structure to solve the graph-matching problem. Pattern Recognition Letters, 65, pp: 204-210.
- ^ Santacruz, Pep; Serratosa, Francesc (2020). Learning the graph edit costs based on a learning model applied to sub-optimal graph matching. Neural Processing Letters, 51, pp: 881–904.
- ^ Algabli, Shaima; Serratosa, Francesc (2018). Embedding the node-to-node mappings to learn the Graph edit distance parameters. Pattern Recognition Letters, 112, pp: 353-360.
- ^ Xavier, Cortés; Serratosa, Francesc (2016). Learning Graph Matching Substitution Weights based on the Ground Truth Node Correspondence. International Journal of Pattern Recognition and Artificial Intelligence, 30(2), pp: 1650005 [22 pages].
- ^ Xavier, Cortés; Serratosa, Francesc (2015). Learning Graph-Matching Edit-Costs based on the Optimality of the Oracle's Node Correspondences. Pattern Recognition Letters, 56, pp: 22 - 29.
- ^ Conte, Donatello; Serratosa, Francesc (2020). Interactive Online Learning for Graph Matching using Active Strategies. Knowledge Based Systems, 105, pp: 106275.
- ^ Rica, Elena; Álvarez, Susana; Serratosa, Francesc (2021). On-line learning the graph edit distance costs. Pattern Recognition Letters, 146, pp: 52-62.
- ^ Fischer, Andreas; Suen, Ching Y.; Frinken, Volkmar; Riesen, Kaspar; Bunke, Horst (2013), "A Fast Matching Algorithm for Graph-Based Handwriting Recognition", Graph-Based Representations in Pattern Recognition, Lecture Notes in Computer Science, vol. 7877, pp. 194–203, doi:10.1007/978-3-642-38221-5_21, ISBN 978-3-642-38220-8
- ^ Neuhaus, Michel; Bunke, Horst (2005), "A Graph Matching Based Approach to Fingerprint Classification using Directional Variance", Audio- and Video-Based Biometric Person Authentication, Lecture Notes in Computer Science, vol. 3546, pp. 191–200, doi:10.1007/11527923_20, ISBN 978-3-540-27887-0
- ^ Birchall, Kristian; Gillet, Valerie J.; Harper, Gavin; Pickett, Stephen D. (Jan 2006). "Training Similarity Measures for Specific Activities: Application to Reduced Graphs". Journal of Chemical Information and Modeling. 46 (2): 557–586. doi:10.1021/ci050465e. PMID 16562986.
- ^ Neuhaus, Michel; Bunke, Horst (Nov 2007). Bridging the Gap between Graph Edit Distance and Kernel Machines. Machine Perception and Artificial Intelligence. Vol. 68. World Scientific. ISBN 978-9812708175.
- ^ Riesen, Kaspar (Feb 2016). Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications. Advances in Computer Vision and Pattern Recognition. Springer. ISBN 978-3319272511.
- ^ Serratosa, Francesc (2014). Fast Computation of Bipartite Graph Matching. Pattern Recognition Letters, 45, pp: 244 - 250.
- ^ Serratosa, Francesc (2015). Speeding up Fast Bipartite Graph Matching through a new cost matrix. International Journal of Pattern Recognition and Artificial Intelligence, 29 (2), 1550010, [17 pages].
- ^ Serratosa, Francesc (2015). Computation of Graph Edit Distance: Reasoning about Optimality and Speed-up. Image and Vision Computing, 40, pp: 38-48.
- ^ Santacruz, Pep; Serratosa, Francesc (2018). Error-tolerant graph matching in linear computational cost using an initial small partial matching. Pattern Recognition Letters.
- ^ Lin, Chih-Long (1994-08-25). "Hardness of approximating graph transformation problem". In Du, Ding-Zhu; Zhang, Xiang-Sun (eds.). Algorithms and Computation. Lecture Notes in Computer Science. Vol. 834. Springer Berlin Heidelberg. pp. 74–82. doi:10.1007/3-540-58325-4_168. ISBN 9783540583257.
Graph edit distance
View on Grokipediafrom Grokipedia
Graph edit distance (GED) is a measure of similarity between two graphs, defined as the minimum cost required to transform one graph into the other through a sequence of edit operations, including the insertion, deletion, and substitution of nodes and edges.[1] These operations can be assigned costs based on attributes of the nodes and edges, allowing GED to handle both unlabeled and attributed graphs in an error-tolerant manner for inexact graph matching.[1] Formally, for two graphs and , GED is the cost of the least expensive edit path, often modeled as an assignment problem where mappings between nodes and edges minimize the total edit cost.[2]
The concept of GED was first formalized by Sanfeliu and Fu in 1983 as a distance measure between attributed relational graphs for pattern recognition tasks. It built on earlier ideas from string edit distance and was further developed by Bunke and Allermann in 1983 for inexact graph matching in structural pattern recognition, emphasizing its role in handling distortions and noise in graph representations. Subsequent work by Messmer and Bunke in the 1990s introduced extensions like error-tolerant subgraph matching and probabilistic interpretations, establishing GED as a foundational metric in graph-based machine learning.[1] Over time, GED has been generalized to include various cost functions, such as those forming convex polygons in labeling spaces, which influence the shape and properties of the edit surface.[2]
Computing the exact GED is NP-hard, equivalent to finding the minimum-cost edit path in a search space that grows factorially with graph size, often reduced to a quadratic assignment problem or bipartite matching for approximations.[1] Exact algorithms, such as branch-and-bound or A* search, are feasible only for small graphs (typically under 20 vertices), while heuristics like bipartite graph matching, self-organizing maps for cost learning, or neural network-based approximations (e.g., via graph neural networks) enable efficient computation for larger structures. Key challenges include defining appropriate edit costs, handling attribute mismatches, and scaling to real-world datasets, with recent advances incorporating machine learning to estimate distances in sub-quadratic time.[3]
GED finds broad applications in pattern recognition, such as offline handwritten character recognition, shape and image analysis, and video indexing, where graphs represent structural relationships tolerant to deformations.[1] In bioinformatics, it measures similarity between molecular structures or protein interaction networks; in computer vision, it supports sketch-to-photo matching and scene recognition; and in machine learning, it underpins tasks like graph classification and clustering by providing a flexible dissimilarity metric.[1] Its adaptability to different domains, combined with ongoing research into faster approximations and learned edit costs, continues to drive its relevance in graph-based data analysis.[4]
Fundamentals
Definition
Graph edit distance (GED) is a measure of similarity between two graphs, defined as the minimum total cost of a sequence of edit operations required to transform a source graph into a target graph . This edit path allows for structural and label differences to be quantified in a flexible manner, making GED particularly useful for inexact graph matching in scenarios where perfect isomorphism is unlikely. The concept was introduced to address error-tolerant comparisons in structural pattern recognition, where graphs represent relational data with potential noise or variations. Formally, let and be two undirected labeled graphs, where denotes the vertex set, the edge set, and the labeling function assigning labels from finite alphabets to both vertices () and edges (). The GED is given by where is the set of all edit paths transforming into , and is the cost of the -th edit operation . Each edit operation incurs a non-negative cost via functions for vertices and for edges, with as a dummy label for insertions or deletions; typically, for no substitution, insertions and deletions have unit cost (e.g., 1), and substitutions reflect label dissimilarity (e.g., for some distance ). To illustrate, consider two simple undirected graphs each with two vertices connected by a single edge and no edge labels. Let have vertices labeled "A" and "B", while has vertices labeled "A" and "C". Assuming unit costs for insertions/deletions and substitution cost equal to 1 if labels differ (0 otherwise), the minimum edit path substitutes "B" with "C" (cost 1), leaving the structure intact, yielding GED() = 1. If labels were identical, GED would be 0, indicating isomorphism. This basic case highlights how GED captures label-based differences without altering connectivity.Edit Operations
The primary edit operations in graph edit distance (GED) are vertex insertion, vertex deletion, edge insertion, and edge deletion, which allow for the addition or removal of structural elements between two graphs. These operations are complemented by substitution operations, specifically vertex relabeling—where the label of a vertex is changed from to at a cost determined by a label distance function —and edge relabeling, which similarly adjusts edge labels based on their dissimilarity.[5] Costs are assigned to each operation to quantify the transformation effort, with insertions and deletions typically incurring a unit cost of 1, though higher values are sometimes used in specific applications. Substitution costs are 0 when labels match exactly, promoting mappings of identical elements, and exceed 0 otherwise to reflect the degree of change required. These cost functions ensure the total GED reflects a meaningful structural dissimilarity while allowing flexibility for domain-specific adaptations.[5] If two graphs are isomorphic, GED is zero, as an edit path exists consisting solely of zero-cost substitutions that preserve all labels and structure.[5] As an illustrative example, consider transforming a path graph with three unlabeled vertices connected as (two edges) into a cycle graph with the same vertices but three edges (). Under unit costs for insertions and deletions, with zero-cost substitutions for matching vertices and existing edges, the minimum edit path substitutes the vertices and the two existing edges at no cost, then inserts the closing edge at cost 1, yielding a total GED of 1.[5]Properties and Variants
Key Properties
Graph edit distance (GED) exhibits several key mathematical properties that underpin its utility as a measure of structural similarity between graphs. It is inherently non-negative, satisfying GED(G₁, G₂) ≥ 0 for any two graphs G₁ and G₂, since edit costs are defined to be non-negative and the distance represents the minimum such cost over all possible edit paths.[6] This non-negativity holds regardless of the specific cost assignment, as long as individual edit operations do not incur negative costs. A fundamental property is the identity of indiscernibles: GED(G₁, G₂) = 0 if and only if G₁ and G₂ are isomorphic. If the graphs are isomorphic, an edit path consisting solely of zero-cost substitutions (via a bijection preserving labels and edges) achieves this minimum. Conversely, a zero-cost path implies no insertions, deletions, or non-trivial substitutions are required, confirming structural equivalence.[6] This direct link to graph isomorphism positions GED as an error-tolerant extension of exact matching, where non-zero distances quantify the minimal structural deviations.[7] Symmetry holds under the condition of symmetric edit costs, where the cost of an operation equals the cost of its inverse (e.g., insertion cost equals deletion cost for vertices and edges). In this case, GED(G₁, G₂) = GED(G₂, G₁). To see this, consider any minimum-cost edit path π from G₁ to G₂ with cost c(π). Reversing π yields an edit path from G₂ to G₁, and symmetry ensures the reversed operations have identical costs, preserving the minimum. If costs are asymmetric, symmetry may fail.[6] The triangle inequality, GED(G₁, G₃) ≤ GED(G₁, G₂) + GED(G₂, G₃), does not generally hold for GED, particularly when computed via edit paths (GED_path) and with arbitrary non-unit costs. For instance, edit paths may not compose in a way that bounds the direct path cost, even if individual edit functions satisfy the inequality. This property is satisfied only under restrictive conditions, such as unit costs for all operations or when GED is reformulated via bijections (GED_bij) with edit functions that themselves obey the triangle inequality. Consequently, GED is a pseudo-metric rather than a full metric in many settings, which can affect its use in certain geometric or optimization contexts.[6] GED also displays intuitive behavior relative to graph sizes. For vertex edits, it is lower bounded by the difference in vertex counts: GED(G₁, G₂) ≥ ||V₁| - |V₂|| ⋅ min(c_ins^v, c_del^v), where c_ins^v and c_del^v are the minimum costs for vertex insertion and deletion, respectively. This bound follows directly from the necessity of at least |V₁| - |V₂| (assuming |V₁| ≥ |V₂|) insert or delete operations to balance the vertex sets before any substitutions or edge edits can occur. Similar bounds apply to edge counts, providing quick estimates for dissimilarity in unbalanced graphs.[8]Common Variants
The concept of graph edit distance was first formalized by Sanfeliu and Fu in 1983, with initial variants for inexact matching developed by Bunke and Allermann in the same year, to enable tolerance for distortions and noise through a sequence of edit operations with associated costs.[9][10] Subsequent extensions in the 2000s adapted these variants for bioinformatics, incorporating domain-specific edit costs for molecular and genomic graphs. Error-tolerant graph edit distance, inherent to the foundational model, permits approximate matches by assigning costs to edit operations and bounding the total error to reflect practical dissimilarities in noisy data. Bounded graph edit distance restricts the maximum allowable edit cost or path length, facilitating efficient computation while ensuring the distance remains within a predefined threshold for applications requiring scalability.[11] Variants for directed graphs extend the standard operations to handle edge directionality, such as inserting, deleting, or substituting directed edges while preserving orientation in the edit sequence.[12] For weighted graphs, adaptations incorporate edge weights into substitution costs beyond mere label matching, allowing the distance to account for quantitative differences in edge properties.[13] Subgraph edit distance modifies the objective to find the minimum edit cost transforming the source graph into any subgraph of the target graph, rather than an exact isomorphic match, which is useful for partial structure detection.[14] An example of a practical variant is the size-normalized graph edit distance, which scales the raw distance by the average graph size—such as dividing by , where denotes the number of vertices in graph —to enable fair comparisons between graphs of differing scales.[15]Applications
Pattern Recognition and Computer Vision
Graph edit distance (GED) was pioneered in the 1980s for syntactic pattern recognition, enabling error-tolerant matching of structural representations in visual data. Introduced by Bunke and Allermann in 1983 as a method for inexact graph matching, it addressed the limitations of exact isomorphism in handling noisy or distorted patterns common in images.[16] By the 1990s, GED had become a cornerstone for inexact graph matching, with Bunke's 1997 work establishing theoretical links between GED and maximum common subgraph approximations, facilitating its adoption in computer vision tasks.[7] In object recognition, GED facilitates graph matching by representing shapes as attributed graphs, where nodes capture features like curvature or position, and edges encode spatial relations, allowing similarity measurement through minimal edit costs. This approach excels in error-tolerant scenarios, such as recognizing deformed or partially occluded objects, by quantifying the cost of insertions, deletions, and substitutions to align graphs. For instance, Sebastian et al. (2003) applied GED to shock graphs—skeletal representations of shape boundaries—for robust object recognition, demonstrating high accuracy in matching silhouettes from databases like MPEG-7, where traditional feature-based methods falter under viewpoint variations. A practical example is handwritten character recognition, where stroke sequences form graphs, and GED measures shape similarity despite variations in writing style. For image analysis, GED supports attributed relational graphs (ARGs) in tasks like scene labeling, where nodes represent regions or objects with attributes (e.g., color, texture), and edges denote relations (e.g., adjacency, inclusion). This enables error-tolerant matching for segmenting and interpreting complex scenes, accommodating segmentation errors or noise. Robles-Kelly and Hancock (2005) utilized GED on ARGs derived from image adjacency matrices for content-based image retrieval, achieving lower intra-class distances on datasets like COIL compared to spectral methods alone. Unlike string edit distance, which is limited to linear sequences, GED captures 2D structural relations, making it superior for hierarchical or relational visual patterns, as highlighted in early applications to syntactic image understanding.[16]Chemoinformatics and Bioinformatics
In chemoinformatics, graph edit distance (GED) serves as a measure of structural similarity between molecular graphs, where atoms are represented as nodes and chemical bonds as edges, facilitating tasks in drug discovery such as virtual screening of compound libraries to identify potential therapeutic agents. The edit operations—node and edge insertions, deletions, and substitutions—directly model chemical modifications, including atom additions, replacements, or alterations in bonding patterns, thereby quantifying the minimal transformations required to align two molecules. This approach has proven effective for retrieving structurally similar compounds from databases, outperforming some fingerprint-based methods in enrichment factors for active molecules in pharmacological screens.[17] In bioinformatics, GED is applied to compare protein structures by converting them into contact map graphs, in which nodes denote amino acid residues and edges signify close spatial contacts (typically within a predefined distance threshold), allowing for the assessment of conformational similarities and differences. Such graph representations enable GED to estimate evolutionary distances between proteins by calculating the edit cost to transform one contact map into another, providing insights into structural divergence over phylogenetic time scales. For example, GED computations on contact maps have been used to align and classify protein domains, revealing conserved motifs in families like kinases or globins. As of 2025, GED has also been applied in genomics for constructing edit-distance graphs to cluster large sets of short reads from sequencing data, aiding in genome assembly and variant detection.[18][19] A specific instance of GED's utility involves approximating the maximum common edge subgraph (MCES) for pharmacophore matching, where pharmacophores—simplified graphs capturing key molecular features like hydrogen bond donors or hydrophobic regions—are compared to identify shared interaction patterns with biological targets. By optimizing GED to minimize edit costs between these pharmacophore graphs, MCES approximations highlight overlapping substructures essential for activity, supporting ligand-based virtual screening and scaffold hopping in medicinal chemistry.[20] The use of GED in chemoinformatics and bioinformatics emerged prominently in the early 2000s, with foundational evaluations by Raymond and Willett demonstrating its viability for similarity searching in chemical databases containing thousands of 2D structures. Subsequent advancements have incorporated GED into machine learning pipelines via specialized kernels that approximate edit distances, enabling supervised classification of biological graphs such as protein-protein interaction networks or metabolic pathways in datasets from sources like the Protein Data Bank. These GED kernels, often based on random walk or convolution formulations, enhance accuracy in tasks like predicting protein function or molecular bioactivity without requiring exact distance computations.[21] Recent applications as of 2024 include using GED for clustering travel-activity patterns in transportation analysis, where graphs represent weekly mobility sequences to identify behavioral similarities tolerant to variations in data collection.[22]Algorithms
Exact Methods
Exact methods for computing graph edit distance (GED) aim to find the minimum cost sequence of edit operations that transforms one graph into another, guaranteeing the optimal solution without approximation. These approaches are essential in scenarios where precision is paramount, such as verifying structural similarities in small datasets from pattern recognition tasks. However, due to the inherent complexity of the problem, exact methods are typically feasible only for graphs with a limited number of vertices, often up to 10-20 nodes depending on the graph density and edit costs.[16] One prominent exact method employs a tree search strategy based on the A* algorithm, which explores the space of possible edit paths in a best-first manner. The search tree is constructed by sequentially assigning nodes from the source graph to nodes in the target graph , including dummy nodes to account for insertions and deletions. At each step, the algorithm selects the partial mapping with the lowest estimated total cost, where the total cost is the sum of the actual cost incurred so far and an admissible heuristic lower bound on the remaining cost. Admissible heuristics, such as those derived from bipartite matching on unmatched nodes or lower bounds on edge edit costs, ensure that the first complete path found is optimal. This approach was formalized in early works on inexact graph matching and has been refined in subsequent implementations to reduce memory usage, such as through depth-first variants like DF-GED.[16][23] The GED problem can be formulated as finding an optimal bijection , where and are sets of dummy (null) nodes representing insertions and deletions, respectively (typically , to balance sizes). The total edit cost under this mapping is the sum of vertex edit costs , where denotes substitution, insertion, or deletion costs based on whether is a real node or dummy, plus edge edit costs determined by the induced mapping: for each edge , a cost for substitution (if both images are real and edge exists in ), deletion (if image edge missing), etc.; symmetrically, insertion costs for edges in without preimages under . This formulation captures the interdependence between node and edge edits, making the search space combinatorial. For the heuristic in A*, a common lower bound is the cost of optimal bipartite matching on the remaining nodes using vertex substitution costs alone, ignoring edge dependencies to ensure admissibility.[16][23] To illustrate the A* approach, consider two small undirected graphs without labels for simplicity (unit costs: 1 for insert/delete/substitute node or edge). Let have vertices with edge , and have vertices with edges . The goal is to transform to with minimum cost.- Initial state: Empty partial mapping, (cost so far), heuristic based on matching 2 nodes to 3 (e.g., for one deletion/insertion imbalance, plus edge costs).
- Step 1: Assign (substitute cost 1, partial edge match possible), new , (remaining to or , plus edge inserts/deletes). Alternative: (delete cost 1), but higher .
- Step 2: From , assign (), check induced edge: matches, no edge cost; (insert and edge ). Total .
- Step 3: Complete by inserting and edge (), , total cost 4. Explore alternatives like (would require edge substitute/delete, higher cost). The search prunes branches where , confirming optimality (actual minimum: substitute , , insert and edge).