Shuffling of tokens on a graph using local swaps
Suppose your graph was a path.  I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries.  Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).