The naive algorithm takes $O(n^4)$ time, , where $n$ is the number of vertices in the graph, as Stephen Bly explains.
It is possible to determine whether a graph contains a $4$-clique in $O(n^{3.334})$ time. See http://cs.stackexchange.com/a/18331/755 for a reference to the algorithm. I suspect their techniques could be extended to solve your problem (e.g., by enumerating all such cliques, and then you could check whether any of them satisfy your partition requirement) in the same running time. However, a caution: the techniques may be somewhat theoretical. The asymptotics may mean that their algorithm only becomes faster than naive solutions for large values of $n$.