Graph Neural Networks (GNNs) have become a popular tool for learning algorithmic tasks, in particular related to combinatorial optimization. In this talk, we will focus on the “algorithmic reasoning” task of learning a full algorithm. While GNNs have shown promising empirical results, their generalization properties are less well understood. We will try to understand in particular out-of-distribution generalization in widely used message passing GNNs, with an eye on applications in learning for optimization: what may be an appropriate metric for measuring shift? Under what conditions will a GNN generalize to larger graphs? In the last part of the talk, we will take a brief look at objective (loss) functions for learning with discrete objects, beyond GNNs. In particular, neural networks work best with continuous, high-dimensional spaces. Can we integrate this into appropriate loss functions?