Learning to solve the Hidden Clique Problem with Graph Neural Networks

Amaury Triboulin, Marc Lelarge, Kevin ScamanOpenReview 2022 · OpenReview

Abstract

We study data-driven methods for the hidden clique problem in random graphs. The training data is obtained by hiding a clique in the random graph, where the signal to noise ratio is tuned by choosing the size of the hidden clique and the density of the random graph. Using synthetic datasets allows us to test empirically the performance and generalization properties of various graph neural network (GNN) architectures at different levels of difficulties for the task. We compare message passing GNNs and GNNs augmented with a single quadratic operation (matrix multiplication) first introduced in \citep{maron2019fgnn}. Adding skip connections and normalization to these augmented GNNs is shown to improve their learning process and their generalization properties without any loss in time complexity. For hard instances of our hidden clique problem, they are shown to outperform message passing GNNs.
BibTeX
@misc{triboulin2022learning,
  author = {Amaury Triboulin and Marc Lelarge and Kevin Scaman},
  title = {{Learning to solve the Hidden Clique Problem with Graph Neural Networks}},
  year = {2022},
  url = {https://openreview.net/forum?id=TpqJy1BmD6K},
  howpublished = {OpenReview},
}

Loading related content...

Figure