Papers on Graph Analytics

This is a list of papers related to graph analytics, adapted from the material for the course 6.886: Graph Analytics at MIT. The papers are loosely categorized and the list is not comprehensive. This list is maintained by Julian Shun.


The Graph Structure in the Web - Analyzed on Different Aggregation Levels

Kronecker Graphs: An Approach to Modeling Networks

Graph structure in the Web

Power laws and the AS-level internet topology

R-MAT: A Recursive Model for Graph Mining

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications

Statistical mechanics of complex networks

Collective dynamics of 'small-world' networks

The Small-World Phenomenon: An Algorithmic Perspective

Four Degrees of Separation


Graph Algorithms

Direction-Optimizing Breadth-First Search

A Faster Algorithm for Betweenness Centrality

The More the Merrier: Efficient Multi-Source Graph Traversal

A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)

Internally Deterministic Parallel Algorithms Can Be Fast

SlimSell: A Vectorizable Graph Representation for Breadth-First Search

Better Approximation of Betweenness Centrality

ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

Fast approximation of betweenness centrality through sampling

Scalable Betweenness Centrality Maximization via Sampling

Articulation Points Guided Redundancy Elimination for Betweenness Centrality

Betweenness Centrality: Algorithms and Implementations

A Simple and Practical Linear-Work Parallel Algorithm for Connectivity

Multicore Triangle Computations Without Tuning

A Survey of PageRank Computing

Mining the link structure of the World Wide Web

Parallel Graph Decompositions Using Random Shifts

Improved Parallel Algorithms for Spanners and Hopsets

Algorithmic Aspects of Triangle-Based Network Analysis

Triangle Listing Algorithms: Back from the Diversion

The Input/Output Complexity of Triangle Enumeration

I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration

An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs

Greedy Sequential Maximal Independent Set and Matching are Parallel on Average

ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs

HADI: Mining Radii of Large Graphs

HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget

Computing the Eccentricity Distribution of Large Graphs

Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs

Better Approximation Algorithms for the Graph Diameter

A Simple Parallel Algorithm for the Maximal Independent Set Problem

Tight Analysis of Parallel Randomized Greedy MIS

Notes on simple analysis of parallel maximal independent set and maximal matching algorithms

Ordering heuristics for parallel graph coloring

A Parallel Graph Coloring Heuristic

Scalable parallel graph coloring algorithms

A Scalable Parallel Graph Coloring Algorithm for Distributed Memory Computers

Parallel Graph Coloring for Manycore Architectures

Algorithms for Balanced Graph Colorings with Applications in Parallel Computing

Fast algorithms for determining (generalized) core groups in social networks

K-Core Decomposition of Large Networks on a Single PC

Incremental k-core decomposition: algorithms and evaluation

A Fast Order-Based Approach for Core Maintenance

Patterns and Anomalies in k-Cores of Real-World Graphs with Applications

I/O Efficient Core Graph Decomposition at Web Scale

Truss Decomposition in Massive Networks

Truss decomposition on shared-memory parallel systems

Nucleus Decompositions for Identifying Hierarchy of Dense Subgraphs

Local Algorithms for Hierarchical Dense Subgraph Discovery

The k-peak Decomposition: Mapping the Global Structure of Graphs

Peeling Bipartite Networks for Dense Subgraph Discovery

Novel Approaches for Analyzing Biological Networks

When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks

Density-friendly graph decomposition

Delta-stepping: a parallelizable shortest path algorithm

Parallel Shortest Paths Using Radius Stepping

An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances

DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem

Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths

A Randomized Parallel Algorithm for Single-Source Shortest Path

Randomized Speedup of the Bellman-Ford Algorithm

A Parallel Priority Queue with Constant Time Operations

Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable (2018)

Parallel Algorithms for Butterfly Computations (2020)

Parallel Algorithms

Parallel Algorithms

Algorithm Design: Parallel and Sequential

Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques

Scheduling Multithreaded Computations by Work Stealing

Thread Scheduling for Multiprogrammed Multiprocessors

Provably Efficient Scheduling for Languages with Fine-Grained Parallelism

Prefix Sums and Their Applications

Cache-Oblivious Algorithms

Cache-Oblivious Algorithms

Cache-Oblivious Algorithms and Data Structures

Scheduling Irregular Parallel Computations on Hierarchical Caches

External Memory Algorithms

I/O-Complexity of Graph Algorithms

External-Memory Graph Algorithms

A Functional Approach to External Graph Algorithms

Beyond Synchronous: New Techniques for External-Memory Graph Connectivity and Minimum Spanning Forest

Parallel External Memory Graph Algorithms

Efficient Parallel and External Matching

Algorithms and Data Structures for External Memory

Streaming Graph Algorithms

A New Parallel Algorithm for Connected Components in Dynamic Graphs

Work-Efficient Parallel Union-Find

Parallel Batch-Dynamic Graph Connectivity

Faster Betweenness Centrality Updates in Evolving Networks

STINGER: Spatio-Temporal Interaction Networks and Graphs (STING) Extensible Representation

STINGER: High Performance Data Structure for Streaming Graphs

Static and dynamic parallel computation of connected components

Sparsification-A Technique for Speeding Up Dynamic Graph Algorithms

Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation

Faster Worst Case Deterministic Dynamic Connectivity

QUBE: a Quick algorithm for Updating BEtweenness centrality

A Fast Algorithm for Streaming Betweenness Centrality

Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks

Scalable Online Betweenness Centrality in Evolving Graphs

Fully Dynamic Betweenness Centrality Maintenance on Massive Networks

Approximating Betweenness Centrality in Fully Dynamic Networks

Fully Dynamic Betweenness Centrality

ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages

An Experimental Analysis of Self-Adjusting Computation

Packed Compressed Sparse Row: A Dynamic Graph Representation


The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing

Big Graph Analytics Platforms (Survey)

Scalable Graph Processing Frameworks: A Taxonomy and Open Challenges (Survey)

Parallel Graph Analytics

Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets

Architectural Implications on the Performance and Cost of Graph Analytics Systems

Shared Memory

Ligra: A Lightweight Graph Processing Framework for Shared Memory

Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+

Shared-Memory Parallelism Can Be Simple, Fast, and Scalable (Chapters 7-8 contain updated descriptions of Ligra and Ligra+)

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing (2017)

GraphIt: A High-Performance DSL for Graph Analytics (2018)

Optimizing Ordered Graph Algorithms with Graphlt (2020)

Practical Parallel Hypergraph Algorithms (2020)

Scalability! But at what COST?

EmptyHeaded: A Relational Engine for Graph Processing (2017)

GraphLab: A New Framework For Parallel Machine Learning

Green-Marl: A DSL for Easy and Efficient Graph Analysis

A Lightweight Infrastructure for Graph Analytics

GraphMat: High performance graph analytics made productive

Ringo: Interactive Graph Analytics on Big-Memory Machines

Graph Analytics Through Fine-Grained Parallelism

Software and Algorithms for Graph Queries on Multithreaded Architectures

SNAP, Small-world Network Analysis and Partitioning: an open-source parallel graph framework for the exploration of large-scale networks

Everything you always wanted to know about multicore graph processing but were afraid to ask

To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations

Making Pull-Based Graph Processing Performant

Congra: Towards Efficient Processing of Concurrent Graph Queries on Shared-Memory Machines

CongraPlus: Towards Efficient Processing of Concurrent Graph Queries on NUMA Machines (2019)

Using Domain-Specific Languages For Analytic Graph Databases

Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling

Laika: Efficient In-Place Scheduling for 3D Mesh Graph Computations

SociaLite: Datalog Extensions for Efficient Social Network Analysis

Graphphi: efficient parallel graph processing on emerging throughput-oriented architectures (2018)

TuFast: A Lightweight Parallelization Library for Graph Analytics (2019)

PnP: Pruning and Prediction for Point-To-Point Iterative Graph Analytics (2019)

Combining Data Duplication and Graph Reordering to Accelerate Parallel Graph Processing (2019)

Efficient Graph Processing with Invalid Update Filtration (2019)

Improving parallel efficiency for asynchronous graph analytics using Gauss-Seidel-based matrix computation (2019)

Understanding priority-based scheduling of graph algorithms on a shared-memory platform (2019)

Distributed Memory

Pregel: A System for Large-Scale Graph Processing

PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing (Survey)

High-Level Programming Abstractions for Distributed Graph Processing (Survey)

How Well do Graph-Processing Platforms Perform? An Empirical Performance Evaluation and Analysis

Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation

An Experimental Comparison of Pregel-like Graph Processing Systems

An Evaluation and Analysis of Graph Processing Frameworks on Five Key Issues

An Evaluation Study of BigData Frameworks for Graph Processing

The Parallel BGL: A Generic Library for Distributed Graph Computations

The STAPL Parallel Graph Library

Signal/Collect: Graph Algorithms for the (Semantic) Web

GPS: A Graph Processing System

Simplifying Scalable Graph Processing with a Domain-Specific Language

Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud

PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs

Bipartite-Oriented Distributed Graph Partitioning for Big Learning

Exploring the Hidden Dimension in Graph Processing

GraphX: Graph Processing in a Distributed Dataflow Framework

Asynchronous Large-Scale Graph Processing Made Easy

ASPIRE: Exploiting Asynchronous Parallelism in Iterative Algorithms using a Relaxed Consistency based DSM

Efficient Processing of Large Graphs via Input Reduction

Mizan: A System for Dynamic Load Balancing in Large-scale Graph Processing

GoFFish: A Sub-graph Centric Framework for Large-Scale Graph Analytics

KLA: A New Algorithmic Paradigm for Parallel Graph Computations

Computation and Communication Efficient Graph Processing with Distributed Immutable View

SYNC or ASYNC: Time to Fuse for Distributed Graph-Parallel Computation

Scaling Iterative Graph Computations with GraphMap

Presto: Distributed Machine Learning and Graph Processing with Sparse Matrices

From "Think Like a Vertex" to "Think Like a Graph"

NScale: neighborhood-centric large-scale graph analytics in the cloud

High Performance Graph Processing with Locality Oriented Design

TuX2: Distributed Graph Computation for Machine Learning

Latency-Tolerant Software Distributed Shared Memory

Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs

PrIter: A Distributed Framework for Prioritized Iterative Computations

Fast Iterative Graph Computation with Block Updates

Maiter: An Asynchronous Graph Processing Framework for Delta-Based Accumulative Iterative Computation

Parallelizing Sequential Graph Computations

Adaptive Asynchronous Parallelization of Graph Algorithms

GraM: Scaling Graph Computation to the Trillions

LazyGraph: Lazy Data Coherency for Replicas in Distributed Graph-Parallel Computation

One Trillion Edges: Graph Processing at Facebook-Scale

An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing

PGX.D: A Fast Distributed Graph Processing Engine

CoRAL: Confined Recovery in Distributed Asynchronous Graph Processing

Zorro: zero-cost reactive failure recovery in distributed graph processing

PAGE: A Partition Aware Engine for Parallel Graph Computation

MOCgraph: Scalable Distributed Graph Processing Using Message Online Computing

GrapH: Traffic-Aware Graph Processing

Vertexica: Your Relational Friend for Graph Analytics!

Graph Analytics using Vertica Relational Database

GraphiQL: A Graph Intuitive Query Language for Relational Databases

The case against specialized graph analytics engines

SHMEMGraph: Efficient and Balanced Graph Processing Using One-sided Communication

LightGraph: Lighten Communication in Distributed Graph-Parallel Processing

L-PowerGraph: a lightweight distributed graph-parallel communication mechanism

DH-Falcon: A language for large-scale graph processing on Distributed Heterogeneous systems

A Lightweight Communication Runtime for Distributed Graph Analytics

Gluon: A Communication-Optimizing Substrate for Distributed Heterogeneous Graph Analytics

Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing Systems

Hieroglyph: Locally-Sufficient Graph Processing via Compute-Sync-Merge

A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters

Processing Concurrent Graph Analytics with Decoupled Computation Model

A High-Level Framework for Distributed Processing of Large-Scale Graphs

Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters

LCC-Graph: A High-Performance Graph-Processing Framework with Low Communication Costs

Global Graphs: A Middleware For Large Scale Graph Processing

Distributed SociaLite: A Datalog-Based Language for Large-Scale Graph Analysis

ShenTu: processing multi-trillion edge graphs on millions of cores in seconds

Pregelix: Big(ger) Graph Analytics on A Dataflow Engine

Phoenix: A Substrate for Resilient Distributed Graph Analytics (2019)

GraphA: Efficient Partitioning and Storage for Distributed Graph Computation

Start Late or Finish Early: A Distributed Graph Processing System with Redundancy Reduction (2019)

A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms (2019)

Ariadne: Online Provenance for Big Graph Analytics (2019)

TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing (2019)

Dynamic Scaling for Parallel Graph Computations (2019)

Gluon-Async: A Bulk-Asynchronous System for Distributed and Heterogeneous Graph Analytics (2019)

External Memory

GraphChi: Large-Scale Graph Computation on Just a PC (2012)

MOSAIC: Processing a Trillion-Edge Graph on a Single Machine (2017)

GraFBoost: Using accelerated flash storage for external graph analytics (2018)

X-Stream: Edge-centric Graph Processing using Streaming Partitions (2013)

TurboGraph: A Fast Parallel Graph Engine Handling Billion-scale Graphs in a Single PC (2013)

TurboGraph++: A Scalable and Fast Graph Analytics System (2018)

MMap: Fast Billion-Scale Graph Computation on a PC via Memory Mapping (2014)

PrefEdge: SSD Prefetcher for Large-Scale Graph Traversal (2014)

PathGraph: A Path Centric Graph Processing System (2016)

GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning (2015)

VENUS: A System for Streamlined Graph Computation on a Single PC (2016)

NXgraph: An Efficient Graph Processing System on a Single Machine (2016)

Chaos: Scale-out graph processing from secondary storage (2015)

FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs (2015)

Clip: A Disk I/O Focused Parallel Out-of-Core Graph Processing System (2019)

Hybrid Pulling/Pushing for I/O-Efficient Distributed and Iterative Graph Computing (2016)

Graphene: Fine-Grained IO Management for Graph Computing (2017)

Load the Edges You Need: A Generic I/O Optimization for Disk-based Graph Processing (2016)

Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code (2017)

Wonderland: A Novel Abstraction-Based Out-Of-Core Graph Processing System (2018)

GraphD: Distributed Vertex-Centric Graph Processing Beyond the Memory Limit (2018)

GraphH: High Performance Big Graph Analytics in Small Clusters (2017)

GPSA: A Graph Processing System with Actors (2015)

AsyncStripe: I/O Efficient Asynchronous Graph Computing on a Single Server (2016)

CGraph: A Correlations-aware Approach for Efficient Concurrent Iterative Graph Processing (2018)

Grapple: A Graph System for Static Finite-State Property Checking of Large-Scale Systems Code (2019)

GraphMP: An Efficient Semi-External-Memory Big Graph Processing System on a Single Machine (2017)

RealGraph: A Graph Engine Leveraging the Power-Law Distribution of Real-World Graphs (2019)

Large-Scale Graph Processing on Emerging Storage Devices (2019)

Pre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines (2019)

LUMOS: Dependency-Driven Disk-based Graph Processing (2019)

GraphSSD: graph semantics aware SSD (2019)

PartitionedVC: Partitioned External Memory Graph Analytics Framework for SSDs


Graph Processing on GPUs: A Survey (Survey of GPU graph processing)

Garaph: Efficient GPU-accelerated Graph Processing on a Single Machine with Balanced Replication

A Distributed Multi-GPU System for Fast Graph Processing

Tigr: Transforming Irregular Graphs for GPU-Friendly Graph Processing

Gunrock: GPU Graph Analytics

Multi-GPU Graph Analytics

Puffin: Graph Processing System on Multi-GPUs

Medusa: Simplified Graph Processing on GPUs

MapGraph: A High Level API for Fast Development of High Performance Graph Analytics on GPUs

CuSha: Vertex-Centric Graph Processing on GPUs

Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems

Efficient graph computation on hybrid CPU and GPU systems

Optimizing Graph Processing on GPUs

Graph Processing on GPUs: Where are the Bottlenecks?

GPU Concurrency Choices in Graph Analytics

Performance Characterization of High-Level Programming Models for GPU Graph Analytics

GTS: A Fast and Scalable Graph Processing Method based on Streaming Topology to GPUs

Frog: Asynchronous Graph Processing on GPU with Hybrid Coloring Model

GBTL-CUDA: Graph Algorithms and Primitives for GPUs

LightHouse: An Automatic Code Generator for Graph Algorithms on GPUs

GraphReduce: Processing Large-Scale Graphs on Accelerator-Based Systems

EvoGraph: On-the-Fly Efficient Mining of Evolving Graphs on GPU

cuSTINGER: Supporting Dynamic Graph Aigorithms for GPUs

Autonomous, Independent Management of Dynamic Graphs on GPUs

Accelerating Dynamic Graph Analytics on GPUs

Graphie: Large-Scale Asynchronous Graph Traversals on Just a GPU

A Compiler for Throughput Optimization of Graph Algorithms on GPUs

Falcon: A Graph Manipulation Language for Heterogeneous Systems

MultiGraph: Efficient Graph Processing on GPUs

Scalable SIMD-Efficient Graph Processing on GPUs

Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs

Abelian: A Compiler for Graph Analytics on Distributed, Heterogeneous Platforms

faimGraph: high performance management of fully-dynamic graphs under tight memory constraints on the GPU

SEP-graph: finding shortest execution paths for graph processing under a hybrid framework on GPU (2019)

A pattern based algorithmic autotuner for graph processing on GPUs (2019)

Large-Scale Graph Processing on Emerging Storage Devices (2019)

DiGraph: An Efficient Path-based Iterative Directed Graph Processing System on Multiple GPUs (2019)

GPU-based Graph Traversal on Compressed Graphs (2019)

SIMD-X: Programming and Processing of Graph Algorithms on GPUs (2019)

Linear Algebra

Mathematical Foundations of the GraphBLAS

GraphMat: High performance graph analytics made productive

The Combinatorial BLAS: design, implementation, and applications

A Flexible Open-Source Toolbox for Scalable Complex Graph Analysis

High-Productivity and High-Performance Analysis of Filtered Semantic Graphs

GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms

PEGASUS: Mining Peta-Scale Graphs

Tiled Linear Algebra a System for Parallel Graph Algorithms

Graphulo: Linear Algebra Graph Kernels for NoSQL Databases

Design of the GraphBLAS API for C

GBTL-CUDA: Graph Algorithms and Primitives for GPUs

LA3: A Scalable Link- and Locality-Aware Linear Algebra-Based Graph Analytics System

Implementing Push-Pull Efficiently in GraphBLAS

Graph Algorithms in the Language of Linear Algebra

Streaming and Temporal

LLAMA: Efficient graph analytics using Large Multiversioned Arrays

GraphIn: An Online High Performance Incremental Graph Processing Framework

KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations

STINGER: Spatio-Temporal Interaction Networks and Graphs (STING) Extensible Representation

STINGER: High Performance Data Structure for Streaming Graphs

DISTINGER: A Distributed Graph Data Structure for Massive Dynamic Graph Processing

On Querying Historical Evolving Graph Sequences

Naiad: A Timely Dataflow System

Differential dataflow

Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows

Facilitating Real-Time Graph Mining

Kineograph: Taking the Pulse of a Fast-Changing and Connected World

Tornado: A System For Real-Time Iterative Analysis Over Evolving Data

Chronos: a graph engine for temporal graph analysis

Time-Evolving Graph Processing at Scale

Real-time Analytics for Fast Evolving Social Graphs

Synergistic Analysis of Evolving Graphs

Towards Large-Scale Graph Stream Processing Platform

ImmortalGraph: A System for Storage and Analysis of Temporal Graphs

Efficient Snapshot Retrieval over Historical Graph Data

Storing and Analyzing Historical Graph Data at Scale

Towards a Distributed Large-Scale Dynamic Graph Data Store

GraphJet: Real-Time Content Recommendations at Twitter

Automatic Algorithm Transformation for Efficient Multi-Snapshot Analytics on Temporal Graphs

CellIQ : Real-Time Cellular Network Analytics at Scale

GraPU: Accelerate Streaming Graph Analysis through Preprocessing Buffered Updates

GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs

GraphOne: A Data Store for Real-time Analytics on Evolving Graphs (2020)

Low-Latency Graph Streaming Using Compressed Purely-Functional Trees (2019)

Locality Optimizations

Locality Exists in Graph Processing: Workload Characterization on an Ivy Bridge Server

Making Caches Work for Graph Analytics

Reducing Pagerank Communication via Propagation Blocking

Optimizing Indirect Memory References with milk

Parallel Graph Processing: Prejudice and State of the Art

Gemini: A Computation-Centric Distributed Graph Processing System

GraphGrind: Addressing Load Imbalance of Graph Partitioning

NUMA-Aware Graph-Structured Analytics

Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning

Accelerating PageRank using Partition-Centric Processing

GPOP: A cache- and work-efficient framework for Graph Processing Over Partitions


Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+

An Experimental Analysis of a Compact Graph Representation

The WebGraph Framework I: Compression Techniques

Compressed representations for web and social graphs

Compact Representations of Separable Graphs

Towards Compressing Web Graphs

The Link database: Fast access to graphs of the Web

The WebGraph Framework II: Codes For The World Wide Web

Fast and Compact Web Graph Representations

Practical Representations for Web and Social Graphs

k2-Trees for Compact Web Graph Representation

Efficient Compression of Web Graphs

Neighbor Query Friendly Compression of Social Networks

Speeding up Algorithms on Compressed Web Graphs

Tight and simple Web graph compression for forward and reverse neighbor queries

Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication

A scalable pattern mining approach to web graph compression with communities

Graph Summarization Methods and Applications: A Survey

Graph Summarization with Bounded Error

Query preserving graph compression

Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)

Slim graph: practical lossy graph compression for approximate graph processing, storage, and analytics (2019)

Partitioning and Reordering

A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

Compressing Graphs and Indexes with Recursive Graph Bisection

Speedup Graph Processing by Graph Ordering

Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks

On Compressing Social Networks

SlashBurn: Graph Compression and Mining beyond Caveman Communities

Order or Shuffle: Empirically Evaluating Vertex Order Impact on Parallel Graph Computations

ReCALL: Reordered Cache Aware Locality based Graph Processing

Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis

Graph Compression by BFS

Permuting Web Graphs

When is Graph Reordering an Optimization?

A Multilevel Algorithm for Partitioning Graphs

Recent Advances in Graph Partitioning (Survey of graph partitioning methods)

A Tutorial on Spectral Clustering (Overview of spectral partitioning)

Allow Me to Introduce Spectral and Isoperimetric Graph Partitioning (Overview of spectral partitioning)

Spectral partitioning with multiple eigenvectors

Weighted Graph Cuts without Eigenvectors: A Multilevel Approach

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly Linear Time Graph Partitioning

Geometry, Flows, and Graph-Partitioning Algorithms

METIS Software and Publications

Karlsruhe High Quality Partitioning Software and Publications

Subgraph Finding

DualSim: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine

ScaleMine: Scalable Parallel Frequent Subgraph Mining in a Single Large Graph

ESCAPE: Efficiently Counting All 5-Vertex Subgraphs

Biological network motif detection: principles and practice

Network Motifs: Simple Building Blocks of Complex Networks

Biomolecular network motif counting and discovery by color coding

Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking

MODA: an efficient algorithm for network motif discovery in biological networks

NeMoFinder: Dissecting genome-wide protein-protein interactions with meso-scale network motifs

Efficient sampling algorithm for estimating sub-graph concentrations and detecting network motifs

Efficient detection of network motifs

Kavosh: a new algorithm for finding network motifs

Efficient Subgraph Frequency Estimation with G-Tries

Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks

Parallel discovery of network motifs

Network Motif Discovery: A GPU Approach

EmptyHeaded: A Relational Engine for Graph Processing (2017)

Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins (2019)

Arabesque: A System for Distributed Graph Mining

Skew Strikes Back: New Developments in the Theory of Join Algorithms

Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows

TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

Distributed Estimation of Graph 4-Profiles

Estimation of Local Subgraph Counts

Counting Graphlets: Space vs Time

Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts

Graphlet decomposition: framework, algorithms, and applications

Mining Graphlet Counts in Online Social Networks

A General Framework for Estimating Graphlet Statistics via Random Walk

Graft: An Efficient Graphlet Counting Method for Large Graph Analysis

Scalable Distributed Subgraph Enumeration

GraphQ: Graph Query Processing with Abstraction Refinement-Scalable and Programmable Analytics over Very Large Graphs on a Single PC

GraMi: Frequent Subgraph and Pattern Mining in a Single Large Graph

Parallel Subgraph Listing in a Large-Scale Graph

Parallel Subgraph Counting for Multicore Architectures

SAHAD: Subgraph Analysis in Massive Networks Using Hadoop

TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data

ASAP: Fast, Approximate Graph Pattern Mining at Scale

RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine

Complex Network Analysis using Parallel Approximate Motif Counting

Shared Memory Parallel Subgraph Enumeration

A Multi-Level Parallel Implementation of a Program for Finding Frequent Patterns in a Large Sparse Graph

Subgraph Matching: on Compression and Computation

PruneJuice: pruning trillion-edge graphs to a precise pattern-matching solution

G-Miner: an efficient task-oriented graph mining system

Fractal: A General-Purpose Graph Pattern Mining System (2019)

Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together (2019)

A survey of frequent subgraph mining algorithms (Survey)

A Survey of Algorithms for Dense Subgraph Discovery (Survey)

The K-clique Densest Subgraph Problem

On Finding Dense Subgraphs

Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees

Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling

Distributed Subgraph Matching on Timely Dataflow (2019)

Fast and Robust Distributed Subgraph Enumeration (2019)

Efficient Algorithms for Densest Subgraph Discovery (2019)

CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching (2019)

BENU: Distributed Subgraph Enumeration with Backtracking-Based Framework (2019)

Scaling Up Subgraph Query Processing with Efficient Subgraph Matching (2019)

AutoMine: harmonizing high-level abstraction and high performance for graph mining (2019)

GraphM: an efficient storage system for high throughput of concurrent graph processing (2019)

Efficient Parallel Subgraph Enumeration on a Single Machine (2019)

More dense subgraph discovery papers

Clustering and Community Detection

Parallel Local Graph Clustering

Community detection in graphs (Survey of methods)

Community structure in social and biological networks

Modularity and community structure in networks

Uncovering the overlapping community structure of complex networks in nature and society

Fast unfolding of communities in large networks

On Modularity Clustering

Fast algorithm for detecting community structure in networks

Community detection algorithms: a comparative analysis

Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters

Empirical Comparison of Algorithms for Network Community Detection

Think locally, act locally: Detection of small, medium-sized, and large communities in large networks

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly Linear Time Graph Partitioning

Local Graph Partitioning using PageRank Vectors

Scalable Motif-aware Graph Clustering

Local Higher-Order Graph Clustering

An Optimization Approach to Locally-Biased Graph Algorithms

A Simple and Strongly-Local Flow-Based Method for Cut Improvement

Flow-Based Algorithms for Local Graph Clustering

A Local Algorithm for Finding Well-Connected Clusters

Heat Kernel Based Community Detection

Higher-order organization of complex networks

Graph Clustering Via a Discrete Uncoupling Process

Scalable Discovery of Best Clusters on Large Graphs

Community detection in large-scale networks: a survey and empirical evaluation

Local Search of Communities in Large Graphs

Databases and RDF Query Engines

TAO: Facebook's Distributed Data Store for the Social Graph (2013)

The Little Engine(s) That Could: Scaling Online Social Networks (2012)

Fast and Concurrent RDF Queries with RDMA-Based Distributed Graph Exploration (2016)

Sub-millisecond Stateful Stream Querying over Fast-evolving Linked Data (2017)

RDF in the clouds: a survey (Survey)

A Survey and Experimental Comparison of Distributed SPARQL Engines for Very Large RDF Data (Survey)

Survey of Graph Database Models (Survey)

ZipG: A Memory-efficient Graph Store for Interactive Queries

Trinity: A Distributed Graph Engine on a Memory Cloud

A Distributed Graph Engine for Web Scale RDF Data

Hexastore: Sextuple Indexing for Semantic Web Data Management

Weaver: A High-Performance, Transactional Graph Database Based on Refinable Timestamps

Managing Large Graphs on Multi-Cores With Graph Awareness

G-SQL: Fast Query Processing via Graph Exploration

A General-Purpose Query-Centric Framework for Querying Big Graphs

G-SPARQL: A Hybrid Engine for Querying Large Attributed Graphs

gStore: a graph-based SPARQL query engine

G-Store: High-Performance Graph Store for Trillion-Edge Processing

Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs

Scalable SPARQL Querying of Large RDF Graphs

S2RDF: RDF Querying with SPARQL on Spark

Combining Vertex-Centric Graph Processing with SPARQL for Large-Scale RDF Data Analytics

Processing SPARQL queries over distributed RDF graphs

EAGRE: Towards Scalable I/O Efficient SPARQL Query Evaluation on the Cloud

Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning

Accelerating SPARQL queries by exploiting hash-based locality and adaptive partitioning

The RDF-3X engine for scalable management of RDF data

Cypher: An Evolving Query Language for Property Graphs (2018)

Updating Graph Databases with Cypher (2019)

PGQL: a Property Graph Query Language

Graphs-at-a-time: Query Language and Access Methods for Graph Databases

T-SPARQL: A TSQL2-Like Temporal Query Language for RDF

The G* graph database: efficiently managing large distributed dynamic graphs

Fast In-Memory SQL Analytics on Typed Graphs

TriAD: A Distributed Shared-Nothing RDF Engine based on Asynchronous Message Passing

Unicorn: A System for Searching the Social Graph

GraphCache: A Caching System for Graph Queries

H2RDF+: High-performance Distributed Joins over Large-scale RDF Graphs

Graph-Aware, Workload-Adaptive SPARQL Query Caching

Scalable Join Processing on Very Large RDF Graphs

Building an Efficient RDF Store Over a Relational Database

SQLGraph: An Efficient Relational-Based Property Graph Store

TripleBit: a Fast and Compact System for Large Scale RDF Data

Matrix "Bit"loaded: A Scalable Lightweight Join Query Processor for RDF Data

Towards Effective Partition Management for Large Graphs

Taming Subgraph Isomorphism for RDF Query Processing

On Smart Query Routing: For Distributed Graph Querying with Decoupled Storage

An Analytics-Aware Conceptual Model For Evolving Graphs

G-CORE: A Core for Future Graph Query Languages

A Graph Database for a Virtualized Network Infrastructure

GraphFrames: An Integrated API for Mixing Graph and Relational Queries

Fast and Concurrent RDF Queries using RDMA-assisted GPU Graph Exploration

Matrix Algebra Framework for Portable, Scalable and Efficient Query Engines for RDF Graphs

Graphflow: An Active Graph Database (2017)

Beyond Macrobenchmarks: Microbenchmark-based Graph Database Evaluation (2019)

Nanosecond Indexing of Graph Data With Hash Maps and VLists (2019)

Optimizing Declarative Graph Queries at Large Scale (2019)

Helios: An Adaptive and Query Workload-driven Partitioning Framework for Distributed Graph Stores (2019)

Pragh: Locality-preserving Graph Traversal with Split Live Migration (2019)


A Survey on Graph Processing Accelerators: Challenges and Opportunities (2019)

Graph Prefetching Using Data Structure Knowledge

IMP: Indirect Memory Prefetcher

Software Prefetching for Indirect Memory Accesses

An Event-Triggered Programmable Prefetcher for Irregular Workloads

A Scalable Architecture for Ordered Parallelism

Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling

Graphicionado: A High-Performance and Energy-Efficient Accelerator for Graph Analytics

Novel Graph Processor Architecture, Prototype System, and Results

A Scalable Processing-in-Memory Accelerator for Parallel Graph Processing

GraphOps: A Dataflow Library for Graph Analytics Acceleration

FPGP: Graph Processing Framework on FPGA

TuNao: A High-Performance and Energy-Efficient Reconfigurable Accelerator for Graph Processing

GraphR: Accelerating Graph Processing Using ReRAM

GraphP: Reducing Communication for PIM-based Graph Processing with Efficient Data Partition

Energy Efficient Architecture for Graph Analytics Accelerators

ForeGraph: Exploring Large-scale Graph Processing on Multi-FPGA Architecture

GraphGen: An FPGA Framework for Vertex-Centric Graph Computation

High-throughput and Energy-efficient Graph Processing on FPGA

Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism

Data-Centric Execution of Speculative Parallel Programs

SAM: optimizing multithreaded cores for speculative parallelism

Harmonizing Speculative and Non-Speculative Execution in Architectures for Ordered Parallelism

Accelerating Graph Analytics on CPU-FPGA Heterogeneous Platform

OSCAR: Optimizing SCrAtchpad Reuse for Graph Processing

Minnow: Lightweight Offload Engines for Worklist Management and Worklist-Directed Prefetching

Efficient Synthesis of Graph Methods: a Dynamically Scheduled Architecture

High Level Synthesis of RDF Queries for Graph Analytics

GraphPIM: Enabling Instruction-Level PIM Offloading in Graph Computing Frameworks

ExtraV: Boosting Graph Processing Near Storage with a Coherent Accelerator

Heterogeneous Memory Subsystem for Natural Graph Analytics

An efficient graph accelerator with parallel data conflict management

HyVE: Hybrid Vertex-Edge Memory Hierarchy for Energy-Efficient Graph Processing (2019)

Analysis and Optimization of the Memory Hierarchy for Graph Processing Workloads (2019)

GraphH: A Processing-in-Memory Architecture for Large-Scale Graph Processing (2019)

Balancing Memory Accesses for Energy-Efficient Graph Analytics Accelerators (2019)

GraphIA: an in-situ accelerator for large-scale graph processing (2018)

SCU: a GPU stream compaction unit for graph processing (2019)


Brief Announcement: The Problem Based Benchmark Suite

The GAP Benchmark Suite

Graph 500

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors

CRONO: A Benchmark Suite for Multithreaded Graph Algorithms Executing on Futuristic Multicores

GraphBIG: Understanding Graph Computing in the Context of Industrial Solutions

LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms

The LDBC Social Network Benchmark: Interactive Workload

LinkBench: a Database Benchmark Based on the Facebook Social Graph

XGDBench: A Benchmarking Platform for Graph Stores in Exascale Clouds

LUBM: A Benchmark for OWL Knowledge Base Systems

The Berlin SPARQL Benchmark

SP2Bench: A SPARQL Performance Benchmark

Diversified Stress Testing of RDF Data Management Systems

LargeRDFBench: A billion triples benchmark for SPARQL endpoint federation

DBpedia SPARQL Benchmark - Performance Assessment with Real Queries on Real Data

FedBench: A Benchmark Suite for Federated Semantic Data Query Processing

BioBenchmark Toyama 2012: an evaluation of the performance of triple stores on biological data

HiBISCuS: Hypergraph-Based Source Selection for SPARQL Endpoint Federation

GARDENIA: A Graph Processing Benchmark Suite for Next-Generation Accelerators (2019)

Sparse matrix storage and sparse matrix-vector multiply (SpMV)

Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication Using Compressed Sparse Blocks

On the Representation and Multiplication of Hypersparse Matrices

Reduced-Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication

Accelerating Sparse Matrix Computations via Data Compression

Hierarchical Diagonal Blocking and Precision Reduction Applied to Combinatorial Multigrid

Exploiting Compression Opportunities to Improve SpMxV Performance on Shared Memory Systems

An Extended Compression Format for the Optimization of Sparse Matrix-Vector Multiplication

Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors

Automatically Tuning Sparse Matrix-Vector Multiplication for GPU Architectures

Model-driven Autotuning of Sparse Matrix-Vector Multiply on GPUs

A new approach for sparse matrix vector product on NVIDIA GPUs

clSpMV: A Cross-Platform OpenCL SpMV Framework on GPUs

SMAT: An Input Adaptive Auto-Tuner for Sparse Matrix-Vector Multiplication

Optimization of sparse matrix-vector multiplication using reordering techniques on GPUs

Accelerating Sparse Matrix-Vector Multiplication on GPUs using Bit-Representation-Optimized Schemes

Efficient Sparse Matrix-Vector Multiplication on x86-Based Many-Core Processors

A Unified Sparse Matrix Data Format for Efficient General Sparse Matrix-Vector Multiplication on Modern Processors with Wide SIMD Units

Efficient Sparse Matrix-Vector Multiplication on GPUs using the CSR Storage Format

Fast Sparse Matrix-Vector Multiplication on GPUs for Graph Applications

An Efficient Two-Dimensional Blocking Strategy for Sparse Matrix-Vector Multiplication on GPUs

CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication

GPU accelerated sparse matrix-vector multiplication and sparsematrix-transpose vector multiplication

Optimizing and Auto-Tuning Scale-Free Sparse Matrix-Vector Multiplication on Intel Xeon Phi

Automatic Selection of Sparse Matrix Representation on GPUs

LightSpMV: Faster CSR-based Sparse Matrix-Vector Multiplication on CUDA-enabled GPUs

Structural Agnostic SpMV: Adapting CSR-Adaptive for Irregular Matrices

A Cross-Platform SpMV Framework on Many-Core Architectures

Merge-based Parallel Sparse Matrix-Vector Multiplication

A work-efficient parallel sparse matrix-sparse vector multiplication algorithm

Dynamic Sparse-Matrix Allocation on GPUs

Evaluation Criteria for Sparse Matrix Storage Formats (Contains citations for many sparse matrix storage formats)

The Tensor Algebra Compiler

Conflict-Free Symmetric Sparse Matrix-Vector Multiplication on Multicore Architectures (2019)

Near-memory data transformation for efficient sparse matrix multi-vector multiplication (2019)


Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Networks, Crowds, and Markets by David Easley and Jon Kleinberg

Mining Massive Data Sets by Jure Leskovec, Anand Rajaraman, and Jeffrey Ullman

Introduction to Parallel Algorithms by Joseph JaJa

Courses on Graph Analytics

Graph Analytics (Julian Shun, MIT)

Algorithm Engineering (Julian Shun, MIT)

Networks (Daron Acemoglu and Asu Ozdaglar, MIT)

Analysis of Networks (Jure Leskovec, Stanford)

Networks (David Easley and Jon Kleinberg, Cornell)

Topics in Social Data (Johan Ugander, Stanford)

Network Theory (Mark Newman, University of Michigan)

Graphs and Networks (Dan Spielman, Yale)

Statistical Network Analysis (Jennifer Neville, Purdue)

Network Analysis and Modeling (Aaron Clauset, Sante Fe Institute)

Parallel Graph Analysis (George Slota, RPI)

Large-Scale Graph Mining (A. Erdem Sariyuce, University of Buffalo)

Mining Large-scale Graph Data (Danai Koutra, University of Michigan)

Data Mining meets Graph Mining (Leman Akoglu, Stony Brook)

Graphs and Networks (Charalampos Tsourakakis, Aalto University)

Large-Scale Graph Processing (Keval Vora, Simon Fraser University)