The Open Problems

Chapter 4 · Navlakha et al. 2008 · Seely 2025

Problem 1: Rate-distortion bounds for journey observables

The question: Given a bit budget R, what is the minimum distortion in journey metrics (reachability, duration, hop count) for a temporal graph?

What exists: Navlakha et al. (2008) proposed MDL-based graph summarization with bounded per-node reconstruction error for static graphs. This is MDL, not Shannon rate-distortion theory — no R-D tradeoff curve, no converse bounds. Adhikari et al. (2017) and Allen et al. (2024) compress temporal networks preserving dynamics heuristically. None provides information-theoretic bounds where distortion is measured on temporal journeys.

What it requires:

• A concrete encoding family — how temporal graphs are represented in bits
• A concrete distortion functional D(G, Ĝ) on journey observables
• A concrete temporal-graph model (e.g., temporal Erdős–Rényi)
• A definition of admissible decoders

Problem 2: Checkpoint spacing via sheaf cohomology

The question: On a directed dependency graph with per-edge prediction error, when are checkpoints necessary, and how should they be spaced?

The sheaf formulation: Seely (2025) shows that on a cellular sheaf, the coboundary δ⁰ produces edgewise prediction errors and the Hodge decomposition splits them into two components:

• Image part (in im D) — eliminable by better activations / encoder choices
• Harmonic part (in ker Dᵀ = H¹) — not eliminable by any activation assignment

The scalar additive error law ε(e₁) ⊕ ... ⊕ ε(eₖ) may be the wrong abstraction. The right quantity could be the harmonic component of accumulated error — the part that no encoder choice can remove. Checkpoints would then correspond to clamped boundary conditions on a subgraph that suppress or localize the harmonic component.

Seely's framework gives exact definitions for every term. The open question is whether checkpoint placement can be formulated as a constraint on a relative coboundary problem, and whether spacing bounds follow from the cohomological structure.

The linear restriction aligns with codec prediction (motion-compensated subtraction is linear). Nonlinear extension requires Jacobian linearization.

Toy model: empirical compression curve

Compress a temporal graph by dropping edges, measure journey distortion. This is greedy edge-dropping, not a Shannon R-D bound — but the shape of the curve is informative:

import random

class TemporalGraph:
    def __init__(self):
        self.edges = []

    def add_edge(self, u, v, t):
        self.edges.append((u, v, t))

    def reachable_pairs(self):
        nodes = set()
        for u, v, t in self.edges:
            nodes.add(u)
            nodes.add(v)
        count = 0
        for s in nodes:
            arrival = {s: -1}
            for u, v, t in sorted(self.edges, key=lambda e: e[2]):
                if u in arrival and t >= arrival[u]:
                    if v not in arrival or t + 1 < arrival[v]:
                        arrival[v] = t + 1
            count += len(arrival) - 1
        return count

# 6 nodes, 15 edges across 5 timesteps
random.seed(42)
g = TemporalGraph()
nodes = list("ABCDEF")
for t in range(1, 6):
    for _ in range(3):
        u, v = random.sample(nodes, 2)
        g.add_edge(u, v, t)

total = len(g.edges)
baseline = g.reachable_pairs()

print(f"Full graph: {total} edges, {baseline} reachable pairs")
print(f"\n{'Kept':>6} {'Rate':>6} {'Reach':>6} {'%':>6}")
print("-" * 28)

for frac in [1.0, 0.87, 0.73, 0.60, 0.47, 0.33, 0.20]:
    n = max(1, int(total * frac))
    current = list(g.edges)
    while len(current) > n:
        best_i, best_r = 0, -1
        for i, edge in enumerate(current):
            trial = current[:i] + current[i+1:]
            tg = TemporalGraph()
            for e in trial:
                tg.add_edge(*e)
            r = tg.reachable_pairs()
            if r > best_r:
                best_r = r
                best_i = i
        current.pop(best_i)
    cg = TemporalGraph()
    for e in current:
        cg.add_edge(*e)
    r = cg.reachable_pairs()
    print(f"{len(current):>6} {len(current)/total:>6.2f} {r:>6} {r/baseline*100:>5.1f}%")

print("\n→ As rate drops, reachability degrades — the R-D curve.")

What the toy model shows

Diminishing returns as you add edges, and a critical threshold below which reachability collapses. The open problem asks for the information-theoretic minimum: for a class of temporal graphs, how close can any compression get to the frontier?

Source material: Temporal Compression (blog post)