Source-linked AI summary
Multi-scale Attributed Node Embedding
Benedek Rozemberczki, Carl Allen, Rik Sarkar
TL;DR
Node embeddings often underuse attributes distributed across neighborhoods and do not naturally transfer between disconnected graphs. This paper introduces pooled and multi-scale Skip-gram-style attributed embeddings, derives their PMI factorization, and reports that they outperform comparable unsupervised methods across attribute prediction tasks.
Problem
Existing proximity-based node embeddings do not generally relate representations across distinct graphs, while neighborhood attributes at different scales can contain useful information.
Method
The paper jointly learns node and feature embeddings from random-walk neighborhood contexts using pooled AE and multi-scale MUSAE Skip-gram-style algorithms.
Results
MUSAE-EGO outperforms other unsupervised attributed algorithms at predicting attributes and typically improves downstream performance by distinguishing neighborhood scales.
Takeaways & Limitations
Explicitly representing attribute-neighborhood relationships across scales supports attribute prediction, link prediction, and transfer learning across graphs with common features.
Abstract
from arXiv · showhide
We present network embedding algorithms that capture information about a node from the local distribution over node attributes around it, as observed over random walks following an approach similar to Skip-gram. Observations from neighborhoods of different sizes are either pooled (AE) or encoded distinctly in a multi-scale approach (MUSAE). Capturing attribute-neighborhood relationships over multiple scales is useful for a diverse range of applications, including latent feature identification across disconnected networks with similar attributes. We prove theoretically that matrices of node-feature pointwise mutual information are implicitly factorized by the embeddings. Experiments show that our algorithms are robust, computationally efficient and outperform comparable models on social networks and web graphs.
1. Introduction
Attributed network embeddings extend random-walk node representations with attribute distributions from neighborhoods at multiple scales. The paper introduces pooled and multi-scale methods, derives their PMI factorization, and reports strong empirical performance and scalability.
- Node attributes and neighborhood distributions provide information for downstream tasks including community detection, recommender systems, node classification, and link prediction.
- Multi-scale representations distinguish nodes whose higher-order neighborhood attributes differ despite similar node and nearest-neighbor features.
- The paper introduces Skip-gram-style attributed embeddings that either pool local attribute distributions (AE) or encode neighborhood scales separately (MUSAE), with EGO variants.
- The algorithms implicitly factorize PMI matrices relating adjacency structure and node-feature information, with DeepWalk and Walklets appearing as special cases.
- The authors report improved attribute prediction over comparable methods, computational scalability, transfer learning, and open-source implementations.
2. Related work
Related work frames the paper as an attributed extension of Skip-gram-based proximity embedding, while distinguishing pooled from multi-scale representations and emphasizing scalability and inductive properties.
- Skip-gram-inspired methods such as DeepWalk generate random-walk corpora and learn embeddings from node proximity statistics.
- Attributed methods incorporate node features alongside neighborhood structure, with TADW decomposing normalized adjacency powers together with a feature matrix.
- Pooled graph neural networks combine attributes from different neighborhood orders, whereas multi-scale models learn separate latent features for each order.
- Embedding techniques are evaluated by expressive properties together with time and space complexity as functions of graph, feature, and embedding dimensions.
- The paper’s desired embedding properties include generic, multi-scale, implicit, proximal, higher-order, inductive, and non-linear representations.
- The described AE procedure samples graph walks, constructs node-feature contexts, and trains Skip-gram with negative sampling to produce node and feature embeddings.
3. Attributed embedding algorithms
The algorithms jointly embed nodes and attributes from local neighborhoods sampled by random walks. AE pools feature contexts across proximity orders, whereas MUSAE learns distinct embeddings for each order and concatenates them.
- The methods jointly learn node and feature embeddings so similar neighborhood-attribute patterns produce similar latent representations.
- AE: AE samples first-order random walks and creates node-feature Skip-gram contexts from target-node features and source-node features.
- AE: AE pools features from neighborhoods at different proximities into a shared node embedding.
- MUSAE: MUSAE assigns separate node and feature embedding components to each proximity r∈{1,...,t} and concatenates the components into a d-dimensional embedding.
- MUSAE: MUSAE sampling stores proximity-specific node-feature tuples in distinct multisets and trains Skip-gram separately for those scales.
4. Attributed embedding as implicit matrix factorization
The paper connects Skip-gram-style attributed node embeddings to implicit factorization of node-feature PMI matrices derived from random-walk statistics. MUSAE preserves multiple neighborhood scales, while AE pools them; DeepWalk and Walklets appear as special cases.
- Background: SGNS embeddings approximately factorize shifted PMI matrices of co-occurrence statistics, extending the matrix-factorization view from words to random-walk node sequences.The factorized matrix reflects probabilities of encountering contexts in the generated corpus.
- Multi-scale case (MUSAE): Random-walk node-feature statistics provide unbiased estimates of joint probabilities for features observed before, after, or on either side of a node at r steps.These estimates support the derivation of the matrices factorized by attributed embedding methods.
- Multi-scale case (MUSAE): MUSAE embeddings approximately factorize node-feature PMI matrices, with the factorization expressed through graph adjacency, transition probabilities, and the node-feature matrix.The derivation uses the graph’s transition matrix P and binary feature matrix F.
- Pooled case (AE): AE pools information across path lengths and approximately factorizes a pooled node-feature matrix.Its empirical node-feature statistics provide unbiased estimates of mean joint probabilities over different path lengths.
- Special cases and extensions: DeepWalk is a special case of AE with one unique feature per node, while Walklets is a special case of MUSAE under the same feature construction.Appending the identity matrix to feature matrices instead yields AE-EGO and MUSAE-EGO, which approximately factorize node-feature PMI matrices.
- Complexity analysis: Corpus generation and optimization have runtime expressions that scale with walk length, feature count, embedding dimension, and negative samples, while parameter storage is O((n + q) ·d).The reported runtime experiments empirically support the complexity analysis.
5. Experimental evaluation
The evaluation compares attributed embedding methods across classification, few-shot learning, regression, transfer learning, and runtime settings. Across tasks, multi-scale attributed embeddings generally perform strongly, transfer across graphs with shared features, and scale linearly with nodes and features.
- Node classification: Attributed embeddings tend to outperform other unsupervised methods, while multi-scale embeddings generally outperform pooled counterparts.The typical supervised advantage is approximately 4%, but can be within 1%.
- Few-shot classification: Attributed embeddings show a material few-shot advantage, particularly on larger Facebook and Github datasets, while EGO models provide a modest additional benefit.The few-shot experiments train logistic regression with k randomly selected samples per class.
- Node attribute regression: MUSAE-EGO outperforms the best regression baseline for each Wikipedia dataset by 2-10%.Attributed embeddings generally outperform other methods, and multi-scale methods tend to outperform pooled methods.
- Transfer learning: MUSAE and AE transfer feature embeddings between Twitch graphs with common features, always beating random guessing and sometimes approaching target-graph retraining.The transfer procedure fixes feature embeddings learned on a source graph before embedding the target graph.
- Efficiency: AE and MUSAE runtimes are linear in node count and average features per node, while more cores do not reduce runtime as feature diversity approaches the feature-set size.This behavior agrees with the paper’s complexity analysis.
6. Discussion and conclusion
The paper concludes that pooled and multi-scale attributed embeddings capture local feature information, with multi-scale and EGO variants often improving downstream performance. Explicitly learned node and feature embeddings also support transfer between graphs sharing features, while the models implicitly factorize interpretable PMI matrices.
- Discussion and conclusion: AE and MUSAE learn local feature information using pooled and multi-scale neighborhood representations, while EGO variants additionally encode local network information.The combined MUSAE-EGO model improves attributed prediction and matches proximity-preserving embeddings in link prediction.
- Discussion and conclusion: MUSAE models typically benefit downstream tasks by distinguishing neighborhood information at different scales, and EGO information typically improves performance further, particularly for link prediction.MUSAE-EGO outperforms other unsupervised attributed algorithms at attribute prediction.
- Discussion and conclusion: Learning distinct node and feature embeddings enables transfer learning between graphs with common features.The paper demonstrates this capability on real datasets.
- Discussion and conclusion: The algorithms implicitly factorize explicit node-feature PMI matrices, and AE and MUSAE scale linearly with the numbers of nodes and features per node.DeepWalk and Walklets are identified as special cases of the proposed models.
A. Proofs
The proofs establish that random-walk statistics for node-feature pairs provide unbiased estimates of the relevant joint probabilities. The argument uses finite-moment and diminishing-covariance properties together with the Weak Law of Large Numbers.
- Lemmas: Random-walk node-feature pair statistics give unbiased estimates of observing a feature r steps before or after a node.The result is stated separately for one-sided observations and observations on either side of the node.
- Proof strategy: The proof models the statistics as random-variable sequences with finite expectation, bounded variance, and covariances that vanish with increasing separation.These properties allow sample means to converge to expectations.
- Proof strategy: The Weak Law of Large Numbers yields convergence in probability of the sample average to the expected node-feature statistic.The argument begins with a single random-walk sequence and extends to multiple walks using indicator functions.
- Graph setting: Symmetry of the adjacency matrix extends the lemma’s final step to directed graphs.The text explicitly attributes this extension to adjacency symmetry.
B. Embedding Model Hyperparameters
The experiments use matched hyperparameter settings and standardized embedding dimensions to compare proposed and competing methods fairly. Implementations and task-specific settings are drawn from established papers or reported separately.
- Evaluation controls: The evaluation matches competing methods in expressive power for target matrix approximation and embedding dimensionality.Implementations come from the open-source Karate Club library.
- Proximity-preserving methods: DeepWalk uses Table 3 settings with negative sampling instead of hierarchical softmax, making it comparable to a first-order Node2Vec special case.The implementation choice is intended to speed calculations while preserving the stated relationship.
- Proximity-preserving methods: LINE2 uses 64-dimensional embeddings for each of first- and second-order proximity, concatenated into one representation.Other LINE2 hyperparameters follow the original work.
- Proximity-preserving methods: Node2Vec’s in-out and return parameters are tuned by grid search over {4,2,1,0.5,0.25} using an internal 80%-20% train-validation split.Other Node2Vec settings follow Table 3.
- Multi-scale baselines: Walklets and GraRep use window size 4 with individual embedding sizes of 32, preserving the overall representation dimensionality.These settings parallel the multi-scale comparison design.
- Other baselines: NetMF uses 128-dimensional embeddings with window size 5, while HOPE uses normalized neighbourhood overlap as its proximity measure.Their remaining hyperparameters follow the respective papers or Table 3.
- Attributed baselines: AANE, ASNE, BANE, TADW, and TENE are configured so each downstream embedding is 128 dimensional.Their other hyperparameters follow the respective papers.
C. Supervised Model Hyperparameters
The supervised graph neural network baselines use sparsity-aware implementations and model-specific neighborhood, propagation, attention, sampling, and clustering settings. Training hyperparameters and baseline configurations are summarized in Table A.6.
- All models use Adam with standard moving-average parameters and sparsity-aware PyTorch Geometric modifications to handle many vertex features.Most models use ReLU intermediate activations and a softmax output for classification, except GAT.
- Except for APPNP, each baseline uses information from neighborhoods of up to 2 hops.
- GraphSAGE samples 40 nodes per source, while GAT uses a single attention head and a leaky-ReLU negative slope of 0.2.
- MixHop combines the 0th, 1st, and 2nd powers of the normalized adjacency matrix with 32-dimensional convolutional filters before node classification.
- ClusterGCN decomposes graphs into disjoint METIS clusters, using a cluster count equal to the number of node classes.For example, the Facebook page-page network uses four clusters.
- APPNP uses 32 hidden neurons, teleport probability 0.2, and 20 approximate personalized PageRank steps, whereas SGCONV uses the 2nd normalized-adjacency power.