A Cross-Interaction Neural Architecture for Submodular Functions

Submodular functions have applications in several domains, \eg, text, vision, speech, \etc. Recent works have proposed neural architectures that are submodular functions by design. However, they do not explicitly capture pairwise interactions between set elements. In this work, we begin with the characterization of pairwise submodular functions, which capture the pairwise interaction across the elements of the input set. We observe that pairwise interactions yield monotone supermodular functions, since the number of terms grows quadratically in terms of the input set size, which poses a significant challenge in converting it into a submodular function. To address it, we provide a novel result that a derivative rate-controlled concave function can transform a monotone supermodular function into a monotone submodular function. We also extend our results to monotone $\alpha$-submodular functions. Leveraging this characterization, we design multi-layer neural cross-interaction architectures for monotone submodular functions and analyze their expressivity. Finally, we perform several experiments which show that our model performs better than existing baselines.