How can I learn a graph given nodes with features in a supervised fashion?
It's perfectly reasonable to apply 'traditional' Deep Learning approaches to try and learn an adjacency matrix (a matrix is just a vector of vectors, which can be flattened into a single output vector) but you might need a lot of training data as N gets larger.

Your outputs could certainly have the form of an adjacency matrix, as you describe. Whether it's more useful to have 'boolean' (either 0 or 1)
or 'probabalistic' entries in the matrix depends both on the data and the specifics of your end application.