Share Email Print

Proceedings Paper

Experimental performance of graph neural networks on random instances of max-cut
Author(s): Weichi Yao; Afonso S. Bandeira; Soledad Villar
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

This note explores the applicability of unsupervised machine learning techniques towards hard optimization problems on random inputs. In particular we consider Graph Neural Networks (GNNs) - a class of neural networks designed to learn functions on graphs - and we apply them to the max-cut problem on random regular graphs. We focus on the max-cut problem on random regular graphs because it is a fundamental problem that has been widely studied. In particular, even though there is no known explicit solution to compare the output of our algorithm to, we can leverage the known asymptotics of the optimal max-cut value in order to evaluate the performance of the GNNs. In order to put the performance of the GNNs in context, we compare it with the classical semidefinite relaxation approach by Goemans and Williamson (SDP), and with extremal optimization, which is a local optimization heuristic from the statistical physics literature. The numerical results we obtain indicate that, surprisingly, Graph Neural Networks attain comparable performance to the Goemans and Williamson SDP. We also observe that extremal optimization consistently outperforms the other two methods. Furthermore, the performances of the three methods present similar patterns, that is, for sparser, and for larger graphs, the size of the found cuts are closer to the asymptotic optimal max-cut value.

Paper Details

Date Published: 9 September 2019
PDF: 10 pages
Proc. SPIE 11138, Wavelets and Sparsity XVIII, 111380S (9 September 2019); doi: 10.1117/12.2529608
Show Author Affiliations
Weichi Yao, New York Univ. (United States)
Afonso S. Bandeira, New York Univ. (United States)
Soledad Villar, New York Univ. (United States)

Published in SPIE Proceedings Vol. 11138:
Wavelets and Sparsity XVIII
Dimitri Van De Ville; Manos Papadakis; Yue M. Lu, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?