Algoritmos heurísticos para la búsqueda de grafos contrafactuales en redes cerebrales

Abstract

En neurociencias, los grafos contrafactuales se utilizan para explicar las decisiones tomadas en la clasificación de redes cerebrales y los factores esenciales que influyen en los resultados de dicha clasificación. El objetivo de este trabajo es implementar dos algoritmos heurísticos para la búsqueda de grafos contrafactuales en redes cerebrales. Nuestra propuesta parte de las ideas de los algoritmos diseñados por Abrate y Bonchi (2021). Estos algoritmos tienen como objetivo encontrar un grafo contrafactual a partir de un grafo inicial dado como entrada, utilizando una búsqueda heurística hacia adelante y hacia atrás respectivamente. La finalidad es encontrar un grafo que tenga una gran similitud estructural con el grafo original, pero que sea clasificado en una clase diferentes por un clasificador de caja negra. El primer algoritmo añade y elimina aristas gradualmente para encontrar un primer grafo contrafactual. El segundo algoritmo realiza el mismo método para disminuir la distancia entre el grafo contrafactual encontrado y el grafo original, con el propósito de encontrar un grafo que minimice la distancia de edición con el grafo dado. Finalmente, se analizan los algoritmos mencionados en términos de la distancia de edición, el número de redes procesados por ambos algoritmos y el promedio de las aristas entre los grafos procesados. Estos análisis proporcionan información sobre la eficiencia de los algoritmos implementados y la calidad de los grafos contrafactuales generados.

In neuroscience, counterfactual graphs are used to explain the decisions made in a classification based on brain activities and the significant factors that influence the outcomes of such classification. The core of this project involves implementing two heuristic algorithms for the search of counterfactual graphs in brain networks. Our proposal is based on the ideas of the algorithms designed by Abrate and Bonchi (2021). These algorithm aim to find a counterfactual graph from an initial graph provided as input using forward and backward heuristic search, respectively. The goal is to discover a graph that closely resembles the original one but is classified differently by the black-box classifier. The first algorithm gradually adds and removes edges in order to obtain a contrafactual graph. The second one employs the same approach to decrease the distance between the contrafactual graph found and the original graph. Its purpose is to discover an optimal graph for the given input graph. Finally, the mentioned algorithms will be analyzed in terms of edit distance, the number of networks processed by both algorithms, and the average number of edges between the processed graphs. These experiments will provide information about the efficiency of the implemented algorithms and the quality of the generated contrafactual graphs.