We analyze greedy algorithms for the Hierarchical Aggregation (HAG) problem, a strategy introduced in [Jia et. al., KDD 2020] for speeding up learning on Graph Neural Networks (GNNs). The idea of HAG is to identify and remove redundancies in computations performed when training GNNs. The associated optimization problem is to identify and remove the most redundancies. Previous work introduced a greedy approach for the HAG problem and claimed a 1-1/e approximation factor. We show by example that this is not correct, and one cannot hope for better than a 1/2 approximation factor. We prove that this greedy algorithm does satisfy some (weaker) approximation guarantee, by showing a new connection between the HAG problem and maximum matching problems in hypergraphs. We also introduce a second greedy algorithm which can out-perform the first one, and we show how to implement it efficiently in some parameter regimes. Finally, we introduce some greedy heuristics that are much faster than the above greedy algorithms, and we demonstrate that they perform well on real-world graphs.
翻译:我们分析高层次聚合(HAG)问题的贪婪算法,这是[Jia等人,KDD 2020]为加速在图形神经网络(GNNs)上学习而采用的一项战略。HAG的想法是确定并消除在培训GNNs时进行的计算中的冗余。与此相关的优化问题在于识别并消除最冗余的情况。先前的工作对HAG问题采用了贪婪的方法,并主张了1-1/e近似系数。我们举例地表明,这不正确,人们也希望比1/2近似系数更好。我们证明,这种贪婪算法确实满足了某些(weker)近似保证,我们展示了HAG问题和最高匹配高光学问题之间的新联系。我们还引入了第二种贪婪算法,可以比前一种方法更完善,我们在某些参数系统中展示了如何有效地实施。最后,我们引入了一些比以上贪婪算法更快的贪婪高得多,我们证明它们在真实世界的图表上表现得很好。