The motivation for this question is counting cycles in directed graphs with millions of vertices.
Given a large (not necessarily symmetric) adjacency matrix $A \in \{0, 1\}^{n \times n}$, where $n \sim 10^6$, and $1 \leq k \leq n$, we aim to approximate the trace (i.e., the sum of only the diagonal entries) of the $k$-th power of $A$, i.e., $A^k$.
I know that if we can compute all the eigenvalues $\lambda_i$'s of $A$ then $$\operatorname{Trace} \left(A^k\right) = \sum_{i = 1}^n \lambda_i^k$$ However, for large $A$, even computing all the eigenvalues would be impractical. One idea I have is to simply obtain the largest eigenvalues, say, the largest $m \ll n$ eigenvalues, then use the real part of $\sum_{i = 1}^m \lambda_i^k$ as an approximation. Certainly, we cannot really have a guarantee, but this partial sum at least provides some information of the interested value.