PaperlayerView exact revision on arXiv

Source-linked AI summary

A new graph-based two-sample test for multivariate and object data

Hao Chen, Jerome H. Friedman

arXiv:1307.6294v6stat.ME

TL;DR

Existing similarity-graph two-sample tests have limited practical sensitivity across location and scale alternatives, motivating a more general procedure for multivariate and non-Euclidean data. The paper constructs a graph on pooled observations and defines a statistic using a common pattern across alternatives. The resulting test has good power for general alternatives, with an asymptotic permutation null distribution and applications to matched-study covariate balance and network comparisons.

  • Problem

    Existing similarity-graph tests lack practical power for both location and scale alternatives, while high-dimensional testing becomes increasingly difficult.

  • Method

    The paper proposes a graph-based two-sample statistic built from a similarity graph on pooled observations and a common pattern across location and scale alternatives.

  • Results

    The test has good power for detecting general alternatives in multivariate and non-Euclidean data, and its test statistic has an asymptotic permutation null distribution.

  • Takeaways & Limitations

    The proposed test supports two-sample comparisons across multivariate and non-Euclidean data when a similarity measure is available.

  • Takeaways & Limitations

    The paper identifies an optimal graph density for each application, with the 5-MST suggested as a reasonable initial choice in practice.

Abstract

from arXiv · show

Two-sample tests for multivariate data and especially for non-Euclidean data are not well explored. This paper presents a novel test statistic based on a similarity graph constructed on the pooled observations from the two samples. It can be applied to multivariate data and non-Euclidean data as long as a dissimilarity measure on the sample space can be defined, which can usually be provided by domain experts. Existing tests based on a similarity graph lack power either for location or for scale alternatives. The new test utilizes a common pattern that was overlooked previously, and works for both types of alternatives. The test exhibits substantial power gains in simulation studies. Its asymptotic permutation null distribution is derived and shown to work well under finite samples, facilitating its application to large data sets. The new test is illustrated on two applications: The assessment of covariate balance in a matched observational study, and the comparison of network data under different conditions.

1 Introduction

Two-sample testing for multivariate and object data remains challenging, especially when alternatives differ in location or scale. The paper proposes a graph-based nonparametric test designed to address both.

  • Multivariate testing becomes difficult when many features must be analyzed jointly and may contain underlying structure.
  • Similarity-graph tests extend two-sample comparisons to non-Euclidean data when a similarity measure can be defined.
  • Existing graph-based tests can lack practical power for either location or scale alternatives, despite being proposed for general alternatives.
  • The edge-count test may have low or no power for scale alternatives in moderate or high dimensions unless sample sizes are astronomical.
  • Other graph-based procedures show complementary weaknesses: Smirnov-type tests lack power for scale-only alternatives, while radial Smirnov and degree tests lack power for location-only alternatives.
  • The proposed test uses a common pattern across location and scale alternatives and is intended to work for general location-scale alternatives.
  • The paper derives an asymptotic permutation null distribution and evaluates finite-sample p-value approximation, simulations, and applications to covariate balance and network data.

2 The problem

In moderate or high dimensions, similarity graphs can fail under scale differences because outer-layer observations connect preferentially to an inner layer. The paper therefore retains ordinary closeness while changing the test statistic.

  • Under a representative mixed mean-and-variance scenario, the MST had 979 between-sample edges versus a null expectation of 1,000 and did not reject.
  • The same MST contained 991 within-sample edges for X but only 29 for Y, because nearly all Y points found X points closer.
  • The samples formed two layers, with X in the inner layer and Y in the outer layer.
  • In moderate to high dimensions, outer-layer points often find inner-layer points closer than other outer-layer points under scale differences.
  • Consequently, ordinary distance-based edge-count graphs may not work for scale alternatives at moderate or high dimension with realistic sample sizes.
  • Defining closeness by similarity of distances to the center can address scale changes, but depends heavily on the alternative type.
  • The proposed approach instead uses usual closeness to construct the graph and a statistic exploiting a common pattern across both alternative types.

3 A new test statistic

The paper defines a graph-based statistic from within-sample edge counts, standardizing their joint deviations from permutation-null expectations. Its construction is designed to detect both location and scale alternatives, including cases where the two within-sample counts deviate in opposite directions.

  • Power mechanism: S is sensitive to location and scale alternatives because it aggregates deviations in either direction rather than requiring both within-sample counts to increase.Under moderate or high-dimensional scale alternatives, the smaller-variance sample is expected to have more within-sample edges while the larger-variance sample has fewer.
  • Graph construction: The test pools two samples and constructs a no-multi-edge similarity graph using a notion of closeness, such as L2 or L1 distance.The graph may also be supplied directly by domain experts rather than derived from a similarity measure.
  • Edge counts: R1 and R2 count within-sample edges for samples X and Y, while R0 counts between-sample edges.The observations are pooled and assigned group indicators before edge counts are computed.
  • Test statistic: The new statistic S standardizes the vector of deviations (R1−μ1, R2−μ2) using its permutation-null covariance matrix Σ.Here μ1 and μ2 are null expectations, and Σ is the covariance matrix of the two within-sample edge counts.
  • Graph conditions: The statistic is undefined for equal-degree graphs and perfect star-shaped graphs, and its inversion can be unstable for roughly star-shaped or k-MDP graphs.The paper recommends avoiding such graphs or constructing better ones.
  • Null distribution: The permutation null distribution of S approaches χ2_2 under mild graph conditions, supporting approximate p-values for large data sets.Direct permutation calculations remain feasible for small samples but can be time consuming for large samples.

4 Power comparison

Simulation comparisons examine the new graph test against classical and graph-based competitors under location, scale, and combined location-scale alternatives. The new test is especially advantageous for moderate- to high-dimensional scale and general alternatives, while the edge-count test can be slightly better for simple low-dimensional location differences.

  • Compared tests: The comparisons include Hotelling’s T 2, GLR, edge-count tests, the degree test, and the new test on MSTs, k-MSTs, and MDPs.The graph-based methods use Euclidean distance in these simulations.
  • Location alternatives: For location alternatives, Hotelling’s T 2 performs well at low to moderate dimension, while graph tests become more competitive as dimension increases.The new test is only slightly worse than the edge-count test in the reported location scenario.
  • General alternatives: The new test dominates all other tests for moderate- to high-dimensional product log-normal alternatives combining location and scale changes.Changing the log-normal location parameter changes both the mean and variance.
  • Overall comparison: Overall, simulations show high power for the new test under location, scale, and general location-scale alternatives.The paper prefers it in moderate to high dimensions unless a location-only alternative is strongly expected.
  • Graph density: Increasing graph density from a 1-MST to a 5-MST increases power in the simulations, but denser graphs also increase computation and may eventually reduce power.The paper states that each application has an optimal graph density, which was not explored fully.
  • Rejection regions: The rejection-region analysis shows that scale alternatives in moderate or high dimension often produce opposite-signed within-sample deviations, favoring S over the edge-count test.For purely locational or very low-dimensional differences, the alternative lies in the first quadrant and the edge-count test can have slightly higher power.

5 Asymptotics

The paper derives an asymptotic permutation-null distribution for the graph statistic and establishes consistency under multivariate conditions. The approximation supports large-sample use, while finite-sample accuracy improves with sample size and slightly denser graphs but declines somewhat with dimension.

  • Finite-sample computation: Direct permutation p-values are feasible for small samples but become time consuming for large samples, motivating the asymptotic approximation.The finite-sample study compares approximate p-values with permutation p-values from 10,000 permutations.
  • Asymptotic null distribution: The permutation null distribution of S approaches χ2_2 under the usual limiting regime and mild conditions on the similarity graph.This asymptotic result provides the basis for approximate p-values.
  • Graph conditions: For a Euclidean k-MST with k = O(1), the graph satisfies the conditions needed for the asymptotic null distribution in multivariate data.The result is also useful for object data when the objects can be embedded in a high-dimensional Euclidean space.
  • Consistency: For continuous multivariate distributions differing on a set of positive measure, the k-MST-based test is consistent against all alternatives.This consistency result extends the usefulness of the method to many object-data settings with suitable embeddings.
  • Finite-sample accuracy: Approximate p-values become more accurate as sample sizes increase and as the graph becomes denser from a 1-MST to a 5-MST.Increasing dimension slightly decreases approximation accuracy, while sample sizes in the hundreds are reported as sufficient for use.

6 Real Data Examples

The paper applies the new graph-based test to matched-study covariates and phone-call networks. In both applications, the new test reveals distributional differences that edge-count tests can miss.

  • Covariate balance: The matched observational study compares treatment and three control groups using 20 covariates and graph-based tests.The groups contain 429 students each, and the comparisons use a ranked-based Mahalanobis distance to construct the MST.
  • Covariate balance: C-3 is very different from the other three groups, so the analysis focuses on T, C-1, and C-2.Across tests, T is similar to C-1 but significantly different from C-2.
  • Covariate balance: The new test gives more consistent results than edge-count tests for comparing C-1 and C-2.Edge-count tests do not reject C-1 versus C-2, whereas the new test aligns this comparison with the relative differences involving T and C-2.
  • Phone-call networks: The network application compares weekday and weekend phone-call networks constructed from daily calls among 106 subjects.The pooled data contain 330 networks, and k-MSTs are constructed using the number of different directed edges as the distance.
  • Phone-call networks: The network result reflects opposite within-sample deviations: weekdays have fewer and weekends more within-sample edges than expected.The reported counts are R1 = 327 versus E(R1) = 504.2 for weekdays and R2 = 125 versus E(R2) = 79.5 for weekends.

7 Discussion

The discussion explains that the proposed statistic combines deviations from the null expectation in both directions and compares favorably with related statistics. Its main advantage is strongest for high-dimensional location alternatives, while specialized statistics can be preferable for scale-only alternatives.

  • Proposed statistic: The proposed statistic S uses deviations from the null expectation in both directions.This design distinguishes cases where within-sample edge counts deviate in opposite directions.
  • Related statistics: When n = m, T2 equals T1 and T4 equals T3; when n != m, T2 and T4 perform slightly better for location alternatives.These comparisons are reported in Tables 6 and 7.
  • Power comparisons: In low dimensions, the four alternative statistics are comparable to S, whereas in d = 100, S is much more powerful for location-only alternatives.The low-dimensional comparison uses d = 10 and the high-dimensional comparison uses d = 100.
  • Scale alternatives: S is slightly less powerful than four other statistics for scale-only alternatives.The discussion therefore recommends S generally, unless the alternative is confidently known to be scale-only.

8 Conclusion

The paper proposes a graph-based two-sample statistic with good power for location, scale, and general alternatives, supported by an asymptotic permutation null distribution and applications to multivariate and network data.

  • The new graph-based statistic uses a common pattern under location and scale alternatives to detect general alternatives in multivariate and non-Euclidean data.Its similarity graph is constructed on the pooled observations.
  • The asymptotic permutation null distribution is χ2 under the stated graph conditions.For Euclidean multivariate data, these conditions hold for a k-MST with k = O(1).
  • P-value approximation based on the asymptotic null distribution works well for samples in the hundreds and beyond, supporting large-data analysis.The paper describes the test as an off-the-shelf tool for analyzing large data sets.
  • For Euclidean distance, a k-MST with k = O(1) is consistent against all alternatives.
  • In applications, the test gives more consistent covariate-balance results than existing graph-based tests and captures variance differences in network data.The applications involve a matched observational study and network data under two conditions.

A.1 Proof to Lemma 3.1

This proof section derives moments and covariance relationships for the graph-based statistics under the permutation null distribution.

  • The proof calculates the expectation and variance of R2 and the covariance between R1 and R2 under the permutation null distribution.

A.2 Proof of Theorem 5.1

The proof establishes the asymptotic Gaussian behavior needed for the test statistic under the permutation null distribution by first analyzing a bootstrap null distribution.

  • The proof of Theorem 5.1 relies on Stein’s method for sums of dependent random variables.
  • The proof verifies graph-size and neighborhood conditions, including limiting constants for |G| and local degree terms.
  • Under the bootstrap null, observations are independently assigned to sample X with probability n/N and to sample Y with probability 1 − n/N.
  • Conditioning on the number of observations assigned to sample X makes the bootstrap null distribution equivalent to the permutation null distribution.
  • As N →∞, the relevant bootstrap statistics become multivariate Gaussian under the stated conditions.
  • The corresponding statistics therefore follow a bivariate Gaussian distribution under the permutation null distribution as N →∞.

A.3 Proof of Theorem 5.2

This section verifies graph-degree and density-based conditions used in the asymptotic theory, including for k-MST graphs and multivariate distributions.

  • For a k-MST, |G| = k(N−1), so k = O(1) implies |G| = O(N).
  • The proof uses degree moments and variance bounds for k-MSTs constructed under Euclidean distance.It relates the degree of the origin to homogeneous Poisson-process calculations.
  • The argument shows that the required degree variance and fourth-moment quantities are controlled for the relevant Euclidean k-MST setting.
  • For multivariate distributions with density functions f and g, the proof evaluates limiting integrals involving p, q, f, and g.
  • When f and g differ on a set of positive measure, qδ1 + pδ2 is strictly positive.
Loading 1307.6294v6…