A Graph Whose Edges Never Stop Arriving
Imagine watching a city’s road network while roads continually open and close. You want to know whether every district remains reachable, which bridges are critical, how many triangles of mutual connections exist, or whether a much smaller weighted network would answer the same cut and flow questions. Storing every edge may be impossible when the graph has billions of interactions.
Graph streaming treats each edge event as an update to an implicit graph. In an insertion-only stream, edges arrive and remain. In a dynamic stream, an edge may later be deleted, so the algorithm must respect cancellations. Different questions demand different summaries: degrees are local counts, connectivity needs a spanning forest or cut witnesses, triangle counts need information about neighboring edge pairs, and spectral queries need a sparsifier that preserves quadratic forms.
For a tiny example, process $(A,B)$, $(B,C)$, $(A,C)$, $(C,D)$. After the first two edges, $A,B,C$ form one connected component. The third edge creates a triangle but does not change connectivity. The fourth connects $D$. A connectivity summary may discard $(A,C)$; a triangle estimator cannot. There is no universally sufficient “graph sketch” independent of the query.
Linear-sketch ideas enter because an edge incidence vector supports signed updates and mergeability. An $\ell_0$-sampler can recover a surviving edge crossing a component cut. Repeated across levels and vertices, such primitives can support dynamic spanning-forest recovery. Sampling edges according to effective-resistance-like importance can produce spectral sparsifiers, but only with the correct probabilities, weights, and proof assumptions.
A graph stream is not merely a list of edges: its model specifies insertions, deletions, multiplicity, order, weights, and when queries occur. The right summary is query-specific—connectivity can ignore cycles that triangle counting or spectral approximation must preserve.
| Concept | Intuitive meaning | Exact example | Non-example or boundary | Main assumption | Question answered |
|---|---|---|---|---|---|
| Insertion-only stream | Edges arrive but do not leave | $+(u,v)$ once or with positive multiplicity | A later deletion | Final graph is monotone in edges | What can be summarized as connectivity only grows? |
| Dynamic edge stream | Signed updates define final edge multiplicities | $+(u,v)$ then $-(u,v)$ cancels | Treating both events as two surviving edges | Strict or general turnstile semantics are declared | What survives after additions and removals? |
| Spanning forest | Acyclic edges connecting each component | Three edges connect four vertices in a tree | All graph edges | Undirected connectivity | Which vertices are reachable from one another? |
| Cut | Edges with one endpoint in $S$ and one outside | For $S=\{A,B\}$, count crossing edges | Edges internal to $S$ | Vertex set and edge direction/weight convention | How strongly are two sides connected? |
| Matching | Vertex-disjoint selected edges | $(A,B)$ and $(C,D)$ | Two chosen edges sharing $B$ | Simple or multigraph model is fixed | How many disjoint relationships can be selected? |
| Spectral sparsifier | Smaller weighted graph preserving Laplacian quadratic forms | $(1\pm\varepsilon)x^\mathsf TL_Gx$ for all $x$ | Merely preserving degrees | Nonnegative weighted undirected graph in the standard setting | Can all cuts and energy queries be approximated? |
A Graph Whose Edges Never Stop Arriving
Process the undirected insertion stream $(A,B),(B,C),(A,C),(C,D)$.
- After $(A,B)$ and $(B,C)$, record the spanning-forest edges $\{(A,B),(B,C)\}$ and components $\{A,B,C\},\{D\}$.
- Edge $(A,C)$ closes a triangle. A connectivity-only summary may reject it as redundant, but a triangle counter must account for it.
- Edge $(C,D)$ joins the components; add it to the forest. The final graph is connected, the forest has three edges, and the graph has one triangle.
- Now delete $(B,C)$. The stored forest edge disappears, yet connectivity remains through $B-A-C$. A dynamic algorithm needs a replacement edge; insertion-only union–find alone cannot undo and repair this state.
Reflection: which discarded edge was useless for insertion-only connectivity but essential after a later deletion? Explain why the stream model changes what can safely be forgotten.
Insertion, Deletion and Dynamic Graph Models
Let the vertex universe be $V=[n]$. For an undirected simple graph, assign each possible edge $e=\{u,v\}$ a coordinate in a vector $x$. An update $(e,\Delta)$ changes $x_e\leftarrow x_e+\Delta$. Under strict turnstile semantics, coordinates remain nonnegative; in a simple-graph stream they are usually constrained to $0$ or $1$. Under general turnstile semantics, intermediate or final values may be signed, which changes the graph interpretation.
An insertion-only algorithm can maintain a spanning forest with disjoint-set union using $O(n)$ words: add an edge exactly when it joins two components. It answers final connectivity but does not support deletion because union–find cannot split a component or remember every alternative cycle edge.
Dynamic connectivity sketches use linearity. Give each vertex a signed incidence vector over edges: an edge contributes with opposite signs at its endpoints. Summing the vectors over vertices in a component cancels internal edges and leaves precisely the boundary or cut vector. A linear $\ell_0$-sampler applied to that sum can recover a surviving outgoing edge. Multiple independent levels and repetitions support recovery across different cut sizes and reduce failure; the exact theorem determines space and adaptivity assumptions.
Degrees satisfy $d_v=\sum_{e\ni v}x_e$ in a nonnegative undirected model. A cut has size $|\delta(S)|$. Triangle count is $\operatorname{tr}(A_G^3)/6$ for a simple undirected adjacency matrix, but estimating it from a stream is harder because it depends on correlated triples. Matchings depend on global conflicts between edges. Spectral structure is expressed through the Laplacian
$$ L_G=\sum_{e=\{u,v\}}w_e b_e b_e^\mathsf T, $$
where $b_e$ is a signed incidence vector. Then $x^\mathsf TL_Gx=\sum_e w_e(x_u-x_v)^2$. This linear sum of edge matrices makes sparsification possible, but sampling must control all directions simultaneously.
flowchart TD
A[Edge update e and Delta] --> B{Stream model}
B -->|Insertion only| C[Monotone edge set]
B -->|Dynamic| D[Turnstile edge vector]
C --> E[Union-find spanning forest]
D --> F[Linear incidence sketches]
F --> G[Sum sketches over a component]
G --> H[Internal edges cancel]
H --> I[l0-sample an outgoing cut edge]
I --> J[Repair or build spanning forest]
D --> K[Linear Laplacian contributions]
K --> L[Importance sampling or sketch recovery]
L --> M[Spectral sparsifier]
C --> N[Edge or wedge samples]
N --> O[Triangle or matching estimates]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B navy;
class C,D,F,K,N purple;
class E,G,H,I,L teal;
class J,M,O crimson;
| Definition or claim | Exact scope | Required assumptions | What it does not imply | Counterexample or consequence |
|---|---|---|---|---|
| Insertion-only connectivity | A spanning forest can be maintained by accepting component-joining edges | Undirected edge insertions, fixed vertex universe | Deletion support | Removing a tree edge may require a discarded cycle edge |
| Dynamic linear sketch | Sketch of final edge vector is sum of signed update sketches | Compatible matrix/seed and arithmetic; declared turnstile model | Final coordinates are valid simple-graph indicators | Duplicate deletion can make a negative edge coordinate |
| Component-cut cancellation | Sum of signed vertex incidences cancels edges internal to $S$ | Consistent orientation and linear addition | An outgoing edge is found deterministically from one small sketch | Sampler may fail or collide with bounded probability |
| Triangle identity | Simple undirected triangles equal $\operatorname{tr}(A_G^3)/6$ | No loops, symmetric adjacency, appropriate multiplicity | Easy estimation in every streaming regime | Wedge sampling variance can explode when triangles are rare |
| Spectral sparsifier | $(1-\varepsilon)x^\mathsf TL_Gx\le x^\mathsf TL_Hx\le(1+\varepsilon)x^\mathsf TL_Gx$ for every $x$ | Standard result uses nonnegative weighted undirected graphs | Exact adjacency or triangle preservation | Two spectrally close graphs can have different motif counts |
| Mergeable graph sketch | Sketches add for edge-disjoint or signed partial streams | Same vertex IDs, orientation, seed, epoch, and weights | Decoded forests themselves can simply be unioned after arbitrary deletions | Local summaries may omit globally needed replacement edges |
For a signed incidence representation, summing vertex sketches over a set $S$ cancels every internal edge twice with opposite signs and retains each cut edge once. This invariant turns dynamic connectivity into repeated recovery of nonzero cut coordinates, provided the stream and sampler satisfy their stated turnstile and randomness assumptions.
Connectivity, Cuts and Spectral Summaries
Insertion-only connectivity has a simple proof: every rejected edge joins vertices already connected by the maintained forest, so rejecting it preserves the component partition; every accepted edge reduces the number of components without creating a cycle. At the end, the forest connects exactly the graph’s components.
Deletion breaks monotonicity. If a tree edge disappears, the algorithm must determine whether another surviving edge crosses the resulting cut. Linear incidence sketches make the cut vector recoverable without storing all cycle edges. Multi-level subsampling helps when a cut is too dense for a one-sparse test: at some level, each edge is retained with a smaller probability, giving a useful chance that exactly one cut edge survives. Independent repetitions amplify success.
Cut sparsification samples edges with probabilities related to their importance and reweights selected edges by inverse probability. Spectral sparsification targets the stronger quadratic-form condition. In electrical terms, effective resistance $R_e=b_e^\mathsf TL_G^+b_e$ measures how structurally irreplaceable edge $e$ is; $w_eR_e$ acts like a leverage score. Sampling roughly in proportion to these scores and applying matrix concentration can preserve all Laplacian energies simultaneously.
The “all $x$” quantifier implies cut preservation because the indicator vector of $S$ satisfies $1_S^\mathsf TL_G1_S=w(\delta(S))$. The converse is subtler in approximation constants and proof machinery; preserving a few observed cuts is not a spectral guarantee. Spectral closeness also does not preserve adjacency, triangles, or maximum matching exactly.
flowchart TD
A[Maintain forest plus linear edge sketches] --> B[Tree edge is deleted]
B --> C[Split former tree into components S and V minus S]
C --> D[Aggregate signed vertex sketches over S]
D --> E[Internal edges cancel; cut edges remain]
E --> F{Can sampler recover a surviving cut edge?}
F -->|Yes| G[Add replacement edge to forest]
F -->|No edge exists| H[Components remain separated]
F -->|Random failure| I[Use levels and independent repetitions]
I --> F
A --> J[For spectral queries, form weighted edge samples]
J --> K[Importance from resistance or leverage estimates]
K --> L[Reweight sampled edges]
L --> M[Matrix concentration preserves all quadratic forms]
D -. inconsistent orientation .-> X[Cancellation proof fails]
K -. uniform sample misses bridge-like edge .-> Y[Spectral failure]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,C,J navy;
class D,E,F,K,L purple;
class G,H,I,M teal;
class X,Y crimson;
Connectivity, Cuts and Spectral Summaries
Let the current graph have vertices $A,B,C,D$ and edges $(A,B),(B,C),(A,C),(C,D)$. Use $S=\{A,B,C\}$.
- The internal edges are $(A,B),(B,C),(A,C)$; the only cut edge is $(C,D)$.
- Give every undirected edge a fixed orientation. In the signed incidence vector of each vertex, an edge has $+1$ at its tail and $-1$ at its head.
- Sum the vectors for $A,B,C$. Every internal edge appears once with $+1$ and once with $-1$, so it cancels. Edge $(C,D)$ appears only at $C$ and survives.
- An ideal $\ell_0$-sampler on the aggregate cut vector therefore returns $(C,D)$ with probability one conditional on sampler success.
- If $(C,D)$ is deleted, the aggregate becomes zero and no replacement exists; $D$ is disconnected.
Assumption-breaking variation: orient $(A,B)$ differently in the sketches for $A$ and $B$. Their contributions add instead of canceling, so an internal edge masquerades as a cut edge. State the metadata invariant required across every shard and vertex.
| Analytical tool | What it establishes | Assumptions | Tightness or limitation | Representative failure case |
|---|---|---|---|---|
| Forest invariant | Exact insertion-only component partition | Undirected insertions and correct union operations | Retains no general deletion witnesses | Deleted tree edge reveals a forgotten alternative path |
| Signed-incidence cancellation | Aggregate component sketch represents its cut | Fixed orientation, linearity, compatible seeds | Recovery remains randomized | Inconsistent endpoint signs leave internal-edge noise |
| Multi-level subsampling | Some level isolates a cut edge with useful probability | Independent hash levels and nonempty cut | Needs repetitions and union-bound budgeting | Adaptive stream targets exposed levels |
| Cut sparsification | Approximate weights of all cuts | Correct importance sampling and reweighting | Does not preserve motifs | Triangle count changes despite accurate cuts |
| Effective-resistance sampling | Controls Laplacian quadratic forms | Nonnegative weights and sufficiently accurate upper estimates | Computing estimates has cost | Uniform sampling drops a high-resistance bridge |
| Matrix concentration | Simultaneous spectral approximation | Bounded independent or controlled edge contributions | Constants and failure budget matter | Underestimated sampling probabilities create large summands |
| Wedge/edge sampling | Unbiased or controlled motif estimators | Declared order model and inclusion probabilities | High variance in sparse-triangle regimes | One dense hub produces many wedges but few triangles |
Networks, Social Graphs and Security Events
For a classroom friendship graph, an insertion-only forest can answer whether every student lies in one connected component while storing at most $n-1$ forest edges. It cannot answer how many friendship triangles exist because cycle edges were intentionally discarded.
For network telemetry, vertices may be devices and edges observed communications. Dynamic updates represent session openings and closures or window expiration. Connectivity can reveal segmentation failures, degree summaries can flag scans, and spectral summaries can support cut or diffusion analysis. But duplicate events, NAT, identity rotation, and missing collectors alter the graph before any approximation occurs.
For social or marketplace graphs, matchings can model disjoint recommendations, triangles can indicate clustering, and sparsifiers can accelerate downstream graph algorithms. Directed, temporal, signed, and weighted relationships require their own semantics; converting them blindly to one undirected edge discards meaning.
Adversaries may generate dense bursts, target public hash collisions, or alternate insertions and deletions to stress state. A sketch proved for an oblivious stream may fail under adaptive querying. Seed secrecy or rotation, rate controls, multiple validation sketches, overflow-safe counters, and sampled exact replay belong in the system design.
Networks, Social Graphs and Security Events: Graph Streaming
A club records friendships $(A,B),(B,C),(A,C),(C,D),(D,E)$. It asks two questions: “Is everyone connected?” and “How many triangles exist?”
- An insertion-only forest keeps $(A,B),(B,C),(C,D),(D,E)$ and proves one connected component.
- The rejected edge $(A,C)$ completes exactly one triangle $A-B-C$.
- If only the forest is retained, the triangle count becomes zero even though connectivity remains exact.
- Choose a separate triangle estimator or retain the full graph for this tiny case; a forest is the correct summary only for reachability.
- Delete $(B,C)$. The graph remains connected because $B-A-C$, but the original forest needs $(A,C)$ as a replacement.
Success criteria: produce the forest, component count, exact triangle, deletion repair edge, and a one-sentence statement of why one summary cannot answer both questions.
Networks, Social Graphs and Security Events: Graph Streaming
A security platform receives $5$ million communication-edge updates per second over $n=100$ million device identities. Updates include session starts, ends, retries, and delayed corrections. It needs hourly connectivity alarms, degree outliers, approximate cut queries, and sampled suspicious motifs within 60 seconds, using less than 5% of raw-edge storage.
Design: define a strict-turnstile edge lifecycle with canonical undirected or directed semantics per query; deduplicate retries; version vertex IDs, edge orientation, weights, seeds, and hourly epochs. Maintain separate query-specific structures: dynamic connectivity sketches with replacement recovery, degree counters/sketches, a weighted sparsifier for cut/spectral questions, and motif samples for triangles. Do not infer motifs from the sparsifier.
Evidence: exact replay on sampled partitions; insertion/deletion imbalance; recovery failure rates; component and cut accuracy; motif variance; degree error; memory and update latency; seed-to-seed variance; hot vertices; identity churn; counter overflow; adaptive collision tests; and late-event behavior across epoch boundaries.
Risks: missing deletions create phantom edges, duplicate ends create negative multiplicities, public hashes invite targeted collisions, and merging incompatible epochs corrupts cancellation. Use metadata rejection, bounded-lateness correction, independent verification sketches, seed management, overflow-safe arithmetic, and an explicit unknown/degraded state.
Decision: use approximate summaries for monitoring only when confidence bounds meet per-query targets and exact audits detect lifecycle errors. Require authoritative edge evidence before automated isolation of devices; a probabilistic graph alarm should generate investigation, not silently redefine the network.
Match a Graph Question to a Stream Model
The design sequence is: define vertices and edges; specify direction, weight, multiplicity, lifetime, and turnstile rules; state the query and error; then choose a summary whose invariant directly supports that query. Memory bounds without model semantics are not meaningful.
Practice: Match a Graph Question to a Stream Model
Process updates $+(A,B), +(B,C), +(A,C), +(C,D), -(B,C), +(D,E)$ in a simple undirected dynamic graph.
Tier 1 — Definitions. Define insertion-only and dynamic streams, spanning forest, cut, matching, triangle, $\ell_0$ sampler, and spectral sparsifier. Include direction, multiplicity, or weight assumptions where relevant.
Tier 2 — Exact trace. List the final edges, components, degrees, one spanning forest, triangle count, and a maximum matching. Expected: final edges $(A,B),(A,C),(C,D),(D,E)$ form one connected tree; degrees are $d(A)=2$, $d(B)=1$, $d(C)=2$, $d(D)=2$, and $d(E)=1$; triangle count is zero; and a matching of size two exists.
Tier 3 — Cut algebra. Orient every edge lexicographically. For $S=\{A,B\}$, sum signed incidence vectors and show internal edge $(A,B)$ cancels while $(A,C)$ remains. Explain what changes before deletion when $(B,C)$ also crosses the cut.
Tier 4 — Counterexamples. Give: a cycle edge useless to insertion-only connectivity but essential after deletion; two graphs with the same degree sequence but different triangle counts; a uniform edge sample that drops a bridge; and an invalid stream whose deletion makes an edge multiplicity negative.
Tier 5 — Model matching. Select summaries for insertion-only connectivity, fully dynamic connectivity, degree moments, triangle estimation, approximate matching, cut queries, and spectral energy. State which outputs are exact, approximate, or probabilistic.
Tier 6 — Professional artifact. Write a graph-stream contract naming vertex/edge identity, direction, weights, multiplicity, update lifecycle, ordering, window/epoch, strict or general turnstile model, queries, $(\varepsilon,\delta)$ per query, seed/orientation metadata, merge rules, adversary model, overflow behavior, verification sample, and degraded-state policy.
Debugging prompts: if internal edges appear in cut sketches, check orientation; if connectivity fails only after deletions, inspect replacement recovery; if merged counts go negative, inspect duplicates and epochs; if triangle estimates have huge variance, inspect wedges and clustering; if a sparsifier passes cuts but motifs fail, remember that motif preservation was never guaranteed.
Stretch goal: compare a cut sparsifier and spectral sparsifier. Explain why the spectral condition applies to every real vector, how cut indicators fit inside it, and why neither guarantees exact triangle count.
Rubric (10 points): definitions and models 2; exact trace 2; cut-cancellation derivation 2; valid counterexamples 2; reviewable production contract 2. Full credit requires using different summaries for connectivity, motifs, and spectral queries.
Decision checklist: define the graph and edge lifecycle; choose insertion-only or turnstile semantics; match each query to its invariant; budget sampling and sketch failure across all queries; version orientation, seeds, IDs, and epochs; and validate against exact edge samples. A spanning forest is not a motif summary, cut preservation is not adjacency preservation, and linear mergeability does not repair inconsistent graph semantics. These foundations lead naturally to dynamic-connectivity sketches, graph sparsification, distributed graph summaries, and lower bounds for streaming graph problems.
Next in the Series
In Geometric Streams & Coresets, we'll explore Compress geometric data while preserving objective costs..