FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

Peng Fang

Arijit Khan

Ziqiang Wu

Zhenli Li

Huazhong University of Science and Technology [email protected]

Bowling Green State University [email protected]

Huazhong University of Science and Technology [email protected]

Yibo Zhou

Fang Wang*

Dan Feng

Huazhong University of Science and Technology [email protected]

ABSTRACT

Efficiency

Graph embedding maps graph nodes into low-dimensional vectors to support applications such as recommendation, fraud detection, and graph-based retrieval-augmented generation (GraphRAG). As graphs scale to billions of edges, scalable and efﬁcient graph embedding has become increasingly important. Existing frameworks commonly adopt a sampling-training paradigm, in which mini-batches are constructed by sampling nodes and their neighbors. However, sampling is typically decoupled from evolving embedding quality, causing redundant exploration of well-trained regions while undersampling undertrained nodes. At the system level, such decoupling further leads to excessive communication, serialized execution, and low resource utilization in distributed environments. We present FeLoG, a feedback loop-driven system for scalable distributed graph embedding. (1) FeLoG introduces feedback-coupled sampling and training, dynamically prioritizing undertrained nodes according to real-time embedding-quality feedback, thereby reducing redundant computation and accelerating convergence. (2) It employs activity-aware communication that compresses frequently occurring node sequences to reduce intra-machine PCIe trafﬁc and selectively synchronizes frequently updated embeddings to reduce inter-machine communication. (3) It adopts a round-interleaved pipeline that overlaps next-round sampling with current-round training to improve CPU-GPU utilization. Experiments against six state-of-theart baselines on large-scale graphs show that FeLoG achieves an average speedup of 27.9×, reduces communication cost by more than 53.1%, and sustains over 80% CPU-GPU utilization.

KEYWORDS Graph embedding; Sampling-training paradigm; Feedback

Distributed

CPU-GPU

INTRODUCTION

Graph embedding [7], a powerful tool for graph analytics, has become a cornerstone for learning node representations from graph data. Speciﬁcally, it transforms high-dimensional, sparse graph structures into low-dimensional, dense vector spaces, preserving both structural and attribute information of the original graph. Beyond

* Corresponding Author.

FeLoG GIDS[45] NeutronTP[3] (VLDB’24) (VLDB’25) DistGER[17] MGG[68] LeapGNN[13] (VLDB’23) (OSDI’23) BGL[39] (NSDI’23)

FeLoG DistGER [17] DistDGL [85]

NeutronTP [3] LeapGNN [13] Pytorch-Biggraph [33]

(FAST’25)

NeutronStar[65] MariusGNN[60] DistDGL[85] (SIGMOD’22)

Efficiency

arXiv:2606.22180v1 [cs.DC] 20 Jun 2026

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

(EuroSys’23)

Seastar[73]

Pytorch-Biggraph[33]

(EuroSys’21)

ProNE[79] (IJCAI’19)

(IA3’20)

(MLSys’19)

HuGE[21] (ICDE’21)

GraphSAGE[25] (NeurIPS’17)

Deepwalk[47] Node2vec[24] (KDD’14) (KDD’16)

OMeGa[19] BeaconGNN[69](ICDE’25) (HPCA’24)

SmartSAGE[32] (ISCA’22) Ginex[46] AWB-GCN[22]

(VLDB’22)

(MICRO’20)

Model-level

Hardware

Scalability

(a) Existing Solutions

(b) Our Design Objectives

Figure 1: (a) Existing approaches vs. FeLoG (ours) w.r.t. modeland system-level design choices and efﬁciency-scalability performance; (b) our design objectives for the proposed system FeLoG. traditional data-driven tasks, e.g., recommendation [83], link prediction [52], and node classiﬁcation [72], their versatility has recently extended to retrieval-augmented generation (RAG) [15]. Embeddings act as a bridge between graph-structured data and large language models (LLMs), enabling efﬁcient retrieval and grounding over large-scale graphs. In such applications, graphs can be huge with millions of nodes and billions of edges. For example, the Stanford OGB-papers100M citation network contains over 111 million nodes and 1.6 billion edges, posing signiﬁcant challenges for tasks such as link prediction and classiﬁcation [27]. Similarly, GraphRAG frameworks leverage knowledge graphs with comparable or greater scale, often containing millions of entities and relationships [40]. The commonly-used graph embedding paradigms follow a twostage process: sampling and training. In random walk-based methods [21, 24, 47], node sequences or subgraphs are sampled from the original graph, and are used to train embedding models. In graph neural network (GNN)-based approaches [25, 37, 59], the sampling step selects a subset of neighbors for each node to construct computation subgraphs, and the training stage then performs message passing and aggregation on these sampled subgraphs to learn the ﬁnal embeddings. When the scale of graph data increases, the fundamental challenges in graph embedding primarily lie in efﬁciency and scalability, as depicted in Figure 1(a). At the core of these challenges is the decoupled sampling-training paradigm, which serves as the root cause of inefﬁciencies across both the model and system levels.

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

Training

···

Skip-Gram

Random Walk

··· Subgraph

G = (V, E)

···

Sampling

··· ···

From the model perspective, the separation of sampling from training generates large amounts of redundant or uninformative training data without guidance from the evolving embedding states, thereby driving both computational and memory inefﬁciencies. Classical methods such as DeepWalk [47] and node2vec [24] require months to process graphs with hundreds of millions of nodes and edges [79], and their scalability is further constrained by excessive memory consumption [21]. Even neighbor-sampling methods such as GraphSAGE [25] spend over 80% of runtime on sampling due to the lack of feedback from training. More recent methods like HuGE [20, 21] guide sampling adaptively but remain limited by the decoupled paradigm, hindering redundancy control and efﬁciency. From the system perspective, existing efforts exploit heterogeneous architectures or distributed clusters by leveraging stronger GPUs [39, 60, 68], larger SSDs [32, 45, 46], or scale-out designs [17, 65, 85]. However, the decoupled sampling-training paradigm is also the key reason behind system-level inefﬁciencies, which persist despite these advances. One critical challenge is high communication overhead, as the bandwidth gap between computation and interconnect severely limits scalability. Since sampling is decoupled from training, the system must transfer all sampled data, including redundant neighborhoods, across CPU-GPU or machine boundaries, which signiﬁcantly inﬂates communication costs. For example, the NVIDIA A100 provides 2 TB/s of GPU memory bandwidth, whereas PCIe bandwidth remains around 20 GB/s, making CPUside sampling the bottleneck. In distributed settings, synchronizing embeddings for billion-edge graphs such as Twitter [31] requires hundreds of GBs of data exchange, incurring multi-second latencies and reducing GPU utilization to as low as 10% in DistDGL [85]. Another challenge is low resource utilization, since the sequential dependency enforced by decoupled sampling and training prevents overlap between the two stages and results in long idle periods. In DistGER [17], CPU and GPU utilization remain only 15.8% and 25.5%, respectively, even under heavy workloads. Pipeline and caching strategies adopted in MariusGNN [60] and Ginex [46] partially mitigate this issue, but their decoupled designs lack runtime feedback to dynamically adapt sampling to training needs. To address the above challenges, we present FeLoG, a distributed system built around a sampling-training Feedback Loop for Graph embedding. This feedback loop directly targets the root cause of inefﬁciencies and serves as the foundation that enables our three technical contributions. Figure 1(b) summarizes the design objectives of FeLoG, which correspond to improving execution efﬁciency, reducing communication overhead, and enhancing resource utilization. First, FeLoG introduces a Feedback-coupled Sampling-Training model (FeeST) that tightly integrates sampling with training. Unlike existing methods that sample blindly or heuristically, FeeST leverages real-time feedback from embedding quality to guide subsequent sampling. By prioritizing nodes with undertrained embeddings, it captures more informative context, reduces redundancy, and accelerates convergence. Second, to mitigate communication bottlenecks, FeLoG incorporates an Activity-aware Communication Mechanism (ACM). Here, activity refers to dynamic access and update patterns of nodes during embedding training, e.g., how frequently a node or its context is sampled and how often its embedding is modiﬁed. By exploiting these patterns, ACM analyzes data ﬂow characteristics and applies targeted optimizations. Speciﬁcally,

Layer 1

Layer K

φ: V → Rd

Figure 2: Sampling and training in graph embedding.

it uses a Frequency-aware Bitmap Compression strategy (FaBC) to reduce PCIe trafﬁc between CPU and GPU, and a Hotspot-aware Synchronization strategy (HaSyn) to minimize inter-machine communication by focusing only on embeddings with high update activity. Last, to overcome resource underutilization, FeLoG employs Round-interleaved Pipeline Parallelism (RiPP), which overlaps sampling in the next round with training in the current one. This design decouples strict sequential execution, allowing CPU-based samplers and GPU-based trainers to operate concurrently across rounds, improving system throughput. Contributions and roadmap. We present FeLoG, a scalable, efﬁcient, end-to-end distributed graph-embedding system, which, to our best knowledge, is the ﬁrst general-purpose system that integrates feedback loop coordination to couple sampling and training. • We propose the feedback-coupled sampling-training model (FeeST) for adaptive sampling based on embedding quality (§5.1). • We develop an activity-aware communication mechanism (ACM), including frequency-aware bitmap compression (FaBC) and hotspotaware synchronization (HaSyn), to reduce intra- and inter-machine communication overheads (§5.2). • We design the round-interleaved pipeline parallelism (RiPP) to overlap sampling and training, improving resource utilization (§5.3). • We demonstrate the generalization of FeLoG, supporting diversity techniques as well as diverse graph types, including purely structural graphs and structure with feature graphs (§5.4 & §6). • We conduct extensive experiments on seven large, real-world and synthetic graphs to demonstrate that FeLoG achieves superior efﬁciency, scalability, and effectiveness over state-of-the-art, popular distributed graph embedding frameworks. Moreover, we are the ﬁrst to exhibit a Graph-based RAG case study using distributed graph embeddings, showcasing FeLoGs integration into a retrievalaugmented generation pipeline (§6).

PRELIMINARIES

Most graph embedding methods use a two-stage pipeline: a sampling stage that extracts node sequences or subgraphs from the input graph, followed by a training stage that learns node embeddings from those samples (Figure 2). The stages run independently, with sampling driven only by the graph structure or previous samples and receiving no feedback from the training process. Sampling process is commonly implemented via truncated walks. Starting from each node, multiple ﬁxed-length walks are performed to explore the local graph structure. Walk directions are determined

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Table 1: Frequently used notations. Notation

Complexity analysis. For random walk-based approaches, assume that the number of walks per node is 𝑟 , walk length 𝐿, embedding dimensions 𝑑, window size 𝑤, and the number of negative samples 𝐾. The time complexity of sampling procedure is O (𝑟 · 𝐿 · |𝑉 |). For training procedure, the corpus size 𝐶 = 𝑟 · 𝐿. Let us denote the complexity of the unit operation of predicting and updating one node’s embedding as 𝑜. The Skip-Gram with the negative sampling only needs 𝐾 + 1 words to obtain a probability distribution (Eq. 2), thus the time complexity of training procedure is O (𝐶 ·𝑤 · (𝐾 +1) ·𝑜). For GNN-based methods, let |N (𝑣)| denote the total number of nodes accessed for message passing for node 𝑣 across all 𝑙 layers (including multi-hop neighbors selected by sampling). The sampling complexity is O(|𝑉 | · |N (𝑣)|), and the training complexity from Eq. 3 (i.e., one forward pass in GNN) is O(|𝑉 | · |N (𝑣)| · 𝑑).

Meaning

𝐺 = (𝑉 , 𝐸 ) Undirected, unweighted graph: 𝑉 nodes and 𝐸 edges 𝜑 (𝑢 ) Embedding of node 𝑢 with dimension 𝑑 N (𝑣) Sampled nodes accessed for message passing of node 𝑣 𝑟 𝑉𝑎 Active nodes in round 𝑟 Ψ(𝑣) Embedding quality of node 𝑣 𝐿 Random walk length 𝑙 𝑙 -th GNN layer 𝑟 Number of random walks per node

based on structural heuristics, such as node degree or common neighbors [21]. To ensure coverage, sampling is repeated across the entire graph. While effective, this process often generates redundant or low-quality information, especially when applied uniformly across all nodes regardless of their structural roles [47]. For GNN-based approaches, the sampling step corresponds to selecting a subset of neighbors for each node at every layer, thereby constructing a smaller computation subgraph for subsequent training. This reduces the input size compared to using the full neighborhood, but redundancy still exists when large neighborhoods are uniformly sampled. Training process typically uses models inspired by natural language processing, such as word2vec [44]. Here, sampled node sequences form a corpus, with nodes as words and their co-occurrences deﬁning context. The Skip-gram model predicts surrounding nodes (context) given a target node (center), learning embedding vectors that capture structural and semantic proximity. Formally, it maximizes the co-occurrence probability within a window 𝑤: argmax 𝑉®

|𝑉 | 1 Õ Õ log 𝑝 (𝑢 𝑗 +𝑖 |𝑢 𝑗 ) |𝑉 | 𝑗 =1 −𝑤 ≤𝑖 ≤𝑤

We analyze existing graph embedding systems from both singlemachine and distributed perspectives, with additional discussions of model-level graph embedding methods provided in Appendix A. Graph embedding algorithms. Graph embeddings [7] have been applied to uncertain graphs [26], dynamic graphs [67], heterogeneous networks [66], retrieval-augmented generation [82], and knowledge graphs [9]. Broadly, recent algorithms fall into two families. GNN-based approaches [25, 58, 59, 63] learn embeddings via iterative message passing and aggregation over sampled neighborhoods, enabling semi-supervised or supervised learning; representative methods include GraphSAGE [25], GAT [59], and GraphGAN [63]. Random-walk-based methods [20, 21, 24, 47] transform graphs into node sequences via random walks and train with SkipGram [44]; e.g., DeepWalk [47] pioneered the idea and node2vec [24] introduced biased walks, while HuGE [20, 21] adapts sampling conﬁgurations on the ﬂy. Despite their differences, both paradigms adopt a sequential, decoupled execution of sampling and training, which can induce redundant sampling and high training overhead, ultimately limiting efﬁciency and scalability [17].

(1)

The generated walks are treated as a corpus with vocabulary 𝑉 , where 𝑢 𝑗+𝑖 denotes a context node in a window 𝑤. Existing methods speed-up training via negative sampling [43]. It adjusts the embeddings such that the target node is close to its true context nodes in the vector space, while the negative samples are pushed farther away. log 𝑝 (𝑢 𝑗 |𝑢 𝑗 +𝑖 ) ≈ log 𝜎 (𝜑𝑖𝑛 (𝑢 𝑗 +𝑖 ) · 𝜑𝑜𝑢𝑡 (𝑢 𝑗 ) ) +

𝐾 Õ 𝑘=1

E𝑢𝑘 ∼𝑃𝑛 (𝑢) [log 𝜎 (−𝜑𝑖𝑛 (𝑢 𝑗 +𝑖 ) · 𝜑𝑜𝑢𝑡 (𝑢𝑘 ) ) ]

Single-Machine Graph Embedding Systems. To overcome efﬁciency bottlenecks in large-scale graph embedding, prior work ranges from full-GPU systems (e.g., GENTI [77], GAMMA [50], and XGNN [55]) that maximize on-device throughput to heterogeneous architectures that address end-to-end bottlenecks. Early systems such as BGL [39] adopt a CPU-GPU hybrid design, with CPUs performing random-walk sampling and GPUs handling embedding training. MariusGNN [60] further optimizes this paradigm with diskefﬁcient pipelines, while Seastar [73] provides a GPU-centric execution framework with a vertex-centric programming model [41]. Recently, NeutronOrch [2] orchestrates computation and communication across devices via runtime scheduling, DAHA [36] adapts hardware assignment based on workload characteristics, and GIDS [45] enables GPU-direct storage access to accelerate data loading. LPS-GNN [14] further scales single-node GNN training via improved partitioning. Despite these advances, single-machine systems still face fundamental scalability limits, primarily due to CPU-GPU imbalance and the constrained GPU memory capacity. Beyond CPUGPU pipelines, several systems leverage specialized hardware to further enhance scalability and efﬁciency. Ginex [46] exploits SSDs to extend memory for large-scale embeddings; SmartSAGE [32]

(2)

Here, 𝜎 (𝑥) = 1+𝑒𝑥𝑝1 (−𝑥 ) is the sigmoid function, and the expectations are computed by drawing random nodes from a sampling distribution 𝑃𝑛(𝑢), ∀𝑢 ∈ 𝑉 . Typically, the number of negative samples 𝐾 is much smaller than |𝑉 | (e.g., 𝐾 ∈ [5, 20]). However, since the training process does not inﬂuence how samples are collected, it cannot correct or avoid redundant or ineffective sampling. For GNN-based methods, the training stage performs iterative message passing and aggregation on the sampled subgraphs. Each node updates its embedding by aggregating the representations of its sampled neighbors through parameterized functions (e.g., mean pooling, attention), followed by non-linear transformations. Formally, the 𝑙-th layer of a GNN is expressed as: (𝑙 ) (𝑙 −1) ℎ 𝑣 = 𝜎 𝑊 (𝑙 ) · AGG {ℎ𝑢 : 𝑢 ∈ N (𝑣) ∪ {𝑣 } }

RELATED WORK

(3)

where ℎ 𝑣(𝑙 ) is the embedding of node 𝑣 at layer 𝑙, N (𝑣) are the sampled neighbors, AGG(·) is a permutation-invariant function, 𝑊 (𝑙 ) is a learnable weight matrix, and 𝜎 (·) is a non-linear activation. 3

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

Table 2: Comparison of distributed graph embedding systems. Coupling

Commun.

Pipeline

DistDGL [85] PBG [33] ByteGNN [84] DistGER [17] LeapGNN [13] NeutronHeter [8] NeutronTP [3]

7 7 7 3 7 7 7

3 7 3 7 3 3 3

7 7 7 7 7 7 7

Partial 7 3 Partial 3 3 3

7 7 7 Partial 7 Partial 7

FeLoG (ours)

Kernel Density

GNN

2 0

0.5

1.0 Emb-5 Emb-6

and AWB-GCN [22] design hardware-conscious scheduling strategies for GNN workloads; BeaconGNN [69] incorporates hardware accelerators for higher throughput; and the very recent OMeGa [19] utilizes heterogeneous memory processing to deliver high-performance embedding at scale. While these systems train on larger datasets, they often sacriﬁce generalizability and face compatibility challenges across diverse heterogeneous environments. Distributed Graph Embedding Systems. To scale graph embeddings, distributed systems have been developed to leverage multimachine and multi-GPU clusters [51, 86]. MSPipe [53] accelerates memory-based temporal GNN training on multi-GPUs via stalenessaware pipeline scheduling. GraNNDis [54] accelerates distributed GNN training on multi-server clusters by reducing inter-server communication, redundant computation, and sampling-induced inefﬁciency. Amazons DistDGL [85] extends the Deep Graph Library [64] with distributed GNN training via mini-batch execution. Similarly, PyTorch-BigGraph [33] scales embedding training to large graphs using graph partitioning and parameter servers. However, both face communication bottlenecks that limit GPU utilization and scalability (§6). Recent works enhance distributed efﬁciency via improved scheduling and communication. ByteGNN [84] employs two-level scheduling and tailored graph partitioning to improve parallelism. DistGER [17] and DistGER-Pipe [18] adopt informationoriented random walks to reduce redundant sampling and communication. LeapGNN [13] proposes a feature-centric distributed GNN training framework to optimize feature access and communication. However, these systems largely suffer from decoupled execution and high transfer overheads under heterogeneous clusters. NeutronHeter [8] accelerates GNN training through hierarchical workload mapping and adaptive communication, while NeutronTP [3] optimizes tensor parallelism for GNNs by improving communication and memory usage. However, NeutronTP applies uniform processing across all node features and lacks feedback-driven embedding evaluation, leading to redundant computation and slower convergence compared to FeLoG (§6). Table 2 compares representative distributed graph embedding systems across two techniques: random walk-based (RW) and GNN-based embeddings (GNN), along with three system-level dimensions: sampling-training coupling (Coupling), communication optimization (Commun.), and pipeline optimization (Pipeline). Existing systems address only a subset, while FeLoG uniﬁes all embedding paradigms with comprehensive systemlevel optimizations.

0.0

0.5

1.0 Emb-9 Emb-10

0.0

0.5

0 4

1.0 Emb-6 Emb-7

0.5

1.0

Node Similarity

0.0

0.5

1.0 Emb-10 Emb-11

0.0

0.5

0 4

1.0 Emb-7 Emb-8

0.5

1.0

Node Similarity

Emb-4 Emb-5

0.0

0.5

1.0 Emb-8 Emb-9

2 0.0

0.5

1.0 Emb-11 Emb-12

2 0.0

4 2

2 0.0

Emb-3 Emb-4

4 2

2 0

Emb-2 Emb-3

4 2

Kernel Density

Emb-1 Emb-2

Kernel Density

System

0.0

0.5

1.0 Emb-12 Emb-13

2 0.0

0.5

1.0

Node Similarity

0.0

0.5

1.0

Node Similarity

Figure 3: Kernel density distribution of node embedding similarity across different sampling-training rounds on Flickr graph. Each subplot compares the similarity distributions of embeddings from round 𝑖 (red) and round 𝑖 + 1 (blue). The xaxis represents cosine similarity, the y-axis represents density. sampling-training paradigm and identify system-level bottlenecks that hinder efﬁciency and scalability in distributed settings.

4.1

Limitations of the Sampling-Training Decoupled Paradigm

Despite efforts to improve sampling quality, existing graph embedding methods still operate under the decoupled sampling-training paradigm, limiting efﬁciency and scalability on large graphs. For example, node2vec [24] uses ﬁxed conﬁgurations for biased random walks (e.g., walk length 𝐿 = 80, 𝑟 = 10 random walks per node), effective for smaller graphs but generating redundant walks for large-scale graphs. To address this, HuGE [21] introduces an information-theoretic random walk mechanism that adaptively determines walk conﬁgurations. While reducing redundancy, it still adheres to a sequential, decoupled sampling-training design, resulting in slow training times. For instance, processing a billion-edge Twitter graph [31] takes over a week on a modern server. The most recent system, DistGER [17], extends HuGE with incremental informationcentric computation in distributed environments, but still evaluates the quality of sampled information solely based on historical statistics, leading to redundancy in sampling. In our observation, DistGER spends over 50% of its total execution time on sampling, with training contributing only 27%, demonstrating inefﬁciency in the decoupled execution paradigm. We evaluate whether heuristic-driven sampling strategies like HuGE and DistGER effectively capture informative data without redundancy. Using the Flickr graph [56] and following the default conﬁguration of DistGER, which heuristically determines the 𝑟 by comparing the distribution of node occurrences in sampled walks with the node degree distribution. In our experiment the sampling procedure terminated after 12 rounds. After each sampling-training round, we compute the pairwise cosine similarity of node embeddings and use kernel density estimation [71] to obtain the distribution of these similarity values. Figure 3 visualizes how these distributions evolve, where each subplot compares consecutive rounds. We observe that the distributions converge around the 6th round, with minimal changes in subsequent rounds. This indicates that the remaining sampling rounds introduce little additional contribution,

MOTIVATIONS

To motivate our proposed scalable and efﬁcient distributed graphembedding system, we ﬁrst analyze the limitations of the decoupled 4

0 Flickr

Youtube LiveJournal ComOrkut

Twitter

(a) Runtime Breakdown

CPU

GPU

80 60 40

AVG: 25.5%

AVG: 15.8%

20 0 0

Data Loading

Training

Sampling

Data Transfer Communication

-2

FeeST

-3

-4

-5

-6

Iteration Rounds (r)

(a) CPU/GPU Utilization Training Synchronization

w/o-FeeST 10

Running Time (seconds)

Gradient Variance

100

Number of Active Nodes

Computations

Utilization (%)

Communications 100

Running Time (seconds)

Time Overhead Ratio (%)

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

(b) Active Nodes

Iteration Rounds (r)

Embedding

Figure 5: Resource utilization in decoupled sampling-training, and active nodes and gradient variance on YouTube graph.

Persistence

(b) Communication Type

Figure 4: Analysis of communication overheads.

demonstrating redundancy in both computation and communication. Current methods make sampling decisions based on structural heuristics or historical statistics, which are indirect proxies for representation quality and do not reveal whether the samples are effectively utilized. A mechanism is needed to identify converged nodes and those that remain undertrained, enabling efﬁcient sampling. Without runtime feedback, samplers continue redundant exploration. This highlights the importance of training feedback for eliminating redundancy and enabling efﬁcient, scalable graph embedding.

Decoupled Execution of Sampling and Training. In DistGER, sampling and training follow the sampling-training decoupled paradigm and are separated by a round-level barrier: training cannot begin until sampling fully completes and materializes the node sequences for the current round. Once sampling ﬁnishes, the resulting node sequences are passed to the training stage as input. To ensure fault tolerance, DistGER checkpoints the sampled data to storage before launching training, introducing additional I/O overhead. As a result, sampling and checkpointing phase lies on the critical path; any imbalance or delay in sampling directly stalls GPU execution, creating bubbles in the end-to-end pipeline. Figure 5(a) shows that CPU and GPU are signiﬁcantly underutilized on the YouTube graph, with average utilizations of only 15.8% and 25.5%, respectively.

4.2

System-Level Bottlenecks in Distributed Graph Embedding

FeLoG

To address the challenges from sampling-training decoupled paradigm and system-level bottlenecks, we design FeLoG, a scalable and efﬁcient distributed graph embedding system that integrates feedback loop coordination to couple sampling and training. Figure 6 summarizes the workﬂow of FeLoG. We discuss our feedbackcoupled sampling-training model (FeeST) in §5.1, and activity-aware communication mechanism (ACM) in §5.2, including the frequencyaware bitmap compression strategy (FBC) and the hotspot-aware synchronization strategy (HaSyn), while our novel round-interleaved pipeline (RiPP) is given in §5.3. Finally, we present how FeLoG can be integrated into existing graph embedding frameworks in §5.4.

To address scalability challenges, existing graph embedding systems have been extended to distributed settings and CPU-GPU heterogeneous architectures. In these systems, sampling is typically executed on CPUs, while training is ofﬂoaded to GPUs. However, such designs still suffer from signiﬁcant system inefﬁciencies. To systematically analyze these bottlenecks, we implemented DistGER on an 8-machine cluster with a CPU-GPU heterogeneous architecture. Data Communication Overhead. We conducted experiments on ﬁve real-world datasets and proﬁled the end-to-end runtime of DistGER, decomposing it into computation (sampling and training) and communication (both intra- and inter-machine). As shown in Figure 4(a), communication dominates the total runtime, accounting for an average of 71%, with its proportion increasing as the dataset size grows. We further analyzed communication costs using the Flickr dataset by categorizing the communication into distinct types (Figure 4(b)). Among them, training synchronization and training data transfer emerge as major performance bottlenecks. During training synchronization, updated embedding gradients must be synchronized across machines over Ethernet to ensure consistency. The communication volume increases linearly with the number of machines. For instance, in our 8-machine setup, synchronizing 128-dimensional embeddings on the Twitter graph using 10 Gbps NICs may introduce up to 4.6 seconds of delay per round, causing communication to dominate the runtime and accounting for 78% of the total execution time. Training data transfer also incurs considerable cost. Since sampling is decoupled from training, all sampled data including redundant neighborhoods must be moved from CPU memory to GPU memory and persisted to storage. This overhead grows proportionally with the size of training data and is constrained by PCIe and I/O bandwidth.

···

··· FaBC Compression

Feedback

FeeST Model

Sampler

Trainer

Machine 1 Ri+1

Ri Ci

Ci+1

Pi+1

Ui+1

Ti+1

RiPP Execution

HaSyn Synchronization

Feedback

FeeST Model

··· Sampler

··· FaBC Compression

Machine 2

Trainer

Figure 6: The workﬂow of FeLoG. 5

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

× 10

Round 1

Round 2

Round r

Sampler

×0

×6

Active Node Set

×4

×3

...

×7

Active Node Set

Embedding Quality Feedback

This approximation is effective because real-world graphs often exhibit redundant local neighborhoods. In many graphs, nodes with similar attributes or roles tend to connect, making neighboring nodes highly correlated [30, 42]; meanwhile, power-law degree distributions create hubs with many overlapping neighbors [5]. Empirical studies on GNNs also suggest that aggregating a small subset of neighbors is often sufﬁcient, while using all neighbors yields diminishing returns but incurs extra overhead [12, 25]. An alternative is to detect convergence via self-stability, i.e., comparing a node’s embedding across consecutive rounds. However, this requires storing historical embeddings, incurring additional 𝑂 (|𝑉 |· 𝑑) memory overhead at scale. More importantly, graph embedding aims to preserve structural and attribute relationships with respect to the original graph. By evaluating consistency with neighbors (Eq. 4), FeeST aligns the feedback signal with this objective. In contrast, self-stability alone can yield false convergence: an embedding may change little across rounds yet remain inconsistent with its neighborhood, providing misleading guidance to the sampler. Finally, training-parameter signals such as gradient magnitudes are not reliable indicators of structural consistency, as they mainly capture within-iteration optimization dynamics and minibatch stochasticity [70, 87], and lack a cross-round structural view for updating the sampling frontier (i.e., the active set). If Ψ(𝑣𝑖 ) < 𝜇, the embedding of 𝑣𝑖 is considered undertrained, and the node will be included in the active node set for the next round of sampling 𝑉𝑎(𝑟 +1) . Otherwise, it is excluded from further sampling. The active node set for round 𝑟 + 1 is formally deﬁned as:

Termination

... Trainer

Trainer Active Node

Inctive Node

Trainer

Training Embedding

Converged Embedding

Figure 7: Feedback-driven sampling-training coupling model.

5.1

Feedback-coupled Sampling-Training Model

Traditional graph embedding pipelines treat sampling and training as separate stages, which often leads to redundant sampling and unnecessary computation on large-scale graphs (§4.1). Existing ﬁxes [17, 21] decide per-node sampling rounds using structural heuristics or historical statistics, yet lack training feedback and may still incur substantial redundancy. To overcome this limitation, we propose the Feedback-coupled Sampling-Training Model (FeeST), which integrates real-time training feedback into sampling. The key idea is to derive a neighborhood-consistency metric from training feedback as a direct proxy for representation quality, so that only undertrained nodes remain active for subsequent sampling. Overview of FeeST. As illustrated in Figure 7, FeeST closes the loop between sampling and training via an active node set. At round 𝑟 , FeeST samples only from active nodes to generate walks or neighborhood subgraphs as training input. After training updates embeddings, FeeST computes the neighborhood-consistency metric to assess representation quality. Nodes that meet the consistency criterion are removed from the active set, while under-trained nodes remain active for the next round. By iteratively shrinking the active set, FeeST dynamically allocates sampling effort where it is still beneﬁcial, reducing redundant exploration and speeding up convergence.

(𝑟 +1)

𝑉𝑎

1 | 𝑁˜ (𝑣𝑖 ) |

˜ (𝑣𝑖 ) 𝑣𝑗 ∈𝑁

𝑣®𝑖 · 𝑣®𝑗 k 𝑣®𝑖 k k 𝑣®𝑗 k

(5)

Empirically, we set the default 𝜇 to 0.65. With this feedback mechanism, FeeST treats active nodes as a round-level operational state rather than a static graph property or homophily-based label category: after each training round, a node remains active if Ψ(𝑣𝑖 ) < 𝜇, indicating that its representation may still beneﬁt from further sampling and training. This helps FeeST identify insufﬁciently stable embeddings, avoiding redundant sampling and computation without sacriﬁcing downstream accuracy (§6). While Eq. 4 is most directly aligned with graphs where local similarity is informative, its scale becomes more dataset-dependent in heterophilic graphs because neighbors may not be semantically similar. Therefore, in heterophilic settings, we treat 𝜇 as a validation-calibrated decision boundary rather than a universally ﬁxed threshold, optionally guided by structural homophily metrics [23, 48]. Speciﬁcally, we calibrate 𝜇 over a small candidate set using only the held-out validation split under the standard 50%/25%/25% split, select the best validation quality-efﬁciency trade-off, and use the test set only for ﬁnal reporting. As shown in Figure 5(b), the number of active nodes decreases rapidly during the early rounds on the YouTube graph. This observation aligns with the power-law distribution commonly found in real-world graphs, where most nodes have a low degree. These lowdegree nodes become sufﬁciently trained quickly due to sparse connectivity and limited information content, while high-degree nodes require more rounds of sampling to capture their neighborhood context. This validates that FeeST eliminates redundant exploration from the early rounds, unlike decoupled paradigms where all nodes continue to be sampled regardless of representation quality. Importantly,

Feedback Mechanism. Graph embedding aims to preserve node attributes and graph structure in a low-dimensional space, such that nodes that are proximate or structurally related in the original graph remain similar in the embedding space. We therefore use embedding similarity with neighbors as a feedback signal to assess representation quality. Speciﬁcally, for a node 𝑣𝑖 , if its embedding is sufﬁciently consistent with those of its neighbors, we treat 𝑣𝑖 as welltrained and exclude it from future sampling rounds. We quantify this neighborhood-consistency as the average cosine similarity between 𝑣𝑖 and its neighbors. Let 𝑁 (𝑣𝑖 ) represent the set of neighbors of node 𝑣𝑖 , and 𝜇 be a predeﬁned similarity parameter. To mitigate the computational overhead of computing similarities for pair-wise nodes, FeeST adopts a neighbor subsampling strategy. Instead of evaluating similarities across the entire neighborhood, we estimate the neighborhood-consistency score Ψ(𝑣𝑖 ) using a sampled subset 𝑁˜ (𝑣𝑖 ) ⊆ 𝑁 (𝑣𝑖 ): Ψ(𝑣𝑖 ) ≈

o n (𝑟 ) Ψ(𝑣𝑖 ) < 𝜇 = 𝑣𝑖 ∈ 𝑉𝑎

(4) 6

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

the active frontier is recomputed every round, enabling nodes to be reactivated when they become inconsistent with their neighborhoods. Inactive nodes may still be revisited through random walks or neighbor aggregation, allowing their embeddings to keep evolving. On the ComOrkut graph, we observe that 6.4% of nodes are reactivated per round on average. Moreover, Figure 5(c) shows that although FeeST starts pruning from the ﬁrst round and rapidly shrinks the active frontier, its gradient variance remains comparable to w/oFeeST in the ﬁrst few rounds and becomes consistently lower afterward, suggesting that the induced non-stationary sampling does not introduce harmful optimization instability in practice.

Graph Data

Machine n

Generated Embeddings

… Machine 2

Storage

Sub-Graph

Storage

Generated Walk Paths

Generated Embeddings

Sub-Graph

Generated Walk Paths

Generated Embeddings

Figure 8: Data ﬂow in the feedback-coupled sampling-training.

Implementation. Algorithm 1 presents the workﬂow of FeeST, which iteratively performs sampling, training, and feedback until the active node set becomes empty. To ensure generalizability, FeeST abstracts both sampling and training through model-agnostic interfaces. The Sample(𝑣𝑖 , 𝜃 ) → 𝑊𝑣𝐿𝑖 function generates either randomwalk sequences (e.g., DeepWalk, node2vec, HuGE) or GNN-based neighborhood subgraphs with conﬁgurable fan-out, where 𝑣𝑖 is the source node, 𝜃 denotes conﬁgurable parameters such as walk bias or neighbor budget, and 𝑊𝑣𝐿𝑖 is the resulting walk or subgraph. The Train(𝑊𝑣𝐿𝑖 , 𝑚𝑜𝑑𝑒𝑙) → 𝑉® function then consumes these samples to update embeddings using the corresponding model, such as SkipGram with negative sampling for random walks, or message passing and aggregation for GNNs. This uniﬁed abstraction allows FeeST to plug feedback into different embedding pipelines (details in §5.4).

5.2

Activity-aware Communication Mechanism

In large-scale graph embedding systems, efﬁcient communication is essential to overcome the bottlenecks introduced by both intramachine sampling-training transmission and inter-machine embedding synchronization. As observed in § 4.2, communication overhead, particularly between the CPU and GPU, as well as across distributed machines, comprises a signiﬁcant portion of the overall execution time (up to 78%), leading to low resource utilization and scalability issues. To address these challenges, we propose an activity-aware communication mechanism (ACM), which encompasses a frequency-aware bitmap compression strategy (FaBC) to alleviate PCIe bandwidth pressure and a hotspot-aware synchronization strategy (HaSyn) to reduce network trafﬁc.

Complexity Analysis. The computational complexity can be interpreted directly from the following phases: Sampling (line 3). Let 𝑉𝑎𝑟 denote the active node set in round 𝑟 , for each active node 𝑣𝑖 ∈ 𝑉𝑎𝑟 , the Sample function generates a walk or subgraph of average length 𝐿. The cost is 𝑂 (|𝑉𝑎𝑟 | · 𝐿). Training (line 4). Embeddings are updated on the collected samples. With walk length 𝐿, window size 𝑤, and embedding dimension 𝑑, the training cost is 𝑂 (|𝑉𝑎𝑟 | ·𝐿 ·𝑤 ·𝑑). Feedback (lines 5-6). For each active node, FeeST computes the neighborhood-consistency score Ψ(𝑣𝑖 ) using a subsampled neighborhood 𝑁˜ (𝑣𝑖 ) of size 𝑘¯𝑠 , costing 𝑂 (|𝑉𝑎𝑟 |·𝑘¯𝑠 ·𝑑). Since |𝑉𝑎𝑟 | shrinks across rounds Í as sufﬁciently trained nodes are removed, the total runtime is 𝑂 𝑅 |𝑉 𝑟 | · (𝐿 · 𝑤 · 𝑑 + 𝑘¯𝑠 · 𝑑) , which can be 𝑟 =1

Generated Walk Paths

Machine 1

5.2.1 Analysis of Data Flow in FeeST. As shown in Figure 8, the communication process can be summarized in the following stages: (1) Graph data loading and distribution: Raw graph data is read from storage into CPU memory and partitioned across worker nodes (red arrows). (2) Sampling and path generation: Each worker performs random walks on its local subgraph, and path fragments are exchanged if walks cross partitions. The generated walk paths are then aggregated for training (green arrows). (3) CPU-GPU transfer for training: Aggregated sequences are transmitted from CPU to GPU memory as training input. This PCIe transfer grows with the volume of samples and often emerges as a major bottleneck (green arrows). (4) Distributed synchronization: During training, updated gradients or embeddings are copied from GPU to CPU, aggregated across machines, and written back to GPUs for parameter updates. This synchronization dominates communication costs in distributed environments (blue arrows). (5) Persistence: After convergence, ﬁnal embeddings are transferred back to CPU memory and persisted to storage (blue arrows). In addition, generated walk paths are periodically checkpointed for reproducibility and recovery purposes (green arrows). Among these stages, (3) CPU–GPU transfer and (4) distributed synchronization are the two dominant bottlenecks during communication, which motivate the design of FaBC and HaSyn.

𝑎

substantially smaller than the decoupled baseline that repeatedly samples and trains over all nodes. The space complexity is dominated by embeddings 𝑂 (|𝑉 | ·𝑑) at the current round, with temporary memory 𝑂 (max𝑟 |𝑉𝑎𝑟 | · (𝐿 + 𝑘¯𝑠 )) for sampled walks and neighbor subsets. Algorithm 1 Feedback-driven Sampling-Training Coupling Input: Graph 𝐺 = (𝑉 , 𝐸 ), embedding dimension 𝑑, parameter 𝜇 Output: Node embeddings 𝑉® 1: Initialize active node set 𝑉𝑎 ← 𝑉 2: while 𝑉𝑎 ≠ ∅ do 3: Sampling: For each 𝑣𝑖 ∈ 𝑉𝑎 , generate samples 𝑊𝑣𝐿𝑖 ← Sample(𝑣𝑖 , 𝜃 ) 4: Training: Update embeddings 𝑉® ← Train(𝑊𝑣𝐿𝑖 , 𝑀𝑜𝑑𝑒𝑙 ) 5: Feedback: For each 𝑣𝑖 ∈ 𝑉𝑎 , evaluate embedding quality Ψ(𝑣𝑖 ) 6: Form next active set 𝑉𝑎next = {𝑣𝑖 ∈ 𝑉𝑎 | Ψ(𝑣𝑖 ) < 𝜇 } 7: 𝑉𝑎 ← 𝑉𝑎next 8: return 𝑉®

5.2.2 Frequency-aware Bitmap Compression Strategy. In graph embedding systems, sampling generate node sequences or subgraphs as training input. Due to the skewed degree distribution in realworld graphs, high-degree nodes tend to be revisited more frequently, and random walks are more likely to repeatedly traverse their local neighborhoods [20, 35]. Existing strategies (e.g., biased transitions in node2vec or backtracking in HuGE) exacerbate this issue 7

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

Top-1 Fre uency Top-2 Fre uency

Top-3 Fre uency Top-4 Fre uency

Fitting Curve

Fre uency Ratio

0.7

FaBC Compression Bitmap Array

Array Format

0 10 1 1 0 1 1 0 01 1 1 01 0 0 0 0 0 1 00 0

Fre uency

103

0.6

102

0.5

0 01 1 0 1 0 1 1 10 0 1 00 0 1 0 1 0 0 01 0

N 80%

0.4 0

Generated Walks

Embedding %ector updates Node occurrences in walk path

104

20%

···

··· 0 10 0 1 0 1 1 0 01 0 1 01 0 0 0 0 0 1 00 1

101 10000

20000

30000

40000

Generated Walk Path ID

(a) Node Occurrences

50000

1000 2000 3000 4000 5000 6000 7000

Node Id (Descending order)

L/8 bytes

(b) Embedding Updates

Figure 9: Distribution characteristics of node occurrences and embedding updates.

Figure 10: Frequency-aware compression process.

by favoring repeated exploration of local neighborhoods. As a result, sampled paths or subgraphs contain many duplicate node occurrences that must be transferred from CPU to GPU for training, imposing substantial PCIe bandwidth overhead. However, existing systems typically materialize samples as plain arrays of node IDs, which fails to exploit this repetition. Since redundancy is dominated by a small set of frequent nodes, encoding their occurrence patterns with compact bitmap representations [11] is often far more efﬁcient than repeatedly sending the same identiﬁers. We propose the Frequency-aware Bitmap Compression (FaBC) strategy, which identiﬁes high-frequency nodes and records their positions as compact bitmaps, turning repeated identities into lightweight markers for CPU-GPU transfer. Unlike prior bitmap techniques that mainly target static bitvectors or graph adjacencies, FaBC is workload-driven and tailored to the highly repetitive access patterns in sampling-generated walk paths, and is co-designed with FeLoG’s workﬂow to reduce the dominant transfer bottleneck. While ﬁner-grained frequency buckets can improve compression, they also introduce extra bitmap construction and decoding overhead. FaBC therefore selects a small number of buckets (or ranges) based on the observed node-frequency distribution to balance compression effectiveness and runtime cost. To this end, FaBC determines the compression range by proﬁling the node-frequency distribution in the ﬁrst sampling–training round. After the initial sampling, we compute normalized node frequencies on the sampled sequences and sort them as 𝑝 (1) ≥ 𝑝 (2) ≥ · · ·. We deﬁne the cumulative frequency of the top-𝑘 nodes as 𝐹𝑘 = Í𝑘 𝑖=1 𝑝 (𝑖). Under FaBC, selecting the top-𝑘 nodes compresses their repeated occurrences into per-sequence bitmaps and stores the remaining (infrequent) nodes in the original ID form. For 𝑁 sequences with average length 𝐿, the baseline storage is 𝑆 0 = 4𝑁 𝐿 bytes (4 bytes per node ID). After compressing the top-𝑘 nodes, the uncompressed tail accounts for a (1 − 𝐹𝑘 ) fraction of positions and costs 4𝑁 𝐿(1 − 𝐹𝑘 ). We store the 𝑘 selected node IDs once per sequence, costing 4𝑁𝑘, and store one length-𝐿 bitmap per selected node per sequence, costing 𝑁𝑘 · (𝐿/8) bytes. Thus, the compressed size is

FaBC expands the compression target set only when the (𝑘+1)1 th node provides sufﬁcient marginal beneﬁt. Let 𝑐 = 𝐿1 + 32 denote the amortized overhead of adding one more compressed node, so 𝑔(𝑘) = 1 − 𝐹𝑘 + 𝑘𝑐. Since 𝐹𝑘+1 = 𝐹𝑘 + 𝑝 (𝑘+1), we have 𝑔(𝑘+1) = 𝑔(𝑘) − 𝑝 (𝑘+1) + 𝑐, To avoid diminishing returns, FaBC selects the largest 𝑘 satisfying

𝑆 (𝑘) = 4𝑁 𝐿(1 − 𝐹𝑘 ) + 4𝑁𝑘 + 𝑁𝑘

𝐿 8

𝑔(𝑘) − 𝑔(𝑘+1) ≥ 0.1 𝑔(𝑘)

𝑘 𝑘 𝑆 (𝑘) = 1 − 𝐹𝑘 + + 𝑆0 𝐿 32

𝑝 (𝑘+1) ≥ 𝑐 + 0.1𝑔(𝑘)

(8)

which requires the marginal reduction to be at least 10% of the current ratio. The selected top-𝑘 nodes are then used as compression targets, and their occurrences are encoded with bitmaps in subsequent samples. In practice, the frequency proﬁle is largely stable under ﬁxed sampling parameters, so the conﬁguration can be reused without repeated analysis; if needed, FaBC can refresh the proﬁle periodically with low overhead. Example. Figure 9(a) illustrates the node frequency curve of walks generated by FeeST on the YouTube graph. The top-1 and top2 nodes together contribute over 50% of the total frequency. Including the third most frequent node increases the cumulative frequency by less than 10%, and adding the fourth brings only marginal improvement. Hence, according to the above criterion, FaBC selects the top-1 and top-2 nodes as compression targets. This demonstrates how the adaptive rule captures dominant redundancy without extra bitmaps. The impact of different frequency ranges on compression ratio is further evaluated in Table 6. As illustrated in Figure 10, FaBC achieves notable compression. In a set of 𝑁 random walks with average length 𝐿, storing nodes as 4-byte unsigned integers results in a raw size of 4𝑁 𝐿 bytes. After compression, the positions of the top-𝑘 frequent nodes are stored using 𝑘 bitmaps of length 𝑁 , while the remaining nodes are stored as an ID stream. Let 𝐿𝑐 denote the average length of the remaining sequence. From Figure 9(a), when the top-2 nodes cover approximately 60% of the walk content, we have 𝐿𝑐 ≈ 0.4𝐿. There𝐿 fore, the compressed data size is approximately 𝑘 ·𝑁 + 4𝑁 𝐿𝑐 ≈ 8 0.25𝑁 𝐿 + 1.6𝑁 𝐿 bytes, which signiﬁcantly reduces the training data size while incurring minimal computational overhead (details in 6.6).

(6)

5.2.3 Hotspot-aware Synchronization Strategy. Synchronization of embedding vectors is a critical factor inﬂuencing both accuracy and system performance in distributed training. Existing methods such as parameter-server based designs (e.g., PBG [33] and NuPS [51]) and optimized communication topologies (e.g., TidalMesh [38]) improve efﬁciency, but they typically treat all embeddings equally, ignoring the skewed update activity across nodes. In real-world

and the compression ratio is 𝑔(𝑘) =

⇐⇒

(7)

Here, 1 − 𝐹𝑘 is the fraction of positions that remain uncompressed, 𝑘 𝐿 corresponds to storing the 𝑘 selected IDs once per sequence, and 𝑘 32 is the bitmap overhead (1 bit per position). 8

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Update Hotness

Machine 1 B1 B2

Machine 2

5.3

Machine n

While FeLoG improves end-to-end efﬁciency via the FeeST model (§5.1) and the ACM mechanism (§5.2), its execution still remains round-synchronous and decoupled between sampling and training. As discussed in §4.2, training starts only after sampling for the current round is fully completed and materialized, which limits CPUGPU concurrency and leads to low utilization leading to a low average utilization ratio (less than 26%).

···

··· ···

Bn Hotspot Blocks

Hotspot Embeddings

Synchronized Block

Round-interleaved Pipeline Parallelism

Execution Analysis of FeLoG Components. Figure 12(a) depicts the decoupled execution mode of FeLoG, where in each round the training phase is launched only after the sampling phase ﬁnishes completely. Furthermore, there exists an intermediate phase, corpus management, between sampling and training. This includes: (1) the compression and decompression of walk paths using FaBC, as introduced in §5.2.2, and (2) checkpointing the sampled data to persistent storage for fault tolerance. Speciﬁcally, after each round of sampling, the system performs compression on the CPU. This step signiﬁcantly reduces the size of the walk paths by identifying and encoding high-frequency nodes via compact bitmap indices, thereby lowering the PCIe transmission load from CPU to GPU. The compressed walk sequences are then serialized and checkpointed to persistent storage to ensure fault tolerance. Later, during training, the decompression is executed on the GPU side. The GPU ﬁrst transfers the compressed sequences into its memory, then reconstructs the original node sequences by decoding the bitmap and reassembling the full walk paths. Afterwards, the updated embeddings are synchronized across machines by the hotspot-aware strategy (§5.2.3). Because sampling and training are separated by round-level barriers and corpus materialization, both CPU and GPU can be idle around these intermediate steps, resulting in poor overall resource utilization.

Figure 11: Hotspot-aware Synchronization Strategy across distributed machines.

graphs, the sampling workload is highly skewed, and a small set of high-frequency nodes appears far more often in sampled sequences, leading to disproportionately more embedding updates. As shown in Figure 9(b), more than 80% of updates on the Wiki-Vote graph [34] are concentrated on a small set of high-frequency nodes, while the majority of embeddings are rarely updated. This makes uniform full-model synchronization inefﬁcient, as most bandwidth is wasted transmitting nearly static vectors, motivating hotness-aware selective synchronization that prioritizes frequently updated embedding. To address this issue, we propose the Hotspot-aware Synchronization Strategy (HaSyn), which dynamically adjusts the synchronization frequency of embedding vectors based on their update hotness. As illustrated in Figure 11, during the initialization phase, the embedding matrix is constructed by sorting nodes in descending order of their frequencies observed in the training data, where the frequency statistics are collected asynchronously during sampling by a background thread. During synchronization, we partition 𝑉® into hotspot blocks 𝐵 𝑓 = {𝑣 | 𝑓 (𝑣) = 𝑓 } indexed by distinct frequency values 𝑓 ∈ F , yielding |F | blocks in total, and randomly select one node from each block 𝐵 𝑓 to form a synchronization set of size |F |. Due to the skewed frequency distribution, a node in block 𝐵 𝑓 is selected with probability 1/|𝐵 𝑓 |, making hot embeddings (typically in smaller blocks) more likely to be synchronized, while cold embeddings are synchronized less frequently. Thus, HaSyn avoids repeated global graph analysis or full re-ranking in each synchronization period, and maintaining the synchronization set only requires lightweight block-level lookup/update operations. Compared to full-model synchronization, the communication cost of HaSyn is reduced to O (|F | · 𝑑 · 𝑀), where 𝑑 is the embedding dimension and 𝑀 is the number of machines, with |F | |𝑉 | in practice (details in §6.6). Furthermore, under FeeST (§5.1), the active frontier shrinks across rounds, so update activity concentrates on a progressively smaller subset of embeddings and shifts over time. HaSyn therefore prioritizes embeddings with high update frequency and adapts to crossround workload shifts, reducing inter-machine synchronization volume while avoiding indeﬁnite staleness through periodic synchronization of cold embeddings. As a lightweight hotspot-based strategy, HaSyn is most effective when update activity is skewed; under nearly uniform updates or stricter consistency requirements, more sophisticated graph partitioning and adaptive synchronization techniques can be complementary to FeLoG. We analyze the resulting quality-efﬁciency trade-off of selective synchronization in §6.6.

Pipeline Execution Design. To overcome the limitations of decoupled execution, FeLoG introduces a round-interleaved pipeline parallelism (RiPP) to fully exploit the parallelism of heterogeneous systems and reduce idle time. The core idea of RiPP is to analyze the data dependencies across the sampling and training phases, decouple their operators into ﬁne-grained execution units, and schedule them in an interleaved, round-wise pipeline to maximize concurrency. As illustrated in Figure 12(b), each sampling-training round in FeLoG is decomposed into six operators: random walk generation (𝑅), data compression (𝐶), checkpointing (𝑃), data decompression (𝐷), model training (𝑇 ), and synchronization (𝑆). For instance, 𝑅𝑖 denotes the random walk generation operator in round 𝑖, and 𝑇𝑖 corresponds to the associated training operator that consumes the walk corpus. Unlike DistGER-Pipe [18], which overlaps sampling and training in a decoupled CPU-only pipeline driven by pre-deﬁned graph-structural signals, RiPP targets feedback-coupled CPU-GPU execution in FeLoG. Speciﬁcally, the sampling frontier of round 𝑖 + 1 depends on the embedding-quality feedback produced after training round 𝑖, so 𝑅𝑖+1 must preserve this one-round feedback dependency rather than being launched independently of 𝑇𝑖 . This feedback dependency also differentiates RiPP from general GNN pipeline schedulers such as NeutronOrch [2], DAHA [36], and LeapGNN [13], which mainly optimize execution scheduling without modeling FeeST’s round-level embedding-quality feedback. 9

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

where Sample generates walks such as uniform walks in DeepWalk, second-order walks in node2vec, or biased walks toward informative neighbors in HuGE/DistGER; (2) GNN systems, where Sample extracts subgraphs with conﬁgurable fan-out for message passing. Within FeLoG, the Sample stage is enhanced by two mechanisms: FeeST dynamically updates the active node sets to avoid redundant walks, and FaBC compresses generated sequences to reduce CPU-GPU transmission. Train Interface. The training process is abstracted as Train(𝑊𝑣𝐿𝑖 , 𝑚𝑜𝑑𝑒𝑙, 𝑓 𝑒𝑒𝑑𝑏𝑎𝑐𝑘 = 𝑇𝑟𝑢𝑒) → 𝑉® , where 𝑊𝑣𝐿𝑖 denotes the sampled corpus, model is the embedding architecture, and 𝑉® is the resulting embedding matrix. For random walk systems, this corresponds to Skip-Gram with negative sampling (Eq. 1, Eq. 2), while for GNN systems it corresponds to iterative message passing and aggregation (Eq. 3). FeLoG integrates feedback directly into this step: after each update, FeeST evaluates embedding quality and prunes converged nodes, while HaSyn adaptively synchronizes high-frequency embeddings across machines to reduce network costs. In GNNs, FaBC can be reused to compact redundant neighbor lists, and HaSyn applies to hotspot embedding vectors arising from skewed node access. Uniﬁed Deployment View. From a system perspective, the deployment of FeLoG can be summarized as:

Corpus Management Ri-1

Ci-1

Pi-1

Di-1 Ti-1 Si-1

Ri+1

Ci+1 Pi+1 Di+1 …Ti+1 Si+1

Time

(a) Decoupled Execution …

Ri-1 … …

Ri Ci-1

Ri+1 Ci

Ti-1 Si-1 Di

Pi-1

…

Pi+1 Si

R Random Walk

T Training

C Compression

P Checkpointing

… … D Decompression S Synchronization

Time

(b) Round-interleaved Pipeline Execution

Figure 12: Execution ﬂow comparison in FeLoG. To maximize concurrency under this feedback dependency, RiPP adopts a three-group operator scheduling strategy. It groups and dispatches: Ê CPU-side random walk generation (𝑅), Ë CPU-side data compression (𝐶) and checkpointing (𝑃), and Ì GPU-side data decompression (𝐷), model training (𝑇 ), and synchronization (𝑆) into three asynchronous operator pipelines, each mapped to the most appropriate hardware resources. These operators form a hybrid parallelism scheme: intra-round serial execution for dependent operators on the same data chunk, and inter-round parallel execution across different threads and devices whenever their dependencies are satisﬁed. For example, once walk chunks of round 𝑖 are generated on the CPU, 𝐶𝑖 and 𝑃𝑖 proceed on CPU-side threads, while ready chunks from adjacent rounds are decompressed, trained, and synchronized on the GPU. Under RiPP, active-frontier construction is separated from random-walk generation. After 𝑇𝑖 −1 , each machine computes Ψ(𝑣) for its local candidate nodes using the locally visible embedding snapshot, which contains local training updates and previously synchronized remote embeddings. Each machine then materializes its local portion of 𝑉𝑎(𝑖 ) , allowing 𝑅𝑖 to start without waiting for the current synchronization 𝑆𝑖 −1 to complete. This use of locally visible or slightly stale embeddings follows common distributed graph learning practice [4, 61, 85]. Once 𝑉𝑎(𝑖 ) is ﬁxed, 𝑅𝑖 no longer computes Ψ(𝑣) or accesses embeddings, but only performs graph-structure-based walk generation from active nodes. Thus, 𝑅𝑖 can overlap with 𝑆𝑖 −1 , which asynchronously propagates previousround embedding updates for subsequent training and later activefrontier construction. This design keeps CPU and GPU resources continuously utilized while preserving the feedback dependency required by FeeST, thereby improving end-to-end training efﬁciency.

5.4

S = Sample(𝐺, 𝜃 )

(FeeST + FaBC)

𝑉® = Train(𝑆, 𝑚𝑜𝑑𝑒𝑙, 𝑓 𝑒𝑒𝑑𝑏𝑎𝑐𝑘 = 𝑇 𝑟𝑢𝑒 )

(FeeST + HaSyn)

Persist(𝑆, 𝑉® ) RiPP( {𝑆𝑎𝑚𝑝𝑙𝑒,𝑇 𝑟𝑎𝑖𝑛, 𝑃𝑒𝑟𝑠𝑖𝑠𝑡 } )

(Pipeline execution)

This API-style abstraction emphasizes that FeLoG is not a standalone framework, but a modular optimization layer that can be embedded into both CPU-GPU and multi-machine distributed environments. In random-walk frameworks such as DistGER, all three mechanisms (FeeST, FaBC, HaSyn) are integrated together with pipeline execution (RiPP). In GNN frameworks, FeLoG mainly leverages (FeeST) and can extend FaBC and HaSyn to reduce neighbor redundancy and hotspot synchronization. Our experiments in §6 demonstrate the end-to-end beneﬁts of this integration when applied to DistGER, while also validating its extensibility to GNN-based systems such as DistDGL and NeutronTP.

Integration of FeLoG with Existing Systems

Modern graph embedding frameworks can be broadly classiﬁed into two categories: random walk-based systems (e.g., DeepWalk [47], node2vec [24], HuGE [21], DistGER [17]) and GNN-based systems (e.g., GraphSAGE [25], DistDGL [85], NeutronTP [3]). FeLoG is designed as a lightweight optimization layer that can be seamlessly incorporated into both paradigms through two uniﬁed interfaces, Sample and Train. This abstraction decouples state-of-the-art embedding models from our proposed feedback loop, enabling systemlevel integration without modifying the core model design. Sample Interface. The sampling process is abstracted as Sample(𝑣𝑖 , 𝜃 ) → 𝑊𝑣𝐿𝑖 , where 𝑣𝑖 is the source node, 𝜃 denotes model-speciﬁc parameters (e.g., bias factor, neighbor budget, entropy criterion), and 𝑊𝑣𝐿𝑖 is either a node sequence or a neighborhood subgraph of length 𝐿. This uniﬁed form supports: (1) Random-walk systems,

EXPERIMENTAL RESULTS

We evaluate the efﬁciency (§6.2) and scalability (§6.3) of our proposed method, FeLoG by comparing with PyTorch-BigGraph (PBG) [33], Distributed DGL (DistDGL) [85], DistGER [17], DistGERPipe [18], LeapGNN [13], and NeutronTP [3]. We also compare the effectiveness (§6.4) of generated embeddings on link prediction, graph-based RAG, and node classiﬁcation. Finally, we analyze the generalizability of FeLoG for the GNN-based embeddings (§6.5) and efﬁciency due to individual parts of FeLoG (§6.6). Our codes and datasets are at [1].

6.1

Experimental Setup

Environment. We conduct experiments on a cluster of 8 machines, each equipped with a 2.60GHz Intel® Xeon® Gold 6240 CPU (36 cores with 72 threads), a 32GB NVIDIA V100 GPU, 192GB DDR4 memory, and interconnected via full-duplex 10 Gbps networking. 10

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Graph

Datasets statistics #Nodes

FL YT LJ OR TW OGB UK

End-to-end Running Time (second)

Table 3: Datasets statistics (𝐾=103, 𝑀=106, 𝐵=109 ) and Avg. memory footprint (GB) per machine. “7” indicates failure due to out of memory or > 1 day runtime. Avg. memory footprint per machine (GB, CPU/GPU)

#Edges PBG DistDGL DistGER DistGER-G NeutronTP LeapGNN FeLoG

80.51 K 5.90 M 8.9/- 5.4/1.4 1.14 M 2.99 M 9.7/- 5.5/1.5 2.24 M 14.61 M 10.3/- 5.8/1.7 3.07 M 117.19 M 11.4/- 6.3/2.1 41.65 M 1.47 B 31.7/7 111.06 M 1.62 B 7 7 105.15 M 3.72 B 7 7

0.9/4.3/5.5/6.9/67.2/72.3/125.8/-

0.5/0.9 2.3/5.3 2.6/6.6 6.0/8.0 7 7 7

8.6/1.2 6.8/1.2 0.5/0.5 9.0/1.6 17.0/3.4 1.9/0.6 9.3/2.2 30.7/7.7 2.1/0.9 9.7/2.6 39.4/20.1 6.1/1.8 19.6/19.4 7 59.7/7.2 30.7/31.2 7 71.5/9.4 7 7 107.3/9.0

The machines run Ubuntu 20.04, with GCC 9.4.0 used for compiling DistGER, DistGER-GPU, and FeLoG, and Python 3.10 with torch 1.11.0 used as the backend deep learning framework for PyTorchBigGraph, DistDGL, LeapGNN, NeutronTP, and GraNNDis. The multi-GPU comparison with GraNNDis is conducted on a server equipped with four NVIDIA A40 GPUs. Datasets. We employ seven widely-used, real-world graphs (Table 3): Flickr (FL) [56], Youtube (YT) [56], LiveJournal (LJ) [78], Com-Orkut (OR) [74], Twitter (TW) [31], U.K.-2007 (UK) [6] and OGB-papers100M (OGB) [27]. The FL and YT datasets are labeled, with FL having 195 labels for user-content interactions and YT 47 labels for video engagement. The OGB dataset has 128-dimensional node features, representing citation networks of scientiﬁc papers. For heterophilic settings, we use two labeled benchmarks, Amazonratings (AR: |𝑉 | = 24.49K, |𝐸| = 93.05K, 5 classes) and Romanempire (RE: |𝑉 | = 22.66K, |𝐸| = 32.93K, 18 classes) [49], to evaluate the sensitivity of FeeST to 𝜇 via downstream node classiﬁcation. We also use synthetic graphs [10] (up to 1 billion nodes, 10 billion edges) to assess the scalability of FeLoG. Considering the default settings of popular graph embedding methods, we use their undirected version.

PBG

DistDGL

DistGER

NeutronTP

LeapGNN

FeLoG

DistGER-G

OGB

Graphs

Figure 13: Efﬁciency of PBG [33], DistDGL [85], DistGER [17], DistGER-G [18], NeutronTP [3], LeapGNN [13] and FeLoG (ours). § 6.7). For DistGER and DistGER-G, we set the sliding window size 𝑤=10, the number of negative samples 𝐾=5, and the synchronization period to 0.1 sec [28]. For PBG, DistDGL, LeapGNN and NeutronTP, we follow the default settings in their papers [3, 13, 33, 85]. For fair system comparison, we use embedding dimension 𝑑=128 that is commonly adopted [21, 24, 47, 57, 79], and report the average end-to-end epoch time. For task effectiveness, we select the best results via grid search over learning rates in [0.001, 0.1], training epochs in [1, 30], embedding dimensions in {32, 64, 128, 256, 512}, and, for neighbor-sampling based GNN settings, sampling hyperparameters including the number of layers ∈ {2, 3, 4} and per-layer fanout ∈ {5, 10, 15, 25}.

6.2

Efﬁciency and Memory Requirement

We report the end-to-end running times of PBG, DistDGL, DistGER, DistGER-G, NeutronTP, LeapGNN, and FeLoG on seven realworld graphs with the cluster of 8 machines in Figure 13. The reported average epoch end-to-end time includes sampling, training, Baselines. We select six state-of-the-art distributed graph embedand communication overheads. FeLoG signiﬁcantly outperforms the ding frameworks: the multi-relation embedding system PyTorchcompetitors on all these graphs, achieving an average acceleration BigGraph (PBG) developed by Facebook https://github.com/facebookresearch/ of 27.9×. PBG leverages a parameter server to synchronize embedPyTorch-BigGraph [33]; the GNN-based system DistDGL from Amadings between clients, resulting in more load on the communication zon https://github.com/dmlc/dgl [85]; the recent GNN-based framenetwork. As a result, PBG is on average 68.4× slower than FeLoG. work NeutronTP https://github.com/iDC-NEU/NeutronTP [3] and LeapGNNAs a system of the same type, FeLoG outperforms the CPU-based https://github.com/ISCS-ZJU/LeapGNN-AE [13]; and the random walkDistGER and the CPU-GPU hybrid DistGER-G by 3.9× and 5.3× based system DistGER https://github.com/RocmFang/DistGER [17]. on average, respectively. DistGER uses information-theoretic walks In addition, we include DistGER-Pipe [18], a CPU-only pipelineto adapt sampling, but without training feedback it applies a unioptimized extension of DistGER, and further implement its hybrid form conﬁguration to all nodes, causing coarse-grained control and CPU-GPU variant, DistGER-G, which performs sampling on CPUs redundancy. DistGER-G, though accelerating training via GPU, inand ofﬂoads training to GPUs. We additionally compare with GraNNDis curs heavy CPU-GPU data transfer overhead, which reduces GPU https://github.com/AIS-SNU/GraNNDis_Artifact [54], a recent multiutilization and degrades overall performance. Notice that DistGERGPU GNN training framework. We do not compare against singleG fails on larger datasets such as TWT, OGB, and UK due to its machine execution planners such as NeutronOrch [2], DAHA [36], redundant corpus generation during sampling and suboptimal sysand GIDS [45], as they target intra-node scheduling and are not detem support for training, which lead to memory consumption exsigned for FeLoG’s multi-machine setting. Empirically, in our setup ceeding available capacity. For GNN-based system DistDGL, due on OR, SSD-based GIDS takes 3095 s while FeLoG completes in to the long running time of graph sampling (e.g., taking 80% of the 61.8 s, and the in-memory NeutronOrch/DAHA run out of memory overhead), it is highly inefﬁcient than other systems. Similarly to on the billion-scale UK graph. DistGER-G, it cannot run on billion-edge graphs, as it fails to terParameters. By default, FeLoG uses random-walk based graph emminate within one day. Two recent GNN systems, NeutronTP and bedding, while we also evaluate its generality over GNN-based emLeapGNN, optimize communication and feature operations. Howbeddings in §6.5. We set 𝜇=0.65 in FeeST, and compress the top-2 ever, their lack of real-time embedding quality awareness and unimost frequent nodes in FaBC (the sensitivity analysis is reported in form treatment of node features across iterations lead to redundant 11

End-to-end Running Time (second)

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

PBG

DistDGL

DistGER

NeutronTP

LeapGNN

FeLoG

DistGER-GPU

Table 4: 𝐴𝑈𝐶 of FeLoG and competitors for link prediction.

DistGER-G 4

OGB

DistDGL NeutronTP

LeapGNN UK

FeLoG

Twitter

Youtube

Com-Orkut 1

LiveJournal

Flick

Number of Machines

Youtube

LiveJournal

Com-Orkut

Twitter

PBG DistDGL DistGER FeLoG

0.753 0.894 0.966 0.949

0.882 0.718 0.976 0.979

0.955 0.815 0.921 0.965

0.912 running time > 1 day 0.919 0.942

Number of Nodes

Table 5: RAG retrieval performance of FeLoG and NeutronTP on Flickr and Youtube datasets (𝐾=20, 2-hop retrieval).

(a) Scalability across Machine Scales (b) Scalability across Graph Sizes

Figure 14: Scalability analysis of FeLoG.

Flickr

Metric

computation and hinder convergence speed. Hence, they are on average 7.9× and 15.8× slower than FeLoG, and cannot run on the largest dataset UK due to out-of-memory issues. We further discuss accuracy-time convergence in §6.4 to quantify the time-to-quality tradeoff. Considering the resource consumption that affects scalability, Table 3 reports the average per-machine memory footprint of FeLoG and baseline systems on each graph. FeLoG consistently achieves the lowest or one of lowest memory usage across both CPU and GPU components, with particularly low usage on GPU. For the billion-scale graphs like UK, FeLoG is one of the few systems able to run without exceeding memory limits, highlighting its efﬁciency and scalability in distributed settings.

6.3

Method

Hit@K nDCG@K MRR@K

Youtube

NeutronTP

FeLoG

NeutronTP

FeLoG

0.817 0.202 0.343

0.955 (+16.9%) 0.499 (+147.0%) 0.714 (+108.2%)

0.790 0.267 0.430

0.860 (+8.9%) 0.677 (+153.6%) 0.924 (+114.9%)

from 105 to 109 . Figure 14(b) presents the running times on these synthetic graphs using a cluster of 8 machines, suggesting that the running time increases linearly with the size of a graph, and FeLoG has the capability to handle even billion-node graphs. Moreover, the running times for seven real-world graphs (including the billionsscale graphs, for which the competing systems do not terminate in 1 day or crash due to memory limitation) are inserted into the plot, which is consistent with the trend on synthetic data.

Scalability

6.4

Figure 14(a) shows end-to-end running times of all competing systems on the LiveJournal graph, as we increase # machines from 1 to 8 to evaluate scalability. FeLoG achieves better scalability than the other six distributed systems. Due to space limitations, we omit results on other graph datasets, which either exhibit similar trends or are too large for the competing systems to scale. PBG leverages a parameter server and a shared network ﬁlesystem to synchronize the parameters in the distributed model. When the number of machines increases, PBG puts more load on the communications network, resulting in poor scalability. DistDGL suffers from limited scalability due to its full-graph parameter synchronization and frequent gradient communication across machines. The CPU-based DistGER exhibits better scalability than the CPU-GPU hybrid DistGER-G, as the latter suffers from substantial CPU-GPU data transfer overhead and a sequential execution pattern that undermines the performance beneﬁts of GPU acceleration. NeutronTP’s end-to-end running time remains nearly stable as the number of machines increases, indicating limited scalability. This is mainly due to its uniform processing of all node features, leading to redundant computation and underutilization of distributed resources. LeapGNN scales poorly due to frequent step-wise global synchronization that ampliﬁes stragglers and idle GPUs as machines increase. In comparison, FeLoG incorporates a feedback-driven sampling-training coupling model and an activity-aware communication mechanism to reduce both computation and communication costs, it also employs a round-interleaved pipeline to maximize CPU-GPU utilization. Hence, FeLoG achieves better scalability than other systems. To further assess the scalability of FeLoG, we generate synthetic graphs [10] with a ﬁxed node degree of 10 and the number of nodes

Effectiveness

Application in Link Prediction. To perform link prediction on a given graph 𝐺, following [17, 57, 75], we ﬁrst uniformly at random remove 50% edges as positive test edges, and the rest are used as positive training edges. We also provide negative training and test edges by considering those node pairs between which no edge exists in 𝐺. We ensure that the positive and negative set sizes are similar. For a pair of nodes (𝑢, 𝑣), let 𝜑 (𝑢) and 𝜑 (𝑣) be the vectors learned by embedding methods. The link prediction is conducted as a classiﬁcation task based on the similarity of 𝑢 and 𝑣, i.e., 𝜑 (𝑢) · 𝜑 (𝑣). The effectiveness of link prediction is measured via the 𝐴𝑈𝐶 (Area Under Curve) score [76], the higher the better. We repeat this procedure 50 times to offset the randomness of edge removal and report the average 𝐴𝑈𝐶 in Table 4. FeLoG outperforms all competitors on these graphs, except for DistGER on Youtube, where FeLoG ranks second. On average, FeLoG achieves a 9.8% higher 𝐴𝑈𝐶 score compared with the other three systems. Figure 15(a) exhibits accuracyefﬁciency tradeoffs of FeLoG and competitors, i.e., their 𝐴𝑈𝐶 score convergence curves w.r.t. increasing running times, over LiveJournal, indicating that FeLoG tends to reach its peak accuracy in fewer epochs (around 4). In addition, Figure 15(b) shows consistently fast accuracy-efﬁciency convergence of FeLoG across graphs, reaching high 𝐴𝑈𝐶 within a short running time on Youtube (3 epochs) and Com-Orkut (6 epochs). Application in Multi-label Classiﬁcation. This task predicts one or more labels for each graph node and has applications in text categorization [81] and bioinformatics [80]. We use embedding vectors and a one-vs-rest logistic regression classiﬁer with L2 regularization [16], then evaluate the effectiveness by micro-averaged F1 12

0.8

0.7

0.9

0.8

0.7

Youtube LiveJournal

0.6

Normalization Runtime (s)

FeLoG

Micro-F1 Score

DistGER

AUC Score

PBG

DistDGL

DistDGL DistGER FeLoG

0.4

Com-Orkut

0.6 10

100

1000

0.3

100

Running Time (seconds)

100

Running Time (seconds)

1 w/o-ACM w-ACM

0 FL

(b) FeLoG Across Graphs

(a) Time-AUC

Flickr

Youtube 0.30

Micro-F1 Score

Macro-F1 Score

Flickr (a1)

(b1)

0.24 0.28

0.21

0.18 0.0

0.2

0.4

0.6

0.8

0.26 0.00 1.0

0.03

0.06

0.42

0.39

0.09

PBG

0.2

0.4

DistGER

0.6

0.8

1.0

0.00

0.03

0.06

0.09

FeLoG

NeutronTP+FeeST

DistDGL

DistDGL+FeeST

0.8

0.2

GraNNDis FeLoG

LJ Graphs

(a) Generalizability

Normalization Runtime (s)

NeutronTP

End-to-end Runtime (s)

Normalization Runtime (s)

Figure 16: 𝑀𝑎𝑐𝑟𝑜 − 𝐹 1 (a1, b1) and 𝑀𝑖𝑐𝑟𝑜 − 𝐹 1 (a2, b2) scores for multilabel node classiﬁcation. 1.0

OGB

Graphs

(b) Multi-GPU

1 w/o-FeeST w-FeeST

Graphs

(b) Training Reduction

All Sync

w-HaSyn 10

Graphs

Generalizability of FeLoG

A key feature of FeLoG is its general API design, which supports seamless integration with both random walk-based and GNN-based systems (§5.1). To validate this generalizability, we extend two representative distributed GNN systems, NeutronTP and DistDGL, by incorporating the feedback-coupled sampling-training (FeeST) via the uniﬁed API of FeLoG, resulting in NeutronTP+FeeST and DistDGL+FeeST. As shown in Figure 17(a), FeLoG consistently reduces normalization runtime across datasets. For NeutronTP, it achieves speedups between 1.33× and 1.69×, with an average of 1.50×. For DistDGL, the speedups range from 1.23× to 1.67×, averaging 1.45×. These results demonstrate that the proposed feedback loop mechanism generalizes beyond random walk-based solutions and can be effectively applied to GNN-based pipelines, yielding signiﬁcant efﬁciency gains without altering their underlying training logic. We further compare FeLoG with GraNNDis [54], a recent multi-GPU GNN training framework, under a four-NVIDIA-A40 setting. As shown in Figure 17(b), FeLoG achieves an average 3.45× speedup over GraNNDis across datasets, further conﬁrming its ability to support and accelerate multi-GPU training.

0.38

0.0

DistDGL

6.5

0.40

0.36

w-FaBC

Figure 18: Impact of ACM on communication performance.

(b2)

0.42

(a) ACM Efﬁciency

Youtube

(a2)

Graphs

Figure 15: The inﬂuence of running time on embedding quality for FeLoG and competitors. Each point corresponds to one training epoch. 0.27

Original Data Size

10 Size (Bytes)

1.0 PBG

0.9

Sampling-Training Data

1.0

Synchronization Size (Bits)

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Graphs

Figure 17: FeLoG generalizability and FeeST impact on efﬁciency. (𝑀𝑖𝑐𝑟𝑜 − 𝐹 1) and macro-averaged F1 (𝑀𝑎𝑐𝑟𝑜 − 𝐹 1) [62] scores, where 𝑀𝑖𝑐𝑟𝑜 − 𝐹 1 gives equal weight to each test instance and 𝑀𝑎𝑐𝑟𝑜 − 𝐹 1 assigns equal weight to each label category [29]. Following [21, 24, 47, 57], we select 10% to 90% training data ratio on Flickr, and 1% to 9% training ratio on Youtube. We report the averaged 𝑀𝑎𝑐𝑟𝑜 − 𝐹 1 and 𝑀𝑖𝑐𝑟𝑜 − 𝐹 1 scores in Figure 16. We ﬁnd that FeLoG has better 𝑀𝑎𝑐𝑟𝑜 − 𝐹 1 and 𝑀𝑖𝑐𝑟𝑜 − 𝐹 1 scores than existing frameworks, gaining 9.8% and 2.8% average improvements, respectively, due to its more effective information-centric random walks. Figure 15 (c) shows the time-accuracy trade-offs of FeLoG and competitors on node classiﬁcation over YTB. The results also show that FeLoG reaches the same or higher accuracy in less time.

6.6

Performance due to Individual Parts of FeLoG

Feedback-driven Sampling-Training Efﬁciency. To evaluate the effectiveness of FeLoG’s design (§5), we ﬁrst examine the impact of the feedback-driven sampling-training coupling mechanism (FeeST, §5.1). We compare the execution time of FeLoG with and without FeeST (denoted as w-FeeST and w/o-FeeST) across all graphs. In w/o-FeeST, the number of sampling iterations is determined using the same strategy as DistGER, while all other settings remain consistent. As shown in Figure 17(c), w-FeeST achieves signiﬁcant acceleration, ranging from 1.6× to 5.5×. This improvement comes from the dynamic feedback loop between sampling and training, where Application in Graph-based RAG. To evaluate the generalization of FeLoG to graph-based retrieval-augmented generation (GraphRAG), sampling is adaptively guided by real-time embedding quality indicators, effectively reducing redundant sampling and unnecessary where graph embeddings serve as the retrieval backbone for LLMs, computation. We further assess the sensitivity of FeeST to the simiwe integrate the learned embeddings into a FAISS-based vector larity parameter 𝜇 in §6.7. retrieval pipeline on FK and YTB. FK captures user-content interactions, while YTB models large-scale user-item engagement, enCommunication Efﬁciency. We next evaluate the impact of the abling us to construct ground-truth relevance based on shared seactivity-aware communication mechanism (ACM, §5.2) on FeLoG’s mantic attributes reﬂected by these interactions. Given a query node, communication performance in distributed settings. Speciﬁcally, we we retrieve top-𝐾 candidate nodes by embedding similarity and compare the end-to-end runtime of FeLoG with and without ACM, evaluate retrieval quality using Hit@K, nDCG@K, and MRR@K denoted as w-ACM and w/o-ACM, respectively. As shown in Fig(Table 5). Across both datasets, FeLoG consistently outperforms ure 18(a), enabling ACM yields an average speedup of 6.19× across NeutronTP, achieving an average improvement of 150.3% in nDCG@20, all datasets. This substantial gain comes from two complementary 12.9% in Hit@20, and 111.6% in MRR@20. These results indicate strategies in ACM: FaBC (§5.2.2) alleviates PCIe bottlenecks within that FeLoG yields higher-quality retrieval embeddings for GraphRAG. each machine, while HaSyn (§5.2.3) reduces network trafﬁc across 13

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

AVG: 34.6%

AVG: 82.2%

80 AVG: 79.2%

AVG: 13.9%

CPU

GPU

0 0

Running Time (seconds)

(a) Decouple

Running Time (seconds)

(b) Pipeline

FeeST-S

FeeST-T

FeeST-A

FaBC-D

HaSyn-S

HaSyn-C

FaBC-C

100

FeeST-S

100

FaBC-C

FeeST-T

100

HaSyn

FaBC-D

0 FL

Ratio (%)

100

Ratio (%)

GPU

Runtime Ratio (%)

CPU

Utilization (%)

100

Graphs

0 FL

Figure 19: Resource utilization and runtime breakdown analysis.

Graphs

(a) Sampling

(b) Training

Figure 20: Breakdown analysis of FeLoG for sampling and training, and impact of FeeST on efﬁciency.

machines. To better understand the contributions of these two components, we further break down their individual impact. Figure 18(b) shows the size of training data transferred between CPU and GPU, before and after applying FaBC, denoted as Original Data Size and w-FaBC, respectively. On average, FaBC reduces intra-machine data transfer volume by 53.1%, demonstrating its effectiveness in relieving PCIe overhead. Finally, Figure 18(c) compares HaSyn against the conventional full synchronization method AllSync adopted by systems like DistDGL and PBG. The results show that HaSyn reduces communication cost by over 90% during each synchronization period. We compare HaSyn with AllSync and RandomSync on LJ. Compared with AllSync, HaSyn reduces runtime from 509.39s to 111.26s, achieving a 4.58× speedup with only a slight AUC drop. It also achieves higher AUC than RandomSync under the same synchronization size, indicating that update hotness is effective for selecting embeddings to synchronize. In addition, we assess how compression frequency range affects the compression ratio of FaBC in § 6.7.

Table 6: Impact of different compression frequency ranges on compression ratio.

6.7

Dataset

Top-1

Top-2

Top-3

Flickr YouTube LiveJournal ComOrkut Twitter

0.67 0.59 0.59 0.60 0.59

0.48 0.42 0.48 0.49 0.47

0.46 0.40 0.44 0.43 0.41

Experiments on Parameter Sensitivity Analysis

To further assess the sensitivity of FeeST to the similarity convergence parameter 𝜇, we report the 𝐴𝑈𝐶 scores and execution times of FeLoG on the Flickr graph with varying 𝜇 values. While a smaller 𝜇 often requires more sampling to reach convergence, increasing 𝜇 leads to longer training time without consistently improving accuracy. As shown in Figure 21(a) and (b), the 𝐴𝑈𝐶 score peaks around 𝜇 = 0.6-0.65, beyond which accuracy slightly drops, while execution time continues to grow. This observation suggests that 𝜇 values in this range provide a favorable trade-off between efﬁciency and accuracy for this dataset. Similar trends are observed on other datasets used in our experiments, so we use 𝜇 = 0.65 as the default conﬁguration for our datasets in the experiments. For heterophilic settings, we further evaluate FeeST on Amazon-ratings (AR) and Roman-empire (RE). As shown in Figure 21 (c) and (d), FeeST provides a meaningful quality-efﬁciency trade-off under varying 𝜇: AR is broadly stable, while RE favors a lower threshold. Runtime increases with 𝜇, and 𝜇 = 1 corresponds to the w/o-FeeST setting. These results support validation-calibrated 𝜇 in heterophilic settings, with only 1.85s and 1.68s per candidate on AR and RE, respectively. To assess how compression frequency range affects the compression ratio, Table 6 shows the results when compressing the top-1, top-2, and top-3 most frequent nodes in the training data. The results indicate that expanding the compression range does not signiﬁcantly improve the compression ratio. Thus, a balance must be struck between compression efﬁciency and computation overhead. FeLoG addresses this by analyzing the ﬁrst-round sampling to dynamically conﬁgure compression parameters, effectively balancing compression gain and processing cost.

Computing Resources Utilization. To improve computational efﬁciency, FeLoG introduces a round-interleaved pipeline mechanism (RiPP, §5.3) by decoupling the sampling and training operators. To evaluate its effectiveness, we measure CPU and GPU utilization over time on the LJ dataset under both decoupled and pipelined execution. As shown in Figure 19(a), under decoupled execution, CPU utilization drops signiﬁcantly after the initial sampling phase, leaving resources idle. Similarly, GPU utilization remains low, as each training round must wait for sampling to complete. In contrast, RiPP enables concurrent execution between rounds; the sampling stage overlaps with the training stage through different threads and devices. This design leads to much higher resource utilization: Figure 19(b) shows average CPU and GPU utilizations of 82.2% and 79.2%, respectively. Overall, RiPP effectively boosts system throughput and scalability by maximizing hardware utilization. Breakdown Analysis We further provide a ﬁne-grained runtime breakdown of FeLoG. As shown in Figure 19(c), we separate the execution into sampling (FeeST-S), training (FeeST-T), active-set computation (FeeST-A), compression (FaBC-C), decompression (FaBCD), embedding synchronization (HaSyn-S), and synchronizationset selection (HaSyn-C) across different graphs. The normalized breakdown shows that sampling and training remain the dominant components. In contrast, FeeST-A, FaBC, and HaSyn introduce only limited runtime overhead, accounting for 4.0%, 4.7%, and 2.4% on average, respectively. In addition, the dominant extra memory of HaSyn comes from the synchronization-set buffer, whose size is |F | × 𝑑 × 4 bytes for 𝑑-dimensional ﬂoat embeddings. For example, on LJ, |F | = 1316, so it requires only 0.64 MB memory footprint. 14

0.93

0.92

0.91

0.90 0.5

0.6

0.7

0.8

(a) Accuracy on link prediction Amazon-ratings Roman-empire

Accuracy

0.40

w/o-FeeST

0.12 0.0

0.2

0.4

0.6

0.8

1.0

[4] Guangji Bai, Ziyang Yu, Zheng Chai, Yue Cheng, and Liang Zhao. 2025. Staleness-alleviated distributed gnn training via online dynamic-embedding prediction. In Proceedings of the 2025 SIAM International Conference on Data Mining (SDM). SIAM, 578–587. [5] Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509–512. [6] Paolo Boldi, Massimo Santini, and Sebastiano Vigna. 2008. A large time-aware web graph. In ACM SIGIR Forum, Vol. 42. ACM New York, NY, USA, 33–38. [7] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2018. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering 30, 9 (2018), 1616– 1637. [8] Chunyu Cao, Xin Ai, Qiange Wang, Yanfeng Zhang, Zhenbo Fu, Hao Yuan, Mingyi Cao, Chaoyi Chen, Yingyou Wen, Yu Gu, et al. 2025. NeutronHeter: Optimizing Distributed Graph Neural Network Training for Heterogeneous Clusters. Proceedings of the ACM on Management of Data 3, 4 (2025), 1–29. [9] Jiahang Cao, Jinyuan Fang, Zaiqiao Meng, and Shangsong Liang. 2024. Knowledge graph embedding: A survey from the perspective of representation spaces. Comput. Surveys 56, 6 (2024), 1–42. [10] Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004. R-MAT: A Recursive Model for Graph Mining. In Proceedings of the SIAM International Conference on Data Mining. 442–446. [11] Chee-Yong Chan and Yannis E Ioannidis. 1998. Bitmap index design and evaluation. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. 355–366. [12] Jie Chen, Tengfei Ma, and Cao Xiao. 2018. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In International Conference on Learning Representations. [13] Weijian Chen, Shuibing He, Haoyang Qu, and Xuechen Zhang. 2025. LeapGNN: Accelerating Distributed GNN Training Leveraging Feature-Centric Model Migration. In 23rd USENIX Conference on File and Storage Technologies (FAST 25). 255–270. [14] Xu Cheng, Liang Yao, Feng He, Yukuo Cen, Yufei He, Chenhui Zhang, Wenzheng Feng, Hongyun Cai, and Jie Tang. 2025. LPS-GNN: Deploying Graph Neural Networks on Graphs with 100-Billion Edges. arXiv preprint arXiv:2507.14570 (2025). [15] Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. 2024. From local to global: A graph rag approach to queryfocused summarization. arXiv preprint arXiv:2404.16130 (2024). [16] R. Fan, K. Chang, C. Hsieh, X. Wang, and C. Lin. 2008. LIBLINEAR: A Library for Large Linear Classiﬁcation. Journal of Machine Learning Research (2008), 18711874. [17] Peng Fang, Arijit Khan, Siqiang Luo, Fang Wang, Dan Feng, Zhenli Li, Wei Yin, and Yuchao Cao. 2023. Distributed Graph Embedding with InformationOriented Random Walks. Proceedings of the VLDB Endowment 16, 7 (2023), 1643–1656. [18] Peng Fang, Zhenli Li, Arijit Khan, Siqiang Luo, Fang Wang, Zhan Shi, and Dan Feng. 2025. Information-Oriented Random Walks and Pipeline Optimization for Distributed Graph Embedding. IEEE Transactions on Knowledge and Data Engineering 37, 1 (2025), 408–422. [19] Peng Fang, Siqiang Luo, Fang Wang, Bolong Zheng, Hong Jiang, Dan Feng, Hechang Pan, and Xingyu Wan. 2025. OMeGa: Boosting Large-Scale Graph Embeddings with Heterogeneous Memory Processing. In 2025 IEEE 41st International Conference on Data Engineering. 3369–3383. [20] Peng Fang, Fang Wang, Zhan Shi, Hong Jiang, Dan Feng, Xianghao Xu, and Wei Yin. 2022. How to Realize Efﬁcient and Scalable Graph Embeddings via an Entropy-driven Mechanism. IEEE Transactions on Big Data (2022). [21] Peng Fang, Fang Wang, Zhan Shi, Hong Jiang, Dan Feng, and Lei Yang. 2021. HuGE: An entropy-driven approach to efﬁcient and scalable graph embeddings. In IEEE 37th International Conference on Data Engineering. IEEE, 2045–2050. [22] Tong Geng, Ang Li, Runbin Shi, Chunshu Wu, Tianqi Wang, Yanfei Li, Pouya Haghi, Antonino Tumeo, Shuai Che, Steve Reinhardt, et al. 2020. AWB-GCN: A graph convolutional network accelerator with runtime workload rebalancing. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). 922–936. [23] Chenghua Gong, Yao Cheng, Jianxiang Yu, Can Xu, Caihua Shan, Siqiang Luo, and Xiang Li. 2024. A survey on learning from graphs with heterophily: Recent advances and future directions. arXiv preprint arXiv:2401.09769 (2024). [24] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 855–864. [25] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems, Vol. 30. [26] Jiafeng Hu, Reynold Cheng, Zhipeng Huang, Yixang Fang, and Siqiang Luo. 2017. On embedding uncertain graphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 157–166.

18 16 14 12 10 8 6 0.5

0.6

0.7

0.8

(b) Efﬁciency on link prediction Running Time (seconds)

AUC scores

0.94

Running Time (seconds)

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

1.2

Amazon-ratings Roman-empire

w/o-FeeST

1.1

1.0 0.0

0.2

0.4

0.6

0.8

1.0

Figure 21: Sensitivity of FeeST w.r.t. parameter 𝜇.

CONCLUSIONS

We presented FeLoG, a scalable and efﬁcient distributed graph embedding system that addresses redundant sampling, excessive communication, and low resource utilization caused by the decoupling between sampling and training. FeLoG introduces three innovations: (1) a feedback-coupled sampling-training model that adapts sampling based on real-time embedding quality, (2) an activity-aware communication mechanism that reduces both intra- and inter-machine communication, and (3) a round-interleaved pipeline that overlaps sampling and training to improve CPU-GPU utilization. Experiments on billion-scale graphs show that FeLoG achieves an average speedup of 27.9×, reduces communication cost by over 53.1%, and sustains over 80% CPU-GPU utilization, while generalizing to different graph embedding and GNN-based frameworks. Future work includes incorporating topology-aware optimization for intra-node GPU interconnects and exploring GPU-directed remote data access to further reduce CPU-mediated transfers.

ACKNOWLEDGMENTS This work was supported by the National Natural Science Foundation of China (Nos. 62402187 and U22A2027), the China Postdoctoral Science Foundation (Nos. GZB20240243 and 2024M751009), and the Postdoctoral Project of Hubei Province (No. 2024HBBHCXA024). Peng Fang is grateful to Professor Beng Chin Ooi for his invaluable guidance and insightful feedback on this work during his postdoctoral research at the National University of Singapore.

REFERENCES [1] 2026. Our code and datasets. https://github.com/RocmFang/FeLoG. [2] Xin Ai, Qiange Wang, Chunyu Cao, Yanfeng Zhang, Chaoyi Chen, Hao Yuan, Yu Gu, and Ge Yu. 2024. NeutronOrch: Rethinking Sample-Based GNN Training under CPU-GPU Heterogeneous Environments. Proceedings of the VLDB Endowment 17, 8 (2024), 1995–2008. [3] Xin Ai, Hao Yuan, Zeyu Ling, Qiange Wang, Yanfeng Zhang, Zhenbo Fu, Chaoyi Chen, Yu Gu, and Ge Yu. 2025. NeutronTP: Load-Balanced Distributed FullGraph GNN Training with Tensor Parallelism. In 51st International Conference on Very Large Data Bases. 173–186. 15

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li, Yibo Zhou, Fang Wang, and Dan Feng

[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 (2020), 22118–22133. [28] Shihao Ji, Nadathur Satish, Sheng Li, and Pradeep K Dubey. 2019. Parallelizing word2vec in shared and distributed memory. IEEE Transactions on Parallel and Distributed Systems 30, 9 (2019), 2090–2100. [29] M. M. Keikha, M. Rahgozar, and M. Asadpour. 2018. Community Aware Random Walk for Network Embedding. Knowledge-Based Systems 148 (2018), 47– 54. [30] Thomas N Kipf and Max Welling. 2017. Semi-Supervised Classiﬁcation with Graph Convolutional Networks. In International Conference on Learning Representations. [31] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proceedings of the 19th International Conference on World Wide Web. 591–600. [32] Yunjae Lee, Jinha Chung, and Minsoo Rhu. 2022. Smartsage: training large-scale graph neural networks using in-storage processing architectures. In Proceedings of the 49th Annual International Symposium on Computer Architecture. 932– 945. [33] Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. 2019. Pytorch-biggraph: A large scale graph embedding system. In Proceedings of Machine Learning and Systems, Vol. 1. 120–131. [34] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web. 641–650. [35] Yongkun Li, Zhiyong Wu, Shuai Lin, Hong Xie, Min Lv, Yinlong Xu, and John CS Lui. 2019. Walking with perception: Efﬁcient random walk sampling via common neighbor awareness. In 2019 IEEE 35th International Conference on Data Engineering. IEEE, 962–973. [36] Zhiyuan Li, Xun Jian, Yue Wang, Yingxia Shao, and Lei Chen. 2024. Daha: Accelerating gnn training with data and hardware aware execution planning. Proceedings of the VLDB Endowment 17, 6 (2024), 1364–1376. [37] Ningyi Liao, Dingheng Mo, Siqiang Luo, Xiang Li, and Pengcheng Yin. 2022. SCARA: scalable graph neural networks with feature-oriented optimization. arXiv preprint arXiv:2207.09179 (2022). [38] Dongkyun Lim and John Kim. 2025. TidalMesh: Topology-Driven AllReduce Collective Communication for Mesh Topology. In 2025 IEEE International Symposium on High Performance Computer Architecture. IEEE, 1526–1540. [39] Tianfeng Liu, Yangrui Chen, Dan Li, Chuan Wu, Yibo Zhu, Jun He, Yanghua Peng, Hongzheng Chen, Hongzhi Chen, and Chuanxiong Guo. 2023. BGL: GPUEfﬁcient GNN training by optimizing graph data I/O and preprocessing. In 20th USENIX Symposium on Networked Systems Design and Implementation. 103– 118. [40] Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Dinh Phung, Chen Gong, and Shirui Pan. 2025. GFM-RAG: graph foundation model for retrieval augmented generation. arXiv preprint arXiv:2502.01113 (2025). [41] Siqiang Luo, Zichen Zhu, Xiaokui Xiao, Yin Yang, Chunbo Li, and Ben Kao. 2023. Multi-Task Processing in Vertex-Centric Graph Systems: Evaluations and Insights. In International Conference on Extending Database Technology. 247– 259. [42] Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415–444. [43] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efﬁcient estimation of word representations in vector space. In International Conference on Learning Representations. [44] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed Representations of Words and Phrases and their Compositionality. Advances in Neural Information Processing Systems 26 (2013). [45] Jeongmin Brian Park, Vikram Sharma Mailthody, Zaid Qureshi, and Wen-mei Hwu. 2024. Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses. Proceedings of the VLDB Endowment 17, 6 (2024), 1227–1240. [46] Yeonhong Park, Sunhong Min, and Jae W Lee. 2022. Ginex: SSD-Enabled Billion-Scale Graph Neural Network Training on a Single Machine via Provably Optimal in-Memory Caching. Proceedings of the VLDB Endowment 15, 11 (2022), 26262639. [47] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 701–710. [48] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. 2023. Characterizing graph datasets for node classiﬁcation: Homophilyheterophily dichotomy and beyond. Advances in Neural Information Processing Systems 36 (2023), 523–548. [49] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2023. A Critical Look at the Evaluation of GNNs under

Heterophily: Are We Really Making Progress?. In International Conference on Learning Representations. [50] Linshan Qiu, Lu Chen, Hailiang Jie, Xiangyu Ke, Yunjun Gao, Yang Liu, and Zetao Zhang. 2024. GPU-Accelerated Batch-Dynamic Subgraph Matching. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 3204–3216. [51] Alexander Renz-Wieland, Rainer Gemulla, Zoi Kaoudi, and Volker Markl. 2022. NuPS: A Parameter Server for Machine Learning with Non-Uniform Parameter Access. In Proceedings of the 2022 International Conference on Management of Data. 481–495. [52] Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. 2021. Knowledge graph embedding for link prediction: A comparative analysis. ACM Transactions on Knowledge Discovery from Data 15, 2 (2021), 1–49. [53] Guangming Sheng, Junwei Su, Chao Huang, and Chuan Wu. 2024. Mspipe: Efﬁcient temporal gnn training via staleness-aware pipeline. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2651–2662. [54] Jaeyong Song, Hongsun Jang, Hunseong Lim, Jaewon Jung, Youngsok Kim, and Jinho Lee. 2024. GraNNDis: Fast distributed graph neural network training framework for multi-server clusters. In Proceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques. 91–107. [55] Dahai Tang, Jiali Wang, Rong Chen, Lei Wang, Wenyuan Yu, Jingren Zhou, and Kenli Li. 2024. Xgnn: Boosting multi-gpu gnn training via global gnn memory store. Proceedings of the VLDB Endowment 17, 5 (2024), 1105–1118. [56] Lei Tang and Huan Liu. 2009. Scalable learning of collective behavior based on sparse social dimensions. In Proceedings of the 18th ACM Conference on Information and Knowledge Management. 1107–1116. [57] Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. 2018. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web conference. 539–548. [58] Ke Tu, Peng Cui, Xiao Wang, Philip S Yu, and Wenwu Zhu. 2018. Deep recursive network embedding with regular equivalence. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2357–2366. [59] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations. [60] Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. 2023. MariusGNN: Resource-Efﬁcient Out-of-Core Training of Graph Neural Networks. In Proceedings of the 18th European Conference on Computer Systems (Rome, Italy). 144161. [61] Cheng Wan, Youjie Li, Cameron R. Wolfe, Anastasios Kyrillidis, Nam Sung Kim, and Yingyan Lin. 2022. PipeGCN: Efﬁcient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication. In International Conference on Learning Representations. [62] Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 1225–1234. [63] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. 2018. GraphGAN: Graph Representation Learning With Generative Adversarial Nets. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, Vol. 32. [64] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. 2019. Deep graph library: A graphcentric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.01315 (2019). [65] Qiange Wang, Yanfeng Zhang, Hao Wang, Chaoyi Chen, Xiaodong Zhang, and Ge Yu. 2022. Neutronstar: Distributed GNN Training with Hybrid Dependency Management. In Proceedings of the 2022 International Conference on Management of Data. 1301–1315. [66] Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and Philip S Yu. 2022. A survey on heterogeneous graph embedding: methods, techniques, applications and sources. IEEE Transactions on Big Data 9, 2 (2022), 415–436. [67] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, et al. 2021. Apan: Asynchronous propagation attention network for real-time temporal graph embedding. In Proceedings of the 2021 International Conference on Management of Data. 2628– 2638. [68] Yuke Wang, Boyuan Feng, Zheng Wang, Tong Geng, Kevin Barker, Ang Li, and Yufei Ding. 2023. MGG: Accelerating graph neural networks with Fine-Grained Intra-Kernel Communication-Computation pipelining on Multi-GPU platforms. In 17th USENIX Symposium on Operating Systems Design and Implementation. 779–795. [69] Yuyue Wang, Xiurui Pan, Yuda An, Jie Zhang, and Glenn Reinman. 2024. BeaconGNN: Large-Scale GNN Acceleration with Out-of-Order Streaming InStorage Computing. In IEEE International Symposium on High-Performance Computer Architecture. IEEE, 330–344. 16

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

[70] Zesong Wang, Peng Fang, Fang Wang, Hong Jiang, Yimin Lu, Zhan Shi, and Dan Feng. 2025. SpiderCache: Semantic-Aware Caching Strategy for DNN Training. In Proceedings of the 54th International Conference on Parallel Processing (ICPP’25). 320330. [71] Brian J Worton. 1989. Kernel methods for estimating the utilization distribution in home-range studies. Ecology 70, 1 (1989), 164–168. [72] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. 2022. Nodeformer: A scalable graph structure learning transformer for node classiﬁcation. Advances in Neural Information Processing Systems 35 (2022), 27387–27401. [73] Yidi Wu, Kaihao Ma, Zhenkun Cai, Tatiana Jin, Boyang Li, Chenguang Zheng, James Cheng, and Fan Yu. 2021. Seastar: Vertex-centric programming for graph neural networks. In Proceedings of the 16th European Conference on Computer Systems. 359–375. [74] Jaewon Yang and Jure Leskovec. 2012. Deﬁning and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. 1–8. [75] Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, and Sourav S Bhowmick. 2020. Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank. Prococeding of VLDB Endowment 13, 5 (2020), 670– 683. [76] Tianbao Yang and Yiming Ying. 2022. AUC maximization in the era of big data and AI: A survey. ACM computing surveys 55, 8 (2022), 1–37. [77] Zihao Yu, Ningyi Liao, and Siqiang Luo. 2024. GENTI: GPU-powered Walkbased Subgraph Extraction for Scalable Representation Learning on Dynamic Graphs. Proceedings of the VLDB Endowment 17, 9 (2024), 2269–2278. [78] Reza Zafarani and Huan Liu. 2009. Social Computing Data Repository at ASU. In http://socialcomputing.asu.edu. [79] Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. 2019. ProNE: Fast and Scalable Network Representation Learning. In International Joint Conference on Artiﬁcial Intelligence, Vol. 19. 4278–4284.

[80] J. Zhang, Z. Zhang, Z. Wang, Y. Liu, and L. Deng. 2018. Ontological function annotation of long non-coding RNAs through hierarchical multi-label classiﬁcation. Bioinformatics 34, 10 (2018), 1750–1757. [81] M. Zhang and Z. Zhou. 2006. Multilabel neural networks with applications to functional genomics and text categorization. IEEE Transactions on Knowledge and Data Engineering 18, 10 (2006), 1338–1351. [82] Qinggang Zhang, Shengyuan Chen, Yuanchen Bei, Zheng Yuan, Huachi Zhou, Zijin Hong, Junnan Dong, Hao Chen, Yi Chang, and Xiao Huang. 2025. A survey of graph retrieval-augmented generation for customized large language models. arXiv preprint arXiv:2501.13958 (2025). [83] Shijie Zhang, Hongzhi Yin, Tong Chen, Zi Huang, Lizhen Cui, and Xiangliang Zhang. 2021. Graph embedding for recommendation against attribute inference attacks. In Proceedings of the Web Conference 2021. 3002–3014. [84] Chenguang Zheng, Hongzhi Chen, Yuxuan Cheng, Zhezheng Song, Yifan Wu, Changji Li, James Cheng, Hao Yang, and Shuai Zhang. 2022. ByteGNN: Efﬁcient Graph Neural Network Training at Large Scale. Proceedings of VLDB Endowment 15, 6 (2022), 1228–1242. [85] Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3). IEEE, 36–44. [86] Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. 2019. AliGraph: A Comprehensive Graph Neural Network Platform. Proceedings of VLDB Endowment (2019), 20942105. [87] Liu Ziyin, Kangqiao Liu, Takashi Mori, and Masahito Ueda. 2022. STRENGTH OF MINIBATCH NOISE IN SGD. In 10th International Conference on Learning Representations, ICLR 2022.

Record · ID 299896 · SHA-256 831b25032efcd070
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.