  We study the problem of two-sample comparison with categorical data when the
contingency table is sparsely populated. In modern applications, the number of
categories is often comparable to the sample size, causing existing methods to
have low power. When the number of categories is large, there is often
underlying structure on the sample space that can be exploited. We propose a
general non-parametric approach that utilizes similarity information on the
space of all categories in two sample tests. Our approach extends the
graph-based tests of Friedman and Rafsky (1979) and Rosenbaum (2005), which are
tests base on graphs connecting observations by similarity. Both tests require
uniqueness of the underlying graph and cannot be directly applied on
categorical data. We explored different ways to extend graph-based tests to the
categorical setting and found two types of statistics that are both powerful
and fast to compute. We showed that their permutation null distributions are
asymptotically normal and that their $p$-value approximations under typical
settings are quite accurate, facilitating the application of the new approach.
The approach is illustrated through several examples.
