Back to search

FRINATEK-Fri mat.,naturv.,tek

SPECTRUM: Graph Learning

Alternative title: SPECTRUM: Graflæring

Awarded: NOK 3.6 mill.

Project Number:


Application Type:

Project Period:

2021 - 2024


Neural networks are computational structures designed to create abstraction, from raw input data - e.g., sensory inputs - to knowledge. Similarly to human brains, they transfer information from one node to another, emulating electrical signals travelling along neurons. The combinatorial object representing the structure of a neural network is known as a graph. The challenge of SPECTRUM is to optimize the power of neural networks by acting on the graphs underlying them. To achieve this goal, we propose to use the set of tools from Spectral Graph Theory. Like a guitar string or a star in the sky, each graph emits information at specific frequencies. Spectral Graph Theory is the mathematical study of properties of graphs in relation to the set of their frequencies, which is known as the spectrum. This framework is particularly well suited to the scope of our project, since various parameters of graphs expressing their ability to transmit information and their connectivity and expansion properties have been shown to be naturally associated with their spectrum. More in detail, we will use spectral-graph-theoretical tools to - optimize the efficiency of existing neural network architectures; - design a novel neural network architecture based on a Markov-chain mechanism, which better resembles the actual information transmission in the human brain. The graph structure of this new architecture will be the root of increased adaptability to various tasks compared to existing architectures. The success of this project will lay the foundation for a new generation of computational structures: graphs that think, and learn.

Artificial neural networks - computing systems fundamental to Machine Learning - can be mathematically viewed as graphs. SPECTRUM aims at exploiting the graph structure of neural networks to improve their performance, by using Spectral Graph Theory (SGT). In particular, the goals of SPECTRUM are: (G1) to provide an original framework for optimizing existing neural network architectures by modifying the graphs underlying their structure; (G2) to design and optimize a novel architecture based on the theory of Markov chains on graphs and inspired by the mechanism of signal transmission in the human brain during the learning process. For both G1 and G2, SGT will provide tools to quantify the dependence of the neural network efficiency on the structure of the graph underlying it and, hence, methods to improve efficiency. The main challenges of SPECTRUM are: (CH1) solving open problems in SGT related to the optimization of quantities such as the algebraic connectivity and Kemeny’s constant over certain families of graphs and to the use of Matrix Theory and Algebraic Graph Theory to speed up the computation of those quantities for graphs associated with neural networks, by exploiting their hierarchical structure; (CH2) solving technical issues concerning the implementation of the novel neural network architecture of G2. The PM will carry out the project at EPFL for the first two years and at UiO for the final year. The training at EPFL and the collaboration with Prof. Marcus will be crucial to address CH2; Prof. Dahl will support the rest of the team mainly for the aspects related to CH1. In the final stage of the project, the PM will organize scientific activities at UiO to disseminate the findings of SPECTRUM and to transfer the knowledge acquired in Switzerland to the Norwegian research community. He will also attend a pedagogical training program and a research leadership program at UiO. They will enhance the necessary skills to foster his future academic career.


FRINATEK-Fri mat.,naturv.,tek