Ego-based Entropy Measures for Structural Representations

Abstract

In complex networks, nodes that share similar structural characteristics often exhibit similar roles (e.g type of users in a social network or the hierarchical position of employees in a company). In order to leverage this relationship, a growing literature proposed latent representations that identify structurally equivalent nodes. However, most of the existing methods require high time and space complexity. In this paper, we propose VNEstruct, a simple approach for generating low-dimensional structural node embeddings, that is both time efficient and robust to perturbations of the graph structure. The proposed approach focuses on the local neighborhood of each node and employs the Von Neumann entropy, an information-theoretic tool, to extract features that capture the neighborhood's topology. Moreover, on graph classification tasks, we suggest the utilization of the generated structural embeddings for the transformation of an attributed graph structure into a set of augmented node attributes. Empirically, we observe that the proposed approach exhibits robustness on structural role identification tasks and state-of-the-art performance on graph classification tasks, while maintaining very high computational speed.

arXiv comment7 pages, 4 figures

References in corpus (7)

• Neural Message Passing for Quantum Chemistry
• Learning Structural Node Embeddings Via Diffusion Wavelets
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• A Fair Comparison of Graph Neural Networks for Graph Classification
• Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification
• Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations