Hypothesis-free learning is increasingly popular given the large amounts of data becoming available. Structure learning, a hypothesis-free approach, of graphical models is a field of growing interest due to the power of such models and lack of domain knowledge when applied on complex real-world data. State-of-the-art techniques improve on scalability of structure learning, which is often characterized by a large problem space. Nonetheless, these techniques still suffer computational bottlenecks that are yet to be approached. In this work, we focus on two popular models: dynamical linear systems and Markov random fields. For each case, we investigate major computational bottlenecks of baseline learning techniques. Next, we propose two frameworks that provide higher scalability using appropriate problem reformulation and efficient structure based heuristics. We perform experiments on synthetic and real data to validate our theoretical analysis. Current results show that we obtain a quality similar to expensive baseline techniques but with higher scalability. / Master of Science