Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization
This work addresses computational efficiency for researchers in graph classification, though it is incremental as it builds on existing unfolding and GDPA methods.
The paper tackled the high computational cost of unfolding proximal splitting algorithms with PSD cone projections by using GDPA linearization to create a projection-free algorithm for SDR of binary graph classifiers, resulting in a network that outperformed model-based classifiers and matched data-driven ones with fewer parameters.
Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. However, unfolding a proximal splitting algorithm with a positive semi-definite (PSD) cone projection operator per iteration is expensive, due to the required full matrix eigen-decomposition. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph classifier, where the PSD cone constraint is replaced by a set of "tightest possible" linear constraints per iteration. As a result, each iteration only requires computing a linear program (LP) and one extreme eigenvector. Inside the unrolled network, we optimize parameters via stochastic gradient descent (SGD) that determine graph edge weights in two ways: i) a metric matrix that computes feature distances, and ii) a sparse weight matrix computed via local linear embedding (LLE). Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.