Learning node embeddings via summary graphs: a brief theoretical analysis

• URL: http://arxiv.org/abs/2207.01189v1
• Date: Mon, 4 Jul 2022 04:09:50 GMT
• Title: Learning node embeddings via summary graphs: a brief theoretical analysis
• Authors: Houquan Zhou, Shenghua Liu, Danai Koutra, Huawei Shen, Xueqi Cheng
• Abstract summary: Graph representation learning plays an important role in many graph mining applications, but learning embeddings of large-scale graphs remains a problem. Recent works try to improve scalability via graph summarization -- i.e., they learn embeddings on a smaller summary graph, and then restore the node embeddings of the original graph. We give an in-depth theoretical analysis of three specific embedding learning methods based on introduced kernel matrix.
• Score: 55.25628709267215
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph representation learning plays an important role in many graph mining applications, but learning embeddings of large-scale graphs remains a problem. Recent works try to improve scalability via graph summarization -- i.e., they learn embeddings on a smaller summary graph, and then restore the node embeddings of the original graph. However, all existing works depend on heuristic designs and lack theoretical analysis. Different from existing works, we contribute an in-depth theoretical analysis of three specific embedding learning methods based on introduced kernel matrix, and reveal that learning embeddings via graph summarization is actually learning embeddings on a approximate graph constructed by the configuration model. We also give analysis about approximation error. To the best of our knowledge, this is the first work to give theoretical analysis of this approach. Furthermore, our analysis framework gives interpretation of some existing methods and provides great insights for future work on this problem.

Related papers

• Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis [7.309233340654514]
  This paper introduces a theoretical framework that rigorously analyzes graph prompting from a data operation perspective. We provide a formal guarantee theorem, demonstrating graph prompts capacity to approximate graph transformation operators. We derive upper bounds on the error of these data operations by graph prompts for a single graph and extend this discussion to batches of graphs.
  arXiv  Detail & Related papers  (2024-10-02T15:07:13Z)
• A Comprehensive Survey on Deep Graph Representation Learning [26.24869157855632]
  Graph representation learning aims to encode high-dimensional sparse graph-structured data into low-dimensional dense vectors. Traditional methods have limited model capacity which limits the learning performance. Deep graph representation learning has shown great potential and advantages over shallow (traditional) methods.
  arXiv  Detail & Related papers  (2023-04-11T08:23:52Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  Graph-level learning has been applied to many tasks including comparison, regression, classification, and more. Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures. Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
  arXiv  Detail & Related papers  (2023-01-14T09:15:49Z)
• Graph Learning and Its Advancements on Large Language Models: A Holistic Survey [37.01696685233113]
  This survey focuses on the most recent advancements in integrating graph learning with pre-trained language models. We provide a holistic review that analyzes current works from the perspective of graph structure, and discusses the latest applications, trends, and challenges in graph learning.
  arXiv  Detail & Related papers  (2022-12-17T22:05:07Z)
• Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities [128.55790219377315]
  Graph neural networks have emerged as a leading architecture for many graph-level tasks. graph pooling is indispensable for obtaining a holistic graph-level representation of the whole graph.
  arXiv  Detail & Related papers  (2022-04-15T04:02:06Z)
• Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters [28.50409304490877]
  We develop a theoretical framework for graph classification problems in the partial observation setting. We propose a new graph classification model that works on a randomly sampled subgraph.
  arXiv  Detail & Related papers  (2021-11-05T08:32:46Z)
• Unbiased Graph Embedding with Biased Graph Observations [52.82841737832561]
  We propose a principled new way for obtaining unbiased representations by learning from an underlying bias-free graph. Based on this new perspective, we propose two complementary methods for uncovering such an underlying graph.
  arXiv  Detail & Related papers  (2021-10-26T18:44:37Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Out-of-Sample Representation Learning for Multi-Relational Graphs [8.956321788625894]
  We study the out-of-sample representation learning problem for non-attributed knowledge graphs. We create benchmark datasets for this task, develop several models and baselines, and provide empirical analyses and comparisons of the proposed models and baselines.
  arXiv  Detail & Related papers  (2020-04-28T00:53:01Z)

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.