Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m
Unfortunately this problem is NP-hard, meaning the best exact algorithm you can hope for will take exponential time in the worst case.
It is NP-hard because any algorithm that would solve this problem can also be used to solve the NP-hard problem Independent Set (IS), in which we have a graph $G = (V, E)$ and an integer $k$, and ask whether there is a subset $X \subseteq V$ of $k$ vertices such that no pair of vertices in this subset are adjacent. Given any algorithm for solving your problem, any instance $G$ of IS can be solved by giving this algorithm the adjacency matrix for $G$, in which every element is 1 (indicating a pair of vertices connected by an edge) or 0 (indicating a pair of vertices that are not) as input, together with $N=k$; there is a size-$k$ independent set in $G$ if and only if there is a subset of $N$ rows/columns in the matrix having sum $N$ (i.e., all diagonal elements are 1 and the rest are 0).