English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We analyze greedy algorithms for the Hierarchical Aggregation (HAG) problem,a strategy introduced in [Jia et al., KDD 2020] for speeding up learning onGraph Neural Networks (GNNs). The idea of HAG is to identify and removeredundancies in computations performed when training GNNs. The associatedoptimization problem is to identify and remove the most redundancies.  Previous work introduced a greedy approach for the HAG problem and claimed a1-1/e approximation factor. We show by example that this is not correct, andone cannot hope for better than a 1/2 approximation factor. We prove that thisgreedy algorithm does satisfy some (weaker) approximation guarantee, by showinga new connection between the HAG problem and maximum matching problems inhypergraphs. We also introduce a second greedy algorithm which can out-performthe first one, and we show how to implement it efficiently in some parameterregimes. Finally, we introduce some greedy heuristics that are much faster thanthe above greedy algorithms, and we demonstrate that they perform well onreal-world graphs.

On Greedy Approaches to Hierarchical Aggregation