  We propose a novel graph-based approach for semantic parsing that resolves
two problems observed in the literature: (1) seq2seq models fail on
compositional generalization tasks; (2) previous work using phrase structure
parsers cannot cover all the semantic parses observed in treebanks. We prove
that both MAP inference and latent tag anchoring (required for
weakly-supervised learning) are NP-hard problems. We propose two optimization
algorithms based on constraint smoothing and conditional gradient to
approximately solve these inference problems. Experimentally, our approach
delivers state-of-the-art results on Geoquery, Scan and Clevr, both for i.i.d.
splits and for splits that test for compositional generalization.
