Succinct circuit representation of graphs The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:

END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0n) = 0n != S(0n), find an input x in {0,1}n such that P(S(x)) != x or S(P(x)) != x != 0n.

Circuits or algorithms such as S and P implicitly define an exponentially large graph that is only revealed on a query-by-query basis (to keep the problem in PSPACE!), e.g. Papadimitrou's paper.

However, I don't understand how one would design a circuit that enables arbitrary graphs (if there is a systematic structure to the graph, it appears much easier to find the circuit). For instance, how would one design a polynomially-sized circuit that represents an exponentially-long directed line, with an all-0 label for the source vertex and randomly assigned binary labels to all other vertices? This seems to be implicit in the PPAD-related papers.

The closest I've come from a search online is Galperin/Widgerson's paper, but the circuit described there takes two vertex labels and returns a Boolean answer to "Are these vertices adjacent?"

So, how would you design a polynomially-sized circuit of an exponentially-sized graph that takes an n-bit input and outputs the n-bit label of its predecessor or successor, respectively? Or even, does someone know of a resource that explains this well?
Your question seems to be asking: how does one represent arbitrary graphs (or even arbitrary path graphs) as a circuit of polynomial size? The answer is, you don't. The number of different path graphs with 2n vertices is (2n)!, far more than the number of different circuits with nc gates (exponential in nc log n). So almost all graphs with this many vertices cannot be represented by a succinct circuit.

Therefore, as you hint, in some sense only graphs that have a high degree of structure can be represented in this way. That's what makes complexity classes like PPAD interesting: despite the structure that we know the input graphs to the EOL problem must have, we don't seem to know how to take advantage of the structure to solve the problem efficiently.

If I'm misunderstanding your question and you're really asking: how does one make a circuit that even meets the input requirements for EOL, for even a very highly structured graph: try the path graph that connects vertex x (considered as a number in binary) to x-1 and x+1, with ends at zero and at 2^n-1. Or if you want something less trivial that seems more difficult to solve EOL for: let E and D be the encryption and decryption functions for a fixed key in your favorite cryptosystem, let the neighbors of x in the graph be E(x) and D(x), and let the ends of the line be 0 and D(0).