PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Graph Normalized Auto-Encoders

Seong Jin Ahn, Myoung Ho Kim

arXiv:2108.08046v2cs.LGcs.AI

TL;DR

GAEs and VGAEs can produce near-zero embeddings for isolated nodes regardless of their content features, although those features matter when predicting links without connectivity information. VGNAE uses L2-normalization through a graph-normalized convolutional encoder to address this issue. The authors report that it outperforms existing methods on link prediction.

  • Problem

    GAEs can shrink isolated-node embeddings toward zero regardless of content, even though those features matter for link prediction when connectivity is absent.

    Source: §1 · pp. 1–2

  • Method

    VGNAE uses a Graph Normalized Convolutional Network with L2-normalization to derive embeddings for link prediction.

    Source: §1 · p. 2, §3.2 · p. 2, §3.3 · p. 3

  • Results

    The authors report that VGNAE performs better than other existing methods on link prediction.

    Source: §1 · p. 2, §5 · p. 5

  • Takeaways & Limitations

    The authors argue that L2-normalization is effective for generating proper isolated-node embeddings in link prediction.

    Source: §5 · p. 5

Abstract

from arXiv · show

Link prediction is one of the key problems for graph-structured data. With the advancement of graph neural networks, graph autoencoders (GAEs) and variational graph autoencoders (VGAEs) have been proposed to learn graph embeddings in an unsupervised way. It has been shown that these methods are effective for link prediction tasks. However, they do not work well in link predictions when a node whose degree is zero (i.g., isolated node) is involved. We have found that GAEs/VGAEs make embeddings of isolated nodes close to zero regardless of their content features. In this paper, we propose a novel Variational Graph Normalized AutoEncoder (VGNAE) that utilize L2-normalization to derive better embeddings for isolated nodes. We show that our VGNAEs outperform the existing state-of-the-art models for link prediction tasks. The code is available at https://github.com/SeongJinAhn/VGNAE.

1 INTRODUCTION

Graph autoencoders use graph-convolutional embeddings for link prediction, but isolated nodes pose a problem because their content features are important when no connectivity information is available. The paper proposes VGNAE, which uses L2-normalization to address this issue and reports better performance than existing state-of-the-art link-prediction models.

1 INTRODUCTION

  • GAEs learn node embeddings from a GCN encoder through reconstruction loss, building on graph-convolutional methods that combine a node’s features with neighborhood information.The paper notes that many GAE/VGAE variants have since been proposed to improve link prediction.Source: §1 · p. 1
  • Isolated nodes matter because, without connectivity information, their content features play a major role in predicting links.The paper illustrates this with new students in a school social network who initially have no connections.Source: §1 · p. 1
  • Existing GAEs do not properly handle isolated-node content, tending to shrink their embeddings toward zero regardless of those features.The paper attributes this to reducing similarity between isolated-node embeddings and other nodes.Source: §1 · pp. 1–2
  • VGNAE uses L2-normalization in a Graph Normalized Convolutional Network to address isolated-node embeddings and outperforms existing state-of-the-art link-prediction models.The VGAE uses the normalized network to derive the mean and a GCN to derive the variance.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries establish graph and embedding notation, then introduce graph convolutional networks and prior uses of L2-normalization. They distinguish those earlier normalization approaches from this paper’s focus on isolated nodes.

2 PRELIMINARIES

  • A graph is represented as G = (V, E, X), where V is the vertex set, E the edge set, and X the feature matrix; node embeddings are vectors whose L2-norm measures their length.The notation also defines neighbors, vertex count, and the adjacency matrix.Source: §2 · p. 2

2.1 Graph Convolutional Networks

  • GCNs generalize convolution to graphs; prior graph autoencoders reconstruct adjacency, while other methods use linear, adversarial, clustering, or mutual-information approaches.The passage describes GCNs as simplifying ChebyConv with a normalization trick.Source: §2.1 · p. 2

2.2 𝐿2-normalization

  • Prior work uses L2-norm properties or normalization in translation, image recognition, image search, and optimization, including to address norm imbalance.PairNorm and MSGNorm are identified as GCN normalization methods for over-smoothing, not isolated-node problems.Source: §2.2 · p. 2

3 OUR APPROACH

GAE embeddings of isolated nodes tend toward zero regardless of their content features, a phenomenon the paper names the norm-zero tendency. The proposed GNCN uses L2-normalization before propagation, and GNAE/VGNAE use it to derive node embeddings or variational means.

3.1 Norm-zero tendency of isolated nodes

  • GAE embeddings of isolated nodes tend to have near-zero norms, making them indistinguishable regardless of their content features.The paper calls this the “norm-zero tendency of isolated nodes.”Source: §3.1 · p. 2

3.2 Graph Normalized Convolutional Network

  • GNCN applies L2-normalization before propagation to derive node embeddings and prevent isolated-node embeddings from approaching zero.It transforms features with a learnable matrix, normalizes the transformed vectors, and propagates them; s represents the norm of the hidden feature being propagated.Source: §3.2 · pp. 2–3

3.3 Variational Graph Normalized AutoEncoder

  • GNAE uses a GNCN encoder to derive node embeddings and an inner-product decoder to reconstruct the adjacency matrix.The decoder uses a sigmoid function.Source: §3.3 · p. 3
  • VGNAE derives its mean vectors with GNCN and its log-variance parameters with GCN, then optimizes a tractable variational lower bound.Its generative model reconstructs graph structure with an inner-product decoder.Source: §3.3 · p. 3

4 EXPERIMENTS

Experiments evaluate GNCN on isolated-node link prediction and compare GNAE/VGNAE with state-of-the-art models. Across datasets and edge-training divisions, the authors report that their methods perform better, while GNCN improves isolated-node AUC without compromising connected-node performance.

4.1 Datasets

  • The experiments use citation networks Cora, CiteSeer, and PubMed, Coauthor CS, and Amazon Photo.The state-of-the-art comparison uses citation datasets; the GNCN comparison includes Cora, CiteSeer, CS, and Photo.Source: §4.1 · p. 3, §4.3.2 · p. 4, §4.3.1 · p. 4

4.2 Setup

  • On Cora, CiteSeer, and PubMed, GNAE/VGNAE were evaluated for link prediction against LGAE, ARGA, ARGVA, GIC, and sGraphite-VAE, using 20%, 40%, or 80% training edges; AUC and AP were measured.The remaining edges were divided between validation and test sets at a 1:3 ratio, and each set received the same number of randomly sampled negative edges.Source: §4.3.2 · p. 4

4 EXPERIMENTS

  • The experiments compare GNCN encoders with several GCN-based alternatives and evaluate link prediction using AUC and average precision.The encoder comparison includes GCN, GAT, SGCN, SuperGAT, APPNP, GraphHeat, PairNorm, and MSGNorm.Source: §4.3.1 · p. 4, §4.2 · p. 4

4.3.1 GNCN : Power of normalization for isolated nodes.

  • GNCN achieves the highest isolated-node AUC across all graphs without compromising connected-node performance.Other GCN encoders show isolated-node AUC 10–20% below connected-node AUC across graph types.Source: Figure 3 · p. 4, §4.3.1 · p. 4

4.3.2 Performance Comparision of GNAE/VGNAE with state-of-the-art methods.

  • GNAE/VGNAE outperform other methods across all edge-training divisions, with a larger relative advantage when fewer edges are observed.The authors attribute this pattern to the increase in isolated nodes as the ratio of unobserved edges rises.Source: Table 2 · p. 4, §4.3.2 · p. 4

5 CONCLUSIONS

The conclusion states that isolated-node embeddings in GAE and VGAE tend toward zero regardless of node content, which can degrade link prediction. It presents L2-normalization as an effective approach and reports that VGNAE performs better than existing methods.

5 CONCLUSIONS

  • In GAE and VGAE, isolated-node embeddings tend toward zero regardless of content features, a tendency that can significantly degrade link prediction accuracy when many isolated nodes are involved.The conclusion describes this tendency across various graph-structured networks.Source: §5 · pp. 4–5
  • The authors report that VGNAE performs better than existing methods in experiments across graph-structured networks.They describe L2-normalization as effective for generating proper isolated-node embeddings in link prediction.Source: §5 · p. 5
  • The conclusion identifies L2-normalization as an effective technique for generating proper isolated-node embeddings for link prediction.Source: §5 · p. 5

Related papers

Loading 2108.08046v2…