Macheo Inexacto de Grafos

• Subdue tiene la capacidad de encontrar subestructuras con ligeras diferencias en sus instancias.
• Estas diferencias pueden ser causa de ruido o por la naturaleza de la información.
• Algunas de estas pequeñas diferencias pueden ser un vértice adicional o uno mejor, una etiqueta diferente en un vértice, un arco que no existe en una instancia, etc.

• La manera en que Subdue maneja el macheo inexacto es asignando un costo a cada diferencia que encuentra en la nueva instancia y lleva un registro del costo total de las diferencias de la nueva instancia con respecto a la original.
• Si el costo es menos que un umbral (este umbral se da como parámetro), entonces se considera que la nueva instancia hace un macheo con la original.
• Se utilizan reglas para asignar un costo a cada tipo de diferencia, estas reglas se ajustan de acuerdo al dominio.
• El procedimiento de macheo de grafos esta restringido a ser polinomial con respecto al tamaño de los grafos que se comparan.