On the tightness of graph-based statistics

We establish tightness of graph-based stochastic processes in the space D[0+ϵ,1−ϵ] with ϵ>0 that allows for discontinuities of the first kind. The graph-based stochastic processes are based on statistics constructed from similarity graphs. In this non-parametric setting, the classic characterization of tightness is intractable, making it difficult to obtain convergence of the limiting distributions for graph-based stochastic processes. We take an alternative approach and study the behavior of the higher moments of the graph-based test statistics. We show that, under mild conditions of the graph, tightness of the stochastic process can be established by obtaining upper bounds on the graph-based statistics’ higher moments. Explicit analytical expressions for these moments are provided. The results are applicable to generic graphs, including dense graphs where the number of edges can be of higher order than the number of observations. Numerical studies are presented to provide insight as to when tightness holds, and potential extensions to other scenarios are explored.