  Partition of unity methods (PUMs) on graphs are simple and highly adaptive
auxiliary tools for graph signal processing. Based on a greedy-type metric
clustering and augmentation scheme, we show how a partition of unity can be
generated in an efficient way on graphs. We investigate how PUMs can be
combined with a local graph basis function (GBF) approximation method in order
to obtain low-cost global interpolation or classification schemes. From a
theoretical point of view, we study necessary prerequisites for the partition
of unity such that global error estimates of the PUM follow from corresponding
local ones. Finally, properties of the PUM as cost-efficiency and approximation
accuracy are investigated numerically.
