  We describe the first algorithms that satisfy the standard notion of
node-differential privacy in the continual release setting (i.e., without an
assumed promise on input streams). Previous work addresses node-private
continual release by assuming an unenforced promise on the maximum degree in a
graph; indeed, the algorithms from these works exhibit blatant privacy
violations when the degree bound is not met. Our algorithms are accurate on
sparse graphs, for several fundamental graph problems: counting edges,
triangles, other subgraphs, and connected components; and releasing degree
histograms. Our unconditionally private algorithms generally have optimal
error, up to polylogarithmic factors and lower-order terms.
  We provide general transformations that take a base algorithm for the
continual release setting, which need only be private for streams satisfying a
promised degree bound, and produce an algorithm that is unconditionally private
yet mimics the base algorithm when the stream meets the degree bound (and adds
only linear overhead to the time and space complexity of the base algorithm).
To do so, we design new projection algorithms for graph streams, based on the
batch-model techniques of Day et al. 2016 and Blocki et al. 2013, which modify
the stream to limit its degree. Our main technical innovation is to show that
the projections are stable -- meaning that similar input graphs have similar
projections -- when the input stream satisfies a privately testable safety
condition. Our transformation then follows a novel online variant of the
Propose-Test-Release framework (Dwork and Lei, 2009), privately testing the
safety condition before releasing output at each step.
