Online Learning with Certified Unlearning over Graphs

Machine learning models on graph-structured data are increasingly deployed in dynamic environments, where data arrive continuously and models must be updated online, while specific data points and their influence are requested to be removed to meet privacy or regulatory requirements. Most existing work on machine unlearning focuses on offline or post-training settings and does not readily extend to online graph learning: updates with arriving data and deletion requests are interleaved, and removing nodes or edges can propagate changes through the graph structure. We study online learning with certified unlearning over graph-structured data, where a model is updated sequentially while accommodating deletion requests at any time. The subsequent outputs need to be indistinguishable from those of a model trained without the removed data. We propose OLUG, a principled framework that performs localized second-order retroactive correction during online graph learning using only recent batch information. We show that OLUG preserves no-regret online learning while supporting certified removal, incurring only an additive regret cost under infrequent deletions. Our analysis further reveals how graph propagation amplifies deletion sensitivity differently across node, edge, and feature removal scenarios. Experiments on multiple benchmark graph datasets demonstrate utility comparable to training from scratch, with substantially reduced computational overhead by avoiding retraining.