diff --git a/pygsp/graphs/nngraphs/nngraph.py b/pygsp/graphs/nngraphs/nngraph.py
index <HASH>..<HASH> 100644
--- a/pygsp/graphs/nngraphs/nngraph.py
+++ b/pygsp/graphs/nngraphs/nngraph.py
@@ -92,6 +92,10 @@ class NNGraph(Graph):
         N, d = np.shape(self.Xin)
         Xout = self.Xin
 
+        if k >= N:
+            raise ValueError('The number of neighbors (k={}) must be smaller '
+                             'than the number of nodes ({}).'.format(k, N))
+
         if self.center:
             Xout = self.Xin - np.kron(np.ones((N, 1)),
                                       np.mean(self.Xin, axis=0))
error if #neighbors greater than #nodes