Edge-Parallel Graph Encoder Embedding

• URL: http://arxiv.org/abs/2402.04403v1
• Date: Tue, 6 Feb 2024 21:04:57 GMT
• Title: Edge-Parallel Graph Encoder Embedding
• Authors: Ariel Lubonja (1), Cencheng Shen (2), Carey Priebe (1) and Randal Burns (1) ((1) Johns Hopkins University, (2) University of Delaware)
• Abstract summary: One-Hot Graph Embedding (GEE) uses a single, linear pass over edges and produces an embedding that convergesally to the spectral embedding. We present a parallel program in the Ligra graph engine that maps functions over the edges of the graph and uses lock-free atomic instrutions to prevent data races.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: New algorithms for embedding graphs have reduced the asymptotic complexity of finding low-dimensional representations. One-Hot Graph Encoder Embedding (GEE) uses a single, linear pass over edges and produces an embedding that converges asymptotically to the spectral embedding. The scaling and performance benefits of this approach have been limited by a serial implementation in an interpreted language. We refactor GEE into a parallel program in the Ligra graph engine that maps functions over the edges of the graph and uses lock-free atomic instrutions to prevent data races. On a graph with 1.8B edges, this results in a 500 times speedup over the original implementation and a 17 times speedup over a just-in-time compiled version.

Related papers

• Efficient Graph Encoder Embedding for Large Sparse Graphs in Python [3.5374094795720854]
  Graph Embedding (GEE) has been shown as the fastest graph embedding technique and is suitable for a variety of network data applications. We propose an improved version of GEE, sparse GEE, which optimize the calculation and storage of zero entries in sparse matrices to enhance the running time further. Our experiments demonstrate that the sparse version achieves significant speedup compared to the original GEE with Python implementation for large sparse graphs, and sparse GEE is capable of processing millions of edges within minutes on a standard laptop.
  arXiv  Detail & Related papers  (2024-06-06T03:49:34Z)
• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNs iteratively update each node's representation in an input graph by aggregating messages from the node's neighbors. MPNNs might quickly become prohibitive for large graphs provided they are not very sparse. We propose approximating the input graph as an intersecting community graph (ICG) -- a combination of intersecting cliques.
  arXiv  Detail & Related papers  (2024-05-31T09:26:26Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. We propose Graph Sparse Training ( GST), which dynamically manipulates sparsity at the data level. GST produces a sparse graph with maximum topological integrity and no performance degradation.
  arXiv  Detail & Related papers  (2024-02-02T09:10:35Z)
• 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)
• Efficiently Visualizing Large Graphs [18.764862799181053]
  We propose a novel dimension reduction method for graph visualization, called t-Distributed Graph Neighbor Embedding (t-SGNE) t-SGNE is specifically designed to visualize cluster structures in the graph. To suit t-SGNE, we combined Laplacian Eigenmaps with the shortest path algorithm in graphs to form the graph embedding algorithm ShortestPath Laplacian Eigenmaps Embedding (SPLEE)
  arXiv  Detail & Related papers  (2023-10-17T12:07:14Z)
• Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs [24.761152163389735]
  We present a one-shot method for compressing large labeled graphs called Random Edge Coding. Experiments indicate Random Edge Coding can achieve competitive compression performance on real-world network datasets.
  arXiv  Detail & Related papers  (2023-05-16T12:23:18Z)
• Boosting Graph Embedding on a Single GPU [3.093890460224435]
  We present GOSH, a GPU-based tool for embedding large-scale graphs with minimum hardware constraints. It employs a novel graph coarsening algorithm to enhance the impact of updates and minimize the work for embedding. It also incorporates a decomposition schema that enables any arbitrarily large graph to be embedded with a single GPU.
  arXiv  Detail & Related papers  (2021-10-19T15:25:04Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale (GAS) is a framework for scaling arbitrary message-passing GNNs to large graphs. Gas prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations. Gas reaches state-of-the-art performance on large-scale graphs.
  arXiv  Detail & Related papers  (2021-06-10T09:26:56Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
  arXiv  Detail & Related papers  (2020-06-15T22:07:54Z)

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.