This is a very partial answer. For simple random walks on Cayley graphs, linear growth of $H_n$ implies that for any $\epsilon>0$, the inequality $r_n \le \exp((\epsilon-1/2)n)$ must hold for infinitely many $n$, see Theorem 1.1 in [1].

For infinite connected graphs of bounded degree, it is possible for $H_n$ to grow linearly while $r_n \asymp cn^{-3/2}$. A simple example is a graph $G$ obtained by adjoining an infinite path to the root of an infinite binary tree. I suspect that slower decay of $r_n$ is not compatible with linear growth of entropy.

(Edit: @tmh Indicated in a comment below that one could get close to decay rate of $1/n$ for $r_n$. So perhaps $1/n$ is a barrier? recall that without any entropy assumptions, the slowest possible decay rate for $r_n$ on an infinite graph of bounded degree is $\;$ const.$/\sqrt{n}$.)

[1] Peres, Yuval, and Tianyi Zheng. "On groups, slow heat kernel decay yields liouville property and sharp entropy bounds." International Mathematics Research Notices 2020, no. 3 (2020): 722-750. https://arxiv.org/abs/1609.05174

This is a very partial answer. For simple random walks on Cayley graphs, linear growth of $H_n$ implies that for any $\epsilon>0$, the inequality $r_n \le \exp((\epsilon-1/2)n)$ must hold for infinitely many $n$, see Theorem 1.1 in [1].

For infinite connected graphs of bounded degree, it is possible for $H_n$ to grow linearly while $r_n \asymp cn^{-3/2}$ for even $n$. A simple example is a graph $G$ obtained by adjoining an infinite path to the root of an infinite binary tree. I suspect that slower decay of $r_n$ is not compatible with linear growth of entropy.

(Edit: @tmh Indicated in a comment below that one could get close to decay rate of $1/n$ for $r_n$. So perhaps $1/n$ is a barrier? recall that without any entropy assumptions, the slowest possible decay rate for $r_n$ on an infinite graph of bounded degree is $\;$ const.$/\sqrt{n}$.)

[1] Peres, Yuval, and Tianyi Zheng. "On groups, slow heat kernel decay yields liouville property and sharp entropy bounds." International Mathematics Research Notices 2020, no. 3 (2020): 722-750. https://arxiv.org/abs/1609.05174

This is a very partial answer. For simple random walks on Cayley graphs, linear growth of $H_n$ implies that for any $\epsilon>0$, the inequality $r_n \le \exp((\epsilon-1/2)n)$ must hold for infinitely many $n$, see Theorem 1.1 in [1].

For infinite connected graphs of bounded degree, it is possible for $H_n$ to grow linearly while $r_n \asymp cn^{-3/2}$. A simple example is a graph $G$ obtained by adjoining an infinite path to the root of an infinite binary tree. I suspect that slower decay of $r_n$ is not compatible with linear growth of entropy.

[1] Peres, Yuval, and Tianyi Zheng. "On groups, slow heat kernel decay yields liouville property and sharp entropy bounds." International Mathematics Research Notices 2020, no. 3 (2020): 722-750. https://arxiv.org/abs/1609.05174

This is a very partial answer. For simple random walks on Cayley graphs, linear growth of $H_n$ implies that for any $\epsilon>0$, the inequality $r_n \le \exp((\epsilon-1/2)n)$ must hold for infinitely many $n$, see Theorem 1.1 in [1].

For infinite connected graphs of bounded degree, it is possible for $H_n$ to grow linearly while $r_n \asymp cn^{-3/2}$. A simple example is a graph $G$ obtained by adjoining an infinite path to the root of an infinite binary tree. I suspect that slower decay of $r_n$ is not compatible with linear growth of entropy.

(Edit: @tmh Indicated in a comment below that one could get close to decay rate of $1/n$ for $r_n$. So perhaps $1/n$ is a barrier? recall that without any entropy assumptions, the slowest possible decay rate for $r_n$ on an infinite graph of bounded degree is $\;$ const.$/\sqrt{n}$.)

[1] Peres, Yuval, and Tianyi Zheng. "On groups, slow heat kernel decay yields liouville property and sharp entropy bounds." International Mathematics Research Notices 2020, no. 3 (2020): 722-750. https://arxiv.org/abs/1609.05174