- GNN model for planted clique node classification problem
- Algorithm compared to a debatably optimal algorithm based on belief propagation (Deshpande et al. )
- This model outperforms BP algorithm in terms of accuracy and test time, but as the number of nodes increase, this performance gap seems to decrease. This might be a sign of BP algorithm being optimal if we consider GNN as an universal approximator of the optimal algorithm.
- The code generates an Erdos-Renyi graph with the prescribed density and plants a clique. The training is done in a supervised fashion.
- Models consist of variants of GNN and an upgraded version of GNN that also utilizes the edge information by considering line graphs. Graphs in planted clique problem are not sparse, so line graph can be approximated through sparsification.
torch
