# Grale: Designing Networks for Graph Learning

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2020.

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

- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)
- [Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning](https://mlsanity.com/paper/2406.09170/) (2024)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)
- [Graph Representation Learning in Biomedicine](https://mlsanity.com/paper/2104.04883/) (2021)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights](https://mlsanity.com/paper/2406.10727/) (2024)
- [Accelerating Large Scale Real-Time GNN Inference using Channel Pruning](https://mlsanity.com/paper/2105.04528/) (2021)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?](https://mlsanity.com/paper/2309.16595/) (2023)
- [LiGNN: Graph Neural Networks at LinkedIn](https://mlsanity.com/paper/2402.11139/) (2024)
- [Robust Training of Graph Neural Networks via Noise Governance](https://mlsanity.com/paper/2211.06614/) (2022)
- [Learning Strong Graph Neural Networks with Weak Information](https://mlsanity.com/paper/2305.18457/) (2023)
- [TF-GNN: Graph Neural Networks in TensorFlow](https://mlsanity.com/paper/2207.03522/) (2022)
- [Graph Sanitation with Application to Node Classification](https://mlsanity.com/paper/2105.09384/) (2021)
- [Synthetic Graph Generation to Benchmark Graph Learning](https://mlsanity.com/paper/2204.01376/) (2022)
- [Hypergraph Neural Networks through the Lens of Message Passing: A Common Perspective to Homophily and Architecture Design](https://mlsanity.com/paper/2310.07684/) (2023)
- [Towards Graph Foundation Models for Personalization](https://mlsanity.com/paper/2403.07478/) (2024)
- [On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks](https://mlsanity.com/paper/2409.17475/) (2024)
- [UGSL: A Unified Framework for Benchmarking Graph Structure Learning](https://mlsanity.com/paper/2308.10737/) (2023)
- [Measuring Re-identification Risk](https://mlsanity.com/paper/2304.07210/) (2023)
- [Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrix](https://mlsanity.com/paper/2307.02126/) (2023)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS](https://mlsanity.com/paper/2310.07667/) (2023)
- [WindTunnel -- A Framework for Community Aware Sampling of Large Corpora](https://mlsanity.com/paper/2410.20301/) (2024)
- [Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality](https://mlsanity.com/paper/2507.10139/) (2025)
- [Entity Representation Learning Through Onsite-Offsite Graph for Pinterest Ads](https://mlsanity.com/paper/2508.02609/) (2025)
- [SYNAPSE-G: Bridging Large Language Models and Graph Learning for Rare Event Classification](https://mlsanity.com/paper/2508.09544/) (2025)

## Abstract (arXiv)

How can we find the right graph for semi-supervised learning? In real world applications, the choice of which edges to use for computation is the first step in any graph learning process. Interestingly, there are often many types of similarity available to choose as the edges between nodes, and the choice of edges can drastically affect the performance of downstream semi-supervised learning systems. However, despite the importance of graph design, most of the literature assumes that the graph is static. In this work, we present Grale, a scalable method we have developed to address the problem of graph design for graphs with billions of nodes. Grale operates by fusing together different measures of(potentially weak) similarity to create a graph which exhibits high task-specific homophily between its nodes. Grale is designed for running on large datasets. We have deployed Grale in more than 20 different industrial settings at Google, including datasets which have tens of billions of nodes, and hundreds of trillions of potential edges to score. By employing locality sensitive hashing techniques,we greatly reduce the number of pairs that need to be scored, allowing us to learn a task specific model and build the associated nearest neighbor graph for such datasets in hours, rather than the days or even weeks that might be required otherwise. We illustrate this through a case study where we examine the application of Grale to an abuse classification problem on YouTube with hundreds of million of items. In this application, we find that Grale detects a large number of malicious actors on top of hard-coded rules and content classifiers, increasing the total recall by 89% over those approaches alone.