  Graph pooling compresses graph information into a compact representation.
State-of-the-art graph pooling methods follow a hierarchical approach, which
reduces the graph size step-by-step. These methods must balance memory
efficiency with preserving node information, depending on whether they use node
dropping or node clustering. Additionally, fixed pooling ratios or numbers of
pooling layers are predefined for all graphs, which prevents personalized
pooling structures from being captured for each individual graph. In this work,
inspired by bottom-up grammar induction, we propose an efficient graph parsing
algorithm to infer the pooling structure, which then drives graph pooling. The
resulting Graph Parsing Network (GPN) adaptively learns personalized pooling
structure for each individual graph. GPN benefits from the discrete assignments
generated by the graph parsing algorithm, allowing good memory efficiency while
preserving node information intact. Experimental results on standard benchmarks
demonstrate that GPN outperforms state-of-the-art graph pooling methods in
graph classification tasks while being able to achieve competitive performance
in node classification tasks. We also conduct a graph reconstruction task to
show GPN's ability to preserve node information and measure both memory and
time efficiency through relevant tests.
