Paper Reading AI Learner

Improving embedding of graphs with missing data by soft manifolds

2023-11-29 12:48:33
Andrea Marinoni, Pietro Lio', Alessandro Barp, Christian Jutten, Mark Girolami

Abstract

Embedding graphs in continous spaces is a key factor in designing and developing algorithms for automatic information extraction to be applied in diverse tasks (e.g., learning, inferring, predicting). The reliability of graph embeddings directly depends on how much the geometry of the continuous space matches the graph structure. Manifolds are mathematical structure that can enable to incorporate in their topological spaces the graph characteristics, and in particular nodes distances. State-of-the-art of manifold-based graph embedding algorithms take advantage of the assumption that the projection on a tangential space of each point in the manifold (corresponding to a node in the graph) would locally resemble a Euclidean space. Although this condition helps in achieving efficient analytical solutions to the embedding problem, it does not represent an adequate set-up to work with modern real life graphs, that are characterized by weighted connections across nodes often computed over sparse datasets with missing records. In this work, we introduce a new class of manifold, named soft manifold, that can solve this situation. In particular, soft manifolds are mathematical structures with spherical symmetry where the tangent spaces to each point are hypocycloids whose shape is defined according to the velocity of information propagation across the data points. Using soft manifolds for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets. Experimental results on reconstruction tasks on synthetic and real datasets show how the proposed approach enable more accurate and reliable characterization of graphs in continuous spaces with respect to the state-of-the-art.

Abstract (translated)

在设计和开发应用于各种任务的自动信息抽取算法中,将嵌入图放入连续空间是一个关键因素。这个因素直接取决于连续空间中几何结构的相似程度。流形是一种数学结构,可以将其拓扑空间中的图特征融入其中,特别是节点距离。基于流形的图嵌入算法的最先进技术利用了每个点在流形上的投影在切向空间上类似于欧氏空间的假设。尽管这个条件有助于实现嵌入问题的高效分析解决方案,但它并不代表处理现代现实图的适当设置。在本文中,我们引入了一种新型的流形类,称为软流形,可以解决这个问题。特别地,软流形是具有球对称的数学结构,其中每个点的切向空间是一个半椭圆,其形状是由数据点中信息传播的速度定义的。使用软流形进行图嵌入,我们可以为复杂数据集上的任何数据分析任务提供连续空间。在合成和真实数据集上的重构任务实验结果表明,与最先进的技术相比,所提出的方案使对连续空间中图的描述更加准确和可靠。

URL

https://arxiv.org/abs/2311.17598

PDF

https://arxiv.org/pdf/2311.17598.pdf


Tags
3D Action Action_Localization Action_Recognition Activity Adversarial Agent Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot