Graphs, which describe pairwise relations between entities, are essential representations for real-world data from many different domains including social science, linguistics, chemistry, biology and physics. Graphs are widely utilized in social science to indicate the relations between individuals. In chemistry, chemical compounds are denoted as graphs with atoms as nodes and chemical bonds as edges. In linguistics, graphs are utilized to capture the syntax and compositional structures of sentences. Specifically, parsing trees are leveraged to represent the syntactic structure of a sentence according to some context-free grammar, while Abstract Meaning Representation (AMR) encodes the meaning of a sentence as a rooted and directed graph. Hence, research on graphs has attracted immense attention from multiple disciplines. In this chapter, we first introduce basic concepts of graphs and discuss the matrix representations of graphs including adjacency matrix and Laplacian matrix and their key properties. Then we introduce attributed graphs where each node is associated with attributes and provide a new understanding on such graph by regarding the attributes as functions or signals on the graph. We present the concepts of graph Fourier analysis and graph signal processing, which lay important foundations for deep learning on graphs. Next, we describe various complex graphs that are frequently utilized to capture complicated relations among entities in real-world applications. Finally, we discuss representative computational tasks on graphs that have been broadly served as downstream tasks for deep learning on graphs.
Graph Representations
Properties and Measures
Spectral Graph Theory
Graph Signal processing
Complex Graphs
Computational Tasks on Graphs
Conclusion
Further Reading