A new robust graph for graph-based methods

Graph-based two-sample tests and change-point detection are powerful tools for analyzing high-dimensional and non-Euclidean data, as they do not impose distributional assumptions and perform effectively across a wide range of scenarios. These methods utilize a similarity graph constructed from the observations, with $K$-nearest neighbor graphs or $K$-minimum spanning trees being the current state-of-the-art choices. However, in high-dimensional settings, these graphs tend to form hubs -- nodes with disproportionately large degrees -- and graph-based methods are sensitive to hubs. To address this issue, we propose a robust graph that is significantly less prone to forming hubs in high-dimensional settings. Incorporating this robust graph can substantially improve the power of graph-based methods across various scenarios. Furthermore, we establish a theoretical foundation for graph-based methods using the proposed robust graph, demonstrating its consistency under fixed alternatives in both low-dimensional and high-dimensional contexts.