Wavelet transforms (WTs) constitute a class of powerful tools for spectral and local analysis of data, such as time series, geophysical data, and well logs, as well as modeling of various problems in oil reservoirs, and in particular upscaling their geological models. The application to upscaling has, however, been limited to the reservoir models that are represented by regular computational grids with blocks or cells with regular shapes, such as squares and cubes. The most natural structure of the computational grid is, however, one with irregular and unequal cells, distributed spatially with stochastic orientations. Such a grid is also the ideal computational model for, for example, fractured reservoirs as it allows inclusion of fractures with spatially distributed orientations. In this paper, we propose a generalization of the WT approach to upscaling by developing a new model of a reservoir based on irregular graphs that make it possible to use the WTs for upscaling the geological model highly efficiently. To do so, we first define a computational grid representing a reservoir as a graph and its adjacency matrix and, then, introduce graph WTs using the concept of lifting, utilized in classical signal processing and its extension to graphs. The application of the lifting-based graph WT to upscaling is then developed. The result is an algorithm that may be applied to upscaling of any unstructured geological model represented by a computational grid in which the multiresolution graph WT is applied directly to the spatial distribution of the permeabilities (or other suitable properties). Examples in which the geological model is represented by the Voronoi tessellations are described, and simulation of waterflooding with such graph networks is carried out in order to demonstrate the accuracy and efficiency of the new method.