Sketch-GNN is a scalable graph neural network (GNN) framework that achieves sublinear training time and memory complexity with respect to graph size. The method uses sketching techniques to approximate GNN operations on the full graph topology, reducing the need to store the full graph adjacency and node embeddings in memory. By leveraging polynomial tensor sketch (PTS) theory, Sketch-GNN can efficiently approximate nonlinear activations and graph convolution matrices, which are typically challenging to handle in traditional GNNs. Additionally, the framework introduces a learnable locality-sensitive hashing (LSH) technique to improve sketch quality adaptively, reducing performance loss while maintaining sublinear complexity. The key contributions of Sketch-GNN include the use of PTS to approximate nonlinear operations in GNNs and the use of learnable LSH to update sketches dynamically. This approach allows for efficient training on large graphs without significant accuracy degradation. Experiments on large-graph benchmarks demonstrate that Sketch-GNN outperforms existing methods in terms of scalability and performance, achieving competitive results with full-size GNNs. The framework is particularly effective for GNNs such as GCN and GraphSAGE, and it is more efficient than data compression approaches that require extensive preprocessing. Sketch-GNN's sublinear complexity is achieved by reducing the dimensionality of graph representations through sketching, which allows for efficient training on large graphs. The method is designed to handle the challenges of training GNNs on large-scale graphs by minimizing memory usage and computational complexity. The framework is also adaptable to different GNN architectures and can be applied to various types of data and neural networks. Despite its effectiveness, Sketch-GNN has limitations, such as the reduced expressiveness of sketched nonlinear activations and the potential for accumulated error during sketching. Future research aims to address these challenges and expand the application of sketching techniques to other domains.Sketch-GNN is a scalable graph neural network (GNN) framework that achieves sublinear training time and memory complexity with respect to graph size. The method uses sketching techniques to approximate GNN operations on the full graph topology, reducing the need to store the full graph adjacency and node embeddings in memory. By leveraging polynomial tensor sketch (PTS) theory, Sketch-GNN can efficiently approximate nonlinear activations and graph convolution matrices, which are typically challenging to handle in traditional GNNs. Additionally, the framework introduces a learnable locality-sensitive hashing (LSH) technique to improve sketch quality adaptively, reducing performance loss while maintaining sublinear complexity. The key contributions of Sketch-GNN include the use of PTS to approximate nonlinear operations in GNNs and the use of learnable LSH to update sketches dynamically. This approach allows for efficient training on large graphs without significant accuracy degradation. Experiments on large-graph benchmarks demonstrate that Sketch-GNN outperforms existing methods in terms of scalability and performance, achieving competitive results with full-size GNNs. The framework is particularly effective for GNNs such as GCN and GraphSAGE, and it is more efficient than data compression approaches that require extensive preprocessing. Sketch-GNN's sublinear complexity is achieved by reducing the dimensionality of graph representations through sketching, which allows for efficient training on large graphs. The method is designed to handle the challenges of training GNNs on large-scale graphs by minimizing memory usage and computational complexity. The framework is also adaptable to different GNN architectures and can be applied to various types of data and neural networks. Despite its effectiveness, Sketch-GNN has limitations, such as the reduced expressiveness of sketched nonlinear activations and the potential for accumulated error during sketching. Future research aims to address these challenges and expand the application of sketching techniques to other domains.