En minería de estructuras , un núcleo de grafos es una función de núcleo que calcula un producto interno en grafos . [1] Los núcleos de grafos pueden entenderse intuitivamente como funciones que miden la similitud de pares de grafos. Permiten que los algoritmos de aprendizaje kernelizados , como las máquinas de vectores de soporte, trabajen directamente en grafos, sin tener que hacer extracción de características para transformarlos en vectores de características de valor real y longitud fija . Encuentran aplicaciones en bioinformática , en quimioinformática (como un tipo de núcleos de moléculas [2] ) y en análisis de redes sociales . [1]
Los conceptos de núcleos de grafos existen desde 1999, cuando D. Haussler [3] introdujo los núcleos convolucionales en estructuras discretas. El término núcleos de grafos fue acuñado de manera más oficial en 2002 por RI Kondor y J. Lafferty [4] como núcleos en grafos, es decir, funciones de similitud entre los nodos de un único grafo, con el grafo de hipervínculos de la World Wide Web como una aplicación sugerida. En 2003, Gärtner et al. [5] y Kashima et al. [6] definieron los núcleos entre grafos. En 2010, Vishwanathan et al. dieron su marco unificado. [1] En 2018, Ghosh et al. [7] describieron la historia de los núcleos de grafos y su evolución a lo largo de dos décadas.
Se ha demostrado que el núcleo gráfico marginado permite predicciones precisas de la energía de atomización de pequeñas moléculas orgánicas. [8]
Un ejemplo de un núcleo entre grafos es el núcleo de paseo aleatorio [5] [6] , que conceptualmente realiza paseos aleatorios en dos grafos simultáneamente, luego cuenta la cantidad de caminos que fueron producidos por ambos paseos. Esto es equivalente a hacer paseos aleatorios en el producto directo del par de grafos, y a partir de esto, se puede derivar un núcleo que se puede calcular de manera eficiente. [1]
Otro ejemplo es el kernel de grafos Weisfeiler-Leman [9] , que calcula múltiples rondas del algoritmo Weisfeiler-Leman y luego calcula la similitud de dos grafos como el producto interno de los vectores de histogramas de ambos grafos. En esos vectores de histogramas, el kernel recopila la cantidad de veces que aparece un color en el grafo en cada iteración. Nótese que, en teoría, el kernel Weisfeiler-Leman tiene una dimensión infinita, ya que la cantidad de colores posibles asignados por el algoritmo Weisfeiler-Leman es infinita. Al restringirse a los colores que aparecen en ambos grafos, el cálculo sigue siendo factible.