Returning the size of the largest clique in a graph
First of all, start passing things by const reference more.  You're passing both nodes and edges by value, which will make a copy.
Instead of looping through the containers by index, you should use iterators.
Pushing tmp into previous_cliques will make a copy.


The following may be faster:

std::vector&lt;VertexID&gt; tmp(1);
for (...) {
    tmp[0] = nodes[i];
    previous_cliques.push_back(tmp);
}


(If you're worried about scope, just wrap it in braces.)


Checking for emptiness with size() may be less efficient than with empty(); unlikely in the case of a vector, though (I think size() must be O(1)).
You're not showing us isClique, so it's hard to comment on that.  Make sure you're passing be const reference there.  Also consider not copying previous_cliques until you know you want to push it into new_cliques and instead handling nodes[i] as a special case (may be faster, may be slower).
If you're using C++11, the emplace functions are your friend.