Triangles and Connectivity in Edge-Stream Graphs

Graph streams present the streaming model with a structural problem that element streams do not have. An edge is not an independent event: it connects two vertices whose other edges matter, and any question about the graph depends on how edges combine. The counting argument that forces linear space for distinct elements applies even more sharply here, and the best one-pass algorithms therefore settle for space proportional to the number of vertices rather than to the number of edges. That regime has a name — semi-streaming — and the algorithms within it are a distinct design style, built on sampling from adjacency and on per-vertex linear sketches.

The semi-streaming regime and why it is the right target

The input is a sequence of edges $(u, v)$, each arriving once, with $n$ vertices and $m$ edges. A graph on $n$ vertices has up to $\binom{n}{2}$ edges, so $m$ can be quadratic in $n$. Space of $O(n \operatorname{polylog} n)$ is therefore sublinear in the input size whenever the graph is dense, and linear in $n$ when it is sparse.

That is the standard target, and it is not an arbitrary compromise. Deciding whether two vertices are connected in a single pass requires $\Omega(n)$ space: an adversary can present a graph that is a single long path in one case and two paths in another, and any algorithm that has not retained enough per-vertex information cannot tell them apart at the end. The lower bound is tight up to polylogarithms, since a spanning forest fits in $O(n)$ space and answers connectivity exactly.

The semi-streaming model is also where the interesting trade lives. With $n \operatorname{polylog} n$ space, connectivity is exact but a spanning forest requires knowing which edges to keep, and an edge that arrives early may be redundant while a later edge completes a component. With $o(n)$ space, connectivity becomes impossible in one pass, and the algorithms that exist use $\log n$ passes over the stream, each pass refining a partial solution. The pass count is the resource being traded against space, and no algorithm achieves both.

Three graph problems illustrate the design space: counting triangles (a global statistic, approximate), finding a spanning forest (an exact structural object), and estimating the number of connected components (a compromise that is exact in some models and approximate in others).

Counting triangles by sampling wedges

The triangle count $T$ is the number of triples of vertices with all three edges present. It is the standard measure of clustering and the standard test case for graph-stream algorithms, because it is a global count that cannot be derived from degrees alone.

The naive approach enumerates wedges — pairs of edges sharing a vertex — and tests whether the third edge exists. That requires the edge set, which is the whole stream. The sampling approach picks a wedge at random and tests its third edge, then scales up by the number of wedges divided by the number sampled. If a wedge is chosen uniformly from the $\sum_v \binom{d_v}{2}$ wedges in the graph, the probability that it closes into a triangle is $3T / \sum_v \binom{d_v}{2}$, so

$$ \hat{T} = \frac{\text{wedges closing}}{\text{wedges sampled}} \cdot \frac{1}{3} \sum_v \binom{d_v}{2} $$

estimates $T$ with relative error governed by the number of samples: if a fraction $q = 3T / \sum_v \binom{d_v}{2}$ of wedges close, the relative standard error of the estimate is about $\sqrt{(1-q)/(q S)}$ for $S$ samples, so the sample count needed for a $1 \pm \varepsilon$ estimate is $O(1/(\varepsilon^2 q))$. For sparse graphs $q$ is tiny, which makes the sample size large.

Two things are needed to execute this: the ability to pick a wedge uniformly, and the ability to test whether a specific edge is present.

Picking a wedge uniformly requires knowing the degrees, and requires sampling an edge incident to a vertex uniformly from that vertex’s incident edges. Degrees are cheap to maintain exactly in $O(n)$ counters. Uniform sampling of incident edges is the hard part, and it is where the algorithms differ: a per-vertex reservoir of $s$ slots is uniform over the neighbours of $v$ seen so far, whatever their number, because each new neighbour of rank $i$ is kept with probability $s/i$.

The other requirement, testing edge presence, cannot be done in $O(n)$ space. Storing the edge set is the thing the model forbids. The standard solution is to accept a second-order error: keep a hash-based edge filter whose false-positive rate is controlled, or use the fact that a sampled wedge’s third edge can be tested against an edge set retained from an earlier pass. Buriol et al. present an algorithm that runs in two passes over the edge stream, sampling edges and testing their closing edges with exact membership in the second pass, and achieves a $1 \pm \varepsilon$ estimate with $O(n \operatorname{polylog} n)$ space.

The adjacency-sampling problem in one pass

The subtlety in the one-pass algorithm is that the reservoir for a vertex must be updated as edges arrive, but the sampling decision for a new neighbour depends on the vertex’s current degree, which is known at that moment and never has to be predicted. A reservoir of size $s$ for vertex $v$ holds a uniform sample of $v$‘s neighbours seen so far: the $i$-th neighbour is kept with probability $s/i$ and replaces a uniform slot. The structure is therefore the stream-long algorithm described in reservoir sampling, instantiated $n$ times, and the memory cost is $ns$ neighbour identifiers — a constant multiple of the semi-streaming budget, but a constant that grows with the sample size rather than staying in the polylogarithm.

import random

class GraphSample:
    """Per-vertex reservoirs of neighbours, plus exact degrees."""

    def __init__(self, n, slots):
        self.slots = slots
        self.deg = [0] * n
        self.res = [[] for _ in range(n)]

    def add_edge(self, u, v):
        for a, b in ((u, v), (v, u)):
            self.deg[a] += 1
            r = self.res[a]
            if len(r) < self.slots:
                r.append(b)
            else:
                j = random.randrange(self.deg[a])
                if j < self.slots:
                    r[j] = b

    def wedges(self):
        return sum(d * (d - 1) // 2 for d in self.deg)

The per-vertex reservoir is uniform over the neighbours, so a wedge formed by a sampled neighbour of $u$ and a sampled neighbour of $v$ — where $(u,v)$ is itself a sampled edge — is uniform over the set of wedges, provided the three sampling decisions are independent. That independence is the part that is easy to get wrong: if the same random seed or the same hash drives the edge sample and the neighbour samples, the resulting distribution is biased toward wedges whose edges hash to particular values, and the bias does not vanish as the sample grows.

The one-pass estimator’s variance comes from two sources at once: the random choice of which edges and neighbours are retained, and the fact that a retained wedge’s closure can only be tested against the sample rather than the whole graph. For a graph in which a constant fraction of wedges close, the error falls as the square root of the retained work increases; for a graph in which almost no wedge closes, the estimator is counting rare events and needs a correspondingly larger budget. That is a property of the estimator rather than of its implementation, and no amount of cleverness removes it.

Why collision counting does not give triangles directly

A tempting route to $T$ runs through the second frequency moment: map every wedge to a key derived from its endpoints, count how often each key appears, and hope that the triangle count falls out of $\sum_k f_k^2$ or similar. It does not. A triangle’s three edges generate wedges whose keys depend on how the mapping is defined, and the contribution of a closed wedge to any moment of the wedge-key distribution depends on the degrees of its endpoints and on which other wedges the graph happens to close. The second moment measures collisions of keys, not closure of wedges, and two graphs with the same wedge-key multiset can have different triangle counts.

The reason is the same one that separates Tug-of-War sketches from structural summaries: a moment of a key distribution counts mass, and a triangle is a relation among three vertices rather than an amount of mass. Estimates of $T$ from frequency moments therefore need a normalisation that depends on the graph, which defeats the purpose of computing the moment in the first place.

What a moment sketch can do for a graph stream is answer questions that are already additive over the edges. The number of wedges is one: an edge arriving at a vertex of current degree $d$ creates $d$ new wedges, so exact degrees are enough to maintain $\sum_v \binom{d_v}{2}$, and a moment sketch over edge keys can estimate quantities of the same additive shape without storing either the degrees or the edge set.

Spanning forests from per-vertex sketches

Connectivity needs no sampling. It needs, for each vertex, enough information to find one incident edge that crosses a cut. The Ahn–Guha–McGregor construction gives exactly that.

Give each vertex a linear sketch of its incident edges: for vertex $v$, the sketch $s_v$ is the sum over incident edges $e$ of a random vector $\phi(e)$, where $\phi$ is an $\ell_0$ sampler — a sketch that can recover a uniformly random non-zero coordinate of the vector it summarises. The union of the sketches over a set of vertices $S$ is a sketch of the cut between $S$ and its complement, because an edge with both endpoints in $S$ contributes $\phi(e)$ twice and cancels, while an edge crossing the cut contributes once. Running the sampler on the union therefore returns a random edge crossing the cut, if any exists.

Borůvka’s algorithm then proceeds without ever storing the edge set: start with each vertex as a component, sketch each component by summing its vertices’ sketches, sample a crossing edge from each, add it to the forest, and merge. Each round halves the number of components, so $\log n$ rounds suffice, and each round needs only the sketches, which are $O(n \operatorname{polylog} n)$ total.

The trick that makes the sketches additive is the same linearity that makes Count-Min mergeable: an edge is represented by a random vector indexed by its endpoints, and the sum over a vertex set is a linear functional of the edge set. The $\ell_0$ sampler is the decoder, and its space cost is polylogarithmic per sketch, which is where the extra log factors in the semi-streaming bound come from.

def cut_sketch(sketches, component):
    """XOR the per-vertex sketches of a component.

    An edge with both endpoints inside the component is XORed twice and
    cancels; a non-zero result proves the cut is non-empty.
    """
    acc = 0
    for v in component:
        acc ^= sketches[v]
    return acc

A sampler built from XOR labels is the one that makes the linearity visible: assign each edge a random label, XOR the label into both endpoints’ sketches, and an edge with both endpoints inside the component cancels exactly. A non-zero accumulator is a certificate that the cut is non-empty, but membership testing of that kind answers only whether a candidate edge is present, so it cannot by itself produce a uniform sample of the cut. Sampling uniformly needs the stronger $\ell_0$ structure described above, which keeps enough information per coordinate to pick one at random. Exact cancellation is why the technique is restricted to graphs: it detects presence and counts nothing, so it cannot say how many edges cross a cut.

What the semi-streaming model hides

Four assumptions are worth stating because each is violated by real graph data.

Edges arrive once. Insert-only edge streams are the standard model. Deletions turn the problem into a dynamic graph stream, where the XOR sketch still works — a deleted edge XORs its label out — but the triangle-counting estimators do not, because a sampled wedge can lose its closing edge between sampling and query. Dynamic triangle counting needs sketches over edge sets, which is a much more expensive construction.

The vertex set is known. Space $O(n)$ presumes $n$ is known and the vertices are numbered densely. A stream over arbitrary string identifiers needs a dictionary from identifier to index, which costs space proportional to the number of distinct vertices and is the actual memory bottleneck in practice. The asymptotic bound does not mention it because the model assumes it away.

The graph is undirected. Directed triangle counting is a different problem with a different sampling distribution, and the estimators do not transfer. A directed wedge has orientations, and the closure condition involves edge directions, so the probability that a sampled wedge closes depends on the orientation pattern, which is exactly the quantity being estimated. Directed versions need either more careful sampling or a reduction to the undirected case on the underlying graph.

The output is a number, not a structure. A triangle estimate is a scalar; a spanning forest is a set of $n-1$ edges. The second is a structural output, and the semi-streaming bound accommodates it. Most graph queries of practical interest — shortest paths, matchings, subgraph isomorphism — are structural, and for several of them the semi-streaming space is not enough for a one-pass exact answer. Approximate distances need spanners, which cost $O(n^{1+1/k})$ space for a stretch of $2k-1$; exact shortest paths need $\Omega(n^2)$ in the worst case, which is the whole graph.

The pattern that recurs here is that each summary preserves exactly the structure its query needs — registers for presence, counters for identity, tuples for rank, sketches for cuts — and the cost is set by how much of the input’s structure that query requires. Graph queries require the most, because the input is relational rather than a bag of independent items, and the space bound moves from polylogarithmic to linear in $n$ accordingly.