# Generalized Equivariance and Preferential Labeling for GNN Node Classification

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 31 references that are in the map.
- First posted on arXiv 23 Feb 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Learning to Represent Programs with Graphs](https://mlsanity.com/paper/1711.00740/) (2017)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs](https://mlsanity.com/paper/1803.08035/) (2018)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [Knowledge Transfer for Out-of-Knowledge-Base Entities: A Graph Neural Network Approach](https://mlsanity.com/paper/1706.05674/) (2017)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Graph Transformer for Graph-to-Sequence Learning](https://mlsanity.com/paper/1911.07470/) (2019)
- [TreeGen: A Tree-Based Transformer Architecture for Code Generation](https://mlsanity.com/paper/1911.09983/) (2019)
- [LambdaNet: Probabilistic Type Inference using Graph Neural Networks](https://mlsanity.com/paper/2005.02161/) (2020)
- [NLocalSAT: Boosting Local Search with Solution Prediction](https://mlsanity.com/paper/2001.09398/) (2020)

## Built on by (most cited first, 7 of 7)

- [Investigating Out-of-Distribution Generalization of GNNs: An Architecture Perspective](https://mlsanity.com/paper/2402.08228/) (2024)
- [An Equal-Size Hard EM Algorithm for Diverse Dialogue Generation](https://mlsanity.com/paper/2209.14627/) (2022)
- [Addressing Variable Dependency in GNN-based SAT Solving](https://mlsanity.com/paper/2304.08738/) (2023)
- [WATS: Calibrating Graph Neural Networks with Wavelet-Aware Temperature Scaling](https://mlsanity.com/paper/2506.23782/) (2025)
- [Towards Causal Classification: A Comprehensive Study on Graph Neural Networks](https://mlsanity.com/paper/2401.15444/) (2024)
- [SSHPool: The Separated Subgraph-based Hierarchical Pooling](https://mlsanity.com/paper/2403.16133/) (2024)
- [Predicting Protein-Ligand Binding Affinity with Equivariant Line Graph Network](https://mlsanity.com/paper/2210.16098/) (2022)

## Abstract (arXiv)

Existing graph neural networks (GNNs) largely rely on node embeddings, which represent a node as a vector by its identity, type, or content. However, graphs with unattributed nodes widely exist in real-world applications (e.g., anonymized social networks). Previous GNNs either assign random labels to nodes (which introduces artefacts to the GNN) or assign one embedding to all nodes (which fails to explicitly distinguish one node from another). Further, when these GNNs are applied to unattributed node classification problems, they have an undesired equivariance property, which are fundamentally unable to address the data with multiple possible outputs. In this paper, we analyze the limitation of existing approaches to node classification problems. Inspired by our analysis, we propose a generalized equivariance property and a Preferential Labeling technique that satisfies the desired property asymptotically. Experimental results show that we achieve high performance in several unattributed node classification tasks.