Non-intrusive load monitoring is a technique for monitoring the operating conditions of electrical appliances by collecting the aggregated electrical information at the household power inlet. Despite several studies on the mining of unique load characteristics, few studies have extensively considered the high computational burden and sample training. Based on low-frequency sampling data, a non-intrusive load monitoring algorithm utilizing the graph total variation (GTV) is proposed in this study. The algorithm can effectively depict the load state without the need for prior training. First, the combined K-means clustering algorithm and graph signals are used to build concise and accurate graph structures as load models. The GTV representing the internal structure of the graph signal is introduced as the optimization model and solved using the augmented Lagrangian iterative algorithm. The introduction of the difference operator decreases the computing cost and addresses the inaccurate reconstruction of the graph signal. With low-frequency sampling data, the algorithm only requires a little prior data and no training, thereby reducing the computing cost. Experiments conducted using the reference energy disaggregation dataset and almanac of minutely power dataset demonstrated the stable superiority of the algorithm and its low computational burden.