Concise Fuzzy Planar Embedding of Graphs: a Dimensionality Reduction Approach

• URL: http://arxiv.org/abs/1803.03114v2
• Date: Fri, 15 Dec 2023 16:04:22 GMT
• Title: Concise Fuzzy Planar Embedding of Graphs: a Dimensionality Reduction Approach
• Authors: Faisal N. Abu-Khzam, Rana H. Mouawi, Amer Hajj Ahmad and Sergio Thoumi
• Abstract summary: We map a graph representation to a $k$-dimensional space and answer queries of neighboring nodes mainly by measuring Euclidean distances. The accuracy of our answers would decrease but would be compensated for by fuzzy logic which gives an idea about the likelihood of error.
• Score: 0.2867517731896504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The enormous amount of data to be represented using large graphs exceeds in some cases the resources of a conventional computer. Edges in particular can take up a considerable amount of memory as compared to the number of nodes. However, rigorous edge storage might not always be essential to be able to draw the needed conclusions. A similar problem takes records with many variables and attempts to extract the most discernible features. It is said that the ``dimension'' of this data is reduced. Following an approach with the same objective in mind, we can map a graph representation to a $k$-dimensional space and answer queries of neighboring nodes mainly by measuring Euclidean distances. The accuracy of our answers would decrease but would be compensated for by fuzzy logic which gives an idea about the likelihood of error. This method allows for reasonable representation in memory while maintaining a fair amount of useful information, and allows for concise embedding in $k$-dimensional Euclidean space as well as solving some problems without having to decompress the graph. Of particular interest is the case where $k=2$. Promising highly accurate experimental results are obtained and reported.

Related papers

• Weighted Embeddings for Low-Dimensional Graph Representation [0.13499500088995461]
  We propose embedding a graph into a weighted space, which is closely related to hyperbolic geometry but mathematically simpler. We show that our weighted embeddings heavily outperform state-of-the-art Euclidean embeddings for heterogeneous graphs while using fewer dimensions.
  arXiv  Detail & Related papers  (2024-10-08T13:41:03Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• 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)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• 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)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Multi-point dimensionality reduction to improve projection layout reliability [77.34726150561087]
  In ordinary Dimensionality Reduction (DR), each data instance in an m-dimensional space (original space) is mapped to one point in a d-dimensional space (visual space) Our solution, named Red Gray Plus, is built upon and extends a combination of ordinary DR and graph drawing techniques.
  arXiv  Detail & Related papers  (2021-01-15T17:17:02Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Manifold structure in graph embeddings [6.09170287691728]
  This paper shows that existing random graph models, including graphon and other latent position models, predict the data should live near a much lower-dimensional set. One may therefore circumvent the curse of dimensionality by employing methods which exploit hidden manifold structure.
  arXiv  Detail & Related papers  (2020-06-09T10:30:17Z)

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.