Computer Science Graduate Seminar

Thursday, September 23, 2021, 2:00pm

Learning on Graphs with Logic and Neural Networks

• Martin Ritzert M.Sc. – Chair for Computer Science 7
• Location: Room 9222 and Zoom video conference: 
  https://rwth.zoom.us/j/95250295111?pwd=cjhFMGk0bStZcGNvcmYrYURPWnQ0dz09
  We kindly request you to register if you would like to participate on site.

 

 

Abstract

In the domain of graphs we show strong connections between logic and machine learning in both theory and practice. In a purely theoretical framework we develop sublinear machine learning algorithms for supervised learning of logical formulas on various graph classes. Further we show that learning first-order logic on arbitrary graphs is intractable unless P=NP. At the intersection of theory and practice, we prove an equivalence between graph neural networks and the 1-dimensional Weisfeiler-Leman algorithm. As a practical application, we approximate combinatorial problems with recurrent graph neural networks. The proposed architecture is unsupervised and can be applied to all maximum constraint satisfaction problems.

 

The computer science lecturers invite interested people to join.