PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Graph Encoder for Attributed Graph Embedding

Ganqu Cui, Jie Zhou, Cheng Yang, Zhiyuan Liu

arXiv:2007.01594v1cs.LGstat.ML

TL;DR

Attributed graph embedding must combine graph topology and node features despite limitations in existing GCN architectures, filters, and reconstruction objectives. AGE separates smoothing from encoding, uses adaptive learning, and outperforms state-of-the-art methods on node clustering and link prediction benchmarks.

  • Problem

    Existing GCN-based attributed graph embedding methods entangle filters with weight matrices, use non-optimal low-pass filters, and rely on reconstruction objectives that may not fit applications.

  • Method

    AGE applies a non-parametric Laplacian smoothing filter to node features, then trains an adaptive encoder using iteratively selected pairwise-similarity samples.

  • Results

    AGE outperforms state-of-the-art methods on node clustering and link prediction across benchmark datasets.

  • Takeaways & Limitations

    AGE provides a unified unsupervised attributed graph embedding framework combining optimal denoising-oriented smoothing with adaptive embedding learning.

  • Takeaways & Limitations

    AGE assumes nearby graph nodes have similar features and selects k = 1/λmax as the optimal smoothing choice under its Laplacian-smoothing analysis.

Abstract

from arXiv · show

Attributed graph embedding, which learns vector representations from graph topology and node features, is a challenging task for graph analysis. Recently, methods based on graph convolutional networks (GCNs) have made great progress on this task. However,existing GCN-based methods have three major drawbacks. Firstly,our experiments indicate that the entanglement of graph convolutional filters and weight matrices will harm both the performance and robustness. Secondly, we show that graph convolutional filters in these methods reveal to be special cases of generalized Laplacian smoothing filters, but they do not preserve optimal low-pass characteristics. Finally, the training objectives of existing algorithms are usually recovering the adjacency matrix or feature matrix, which are not always consistent with real-world applications. To address these issues, we propose Adaptive Graph Encoder (AGE), a novel attributed graph embedding framework. AGE consists of two modules: (1) To better alleviate the high-frequency noises in the node features, AGE first applies a carefully-designed Laplacian smoothing filter. (2) AGE employs an adaptive encoder that iteratively strengthens the filtered features for better node embeddings. We conduct experiments using four public benchmark datasets to validate AGE on node clustering and link prediction tasks. Experimental results show that AGE consistently outperforms state-of-the-art graph embedding methods considerably on these tasks.

1 INTRODUCTION

Attributed graph embedding must jointly capture topology and node features, but existing GCN-based methods have architectural, filtering, and objective limitations. AGE addresses these issues with disentangled filtering, adaptive learning, and benchmark evaluation.

  • Attributed graph embedding jointly represents graph structure and node features for tasks including node classification, link prediction, and node clustering.
  • Existing GCN-based methods commonly use graph autoencoder architectures with a GCN encoder and reconstruction decoder.
  • Entangling graph convolutional filters with weight matrices can reduce training efficiency and harm performance and robustness.
  • Existing graph convolutional filters may fail to remove noise in some high-frequency intervals, preventing optimal low-pass smoothing.
  • Adjacency or feature-matrix reconstruction objectives may conflict with applications by ignoring feature information or retaining high-frequency feature noise.
  • AGE uses a non-parametric Laplacian smoothing filter and an adaptive encoder that selects pairwise-similarity training samples and iteratively fine-tunes embeddings.
  • AGE outperforms state-of-the-art attributed graph embedding methods on node clustering and link prediction benchmarks.

2 RELATED WORK

Graph embedding research progressed from shallow structure-based methods to approaches that jointly encode graph structure and node features. GCN-based attributed graph embedding methods differ mainly in whether they reconstruct adjacency or features.

  • Early graph embedding methods use Laplacian eigenmaps, matrix factorization, or random walks, but their architectures are shallow.
  • Feature-aware methods extend matrix factorization with feature regularization or model features as latent variables in Bayesian networks.
  • Unsupervised GCN-based graph embedding methods are categorized by whether their optimization objectives reconstruct adjacency or node features.
  • Reconstruct the adjacency matrix: Adjacency-reconstruction models use GCN encoders and inner-product decoders to recover localized neighborhood structure.
  • Reconstruct the feature matrix: Feature-reconstruction models treat the adjacency matrix mainly as a filter, but raw feature high-frequency noise can harm learned embeddings.

3 PROPOSED METHOD

AGE formalizes attributed graphs and produces embeddings that preserve topology and feature information. Its pipeline smooths node features before adaptive supervised representation learning for clustering and link prediction.

  • An attributed graph G = (V, E, X) contains nodes, edges, and a node feature matrix X, with topology represented by adjacency matrix A.
  • The embedding matrix Z is intended to preserve both the graph’s topological structure and feature information.
  • AGE consists of a Laplacian smoothing filter followed by an adaptive encoder.
  • Laplacian Smoothing Filter: The smoothing filter denoises high-frequency components of X and supplies smoothed features to the adaptive encoder.
  • Adaptive Encoder: The adaptive encoder selects highly similar or dissimilar node pairs to form a training set and trains representations with supervised learning.
  • The learned embedding matrix Z is used for downstream node clustering and link prediction.

3.3 Laplacian Smoothing Filter

AGE treats node features as graph signals and designs Laplacian smoothing to suppress high frequencies while preserving low frequencies. The generalized filter uses a nonnegative decreasing response, with k = 1/λmax identified as optimal.

  • AGE assumes nearby graph nodes should have similar features, so node features should be smooth on the graph manifold.
  • 3.3.1 Analysis of Smooth Signals.: Graph-signal smoothness is assessed through the Laplacian Rayleigh quotient, where lower values indicate smoother signals.
  • 3.3.1 Analysis of Smooth Signals.: Laplacian eigendecomposition associates smaller eigenvalues with lower-frequency, smoother eigenvectors.
  • 3.3.1 Analysis of Smooth Signals.: The filter aims to remove high-frequency components while preserving low-frequency components using Laplacian smoothing.
  • 3.3.2 Generalized Laplacian Smoothing Filter.: The generalized filter requires frequency response 1−kλ to be nonnegative and decreasing, and stacking t filters yields ˜X = H^t X.
  • 3.3.2 Generalized Laplacian Smoothing Filter.: Setting k = 1 produces the GCN filter, while selecting k = 1/λmax gives the optimal smoothing choice in the stated analysis.
  • 3.3.2 Generalized Laplacian Smoothing Filter.: Because renormalization shrinks λmax to around 3/2, k = 1/2 is not generally optimal; AGE calculates λmax for each dataset.

3.4 Adaptive Encoder

AGE learns node embeddings from Laplacian-smoothed features using an adaptive, similarity-based encoder rather than relying on reconstruction alone. Its curriculum-style sampling progressively focuses training on higher-confidence node pairs.

  • Adaptive encoder: AGE encodes filtered node features with a linear encoder to produce node embeddings.The encoder maps smoothed features ˜X through a weight matrix W.
  • Similarity-based supervision: The method measures pairwise node similarity with cosine similarity after min-max scaling embeddings to [0, 1].This similarity matrix provides training targets for node-pair relationships.
  • Adaptive sampling: AGE selects positive and negative training pairs by ranking pairwise similarities and applying adaptive rank thresholds.The resulting set contains rpos positive samples and n^2 − rneg negative samples before balancing.
  • Adaptive sampling: Negative samples are randomly subsampled each epoch to balance the positive and negative classes before cross-entropy training.Real-world graphs contain substantially more dissimilar pairs than positive pairs.
  • Curriculum update: Inspired by curriculum learning, AGE initially uses more samples and later retains higher-confidence pairs as rpos decreases and rneg increases.Thresholds are updated linearly, and the training set is reconstructed after each update.

4 EXPERIMENTAL SETTINGS

The experiments evaluate AGE on four benchmark networks using an adaptive-encoder procedure and comparisons with feature-only, structure-only, and combined graph-attribute methods. Node clustering and link prediction are assessed with standard metrics, with hyperparameters tuned using DBI.

  • Datasets: AGE is evaluated on Cora, Citeseer, Pubmed, and Wiki for node clustering and link prediction.Cora and Citeseer use binary word vectors, whereas Wiki and Pubmed use tf-idf weighted word vectors.
  • AGE procedure: Algorithm 1 takes adjacency and feature matrices as input and outputs the node embedding matrix Z.The procedure computes a graph Laplacian, smoothing filter, smoothed features, similarities, and training samples before iterative encoding.
  • AGE procedure: The adaptive procedure repeatedly computes embeddings and similarities, selects training samples, trains the encoder, and updates thresholds.These steps are repeated through the specified iteration and threshold-update process.
  • Baseline methods: Comparisons include feature-only, structure-only, and feature-plus-graph methods, including DeepWalk, TADW, GAE, VGAE, ARGA, ARVGA, GALA, MGAE, AGC, and DAEGC.The baselines use varied objectives such as representation learning, adjacency reconstruction, feature reconstruction, and clustering losses.
  • Ablations: AGE variants isolate optimization objectives by combining the same Laplacian filter with adjacency reconstruction, feature reconstruction, filtering alone, or adaptive learning.LS+RA reconstructs adjacency, LS+RX reconstructs features, LS uses smoothed features directly, and AGE uses adaptive learning.
  • Evaluation: Node clustering is measured with ACC, NMI, and ARI, while link prediction uses AUC and AP; higher values indicate better performance.Spectral Clustering is applied to representations from methods that do not specify node clustering.
  • Parameter settings: The encoder uses 400 Adam epochs at learning rate 0.001, a 500-dimensional embedding layer, and threshold updates every 10 epochs.Other hyperparameters, including smoothing depth and sampling thresholds, are tuned using DBI.

5 EXPERIMENTAL RESULTS

Experiments evaluate AGE through controlled comparisons, ablations, eigenvalue-based filter selection, node clustering, and link prediction. AGE generally outperforms baselines, while disentangled filtering improves stability and k = 1/λmax is supported for smoothing.

  • Node clustering: Methods using both feature and graph information usually outperform methods using a single information source on node clustering.The experiments attribute the complementary contributions to different perspectives on clustering.
  • Link prediction: AGE outperforms state-of-the-art unsupervised graph representation models on both AUC and AP for link prediction without explicit links for supervision.The compared reconstruction-based methods use adjacency-matrix reconstruction losses, whereas AGE does not.
  • Controlled comparison: LS+RA outperforms GAE under most circumstances with fewer parameters, while GAE performance decreases as filter layers increase and LS+RA remains relatively stable.The comparison changes only the position of the weight matrices; the remaining parameters are matched.
  • Ablation study: Smoothed features outperform raw features on node clustering because smoothing integrates graph structure.The improvement is described as considerable.
  • Ablation study: AGE outperforms its LS+RA and LS+RX variants, indicating that its adaptive optimization target improves over the two reconstruction-based variants.The variants retain the Laplacian smoothing filter but use different reconstruction objectives.
  • Ablation study: Each AGE component contributes to final performance, and supervision by smoothed-feature similarity outperforms almost all baselines.This ablation supports the adaptive-learning training objective.

6 CONCLUSION

AGE is presented as a unified unsupervised graph representation learning model that combines graph-signal analysis, adaptive learning, and a non-parametric smoothing filter. Standard-benchmark experiments report that it outperformed state-of-the-art baseline algorithms, while future work targets adaptive-learning efficiency.

  • AGE is a unified unsupervised graph representation learning model for attributed graph embedding.
  • AGE designs a non-parametric Laplacian smoothing filter to preserve optimal denoising properties for removing high-frequency noise.
  • AGE uses adaptive learning in its encoder because the paper finds it more appropriate for embedding.
  • Experiments on standard benchmarks show that AGE outperformed state-of-the-art baseline algorithms.
  • Future work could improve adaptive-learning efficiency by avoiding full computation of the pairwise similarity matrix.

A MORE DETAILS ABOUT THE EXPERIMENTS

The section provides additional experimental details intended to support reproducibility.

  • The section describes more details about the experiments.
  • These experimental details are provided to help with reproducibility.
  • The passage frames the section as supplementary experimental documentation.

A.1 Hardware and Software Configurations

All experiments use the same environment, specified by the operating system, CPU, GPU, and software versions.

  • All experiments were conducted on a server under the same environment.
  • The hardware configuration included an Intel Xeon Gold 5218 CPU and a GeForce RTX 2080 Ti GPU.
  • The server used Ubuntu 18.04.3 LTS as its operating system.
  • The software environment included PyTorch 1.3.1 and sklearn 0.21.3.

A.2 Hyperparameter Settings

The paper reports its hyperparameter settings in Table 5, where n denotes the number of nodes in the dataset.

  • The paper reports its hyperparameter settings in Table 5.
  • The hyperparameter settings are presented as a reproducibility reference.
  • Table 5 defines n as the number of nodes in the dataset.
Loading 2007.01594v1…