How to efficiently select the initial node to start a search in a Skip Graph
First, the skip graph is a distributed data structure. There is no reason to use it in a single machine context.

For a singly-linked skip list (on a single machine), you would start at the beginning. This is trivial to find; you just hold a pointer to the first node. For a doubly-linked skip list, you could start at any node, though unless you had some cursor-like abstraction, you'd presumably start at the beginning for most operations anyway.

A skip graph is effectively a collection of doubly-linked skip lists that share structure. There is no need to start at the beginning. This allows the machine on which to initiate an operation to be chosen arbitrarily. In a public peer-to-peer context, you are usually only aware of one or a few machines. In a data-center context, usually a load balancer will choose the machine.

A machine will generally host many nodes of the skip graph. It's not clear to me how much it matters to pick a local node at random. Typically, only some of the nodes will be connected to nodes on other machines, so picking any other node is the same as picking one of these as far as spreading load between the machines. Nevertheless, if you wanted to pick randomly from the local nodes there are a variety of approaches. Since you are only concerned about local nodes, you are free to use any non-distributed data structure to keep track of them. For example, a size-balanced tree would work. You would pick a number between 0 and the number of local nodes, and then do a rank query on a size-balanced tree containing (pointers to) the local nodes. Alternatively, you could probably get something close to a uniform distribution on average by assuming that the any one of the local portions of the skip lists making up the local portion of the skip graph is perfectly "balanced". This lets you estimate how many nodes you are skipping when you traverse a link at a given level which lets you do an approximate rank query directly against (the local portion of) the skip graph. Neither of these approaches is likely to affect the asymptotic complexity of any operation.