Graph Summarization with Graph Neural Networks
  The goal of graph summarization is to represent large graphs in a structured
and compact way. A graph summary based on equivalence classes preserves
pre-defined features of a graph's vertex within a $k$-hop neighborhood such as
the vertex labels and edge labels. Based on these neighborhood characteristics,
the vertex is assigned to an equivalence class. The calculation of the assigned
equivalence class must be a permutation invariant operation on the pre-defined
features. This is achieved by sorting on the feature values, e. g., the edge
labels, which is computationally expensive, and subsequently hashing the
result. Graph Neural Networks (GNN) fulfill the permutation invariance
requirement. We formulate the problem of graph summarization as a subgraph
classification task on the root vertex of the $k$-hop neighborhood. We adapt
different GNN architectures, both based on the popular message-passing protocol
and alternative approaches, to perform the structural graph summarization task.
We compare different GNNs with a standard multi-layer perceptron (MLP) and
Bloom filter as non-neural method. For our experiments, we consider four
popular graph summary models on a large web graph. This resembles challenging
multi-class vertex classification tasks with the numbers of classes ranging
from $576$ to multiple hundreds of thousands. Our results show that the
performance of GNNs are close to each other. In three out of four experiments,
the non-message-passing GraphMLP model outperforms the other GNNs. The
performance of the standard MLP is extraordinary good, especially in the
presence of many classes. Finally, the Bloom filter outperforms all neural
architectures by a large margin, except for the dataset with the fewest number
of $576$ classes.
