Learning Resolution-Consistent Representations for Graph Neural Networks

Co-Supervised by: Kalvin Dobler

If you are interested in this topic or have further questions, do not hesitate to contact: kalvin.dobler@unibe.ch

Background / Context

Graphs are often used to represent the same underlying system at different resolutions. For example, a physical, biological, or molecular system may be represented using fine-grained nodes or by aggregating them into coarser entities. Ideally, a Graph Neural Network (GNN) should produce consistent representations and predictions when the resolution changes. However, recent work shows that standard message-passing GNNs can assign substantially different latent representations to graphs describing the same underlying object at different resolutions.

This raises a fundamental question about the scale consistency and generalization of GNNs: can GNNs learn representations that are stable across different graph resolutions?

Research Question(s) / Goals

The project will investigate:

  • How sensitive are common GNN architectures to changes in graph resolution?
  • How does the choice of graph coarsening/refinement affect learned representations and predictions?
  • Can training objectives or architectural modifications improve cross-resolution consistency?
  • Does resolution consistency improve generalization to graph resolutions not observed during training?

Approach / Methods

The project will construct multiple representations of the same underlying graphs at different resolutions using controlled graph coarsening/refinement procedures. Standard architectures such as GCN, GIN, GraphSAGE, and potentially Graph Transformers will be evaluated.

Experiments will measure:

  1. Representation consistency between corresponding graphs at different resolutions.
  2. Prediction consistency for graph- and node-level tasks.
  3. Cross-resolution generalization, training at one resolution and testing at another.
  4. The influence of graph size, topology, and coarsening ratio.

Expected Contributions / Outcomes

The project is expected to provide:

  • A systematic empirical evaluation of GNN behavior across graph resolutions.
  • A benchmark for cross-resolution generalization of common GNN architectures.
  • An analysis of which architectural and training choices improve scale consistency.
  • Potentially, a simple method for improving resolution-invariant graph representations.
  • An open-source implementation and experimental results that can serve as a basis for further research.

Required Skills

  • Familiarity with graph theoretic concepts, machine learning experimentation and evaluation, or willingness to learn them.
  • Basic programming skills in Python.
  • Interest in graph neural networks and deep learning.

Further Readings

  • Loukas & Vandergheynst, “Spectrally Approximating Large Graphs with Smaller Graphs,” ICML 2018.
  • Loukas, “Graph Reduction with Spectral and Cut Guarantees,” JMLR 2019.
  • Koke et al., “Graph Neural Networks Are Not Continuous Across Graph Resolutions,” ICML 2026.