Graph Data Science (or in short: GDS) aims to provide an integrated analysis of two types of data structures that encompass a large portion of important data science applications arise frequently in science, technology, and society: [D1] Graph-structured data: where the observed data takes the form of an ‘organic’ graph with given pairwise connections. Examples: social network, World Wide Web (WWW), recommendation systems, telecommunication network etc. [D2] Data-graph: such graphs are ‘constructed’ from the given data. Examples: high-dimensional data, image data, computer vision etc. In this talk, I will explore some recent progress in the direction of developing a theoretical foundation and unified algorithms for GDS.