GTED

GTED computes a graph traversal edit distance that quantifies similarity between labeled graphs by comparing strings of edge labels obtained from Eulerian traversals.

Key Features:

• Graph Kernel Paradigm: Operates under the kernel paradigm, decoupling the learning algorithm from the underlying geometric/feature space for graphs.
• Eulerian Traversal-Based Metric: Calculates the minimum edit distance between strings composed of edge labels derived from Eulerian traversals of the graphs.
• Polynomial Time Algorithm: Provides a polynomial-time algorithm that formulates GTED computation as a linear program in the graph product space and guarantees an integer solution.
• Linear Programming Relaxation: Offers a linear programming relaxation that computes a lower bound on the graph traversal edit distance.

Scientific Applications:

• Bioinformatics: Applied to sequence co-assembly and de novo variation detection, providing a formal mathematical approach for analyses of next-generation sequencing data and assembly graphs.
• Machine Learning Evaluation: Used as a graph kernel and evaluated by computing support vector machine (SVM) classifier accuracy across datasets, reporting performance superior to many common graph kernels.
• Genomic Clustering: Employed to cluster viral genomes by analyzing assembly graphs derived from de novo assembly of next-generation sequencing reads.

Methodology:

Derive strings of edge labels from Eulerian traversals, compute the minimum edit distance between those strings, formulate the computation as a linear program in the graph product space that yields an integer solution, and compute a linear programming relaxation to obtain a lower bound.