Type:	Package
Title:	Rank in Similarity Graph Edge-Count Two-Sample Test (RISE)
Version:	0.1
Maintainer:	Doudou Zhou <ddzhou@nus.edu.sg>
Description:	Implements the Rank In Similarity Graph Edge-count two-sample test (RISE) for high-dimensional and non-Euclidean data. The method constructs similarity-based graphs, such as k-nearest neighbor graph (k-NNG), k-minimum spanning tree (k-MST), and k-minimum distance non-bipartite pairing (k-MDP), and evaluates rank-based within-sample edge counts with asymptotic and permutation p-values. For methodological details, see Zhou and Chen (2023) https://proceedings.mlr.press/v195/zhou23a.html.
License:	GPL-2 | GPL-3 [expanded from: GPL (≥ 2)]
Encoding:	UTF-8
Depends:	R (≥ 3.5.0)
Imports:	stats, ade4, nbpMatching
Suggests:	testthat (≥ 3.0.0), rmarkdown
RoxygenNote:	7.3.2
URL:	https://proceedings.mlr.press/v195/zhou23a.html
NeedsCompilation:	no
Packaged:	2025-11-09 08:21:43 UTC; doudou
Author:	Doudou Zhou [aut, cre], Hao Chen [aut]
Repository:	CRAN
Date/Publication:	2025-11-12 21:10:07 UTC

GraphRankTest: Rank-based Two-Sample Tests via Graph/Similarity-Induced Ranks

Description

The GraphRankTest package implements the RISE framework for two-sample testing using rank/graph matrices constructed from either raw data X, Y or a pre-computed similarity matrix S.

Main function

• RISE(): construct a nonnegative symmetric rank/graph matrix R (k-NN, k-MST, or minimum-distance pairing variants), and compute a Hotelling-type quadratic statistic with asymptotic and optional permutation p-values.

Method overview

From a similarity matrix S, the procedure builds R using one of:

• RgNN / RoNN: k-nearest-neighbor graph (graph-induced ranks vs. overall ranks)

• RgMST / RoMST: k-minimum spanning trees (graph-induced ranks vs. overall ranks)

• RoMDP: k-minimum-distance non-bipartite matchings (overall ranks)

Let U_x=\sum_{i,j\in X}R_{ij}, U_y=\sum_{i,j\in Y}R_{ij}. Under the permutation null, the centered vector (U_x,U_y) has a tractable covariance, yielding a chi-square(2) limiting test.

Getting started

library(GraphRankTest)
?RISE
help(package = "GraphRankTest")

Author(s)

Maintainer: Doudou Zhou ddzhou@nus.edu.sg (ORCID)

Authors:

• Hao Chen hxchen@ucdavis.edu (ORCID)

References

Zhou, D. and Chen, H. (2023). A new ranking scheme for modern data and its application to two-sample hypothesis testing. In COLT 2023, PMLR, 3615–3668.

See Also

RISE

Asymptotic Covariance of (Ux, Uy) under Permutation Null

Description

Supporting function for RISE and rTests.base. Computes the 2x2 asymptotic covariance matrix of (U_x, U_y) under the permutation null distribution.

Usage

Cov.asy(R, m, n)

Arguments

Value

2x2 covariance matrix.

Rank-based Two-Sample Tests on Similarity / Graph-Induced Rank Matrices

Description

RISE constructs a nonnegative, symmetric rank/graph matrix R from two samples X and Y (or from a pre-computed similarity matrix S), then computes a Hotelling-type quadratic statistic with an asymptotic chi-square p-value. Optionally, a permutation p-value is returned.

Usage

RISE(
  X = NULL,
  Y = NULL,
  S = NULL,
  sample1ID = NULL,
  sample2ID = NULL,
  k = 10,
  rank.type = "RgNN",
  perm = 0
)

Arguments

Details

From S (or from X, Y), the procedure constructs a symmetric matrix R with zero diagonal using one of the supported graph/ranking schemes. It then forms the within-group edge sums U_x = \sum_{i,j \in X} R_{ij} and U_y = \sum_{i,j \in Y} R_{ij}. The expectation vector and covariance matrix of (U_x, U_y) are derived under the permutation null distribution. The test statistic is

T = ( U_x - \mu_x, U_y - \mu_y ) \Sigma^{-1} \begin{pmatrix} U_x - \mu_x \\ U_y - \mu_y \end{pmatrix},

where \mu_x, \mu_y are the expected values and \Sigma is the covariance matrix. Under the null hypothesis, T is asymptotically chi-square distributed with 2 degrees of freedom.

Value

A list with components:

• test.statistic: quadratic form T_R.

• pval.approx: asymptotic p-value (chi-square, df = 2).

• pval.perm: permutation p-value (present only if perm > 0).

References

Zhou, D. and Chen, H. (2023). A new ranking scheme for modern data and its application to two-sample hypothesis testing. In Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023), PMLR, pp. 3615–3668.

See Also

rTests.base, Cov.asy

Examples

set.seed(1)
X <- matrix(rnorm(50*100, mean = 0), nrow=50)
Y <- matrix(rnorm(50*100, mean = 0.3), nrow=50)
# RgNN: graph-induced ranks from the k-nearest-neighbor graph
out.RgNN <- RISE(X = X, Y = Y, k = 10, rank.type = "RgNN", perm = 1000)
out.RgNN

# RoNN: overall ranks obtained by ordering edges from the k-NN graph
out.RoNN <- RISE(X = X, Y = Y, k = 10, rank.type = "RoNN", perm = 1000)
out.RoNN

# RgMST: graph-induced ranks from layered minimum spanning trees

out.RgMST <- RISE(X = X, Y = Y, k = 10, rank.type = "RgMST", perm = 1000)
out.RgMST


# RoMST: overall ranks obtained by ordering edges in the MST

out.RoMST <- RISE(X = X, Y = Y, k = 10, rank.type = "RoMST", perm = 1000)
out.RoMST


# RoMDP: overall ranks obtained by ordering edges from minimum-distance pairings

out.RoMDP <- RISE(X = X, Y = Y, k = 10, rank.type = "RoMDP", perm = 1000)
out.RoMDP

Within-Group Sums (Ux, Uy)

Description

Supporting function for RISE. Given a symmetric rank/graph matrix R, compute the within-group rank sums for the two samples.

Usage

r.stat(R, sample1ID, sample2ID)

Arguments

Value

Numeric vector c(Ux, Uy).

Core Test on a Given Rank/Graph Matrix R

Description

Internal function used by RISE once a rank/graph matrix R is constructed. It computes the within-group sums, asymptotic covariance, quadratic statistic, and (optionally) permutation-based p-value.

Usage

rTests.base(R, sample1ID, sample2ID, perm = 0)

Arguments

Value

See RISE().