Many search problems in artificial intelligence (such as searching the game tree of a chess game, or searching for solutions to puzzles like the Rubik's cube, or more generally searching for sequences of actions to perform in order to accomplish some desired goal) are, in effect, algorithms on infinite graphs, even though the desired answer is a finite path. It is certainly possible to perform algorithms on such graphs, if they are represented implicitly.
But it is also true that mathematics may be useful even if it is not the mathematics of problems that can be solved by algorithms. Infinite graphs can be used to model birth and death processes (e.g. how do our rules for inheritance of names, and the rates at which people are born and die, lead to nonuniform distributions of family names among different human cultures?), to give a framework for approaching questions about mathematical symmetries (via Cayley graphs, which are often infinite), to provide models for reasoning about systems of logic (see Rado graph and saturated model), etc.