Complex network theory has been well established as one of the main tools for understanding and analyzing the behavior of the natural systems that surround us. Social networks, genetic and protein interaction networks, airline and road traffic networks, brain connectivity networks and web graphs are only some of the examples. As network theory evolves it becomes more apparent that these complex systems are often composed of multiple types of interactions, each carrying a different piece of information, and therefore are commonly represented in the form of multiplex networks, where each layer represents a different type of interaction among nodes. In addition to the interactions among the nodes of the networks, these systems also present correlations among the various types of interactions, as represented by the intrinsic structure and the associations of the various layers of the graph. For example, in social sciences, a network with a large overlap between two layers that represent two distinct types of people interactions i.e. friendship and professional ties might indicate that there is an interconnection between the two in the given network. In another example, in transportation networks, where nodes represent airports connected by flights operated by specific airlines (each airline representing a layer of the graph), the structure of the layers can provide information about the airline: traditional airlines such as Lufthansa tend to have a large overlap in activity pattern with other airlines, whereas low-cost airlines such as easyJet tend to avoid such overlaps. Due to their ability to represent such complex entity interactions, multiplex networks have lately been the focus of a large part of the research community, studying a variety of aspects, such as structural measures, node communities detection, layer reducibility, network generative models, and information spreading. In this work we focus on techniques for the exploration of the intrinsic structure of multiplex networks, and contemplate ways of addressing common challenges of learning from multiplex networks. In particular, our work focuses on three main directions: structured regression, graph summarization and graph similarity. We analyze and discuss the main challenges of each of these research directions, and then we propose novel methods to address them. For each problem, we utilize artificial data to study their effectiveness, understand their intrinsic properties and evaluate their behavior under a controlled network structure. Then, we report applications on real-world data sets, from variety of domains, and compare our proposed methods with state-of-the-art and well established baseline methods. Through this work, we aim to offer proof that the networks' intrinsic structure, when utilized, can increase the informative power of network theory models and allow researchers to build more educated algorithms. / Computer and Information Science