Node Duplication Improves Cold-start Link Prediction

• URL: http://arxiv.org/abs/2402.09711v1
• Date: Thu, 15 Feb 2024 05:07:39 GMT
• Title: Node Duplication Improves Cold-start Link Prediction
• Authors: Zhichun Guo, Tong Zhao, Yozen Liu, Kaiwen Dong, William Shiao, Neil Shah, Nitesh V. Chawla
• Abstract summary: 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.
• Score: 52.917775253887264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are prominent in graph machine learning and have shown state-of-the-art performance in Link Prediction (LP) tasks. Nonetheless, recent studies show that GNNs struggle to produce good results on low-degree nodes despite their overall strong performance. In practical applications of LP, like recommendation systems, improving performance on low-degree nodes is critical, as it amounts to tackling the cold-start problem of improving the experiences of users with few observed interactions. In this paper, we investigate improving GNNs' LP performance on low-degree nodes while preserving their performance on high-degree nodes and propose a simple yet surprisingly effective augmentation technique called NodeDup. Specifically, NodeDup duplicates low-degree nodes and creates links between nodes and their own duplicates before following the standard supervised LP training scheme. By leveraging a ''multi-view'' perspective for low-degree nodes, NodeDup shows significant LP performance improvements on low-degree nodes without compromising any performance on high-degree nodes. Additionally, as a plug-and-play augmentation module, NodeDup can be easily applied to existing GNNs with very light computational cost. Extensive experiments show that NodeDup achieves 38.49%, 13.34%, and 6.76% improvements on isolated, low-degree, and warm nodes, respectively, on average across all datasets compared to GNNs and state-of-the-art cold-start methods.

Related papers

• High-Pass Graph Convolutional Network for Enhanced Anomaly Detection: A Novel Approach [0.0]
  This paper proposes a novel approach by introducing a High-Pass Graph Convolution Network (HP-GCN) for Graph Anomaly Detection (GAD) The proposed HP-GCN leverages high-frequency components to detect anomalies, as anomalies tend to increase high-frequency signals within the network of normal nodes. The model is evaluated and validated on YelpChi, Amazon, T-Finance, and T-Social datasets.
  arXiv  Detail & Related papers  (2024-11-04T05:38:07Z)
• 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)
• GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation [48.88356355021239]
  Graph neural networks (GNNs) usually perform satisfactorily on high-degree nodes with rich neighbor information but struggle with low-degree nodes. We propose a test-time augmentation framework, namely GraphPatcher, to enhance test-time generalization of any GNNs on low-degree nodes. GraphPatcher consistently enhances common GNNs' overall performance by up to 3.6% and low-degree performance by up to 6.5%, significantly outperforming state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-10-01T21:50:03Z)
• Position-based Hash Embeddings For Scaling Graph Neural Networks [8.87527266373087]
  Graph Neural Networks (GNNs) compute node representations by taking into account the topology of the node's ego-network and the features of the ego-network's nodes. When the nodes do not have high-quality features, GNNs learn an embedding layer to compute node embeddings and use them as input features. To reduce the memory associated with this embedding layer, hashing-based approaches, commonly used in applications like NLP and recommender systems, can potentially be used. We present approaches that take advantage of the nodes' position in the graph to dramatically reduce the memory required.
  arXiv  Detail & Related papers  (2021-08-31T22:42:25Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• 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)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  Graph neural networks (GNNs) learn the representation of a node by aggregating its neighbors. Over-smoothing is one of the key issues which limit the performance of GNNs as the number of layers increases. We introduce two over-smoothing metrics and a novel technique, i.e., differentiable group normalization (DGN)
  arXiv  Detail & Related papers  (2020-06-12T07:18:02Z)

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.