Algorithm for finding cliques
Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its output is a clique of size at least $n^\epsilon$. If so, output $n^\epsilon$, otherwise output $1$.

You might want to look into the planted clique problem, in which the goal is to find a clique "planted" inside a uniformly random graph. This is possible in polytime (with high probability) as long as the clique is large enough, $\Omega(\sqrt{n})$. Your case may be different, but similar ideas might work in practice.