A weighted edge-count two-sample test for multivariate and object data
summary
The gist
Two-sample tests for multivariate data and non-Euclidean data are widely used in many fields In this paper…
In short
This paper introduces a weighted edge-count test to compare two samples of multivariate data, specifically addressing issues with unequal sample sizes. The new test uses weights to properly account for different sample sizes when constructing similarity graphs, resulting in higher statistical power compared to the standard edge-count test under various conditions.
Key concepts
- Edge-Count Test
- A traditional two-sample test that counts the number of edges between observations in a similarity graph. It is used to determine if two samples are drawn from the same distribution, but it can have low power when sample sizes are different, especially for scale alternatives.
- Weighted Edge-Count Test
- A modified edge-count test that assigns different weights to edges based on which sample they come from. This weighting scheme ensures the test remains valid and has better statistical performance even when the two samples have unequal sizes.
- k-MST Graph
- The similarity graph constructed using the k-Nearest Neighbor (k-MST) method, where observations are connected to their $k$ nearest neighbors. The paper shows that this type of graph is suitable for multivariate data testing, especially when using Euclidean distance.
- Asymptotic Distribution Convergence
- When the sample size becomes very large, the standardized weighted test statistic converges to a standard normal distribution. This allows researchers to use asymptotic results to approximate p-values accurately even with finite sample sizes under certain conditions.
Terminology used across episodes
This episode discusses
The paper
A weighted edge-count two-sample test for multivariate and object data · Read on arXiv
Hao Chen, Xu Chen, Yi Su
University of California, Davis · Duke University
DOI: 10.1080/01621459.2017.1307757
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "A weighted edge-count two-sample test for multivariate and object data".
Jane: Here's the gist of the paper. Two-sample tests for multivariate data and non-Euclidean data are widely used in many fields In this paper, we study a nonparametric testing procedure that utilizes graphs representing the similarity among observations The new test exhibits substantial power gains in simulation studies Problem Context Two-sample testing is a fundamental problem in statistics Due to the increasing richness of data in both dimension and complexity, this problem is encountering new challenges Parametric approaches can be applied to multivariate data under certain assumptions while their power decreases quickly as the dimension grows unless strong assumptions are made to facilitate the estimation of the large number of (nuisance) parameters, such as the covariance matrix The edge-count test is not restricted to the MST It can be applied to any similarity graph where more similar observations are more likely to be connected However, in practice, sample sizes range from tens to thousands, or somewhat larger Chen and Friedman
2016: found that, when the dimension of the data is moderate to high, for practical sample sizes, the edge-count test is effective for locational alternatives but can have low power for scale alternatives when the Euclidean distance is used to construct the similarity graph This weird phenomenon indicates that the edge-count test statistic is not well defined Weighted Edge-Count Test Construction To address this problem, we propose a modified version of the edge-count test The idea is that, when the sample sizes are different, it is more difficult to form an edge within the sample with a smaller sample size than that for the sample with a larger sample size So we give within-sample edges different weights according to which sample they are from instead of treating them equally in the edge-count test The new test works properly under unequal sample sizes and we call it the weighted edge-count test We consider the following two test statistics: Rw = qR1 + pR2, p = m/N, q = 1 - p, (3) R˜w = ˜qR1 + ˜pR2, p˜ = m − 1/N − 2, q˜ = 1 - p Both of their variances are well controlled no matter how different m and n are, and R˜w has the smallest variance among all tests of the form aR1 + (1 − a)R2 Performance Gains and Comparison The weighted-edge-count test has higher power than the edge-count test when the sample sizes are different for all k-MSTs, k = 1,..., 15 It also has higher power than the corresponding smaller sample size scenario (m = n = 50) Under locational alternatives, the weighted-edge-count test is more powerful than the edge-count test and the generalized edge-count test when sample sizes are different The weighted-edge-count test is the only test in scenario 2 that has higher power than the edge-count test in scenario 1 for all k-MSTs Asymptotic Properties and Consistency When the sample size is large, Rw, normalized by its mean and standard deviation, approaches the standard normal distribution as N → ∞ under some mild conditions on the similarity graph G A k-MST, where k = O(1), constructed on the Euclidean distance satisfies all conditions in obtaining the limiting distribution for the generalized edge-count test
Chen and Friedman, 2016: The weighted edge-count test is consistent against all alternatives in the usual limiting regime Real Data Application The weighted edge-count test rejects the null hypothesis of equal distribution at 0.05 significance level under both distances Under distance 2, the weighted test statistic correctly summarizes the signals provided by both samples and results in a larger than expectation weighted within-sample edges The test based on Rw has slightly higher power than that based on R˜w for all k-MSTs We recommend to use Rw in practice Relation to Generalized Test The generalized edge-count test works under a wider range of alternatives than the weighted-edge-count test does, while if the alternative is of scenario (i), the weighted-edge-count test is slightly more powerful The choice of whether to use the weighted-edge-count test or the generalized edge-count test can be done in a similar manner to the choice between the Hotelling T2 test and the generalized likelihood ratio test not assuming equal covariance matrix The weighted-edge-count test exhibits substantial power gains in simulation studies The weighted-edge-count test and the generalized edge-count test in Chen and Friedman
2016: can be used in a complementary way The choice of whether to use the weighted-edge-count test or the generalized edge-count test can be done in a similar manner to the choice between the Hotelling T2 test and the generalized likelihood ratio test not assuming equal covariance matrix The weighted edge-count test exhibits substantial power gains in simulation studies The weighted-edge-count test statistic, standardized by its mean and standard deviation, is shown to converge to the standard normal distribution under some mild conditions on the similarity graph The approximated p-value based on the asymptotic results is reasonably accurate to the permutation p-value for sample sizes in hundreds The weighted edge-count test and the generalized edge-count test in Chen and Friedman
2016: can be used in a complementary way References Hao Chen and Jerome H Friedman.
Tom: A new graph-based two-sample test for multivariate and object data.
Jane: Journal of the American statistical association, 2016 Hao Chen and Nancy R.
Tom: Zhang.
Title and authors: Tom: So we're looking at this paper today, "A weighted edge-count two-sample test for multivariate and object data" by Hao Chen, Xu Chen, and Yi Su. It’s about a new way to compare two samples when you’re dealing with complex data that doesn't just live in simple Euclidean space.
Jane: Right. So the authors are moving away from those old methods that rely on standard distance measures, like the Minimum Spanning Tree or MST, and they're introducing something that handles situations where your two samples have different sizes.
Lu: Exactly. The paper is focused on building a nonparametric testing procedure using graphs to represent how similar the observations are to each other, specifically addressing the problem that hits when you compare samples of unequal sizes.
Meng: Unequal sample sizes are a real headache when you're shipping models; one side might have thousands of data points and the other only has hundreds, and those old tests just break down.
Lalam: This paper tackles that directly by proposing a modified approach to the classic edge-count test to fix that exact issue.
Tom: So what’s the core idea here? What did they actually change about the original test statistic to make it work better when sample sizes are different?
Jane: They figured that you can give different weights to those edges in the similarity graph, depending on which sample each observation comes from, instead of treating every edge equally. This is what they call the weighted edge-count test.
Lu: That weighting scheme is key; they define two statistics, R w and R t w, and they show that both of their variances are well controlled no matter how different the sample sizes m and n are.
Tom: Wait, so if we look at those two statistics, R w and R t w, which one do the authors say is better for controlling variance?
Jane: They actually say that R t w has the smallest variance among all tests of that form aR1 plus (one minus a)R2. That’s a big win for stability when you have unequal sample sizes.
Meng: Controlling variance is important because if the test statistic itself is wildly unstable, you can't trust your p-values at scale when you're deploying this in production.
Lalam: And they prove that this new weighted edge-count test exhibits substantial power gains in simulation studies compared to the original edge-count test across fifteen different k minimum spanning trees.
Tom: Power gains are good, but what about the assumptions? The paper mentions asymptotic properties when the sample size gets really big. Does it hold up when we look at finite samples?
Jane: Yes, they show that when the sample size is large, like as N goes to infinity, the test statistic R w normalized by its mean and standard deviation approaches a standard normal distribution under mild conditions on the similarity graph.
Title and authors: Lu: They actually derive and show that this asymptotic permutation null distribution works well even for finite samples, which really facilitates applying this test to those large datasets you mentioned earlier.
Meng: That’s helpful because we don't always have infinite data; we have fixed budgets and finite runs, so knowing how it behaves in practice is crucial for deployment.
Tom: Moving on to the actual application, what does this mean for someone who isn't doing heavy statistical modeling every day? What kind of real-world data are we talking about here?
Jane: They use an analysis on a real dataset of network data, which shows that the weighted test statistic R w correctly summarizes the signals coming from both samples.
Lu: In their example, it resulted in more weighted within-sample edges than expected under the null hypothesis of equal distribution. That means it’s actually detecting differences when they exist.
Meng: So if I were looking at my production traffic data, I could use this to check if the patterns between two different time periods are statistically different without needing a full covariance matrix estimate first.
Tom: It seems like they are providing a robust tool for non-Euclidean data, which is super relevant since we're increasingly dealing with network structures instead of just simple coordinate pairs.
Jane: That’s right, and the paper also mentions that the weighted edge-count test can be used in a complementary way alongside the generalized edge-count test they looked at previously.
Lu: They suggest you use this weighted version for locational alternatives, and then maybe switch to the generalized version for a wider range of alternatives, depending on what you're testing.
Meng: So it’s like having two different tools in your toolbox, one optimized for a specific kind of comparison and another that’s more versatile if things get messy.
Tom: And the final conclusion is that this weighted edge-count test exhibits substantial power gains in simulation studies, and it's consistent against all alternatives in the usual limiting regime.
Jane: To wrap up, this paper on "A weighted edge-count two-sample test for multivariate and object data" gives us a concrete way to handle unequal sample sizes without sacrificing statistical power when using similarity graphs.
Lu: It’s about finding a way to weight those edges intelligently so that the resulting test statistic has minimal variance and behaves predictably, even in finite samples.
Meng: For deployment, it means we can rely on this more reliably when comparing samples of different sizes in complex data settings because the variance is better controlled.
Tom: So, we’ve seen how they build a weighted edge-count test for unequal sample sizes that shows big power gains and good asymptotic properties. That’s what we have today.
The paper's summary: Tom: So, to recap, we’re talking about this new weighted edge count test that handles unequal sample sizes better than the original version, even when dealing with complex data structures where standard distance measures aren't enough.
Jane: Right. It’s all about fixing that "undefined" problem they mentioned earlier by giving different weights to the edges in the similarity graph based on which sample each observation came from.
Lu: The authors show that this weighted edge count statistic, R w, has the smallest variance among all tests of that form a R one plus one minus a R two structure, which is pretty neat because it keeps things stable regardless of how different those sample sizes are.
Meng: Stability is key when I’m shipping models; if the test statistic itself is wildly swinging around, you can't trust your p-values at scale in production.
Tom: And they showed that this weighted test actually gives a higher power than the original edge count test when sample sizes are different for all fifteen types of minimum spanning trees they tested.
Jane: That’s the big number here; it means this new method finds real differences more often than the old way when you have unequal groups.
Lu: They also proved that under locational alternatives, meaning there is a true shift in location, this weighted edge count test beats both the original edge count test and their generalized version when sample sizes are different.
Tom: So what does that mean for someone who just wants to run a comparison on some network data? Does this replace everything else we’ve done?
Jane: Not at all. It’s just a better tool in the toolbox, like having two different wrenches for the same job, which is what they suggest with the generalized edge count test.
Lu: The authors suggest you can use this weighted edge count test for one type of alternative—the locational ones—and then maybe switch to that generalized version if you’re testing something more general.
Meng: So it’s a choice based on what kind of difference you expect to find, which makes sense because not every comparison needs the most complex statistical machinery.
Tom: And they do show that when the sample size gets really large, like as N goes to infinity, this weighted statistic follows a normal distribution under mild conditions on the graph structure.
Jane: It’s a nice piece of theory because it gives us confidence that if we have enough data, our p-values will be reasonably accurate for finite samples too.
Lu: They even show that the test is consistent against all alternatives in the usual limiting regime when using minimum spanning trees based on Euclidean distance and where k is small.
Tom: Consistency means it’s reliable across the board under those conditions, which is exactly what we need when we’re building things that actually run in the wild.
Jane: So, to summarize, this paper gives us a solid way to compare samples of different sizes using similarity graphs without having to guess the covariance matrix or worry about unstable statistics.
Lu: It’s a practical improvement on graph-based testing for multivariate data comparison.
Tom: Next up, we’re looking at how these concepts apply to real network traffic data, where you can actually see if the patterns between two different time periods are different in a way that matters.
The paper's improvements: Tom: So we’ve looked at how they fixed the unequal sample size issue by weighting those edges, and now we need to talk about what else they suggest for this test.
Jane: Okay, so what are the actual suggestions in the paper? Beyond just making it work better for different group sizes, is there anything else they recommend doing with this weighted edge count idea?
Lu: They suggest using this weighted edge count test alongside the generalized edge count test because they have different strengths for different kinds of statistical questions.
Meng: So you’re saying you use the weighted version when you expect a specific type of difference, like a shift in location, and the generalized version for broader possibilities?
Tom: That makes sense from an engineering standpoint; it means we can pick the tool that matches our hypothesis better, instead of trying to force one statistic to do everything.
Jane: Exactly. It’s like choosing between a specific type of wrench and a more versatile set of tools depending on the job you're doing.
Lu: And they also pointed out that because this test is robust under unequal sample sizes, it might be a better choice than some other tests when you aren't sure about the exact distribution structure.
Tom: That’s interesting. It implies that when we are dealing with complex, non-Euclidean data—like network structures—we don't always have to default to the most standard tools, right?
Jane: Right. It gives us a pathway for using graph-based methods even when the underlying data isn't perfectly structured like a simple coordinate system.
Lu: The paper points toward using this weighted approach as a way to handle scenarios where you’re comparing different distributions without assuming they have the same covariance matrix.
Tom: That’s a big deal for many of our machine learning applications because estimating that covariance matrix accurately when sample sizes are unequal is often impossible.
Jane: So, the implication is that we can do more robust comparisons in data science, especially with complex objects, without having to assume perfect mathematical structure across both groups.
Lu: And they show how this weighted test can be used complementarily with the generalized edge count test to cover a wider range of possibilities than just locational shifts.
Meng: From a deployment standpoint, that means we might be able to deploy these kinds of similarity-based tests in systems where we know the samples are coming from different sources with varying sizes.
Tom: So, it’s not just a new formula; it’s a more flexible strategy for testing when the data itself is messy and uneven.
Jane: It really does make graph-based statistical inference feel much more accessible for people who aren't deep in multivariate statistics.
Lu: This work opens up ways to apply these concepts to areas like analyzing social networks or complex biological data where standard parametric tests just don't cut it anymore.
Conclusion: Tom: So we’ve covered how this weighted edge count test uses sample size weighting to fix problems in comparing multivariate data when group sizes are different.
Jane: It really is a practical statistical improvement that makes those comparisons much more reliable, even with complex similarity graphs.
Lu: The core idea is that by controlling the weights of the edges based on which sample they come from, you get a test statistic with lower variance, which means it’s more stable when you run it repeatedly.
Meng: For me at startup level, that stability is huge; I don't want to deploy a test that breaks every time the input data distribution shifts slightly.
Tom: And they showed that this weighted edge count test gives higher power than the original version in simulation studies across fifteen different graph structures.
Jane: That means if there’s a real difference between your two samples, this new method is more likely to detect it than the older, simpler way we used to do things.
Lu: And they also established that under locational alternatives, which is a specific type of difference, this weighted test performs better than its counterparts when sample sizes are not equal.
Meng: So for real-world applications where you might have unequal data streams, this gives us a concrete way to be more confident in our results without having to build massive covariance matrices that just won't fit in memory.
Tom: Exactly. It’s about making these complex graph tests actually usable when the data isn't perfectly balanced.
Jane: So, to wrap up on "A weighted edge-count two-sample test for multivariate and object data," we’ve seen how they give us a more stable and powerful tool for comparing samples of different sizes using similarity graphs.
Lu: It’s a solid methodological contribution that strengthens the toolkit for non-Euclidean data analysis.
Meng: It means I can use this framework to check if two different user groups are behaving differently without worrying about the sample size disparity causing noise in my model evaluations.
Lalam: I’m confident in this result; the weighted edge count test is statistically sound and performs better under those conditions than standard approaches.
Tom: It seems like we have a much more robust way to handle these kinds of comparisons across various data types now.
Jane: And that brings us to another topic later, where we’ll be looking at how these ideas connect to testing randomized trials and the challenges in synthesizing evidence from those different methods.
More episodes
- Daily Summary for 2026-11-19
- 2310.07973-Statistical Performance Guarantee for Subgroup Identification with Generic Machine Learning
- 2408.09155-Learning Robust Treatment Rules for Censored Data
- Daily Summary for 2026-11-19
- 2603.23397-Kinetic Langevin Splitting Schemes for Constrained Sampling
- 2606.09906-An information-geometric framework for mapping maximum potential biodiversity
- 2603.27718-Induced replication and the assessment of models
- 1307.0898-Entropy of a Zipfian Distributed Lexicon
- 2406.19974-Generalizing self-normalized importance sampling with couplings
- 2412.10213-Collaborative Optimal Design of Controlled Experiments with Subject Covariates