In this chapter, we cover the basics of graph theory followed by some of the graph-based machine learning algorithms arising in applications. By a “graph”1, we mean a combinatorial object consisting of a finite number of points, known as nodes or vertices, and a finite number of edges, each of which connects two of the nodes. In addition to its many roles in a broad range of mathematics, graph theory finds applications to a wide variety of applied problems, including the analysis of network data, such as communication, social, biological, or academic networks, or more broadly, the internet, molecular property prediction and drug discovery, Markov processes, image processing and computer vision, and geometric structures. The applications of very large graphs, e.g., with millions or billions of nodes, or of very large data sets consisting of millions of graphical objects, are playing an increasingly important role in modern data analysis, machine learning, and computer science.