We consider $U$-statistics on row-column exchangeable matrices, arrays invariant to separate permutations of rows and columns and common in bipartite data. Under the standard dissociation assumption, we develop a graph-indexed analogue of the Hoeffding decomposition tailored to RCE dependence. We present a new decomposition based on orthogonal projections onto probability spaces generated by sets of Aldous-Hoover-Kallenberg variables. These sets are indexed by bipartite graphs, enabling the application of graph-theoretic concepts to describe the decomposition. This framework provides new insights into the characterization of $U$-statistics on row-column exchangeable matrices, particularly their asymptotic behavior, including in degenerate cases. Notably, the limit distribution depends only on specific terms in the decomposition, corresponding to non-zero components indexed by the smallest graphs, namely the principal support graphs. We show that the asymptotic behavior of a $U$-statistic is characterized by the properties of its principal support graphs. The number of nodes in these graphs (the principal degree) dictates the convergence rate to the limit distribution, with degeneracy occurring if and only if this number is strictly greater than 1. Furthermore, when the principal support graphs are connected, the limit distribution is Gaussian, even in degenerate cases. Applications to network analysis illustrate these findings.