One way to sparsify a proximity matrix is the following: For each object (row in the matrix), set all entries to 0 except for those corresponding to the objects k-nearest neighbors. However, the sparsified proximity matrix is typically not symmetric.

Question

(a) If object a is among the k-nearest neighbors of object b, why is b not
guaranteed to be among the k-nearest neighbors of a?
(b) Suggest at least two approaches that could be used to make the sparsi-
fied proximity matrix symmetric.

Answer 1

(a) Consider a dense set of k+1 objects and another object, an outlier, that
is farther from any of the objects than they are from each other. None
of the objects in the dense set will have the outlier on their k-nearest
neighbor list, but the outlier will have k of the objects from the dense
set on its k-nearest neighbor list.
(b) One approach is to set the ijth entry to 0 if the jith entry is 0, or vice
versa. Another approach is to set the ijth entry to 1 if the jith entry is
1, or vice versa.