The　k　nearest　neighbors　(kNN)　graph,　perhaps　the　most　popular　graph　in　machine　learning,　plays　an　essential　role　for　graph-based　learning　methods.　Despite　its　many　elegant　properties,　the　brute　force　kNN　graph　construction　method　has　computational　complexity　of　O(n2),　which　is　prohibitive　for　large　scale　data　sets.　In　this　paper,　based　on　the　divide-and-conquer　strategy,　we　propose　an　efficient　algorithm　for　approximating　kNN　graphs,　which　has　the　time　complexity　of　O(l(d　+　logn)n)　only　(d　is　the　dimensionality　and　l　is　usually　a　small　number).　This　is　much　faster　than　most　existing　fast　methods.　Specifically,　we　engage　the　locality　sensitive　hashing　technique　to　divide　items　into　small　subsets　with　equal　size,　and　then　build　one　kNN　graph　on　each　subset　using　the　brute　force　method.　To　enhance　the　approximation　quality,　we　repeat　this　procedure　for　several　times　to　generate　multiple　basic　approximate　graphs,　and　combine　them　to　yield　a　high　quality　graph.　Compared　with　existing　methods,　the　proposed　approach　has　features　that　are:　(1)　much　more　efficient　in　speed　(2)　applicable　to　generic　similarity　measures;　(3)　easy　to　parallelize.　Finally,　on　three　benchmark　large-scale　data　sets,　our　method　beats　existing　fast　methods　with　obvious　advantages.　©　2013　Springer-Verlag.