In many real world applications, data are characterized by a complex structure, that can be naturally encoded as a graph. In the last years, the popularity of deep learning techniques has renewed the interest in neural models able to process complex patterns. In particular, inspired by the Graph Neural Network (GNN) model, different architectures have been proposed to extend the original GNN scheme. GNNs exploit a set of state variables, each assigned to a graph node, and a diffusion mechanism of the states among neighbor nodes, to implement an iterative procedure to compute the fixed point of the (learnable) state transition function. In this paper, we propose a novel approach to the state computation and the learning algorithm for GNNs, based on a constraint optimisation task solved in the Lagrangian framework. The state convergence procedure is implicitly expressed by the constraint satisfaction mechanism and does not require a separate iterative phase for each epoch of the learning procedure. In fact, the computational structure is based on the search for saddle points of the Lagrangian in the adjoint space composed of weights, neural outputs (node states), and Lagrange multipliers. The proposed approach is compared experimentally with other popular models for processing graphs.

Tiezzi, M., Marra, G., Melacci, S., Maggini, M., Gori, M. (2020). A lagrangian approach to information propagation in graph neural networks. In Frontiers in Artificial Intelligence and Applications (pp.1539-1546). IOS Press BV [10.3233/FAIA200262].

A lagrangian approach to information propagation in graph neural networks

Tiezzi, M.;Melacci, S.;Maggini, M.;Gori, M.
2020-01-01

Abstract

In many real world applications, data are characterized by a complex structure, that can be naturally encoded as a graph. In the last years, the popularity of deep learning techniques has renewed the interest in neural models able to process complex patterns. In particular, inspired by the Graph Neural Network (GNN) model, different architectures have been proposed to extend the original GNN scheme. GNNs exploit a set of state variables, each assigned to a graph node, and a diffusion mechanism of the states among neighbor nodes, to implement an iterative procedure to compute the fixed point of the (learnable) state transition function. In this paper, we propose a novel approach to the state computation and the learning algorithm for GNNs, based on a constraint optimisation task solved in the Lagrangian framework. The state convergence procedure is implicitly expressed by the constraint satisfaction mechanism and does not require a separate iterative phase for each epoch of the learning procedure. In fact, the computational structure is based on the search for saddle points of the Lagrangian in the adjoint space composed of weights, neural outputs (node states), and Lagrange multipliers. The proposed approach is compared experimentally with other popular models for processing graphs.
2020
978-164368100-9
Tiezzi, M., Marra, G., Melacci, S., Maggini, M., Gori, M. (2020). A lagrangian approach to information propagation in graph neural networks. In Frontiers in Artificial Intelligence and Applications (pp.1539-1546). IOS Press BV [10.3233/FAIA200262].
File in questo prodotto:
File Dimensione Formato  
melacci_ECAI2020.pdf

accesso aperto

Tipologia: PDF editoriale
Licenza: Creative commons
Dimensione 256 kB
Formato Adobe PDF
256 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1122687