PaperlayerView exact revision on arXiv

Source-linked AI summary

Large-scale directed network inference with multivariate transfer entropy and hierarchical statistical testing

Leonardo Novelli, Patricia Wollstadt, Pedro Mediano, Michael Wibral, Joseph T. Lizier

arXiv:1902.06828v2q-bio.NCcs.ITcs.SImath.ITphysics.data-an

TL;DR

Large-scale network inference from time series faces multiple comparisons that can inflate false positives, alongside computational demands that have limited validation scale. This paper uses statistical tests designed for family-wise error control and parallel computation, and validates the method on synthetic networks with linear and nonlinear dynamics. For 10,000 samples, precision, recall, and specificity were consistently above 98% on average, and the study reports feasibility for typical EEG and MEG experiments.

  • Problem

    Multiple comparisons in network inference can inflate false positives without family-wise error control, while nonparametric surrogate testing is computationally demanding.

    Source: §I · p. 2

  • Method

    The algorithm uses rigorous statistical tests to control the family-wise error rate and supports parallel analysis of targets.

    Source: §I · p. 2

  • Results

    Precision, recall, and specificity were consistently above 98% on average for 10,000 samples in synthetic-network validation.

    Source: §IV · p. 15

  • Takeaways & Limitations

    The study reports that validation at up to 100 nodes and 10,000 samples shows feasibility for typical EEG and MEG experiments.

    Source: §IV · pp. 15–16

    The analysis assumes stationarity within each experimental time window, so distinct regimes can be studied window by window.

    Source: §IV · p. 15

Abstract

from arXiv · show

Network inference algorithms are valuable tools for the study of large-scale neuroimaging datasets. Multivariate transfer entropy is well suited for this task, being a model-free measure that captures nonlinear and lagged dependencies between time series to infer a minimal directed network model. Greedy algorithms have been proposed to efficiently deal with high-dimensional datasets while avoiding redundant inferences and capturing synergistic effects. However, multiple statistical comparisons may inflate the false positive rate and are computationally demanding, which limited the size of previous validation studies. The algorithm we present---as implemented in the IDTxl open-source software---addresses these challenges by employing hierarchical statistical tests to control the family-wise error rate and to allow for efficient parallelisation. The method was validated on synthetic datasets involving random networks of increasing size (up to 100 nodes), for both linear and nonlinear dynamics. The performance increased with the length of the time series, reaching consistently high precision, recall, and specificity (>98% on average) for 10000 time samples. Varying the statistical significance threshold showed a more favourable precision-recall trade-off for longer time series. Both the network size and the sample size are one order of magnitude larger than previously demonstrated, showing feasibility for typical EEG and MEG experiments.

I. INTRODUCTION

Large-scale multivariate time-series analysis needs efficient ways to manage model complexity, estimation difficulty, and multiple statistical tests. The paper presents statistical testing compatible with parallel analysis and validates the method on synthetic networks, while defining the target and past-variable sets used in inference.

A. Definitions and assumptions

  • For each target, inference selects past variables that help explain its present state; selected target and source pasts are defined from candidate sets up to specified maximum lags.Each process can be studied as the target, and results can be combined into a directed network of information flows.Source: §I · p. 2, A. Definitions and assumptions · p. 3

I. INTRODUCTION

  • Multiple comparisons can inflate false positives without family-wise error control, while naive controls can produce high false negatives and nonparametric surrogate testing is computationally demanding.The task also faces a rapidly growing network-model state space and the curse of dimensionality in information-theoretic estimation.Source: §I · p. 2
  • Rigorous statistical tests control the family-wise error rate and support parallel analysis of targets, addressing computational and multiple-testing challenges.The implementation is available in the IDTxl open-source Python package.Source: §I · p. 2
  • For 10,000 time samples, precision, recall, and specificity were consistently above 98% on average in synthetic-network validation.The validation included vector autoregressive processes and coupled logistic maps; longer series also showed a more favourable precision-recall trade-off across significance thresholds.Source: §I · p. 3

B. Inference algorithm

For each target, the algorithm seeks a minimal set of information contributors and uses a four-step procedure to construct a nonuniform embedding of the relevant time series.

B. Inference algorithm

  • The algorithm seeks the minimal set of information contributors to the target’s present state, defined through selected target and source pasts.The resulting embedding specifies relative lags between selected variables rather than using a uniform set of delays.Source: B. Inference algorithm · pp. 3–4
  • The four steps select target-past variables, select source-past variables, prune selected sources, and test relevant variables collectively for statistical significance.The selected source past is evaluated in the context of the selected target past.Source: B. Inference algorithm · pp. 3–4
  • The nonuniform embedding represents the selected target and source past variables relevant to the target’s present state.The figure illustrates one trial; its target present state is distinguished from candidate target-past variables.Source: B. Inference algorithm · p. 4, Figure 2 · p. 4

1. Step 1: Select variables in the candidate target past set

The first step selects target-past variables that reduce uncertainty about the target’s present state, using a greedy search and statistical significance tests.

1. Step 1: Select variables in the candidate target past set

  • The selected target past is the subset that maximally reduces uncertainty about the target’s present state while meeting statistical significance requirements.The algorithm initializes the set as empty and iteratively adds a candidate when its conditional mutual information contribution is significant.Source: §1 · p. 5
  • A greedy approximation is used because finding the globally optimal embedding is NP-hard and requires testing exponentially many candidate subsets.At each iteration, the candidate with the greatest conditional mutual information contribution is tested against conditional independence.Source: §1 · p. 5
  • The maximum statistic is used to control the family-wise error rate during target-past selection.Selection repeats until the maximum conditional mutual information contribution is no longer significant or the candidate set is exhausted.Source: §1 · p. 5

2. Step 2: Select variables in the candidate sources past set

The second step greedily selects source-past variables that add information about the target in the context of the selected target past, then tests and prunes the selected sources.

2. Step 2: Select variables in the candidate sources past set

  • The source-past search uses a greedy approximation and maximum-statistic testing to control the family-wise error rate, repeating until the maximum contribution is not significant.The selected source past is the subset that further reduces uncertainty about the target in the context of its selected past.Source: §2 · p. 5
  • Source-past candidates are selected by maximizing conditional transfer entropy given the selected target past, and significant candidates are added iteratively.When no source past has yet been selected, the conditional transfer entropy reduces to pairwise transfer entropy.Source: §2 · p. 5
  • Conditioning on the selected target past helps exclude source candidates carrying only redundant information while allowing synergistic interactions to be captured.The source past is optimized in the context of the target past selected in the first step.Source: §2 · p. 5

3. Step 3: Prune the selected sources past variables

The algorithm prunes selected sources that no longer contribute significantly in the context of the final set, then tests the retained sources collectively. Its statistical tests address finite-sample uncertainty and multiple comparisons.

3. Step 3: Prune the selected sources past variables

  • The pruning step repeatedly removes the selected source with the weakest conditional mutual information contribution when it is not significant, controlling the family-wise error rate.Sun et al. [17] proved pruning essential for theoretical convergence in the Granger-Wiener framework.Source: §3 · p. 6

4. Step 4: Test relevant variables collectively for statistical significance

  • The retained sources are tested collectively for nonzero transfer entropy, and are accepted for a target only if all statistical tests pass.The omnibus p-value can also be used for family-wise error correction across multiple targets.Source: §4 · p. 6

C. Statistical tests

  • Finite-sample CMI estimates can be nonzero or negative under a null of conditional independence, so significance tests calibrate the inference.When analytic null distributions are unavailable, surrogates destroy source-target temporal relationships while preserving dependencies within sources.Source: C. Statistical tests · p. 6

1. Maximum statistic test

The maximum statistic test evaluates the largest candidate contribution against a surrogate null distribution, controlling family-wise error during source selection.

1. Maximum statistic test

  • The test mirrors greedy selection by taking the largest CMI contribution among candidates and comparing it with surrogate maxima.For each surrogate, the maximum across the n candidates forms one value in the empirical null distribution.Source: §1 · p. 7, Table I · p. 7
  • The observed maximum is significant when the fraction of surrogate maxima greater than it is below αmax.The number of surrogates S must exceed 1/αmax.Source: §1 · p. 7
  • Surrogates preserve the target's temporal order and source distributions while disrupting potential source-target relationships.Replication order is shuffled when there are enough replications; otherwise, embedded source samples within trials are shuffled.Source: §1 · p. 7
  • The empirical null distribution comprises the maximum candidate CMI from each surrogate and is used to test the observed maximum against zero CMI.Table I defines each surrogate maximum as the maximum across the n candidate values.Source: Table I · p. 7

2. Family-wise error rate correction

The maximum-statistic correction calibrates candidate selection against the maximum under the null, addressing multiple comparisons while controlling family-wise error.

2. Family-wise error rate correction

  • A maximum exceeds a threshold if and only if at least one statistic exceeds it, allowing the maximum's null distribution to set an adjusted threshold.This controls family-wise error in both the weak and strong senses.Source: §2 · p. 7
  • The maximum-statistic correction is equivalent to the Dunn–Šidák correction.Its false-positive rate is less stringently controlled than with Bonferroni correction.Source: §2 · p. 8
  • αmax effectively controls the family-wise error rate for a single target for typical small significance levels, even as the candidate count grows.The analysis accounts for the iterations of the step-down test.Source: §2 · p. 8

3. Minimum statistic test

The procedure prunes redundant selected sources, tests retained sources collectively, and combines target-level tests hierarchically. Its validation evaluates performance across synthetic network sizes and time-series lengths.

3. Minimum statistic test

  • The minimum statistic test removes selected variables that are no longer significant in the context of the final source set, controlling family-wise error during pruning.It applies the maximum-statistic procedure with minimum substituted for maximum.Source: §3 · p. 8

4. Omnibus test

  • The omnibus test assesses whether the selected sources collectively transfer nonzero information to a target using shuffled-source surrogates.Across targets, omnibus p-values can support family-wise error correction, such as FDR correction.Source: §4 · p. 9, §5 · p. 9

5. Combining across multiple targets

  • Hierarchical testing offers greater recall and parallel computation across targets than network-wide link correction, but can discard strong links into targets with nonsignificant overall transfer.The difference may be noticeable for high average in-degree and relatively uniform link transfer; a conservative lower-level threshold can reduce it.Source: §5 · p. 9

D. Validation tasks

  • The validation expected inferred networks to reflect structural networks under causal sufficiency and the causal Markov condition, with sufficiently large samples.The authors note that these assumptions do not always hold.Source: D. Validation tasks · p. 9
  • Validation used random directed networks of 10–100 nodes and time series of 100–10,000 samples, testing precision, recall, and specificity for VAR and coupled logistic-map dynamics.The simulations used a single replication and ten random initial conditions.Source: D. Validation tasks · p. 10

1. Vector autoregressive process

The study tests network inference on linear VAR and nonlinear coupled logistic-map processes. Performance improves with longer time series and is high across network sizes at 10,000 samples.

1. Vector autoregressive process

  • The VAR benchmark uses lagged causal-source inputs, a self-coupling term, and Gaussian noise, with parameters chosen to ensure stable stationary processes.The Gaussian estimator is used for transfer-entropy measurements on these processes.Source: §1 · p. 10

2. Coupled logistic maps process

  • Coupled logistic maps apply a nonlinear logistic activation to weighted past inputs, with Gaussian noise and modulo-1 values confined to [0, 1].Nearest-neighbour estimators are used for transfer-entropy measurements on these processes.Source: §2 · p. 10

A. Influence of network size and length of the time series

  • The evaluation compares inferred links with the known structural network using binary-classification statistics, with αmax = 0.001 and 1,000 surrogates by default.Candidate source and target histories use a maximum lag of five.Source: A. Influence of network size and… · p. 11
  • At T = 10,000, both VAR and CLM achieved high performance across all measures regardless of network size; high precision and specificity reflected effective false-positive control under αmax = 0.001.For both dynamics, performance increased with sample count and decreased with network size.Source: A. Influence of network size and… · p. 11

B. Validation of false positive rate

The tests keep false-positive rates in line with the chosen threshold across network sizes. The results also show how threshold choice, sample length, lag estimation, and estimator choice shape inference performance.

B. Validation of false positive rate

C. Influence of critical level for statistical significance

  • At T = 100, raising αmax increases recall but lowers precision; at T = 1,000, recall rises without a precision penalty, while T = 10,000 is largely unaffected.Figure 5 summarizes the precision–recall trade-off across significance levels, dynamics, and network sizes.Source: C. Influence of critical level for… · p. 12, Figure 5 · p. 13

D. Inference of coupling lags

  • Lag error is below the random expectation even for the shortest series, and 1,000 samples yield nearly optimal lag inference across network sizes and both dynamics.As recall increases, lag error can also rise when newly identified weak sources are not estimated precisely.Source: D. Inference of coupling lags · p. 14, Figure 6 · p. 14

E. Estimators

  • For nonlinear coupled logistic maps, the Gaussian estimator performs worse than the nearest-neighbour estimator at every network size.The hierarchical tests also permit target-wise parallel analysis on CPU or GPU, particularly useful with the nearest-neighbour estimator.Source: E. Estimators · p. 14, Figure 7 · p. 14

IV. DISCUSSION

For 10,000 samples, the method achieved high precision and recall across linear and nonlinear dynamics, while performance depended on sample length and network size. The discussion connects false-positive control to reliable network analysis and states assumptions and potential applications of the approach.

IV. DISCUSSION

  • False positives can distort network topology because spurious inter-module links strongly affect clustering, efficiency, and modularity measures.The discussion cites the view that specificity is at least twice as important as recall for estimating these properties.Source: §IV · p. 15
  • With 100 samples, average recall gain was over five times smaller than precision loss; with 1,000 samples, recall gain was over five times larger than precision loss.The authors suggest a conservative threshold for sparse networks and short series, possibly because of network sparsity.Source: §IV · p. 15
  • At 10,000 samples, precision and recall exceeded 98% on average for both dynamics regardless of significance threshold; the validation reached scales one order larger than previously demonstrated.The conclusion identifies synthetic nonlinear systems with 100 nodes and 10,000 samples as within the study’s demonstrated scope.Source: §IV · pp. 15–16
  • For both dynamics, performance increased with time-series length and decreased with network size, as larger networks require stricter family-wise error control.The wider maximum-statistic null distributions in larger networks can make true links harder to detect, especially for short series and small effects.Source: §IV · p. 15
  • On nonlinear logistic-map processes, the Gaussian estimator had significantly lower recall than the nearest-neighbour estimator, yet detected over half the links with 10,000 samples.Nearest-neighbour estimators are more computationally complex and slower, which helps explain why Gaussian estimation is often used for large datasets despite an unjustified Gaussian hypothesis.Source: §IV · p. 15
  • Convergence to the underlying causal network was proven only under stationarity, causal sufficiency, and the causal Markov condition; conditional-independence relations hold under milder assumptions.The discussion notes that such relations can help exclude variables in later intervention-based causal experiments.Source: §IV · p. 15

VII. AUTHOR CONTRIBUTIONS

  • Conceptualization, software, and writing involved all listed authors; Novelli also led data curation, formal analysis, investigation, validation, and visualization.Wibral and Lizier additionally contributed methodology, funding acquisition, and supervision.Source: §VII · pp. 16–17

A. Run-time on CPU and GPU

The supplementary analyses report runtime scaling and test false-positive calibration on real fMRI data, while the accompanying figures reorganize performance results by sample size and significance threshold.

A. Run-time on CPU and GPU

  • CPU processing parallelizes over targets, while GPU processing can parallelize over targets and surrogates; per-calculation costs are O(kTlogT) for nearest-neighbour CPU and O(T) for Gaussian CPU.GPU calculations are O(T^2); parallelizing over time samples is also possible when memory permits.Source: A. Run-time on CPU and GPU · p. 19
  • Analyzing all targets in parallel can reduce total runtime to a single-target runtime when N computing nodes are available, but requires N times the memory of single-node analysis.With one node, targets run in series and total runtime is the single-target runtime multiplied by N.Source: A. Run-time on CPU and GPU · p. 19
  • Runtime benchmarks used one CPU core or a dedicated NVIDIA V100 GPU per target; Table II summarizes maximum single-target runtimes across time-series lengths and network sizes.The reported CPU runtime per target can be reduced when multiple cores per target are available.Source: A. Run-time on CPU and GPU · p. 19, Table II · p. 19

B. Validation of false positive rate on real fMRI data

  • The HCP null test used 10 random ROIs from different subjects and 800 samples; nearest-neighbour results were consistent with synthetic-data calibration (Figure 8).The test assessed whether the false-positive rate matched the target αmax; Figure 8 plots average rates over 50 repetitions and their expected range.Source: B. Validation of false positive rate… · p. 20, Figure 8 · p. 20
  • The fMRI analysis used nearest-neighbour estimation because the real data could not be assumed Gaussian; IDTxl addresses autocorrelation by excluding temporally close points from the nearest-neighbour search.The Theiler-window size is adapted using autocorrelation decay time as a heuristic.Source: B. Validation of false positive rate… · p. 20

C. Alternative visualisations of performance scaling by network and sample size

Loading 1902.06828v2…