Machine learning is the research field of allowing computers to learn to act properly from sample data without being explicitly programmed. Deep learning is a class of machine learning algorithms that is built upon artificial neural networks. In fact, most of the key building components of deep learning have existed for decades, while deep learning only gains its popularity in recent years. The idea of artificial neural networks dates back to \(1940s\) when McCulloch-Pitts Neuron was first introduced. This linear model can recognize inputs from two categories by linearly aggregating information from inputs and then making the decision. Later on, the perceptron was developed, which is able to learn its parameters given training samples. The research of neural networks revived in the \(1980s\). One of the major breakthroughs during this period is the successful use of the back-propagation algorithm to train deep neural network models. The back-propagation algorithm is still the dominant algorithm to train deep models in the modern ages of deep learning. The research of deep learning revived and gained unprecedented attention with the availability of ‘‘big data’’ and powerful computational resources in recent years. The emerging of fast GPUs allows us to train deep models with extremely large size while the increasingly large data ensures that these models can generalize well. These two advantages lead to the tremendous success of deep learning techniques in various research areas and result in immense real-world impact. Deep neural networks have outperformed state-of-the-art traditional methods by a large margin in various applications. Deep learning has significantly advanced the performance of the image recognition task. The ImageNet Large-Scale Visual Recognition Challenge (ILSVRC) is the largest contest in image recognition, which is held each year between \(2010\) and \(2017\). In \(2012\), the deep convolutional network (CNN) won this challenge for the first time by a large margin, reducing top-\(5\) error rate from \(26.1\\) to \(15.3\\). Since then, the deep convolutional neural networks (CNNs) have wined the competition consistently that have further pushed the error rate down to \(3.57\%\). Deep learning has also dramatically improved the performance of speech recognition systems. The introduction of deep learning techniques to speech recognition leads to huge drop in error rates, which have stagnated for years. The research field of Natural Language Processing (NLP) has also been heavily accelerated by the deep learning techniques. Recurrent Neural Networks such as LSTM have been broadly used in sequence-to-sequence tasks such as machine translation and dialogue systems. As the research of ‘‘deep learning on graphs’’ has its root in deep learning, understanding some basic deep learning techniques is essential. Hence, in this chapter, we briefly introduce important deep learning techniques that will serve as the foundations for studying ‘‘deep learning on graphs’’ including feedforward networks, convolutional networks, recurrent networks, and autoencoders. While focusing on basic deep models in this chapter, we will expand our discussion to more advanced deep models such as variational autoencoders and generative adversarial networks in the later chapters.
Graph Representations
Properties and Measures
Spectral Graph Theory
Graph Signal processing
Complex Graphs
Computational Tasks on Graphs
Conclusion
Further Reading