Embedding Directed Graphs in Potential Fields Using FastMap-D

• URL: http://arxiv.org/abs/2006.03112v1
• Date: Thu, 4 Jun 2020 19:50:04 GMT
• Title: Embedding Directed Graphs in Potential Fields Using FastMap-D
• Authors: Sriram Gopalakrishnan, Liron Cohen, Sven Koenig, T.K. Satish Kumar
• Abstract summary: We present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.
• Score: 24.525270899573734
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. FastMap-D learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.

Related papers

• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance [18.522233517515975]
  We introduce an extension of Gromov-Wasserstein distance for comparing graphs whose both nodes and edges have features. We empirically show the effectiveness of the novel distance in learning tasks where graphs occur in either input space or output space.
  arXiv  Detail & Related papers  (2023-09-28T17:05:03Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested. Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
  arXiv  Detail & Related papers  (2023-05-13T17:29:18Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Primitive Graph Learning for Unified Vector Mapping [14.20286798139897]
  GraphMapper is a unified framework for end-to-end vector map extraction from satellite images. We convert vector shape prediction, regularization, and topology reconstruction into a unique primitive graph learning problem. Our model outperforms state-of-the-art methods by 8-10% in both tasks on public benchmarks.
  arXiv  Detail & Related papers  (2022-06-28T12:33:18Z)
• FastMapSVM: Classifying Complex Objects Using the FastMap Algorithm and Support-Vector Machines [12.728875331529345]
  We present FastMapSVM, a novel framework for classifying complex objects. FastMapSVM combines the strengths of FastMap and Support-Map Machines. We show that FastMapSVM's performance is comparable to that of other state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-04-07T18:01:16Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL) is a framework for embedding entire graphs in a vector space. We leverage new insights on defining similarity between graphs as a function of the similarity between their node embedding distributions. We evaluate our new graph embedding approach on various benchmark graph-property prediction tasks.
  arXiv  Detail & Related papers  (2020-06-16T18:23:00Z)

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.