# NAFS: A Simple yet Tough-to-beat Baseline for Graph Representation Learning

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 17 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [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)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Attributed Graph Clustering via Adaptive Graph Convolution](https://mlsanity.com/paper/1906.01210/) (2019)
- [Symmetric Graph Convolutional Autoencoder for Unsupervised Graph Representation Learning](https://mlsanity.com/paper/1908.02441/) (2019)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [OpenBox: A Generalized Black-box Optimization Service](https://mlsanity.com/paper/2106.00421/) (2021)
- [Node Dependent Local Smoothing for Scalable Graph Learning](https://mlsanity.com/paper/2110.14377/) (2021)

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

- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation](https://mlsanity.com/paper/2310.10998/) (2023)
- [Efficient Graph Neural Network Inference at Large Scale](https://mlsanity.com/paper/2211.00495/) (2022)
- [Molecular Topological Profile (MOLTOP) -- Simple and Strong Baseline for Molecular Graph Classification](https://mlsanity.com/paper/2407.12136/) (2024)
- [Structure-Aware Group Discrimination with Adaptive-View Graph Encoder: A Fast Graph Contrastive Learning Framework](https://mlsanity.com/paper/2303.05231/) (2023)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [Rethinking the positive role of cluster structure in complex networks for link prediction tasks](https://mlsanity.com/paper/2211.02396/) (2022)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [Toward Data-centric Directed Graph Learning: An Entropy-driven Approach](https://mlsanity.com/paper/2505.00983/) (2025)
- [AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective Propagation](https://mlsanity.com/paper/2602.17071/) (2026)
- [SMGFM: Spectral Multimodal Graph Pretraining for Multimodal-Attributed Graphs](https://mlsanity.com/paper/2606.12867/) (2026)

## Abstract (arXiv)

Recently, graph neural networks (GNNs) have shown prominent performance in graph representation learning by leveraging knowledge from both graph structure and node features. However, most of them have two major limitations. First, GNNs can learn higher-order structural information by stacking more layers but can not deal with large depth due to the over-smoothing issue. Second, it is not easy to apply these methods on large graphs due to the expensive computation cost and high memory usage. In this paper, we present node-adaptive feature smoothing (NAFS), a simple non-parametric method that constructs node representations without parameter learning. NAFS first extracts the features of each node with its neighbors of different hops by feature smoothing, and then adaptively combines the smoothed features. Besides, the constructed node representation can further be enhanced by the ensemble of smoothed features extracted via different smoothing strategies. We conduct experiments on four benchmark datasets on two different application scenarios: node clustering and link prediction. Remarkably, NAFS with feature ensemble outperforms the state-of-the-art GNNs on these tasks and mitigates the aforementioned two limitations of most learning-based GNN counterparts.