# Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

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

## Key facts

- Cited by 116 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2020.

## Built on by (most cited first, 30 of 116)

- [Membership Inference Attacks on Machine Learning: A Survey](https://mlsanity.com/paper/2103.07853/) (2021)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation](https://mlsanity.com/paper/2502.05424/) (2025)
- [Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond](https://mlsanity.com/paper/2209.06177/) (2022)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [Turning Tabular Foundation Models into Graph Foundation Models](https://mlsanity.com/paper/2508.20906/) (2025)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [Learning on Graphs with Out-of-Distribution Nodes](https://mlsanity.com/paper/2308.06714/) (2023)
- [The Shapley Value of Classifiers in Ensemble Games](https://mlsanity.com/paper/2101.02153/) (2021)
- [Transformer Copilot: Learning from The Mistake Log in LLM Fine-tuning](https://mlsanity.com/paper/2505.16270/) (2025)
- [GraphPFN: A Prior-Data Fitted Graph Foundation Model](https://mlsanity.com/paper/2509.21489/) (2025)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [Graph Unlearning with Efficient Partial Retraining](https://mlsanity.com/paper/2403.07353/) (2024)
- [GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts](https://mlsanity.com/paper/2312.04693/) (2023)
- [Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models](https://mlsanity.com/paper/2506.14291/) (2025)
- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [Newer is not always better: Rethinking transferability metrics, their peculiarities, stability and performance](https://mlsanity.com/paper/2110.06893/) (2021)
- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [Scalable Spectral Clustering with Group Fairness Constraints](https://mlsanity.com/paper/2210.16435/) (2022)
- [Bringing Graphs to the Table: Zero-shot Node Classification via Tabular Foundation Models](https://mlsanity.com/paper/2509.07143/) (2025)
- [Interpreting Language Models Through Knowledge Graph Extraction](https://mlsanity.com/paper/2111.08546/) (2021)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Taxonomy of Benchmarks in Graph Representation Learning](https://mlsanity.com/paper/2206.07729/) (2022)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization](https://mlsanity.com/paper/2109.07016/) (2021)

## Abstract (arXiv)

In this paper, we propose a flexible notion of characteristic functions defined on graph vertices to describe the distribution of vertex features at multiple scales. We introduce FEATHER, a computationally efficient algorithm to calculate a specific variant of these characteristic functions where the probability weights of the characteristic function are defined as the transition probabilities of random walks. We argue that features extracted by this procedure are useful for node level machine learning tasks. We discuss the pooling of these node representations, resulting in compact descriptors of graphs that can serve as features for graph classification algorithms. We analytically prove that FEATHER describes isomorphic graphs with the same representation and exhibits robustness to data corruption. Using the node feature characteristic functions we define parametric models where evaluation points of the functions are learned parameters of supervised classifiers. Experiments on real world large datasets show that our proposed algorithm creates high quality representations, performs transfer learning efficiently, exhibits robustness to hyperparameter changes, and scales linearly with the input size.