Observe Locally, Classify Globally: Using GNNs to Identify Sparse Matrix
  Structure
Khaled Abdelaal Richard Veras
The performance of sparse matrix computation highly depends on the matching
of the matrix format with the underlying structure of the data being computed
on. Different sparse matrix formats are suitable for different structures of
data. Therefore, the first challenge is identifying the matrix structure before
the computation to match it with an appropriate data format. The second
challenge is to avoid reading the entire dataset before classifying it. This
can be done by identifying the matrix structure through samples and their
features. Yet, it is possible that global features cannot be determined from a
sampling set and must instead be inferred from local features. To address these
challenges, we develop a framework that generates sparse matrix structure
classifiers using graph convolutional networks. The framework can also be
extended to other matrix structures using user-provided generators. The
approach achieves 97% classification accuracy on a set of representative sparse
matrix shapes.