In the context of stochastic search, once regions of high performance are found,
having the property that small changes in the candidate solution correspond to
searching nearby neighborhoods provides the ability to perform effective local
optimization. To achieve this, Gray Codes are often employed for encoding ordinal
points or discretized real numbers. In this paper, we present a method to label
similar and/or close points within arbitrary graphs with small Hamming distances.
The resultant point labels can be viewed as an approximate high-dimensional variant
of Gray Codes. The labeling procedure is useful for any task in which the solution
requires the search algorithm to select a small subset of items out of many. A
large number of empirical results using these encodings with a combination of
genetic algorithms and hill-climbing are presented.