论文标题
摘要图中的边缘权重有用吗？ - 比较研究
Are Edge Weights in Summary Graphs Useful? -- A Comparative Study
论文作者
论文摘要
在具有和没有边缘权重的两个代表性图形摘要模型之间哪个更好？从网络图到在线社交网络，到处都有大图。图形摘要是一种有效的图形压缩技术，旨在找到准确代表给定的大图的紧凑型摘要图。问题的两个版本，一个版本允许在摘要图中允许边缘权重，而另一个则没有在未直接比较其基础表示模型之间进行并行研究。在这项工作中，我们通过将三种搜索算法扩展到模型，并在五个方面评估其在八个数据集上的输出来进行系统的比较：（（a）重建错误，（b）节点重要性中的错误，（c）节点接近性中的错误，（c）（d）重建图的大小和（e）压缩率的大小。令人惊讶的是，使用未加权的摘要图在所有方面都比使用加权方面的输出明显好得多，并且在理论上支持了这一发现。值得注意的是，我们表明可以基于（a），（b）和（c）分别改进最先进的算法（特定于8.2倍，7.8倍和5.9倍，当（a），（b）和（c）基于观察结果固定时（e）时）。
Which one is better between two representative graph summarization models with and without edge weights? From web graphs to online social networks, large graphs are everywhere. Graph summarization, which is an effective graph compression technique, aims to find a compact summary graph that accurately represents a given large graph. Two versions of the problem, where one allows edge weights in summary graphs and the other does not, have been studied in parallel without direct comparison between their underlying representation models. In this work, we conduct a systematic comparison by extending three search algorithms to both models and evaluating their outputs on eight datasets in five aspects: (a) reconstruction error, (b) error in node importance, (c) error in node proximity, (d) the size of reconstructed graphs, and (e) compression ratios. Surprisingly, using unweighted summary graphs leads to outputs significantly better in all the aspects than using weighted ones, and this finding is supported theoretically. Notably, we show that a state-of-the-art algorithm can be improved substantially (specifically, 8.2X, 7.8X, and 5.9X in terms of (a), (b), and (c), respectively, when (e) is fixed) based on the observation.
