En la minería de estructuras , un kernel de gráfico es una función del kernel que calcula un producto interno en los gráficos . [1] Los núcleos de gráficos pueden entenderse intuitivamente como funciones que miden la similitud de pares de gráficos. Permiten que los algoritmos de aprendizaje kernelizados , como las máquinas de vectores de soporte, trabajen directamente en los gráficos, sin tener que realizar una 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 el análisis de redes sociales . [1]
Los conceptos de kernels de grafos han existido desde 1999, cuando D. Haussler [3] introdujo kernels convolucionales en estructuras discretas. RI Kondor y J. Lafferty [4] acuñaron más oficialmente el término núcleos de gráficos en 2002 como núcleos en gráficos, es decir, funciones de similitud entre los nodos de un solo gráfico, con el gráfico de hipervínculo de la World Wide Web como aplicación sugerida. En 2003, Gaertner et al. [5] y Kashima et al. [6] núcleos definidos entre gráficos. En 2010, Vishwanathan et al. dio su marco unificado. [1] En 2018, Ghosh et al. [7] describió la historia de los kernels de gráficos y su evolución durante dos décadas.
Aplicaciones
Se ha demostrado que el kernel de gráfico marginalizado permite predicciones precisas de la energía de atomización de pequeñas moléculas orgánicas. [8]
Núcleos de ejemplo
Un ejemplo de un kernel entre gráficos es el kernel de recorrido aleatorio , [5] [6] que conceptualmente realiza recorridos aleatorios en dos gráficos simultáneamente, luego cuenta el número de recorridos que fueron producidos por ambos recorridos. Esto equivale a realizar caminatas aleatorias sobre el producto directo del par de gráficos 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 gráfico Weisfeiler-Lehman [9] que calcula múltiples rondas del algoritmo Weisfeiler-Lehman y luego calcula la similitud de dos gráficos como el producto interno de los vectores de histograma de ambos gráficos. En esos vectores de histograma, el núcleo recopila el número de veces que aparece un color en el gráfico en cada iteración. Para dos gráficos isomorfos, el kernel devuelve una similitud máxima ya que los dos vectores de características son idénticos. Tenga en cuenta que el kernel de Weisfeiler-Lehman en teoría tiene una dimensión infinita, ya que el número de colores posibles asignados por el algoritmo de Weisfeiler-Lehman es infinito. Al restringirse a los colores que aparecen en ambos gráficos, el cálculo sigue siendo factible.
Ver también
- Núcleo de árbol , como caso especial de gráficos no cíclicos
- Minería de moléculas , como caso especial de pequeños gráficos de etiquetas múltiples
Referencias
- ^ a b c d S.VN Vishwanathan; Nicol N. Schraudolph; Risi Kondor; Karsten M. Borgwardt (2010). "Graph kernels" (PDF) . Revista de investigación sobre aprendizaje automático . 11 : 1201-1242.
- ^ L. Ralaivola; SJ Swamidass; H. Saigo; P. Baldi (2005). "Graficar núcleos para informática química". Redes neuronales . 18 (8): 1093-1110. doi : 10.1016 / j.neunet.2005.07.009 . PMID 16157471 .
- ^ Haussler, David (1999). Núcleos de convolución en estructuras discretas . CiteSeerX 10.1.1.110.638 .
- ^ Risi Imre Kondor; John Lafferty (2002). Núcleos de difusión en gráficos y otros espacios de entrada discretos (PDF) . Proc. Conf. Int. sobre aprendizaje automático (ICML).
- ^ a b Thomas Gaertner; Peter Flach; Stefan Wrobel (2003). Sobre núcleos gráficos: resultados de dureza y alternativas eficientes . Proc. la 16ª Conferencia Anual sobre Teoría del Aprendizaje Computacional (COLT) y el 7º Taller de Kernel. doi : 10.1007 / 978-3-540-45167-9_11 .
- ^ a b Hisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). Núcleos marginados entre gráficos etiquetados (PDF) . Proc. la 20ª Conferencia Internacional sobre Aprendizaje Automático (ICML).
- ^ Ghosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas (2018). "El viaje de los kernels de gráficos a lo largo de dos décadas". Revisión de Ciencias de la Computación . 27 : 88-111. doi : 10.1016 / j.cosrev.2017.11.002 .
- ^ Yu-Hang Tang; Wibe A. de Jong (2019). "Predicción de la energía de atomización mediante kernel de gráfico y aprendizaje activo". La Revista de Física Química . 150 (4): 044107. arXiv : 1810.07310 . Código bibliográfico : 2019JChPh.150d4107T . doi : 10.1063 / 1.5078640 . PMID 30709286 .
- ^ Shervashidze, Nino, et al. "Núcleos de gráficos de Weisfeiler-lehman". Revista de investigación de aprendizaje automático 12.9 (2011).