A distance measure between attributed relational graphs for pattern recognition
1983/05/01 by Alberto Sanfeliu, King-Sun Fu, King‐Sun Fu · 990 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Computation #Computer science #Data mining #Distance matrix #Distance measures #Edit distance #Graph #Graph Theory and Algorithms #Mathematics #Measure (data warehouse) #Natural Language Processing Techniques #Node (physics) #Pattern recognition (psychology) #Similarity (geometry) #Similarity measure #Substitution (logic) #Theoretical computer science
paper · doi:10.1109/tsmc.1983.6313167
published in IEEE Transactions on Systems Man and Cybernetics SMC-13(3), 353-362 (Institute of Electrical and Electronics Engineers)
openalex publication_date 1983/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
Abstract
A method to determine a distance measure between two nonhierarchical attributed relational graphs is presented. In order to apply this distance measure, the graphs are characterised by descriptive graph grammars (DGG). The proposed distance measure is based on the computation of the minimum number of modifications required to transform an input graph into the reference one. Specifically, the distance measure is defined as the cost of recognition of nodes plus the number of transformations which include node insertion, node deletion, branch insertion, branch deletion, node label substitution and branch label substitution. The major difference between the proposed distance measure and the other ones is the consideration of the cost of recognition of nodes in the distance computation. In order to do this, the principal features of the nodes are described by one or several cost functions which are used to compute the similarity between the input nodes and the reference ones. Finally, an application of this distance measure to the recognition of lower case handwritten English characters is presented.
Cited by
- OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories
- Explaining Human Preferences via Metrics for Structured 3D Reconstruction
- Private Graph Data Release: A Survey
- Few-Shot Learning of a Graph-Based Neural Network Model Without Backpropagation
- Empirical Assessment of the Code Comprehension Effort Needed to Attack Programs Protected with Obfuscation
- CoSimGNN: Towards Large-scale Graph Similarity Computation
- Structured Diversification Emergence via Reinforced Organization Control and Hierarchical Consensus Learning
- A framework for cost-constrained genome rearrangement under Double Cut and Join
- SPA-GCN: Efficient and Flexible GCN Accelerator with an Application for Graph Similarity Computation
- DeepNC: Deep Generative Network Completion
- Efficient graph similarity assessment method based on vectors of topological indices
- Graph comparison via nonlinear quantum search
- MapLayNet: map layout representation learning using weakly supervised structure-aware graph neural networks
- Reeb Graph Metrics from the Ground Up
- AMLNet: A Knowledge-Based Multi-Agent Framework to Generate and Detect Realistic Money Laundering Transactions
- Universal Invariant and Equivariant Graph Neural Networks
- LayoutGKN: Graph Similarity Learning of Floor Plans
- An interdisciplinary survey of network similarity methods
- RECAP: REwriting Conversations for Intent Understanding in Agentic Planning
- A statistical test for network similarity
- Function-Described Graphs for Structural Pattern Recognition
- From Legacy to Standard: LLM-Assisted Transformation of Cybersecurity Playbooks into CACAO Format
- A Quadratic Assignment Formulation of the Graph Edit Distance
- Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)
- A Two-Phase Approach Towards Identifying Argument Structure in Natural Language
- Computing Optimal Assignments in Linear Time for Approximate Graph\n Matching
- Contrastive Graph Neural Network Explanation
- Modeling Hierarchical Spaces: A Review and Unified Framework for Surrogate-Based Architecture Design
- Surrogate-Assisted Evolution for Efficient Multi-branch Connection Design in Deep Neural Networks
- A family of graph GOSPA metrics for graphs with different sizes
- Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching
- Recognizing Cuneiform Signs Using Graph Based Methods
- Schema Generation for Large Knowledge Graphs Using Large Language Models
- WILTing Trees: Interpreting the Distance Between MPNN Embeddings
- The quest for the GRAph Level autoEncoder (GRALE)
- Comparison Issues in Large Graphs: State of the Art and Future Directions
- An Iterative Framework for Generative Backmapping of Coarse Grained Proteins
- New Techniques for Graph Edit Distance Computation
- SCENIR: Visual Semantic Clarity through Unsupervised Scene Graph Retrieval
- Interpreting Language Models Through Knowledge Graph Extraction
- Sample Complexity of Correlation Detection in the Gaussian Wigner Model
- Lossless Representation of Graphs using Distributions
- COMRECGC: Global Graph Counterfactual Explainer through Common Recourse
- Graph Matching and Similarity
- Fair splits flip the leaderboard: CHANRG reveals limited generalization in RNA secondary-structure prediction
- Topological Insights into Sparse Neural Networks
- Novel diffusion-derived distance measures for graphs
- Rise of the Kniesians: The professor-student network of Nobel laureates\n in economics
- Maps of Tournaments: Distances, Experiments, and Data
- A subgraph isomorphism algorithm and its application to biochemical data
- An algorithm for finding nearest neighbours in (approximately) constant average time
- Shape modeling and matching in identifying 3D protein structures
- A Separator-based Algorithm for the Graph Edit Distance Problem
- ℓp-Stability of Weighted Persistence Diagrams
- Learning from the Past: Adaptive Parallelism Tuning for Stream Processing Systems
- An ANOVA approach for statistical comparisons of brain networks. [europepmc]
- Analysing the sensitivity of nestedness detection methods. [europepmc]
- Assessing diversity in multiplex networks. [europepmc]
- Ligand-Based Virtual Screening Using Graph Edit Distance as Molecular Similarity Measure. [europepmc]
- Evidence to support common application switching behaviour on smartphones. [europepmc]
- Learning the Edit Costs of Graph Edit Distance Applied to Ligand-Based Virtual Screening. [europepmc]
- A Path-Based Distribution Measure for Network Comparison. [europepmc]
- Graph diffusion distance: Properties and efficient computation. [europepmc]
- Statistical and Machine Learning Link Selection Methods for Brain Functional Networks: Review and Comparison. [europepmc]
- Alignments of biomolecular contact maps. [europepmc]
- Holistic evaluation of biodegradation pathway prediction: assessing multi-step reactions and intermediate products. [europepmc]
- Ligand-Based Virtual Screening Based on the Graph Edit Distance. [europepmc]
- Event prediction from news text using subgraph embedding and graph sequence mining. [europepmc]
- A Low Complexity Persistent Reconnaissance Algorithm for FANET. [europepmc]
- Reconstructing B cell lineage trees with minimum spanning tree and genotype abundances. [europepmc]
- Lacking mechanistic disease definitions and corresponding association data hamper progress in network medicine and beyond. [europepmc]
- Visualizing the Residue Interaction Landscape of Proteins by Temporal Network Embedding. [europepmc]
- Models of similarity in complex networks. [europepmc]
- Building Multiple Classifier Systems Using Linear Combinations of Reduced Graphs. [europepmc]
- Calculating Pairwise Similarity of Polymer Ensembles via Earth Mover's Distance. [europepmc]
- Utilizing Low-Dimensional Molecular Embeddings for Rapid Chemical Similarity Search. [europepmc]
- Investigating heterogeneity across autism, ADHD, and typical development using measures of cortical thickness, surface area, cortical/subcortical volume, and structural covariance. [europepmc]
- Comparing Care Pathways Between COVID-19 Pandemic Waves Using Electronic Health Records: A Process Mining Case Study. [europepmc]
- Estimating Descriptors for Large Graphs [europepmc]
- Comparing care pathways between COVID-19 pandemic waves using electronic health records: a process mining case study [europepmc]
Related