  The graphical balls-into-bins process is a generalization of the classical
2-choice balls-into-bins process, where the bins correspond to vertices of an
arbitrary underlying graph $G$. At each time step an edge of $G$ is chosen
uniformly at random, and a ball must be assigned to either of the two endpoints
of this edge. The standard 2-choice process corresponds to the case of $G=K_n$.
  For any $k(n)$-edge-connected, $d(n)$-regular graph on $n$ vertices, and any
number of balls, we give an allocation strategy that, with high probability,
ensures a gap of $O((d/k) \log^4\hspace{-1pt}n \log \log n)$, between the load
of any two bins. In particular, this implies polylogarithmic bounds for natural
graphs such as cycles and tori, for which the classical greedy allocation
strategy is conjectured to have a polynomial gap between the bin loads. For
every graph $G$, we also show an $\Omega((d/k) + \log n)$ lower bound on the
gap achievable by any allocation strategy. This implies that our strategy
achieves the optimal gap, up to polylogarithmic factors, for every graph $G$.
  Our allocation algorithm is simple to implement and requires only
$O(\log(n))$ time per allocation. It can be viewed as a more global version of
the greedy strategy that compares average load on certain fixed sets of
vertices, rather than on individual vertices. A key idea is to relate the
problem of designing a good allocation strategy to that of finding suitable
multi-commodity flows. To this end, we consider R\"{a}cke's cut-based
decomposition tree and define certain orthogonal flows on it.
