# Ego-based Entropy Measures for Structural Representations on Graphs

arXiv: https://arxiv.org/abs/2102.08735 · HTML: https://mlsanity.com/paper/2102.08735/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 17 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [k-hop Graph Neural Networks](https://mlsanity.com/paper/1907.06051/) (2019)
- [Coloring graph neural networks for node disambiguation](https://mlsanity.com/paper/1912.06058/) (2019)
- [Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification](https://mlsanity.com/paper/1905.04579/) (2019)
- [Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications](https://mlsanity.com/paper/1805.11769/) (2018)
- [Deep learning long-range information in undirected graphs with wave networks](https://mlsanity.com/paper/1810.12153/) (2018)

## Abstract (arXiv)

Machine learning on graph-structured data has attracted high research interest due to the emergence of Graph Neural Networks (GNNs). Most of the proposed GNNs are based on the node homophily, i.e neighboring nodes share similar characteristics. However, in many complex networks, nodes that lie to distant parts of the graph share structurally equivalent characteristics and exhibit similar roles (e.g chemical properties of distant atoms in a molecule, type of social network users). A growing literature proposed 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, based on entropy measures of the neighborhood's topology, for generating low-dimensional structural representations, that is time-efficient and robust to graph perturbations. Empirically, we observe that VNEstruct exhibits robustness on structural role identification tasks. Moreover, VNEstruct can achieve state-of-the-art performance on graph classification, without incorporating the graph structure information in the optimization, in contrast to GNN competitors.