BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks

Omar Alsaqa, Thi Linh Hoang, Muhammed Fatih Balin · 2025

Read BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks by Omar Alsaqa, Thi Linh Hoang, Muhammed Fatih Balin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22388.txt.

Introduction

Omar Alsaqa, Linh Thi Hoang, and Muhammed Fatih Balin introduce BLISS, a sampling strategy that makes training graph neural networks on huge graphs affordable. Such networks learn from connected data but must process every neighbor of every node, which explodes memory and compute on large graphs. BLISS borrows the multi-armed bandit idea from decision theory, dynamically picking the most informative nodes at each layer.

By balancing exploration against exploitation, the sampler keeps coverage of the whole graph while adapting as node importance shifts during training, unlike static sampling schemes. BLISS plugs into both graph convolutional networks and graph attention networks, adjusting its choices to each one's aggregation style. Tests show it maintains or exceeds the accuracy of full-batch training at a fraction of the cost.

Catalog record

CREATOROmar Alsaqa, Thi Linh Hoang, Muhammed Fatih Balin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-22388

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks Omar Alsaqa, Thi Linh Hoang, Muhammed Fatih Balin Abstract Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, but their application to large graphs is hindered by computational costs. The need to process every neighbor for each node creates memory and computational bottlenecks. To address this, we introduce BLISS, a Bandit Layer Importance Sampling Strategy. It uses multi-armed bandits to dynamically select the most informative nodes at each layer, balancing exploration and exploitation to ensure comprehensive graph coverage. Unlike existing static sampling methods, BLISS adapts to evolving node importance, leading to more informed node selection and improved performance. It demonstrates versatility by integrating with both Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs), adapting its selection policy to their specific aggregation mechanisms. Experiments show that BLISS maintains or exceeds the accuracy of full-batch training. 1 Introduction Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, enabling applications such as personalized recommendations 22 ; 21 , drug discovery 14 ; 16 , image understanding 10 ; 11 , and enhancing Large Language Models (LLMs) 23 ; 19 ; 6 . Architectures like GCNs and GATs have addressed early limitations in capturing long-range dependencies. However, training GNNs on large graphs remains challenging due to prohibitive memory and computational demands, primarily because considering all neighbor nodes for each node leads to excessive memory and computational costs. While mini-batching, common in deep neural networks, can mitigate memory issues, uninformative mini-batches can lead to: 1) Sparse representations : Nodes may be isolated, neglecting crucial connections and resulting in poor representations. 2) Neighborhood explosion : A node’s receptive field grows exponentially with layers, making recursive neighbor aggregation computationally prohibitive even for single-node mini-batches. u_{1} u_{2} v_{3} v_{4} v_{5} 0.5 0.5 0.3 0.7 u_{1} u_{2} v_{3} v_{4} v_{5} 0.5 0.5 0.3 0.7 Figure 1: The figures illustrate Node-wise vs. Layer-wise sampling. Left: Node-wise sampling selects nodes per target node, often causing redundancy (e.g., v_{4} sampled for both u_{1} and u_{2} ), higher sampling rates (e.g., v_{4} , v_{5} ), and missing edges (e.g., u_{2} – v_{4} ). Right: Layer-wise sampling considers all nodes in the previous layer, preserving structure and connectivity while sampling fewer nodes. Efficient neighbor sampling is essential to address these challenge. Techniques include random selection, feature- or importance-based sampling, and adaptive strategies learned during training. They fall into three categories: (1) Node-wise sampling , which selects neighbors per node to reduce cost but risks redundancy (e.g., GraphSAGE 9 , VR-GCN 3 , BS-GNN 15 ); (2) Layer-wise sampling , which samples neighbors jointly at each layer for efficiency and broader coverage but may introduce bias (e.g., FastGCN 4 , LADIES 25 , LABOR 1 ); and (3) Sub-graph sampling , which uses induced subgraphs for message passing, improving efficiency but potentially losing global context if reused across layers (e.g., Cluster-GCN 7 , GraphSAINT 24 ). Our key contributions are: (1) Modeling neighbor selection as a layer-wise bandit problem: Each edge represents an "arm" and the reward is based on the neighbor’s contribution to reducing the variance of the representation estimator. (2) Applicability to Different GNN Architectures: BLISS is designed to be compatible with various GNN architectures, including GCNs and GATs. The remainder is organized as follows: section 2 describes BLISS; section 3 reports results; section 4 concludes. A detailed background and related work appear in appendices B and C . 2 Proposed Method 2.1 Bandit-Based Layer Importance Sampling Strategy (BLISS) BLISS selects informative neighbors per node and layer via a policy-based approach, guided by a dynamically updated sampling distribution driven by rewards reflecting each neighbor’s contribution to node representation. Using bandit algorithms, BLISS balances exploration and exploitation, adapts to evolving embeddings, and maintains scalability on large graphs. Traditional node sampling often fails to manage this trade-off or adapt to changing node importance, reducing accuracy and scalability. While 15 framed node-wise sampling as a bandit problem, BLISS extends it to layer-wise sampling, leveraging inter-layer information flow and reducing redundancy (see fig. 1 ). Initially, edge weights w_{ij}=1 for all j\in\mathcal{N}_{i} , with sampling probabilities q_{ij} set proportionally. BLISS proceeds top-down from the final layer L , computing layer-wise sampling probabilities p_{j} for nodes in layer l . These are passed to algorithm 4 , which selects k nodes. The GNN then performs a forward pass, where each node i aggregates from sampled neighbors j_{s} to approximate its representation \hat{\mu}_{i} : \displaystyle p_{j}=\sqrt{\sum_{i}\left(\frac{q_{ij}}{\sum_{k\in\mathcal{N}_{i}}q_{ik}}\right)^{2}} (1) \displaystyle h_{i}=\frac{1}{k}\sum_{s=1}^{k}\frac{\alpha_{{ij}s}}{q_{{ij}s}}\hat{h}_{j_{s}} (2) Here, j_{s}\sim q_{i} denotes the s -th sampled neighbor of node i , drawn from the per-node sampling distribution q_{i} . This process updates node representations h_{j} . The informativeness of neighbors is quantified as a reward r_{ij} , and the estimated rewards \hat{r}_{ij} are calculated as: \displaystyle r_{ij}=\frac{\alpha_{ij}^{2}}{k\cdot q_{j}^{2}}\|h_{j}\|_{2}^{2}, (3) \displaystyle\hat{r}_{ij}^{(t)}=\frac{r_{ij}^{(t)}}{q_{j}^{(t)}}\quad\text{if }j\in S_{i}^{t} (4) where S_{i}^{t} is the set of sampled neighbors at step t , \alpha_{ij} is the aggregation coefficient, and h_{j} is the node embedding. The edge weights w_{ij} and sampling probabilities q_{ij} are updated using the EXP3 algorithm (see algorithm 5 ). The edge weights are updated as follows: \displaystyle w_{ij}^{(t+1)}=w_{ij}^{(t)}\exp\left(\frac{\delta\hat{r}_{ij}^{(t)}}{|\mathcal{N}_{i}|}\right) (5) \displaystyle q_{ij}^{(t+1)}=(1-\eta)\frac{w_{ij}^{(t+1)}}{\sum_{j\in\mathcal{N}_{i}}w_{ij}^{(t+1)}}+\frac{\eta}{|\mathcal{N}_{i}|} (6) where \delta is a scaling factor and \eta is the bandit learning rate. BLISS operates through an iterative process of four steps: (1) dynamically selecting nodes at each layer via a bandit algorithm (e.g., EXP3) that assigns sampling probabilities, (2) estimating node representations by aggregating from sampled neighbors using Monte Carlo estimation, (3) performing standard GNN message passing with these samples, and (4) calculating rewards based on neighbor contributions to update the bandit policy and refine future sampling distributions. For the detailed algorithm check algorithm 2 . 2.2 Adapting to Graph Attention BLISS : We extend BLISS to attentive GNNs, following 15 . With only a sampled neighbor set S_{i} , true normalized attention \alpha_{ij} is unavailable. We compute unnormalized scores \tilde{\alpha}_{ij} and define adjusted feedback attention: \alpha^{\prime}_{ij}\;=\;\sum_{j\in S_{i}}q_{ij}\,\frac{\tilde{\alpha}_{ij}}{\sum_{j\in S_{i}}\tilde{\alpha}_{ij}} where q_{ij} is the bandit-determined sampling probability of edge e_{ij} . We use \sum_{j\in S_{i}}q_{ij} as a surrogate for the normalization over the full neighborhood N_{i} , thus approximating \alpha_{ij} while properly weighting sampled neighbors within the attention mechanism. PLADIES :Applying LADIES to attentive GNNs (e.g., GATs) requires preserving at least one neighbor per node after sampling to respect attention’s dependence on neighbor information. The PLADIES edge-sampling procedure, adapted from 1 and detailed in algorithm 4 , first computes initial probabilities (p_{j}) , then iteratively adjusts a scaling factor (c) so the sum of clipped probabilities approaches the target sample size (k) . Probabilities for seed nodes V_{\text{skip}} are set to \infty , guaranteeing selection and creating “skip connections,” ensuring each node retains a neighbor for attention while enabling LADIES to leverage attention efficiently. 3 Experiments 3.1 Datasets We evaluate the performance of each method in the node prediction task on the following datasets: Cora, Citeseer 18 , Pubmed 17 , Flickr, Yelp 24 , and Reddit 9 . More details of the benchmark datasets are given in table 3 . 3.2 Experiment Settings We compare BLISS with PLADIES, a strong baseline among existing layer-wise sampling algorithms. The code for both BLISS and PLADIES is publicly available. 1 1 1

Read the complete text