  The ability to engineer novel proteins with higher fitness for a desired
property would be revolutionary for biotechnology and medicine. Modeling the
combinatorially large space of sequences is infeasible; prior methods often
constrain optimization to a small mutational radius, but this drastically
limits the design space. Instead of heuristics, we propose smoothing the
fitness landscape to facilitate protein optimization. First, we formulate
protein fitness as a graph signal then use Tikunov regularization to smooth the
fitness landscape. We find optimizing in this smoothed landscape leads to
improved performance across multiple methods in the GFP and AAV benchmarks.
Second, we achieve state-of-the-art results utilizing discrete energy-based
models and MCMC in the smoothed landscape. Our method, called Gibbs sampling
with Graph-based Smoothing (GGS), demonstrates a unique ability to achieve 2.5
fold fitness improvement (with in-silico evaluation) over its training set. GGS
demonstrates potential to optimize proteins in the limited data regime. Code:
https://github.com/kirjner/GGS
