Joint Independence Testing for Latent Position Random Graphs

Xiaoyi Wen; Zoltan Szabo

stat.MLOct 25, 2026

Joint Independence Testing for Latent Position Random Graphs

Authors: Xiaoyi Wen, Zoltan Szabo

Organizations: Department of Epidemiology and Biostatistics University of California, San Francisco San Francisco, USA · Department of Statistics London School of Economics London, UK

Abstract

Kernel techniques are among the most powerful methods in data science and statistics. One of the key properties of kernels contributing to their numerous successful applications is that the associated reproducing kernel Hilbert space is expressive enough to encode probability distributions without loss of information or to capture the joint independence of $M\ge 2$ random variables, under mild conditions. Computationally, these measures (i) rely on the so-called Gram matrix which contains the pairwise similarity of sample points, and (ii) converge at a rate $O \left(n^{-\frac{1}{2}}\right)$ , where $n$ denotes the sample size. We focus on measuring the independence of latent position random graphs (LPRGs), a model widely-applied for instance in neuroscience, sociology, and epidemiology. In LPRGs a latent representation is associated to each node. The similarity of these representations (meant via a kernel) determines whether two nodes are connected, making the Gram matrices only implicitly observable and the estimation challenging. Despite the fundamental importance of quantifying the independence of $M$ LPRGs, very little is known about the solution of this problem; existing techniques are restricted to $M=2$ components and only guarantee consistency without rates. In this work, (i) we define an independence measure called graph Hilbert-Schmidt independence criterion (GHSIC) for $M\ge 2$ LPRGs, (ii) we prove that it can be estimated at a rate $\tilde{O}\left(n^{-\frac{1}{3}}\right)$ relying on spectral decomposition of adjacency matrices, (iii) without the need to choose kernels and their hyperparameters. Numerical experiments demonstrate the effectiveness of the proposed GHSIC estimator both on synthetic examples and in the analysis of brain functional connectivity subnetworks in natural language perception.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of specific latent position random graph (LPRG) models. ER: Erdős-Rényi model; RDPG: random dot product graph.

Panel of Figure 2 — Figure 2: Illustration of measuring the independence of latent position random graphs (r.h.s.; using GHSIC) vs. classical independence (l.h.s.; relying on HSIC). The traditional HSIC estimator relies on the Gram matrices $\left(\mathbf{K}^{m}\right)_{m=1}^{M}$ ; the GHSIC estimator has to be based on the observable adjacency matrices $\left(\mathbf{A}^{m}\right)_{m=1}^{M}$ determined by the hidden Gram matrices $\left(\mathbf{K}^{m}\right)_{m=1}^{M}$ .

Assumption	Constant	Content
Assumption 1 (i)	$C_{0}^{m}$	$\Delta^{m}>C_{0}^{m}\log(n)$
Assumption 1 (ii)	$C_{1}^{m}$	$\bar{\sigma}^{m}>C_{1}^{m}\sqrt{\frac{\log(n)}{n}}$
Assumption 2 (i)	$c_{0}^{m}$	$\frac{\lambda^{m}_{d^{m}}(\mathbf{K}^{m})}{\Delta^{m}}\geq c^{m}_{0}$
Assumption 2 (ii)	$c_{2}^{m}$	$\delta^{m}_{d^{m}}\geq 16c_{1}^{m}(n)\sqrt{\frac{\log\left(\frac{6n}{\eta}\right)}{n}}$ , $c_{1}^{m}(n)=c_{2}^{m}\log\left(2+\log(2n)\right)$
Assumption 3		$C_{k^{m}}$ has simple and positive eigenvalues
Assumption 4		$\hat{C}_{k^{m}}$ has simple and positive eigenvalues

Table 1: Summary of our assumptions, with the constants appearing in them. The bounds in Assumption 1 (i), Assumption 1 (ii) and Assumption 2 (i) are probabilistic. Assumptions 1 - 2 hold for

n

large enough. Assumptions 5 – 7 (Assumptions 8 – 9 ) are used to derive the optimal embedding dimensions under polynomial and exponential eigenvalue decay, respectively, in Section D ; both sets of assumptions are assumed to hold for

n

large enough.

Panel of Figure 3 — Figure 3: Estimation error for different number of components $M$ (Experiment-1A). Line: mean. Upper bar: $97.5\%$ quantile. Lower bar: $2.5\%$ quantile.

Panel of Figure 4 — Figure 4: 1st row: estimation error for different selection of $d_{0}$ (Experiment-1B); 2nd row: associated runtime of $\text{HSIC}_{k}^{2}(\hat{\mathbb{P}}_{n})$ and that of the $3$ estimation steps in $\widehat{\text{GHSIC}_{k}^{2}}$ under different selection of $d_{0}$ . The x and y axis are on logarithmic scale. The legend $\widehat{\text{GHSIC}_{k}^{2}}$ refers to the 3rd step in the discussion on computational after Theorem 2 . Line: mean. Upper bar: $97.5\%$ quantile. Lower bar: $2.5\%$ quantile.

Figure 5: Estimation error with various parameters changing. (a): changing

\rho

(Experiment-1C). (b): varying

\gamma

(Experiment-1D). (c): changing

c

(Experiment-1E). Line: mean. Upper bar:

97.5\%

quantile. Lower bar:

2.5\%

quantile.

Panel of Figure 6 — Figure 6: Test power of $\widehat{\text{GHSIC}_{k}^{2}}$ with $\hat{d}^{m}=\frac{1}{\hat{\tau}_{m}}\log^{\frac{1}{3}}(n)$ , $\hat{\hat{d}}^{m}=\frac{1}{\hat{\hat{\tau}}_{m}}\log^{\frac{1}{3}}(n)$ and $\hat{\hat{d}}^{m}_{d_{0}}=\frac{1}{\hat{\hat{\tau}}_{m,d_{0}}}\log^{\frac{1}{3}}(n)$ . (a): $\rho=0.3$ . (b): $\rho=0.4$ . Line: mean. Upper bar: $97.5\%$ quantile. Lower bar: $2.5\%$ quantile.

Panel of Figure 7 — Figure 7: Runtime of calculating a quantile of $\widehat{\text{GHSIC}_{k}^{2}}$ $(\hat{d}^{m}=\frac{1}{\hat{\tau}_{m}}\log^{\frac{1}{3}}(n))$ , $\widehat{\text{GHSIC}_{k}^{2}}$ $(\hat{\hat{d}}^{m}=\frac{1}{\hat{\hat{\tau}}_{m}}\log^{\frac{1}{3}}(n))$ and $\widehat{\text{GHSIC}_{k}^{2}}$ $(\hat{\hat{d}}^{m}_{d_{0}}=\frac{1}{\hat{\hat{\tau}}_{m,d_{0}}}\log^{\frac{1}{3}}(n))$ , with logarithmic scale on the y axis.

Panel of Figure 8 — Figure 8: The overview of the preprocessing of the fMRI data.

Figure 9: Visual subnetwork. (a)-(b): checking the validity of exponential and polynomial spectral decay. (c): Number of times the alternative (

H_{1}

) was accepted under different threshold

t

Figure 10: Count of rejection of

H_{1}

for different subnetworks. The subnetworks are ordered decreasingly according to their size.

Figure 11: Illustration of the relationships between results and assumptions. Blue nodes: external results. Orange nodes: own results. Green nodes: assumptions. An arrow

R_{1}\rightarrow R_{2}

from a result node

R_{1}

to a result node

R_{2}

means that result

R_{1}

is used to prove result

R_{2}

; each result node is either blue or orange. An arrow

A\rightarrow R

from an assumption node

A

to a result node

R

means that assumption A is imposed (for the first time) in result

R

Statement	Type	Content
Lemma 1	own	non-negativity of $\widehat{\mathrm{GHSIC}^{2}_{k}}$ , estimator $\widehat{\mathrm{GHSIC}_{k}}$
Theorem 2	own	error bound for $\widehat{\mathrm{GHSIC}_{k}}$
Lemma 3	external	$\sin\left(\Theta\right)$ theorem
Corollary 4	external	a variant of the $\sin\left(\Theta\right)$ theorem
Lemma 5	external	concentration inequality of adjacency matrices
Lemma 6	external	concentration inequality of symmetric matrices

Table 2: Summary of external and our own results (indicated in the 2nd column).

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 12 — Figure 12: Illustration of the eigengap $\delta$ defined in ( 37 ).

Panel of Figure 13 — Figure 13: Illustration of $\mathbb{J}^{m}$ events (boxes) leading to our probabilistic bound on $\left\|\bm{\hat{\Phi}}^{m}_{d^{m}}-\bm{\Phi}^{m}_{d^{m}}\right\|_{F}$ (bottom of the figure). In each box, the associated equation and the estimated quantity are included with the probability of the event. The notation $B\rightarrow B^{\prime}$ indicates that the event $B^{\prime}$ can be derived from the event $B$ ; $B_{1},B_{2},\ldots,B_{N}\rightarrow B^{\prime}$ ( $N\geq 2$ ) means that the events $(B_{i})_{i=1}^{N}$ are combined with a union bound to control the event $B^{\prime}$ . When an $\eta$ reparameterization is applied, the corresponding probability shows up on the associated arrow.

	Case	$f(x,y)$	$g(x)$	$S_{0}(x)$	$a$	$b$
( 160 )	(i)	$\left\\|\left\|\mathbf{A}^{m}\right\|-\mathbf{K}^{m}\right\\|$	$4\tilde{C}^{m}\sqrt{\log\left(\frac{12n}{\eta}\right)}$	$\sqrt{\Delta^{m}}$	$\sqrt{C_{0}^{m}\log(n)}$	$\sqrt{n}$
( 234 )	(ii)	$\left\\|\left\|\mathbf{A}^{m}\right\|-\mathbf{K}^{m}\right\\|$	$4\tilde{C}^{m}\sqrt{\log\left(\frac{144n}{\eta}\right)}$	$\sqrt{\Delta^{m}}$	$\sqrt{C_{0}^{m}\log(n)}$
( 274 )	(ii)	$\left\\|\left\|\mathbf{A}^{m}\right\|-\mathbf{K}^{m}\right\\|$	$4\tilde{C}^{m}\sqrt{\log\left(\frac{144n}{\eta}\right)}$	$\sqrt{\Delta^{m}}$	$\sqrt{C_{0}^{m}\log(n)}$
( 433 )	(ii)	$\left\\|\left\|\mathbf{A}^{m}\right\|-\mathbf{K}^{m}\right\\|$	$4\tilde{C}^{m}\sqrt{\log\left(\frac{24n}{\eta}\right)}$	$\sqrt{\Delta^{m}}$	$\sqrt{C_{0}^{m}\log(n)}$
( 657 )	(i)	$-\left\\|\mathbf{D}^{m}\right\\|-\sqrt{32\log(n)}$	$2\sqrt{n}$	$-\bar{\sigma}^{m}$	$-\infty$	$-C_{1}^{m}\sqrt{\frac{\log(n)}{n}}$

Appendix

Table 3: Combination of probability events using Lemma 26 . For all probability events we use the subtitution

(\mathcal{X},\mathcal{Y})\leftarrow\left(\mathcal{X}^{m},\{0,1\}^{\binom{n}{2}}\right)

Figure 14: Illustration of

f

defined in ( 928 ). The horizontal line is

y=\frac{1}{3}

Kernel Methods

Kernel methods use similarity functions and reproducing kernel spaces to model nonlinear relationships, quantify uncertainty, and compare data.

See all 233 papers

Feb 26, 2026

Kernel Integrated $R^2$ : A Measure of Dependence

We introduce kernel integrated

R^2

, a new measure of statistical dependence that combines the local normalization principle of the recently introduced integrated

R^2

with the flexibility of reproducing kernel Hilbert spaces (RKHSs). The proposed measure extends integrated

R^2

from scalar responses to responses taking values on general spaces equipped with a characteristic kernel, allowing to measure dependence of multivariate, functional, and structured data, while remaining sensitive to tail behaviour and oscillatory dependence structures. We establish that (i) this new measure takes values in

[0,1]

, (ii) equals zero if and only if independence holds, and (iii) equals one if and only if the response is almost surely a measurable function of the covariates. Two estimators are proposed: a graph-based method using

K

-nearest neighbours and an RKHS-based method built on conditional mean embeddings. We prove consistency and derive convergence rates for the graph-based estimator, showing its adaptation to intrinsic dimensionality. Numerical experiments on simulated data and a real data experiment in the context of dependency testing for media annotations demonstrate competitive power against state-of-the-art dependence measures, particularly in settings involving non-linear and structured relationships.

Pouya Roudaki, Shakeel Gavioli-Akilagun, Florian Kalinke +2

Department of Statistics, London School of Economics, London, UK · Department of Decision Analytics and Operations, City University of Hong Kong, Hong Kong, China · Chair of Information Systems, Karlsruhe Institute of Technology, Karlsruhe, Germany

Kernel Methods

Ask PDF

Apr 9, 2026

Intensity Dot Product Graphs

Latent-position random graph models usually treat the node set as fixed once the sample size is chosen, while graphon-based and random-measure constructions allow more randomness at the cost of weaker geometric interpretability. We introduce Intensity Dot Product Graphs (IDPGs), which extend Random Dot Product Graphs by replacing a fixed collection of latent positions with a Poisson point process on a Euclidean latent space. This yields a model with random node populations, RDPG-style dot-product affinities, and a population-level intensity that links continuous latent structure to finite observed graphs. We define the heat map and the desire operator as continuous analogues of the probability matrix, prove a spectral consistency result connecting adjacency singular values to the operator spectrum, compare the construction with graphon and digraphon representations, and show how classical RDPGs arise in a concentrated limit. Because the model is parameterized by an evolving intensity, temporal extensions through partial differential equations arise naturally.

Giulio Valentino Dalla Riva, Matteo Dalla Riva

Baffelan OU, Noumea, New Caledonia · Dipartimento di Tecnica e Gestione dei Sistemi Industriali, Università di Padova, Vicenza, Italy

Graphon Theory Latent Variable Models

Ask PDF

May 21, 2026

A Martingale Kernel Independence Test

The Hilbert-Schmidt Independence Criterion (HSIC) and its joint-independence extension

d\mathrm{HSIC}

are degenerate

V

-statistics whose data-dependent weighted-

χ^2

null limits force a permutation calibration that multiplies the per-test cost by the number of permutations, in practice two orders of magnitude. Adapting the recent martingale MMD construction for two-sample testing to the (joint) independence problem, we introduce two studentised statistics whose null distributions are standard normal regardless of the data law, so that a single normal-quantile lookup replaces the permutation step entirely. The first,

m\mathrm{HSIC}

, is a self-normalised lower-triangular sum of the Hadamard product of two empirically centred Gram matrices. Under independence and bounded-fourth-moment kernels it converges to a standard normal. It is consistent against every fixed alternative, and runs at quadratic cost in the sample size without any sample split, matching the biased HSIC

V

-statistic. Our second statistic,

md\mathrm{HSIC}

, achieves finite-sample consistency with a single half-sample split: the centring is estimated on one half and the lower-triangular self-normalised martingale is run on the other, shrinking the conditional-mean residual to a quantity that is exponentially small in

d

, so the statistic is asymptotically standard normal at every fixed number of jointly tested variables, with a per-test cost that grows only linearly in

d

. On synthetic data with per-variable input dimension from

1

500

and between

2

and

10

jointly tested variables, both statistics match the empirical type-I error rate and test power of permutation-calibrated baselines while running

25

60\times

faster.

Felix Laumann, Zhaolu Liu, Mauricio Barahona

Imperial College London

Maximum Mean Discrepancy Kernel Methods Statistical Hypothesis Testing

Ask PDF

Abstract

Kernel Methods

Explore similar work

Kernel Integrated R2R^2R2: A Measure of Dependence

Intensity Dot Product Graphs

A Martingale Kernel Independence Test

Kernel Integrated $R^2$ : A Measure of Dependence