Permute Me Softly: Learning Soft Permutations for Graph Representations.

Area of Science:

• Machine Learning
• Graph Neural Networks
• Artificial Intelligence

Background:

• Graph neural networks (GNNs), particularly message passing neural networks (MPNNs), are dominant in graph machine learning.
• Current research heavily focuses on MPNNs, necessitating novel architectures to advance the field.
• The Weisfeiler-Leman (WL) test provides a basis for understanding vertex representation updates in MPNNs.

Purpose of the Study:

• To propose a new GNN architecture, π-GNN, that moves beyond the MPNN paradigm.
• To introduce a method for projecting graphs into a common vector space using learned soft permutation matrices.
• To offer a novel approach for graph representation learning and subsequent supervised learning tasks.

Main Methods:

• Developed π-GNN, a novel graph neural network model.
• Employed doubly stochastic matrices to learn a soft ordering of vertices for each graph.
• Mapped adjacency matrices into vectors based on learned vertex ordering for downstream tasks.
• Relaxed doubly stochastic matrices to row stochastic matrices for efficiency with large graphs.

Main Results:

• π-GNN successfully projects graphs into a common vector space.
• The model imposes a soft ordering on graph vertices, enabling vector mapping.
• Empirical evaluation on graph classification and regression datasets shows competitive performance against state-of-the-art models.

Conclusions:

• π-GNN presents a viable and competitive alternative to existing MPNN approaches.
• The soft permutation matrix mechanism offers a novel way to learn graph representations.
• The proposed architecture demonstrates effectiveness in various graph-based supervised learning tasks.