An algorithm for simulating permutation tests of graph-intersection measures of association

This paper proposes an algorithm for a randomization test of the graph-theoretic measure of association proposed by Friedman and Rafsky [1983. Graph-theoretic measures of multivariate association and prediction. Ann. Statist. 11(2), 377–391]. Treating the simulation as a random walk on the set of graphs isomorphic to the observed graph, the simulation can run with only one reference to the interpoint distance matrix used to form the graphs. This fact allows the randomization test for association to be run quickly for large, high-dimensional, sparse data. An example of a test for dependence between word use and time in US Supreme Court cases is presented.