Promise and Limitations of Supervised Optimal Transport-Based Graph
  Summarization via Information Theoretic Measures
Sepideh Neshatfar Abram Magner Salimeh Yasaei Sekeh
Graph summarization is the problem of producing smaller graph representations
of an input graph dataset, in such a way that the smaller compressed graphs
capture relevant structural information for downstream tasks. There is a recent
graph summarization method that formulates an optimal transport-based framework
that allows prior information about node, edge, and attribute importance (never
defined in that work) to be incorporated into the graph summarization process.
However, very little is known about the statistical properties of this
framework. To elucidate this question, we consider the problem of supervised
graph summarization, wherein by using information theoretic measures we seek to
preserve relevant information about a class label. To gain a theoretical
perspective on the supervised summarization problem itself, we first formulate
it in terms of maximizing the Shannon mutual information between the summarized
graph and the class label. We show an NP-hardness of approximation result for
this problem, thereby constraining what one should expect from proposed
solutions. We then propose a summarization method that incorporates mutual
information estimates between random variables associated with sample graphs
and class labels into the optimal transport compression framework. We
empirically show performance improvements over previous works in terms of
classification accuracy and time on synthetic and certain real datasets. We
also theoretically explore the limitations of the optimal transport approach
for the supervised summarization problem and we show that it fails to satisfy a
certain desirable information monotonicity property.