Textual Relation Extraction is an important task for Natural Language Processing that aims to detect semantic relations between named entities in text. It can be seen as a multi-aspect challenge, with varying applications to several downstream tasks such as Question Answering, Knowledge Base completion and Event Extraction. In this dissertation, we aim to address two of the most common subtasks of Relation Extraction: the detection of relations inside sentences, also known as intra-sentence RE, as well as across sentences, known as inter-sentence RE. Our objectives in this study are two fold. Firstly, we suggest that interactions between multiple pairs should be taken into account when modelling relations, so as to enrich pair representations. Secondly, we want to leverage information encoded in the connections between different pairs, rather than the entities of the pair alone. To realise both goals, we propose a novel graph-based neural model, which we call edge-oriented; that is, it exploits the edges of a graph, which by definition correspond to relations, in the form of multi-dimensional representations. The proposed model can construct and/or update edge representations between pairs of nodes using other edges in the graph. As a result, we simultaneously model multiple pairs in a textual snippet by forming their representations as multi-hop interactions between their arguments. Throughout this work, we validate the proposed approach on several datasets, showing that it effectively improves relation detection on both multi-pair and single-pair sentences in different domains. Regarding document-level relations, we further propose a simple but intuitive way to construct heterogeneous document-level graphs and infer interactions between their nodes. We suggest that simple graph structures that can be constructed with heuristics can effectively capture interactions of interest in documents. In addition, incorporating information from the entire document proves beneficial for both intra- and inter-sentence relations. Overall, our edge-oriented model achieves promising results, thus demonstrating its potential suitability for relation extraction and other graph-based tasks.