Source-linked AI summary
Anonymous Walk Embeddings
Sergey Ivanov, Evgeny Burnaev
TL;DR
Graph representation needs task-agnostic methods beyond supervised neural graph classifiers, while efficient graph-to-vector conversion remains challenging. The paper uses anonymous walks to learn feature-based and distributed graph embeddings, with sampling for scalable computation. On real datasets, these embeddings achieve state-of-the-art classification performance and improve accuracy over supervised neural networks and graph kernels when paired with a simple SVM.
Problem
Task-agnostic graph representation remains challenging because computationally efficient graph-to-vector conversion must preserve graph similarity despite fundamental graph-isomorphism constraints.
Method
The paper learns feature-based and distributed graph embeddings from anonymous walks, using sampling to make exact anonymous-walk computation more tractable.
Results
The embeddings achieve state-of-the-art graph-classification performance on widely used real datasets compared with graph kernels and neural networks.
Takeaways & Limitations
Anonymous walks support scalable unsupervised graph representations that can be used with a simple SVM for graph classification.
Takeaways & Limitations
Direct computation of anonymous-walk embeddings requires enumerating all random walks, whose number grows exponentially with walk length.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses task-agnostic graph representation by proposing anonymous-walk embeddings with both feature-based and data-driven learning procedures. On real datasets, these embeddings achieve state-of-the-art graph-classification performance against graph kernels and neural networks.
- Motivation: Graph embeddings convert graphs into vectors suitable for standard machine-learning methods, but polynomial-time graph-to-vector conversion faces fundamental challenges related to graph isomorphism.The paper motivates computationally efficient embeddings that preserve similarity between graphs.
- Existing approaches: Feature-based methods use engineered graph components, while data-driven methods learn distributed representations by optimizing objectives defined on graph data.Feature-based approaches can require ad-hoc structural assumptions and may produce sparse, diagonally dominant representations.
- Our approach: The paper introduces anonymous walks as a basis for feature-based and data-driven network embeddings.Anonymous-walk distributions provide graph traits and can reconstruct local topology under the cited results.
- Contributions: An efficient sampling procedure approximates anonymous-walk features, alleviating the time complexity of exact computation.The sampling procedure is designed for feature-based network embeddings.
- Contributions: A scalable data-driven algorithm learns embeddings by maximizing the likelihood of preserving network proximity among anonymous walks.The approach learns distributed representations from anonymous-walk data.
- Results: On widely used real datasets, the embeddings achieve state-of-the-art graph-classification performance compared with graph kernels and neural networks.The reported comparison covers both traditional graph kernels and neural-network methods.
2. Anonymous Walks
An anonymous walk replaces node identities in a random walk with the positions where nodes first appear. This representation groups walks with the same recurrence pattern while preserving structural information relevant to local network reconstruction.
- Random walks: Random walks generate node sequences by selecting each next node from the neighbors of the current node.Anonymous walks remove dependence on global node names, which may be unavailable to an observer.
- Anonymous-walk definition: The positional function returns all positions at which a given element occurs in an ordered list.For example, in (a, b, c, b, c), the positions of b are (2, 4).
- Anonymous-walk definition: An anonymous walk maps each visited node to the position of its first occurrence in the random walk.States begin at 1 and new states increment the current maximum state.
- Interpretation: Different random walks can correspond to the same anonymous walk when they share the same pattern of node revisits.The figure contrasts two walks mapped to one anonymous walk with a third walk mapped to another.
- Interpretation: Anonymous-walk state names are arbitrary, while their recurrence pattern and number of distinct visited nodes determine the representation.The same pattern is invariant to the particular names assigned to states.
- Structural significance: The distribution of anonymous walks of a fixed length can reconstruct the topology of the graph neighborhood around a starting node.The cited result concerns the subgraph induced by vertices within a fixed radius.
3. Algorithms
The paper develops feature-based and data-driven anonymous walk embeddings, using walk distributions for explicit graph vectors and prediction-based training for distributed graph representations. Sampling makes feature-based computation scalable, while the data-driven model learns graph vectors by predicting anonymous walks from shared-node contexts.
- Feature-based AWE: Anonymous walks record each random walk state by its first occurrence index, and their possible patterns grow exponentially with walk length l.This combinatorial growth motivates sampling for estimating walk distributions.
- Feature-based AWE: Feature-based AWE represents graph G as a vector whose components are probabilities of anonymous walks of length l.The vector has one component for each possible anonymous walk.
- Feature-based AWE: Direct enumeration is exponential in l, whereas sampling m random walks computes the feature-based embedding in O(ml).Sampling approximates the true distribution using an empirical distribution, with sample size controlled by accuracy and confidence.
- Data-driven AWE: Anonymous-walk neighborhoods group walks sharing a source node, forming graph-specific corpora analogous to sentences in paragraph-vector training.Each graph receives a document vector, while anonymous walks receive rows in a walk-embedding matrix.
- Data-driven AWE: The data-driven model averages context-walk vectors, concatenates that representation with a graph vector, predicts a target walk, and updates vectors by backpropagation.Training repeats target prediction and vector updates over sampled co-occurring anonymous walks.
- Results: Experiments report state-of-the-art graph-classification accuracy for anonymous walk network embeddings and feature-based AWE on real datasets.The paper presents the data-driven approach as addressing sparsity in feature-based embeddings.
4. Graph Classification
The paper uses anonymous walk embeddings with kernel functions to classify whole graphs while avoiding labeled-data requirements during embedding learning. Kernelized SVM with these embeddings achieves top performance against more complex models.
- Anonymous walk embeddings support task-agnostic graph classification without requiring labeled data during representation learning.The approach defines a kernel on graph embeddings for classifying new graphs.
- A graph classifier can use a kernel matrix whose entries compare pairs of graph embeddings, then provide it to a kernelized algorithm such as SVM.For a test graph, its kernel values against training graphs are supplied to the trained classifier.
- Anonymous walk embeddings with kernelized SVM achieve top performance compared with more complex state-of-the-art models.The experiments use anonymous walk embeddings to compute the kernel matrices.
5. Experiments
Experiments evaluate anonymous walk embeddings on social and bioinformatics graph datasets using repeated cross-validated SVM classification. The methods are competitive with supervised and kernel baselines while scaling to graphs with tens of thousands of nodes and edges.
- Datasets: The evaluation covers unlabeled social graphs and graphs with node or edge labels from bioinformatics.The datasets are widely used graph-classification benchmarks.
- Evaluation: Multiclass SVM is evaluated with repeated 10-fold cross-validation, and reported accuracy averages correctly classified test graphs.The SVM parameter C is selected from five candidate values using a validation set.
- Setup and competitors: AWE is compared with PSCN, GK, DGK, WL, ER, and kR using walk lengths, embedding sizes, kernels, and optimization settings specified in the experimental setup.Feature-based walks use lengths 2 through 10; data-driven embeddings use length 10 and size 128.
- Classification results: AWE approaches share top-two results across all six social datasets, while feature-based AWE remains competitive on labeled bioinformatics datasets.AWE embeddings use only network topology rather than node or edge labels.
- Classification results: Feature-based and data-driven accuracy is close across many datasets; data-driven AWE exceeds feature-based AWE by more than 5% only on RE-B.Feature-based methods work well for small walk lengths, whereas data-driven methods work best with more iterations and larger lengths.
- Scalability: AWE (DD) scales to graphs with tens of thousands of nodes and edges and maps a graph to a vector in no more than a few seconds.The scalability test uses Erdos-Renyi graphs with increasing node counts and average degree parameter µ = np in [2, 3, 4, 5].
6. Related Work
The paper connects its feature-based embeddings to graph-kernel decompositions and its data-driven embeddings to distributed representations from NLP. It situates anonymous walks among established graph representation and aggregation methods.
- Feature-based anonymous walk embeddings learn graph representations from anonymous-walk distributions, similarly to graph-kernel approaches.Related graph-kernel decompositions include random walk, graphlet, Weisfeiler-Lehman, and shortest-path methods.
- The data-driven approach draws from paragraph-vector distributed-memory models and relates to graph2vec, which learns embeddings from rooted subgraphs.Distributed graph representations originated in successful NLP applications.
- Other graph representation approaches include feature vectors built from histograms of node pairwise distances and techniques that aggregate node embeddings for graph classification.These methods complement graph-kernel and distributed-representation approaches.
7. Conclusion
The paper presents two unsupervised anonymous-walk algorithms for graph representations and reports improved classification accuracy with a simple SVM over supervised neural methods and graph kernels. The approach also extends to node, edge, and subgraph representations.
- Two unsupervised algorithms compute network vector representations from anonymous walks.One uses anonymous-walk distributions directly; the other learns distributed representations in a data-driven manner.
- Sampling anonymous walks approximates expensive exact distributions with a given confidence.
- Anonymous-walk embeddings with a simple SVM increase classification accuracy over state-of-the-art supervised neural methods and graph kernels.
- AWE can represent nodes, edges, or subgraphs by replacing the graph vector with the corresponding subgraph vector.