Universität Bielefeld Play

[MA]

Graph Neural Networks: Random-Walk vs. Aggregation-based Models

Contact: Luca Hermes

Graph Neural Networks (GNNs) are a highly active research area that enable deep learning on irregularly structured data. Molecules, infrastructure and social networks are popular domains where these models are being applied. Three fundamentally different types of GNNs exist, i.e. spatial, spectral and random-walk-based GNNs. Despite extensive research conducted towards all three, it is still not well-understood how to decide on a type of GNN. This thesis has a focus on the spatial and random-walk GNNs and aims to investigate the strengths and weaknesses of either one. Whether this is done theoretically or empirically is completely left to the student.

This thesis proposal is very general on purpose and leaves room for personal preference on what aspects to investigate. In general, the idea is that different graph benchmarks/datasets test different properties of a GNN and the main question here is: How do spatial- and random walk-based GNNs compare on the different benchmarks? From the experiments further questions can arise, like: Is there a type of benchmark where either one of the architectures fails and if so, why? For a nice overview of the differences between benchmarks, [7] (http://arxiv.org/abs/2206.07729) is a perfect read.

Literature

  1. [Random Walk] Deepwalk: Online Learning of Social Representations: https://arxiv.org/abs/1403.6652 (2014)
  2. [Random Walk] node2vec: Scalable Feature Learning for Networks: https://cs.stanford.edu/-jure/pubs/node2vec-kdd16.pdf (2016)
  3. [Random Walk] Attributed Random walk as Matrix Factorization: https://par.nsf.gov/biblio/10159689-attributed-random-walk-matrix-factorization (2022)
  4. [Spatial GNN] Semi-Supervised Classification with Graph Convolutional Networks: http://arxiv.org/abs/1609.02907 (2017)
  5. [Spatial GNN] Neural Message Passing for Quantum Chemistry: http://arxiv.org/abs/1704.01212 (2017)
  6. [Spatial GNN] How Powerful are Graph Neural Networks?: http://arxiv.org/abs/1810.00826 (2018)
  7. [GNN Benchmarks] Taxonomy of Benchmarks in Graph Representation Learning: http://arxiv.org/abs/2206.07729 (2022)