Source-linked AI summary
Attributed Network Embedding for Learning in a Dynamic Environment
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, Huan Liu
TL;DR
Dynamic attributed network embedding must handle correlated, noisy, incomplete topology and attributes that evolve over time, whereas prior work largely focuses on plain static networks. DANE builds an offline consensus embedding and uses matrix perturbation theory for online updates. Experiments on synthetic and real attributed networks report effectiveness and efficiency, including stronger clustering performance than the compared baselines.
Problem
Existing network embedding work largely targets plain static networks, leaving evolving topology and attributes—and their noisy, incomplete correlation—as an embedding challenge.
Method
DANE first learns a consensus embedding offline from network structure and node attributes, then updates their embeddings online using matrix perturbation theory.
Results
DANE and DANE-O consistently outperform all baseline methods on four dynamic attributed networks for clustering, with statistically significant improvements.
Takeaways & Limitations
The experiments support using both topology and attributes while updating embeddings online for dynamic attributed network mining.
Takeaways & Limitations
The study uses first-order matrix perturbation theory and assumes a constant number of nodes in its presented formulation.
Abstract
from arXiv · showhide
Network embedding leverages the node proximity manifested to learn a low-dimensional node vector representation for each node in the network. The learned embeddings could advance various learning tasks such as node classification, network clustering, and link prediction. Most, if not all, of the existing works, are overwhelmingly performed in the context of plain and static networks. Nonetheless, in reality, network structure often evolves over time with addition/deletion of links and nodes. Also, a vast majority of real-world networks are associated with a rich set of node attributes, and their attribute values are also naturally changing, with the emerging of new content patterns and the fading of old content patterns. These changing characteristics motivate us to seek an effective embedding representation to capture network and attribute evolving patterns, which is of fundamental importance for learning in a dynamic environment. To our best knowledge, we are the first to tackle this problem with the following two challenges: (1) the inherently correlated network and node attributes could be noisy and incomplete, it necessitates a robust consensus representation to capture their individual properties and correlations; (2) the embedding learning needs to be performed in an online fashion to adapt to the changes accordingly. In this paper, we tackle this problem by proposing a novel dynamic attributed network embedding framework - DANE. In particular, DANE first provides an offline method for a consensus embedding and then leverages matrix perturbation theory to maintain the freshness of the end embedding results in an online manner. We perform extensive experiments on both synthetic and real attributed networks to corroborate the effectiveness and efficiency of the proposed framework.
1 INTRODUCTION
Dynamic attributed network embedding addresses evolving topology and node attributes, extending network mining beyond predominantly plain, static networks. DANE combines offline consensus embedding with online updates to maintain fresh representations.
- Motivation: Existing network embedding methods mainly target plain, static networks and overlook complementary node attributes and temporal changes.The gap is especially relevant when network sparsity makes attribute information useful.
- Challenges: Dynamic attributed networks require noise-resilient consensus representations because topology and attributes are correlated but individually noisy or incomplete.The embedding must capture both their individual properties and correlations.
- Approach: DANE introduces an offline model for consensus embedding and an online model that maintains embedding freshness as the network evolves.The framework is designed around an initial offline model followed by online maintenance.
- Evaluation: The framework is evaluated on synthetic and real-world attributed networks for unsupervised and supervised network mining tasks.The evaluation also compares efficiency with baseline methods and DANE's offline counterpart.
2 PROBLEM DEFINITION
The problem definition represents a dynamic attributed network through topology and node attributes that change across time steps. DANE produces an offline embedding initially and updates structure- and attribute-based embeddings online to derive a fresh consensus representation.
- Network Representation: At time t, the network contains n nodes, adjacency matrix A(t), and d-dimensional node attributes represented by X(t).The formulation assumes a constant node count for presentation, while allowing extension to node addition and deletion.
- Dynamic Changes: Between consecutive time steps, topology and attribute changes are represented by ∆A and ∆X, respectively.These changes include edge or node updates and changes in node attribute values.
- Offline Model: The offline model takes A(t) and X(t) as input and outputs attributed network embeddings Y(t) for all nodes.This defines the initial embedding stage of DANE.
- Online Model: At time t+1, the online model uses updated topology, attributes, and intermediate embeddings from time t to output Y(t+1).The online stage is intended to avoid repeatedly recomputing embeddings offline.
- Consensus Update: DANE spectrally embeds network structure and node attributes separately, then maximizes their correlation to obtain a consensus embedding.When ∆A and ∆X occur, matrix perturbation theory updates the two embeddings before deriving the new consensus representation.
3 THE PROPOSED FRAMEWORK - DANE
DANE learns a robust consensus embedding from network structure and node attributes, then updates it online as the attributed network evolves. Its online model uses matrix perturbation to update eigenpairs instead of repeatedly recomputing generalized eigendecompositions.
- 3.1 DANE: Offline Model: DANE addresses noisy and incomplete network topology and node attributes by combining their complementary information into a consensus embedding.The method first derives separate embeddings and then maximizes their correlations so the representations compensate for one another.
- 3.1 DANE: Offline Model: The offline model reduces network noise through a Laplacian-based embedding in which connected nodes are close in the embedded space.The embedding is obtained from eigenvectors associated with the generalized eigen-problem.
- 3.1 DANE: Offline Model: Attribute noise is reduced similarly by normalizing node attributes, constructing a cosine similarity matrix, and retaining its top-k eigenvectors.These attribute embeddings are combined with the network embeddings during consensus learning.
- 3.2 Online Model of DANE: DANE updates the network and attribute embeddings at time t+1 using their perturbations, then derives a final consensus representation by correlation maximization.This online procedure updates each representation before combining them.
- 3.2 Online Model of DANE: The online model updates eigenvalues and eigenvectors from sparse matrix changes, avoiding generalized eigendecomposition at every time step.The paper reports complexity O(Tk2(n + l + la + lx + dx + dx)) and states that sparse perturbations make the online method much more efficient than repeatedly rerunning the offline method.
4 EXPERIMENTS
Experiments evaluate DANE’s effectiveness on clustering and classification, and its efficiency against offline methods across synthetic and real dynamic attributed networks. DANE generally achieves stronger task performance while substantially reducing cumulative running time.
- Experimental Setup: Experiments assess DANE on network clustering, node classification, and cumulative running time across four dynamic attributed networks.The datasets are BlogCatalog, Flickr, Epinions, and DBLP; baselines are rerun at each time step when necessary.
- Datasets: BlogCatalog and Flickr simulate evolution by adding 0.1% new edges and changing 0.1% of attribute values at each time step.Epinions and DBLP are real-world dynamic attributed networks.
- Network Clustering: DANE and DANE-O consistently outperform all baselines on four dynamic attributed networks in clustering, with significant pairwise Wilcoxon signed-rank test results.The comparison uses average clustering performance over time and reports ACC and NMI.
- Node Classification: DANE and DANE-O obtain higher node-classification performance, while attribute-only DANE-A performs better than network-only methods on BlogCatalog, Flickr, and Epinions.For DBLP, labels are more closely related to coauthor relationships than attribute information.
- Efficiency: DANE terminates within one hour on all datasets and is 84×, 21×, and 14× faster than LCMF, CCA, and LANE, respectively, on Flickr.At small embedding dimensions, DANE achieves approximately 8×–12× speedup over DANE-O across the four datasets.
5 RELATED WORK
Related work spans network embedding, attributed-network mining, and dynamic network analysis. Existing approaches generally address only plain or static settings, whereas DANE targets attributed network embedding in a dynamic environment.
- Network Embedding: Network embedding methods learn low-dimensional representations by preserving network proximity, supporting tasks such as node classification, community detection, and link prediction.The reviewed methods primarily concern plain networks.
- Attributed Network Mining: Attributed-network methods combine links and node attributes through techniques such as collective matrix factorization, joint feature learning, and feature selection.These approaches seek shared or complementary representations from network structure and attributes.
- Dynamic Network Analysis: Dynamic network analysis addresses evolving graphs through methods including low-rank approximation, temporal multimode analysis, dynamic feature selection, and rare-category detection.These methods are distinct from dynamic attributed network embedding.
- Research Gap: The paper identifies dynamic attributed network embedding as an unaddressed problem and presents its framework as the first to tackle it.The stated distinction is that prior reviewed methods handle either attributed or dynamic settings rather than their combination.
6 CONCLUSIONS AND FUTURE WORK
The paper presents DANE for learning node embeddings in dynamic attributed networks, combining offline consensus representation learning with efficient online updates. It concludes with future work on higher-order perturbation approximations and extensions to multi-mode and multi-dimensional dynamic networks.
- 6 CONCLUSIONS AND FUTURE WORK: DANE learns consensus embeddings from both network topology and node attributes, then updates them online to capture evolving attributed networks.The offline model captures node proximity across both data representations, while the online method updates embeddings as the network changes.
- 6 CONCLUSIONS AND FUTURE WORK: Experiments on synthetic and real dynamic attributed networks demonstrate the proposed framework’s efficacy and efficiency.
- 6 CONCLUSIONS AND FUTURE WORK: Future work will investigate high-order matrix perturbation approximations for online embedding updates.The current method employs first-order matrix perturbation theory.
- 6 CONCLUSIONS AND FUTURE WORK: The framework is planned for extension to multi-mode and multi-dimensional dynamic networks.