Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Exact and approximate graph matching using random walks.

Marco Gori1, Marco Maggini, Lorenzo Sarti

  • 1DII-Università degli Studi di Siena, Via Roma, 56-53100 Siena, Italy. marco@dii.unisi.it

IEEE Transactions on Pattern Analysis and Machine Intelligence
|July 15, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Artificial intelligence in medicine: a position paper by the Italian Society of Internal Medicine.

Internal and emergency medicine·2025
Same author

A systematic literature review of spatio-temporal graph neural network models for time series forecasting and classification.

Neural networks : the official journal of the International Neural Network Society·2025
Same author

Interoperable Traceability in Agrifood Supply Chains: Enhancing Transport Systems Through IoT Sensor Data, Blockchain, and DataSpace.

Sensors (Basel, Switzerland)·2025
Same author

State-space modeling in long sequence processing: a survey on recurrence in the transformer era.

Neural networks : the official journal of the International Neural Network Society·2025
Same author

Continual learning of conjugated visual representations through higher-order motion flows.

Neural networks : the official journal of the International Neural Network Society·2025
Same author

Effects on Posture of a Two-Diopter Horizontal Prism Base Out on the Non-Dominant Eye.

Journal of clinical medicine·2025
Same journal

Benchmarking the Robustness of Autonomous Driving to Environmental Illusions: A Lane Perception Perspective.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Learning Topology-Aware Representations via Test-Time Adaptation for Anomaly Segmentation.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

TraGraph-GS: Trajectory Graph-based Gaussian Splatting for Arbitrary Large-Scale Scene Rendering.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

SWIFT: A Small-World Interaction Framework for Flow-Aware Trajectory Prediction in Autonomous Driving.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

HardFlow: Hard-Constrained Sampling for Flow-Matching Models Via Trajectory Optimization.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Industrial Brain: Self-Evolving Neuro-Symbolic Autonomy with Causal Resilience for Cyber-Physical Systems.

IEEE transactions on pattern analysis and machine intelligence·2026
See all related articles

This study introduces a novel graph matching framework using random walks, enhancing pattern recognition. The method efficiently solves graph isomorphism and excels at approximate matching for image retrieval tasks.

Area of Science:

  • Computer Science
  • Graph Theory
  • Pattern Recognition

Background:

  • Traditional pattern recognition relies on either structured symbolic representations or subsymbolic real-valued features.
  • Existing graph matching algorithms face challenges with complex, real-world data, especially in partial or approximate matching scenarios.

Purpose of the Study:

  • To propose a general graph matching framework integrating structured and subsymbolic pattern representations.
  • To develop an efficient algorithm for graph isomorphism and extend it to approximate graph matching.
  • To demonstrate the framework's applicability in image retrieval tasks.

Main Methods:

  • Utilizing random walk-based models, inspired by Google's PageRank, to develop a spectral theory for graph analysis.
  • Deriving a polynomial-time algorithm for graph isomorphism on Markovian spectrally distinguishable (MSD) graphs.

Related Experiment Videos

  • Applying bipartite graph matching algorithms for partial and approximate graph matching on visual data.

    • Main Results:

    • The proposed spectral theory enhances graph topological features at the node level.
    • The MSD graph class, defined by the spectral theory, covers a significant portion of benchmark graph databases (TC-15).
    • The algorithm demonstrates superior efficiency compared to the VF algorithm on TC-15 and achieves promising results in image retrieval (COIL-100).

    Conclusions:

    • The proposed framework offers a unified approach to graph matching, bridging symbolic and subsymbolic methods.
    • The random walk-based spectral approach provides an efficient solution for graph isomorphism and is highly effective for approximate graph matching.
    • The framework shows significant potential for applications in computer vision and image retrieval.