{'fraction_non_alphanumeric': 0.034402241594022415, 'fraction_numerical': 0.009417808219178082, 'mean_word_length': 4.6728476821192055, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs

Accelerating research in the emerging field of deep graph learning requires new tools. Such systems should support graph as the core abstraction and take care to maintain both forward (i.e. supporting new research ideas) and backward (i.e. integration with existing components) compatibility. In this paper, we present Deep Graph Library (DGL). DGL enables arbitrary message handling and mutation operators, flexible propagation rules, and is framework agnostic so as to leverage high-performance tensor, autograd operations, and other feature extraction modules already available in existing frameworks. DGL carefully handles the sparse and irregular graph structure, deals with graphs big and small which may change dynamically, fuses operations, and performs auto-batching, all to take advantages of modern hardware. DGL has been tested on a variety of models, including but not limited to the popular Graph Neural Networks (GNN) and its variants, with promising speed, memory footprint and scalability.


INTRODUCTION
Learning from structured data like graphs is widely regarded as an important problem (Wu et al., 2019b), because the graph is inherently a more general form of data structure than tensors. A broad range of models can be unified as either learning from explicit or inferring latent structures. Examples include TreeLSTM  that works on sentence parsing trees, Capsule Network  and Transformer  that learns soft connections among entities (e.g. capsules, words). Recently, Graph neural networks (GNNs) is a rising family of models that aim to model a set of node entities together with their relationships (edges). The application regime of the GNN framework is broad, such as chemical molecules, social networks, knowledge graphs and recommender systems Hamilton et al., 2018;.
Unfortunately, existing tensor-based frameworks (e.g. Tensorflow, Pytorch, MXNet) lack intuitive support for this trend of deep graph learning. Specifically, GNNs are defined using the message passing paradigm (Gilmer et al., 2017), which can be seen as a model inductive bias to facilitate information flow across the graph. However, tensor-based frameworks do not support the messagepassing interface. As such, researchers need to manually emulate graph computation using tensor operations, which poses an implementation challenge.
During the past year we have seen the release of several graph training systems Ma et al., 2018;Alibaba, 2019;Fey & Lenssen, 2019). However, most if not all of these libraries compromise programming flexibility to boost the performance of a narrow range of GNNs, as we briefly summarize in the Table 1. As research on deep graph learning is going to evolve and iterate quickly, we dive in to the source of graph learning problems to provide a more comprehensive graph-oriented solution, the Deep Graph Library (DGL) 1 . Accepted as a workshop paper at ICLR 2019 Currently, with DGL, we provide 1) graph as the central abstraction for users; 2) flexible APIs allowing arbitrary message-passing computation over a graph; 3) support for gigantic and dynamic graphs; 4) efficient memory usage and high training speed.
DGL is platform-agnostic so that it can easily be integrated with tensor-oriented frameworks like PyTorch and MXNet. It is an open-source project under active development. Appendix A summarizes the models released in DGL repository. In this paper, we compare DGL against the state-ofthe-art library on multiple standard GNN setups and show the improvement of training speed and memory efficiency.

FRAMEWORK REQUIREMENTS OF DEEP LEARNING ON GRAPHS
Message passing paradigm. Formally, we define a graph G(V, E). V is the set of nodes with v i being the feature vector associated with each node. E is the set of the edge tuples (e k , r k , s k ), where s k → r k represents the edge from node s k to r k , and e k is feature vector associated with the edge. DGNs are defined by the following edge-wise and node-wise computation: In Equation 1, φ e is a message function defined on each edge to generate a "message" by combining the edge feature with node features at its two ends; φ v is an update function defined on each node to update the node feature by aggregating its incoming messages using the reduce operation ⊕. In GNNs, these functions are parameterized by neural network modules, ⊕ can be a sum operation, or mean, max/min, or even an LSTM network . Recent study on the theoretical capability of GNNs (Xu et al., 2018) revealed the limitation of simple reduce operations. Thus, it is crucial for the graph learning system to be flexible and let users express arbitrary φ e , φ v and ⊕.
Propagation order. The message passing paradigm defines the computation on each node/edge while the propagation order determines how messages are propagated. One can trigger the computation synchronously (Kipf & Welling, 2017;Ying et al., 2018b) (full propagation), or following a certain order like TreeLSTM  and Belief Propagation ) (partial propagation), or on some random walks (Perozzi et al., 2014;Grover & Leskovec, 2016) and sampled subgraphs . All said, the propagation aspect is another crucial aspect to consider.
Graph type. One dimension to categorize graphs has to do with scale and instances: • datasets containing many moderately-sized graph samples such as molecule structures. For this type of dataset, each graph can easily fit into a single GPU, which leaves the main performance challenge to be batching and training across multiple GPUs. • datasets containing one potentially giant graph, such as the social network, knowledge graph and the user-item bipartite graph for recommendation. Here, it is non-trivial to keep the memory footprint under budget, especially when node and edge features have a large dimension.
The second dimension is whether they are static. Dynamic graphs are particularly important in generative models, for example to infer latent graph structure which is crucial in relational reasoning AI . Graph mutation occurs from time to time, e.g. by adding/removing nodes/edges  or pooling (Ying et al., 2018b). Finally, no graphs are born giant, they grow to be (e.g. a knowledge graph); it is important to keep this evolution viewpoint in mind.
Obviously, the above categorization is not mutually exclusive and a complete model can embrace multiple aspects, depending on model dynamics, dataset type or optimization algorithm design.

DEEP GRAPH LIBRARY
In this section, we focus on the core design of DGL's APIs and its system performance optimization.   (Hagberg et al., 2008) -a popular package for graph analytic, to which we maintain maximal similarity. DGLGraph stores node/edge features so that it can access or modify them at any time, even when the graph is mutated. Users query or modify these features with a dictionary-style interface, for example g.ndata ['x'] returns the x features of all nodes that are packed in one tensor.
DGL provides the following two basic primitives to perform computation on graphs: Here, send and recv are message passing triggers on edge and node respectively. In addition, DGL extends them with the following: User-defined function (UDF). DGL makes no assumption on what φ e , φ v and in Equation 1 should be. They could be parameterized by neural network modules (e.g. torch.nn.module). Supporting arbitrary efficiently is non-trivial due to varying node degrees. In DGL, we analyze the graph structure and process nodes with the same neighborhood size in a batch. We also perform aggressive optimization for the most popular UDF combinations, as we will explain later.
Active set. E and V define the set of edges and nodes that are triggered for message passing. Collectively, we call them active set. Computation can be repeatedly triggered on different active sets to propagate messages and update features along a walk on the graph or a preset path. DGL supports a variety of propagation orders using the active set design: • subset node/edge propagation under certain traversal order ; • random walk ; • active sets that are generated dynamically, including exploration algorithms on graph navigation (Nogueira & Cho, 2016;Das et al., 2017) and graph generative models .
DGL also provides convenient utilities for message passing following common graph traversal orders (e.g. topological traversal, DFS, BFS, etc.).
Batching and Sampling APIs. In DGL, we expose batching as an API to collect a set of small graphs of different sizes into batches for efficient optimization. When faced with much larger graphs, many  propose to sample the graph to avoid full-graph propagation. In DGL, we provide graph sampling API in the form of data loader rendering sampled subgraphs. Optionally, these subgraphs can then be batched for efficient processing.

IMPLEMENTATION AND OPTIMIZATION
Graph storage management. Prior libraries including GraphNet and PyG require users to maintain graphs as sparse matrices and features separately as dense tensors. Although this is convenient   for quick prototyping, many low-level system design choices are exposed to users: which sparse format (CSR or COO) to use, what is the order of stacking node/edge features, shall we store all the node/edge features in one tensor or many for heterogeneous graphs? By contrast, the DGL system (i.e, DGLGraph) manages the storage so that users are freed from the low-level decisions on how to manipulate graphs as tensors.
Tensorization and kernel fusion. Rarely does a user perform computation on a single node or edge. DGL stacks node/edge features so that the user-defined φ e and φ v can operate on a batch of nodes and edges. send and recv can also be fused together to avoid materializing messages. For example, when φ e simply returns the sending node's feature and is defined to be a sum, the overall computation is equivalent to a Sparse-Dense Matrix Multiply (SPMM) where the sparse matrix is the adjacency matrix of the subgraph defined by the edge set E. In DGL, system automatically detects pattern of fusion and optimizes. It takes send and recv(E, φ e , , φ v ) and gauges the possibility of fusion by assessing φ e and . When fusion is possible it saves both time and memory, since messages typically do not need to be materialized.

EVALUATION
Experimental setup. We focus on the semi-supervised setup for node classification (Kipf & Welling, 2017). Our datasets include three citation networks (Cora, Citeseer and Pubmed (Kipf & Welling, 2017)) as well as the larger scale Reddit posting graph ). For model selection, we follow the setup in the original papers and report the average performance from 10 rounds of experiments. All experiments are carried out on an AWS EC2 p3.2xlarge instance installed with one NVIDIA Tesla V100 GPU and 8 vCPUs.
Speed and memory efficiency.  Table 2, DGL is consistently faster than PyG in training GAT. For GCN, DGL lags behind because it has a slightly higher python overhead cost in the wrapper codes (e.g. storage APIs) in the original setting. However when we increase the hidden layer size, DGL starts to out-perform PyG, as shown in Figure 1. GAT causes OOM for both DGL and PyG on Reddit so is not included.
DGL's superior performance is largely owing to kernel fusion. It brings both speed and memory advantage, in particular on larger and denser graphs such as Reddit graph whose average degree is around 500. On this dataset, PyG runs out of memory while DGL can complete training by using less than 12 GB memory. For further comparison, we randomly prune out 80% of the edges in Reddit graph (dubbed as Reddit-S). Under this setup, we can measure PyG's memory consumption. In this case, DGL is still 3× faster and saves 77% memory.
Handling large graphs with sampling. We test our sampling APIs on large graphs. Currently, its MXNet version runs on both large shared-memory NUMA machine as well as on multi-GPUs, scaling upwards to 500M nodes. For Reddit graph, we verify that using the algorithm proposed by , training GCN is roughly 3× faster than the full graph propagation while converging to similar accuracy.

OUTLOOK
We present Deep Graph Library, a graph-oriented library built for deep learning on Graphs. On the ML side, we will continue to push ease of use, diversity and scale. On the system end, as the models grow deeper and larger, or structurally more complex, how to speed up them using modern hardware is another challenge; kernel fusion technique in DGL is only a stepping stone.

ACKNOWLEDGEMENT
This work is in part supported by Science and Technology Commission of Shanghai Municipality under award 17JC1404101, National Science Foundation (CNS-1816717) and NVIDIA AI Lab (NVAIL) at NYU. We also thank Tianqi Chen, Sheng Zha and Damon Deng for the help on open sourcing the project.