In this talk, I will present recent works on large-scale similarity search, and show that it is possible to build a graph connecting up to one billion of images on a regular server, assuming that a vector representation is provided for each image. In particular, I will introduce a new method based on hierarchical navigable small words graph, which explicitly exploits the graph structure in the encoding stage (compression) of each vector so that the indexing structure can fit into memory. I will then discuss applications involving large graphs, including semi-supervised classification and unsupervised learning.