An Experimental Study of Variable Neighborhood Search for General-Purpose Subgraph Optimization in Parallel Systems - Carvalho, Diogo; Moreira, Mayron; Dias, Vinícius (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD), 2025)
Many network analysis tasks over large graphs involve finding subgraphs that optimize a given scoring function. Scoring functions are defined according to the analysis objective and thus, they can be very diverse (e.g. high density, high reachability, high entropy). In this context we study the Connected Subgraph Optimization Problem (CSOP) in which the goal is to find a subgraph that optimizes a given scoring function within a graph. Such tasks are computationally intensive since (i) they require handling an exponential search space over large graphs and (ii) they involve very skewed and sparse real graphs, which is why algorithm scalability and efficiency are central for feasibility. In this work we provide an experimental characterization of the potential of Variable Neighborhood Search metaheuristic (VNS) in providing a competitive and efficient parallel framework for the CSOP problem. Our results show that VNS offers competitive, near-ideal scalability for accelerating CSOP, but its effectiveness can be limited by expensive scoring functions, branch mispredictions, and both backend and frontend CPU bottlenecks.