Scalable methods for mining, indexing, and similarity search in graphs and other complex structures, such as trees, lattices, and networks, have become increasingly important in data mining and database management. This is because a large set of emerging applications need to handle new kinds of objects with complex structures, such as trees (e.g., XML data), graphs (e.g., Web, chemical structures and biological graphs) and networks (e.g., social and biological networks). Such complicated data structures pose many new challenging research problems related to data mining, data management, and similarity search that do not exist in the traditional database and data mining studies.