We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < \alpha < 1$<alternatives> <inline-graphic xlink:href="mukherjee-ieq1-2527643.gif"/></alternatives>, we define the notion of an $\alpha$<alternatives> <inline-graphic xlink:href="mukherjee-ieq2-2527643.gif"/></alternatives>-maximal clique in an uncertain graph. We present matching upper and lower bounds on the number of $\alpha$<alternatives><inline-graphic xlink:href="mukherjee-ieq3-2527643.gif"/> </alternatives>-maximal cliques possible within a (uncertain) graph. We present an algorithm to enumerate $\alpha$<alternatives> <inline-graphic xlink:href="mukherjee-ieq4-2527643.gif"/></alternatives>-maximal cliques whose worst-case runtime is near-optimal, and an experimental evaluation showing the practical utility of the algorithm.