In the past decade, semi-supervised learning (SSL) over graphs has gained popularity due to its importance in a gamut of network science applications. While most of existing SSL methods provide only point estimates of the targeted variables, the present work capitalizes on Gaussian processes (GPs) to offer a Bayesian SSL approach over graphs with uncertainty quantification, a key attribute especially in safety-critical domains. To accommodate also delay-sensitive scenarios, an incremental learning mode is considered, where prediction of the desired value of a new node per iteration is followed by processing the corresponding nodal observation. Taking the per-node one-hop connectivity vector as the input, the prediction of targeted nodal value is enabled by leveraging an ensemble (E) of GP experts, whose weights are updated in a data-adaptive fashion. In the resultant GRaph-ADpative EGP framework, random feature-based kernel approximation is employed to not only allow learning with scalability, but also preserve privacy by relying on an encrypted version of each node’s connectivity. Besides the one-hop connectivity vector, the novel GradEGP accommodates each node’s egonet features as alternative inputs. On the analytical side, to assess the performance of GradEGP in the adversarial setting where the generative assumptions are violated, regret analysis measures the cumulative online losses relative to their counterparts of a benchmark learner with batch data in hindsight. Tests conducted on real and synthetic datasets demonstrate the effectiveness of the advocated method.