# Motif Prediction with Graph Neural Networks

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 112 references that are in the map.
- First posted on arXiv 26 May 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [AliGraph: A Comprehensive Graph Neural Network Platform](https://mlsanity.com/paper/1902.08730/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [Attention-based Graph Neural Network for Semi-supervised Learning](https://mlsanity.com/paper/1803.03735/) (2018)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems](https://mlsanity.com/paper/2008.11359/) (2020)
- [Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries](https://mlsanity.com/paper/1910.09017/) (2019)
- [Serverless Computing: Current Trends and Open Problems](https://mlsanity.com/paper/1706.03178/) (2017)
- [SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems](https://mlsanity.com/paper/2104.07582/) (2021)
- [Bridging the Gap between Spatial and Spectral Domains: A Survey on Graph Neural Networks](https://mlsanity.com/paper/2002.11867/) (2020)
- [Mathematical Foundations of the GraphBLAS](https://mlsanity.com/paper/1606.05790/) (2016)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems](https://mlsanity.com/paper/1912.12740/) (2019)
- [Scaling betweenness centrality using communication-efficient sparse matrix multiplication](https://mlsanity.com/paper/1609.07008/) (2016)
- [To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations](https://mlsanity.com/paper/2010.16012/) (2020)

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

- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [AdaFGL: A New Paradigm for Federated Node Classification with Topology Heterogeneity](https://mlsanity.com/paper/2401.11750/) (2024)
- [GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuning](https://mlsanity.com/paper/2511.05592/) (2025)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [Repeat-Aware Neighbor Sampling for Dynamic Graph Learning](https://mlsanity.com/paper/2405.17473/) (2024)
- [HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers](https://mlsanity.com/paper/2311.18526/) (2023)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [Tango: rethinking quantization for graph neural network training on GPUs](https://mlsanity.com/paper/2308.00890/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Approximate Network Motif Mining Via Graph Learning](https://mlsanity.com/paper/2206.01008/) (2022)
- [Towards Data-centric Machine Learning on Directed Graphs: a Survey](https://mlsanity.com/paper/2412.01849/) (2024)
- [Deal: Distributed End-to-End GNN Inference for All Nodes](https://mlsanity.com/paper/2503.02960/) (2025)
- [When LLMs meet open-world graph learning: a new perspective for unlabeled data uncertainty](https://mlsanity.com/paper/2505.13989/) (2025)
- [Studying and Improving Graph Neural Network-based Motif Estimation](https://mlsanity.com/paper/2506.15709/) (2025)
- [Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability](https://mlsanity.com/paper/2512.08475/) (2025)

## Abstract (arXiv)

Link prediction is one of the central problems in graph mining. However, recent studies highlight the importance of higher-order network analysis, where complex structures called motifs are the first-class citizens. We first show that existing link prediction schemes fail to effectively predict motifs. To alleviate this, we establish a general motif prediction problem and we propose several heuristics that assess the chances for a specified motif to appear. To make the scores realistic, our heuristics consider - among others - correlations between links, i.e., the potential impact of some arriving links on the appearance of other links in a given motif. Finally, for highest accuracy, we develop a graph neural network (GNN) architecture for motif prediction. Our architecture offers vertex features and sampling schemes that capture the rich structural properties of motifs. While our heuristics are fast and do not need any training, GNNs ensure highest accuracy of predicting motifs, both for dense (e.g., k-cliques) and for sparse ones (e.g., k-stars). We consistently outperform the best available competitor by more than 10% on average and up to 32% in area under the curve. Importantly, the advantages of our approach over schemes based on uncorrelated link prediction increase with the increasing motif size and complexity. We also successfully apply our architecture for predicting more arbitrary clusters and communities, illustrating its potential for graph mining beyond motif analysis.