I think the code below would do it, but I think your example is missing some NONs. If, as you say, [1,2] and [2,1] are equivalent, then I think 2 and 4 should be NONs because they are both neighbors of 1. Similarly, 7 and 8 both neighbor 6.
m=max(A(:));
Ac=sparse(A(:,1),A(:,2),true,m,m);
Ac=double(Ac|Ac.');
Bc=(Ac*Ac)&(~Ac);
[i,j]=find(tril(Bc,-1));
B=[j,i]
