In the Graph Representation Learning book by Hamilton (P. 20), it is mentioned that :
The largest eigenvalue can be used to approximate the growth in the number of paths. In particular, if we define $p_i ∈ R^{|V|}$ as the vector counting the number of length-i paths between node u and all other nodes, then we have that for large i
$$\mathbf{A p}_{i}=\lambda_{1} \mathbf{p}_{i-1}$$
since $p_i$ will eventually converge to the dominant eigenvector of the graph. This implies that the number of paths between two nodes grows by a factor of λ1 at each iteration, where we recall that λ1 is the largest eigenvalue of A.
I understand that the number of length-i walks between two nodes is computed by the corresponding element of the adjacency matrix power $A^i$, but I don't understand the latter part stating that "the number of paths between two nodes grows by a factor of λ1 at each iteration". Is there a hint or proof for this?
Since $A$ is a symmetric matrix, we can find a basis of eigenvectors: vectors $\mathbf v^{(1)}, \mathbf v^{(2)}, \dots, \mathbf v^{(n)}$ such that $A\mathbf v^{(i)} = \lambda_i \mathbf v^{(i)}$.
If we start at the $i^{\text{th}}$ node, then the vector $A^\ell \mathbf e^{(i)}$ (where $\mathbf e^{(i)}$ has a $1$ in the $i^{\text{th}}$ position and $0$'s everywhere else) counts the number of length-$\ell$ walks to all other nodes.
We can write $\mathbf e^{(i)}$ in the eigenbasis as $c_1 \mathbf v^{(1)} + c_2 \mathbf v^{(2)} + \dots + c_n \mathbf v^{(n)}$ for some constants $c_1, c_2, \dots, c_n$. If we do, then we get $$ A^{\ell} \mathbf e^{(i)} = A^\ell(c_1 \mathbf v^{(1)} + \dots + c_n \mathbf v^{(n)}) = c_1 \lambda_1^\ell \mathbf v^{(1)} + \dots + c_n \lambda_n^\ell \mathbf v^{(n)}. $$ No matter what $c_1, \dots, c_n$ and $\mathbf v^{(1)}, \dots, \mathbf v^{(n)}$ are, as long as $c_1 \ne 0$, the first term will dominate when $\ell$ is large enough, because $\lambda_1^\ell$ grows exponentially faster than all other $\lambda_i^\ell$ terms. So the number of length-$\ell$ walks from the $i^{\text{th}}$ node to any other node will be proportional to $\lambda_1^\ell$, as desired.
There are actually some quibbles here. What if $c_1 = 0$? Or what if the $j^{\text{th}}$ component of $\mathbf v^{(1)}$ is $0$, in which case the number of $i-j$ walks will not be affected by the first term of the sum? (These are actually the same quibble, because the basis of eigenvectors is orthonormal, so $c_1$ is equal to $\mathbf v^{(1)} \cdot \mathbf e^{(i)}$, which is the $i^{\text{th}}$ component of $\mathbf v^{(1)}$.)
Indeed, this could happen. For example, if our graph has two components with different largest eigenvalues, the largest eigenvalue of one component will not affect the number of walk between vertices in the other component.
But that's essentially the only problematic case. There will always be some vertex $v$ from which the number of walks grows as fast as $\lambda_1^\ell$, because $\mathbf v^{(1)}$ cannot have a zero in every coordinate. But then, if all other vertices can get to vertex $v$, they can also benefit from the large growth rate of walks starting from $v$.