I know at least one special case where your second question makes sense.  If $G$ is a compact group, it has a category $\text{Rep}(G)$ of finite-dimensional unitary representations which break up into direct sums of irreducible representations.  Fix a representation $V$ such that every irreducible representation appears in $V^{\otimes n}$ for some $n$.  One can construct a graph $\Gamma(V)$ whose vertices are the irreducible representations of $G$ and where the number of edges from $A$ to $B$ is the multiplicity by which $B$ appears in $A \otimes V$.  By the assumption, $\Gamma(V)$ is connected, and its combinatorial properties encode information about the behavior of the tensor powers of $V$, hence behavior about $G$.  

When $G$ is finite, this graph has the property that its eigenvalues are precisely the character values $\chi_V(g)$ as $g$ runs through all conjugacy classes.  But the great thing is that this statement still makes sense even when $G$ is infinite in a sense which is made precise <a href="https://qchu.wordpress.com/2010/03/07/walks-on-graphs-and-tensor-products/">in this blog post</a>.

Finally, if $G$ is abelian, all of the finite-dimensional irreducible representations are one-dimensional.  They can be identified with the <a href="https://en.wikipedia.org/wiki/Pontryagin_duality">Pontryagin dual</a> $G^{\vee}$, which is discrete, and $\Gamma(V)$ becomes precisely the Cayley graph of $G^{\vee}$ with respect to the generators that make up $V$!  So this is one sense in which the Cayley graph of an infinite group gives you algebraic data, but about its **dual** group.