View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        The Think Like A Vertex approach in a parallel graph neural network

        Thumbnail
        View/Open
        KatharinaKlein_Thesis_Final.pdf (283.8Kb)
        Publication date
        2022
        Author
        Klein, Katharina
        Metadata
        Show full item record
        Summary
        Neural networks have been on the rise in the past years and are being applied in many different areas. Since in many applications the underlying data naturally has a graph-like structure, a type of network called graph neural network (GNN) has been proposed in 2009. This network type is able to capture dependencies within the graph by updating the state of each vertex based on the states of its neighbors, a process which has more recently been introduced as message passing. As graphs in practical applications are becoming considerably large, training and applying a GNN is computationally expensive and time-consuming and parallelization is therefore expected to be worthwhile. In the context of implementation, the Think Like A Vertex (TLAV) framework is a reasonable approach as it fits nicely with the BSP model for parallel programming. First introduced in 2010, the TLAV approach focuses on alternating local computations in a vertex and exchanging information with neighboring vertices. In this project, we combine TLAV with the BSP model in order to design a parallel algorithm implementing the message passing process of a GNN. We test this parallelization with an update function based on the Gated Recurrent Unit (GRU). Our experiments indicate that a reasonable speedup is obtained with respect to a sequential implementation, showing that the running time can be significantly reduced when applied to graphs of different sizes and with different properties.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/41581
        Collections
        • Theses
        Utrecht university logo