Spectral Maps for Learning on Subgraphs

Abstract

In graph learning, maps between graphs and their subgraphs frequently arise. For instance, when coarsening or rewiring operations are present along the pipeline, one needs to keep track of the corresponding nodes between the original and modified graphs. Classically, these maps are represented as binary node-to-node correspondence matrices and used as-is to transfer node-wise features between the graphs. In this paper, we argue that simply changing this map representation can bring notable benefits to graph learning tasks. Drawing inspiration from recent progress in geometry processing, we introduce a spectral representation for maps that is easy to integrate into existing graph learning models. This spectral representation is a compact and straightforward plug-in replacement and is robust to topological changes of the graphs. Remarkably, the representation exhibits structural properties that make it interpretable, drawing an analogy with recent results on smooth manifolds. We demonstrate the benefits of incorporating spectral maps in graph learning pipelines, addressing scenarios where a node-to-node map is not well defined, or in the absence of exact isomorphism. Our approach bears practical benefits in knowledge distillation and hierarchical learning, where we show comparable or improved performance at a fraction of the computational cost.

Publication
NeurReps Workshop 2023
Marco Pegoraro
Marco Pegoraro
PhD Student

I am a Ph.D. student in Geometric Deep Learning. My research activity is focused on spectral geometry processing applied to graph learning and computational biology.

Riccardo Marin
Riccardo Marin
PostDoctoral Researcher
Arianna Rampini
Arianna Rampini
Senior Research Scientist
Simone Melzi
Simone Melzi
Assistant Professor

Assistant Professor at the University of Milano-Bicocca

Luca Cosmo
Luca Cosmo
Assistant Professor
Emanuele Rodolà
Emanuele Rodolà
Full Professor