Title: Multi-hop assortativities for networks classification,
Abstract: Several social, medical, engineering and biological challenges rely on
discovering the functionality of networks from their structure and node
metadata, when it is available. For example, in chemoinformatics one might want
to detect whether a molecule is toxic based on structure and atomic types, or
discover the research field of a scientific collaboration network. Existing
techniques rely on counting or measuring structural patterns that are known to
show large variations from network to network, such as the number of triangles,
or the assortativity of node metadata. We introduce the concept of multi-hop
assortativity, that captures the similarity of the nodes situated at the
extremities of a randomly selected path of a given length. We show that
multi-hop assortativity unifies various existing concepts and offers a
versatile family of 'fingerprints' to characterize networks. These fingerprints
allow in turn to recover the functionalities of a network, with the help of the
machine learning toolbox. Our method is evaluated empirically on established
social and chemoinformatic network benchmarks. Results reveal that our
assortativity based features are competitive providing highly accurate results
often outperforming state of the art methods for the network classification
task.