Introduction to Graph Computing and the JoyGraph System

Graph Computing Overview

Graph computing systems and graph database systems share many similarities, but they differ in several key aspects such as real‑time requirements, load type, input data format, optimization focus, transaction consistency, and fault tolerance.

Graph Computing System

Graph Database

Real‑time

offline

online

Load Type

graph algorithms

query (requires query language)

Input Data Format

abstract graph

business graph

Optimization Focus

iterative graph traversal

high‑concurrency writes and queries

Transaction & Consistency

not required

highly required

Fault Tolerance

less considered

needs careful handling, especially in distributed mode

Figure comparing GraphX and Neo4j (image omitted for brevity).

Challenges of Graph Computing Systems

Illustration of typical difficulties (image omitted).

Common Graph Computing Systems

Key systems influencing JoyGraph implementation:

Pregel

Bulk‑Asynchronous‑Processing, vertex‑centric model, combiner & aggregator to reduce communication.

Ligra

Pull/push modes for dense and sparse graphs, coordinated scheduling.

Polymer

NUMA‑aware performance improvements.

GraphChi

Parallel‑Sliding‑Window for cache efficiency, incremental computation on dynamic graphs.

GraphX

Built on RDD, strong expressive power, easy ETL integration.

XStream

Edge‑centric, streaming unordered edge lists.

PowerGraph

Handles power‑law graphs, GAS model, multiple vertex‑partitioning strategies, three execution modes, delta‑cache.

Galois

Fine‑grained tasks, topology‑aware work‑stealing scheduler, speculative execution.

Gemini

Extends pull/push to distributed environments, chunk‑based partitioning, dual compression vertex indices.

GMiner

Optimized for computation‑intensive and memory‑intensive graph mining workloads.

JoyGraph Overview

JoyGraph is a graph‑processing framework that implements a vertex‑centric model with the following core data structures:

Adjacency lists for inbound/outbound edges and corresponding index arrays.

Vertex interval partitioning.

Auxiliary bitmap and vertex array.

Multi‑Level Partition (see “Load Balancing”).

Architecture diagram (image omitted).

NUMA‑Aware Design

NUMA (Non‑Uniform Memory Access) architectures provide roughly twice the bandwidth and half the latency for local memory accesses compared to remote accesses; exploiting NUMA is crucial for graph‑computing performance, influencing both graph construction and runtime load balancing.

Illustration of NUMA impact (image omitted).

Graph Computation Execution Process

Typical vertex‑centric execution: a user‑defined update function modifies a vertex and its neighbors, votes for activity, and JoyGraph handles concurrency internally.

Execution flow diagram (image omitted).

The system dynamically chooses between push and pull modes based on vertex degree and edge density to minimize cost.

Push/Pull Dual Mode

Diagram showing the two modes (image omitted).

Load Balancing

JoyGraph leverages both static and dynamic load‑balancing strategies to fully utilize NUMA and multi‑core resources.

Static Load Balancing: Two‑stage vertex partitioning – first by socket (NUMA node) to evenly distribute edge sets, then by core within each socket.

Dynamic Load Balancing: Work‑stealing where idle threads steal work from others, preferring tasks on the same socket before crossing sockets.

Summary and Outlook

JoyGraph currently supports algorithms such as LPA, Louvain, CC, SCC, WCC, MSSP, APSP, and provides extensible interfaces for custom algorithm development (load, parse, filter, graph initialization, dense/sparse vertex updates, I/O, etc.).

Future directions include:

Developing an in‑house graph database engine to embed OLAP capabilities.

Integrating graph visualization and scheduling services for “process‑as‑a‑service”.

Expanding the algorithm library and continuously optimizing performance.

Offering an online notebook‑style interactive platform for end‑to‑end graph algorithm development, analysis, and deployment, integrated into the “Turing” platform.