We consider a class of sparsity-inducing regularization terms based on submodular functions. While earlier work has focused on non-decreasing functions, we explore symmetric submodular functions and their Lovasz extensions. We show that the Lovasz extension may be seen as the convex envelope of a function that depends on level sets: this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not on the supports of the underlying predictors. We provide a unified set of optimization algorithms (such as proximal operators), and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions, we give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics, and on noisy cuts in graphs.