  Motivated by the need to extract meaning from large amounts of complex
structured data, we consider three critical problems on graphs: localization,
decomposition, and dictionary learning of piecewise-constant signals. These
graph-based problems are related to many real-world applications, such as
localizing stimulus in brain connectivity networks, and mining traffic events
in city street networks, where the key issue is to find the supports of
localized activated patterns. Counterparts of these problems in classical
signal/image processing, such as impulse detection and foreground detection,
have been studied over the past few decades. We use piecewise-constant graph
signals to model localized patterns, where each piece indicates a localized
pattern that exhibits homogeneous internal behavior and the number of pieces
indicates the number of localized patterns. For such signals, we show that
decomposition and dictionary learning are natural extensions of localization,
the goal of which is not only to efficiently approximate graph signals, but
also to accurately find supports of localized patterns. For each of the three
problems, i.e., localization, decomposition, and dictionary learning, we
propose a specific graph signal model, an optimization problem, and a
computationally efficient solver. The proposed solvers directly find the
supports of arbitrary localized activated patterns without tuning any
thresholds. We then conduct an extensive empirical study to validate the
proposed methods on both simulated and real data including the analysis of a
large volume of spatio-temporal Manhattan urban data. The analysis validates
the effectiveness of the approach and suggests that graph signal processing
tools may aid in urban planning and traffic forecasting.
