Owing to the prevalence of unlabeled data, semisupervised learning has been one of the most prominent machine learning paradigms, and applied successfully in many real-world applications. However, most of existing semi-supervised learning methods are neither computationally efficient nor economic in memory usage. In this paper, we present the Graph-based Semisupervised Kernel Machine (GKM), a method that leverages the generalization ability of kernel-based method with the geometrical and distributive information carried in a spectral graph induced from data for semi-supervised learning purpose. Our proposed GKM can be solved directly in the primal form using the Stochastic Gradient Descent method with the ideal convergence rate $O(\frac{1}{T})$. Besides, our formulation is suitable for a wide spectrum of important loss functions in the literature of machine learning (e.g., Hinge, smooth Hinge, Logistic, L1, and {\epsilon}-insensitive) and smoothness functions (i.e., $l_p(t) = |t|^p$ with $p\ge1$). We note that the well-known Laplacian Support Vector Machine falls into the spectrum of gS3VM corresponding to the combination of the Hinge loss and the smoothness function $l_2(.)$. We further show that the well-known Laplacian Support Vector Machine is a special case of our formulation. We validate our proposed method on several benchmark datasets to demonstrate that GKM is appropriate for the large-scale datasets since it is optimal in memory usage and yields superior classification accuracy whilst simultaneously achieving a significant computation speed-up in comparison with the state-of-the-art baselines.