Constantin
We study semi-supervised classification in a dynamic data-stream setting, where objects and their relations evolve over time while only a small fraction of observations is labeled. Classical graph-based semi-supervised learning methods, such as label propagation and Laplacian-based regularization, typically reduce learning to the solution of a global graph problem. This requires storing the full graph and recomputing the solution whenever
the graph structure changes, which becomes computationally expensive in streaming environments, especially when noisy, corrupted, or obsolete observations must be removed promptly from the model. Moreover, classical harmonic formulations degenerate in extremely low-label regimes.
We propose Semi-Supervised Local Poisson Label Propagation (SSLPLP), a local Poisson-based framework for evolving graphs. The method formulates prediction updates through a graph Poisson equation with class-dependent sources and sinks induced by labeled vertices, aggregated through class supernodes. Instead of maintaining the full graph, SSLPLP keeps only a compact active neighborhood, where each newly arriving observation is
connected to a limited set of active neighbors within a temporal window or k-NN structure.
The key efficiency mechanism is local graph reduction via the star--mesh transformation. We prove that this reduction is exact: under the zero-sum solvability condition, elimination of zero-forcing unlabeled vertices preserves Poisson potentials on the active region. We further prove linear convergence of the iterative Poisson solver on the reduced graph, derive its spectral rate, and bound the numerical error accumulated over sequential reductions. Computational complexity is $O(\tau^{2}C)$ per streaming step, where $\tau$ is the active window size and C the number of classes, compared with
$\Omega(n\tau^{2}C)$ for batch recomputation.
We validate SSLPLP on two datasets: synthetic Two Moons, ECG arrhythmia classification (INCART-ECG).
On temporally ordered streams, SLPLP achieves $88$--$96\%$ accuracy with as few as 2--5 labeled examples per class, consistently outperforming quantized label propagation and labels-only baselines.
The framework is particularly suitable for sparse-label regimes with local temporal structure and naturally accommodates concept drift through exponentially decaying edge weights.