Interactive demo · Probabilistic Machine Learning · Chapter 23

Shallow embeddings of the karate-club graph

The 34 members of Zachary's karate club (edges: who interacted outside the club) split into two factions, shown in red and blue. Each method turns the graph into a matrix and embeds the nodes with the leading eigenvectors of that matrix: Laplacian eigenmaps use \(\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2}\), classical MDS uses the squared hop distances, the adjacency spectral embedding uses \(\mathbf A\), and NetMF uses \(\log\max\!\big(\tfrac{\mathrm{vol}}{b}\sum_{r\le T}\omega_r\mathbf P^r\mathbf D^{-1},1\big)\), the matrix that DeepWalk's skip-gram with \(b\) negative samples and window \(T\) implicitly factorises. The score is the leave-one-out 3-nearest-neighbour accuracy of the faction in the 2-D embedding.

Method

Window length T (NetMF)

Negative samples b (NetMF)

Window distribution (NetMF)

Try these

Edges are drawn in grey; node size grows with the degree. The right-hand matrix is the one the method factorises (nodes ordered by faction); the bars are its eigenvalues, the two used by the embedding in gold. For NetMF the sum of the squares of the dropped eigenvalues is the squared Frobenius error of the best rank-2 factorisation (Eckart–Young).

In the lecture notes