Anonymous Walk Embeddings

By Sergey Ivanov, Evgeny Burnaev. 2018

192 citations recorded by the source corpus.

The task of representing entire graphs has seen a surge of prominent results, mainly due to learning convolutional neural networks (CNNs) on graph-structured data. While CNNs demonstrate state-of-the-art performance in graph classification task, such methods are supervised and therefore steer away from the original problem of network representation in task-agnostic manner. Here, we coherently propose an approach for embedding entire graphs and show that our feature representations with SVM classifier increase classification accuracy of CNN algorithms and traditional graph kernels. For this we describe a recently discovered graph object, anonymous walk, on which we design task-independent algorithms for learning graph representations in explicit and distributed way. Overall, our work represents a new scalable unsupervised learning of state-of-the-art representations of entire graphs.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

How Powerful are Graph Neural Networks? (2018, neutral): “The hyper-parameters we tune are C in SVM and the number of WL iterations ∈ { 1 , 2 , . . . , 6 } ; (2) state-of-the-art deep learning architectures Diffusion-convolutional neural networks (DCNN) (Atwood & Towsley, 2016), PATCHY-SAN (Niepert et al., 2016) and Deep Graph CNN (DGCNN) (Zhang et al., 20”
Towards multi-modal causability with Graph Neural Networks enabling information fusion for explainable AI (2021, background): “…sampled, they are rather representatives of interesting clusters w.r.t. solving specific tasks; (iii) sampling strategies such as Random Walks (RW) or Anonymous RWs [43], where the local graph structure itself is translated to fixed-size vectors which are subsequently used as inputs to an embedder.”
Capsule Graph Neural Network (2018, methodology): “However, in cases where the results are not available, we use the best testing results reported in Verma & Zhang (2018), Zhang et al. (2018) and Ivanov & Burnaev (2018).”
Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (2021, methodology): “However, AWs have only been used for entire static graph embedding (Ivanov & Burnaev, 2018) and are not directedly applied to represent temporal networks: AWs cannot capture causality; AWs get anonymized based on each single walk and hence lose the correlation between network motifs.”
A Gentle Introduction to Deep Learning for Graphs (2019, unknown): “Random-walks In an attempt to capture local and global properties of the graph, random walks are often used to create node embeddings and they have have been studied for a long time [67, 104, 85, 50].”
Invariant and Equivariant Graph Networks (2018, methodology): “We also compare our results to four popular graph kernel methods: Graphlet Kernel (GK) (Shervashidze et al., 2009),Random Walk Kernel (RW) (Vishwanathan et al., 2010), Propagation Kernel (PK) (Neumann et al., 2016), and Weisfeiler-lehman kernels (WL) (Shervashidze et al., 2011) and two recent featur”
Gromov-Wasserstein Learning for Graph Matching and Node Embedding (2019, methodology): “More recently, many new embedding methods have been proposed, e.g., the anonymous walk embedding in (Ivanov & Burnaev, 2018) and the mixed membership word embedding (Foulds, 2018), which help to improve the representations of complicated graphs and their nodes.”
Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels (2019, methodology): “Modern GNNs generally follow a neighborhood aggregation scheme Xu et al. [2019], Gilmer et al.”