Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures
Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures
复制标题
DOI：
10.1109/access.2023.3302830
复制
发表时间：
2023-05
期刊：
影响因子：
3.9
通讯作者：
Sepideh Neshatfar;A. Magner;S. Y. Sekeh
中科院分区：
文献类型：
--
作者：
Sepideh Neshatfar;A. Magner;S. Y. Sekeh
图汇总是指生成输入图数据集的较小图表示的问题，以使较小的压缩图捕获下游任务的相关结构信息。最近的图摘要方法之一制定了一个基于传输的最优框架，该框架允许将关于节点、边和属性重要性的先验信息合并到图摘要过程中。然而，人们对这一框架的统计特性知之甚少。为了阐明这个问题，我们考虑了有监督图摘要问题，在这个问题中，通过使用信息论的方法，我们试图保持关于类标签的相关信息。为了对有监督的摘要问题本身有一个理论上的观点，我们首先用最大化摘要图和类标签之间的Shannon互信息的方式来描述它。我们证明了这个问题的近似结果是NP-难的，从而限制了人们对所提出的解的期望。然后，我们提出了一种摘要方法，该方法将与样本图和类标签相关的随机变量之间的互信息估计结合到最优传输压缩框架中。我们在合成数据集和某些真实数据集上的实验表明，在分类准确率和时间方面，性能都比以前的工作有所提高。我们还从理论上探讨了有监督摘要问题的最优传输方法的局限性，证明了它不能满足某种期望的信息单调性。
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. One of the recent graph summarization methods formulates an optimal transport-based framework that allows prior information about node, edge, and attribute importance 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.