  With the advent of data science, the analysis of network or graph data has
become a very timely research problem. A variety of recent works have been
proposed to generalize neural networks to graphs, either from a spectral graph
theory or a spatial perspective. The majority of these works however focus on
adapting the convolution operator to graph representation. At the same time,
the pooling operator also plays an important role in distilling multiscale and
hierarchical representations but it has been mostly overlooked so far. In this
paper, we propose a parameter-free pooling operator, called iPool, that permits
to retain the most informative features in arbitrary graphs. With the argument
that informative nodes dominantly characterize graph signals, we propose a
criterion to evaluate the amount of information of each node given its
neighbors, and theoretically demonstrate its relationship to neighborhood
conditional entropy. This new criterion determines how nodes are selected and
coarsened graphs are constructed in the pooling layer. The resulting
hierarchical structure yields an effective isomorphism-invariant representation
of networked data in arbitrary topologies. The proposed strategy is evaluated
in terms of graph classification on a collection of public graph datasets,
including bioinformatics and social networks, and achieves state-of-the-art
performance on most of the datasets.
