The Role of graph structure in the generalization performance of anyCSP

Abstract

Treball fi de màster de: Master in Intelligent Interactive Systems

Supervisor: Vicenç Gómez

Neural approaches to constraint satisfaction problems (CSPs) have demonstrated competitive performance on various combinatorial optimization tasks, yet their generalization capabilities across different structural patterns remain underexplored. Understanding how neural CSP solvers transfer learned strategies between graph topologies with distinct connectivity patterns is important for developing robust neural combinatorial optimization approaches. We present a systematic study of structural generalization in neural CSP solvers, focusing on the AnyCSP model’s ability to adapt across diverse graph structures. We conduct two complementary experiments using the k-coloring problem as a controlled testbed for evaluating structural transfer capabilities. The first experiment examines cross-connectivity generalization by training models exclusively on one graph type and testing their performance on the remaining types. This design allows us to isolate the impact of structural training bias on generalization across topologically distinct problem classes. The second experiment performs connectivity ablation by training on pairwise combinations of graph types and evaluating their effectiveness on real-world structured benchmark instances. Our cross-connectivity results reveal that models trained on geometric and scale free structures achieve a success rates of 91.4% and 92.2% when tested on random graphs. However, the reverse directions yield drastically different outcomes, with only 14.8–60% success rates, indicating that models trained on structurally simpler topologies cannot adapt to more complex patterns. The connectivity ablation study shows that training combinations that include geometric graphs consistently outperform other pairings on structured benchmark instances. Our work provides theoretical insights into the mechanisms underlying neural CSP generalization and practical suggestions for developing more robust neural approaches to combinatorial optimization problems with complex graph structures.