The Expressive Power of (Multi)Set-based higher-order Graph Neural Networks

Abstract

Graph data is widely used in various applications, driving the rapid development of graph-based machine learning methods. However, traditional algorithms tailored for graphs have constraints in capturing intricate node relationships and higher-order patterns. Recent insights from prior research have shed light on comparing different graph neural network architectures. This work introduced higher-order neural networks capable of grasping complex graph patterns. Nevertheless, these models encounter scalability issues that hinder their application to real-world datasets. This thesis builds on this foundation by theoretically assessing the various neural architectures proposed in those studies. Moreover, we present novel models aiming to find a middle ground between capturing higher-order patterns and maintaining scalability. Our objective is to enhance the modeling capabilities of graph-based algorithms and address existing limitations. Additionally, we implemented our models on benchmark datasets to gauge their performance. The outcomes confirm that our models achieve notably improved generalization compared to conventional graph neural networks. Furthermore, our models exhibit substantial scalability enhancements when contrasted with other higher-order graph neural networks. This research contributes to graph machine learning by offering more efficient and scalable methods for capturing higher-order patterns in graph data.