Dictionary Learning techniques aim to find sparse signal representations that capture prominent characteristics in the given data. For signals residing on non-Euclidean topologies, represented by weighted graphs, an additional challenge is incorporating the underlying geometric structure of the data domain into the learning process. In this talk, we introduce an approach that aims to infer and preserve the local intrinsic geometry in both dimensions of the data. Combining ideas from spectral graph theory, manifold learning and sparse representations, our proposed algorithm simultaneously takes into account the underlying graph topology as well as the data manifold structure. The efficiencyof this approach is demonstrated on a variety of applications, including sensor network data completion and enhancement, image structure inference, and challenging multi-label classification problems.