The first set of experiments is for link prediction. We design a setting similar to the one in [1]}. We removed 20% of the edges selected at random but such that the graph remains connected, and held them out as a test set. The rest of the edges together with four times more negative examples, i.e., pairs of nodes not connected by an edge, yield an imbalanced dataset with 20% positive examples. Each node \(u\)  is represented by a \(d\) -dimensional vector of discrete features \(\mathbf {u} \in \mathbb {K}^d\)  where \(\mathbb {K}\)  is the set of attributes describing nodes. We set \(d=25\) . For the citation networks the attributes are words describing the articles, and for PPI, Wikipedia and BlogCatalog we set the attribute to be the node itself, i.e. \(\mathbb {K}=V\) . For a pair of nodes \(u\)  and \(v\)  the input to a classification model is a \(2d\) -dimensional vector \(z\)  such that the entries in the \(i\) -coordinates in \(u\)  and \(v\)  are mapped to “twin” coordinates in \(z\) , i.e., the \(i\) -th coordinate in \(u\)  is mapped to the \(2i\) -th coordinate in \(z\) , and the \(i\) -th coordinate in \(v\)  is mapped to \((2i+1)\) -th coordinate in \(z\) . For random walks we sampled an attribute at random, while for NodeSketch and COLOGNE we sampled an attribute in a coordinated way using the corresponding basic sampling algorithm where attributes share a random seed. For example, in Pubmed nodes are described by a list of weighted features which are reweighted according to the algorithm used in COLOGNE or NodeSketch.
