Graph-Guided Reduction of the Information Decomposition Lattice

Partial information decomposition (PID) splits the information that several "source" variables carry about a target into parts. Some information is unique to one source, some is redundant (shared across sources), and some is synergistic (available only when sources are seen together). The method is attractive for neuroscience, causal analysis, and model interpretability. It is also computationally hopeless beyond a handful of sources, because the number of parts, called atoms, follows the Dedekind numbers: 4 atoms for 2 sources, 18 for 3, 166 for 4, 7,581 for 5, and more than 7.8 million for 6 (Bits and pieces). Every existing exact method treats the sources as a fully interacting set, so all of those atoms have to be computed.

In practice the sources are almost never fully interacting. In a signaling network, a sensor factor graph, or a parse tree, we usually know or can estimate a dependency graph among sources and target. This proposal borrows the central move of kernelization, the theory of provably safe preprocessing that shrinks a hard instance to a core whose size depends only on a structural parameter. Applied to PID, the move is to use the dependency graph to provably zero out, merge, or factor atoms before any information measure is evaluated. The goal is an exact decomposition whose cost grows as the Dedekind number of a structural parameter $k$, much smaller than the source count $n$, together with an honest map of which graph structures allow this and which do not.

Core Claim

Suppose the joint distribution of sources $S_1,\dots,S_n$ and target $T$ is Markov with respect to a known graph $G$. For redundancy measures satisfying explicit axioms, three graph-checkable reduction rules shrink the redundancy lattice without changing any atom value.

The first is an irrelevance rule. If $S_i$ is d-separated from $T$ given every subset of the other sources, then every atom whose antichain mentions $S_i$ is zero, and $S_i$ can be deleted.

The second is a block factorization rule. If the sources split into blocks that the graph separates in a specified way, cross-block atoms are determined by quantities computed within each block. Which separation conditions suffice is an open question, and answering it is the main theoretical task.

The third is a bounded-interaction rule. When the graph bounds how many sources jointly affect $T$, for example through bounded in-degree or a small modulator (a small vertex set whose removal leaves a simple structure), synergistic atoms above that order vanish.

Under these rules, the exact decomposition costs

$$ \mathrm{cost} = D(k)\cdot \mathrm{poly}(n), $$

where $D(\cdot)$ is the Dedekind-type atom count and $k$ is the size of the largest irreducible block after reduction. This replaces $D(n)$.

The rules are not equally safe, and the second is the risky one. Two copies of $T$ placed in different blocks are conditionally independent given $T$, yet they share a large cross-block redundancy. Naive factorization therefore fails, and the correct separation condition must be stronger. Mapping where factorization holds and where it provably cannot hold is half the contribution. This mirrors the "knife-edge" dichotomies of parameterized complexity, where Dominating Set becomes tractable on graphs without the claw ($K_{1,3}$) as an induced subgraph and becomes hard again once $K_{1,4}$ is allowed (Philip et al.).

Relation to Prior Work

Two papers motivate the gap by hitting the lattice wall directly.

  • Bits and pieces grounds PID in part-whole logic and introduces the shared-exclusion measure $i^{sx}_\cap$, computed by Möbius inversion (the standard way to recover lattice atoms from cumulative quantities) over the full lattice.
  • Decomposing Interventional Causality builds the same lattice for interventional causal effects and states it "limits practical analysis to systems of about five variables."
  • Both assume the causal graph is known. Neither uses that graph to shrink the lattice; this proposal does exactly that.

The closest structural work replaces fine resolution with coarsening.

  • Information-theoretic signatures of causality proves that unique information and synergy identify parents, children, and co-parents. It avoids the lattice by lumping "the rest of the system" into a single supervariable, so it computes only two-source decompositions and gives up the multi-source atoms.
  • Measuring Multi-Source Redundancy in Factor Graphs derives closed-form redundancy for linear-Gaussian factor graphs and shows that redundancy follows the geometry of the graph. That is evidence that graph structure governs atom values, but the paper stops at a single redundancy score.

Coarse summaries constrain the design.

  • Rosas et al. (Characterising directed and undirected metrics) show that O-information and the redundancy-synergy index measure only the net balance of redundancy and synergy. They cannot separate "no interaction" from "large redundancy cancelling large synergy."
  • Score-based O-information estimation (SΩI) scales the summary to non-Gaussian data but inherits that blind spot.
  • Gaussian PID (Venkatesh et al.) scales to hundreds of feature dimensions but only to two sources. It supplies the estimator used inside each reduced block in the continuous experiments.

The method template comes from kernelization.

  • Carbonnel and Hebrard's loss-less kernels (On the Kernelization of Global Constraints) preserve every solution, not only one. That is the right notion here, because every atom must survive reduction unchanged.
  • Manurangsi's sparsity-specific sunflower lemma (Biclique-Free Max k-Weight SAT) shows that forbidding dense bipartite substructures collapses exponentially many combinations to polynomially many. It is the model for the bounded-interaction rule.
  • Limits of Preprocessing proves that structural parameters such as treewidth and loop-cutset size do not guarantee polynomial kernels for constraint satisfaction and Bayesian inference. It warns that treewidth alone may not suffice for lattice reduction either, and the dichotomy study tests that warning directly.

Research Program

Theory: rules and axioms. The first theoretical aim is to state each reduction rule together with the axioms on the redundancy measure under which it is exact. The irrelevance rule should follow from any measure whose redundancy over collections is a function of the mutual informations $I(S_A;T)$ for source subsets $A$, but this must be checked for $i^{sx}_\cap$ and for the minimum-mutual-information measure.

Theory: block factorization. The second aim is to find separation conditions under which factorization holds. The candidate conditions are blocks that are independent given $T$ and also contain no deterministic copy of $T$, or blocks separated by a small cut through which all target information must pass. Counterexamples showing that weaker conditions fail are as important as the positive results.

Theory: dichotomy over graph parameters. The third aim is a dichotomy across the parameters common in this literature: in-degree of $T$, modulator size, neighborhood diversity, and treewidth. For each parameter, the question is whether the irreducible core is bounded by a function of it. The working conjecture is that bounded-width chains still allow high-order synergy, so treewidth fails as a parameter, consistent with Szeider's incompressibility results.

Algorithm and software. The algorithm takes $G$ and a redundancy measure. It applies the rules to a fixed point and runs Möbius inversion only on irreducible blocks. It then lifts the results back to a full atom table, reporting zeros explicitly. Continuous blocks use the Gaussian estimator. Discrete blocks use exact plug-in estimates on synthetic data and $i^{sx}_\cap$.

Robustness when the graph is estimated. When $G$ is learned rather than given, a wrong d-separation can wrongly delete a source. A conservative variant handles this by applying a rule only when an independence test rejects the dependence that would invalidate it, and by measuring how much mass the deleted atoms would have carried.

Baselines

Full Möbius inversion. The naive reference is full Möbius inversion over the unreduced lattice with the same redundancy measure, as in Bits and pieces and Decomposing Interventional Causality. It is also the exactness oracle. Wherever it runs ($n \le 5$, and $n=6$ for single runs on sparse instances), the reduced method must match every atom to numerical precision on the same distribution. Beyond that range the comparison becomes wall-clock time and atom count at equal hardware. Beating it means identical atoms at a cost governed by $D(k)$ rather than $D(n)$. No reported runtime for full inversion was found on Lacuna; the only scaling figure in the file is the qualitative "about five variables" limit.

Supervariable coarsening. The strongest existing scalable method is the coarsening of Information-theoretic signatures, which runs two-source PID between each source and the merged remainder. It is the strongest competitor because it already uses the graph-causal reading of unique information and synergy, and it scales linearly. It runs with the same estimator and data. Beating it means recovering multi-source atoms it cannot express, scored against oracle atoms where those exist. The causal-discovery application below gives a second test: classifying co-parents and colliders more accurately on networks with known structure. That paper reports no empirical numbers, so no reported result was found on Lacuna for its procedure.

Net summaries. O-information and the redundancy-synergy index (Rosas et al.) serve as the coarse-summary reference. They are scored on whether they separate constructed cancellation instances from interaction-free instances.

Ablations. Two ablations isolate the key ingredient. The first applies each rule alone, which separates how much reduction comes from irrelevance, factorization, and bounded interaction. The second feeds the algorithm a deliberately misspecified graph, with edges deleted at controlled rates. This shows whether the gains depend on correct structure or only on sparsity.

Why not just…?

Why not just use the supervariable trick and stay with two-source PID? It scales, but it answers a different question. Merging the remainder into one variable hides which particular sources share or combine information, and that is the multi-source detail practitioners want. The proposal tests the loss directly. On synthetic networks with planted three-way synergy and planted redundancy groups, coarsening should misattribute mass that the exact reduced lattice localizes. If coarsening recovers the planted structure equally well, the case for this work weakens to runtime, and the note would say so.

Why not just truncate the lattice to low-order atoms? This is the most serious threat. Dropping all atoms involving more than two or three sources is cheap and is often roughly right on sparse data. The difference is that truncation is unprovable and silently moves the dropped mass into other atoms after inversion. The bounded-interaction rule keeps only the orders the graph permits and certifies that the rest are zero. The experiments include a truncation baseline at matched cost and measure its atom error against the oracle. If truncation error is negligible on every realistic benchmark, the honest conclusion is that the contribution is the certificate rather than the accuracy, and the note would report that.

Why not just report O-information? It is scalable and estimator-friendly (SΩI). However, it is provably blind to cancellation between redundancy and synergy (Rosas et al.). Constructed copy-plus-XOR mixtures in which O-information is near zero while both redundancy and synergy atoms are large settle this question directly.

Proposed Experiments

Canonical systems. The first experiment uses the copy and XOR systems of Rosas et al., together with the logic gates and Rule 90 and Rule 110 cellular automata from the interventional paper, extended to $n=8$–$12$ sources embedded in sparse graphs. Exact ground truth is known analytically for these systems. The checks are exact atom match at $n\le5$ against full inversion, atom count and runtime as $n$ grows, and an explicit attempt to break block factorization with deterministic cross-block copies.

Discrete Bayesian networks. The second experiment uses networks of 16–40 variables from the 99-network suite of Turbocharging Treewidth-Bounded BN Structure Learning. Each node's Markov blanket serves as the source set, with distributions sampled from the true network. Two quantities are reported. The first is the distribution of irreducible block size $k$ against $n$ across the suite, which shows whether the reduction matters on realistic structure. The second is whether reduced-lattice signatures identify co-parents better than supervariable signatures, measured by F1 against the known structure.

Sachs protein-signaling data. The third experiment uses the 11-protein Sachs data with Erk and Akt as targets. The consensus graph and a learned graph each supply $G$, the reduction step uses Gaussian estimation within blocks, and the graph-misspecification ablation is applied. As context for learned-graph quality, the file reports FASK at adjacency precision 0.84 and recall 0.80 (FASK) and REX at F1 0.629 (REX). These are causal-discovery scores, not PID scores; no reported PID-atom result on Sachs was found on Lacuna.

SST-2 sentiment with DistilBERT. The fourth experiment revisits the SST-2 analysis of Decomposing Interventional Causality on phrases of 6–10 tokens, using the dependency parse as $G$. The decisive check is whether parse-guided reduction reproduces the paper's published qualitative calls on short phrases: "not bad" as synergistic, "horribly bad" as redundant, and "really bad" as unique. It must also make lattice analysis possible at lengths where full inversion cannot run.

Decisive checks. Three outcomes would decide the question. The first is exact agreement with full inversion wherever the oracle runs; any mismatch falsifies a rule. The second is a median irreducible block size on the network suite well below $n$; if $k\approx n$ on realistic graphs, the reduction is theoretically correct but practically useless. The third is a positive margin over matched-cost truncation and over supervariable coarsening in atom error on planted-structure benchmarks.