Resumen: En los últimos años, ha habido un creciente interés en comprender el poder expresivo de las redes neuronales gráficas (GNN) relacionándolas con idiomas lógicos. Esta investigación ha sido inicializada por un resultado influyente de Barceló et al. (2020), quienes mostraron que la lógica modal graduada (o un fragmento protegido de la lógica C2), caracteriza la expresividad lógica de los GNN de combina agregada. Como un “ problema abierto desafiante ”, dejaron la pregunta de si C2 completo caracteriza la expresividad lógica de los GNN de lectura de combina agregada. Esta pregunta ha permanecido sin resolver a pesar de varios intentos. En este documento, resolvemos el problema abierto anterior al demostrar que la expresividad lógica de los GNN de lectura de combina agregada excede estrictamente la de C2. Este resultado se mantiene sobre gráficos no dirigidos y dirigidos. Más allá de sus implicaciones para los GNN, nuestro trabajo también conduce a ideas puramente lógicas sobre el poder expresivo de las lógicas infinitarias.
Publicado Originalme en export.arxiv.org El 10 de agosto de 2025.
Ver Fuente Original
