Representation learning from graphs has been an active research area over the past decade. DeepWalk [24], one of the pioneering approaches in this field, learns node embeddings by generating random walks on the graph. A standard and highly efficient method for optimizing the embedding objective is to train a binary classification model that distinguishes between positive and negative node pairs, known as the negative sampling approach. Positive pairs are generated by applying the skip-gram model [21] to the node sequences and represent nodes whose embeddings should be similar, in contrast to negative pairs. Many works have since extended the original DeepWalk algorithm in three main directions: i) presenting different (random) walk strategies for traversing the graph and generating node sequences [1, 9, 10, 25, 29, 31, 39, 41], ii) designing new embedding learning models [1, 2, 11, 12, 26], and iii) designing new techniques for negative pair sampling [3, 16, 19, 35]. Inspired by observations on real graphs, we take a different approach and propose a general regularization technique that adjusts the frequency distribution of positive node pairs. In the standard negative sampling setting, when a positive pair u, v is generated, we also sample k 1 negative pairs u, x, where the node x is selected at random from some distribution on the graph nodes.

Graphs are ubiquitous representation for structured data. They model naturally occurring relations between objects and, in a sense, generalize sequential data to more complex dependencies. Many algorithms originally designed for learning from sequential data are thus generalized to learning from graphs. Learning continuous vector representations of graph nodes, or node embeddings, have become an integral part of the graph learning toolbox, with applications ranging from link prediction [9] to graph compression [2]. The first algorithm [18] for learning node embeddings generates random walks, starting from each node in the graph, and then feeds the sequences of visited nodes into a word embedding learning algorithm such as word2vec [15]. The approach was extended to a more general setting where random walks can consider different properties of the local neighborhood [9, 26, 27]. An alternative method for training continuous node embeddings is based on matrix factorization of (powers of) the graph adjacency matrix. As an alternative, researchers proposed to use coordinated node sampling for training discrete node embeddings [28, 29]. In this setting, each sample is an independent estimator of the similarity between nodes.

Representation learning for graphs enables the application of standard machine learning algorithms and data analysis tools to graph data. Replacing discrete unordered objects such as graph nodes by real-valued vectors is at the heart of many approaches to learning from graph data. Such vector representations, or embeddings, capture the discrete relationships in the original data by representing nodes as vectors in a high-dimensional space. In most applications graphs model the relationship between real-life objects and often nodes contain valuable meta-information about the original objects. While being a powerful machine learning tool, embeddings are not able to preserve such node attributes. We address this shortcoming and consider the problem of learning discrete node embeddings such that the coordinates of the node vector representations are graph nodes. This opens the door to designing interpretable machine learning algorithms for graphs as all attributes originally present in the nodes are preserved. We present a framework for coordinated local graph neighborhood sampling (COLOGNE) such that each node is represented by a fixed number of graph nodes, together with their attributes. Individual samples are coordinated and they preserve the similarity between node neighborhoods. We consider different notions of similarity for which we design scalable algorithms. We show theoretical results for all proposed algorithms. Experiments on benchmark graphs evaluate the quality of the designed embeddings and demonstrate how the proposed embeddings can be used in training interpretable machine learning algorithms for graph data.

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs. These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes. Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs. Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.