PaperlayerView exact revision on arXiv

Source-linked AI summary

Don't Walk, Skip! Online Learning of Multi-scale Network Embeddings

Bryan Perozzi, Vivek Kulkarni, Haochen Chen, Steven Skiena

arXiv:1605.02115v2cs.SIphysics.soc-ph

TL;DR

Social networks have relationships at multiple scales, but common representations do not explicitly capture this range. WALKLETS learns scale-specific representations from random-walk offsets, and improves multi-label classification results over previous methods on real-world graphs. It is an online algorithm that scales to large networks.

  • Problem

    Many network representation methods use a single representation, while prior multiscale approaches have been indirect or too computationally demanding for real-world graphs.

    Source: 1) Multi-scale Properties of DeepWalk · p. 3

  • Method

    WALKLETS uses offsets between vertices observed in random walks to learn latent representations of successively larger relationships.

    Source: §VIII · p. 8

  • Results

    WALKLETS improves multi-label classification results over previous methods on real-world graphs; on BlogCatalog, it improves Micro-F1 over DeepWalk by 8.9% and over LINE by 58.4%.

    Source: A. Multi-label Classification · p. 6, §VIII · p. 8

  • Takeaways & Limitations

    WALKLETS approximates higher-order transition matrices by sampling vertex pairs, supporting scalability to graphs with millions of vertices.

    Source: B. Scalability · p. 7

Abstract

from arXiv · show

We present Walklets, a novel approach for learning multiscale representations of vertices in a network. In contrast to previous works, these representations explicitly encode multiscale vertex relationships in a way that is analytically derivable. Walklets generates these multiscale relationships by subsampling short random walks on the vertices of a graph. By `skipping' over steps in each random walk, our method generates a corpus of vertex pairs which are reachable via paths of a fixed length. This corpus can then be used to learn a series of latent representations, each of which captures successively higher order relationships from the adjacency matrix. We demonstrate the efficacy of Walklets's latent representations on several multi-label network classification tasks for social networks such as BlogCatalog, DBLP, Flickr, and YouTube. Our results show that Walklets outperforms new methods based on neural matrix factorization. Specifically, we outperform DeepWalk by up to 10% and LINE by 58% Micro-F1 on challenging multi-label classification tasks. Finally, Walklets is an online algorithm, and can easily scale to graphs with millions of vertices and edges.

I. INTRODUCTION

Social networks contain communities at multiple scales, but many network representations use a single embedding and do not explicitly capture those different relationships. WALKLETS learns multiscale representations and is evaluated on social-network classification and analysis tasks.

  • Social relationships vary in topology across scales, from dense ties among friends and family to looser ties across universities and nations.The paper notes that prediction tasks also range from specific user interests to attributes associated with broader communities.Source: §I · p. 1
  • Many prior methods use a single representation, while some earlier multiscale approaches are indirect or computationally intractable for real-world graphs.The paper describes one earlier approach as an artifact of learning, another as combining objectives, and a more recent approach as computationally intractable.Source: §I · p. 1
  • WALKLETS learns multiple scales of vertex relationships, with dimensions intended to support network classification and visualization.The paper reports using these representations to analyze multiscale effects in large graphs.Source: §I · pp. 1–2
  • The paper evaluates WALKLETS on multi-label classification across social networks including BlogCatalog, DBLP, Flickr, YouTube, and Arxiv.It also identifies visualization and analysis of multiscale effects in large graphs as a contribution.Source: §I · pp. 1–2

II. PRELIMINARIES

The preliminaries define graph and representation notation, formulate multiscale representation learning, and describe random-walk-based representation learning and its computational relaxation.

A. Notations and Definitions

  • A graph G = (V, E) has vertices V and edges E; its adjacency matrix A records edges, and A^k defines the graph view at scale k.A representation maps each vertex to a d-dimensional vector, represented in practice by a matrix X.Source: A. Notations and Definitions · p. 2

B. Problem Definition

  • The multiscale problem is to learn successively coarser representations, each encoding social similarity through shared membership in latent communities at a different scale.The paper also defines predictive learning as mapping representations to labels to infer labels for unlabeled vertices.Source: B. Problem Definition · p. 2

C. Representation Learning

  • Random-walk co-occurrences model local community structure, but computing the conditional probability becomes infeasible as walk length grows.The paper addresses this complexity by ignoring the order of neighboring vertices and using one vertex to predict its local structure.Source: C. Representation Learning · p. 2
  • The relaxed representation-learning objective is directly equivalent to learning a low-rank approximation of the adjacency matrix A.Source: C. Representation Learning · p. 2

D. Neural Matrix Factorization

Neural matrix factorization models vertex co-occurrence probabilities from embedding similarities. The section describes softmax and noise-contrastive estimation, and connects probabilistic models to adjacency-matrix factorization.

  • Softmax maps pairwise embedding similarity to a probability of vertex co-occurrence, but calculating its denominator is computationally expensive.The embeddings represent input and output roles for the vertices in a pair.Source: D. Neural Matrix Factorization · p. 3
  • Noise-contrastive estimation is presented as a relaxation of the softmax probability model for vertex co-occurrence pairs.Source: D. Neural Matrix Factorization · p. 3
  • Both probabilistic models correspond to implicitly factoring a transformation of the adjacency matrix.Source: D. Neural Matrix Factorization · p. 3

1) Social Representations as Matrix Factorization:

The paper frames network representations as implicit matrix factorizations, then argues that DeepWalk does not reliably preserve or expose distinct relationship scales. WALKLETS extends this framework to model those scales explicitly.

1) Social Representations as Matrix Factorization:

  • DeepWalk’s implicit factorization uses powers of the random-walk transition matrix, whose entries represent expected paths of length t between vertices.The paper relates this view to a matrix of logged vertex-pair counts.Source: 1) Social Representations as Matrix… · p. 3

III. MULTI-SCALE NEURAL MATRIX DECOMPOSITION

  • The method section introduces an algorithm for capturing different representation scales and formally extending prior social representation learning to model multiscale effects.This section also previews the model, optimization and search strategy, and a Cora case study.Source: §III · p. 3, A. Model Description · p. 3

1) Multi-scale Properties of DeepWalk:

  • DeepWalk implicitly factors terms from A through A^k, with each power corresponding to a different scale of network structure.The paper notes that entries of A^k count paths of length k between nodes.Source: 1) Multi-scale Properties of DeepWalk · p. 3
  • DeepWalk does not guarantee multiscale representations, biases toward lower powers of A, and combines scales in one global representation that tasks cannot access independently.The paper argues that tasks may benefit from different scales, such as coarse representations for features correlated with large-scale graph structure.Source: 1) Multi-scale Properties of DeepWalk · p. 3

B. WALKLETS: Multiple Scales of Random Walks

WALKLETS extends random-walk-based representation learning by skipping vertices to sample relationships at distinct path lengths. It then learns representations from separate scale-specific corpora.

B. WALKLETS: Multiple Scales of Random Walks

  • WALKLETS extends prior social-representation methods by factoring powers of the adjacency matrix to model multiscale dependencies explicitly.It builds on the approach introduced in.Source: B. WALKLETS: Multiple Scales of Random… · p. 3
  • Skipping vertices in truncated random walks samples relationships from successively higher powers of A, with each sampled edge representing a path of length k.Figure 2 illustrates this relationship between skipped-walk edges and paths in the original graph.Source: B. WALKLETS: Multiple Scales of Random… · pp. 3–4, Figure 2 · p. 4
  • Each adjacency-matrix power produces a separate corpus that models a specific distance dependency in the network.The method denotes representations derived from powers A^1 through A^k as WALKLETS(A1, . . . , Ak).Source: B. WALKLETS: Multiple Scales of Random… · p. 4
  • For each scale, WALKLETS maximizes the likelihood of a vertex co-occurring with its context node using a Skip-gram objective over corpus Ck.Ck contains the random-walk pairs generated for scale k.Source: B. WALKLETS: Multiple Scales of Random… · p. 4

1) Loss function Optimization:

The paper connects skipped-walk sampling to factorization of powers of the adjacency matrix and discusses search strategies for generating relationships. A Cora case study illustrates how representations at coarser scales capture larger communities.

1) Loss function Optimization:

  • The loss is optimized with back propagation and stochastic gradient descent, using learning rate 0.025 and embedding size 128 unless stated otherwise.The method can extend to weighted graphs by adapting gradients to weights, and edge sampling techniques can also be adapted.Source: 1) Loss function Optimization · p. 5

2) Implicit matrix factorization view:

  • Skipped walks with skip factor k implicitly factor a matrix derived from A^k because consecutive sampled vertices are connected by paths of length exactly k.With co-occurrence restricted to those pairs, only the A^k term remains in the factorization.Source: 2) Implicit matrix factorization view · p. 5

3) Search Strategy:

  • Random-walk sampling may scale better for multiscale relationship discovery, while directly computing A^k is presented as an alternative for smaller graphs.The skipping procedure could also be applied to node2vec’s biased random walks.Source: 3) Search Strategy · p. 5

C. Case study: Cora

  • In Cora, deeper representations bring a proximal group of papers from the larger Genetic Algorithms community closer to v35, which the authors say enables easier classification generalization.The case study uses a citation graph with 2,708 nodes and 5,429 edges.Source: C. Case study: Cora · p. 5

IV. EXPERIMENTAL DESIGN

The experiments evaluate Walklets on multi-label classification and examine multiscale effects across social networks. Comparisons include three representation-learning baselines, with GraRep providing explicit multiscale representations but not scaling to large graphs.

IV. EXPERIMENTAL DESIGN

  • Multi-label classification is evaluated on BlogCatalog, DBLP, Flickr, and YouTube, whose labels represent topics, research areas, interests, and shared group memberships.The graphs range from 10,312 nodes in BlogCatalog to 1,138,499 in YouTube.Source: §IV · p. 5
  • The evaluation targets unsupervised network representations as features for predicting users’ multiple group memberships.The paper motivates the task by shared memberships among network neighbors and notes commercial applications such as ad targeting.Source: §IV · p. 5

A. Baseline Methods

  • DeepWalk learns from truncated random walks, while LINE uses only immediate connections in A1.GraRep explicitly computes successive powers of the random-walk transition matrix and applies SVD, but is not online and does not scale to large graphs.Source: A. Baseline Methods · pp. 5–6
  • Table I reports Micro-F1 on BlogCatalog and DBLP; its caption says higher-order representations generally improve performance, while GraRep beats Walklets on DBLP.The caption describes DBLP as a small, well-behaved graph and specifies paired t-tests for significance against DeepWalk.Source: Table I · p. 6

B. Multi-label classification

Walklets is evaluated for multi-label classification using repeated labeled-node splits and Micro-F1. It outperforms scalable baselines on BlogCatalog, Flickr, and YouTube, while GraRep outperforms it on DBLP; results vary with representation scale.

B. Multi-label classification

  • The evaluation randomly assigns a fraction of labeled nodes to training, repeats the split 10 times, and reports mean Micro-F1.The same procedure is used for the baselines; accuracy and Macro-F1 are omitted because they follow the same trend.Source: B. Multi-label classification · p. 6
  • Walklets uses representations from π ∈ {1, 2, 3}, concatenating multiple scales and applying PCA to 128 dimensions when needed.Walks use 1,000 samples per node and length 11; embedding dimensions are 128 for Walklets and the baselines.Source: B. Multi-label classification · p. 6

A. Multi-label Classification

  • At 10% labeled data, Walklets’ BlogCatalog A2 features improve Micro-F1 by 8.9% over DeepWalk and 58.4% over LINE.The reported difference is statistically significant at the 0.001 level.Source: A. Multi-label Classification · p. 6
  • At 1% labeled nodes, DBLP Walklets(A3) gains 10.1% over DeepWalk and 34.3% over LINE in Micro-F1.The passage says GraRep still outperforms Walklets on this task.Source: A. Multi-label Classification · p. 6
  • On Flickr, with only 1% of data labeled for training, WALKLETS features derived from A2 outperform DeepWalk by 4.1% and LINE by 29.6% in Micro-F1.The passage says GraRep, the most competitive baseline, fails to run on Flickr, which has 80,513 vertices.Source: A. Multi-label Classification · p. 6
  • Table II and the reported results show Walklets outperforming scalable baselines on Flickr and YouTube; BlogCatalog results favor Walklets over all baselines, while GraRep beats it on DBLP.On YouTube, the joint A2,A3 representation performs best; GraRep cannot run on the larger graphs described.Source: A. Multi-label Classification · pp. 6–7, Table II · p. 7

VI. DISCUSSION

The discussion addresses scale-dependent classification performance, scalability, and the random-walk sampling procedure.

VI. DISCUSSION

  • The discussion proceeds from representation-scale effects in classification to scalability and then analysis of the sampling procedure.These are the three topics identified for the section.Source: §VI · p. 7

A. Multi-scale Effects in Classification

The paper finds that useful representation scales vary by task, and describes Walklets as a scalable sampling-based alternative to explicit transition-matrix computation. Its sampled matrices approximate exact computations on the smaller tested graphs.

A. Multi-scale Effects in Classification

  • No single representation scale performs best across tasks, and explicit multiscale features enable analysis of which scales are informative.The paper contrasts this with baselines that do not explicitly encode multiple scales.Source: A. Multi-scale Effects in Classification · p. 7
  • A2 performs best on BlogCatalog and Flickr across training-data variations, and its neighbor-of-neighbor information may help with missing links such as in cold start.The paper relates length-2 paths to shared interests such as topic categories and photography interests.Source: A. Multi-scale Effects in Classification · p. 7
  • A3 performs best on DBLP and joint A2,A3 on YouTube; performance increases with scale on both graphs.The authors surmise that these tasks exhibit hierarchy and that higher-order representations allow use of correlations between graph hierarchy and labels.Source: A. Multi-scale Effects in Classification · p. 7

B. Scalability

  • Walklets samples vertex pairs at different dependency levels to approximate higher-order transition matrices, supporting online operation on graphs with millions of vertices.GraRep instead materializes dense matrix powers and depends on SVD, which the passage says does not necessarily scale well.Source: B. Scalability · p. 7

C. Sampling Analysis

  • On DBLP and BlogCatalog, sampling yields low mean and standard deviation of transition-matrix error across scales; adding walks improves the approximation.Table III reports mean and standard deviation of errors relative to exact computation.Source: C. Sampling Analysis · pp. 7–8, Table III · p. 8

VII. RELATED WORK

Related work covers unsupervised feature learning, multiscale community detection, and graph kernels, while distinguishing Walklets’ sampling and online-learning approach. The conclusion reports multiscale representations, improved multi-label classification, and scalability, while identifying further theoretical backing as future work.

VII. RELATED WORK

  • Related work spans unsupervised feature learning, multiscale community detection, and graph kernels; Walklets uses sampling and online learning rather than SVD for multiscale representations.The closest related work uses an SVD of the random-walk transition matrix; Walklets is described as operating on larger corpora and preserving multiple scales.Source: §VII · p. 8
  • Multiscale community-detection methods generally return hard clusterings of graph relationships, unlike Walklets’ representations.The cited approaches seek discrete communities and their hierarchy.Source: §VII · p. 8
  • Graph kernels use relational data for classification but are slow unless approximated; neural networks have also been applied to learn subgraph similarity for kernels.Source: §VII · p. 8

VIII. CONCLUSION

  • Walklets uses random-walk offsets to learn latent representations of successively larger relationships and improves multi-label classification on real-world graphs.The conclusion also reports that the representations encode varied scales of social hierarchy.Source: §VIII · p. 8
  • Walklets scales gracefully to arbitrarily large networks.Source: §VIII · p. 8
  • The authors identify additional theoretical backing for Walklets as a target for future investigation.They describe the method as a foundation for future multiscale approaches.Source: §VIII · p. 8

Related papers

Loading 1605.02115v2…