Joint Independence Testing for Latent Position Random Graphs

Xiaoyi Wen, Zoltan SzaboarXiv 2026 · arXiv

TL;DR

The paper introduces the Graph Hilbert-Schmidt Independence Criterion (GHSIC), a novel method to test whether multiple random graphs (such as different layers of a brain network) are jointly independent. Unlike previous methods, GHSIC works directly on observable adjacency matrices, requires no manual kernel selection, and provides a guaranteed convergence rate of $\tilde{O}(n^{-1/3})$.

What Problem Does This Paper Address?

In fields like neuroscience and sociology, researchers often deal with "multiplex networks"—multiple graphs defined over the same set of nodes. For example, in a brain study, one graph might represent structural connections while another represents functional activity during a specific task. A fundamental question is: Are these graphs independent, or is there a underlying relationship between them?

The authors focus on Latent Position Random Graphs (LPRGs). In this model, every node has a hidden "latent position" in some space, and the probability of two nodes connecting depends on how similar their latent positions are.

The challenge is twofold:

  1. Hidden Information: We only observe the binary connections (the adjacency matrix), not the latent positions or the similarity function (the kernel) that generated them.
  2. Joint Independence: While testing if two variables are independent is common, testing if $M \ge 2$ variables are jointly independent is much harder. Existing graph-based tests were largely restricted to pairs ($M=2$) and lacked theoretical proofs regarding how fast they improve as the number of nodes ($n$) grows.

Methods

The authors adapt the classical Hilbert-Schmidt Independence Criterion (HSIC)—a powerful tool for testing independence between random variables—to the world of graphs.

The key innovation is the GHSIC estimator. Since the underlying "Gram matrices" (which measure similarity between nodes) are unobservable, the authors use spectral decomposition of the adjacency matrices to estimate them.

  • Adjacency Spectral Embedding (ASE): They perform a truncated Singular Value Decomposition (SVD) on the adjacency matrix of each graph.
  • Kernel-Free Approach: Remarkably, this method doesn't require the user to choose a kernel or tune hyperparameters. The spectral features extracted from the graph itself act as an empirical map of the latent space.
  • Optimal Dimensioning: The paper provides a theoretical framework to choose the "optimal" number of dimensions to keep during the SVD, depending on whether the graph's spectrum decays at a polynomial or exponential rate.
LPRG generalizes common models like Erdős-Rényi (ER) and Random Dot Product Graphs (RDPG).

Datasets

The researchers evaluated GHSIC using:

  1. Synthetic Simulations: They generated graphs with Gaussian latent positions and Gaussian kernels to verify that the estimator converges to the true independence value as the number of nodes increases.
  2. Human Brain fMRI Data: They used a natural language perception dataset (LeBel et al., 2023) involving 8 participants listening to narrative stories. They constructed functional connectivity networks for different brain subnetworks (like the Visual and Somatomotor networks) to test if different language tasks triggered dependent or independent neural patterns.

Key Insights and Ideas

  • The "Implicit" Hurdle: In standard statistics, we have direct samples. In graphs, the "samples" are filtered through a Bernoulli process (the coin flip that decides if an edge exists). This makes the estimation noisier.
  • Convergence Gap: While standard HSIC converges at a rate of $O(n^{-1/2})$, GHSIC converges at $\tilde{O}(n^{-1/3})$. This slower rate is the theoretical "price" paid for only being able to observe edges rather than the latent positions themselves.
  • Neuroscience Validation: The tool successfully identified that the Somatomotor (SomMot) and Visual (Vis) subnetworks are highly active and coordinated during speech perception, which aligns with recent findings in neuroscience that these areas do more than just process basic touch or sight.

Key Results

  • Consistency: In synthetic tests, GHSIC accurately tracked the "oracle" HSIC (a version that has access to the hidden latent positions) as the node count $n$ grew from 100 to 3,000.
  • Power and Speed: By using truncated SVD, the method achieves a quadratic runtime $O(n^2)$, making it computationally efficient enough for real-world biological networks.
  • Threshold Robustness: In the fMRI analysis, the test remained effective across various correlation thresholds used to define the brain networks, proving its practical utility.

Limitations and Future Work

The authors identify several paths for future research:

  • Improving the Rate: It remains an open question whether the $\tilde{O}(n^{-1/3})$ rate is an artifact of the current analysis or a fundamental limit. Future work might find estimators that reach the $O(n^{-1/2})$ speed of classical HSIC.
  • Broader Models: While LPRGs are flexible, extending this framework to other types of random graph models would broaden its impact.
  • Minimax Optimality: Determining the absolute best possible error bound (minimax lower bound) for this problem is still needed to understand how much room for improvement exists.

Summary updated

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.
BibTeX
@misc{wen2026joint,
  author = {Xiaoyi Wen and Zoltan Szabo},
  title = {{Joint Independence Testing for Latent Position Random Graphs}},
  year = {2026},
  eprint = {2610.34544},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34544},
}
Figure