Recognizing and classifying implicit discourse relations is a challenging task since hardly any strong indicators exist, and a variety of weak indicators has to be harnessed to yield evidence for a particular discourse relation or another. Most current approaches rely on a combination of shallow, surface-based features and rather specialized hand-crafted features, with a considerable gap in between which is partly due to the sheer complexity of combining evidence from different levels of linguistic description. As a way to avoid both the shallowness of word-based representations and the lack of coverage of specialized linguistic features, we use a graph-based representation of discourse segments, which allows for a more abstract (and hence generalizable) notion of syntactic (and partially of semantic) structure, we propose an approach to use a graph-structured representation of discourse units in order to improve the classification of implicit discourse relations. We validate this approach using implicit discourse relation data from the TüBa-D/Z treebank, providing an extended discussion and error analysis that looks at the impact of the graph-based representation on the different kinds of discourse relations. The empirical evaluation shows that our graph-based approach not only provides a suitable representation for the linguistic factors that are needed in disambiguating discourse relations, but also improves results over a strong state-of-the-art baseline by more accurately identifying Temporal, Comparison and (for the German data) Reporting discourse relations. 1.