PaperlayerView exact revision on arXiv

Source-linked AI summary

Connectome Smoothing via Low-rank Approximations

Runze Tang, Michael Ketcha, Alexandra Badea, Evan D. Calabrese, Daniel S. Margulies, Joshua T. Vogelstein, Carey E. Priebe, Daniel L. Sussman

arXiv:1609.01672v3stat.MEstat.ML

TL;DR

Estimating a population graph mean is challenging when only a small sample is available, because the mean is high-dimensional and the entry-wise sample mean does not exploit graph structure. The paper proposes a low-rank estimator with dimension selection and diagonal augmentation; it reports improved performance over the entry-wise estimator, including in cross-validation on SWU4 brain graphs.

  • Problem

    The population mean has O(N^2) parameters, and the entry-wise sample mean can have high variance and perform poorly when the graph sample is small.

    Source: §1 · p. 2, §3.1 · p. 6

  • Method

    The paper estimates the population mean with a low-rank approximation, using automatic dimension selection and diagonal augmentation for hollow adjacency matrices.

    Source: §1 · pp. 2–3, §3.2 · p. 6

  • Results

    The proposed estimator outperforms the entry-wise maximum-likelihood estimator in cross-validation analysis of SWU4 brain graphs.

    Source: §7 · p. 22

  • Takeaways & Limitations

    The low-rank estimates provide parsimonious, interpretable latent structure whose interpretations relate to established brain anatomy.

    Source: §1 · p. 3

    For fixed M and N, whether the low-rank estimate or the entry-wise sample mean performs better is a difficult theoretical question beyond the manuscript’s scope.

    Source: §4.3 · p. 10

Abstract

from arXiv · show

In statistical connectomics, the quantitative study of brain networks, estimating the mean of a population of graphs based on a sample is a core problem. Often, this problem is especially difficult because the sample or cohort size is relatively small, sometimes even a single subject. While using the element-wise sample mean of the adjacency matrices is a common approach, this method does not exploit any underlying structural properties of the graphs. We propose using a low-rank method which incorporates tools for dimension selection and diagonal augmentation to smooth the estimates and improve performance over the naive methodology for small sample sizes. Theoretical results for the stochastic blockmodel show that this method offers major improvements when there are many vertices. Similarly, we demonstrate that the low-rank methods outperform the standard sample mean for a variety of independent edge distributions as well as human connectome data derived from magnetic resonance imaging, especially when sample sizes are small. Moreover, the low-rank methods yield "eigen-connectomes", which correlate with the lobe-structure of the human brain and superstructures of the mouse brain. These results indicate that low-rank methods are an important part of the tool box for researchers studying populations of graphs in general, and statistical connectomics in particular.

1 Introduction

Estimating a graph population mean is difficult when the number of sampled graphs is small relative to the high-dimensional mean. The paper proposes low-rank estimation to trade bias for reduced variance, with potential gains in accuracy and interpretability.

1 Introduction

  • With N vertices, the population mean has O(N^2) parameters, so small samples can make naive unbiased estimates highly variable and inaccurate.This setting is common in studies of higher-resolution connectomes and small or hard-to-sample subpopulations.Source: §1 · p. 2
  • Improved mean-graph estimation may also support downstream inference, including two-group network-distribution testing [2] and community detection.Source: §1 · p. 2
  • The entry-wise sample mean is reasonable without structural assumptions, but its high variance can make it perform poorly at small sample sizes.The paper motivates incorporating known graph structure when computationally tractable.Source: §1 · p. 2
  • The proposed low-rank estimator trades bias for lower variance, which can reduce overall estimation error.The paper also notes that many full-rank statistical models may be well approximated by low-rank structures.Source: §1 · pp. 2–3
  • The method combines low-rank approximation with network-specific handling of bounded entries and missing diagonal values, and considers two automatic rank-selection methods.Source: §1 · p. 3
  • Low-rank spectral methods have prior uses in connectomics, and this work specifies when and how they can improve mean-graph estimation.Prior applications include functional-connectivity shrinkage and connectome harmonics.Source: §1 · p. 3
  • The resulting latent-structure estimates are parsimonious and interpretable, with interpretations related to established brain anatomy and possible mapping of brain-organization hierarchies.Source: §1 · p. 3

2 Statistical Connectome Models

The paper represents connectomes as aligned adjacency matrices and defines their population mean as the expected adjacency matrix. It then describes independent-edge, random-dot-product, and stochastic-block models, including assumptions and relationships among them.

2 Statistical Connectome Models

  • The setup considers M aligned graphs with N vertices, represented by undirected, unweighted binary adjacency matrices with no self-loops.Source: §2 · pp. 3–4
  • The mean graph P is the expected adjacency matrix, a definition that does not require a particular graph-distribution assumption.Source: §2 · p. 4

2.1 Independent Edge Model

  • In the independent edge model, each edge occurs independently with probability P_ij; this assumption supports the theory but may not hold for brain graphs with spatial or functional dependencies.The method can still improve performance when P has low-rank structure and estimates low-rank structure regardless of P's structure.Source: §2.1 · p. 4

2.2 Random Dot Product Graph

  • The random dot product graph assigns each vertex a latent position, with edge probabilities given by dot products; its mean matrix P = XX^T is positive semidefinite and has rank at most d.Source: §2.2 · pp. 4–5

2.3 Stochastic Blockmodel as an RDPG

  • The stochastic blockmodel makes edge probabilities depend on vertices’ block memberships and, under the paper’s positive-semidefinite block-matrix condition, can be represented as a random dot product graph.The RDPG framework also represents mixed-membership and degree-corrected SBMs.Source: §2.3 · p. 5

3 Estimators

The paper contrasts the entry-wise sample mean with a low-rank estimator designed to exploit graph structure. The proposed estimator selects an embedding dimension, iteratively augments the diagonal, and bounds its final entries.

3.1 Element-wise Sample Mean ¯

  • For independent-edge graphs, the entry-wise sample mean is the maximum-likelihood and uniformly minimum-variance unbiased estimator, but it is not consistent for low-rank P as N grows with fixed M.Its entry-wise variance is P_ij(1 − P_ij)/M.Source: §3.1 · p. 5
  • When M is small relative to N, the sample mean can perform poorly; at M = 1 it is simply the observed binary adjacency matrix.Source: §3.1 · p. 6

3.2 Low-Rank Estimator ˆ

  • The proposed estimator spectrally approximates the sample mean with a low-rank matrix, exploiting structure such as that motivated by the random dot product graph.It is similar to the estimator in but adds adjustments for mean-graph estimation.Source: §3.2 · p. 6
  • The estimator chooses its embedding dimension using either an elbow method or universal singular value thresholding.Source: §3.2 · p. 7
  • Because hollow adjacency matrices have missing diagonal entries, the algorithm augments the diagonal iteratively, then clips estimated entries to the interval [0, 1].The diagonal adjustments are intended to improve performance for mean-graph estimation.Source: §3.2 · pp. 6–7

4 Theoretical Results

The theoretical comparison uses relative efficiency (RE), the ratio of the estimators’ mean squared errors, with values below 1 favoring the low-rank estimator. Under SBM and RDPG assumptions, its relative efficiency improves as the number of vertices grows; results for full-rank models are more conditional.

4 Theoretical Results

  • RE is the ratio of the estimators’ mean squared errors; values below 1 favor the low-rank estimate, while values above 1 favor the sample mean.The passage describes RE as useful for comparing estimators across settings because it is often invariant to noise scale.Source: §4 · pp. 7–8

4.1 SBM

  • Under the SBM, RE is O(N^-1) as N grows, and its asymptotic behavior does not depend on the number of graphs M.For block sizes near balance, the passage gives an approximate RE of 4/N; some cross-block edges can instead have RE near 1 when one block dominates.Source: §4.1 · p. 9

4.2 RDPG

  • For RDPG graphs, RE between the sample mean and low-rank estimator is O(1/N), with asymptotic behavior independent of M.The passage notes that no compact analytical formula is available for the general RDPG case.Source: §4.2 · p. 10

4.3 Generalizations

  • When the mean graph is full-rank or nearly full-rank, the theory does not guarantee that the low-rank estimator will outperform the sample mean.For fixed M and N, which estimator performs better is described as a difficult theoretical question beyond the manuscript’s scope.Source: §4.3 · p. 10
  • For full-rank independent-edge models, RE can increase with M and may reach or exceed 1 because dimension selection is not guaranteed to be optimal.As M grows, more sample-mean eigenvectors concentrate around those of the mean graph, and the optimal embedding dimension increases.Source: §4.3 · p. 10
  • The theory extends to sparse graphs with average degree as small as θ(log^4 N), based on extensions of the proof results.Source: §4.3 · p. 10

5 Human Connectomes

Across the human connectome atlases, the low-rank estimate is most advantageous with small samples, while its performance depends on whether the target is the full mean graph or its low-rank structure. Its latent dimensions also correspond to brain anatomy, with lobe associations persisting after accounting for spatial geometry.

5 Human Connectomes

  • Cross-validation compares estimates from sampled graphs with the entry-wise mean of all 454 SWU4 graphs across three atlases, sample sizes, and two dimension-selection procedures.The graphs represent brain regions under the JHU, Desikan, or CPAC200 atlas; the procedures are Zhu and Ghodsi’s method and USVT.Source: §5 · pp. 11, 13
  • At M = 1, ˆP achieves MSE 0.049 versus 0.104 for ¯A, a 53% relative improvement.Figure 1 also shows 234 edges above the 0.4 error threshold for ˆP, versus 504 for ¯A.Source: §5 · p. 11, Figure 1 · p. 12
  • Across atlases, ˆP substantially improves on ¯A at M = 1 or 5 (RE < .7), but at M = 10 only ZG continues to improve on ¯A.For M = 5 in the Desikan example, MSE is 0.015 for ˆP and 0.016 for ¯A, a 3% relative improvement.Source: §5 · pp. 11, 13, Figure 2 · p. 13

5.1 Challenges of the SWU4 Dataset

  • The SWU4 population mean is not well approximated by low-rank matrices, yet ˆP performs better than ¯A for small samples and larger atlases.For large M, ˆP performs poorly when estimating the full mean P but well when estimating its selected low-rank approximation P_d*; negative eigenvalues and entries equal to 1 also pose challenges.Source: §5.1 · pp. 14–15

5.2 Eigen-connectomes and Lobe Structure

  • In the Desikan atlas, the first latent dimension correlates strongly with vertex degree, the second distinguishes hemispheres, and other dimensions qualitatively correspond to lobes.The latent positions are estimated from the mean graph using dimension d = 8 selected by Zhu and Ghodsi’s method.Source: §5.2 · p. 16
  • The paper frames these latent dimensions as interpretable eigen-connectomes related to anatomical structure, while noting their similarity to structural connectome harmonics.The authors suggest these representations may support multivariate analysis of the mean graph and future study of cortical hierarchies.Source: §5.2 · pp. 16–17
  • After conditioning on anatomical geometry, the lobe-association test finds p < 0.05 when the lobe assignment has been flipped more than seven times.The flips preserve lobe size and spatial contiguity, though few flips provide little power and many can eventually break contiguity.Source: §5.2 · pp. 17, 19

6 Application to a Mouse Connectome

The mouse connectome analysis applies low-rank approximation to a single weighted, directed graph and finds that its singular vectors reflect aspects of the brain’s superstructure organization. A permutation analysis also finds the eight superstructures significant after accounting for spatial structure.

6 Application to a Mouse Connectome

  • The connectome contains 296 brain regions arranged into eight superstructures, with four in each hemisphere.The analysis partitions the label set into forebrain, midbrain, hindbrain, and white matter in each hemisphere.Source: §6 · pp. 19–20
  • The rank-7 approximation visually captures many features of the single-observation mouse connectome, although cross-validation was unavailable at M = 1.The 296-node weighted adjacency matrix was transformed using log(W_ij + 1) before approximation.Source: §6 · p. 20, Figure 8 · p. 20
  • The second and fourth singular vectors correlate closely with superstructure and hemisphere groupings, while the first appears to separate the midbrain from other superstructures.The scatter-plot classifier has training error 87/296 ≈ 0.29; excluding white matter, 29/236 ≈ 0.12 vertices were misclassified.Source: §6 · pp. 20–21, Figure 9 · p. 21
  • The permutation analysis indicates that all eight superstructures remain significant after accounting for the regions’ spatial structure.Source: §6 · p. 21

7 Discussion

The discussion reports that low-rank estimation can improve mean-graph estimation in theory and in several empirical settings, while emphasizing that performance depends on sample size and method choices. The appendices examine dimension selection and diagonal augmentation as parts of that trade-off.

7 Discussion

  • The low-rank estimator outperforms the entry-wise MLE in SWU4 cross-validation and low- and full-rank simulations when M is small, and theoretical SBM results show substantial improvements.The theoretical analysis concerns lowrank_d(Ā); under dense low-rank models, the proposed estimator’s asymptotic difference from it is typically small.Source: §7 · p. 22
  • Many random-network mean graphs may have low-rank structure, but the method assumes uncontaminated adjacency matrices and may need robust refinements for heavy-tailed noise.Source: §7 · p. 22
  • For human connectomes, low-rank gains are largest at small sample sizes and may be minor or slightly negative when M is large.The discussion notes that small subpopulations can still have fewer than ten subjects, even in large studies.Source: §7 · p. 22

A.1 Choosing Dimension

  • Dimension selection is difficult, but many dimensions yield nearly optimal MSE; underestimating dimension is more harmful than overestimating it, motivating use of the third Zhu–Ghodsi elbow.USVT selects singular values above c√(N/M), with c = 0.7 in these experiments.Source: §A.1 · p. 28

A.1.1 Exploration of Dimension Selection Procedures

  • Both dimension-selection algorithms tend to choose dimensions near the MSE minimum; with M = 1 or 5, low-rank smoothing performs better across a wide dimension range.At M = 1, the sample mean is binary and bumpy; as M grows, it often performs better but is nearly identical to the low-rank estimate.Source: §A.1.1 · pp. 28–29

A.2 Graph Diagonal Augmentation

  • Because hollow adjacency matrices have structural zero diagonals, low-rank approximation can incur error; the method combines row-average diagonal imputation with one iterative augmentation step.Errors are computed omitting the diagonal, whose entries are known to be zero.Source: §A.2 · p. 29

A.3 Evaluation of Method Choices

The method-choice evaluation finds that the selected defaults improve performance overall in the examined settings, although individual choices can matter and are not universally best. The appendix also describes spatially constrained label permutations for testing lobe structure.

A.3 Evaluation of Method Choices

  • The evaluated defaults improve performance overall in the Desikan and CPAC200 settings, and are nearly always competitive across the compared alternatives.Figure 11 compares relative efficiency across atlases and parameter choices; opaque lines mark defaults and transparent lines mark alternatives.Source: §A.3 · p. 31, Figure 11 · p. 32
  • Diagonal augmentation generally improves relative efficiency, especially at large M, though the second step can hurt performance for CPAC200 when M is small.The first augmentation’s impact is small but essentially universally positive; the second can have a larger impact.Source: §A.3 · p. 31
  • Keeping the largest positive eigenvalues usually improves performance, but for large M with USVT, keeping the largest-magnitude eigenvalues is preferable.Source: §A.3 · p. 31
  • USVT can outperform Zhu–Ghodsi for the Desikan atlas at larger M when retaining eigenvalues by magnitude, plausibly because it selects a larger dimension.Source: §A.3 · p. 31

A.4 Flipping Procedure for Permutation Test

  • A uniform 1-flip swaps two regions across the same lobe boundary while preserving each lobe’s size; k-flips repeat this operation, and the permutation p-value counts flips with smaller T.Source: §A.4 · p. 33

B Dataset Description

The appendix describes the human and mouse connectome datasets and outlines the stochastic blockmodel variance argument underlying the theory. In that argument, the low-rank estimate’s entrywise variance decreases with the number of vertices relative to the sample mean’s variance.

B.1 Human Connectomes

  • The human dataset contains 454 scans from 235 college students, each scheduled for two anatomical and resting-state DTI sessions one year apart.Incomplete data account for the difference between the number of subjects and available scans.Source: §B.1 · p. 33
  • Human connectomes are undirected, unweighted graphs without self-loops, with edges representing tract connections between atlas-defined brain regions.The Desikan atlas has 70 regions; three regions per hemisphere without obvious lobe assignments are grouped as “other.”Source: §B.1 · pp. 33–34

B.2 Mouse Connectome

  • The mouse dataset is a 296 × 296 weighted, directed graph derived from tractography, with 296 regions of interest.Source: §B.2 · p. 34

C.1 Outline for Main Theorems

  • In the SBM outline, the low-rank estimate’s entrywise variance converges to P_ij(1 − P_ij)/(N · M), versus P_ij(1 − P_ij)/M for the sample mean.The stated relative efficiency is approximately (ρ − 1/τ_j)/N when N is sufficiently large.Source: §C.1 · p. 35

C.2 Proof Details

The proof appendix develops the stochastic blockmodel results using fixed memberships across graphs and a central limit theorem, then combines lemmas to derive the relative-efficiency result.

C.2 Proof Details

  • The proof assumes block memberships are fixed across graphs for a given N and uses a central limit theorem adapted to the multiple-graph setting.The theorem is presented for the stochastic blockmodel.Source: §C.2 · p. 35
  • Under the stochastic blockmodel, the graph mean has entries Pij = Bτi,τj, and the proof represents the block matrix as B = νν⊤.The proof takes B to have rank K and be positive definite.Source: §C.2 · pp. 35–36
  • The proof combines the MSE results for the sample mean and low-rank estimator with Lemma 4.1 to obtain the relative-efficiency result.The appendix describes the ARE result as following by taking the limit of relative efficiency as N grows.Source: §C.2 · p. 37
  • Figure 12 plots relative efficiency by block pair and its scaled version, with a horizontal line for the theoretical asymptotic scaled relative efficiency.Its caption identifies the top panel as relative efficiency versus N for fixed M = 100 in SBM simulations.Source: §C.2 · p. 38, Figure 12 · p. 38

D SBM Simulations

SBM simulations show that the low-rank estimator improves relative efficiency as the number of vertices grows. The scaled efficiency approaches its theoretical limit, while small-graph differences between block pairs have an unclear explanation.

D SBM Simulations

  • Relative efficiencies for all three block pairs are much less than 1 and decrease at rate 1/N, indicating better performance by the low-rank estimator than the sample mean.Figure 12 plots these estimates for a two-block SBM; values below 1 favor the low-rank estimator.Source: D SBM Simulations · p. 39
  • The scaled relative efficiency converges rapidly to the theoretical asymptote 4 as N grows.The asymptotic value is given as 1/ρτi + 1/ρτj = 4 for all vertex pairs.Source: D SBM Simulations · p. 39
  • For small graphs, cross-block edge-probability estimates are better than within-block estimates, but the reason is unclear.The passage suggests more cross-block pairs could increase effective sample size; these differences are nearly indistinguishable in unscaled relative efficiency overall.Source: D SBM Simulations · pp. 39–40

E Synthetic Data Analysis for Full Rank IEM

In simulations using a full-rank independent-edge probability matrix based on the Desikan dataset, the low-rank estimator outperforms the sample mean at small sample sizes across a flexible range of embedding dimensions. Its relative efficiency is more favorable than in the real-data analysis.

E Synthetic Data Analysis for Full Rank IEM

  • The synthetic analysis samples independent graphs from a full-rank probability matrix equal to the sample mean of the 454 Desikan graphs.The simulations examine sample sizes M = 1, 5, and 10.Source: E Synthetic Data Analysis for Full… · p. 40
  • For small M, the low-rank estimator outperforms the sample mean across flexible embedding dimensions, including dimensions selected by Zhu and Ghodsi.For large enough M, both estimators perform well and the comparison is less conclusive.Source: E Synthetic Data Analysis for Full… · p. 40
  • At M = 1, relative efficiency is lower than 1/3 in the synthetic analysis, versus best values around 1/2 in the original real-data analysis.The authors suggest real-data degradation may partly reflect violation of the independent-edge assumption.Source: E Synthetic Data Analysis for Full… · p. 40

F Analysis of Mouse Superstructures

The mouse-connectome permutation analysis examines whether latent positions correlate with superstructures after conditioning on spatial structure. The null distribution moves farther from the true-assignment reference as flips increase.

F Analysis of Mouse Superstructures

  • The mouse-connectome analysis uses a permutation test with 1,000 simulations for each number of flips.Figure 14 is described as analogous to the permutation analysis for the human data.Source: F Analysis of Mouse Superstructures · p. 40, Figure 14 · p. 42
  • As the number of flips increases, the null distribution moves farther from the dashed line representing the true superstructure assignment.This is the comparison depicted in Figure 14's violin plot.Source: Figure 14 · p. 42
  • The passage interprets the permutation result as indicating that latent positions correlate with mouse superstructures even after conditioning on spatial structure.Source: Figure 14 · p. 42

Related papers

Loading 1609.01672v3…