Norm Augmented Graph AutoEncoders for Link Prediction

• URL: http://arxiv.org/abs/2502.05868v1
• Date: Sun, 09 Feb 2025 12:08:02 GMT
• Title: Norm Augmented Graph AutoEncoders for Link Prediction
• Authors: Yunhui Liu, Huaisong Zhang, Xinyi Gao, Liuye Guo, Zhen Tao, Tieke He,
• Abstract summary: Link Prediction is a crucial problem in graph-structured data. In this study, we demonstrate that the norm of node embeddings learned by GAEs exhibits variation among nodes with different degrees. We show that embeddings with larger norms tend to guide the decoder towards predicting higher scores for positive links and lower scores for negative links.
• Score: 26.246289321470385
• License:
• Abstract: Link Prediction (LP) is a crucial problem in graph-structured data. Graph Neural Networks (GNNs) have gained prominence in LP, with Graph AutoEncoders (GAEs) being a notable representation. However, our empirical findings reveal that GAEs' LP performance suffers heavily from the long-tailed node degree distribution, i.e., low-degree nodes tend to exhibit inferior LP performance compared to high-degree nodes. \emph{What causes this degree-related bias, and how can it be mitigated?} In this study, we demonstrate that the norm of node embeddings learned by GAEs exhibits variation among nodes with different degrees, underscoring its central significance in influencing the final performance of LP. Specifically, embeddings with larger norms tend to guide the decoder towards predicting higher scores for positive links and lower scores for negative links, thereby contributing to superior performance. This observation motivates us to improve GAEs' LP performance on low-degree nodes by increasing their embedding norms, which can be implemented simply yet effectively by introducing additional self-loops into the training objective for low-degree nodes. This norm augmentation strategy can be seamlessly integrated into existing GAE methods with light computational cost. Extensive experiments on various datasets and GAE methods show the superior performance of norm-augmented GAEs.

Related papers

• Node Duplication Improves Cold-start Link Prediction [52.917775253887264]
  Graph Neural Networks (GNNs) are prominent in graph machine learning. Recent studies show that GNNs struggle to produce good results on low-degree nodes. We propose a simple yet surprisingly effective augmentation technique called NodeDup.
  arXiv  Detail & Related papers  (2024-02-15T05:07:39Z)
• Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification [25.831508778029097]
  We introduce AMUD, which quantifies the relationship between node profiles and topology from a statistical perspective. We also propose ADPA as a new directed graph learning paradigm for AMUD.
  arXiv  Detail & Related papers  (2023-12-07T07:54:11Z)
• A Topological Perspective on Demystifying GNN-Based Link Prediction Performance [72.06314265776683]
  Topological Concentration (TC) is based on the intersection of the local subgraph of each node with the ones of its neighbors. We show that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density. We propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the complexity.
  arXiv  Detail & Related papers  (2023-10-06T22:07:49Z)
• OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization [66.30021126251725]
  Graph Neural Networks (GNNs) are currently dominating in modeling graphstructure data. Graph-regularized networks (GR-MLPs) implicitly inject the graph structure information into model weights, while their performance can hardly match that of GNNs in most tasks. We show that GR-MLPs suffer from dimensional collapse, a phenomenon in which the largest a few eigenvalues dominate the embedding space. We propose OrthoReg, a novel GR-MLP model to mitigate the dimensional collapse issue.
  arXiv  Detail & Related papers  (2023-01-31T21:20:48Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  This paper focuses on improving the performance of GNNs via normalization. By studying the long-tailed distribution of node degrees in the graph, we propose a novel normalization method for GNNs. The $scale$ operation of ResNorm reshapes the node-wise standard deviation (NStd) distribution so as to improve the accuracy of tail nodes.
  arXiv  Detail & Related papers  (2022-06-16T13:49:09Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network [102.27090022283208]
  Graph Convolutional Network (GCN) plays pivotal roles in many real-world applications. GCN often exhibits performance disparity with respect to node degrees, resulting in worse predictive accuracy for low-degree nodes. We formulate the problem of mitigating the degree-related performance disparity in GCN from the perspective of the Rawlsian difference principle.
  arXiv  Detail & Related papers  (2022-02-28T05:07:57Z)
• Understanding and Resolving Performance Degradation in Graph Convolutional Networks [105.14867349802898]
  Graph Convolutional Network (GCN) stacks several layers and in each layer performs a PROPagation operation (PROP) and a TRANsformation operation (TRAN) for learning node representations over graph-structured data. GCNs tend to suffer performance drop when the model gets deep. We study performance degradation of GCNs by experimentally examining how stacking only TRANs or PROPs works.
  arXiv  Detail & Related papers  (2020-06-12T12:12:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.