${\rm N{\small ode}S{\small ig}}$: Random Walk Diffusion meets Hashing for Scalable Graph Embeddings

• URL: http://arxiv.org/abs/2010.00261v1
• Date: Thu, 1 Oct 2020 09:07:37 GMT
• Title: ${\rm N{\small ode}S{\small ig}}$: Random Walk Diffusion meets Hashing for Scalable Graph Embeddings
• Authors: Abdulkadir \c{C}elikkanat and Apostolos N. Papadopoulos and Fragkiskos D. Malliaros
• Abstract summary: $rm Nsmall odeSsmall ig$ is a scalable embedding model that computes binary node representations. $rm Nsmall odeSsmall ig$ exploits random walk diffusion probabilities via stable random projection hashing.
• Score: 7.025709586759654
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning node representations is a crucial task with a plethora of interdisciplinary applications. Nevertheless, as the size of the networks increases, most widely used models face computational challenges to scale to large networks. While there is a recent effort towards designing algorithms that solely deal with scalability issues, most of them behave poorly in terms of accuracy on downstream tasks. In this paper, we aim at studying models that balance the trade-off between efficiency and accuracy. In particular, we propose ${\rm N{\small ode}S{\small ig}}$, a scalable embedding model that computes binary node representations. ${\rm N{\small ode}S{\small ig}}$ exploits random walk diffusion probabilities via stable random projection hashing, towards efficiently computing embeddings in the Hamming space. Our extensive experimental evaluation on various graphs has demonstrated that the proposed model achieves a good balance between accuracy and efficiency compared to well-known baseline models on two downstream tasks.

Related papers

• Efficient Verification-Based Face Identification [50.616875565173274]
  We study the problem of performing face verification with an efficient neural model $f$. Our model leads to a substantially small $f$ requiring only 23k parameters and 5M floating point operations (FLOPS) We use six face verification datasets to demonstrate that our method is on par or better than state-of-the-art models.
  arXiv  Detail & Related papers  (2023-12-20T18:08:02Z)
• Quantifying lottery tickets under label noise: accuracy, calibration, and complexity [6.232071870655069]
  Pruning deep neural networks is a widely used strategy to alleviate the computational burden in machine learning. We use the sparse double descent approach to identify univocally and characterise pruned models associated with classification tasks.
  arXiv  Detail & Related papers  (2023-06-21T11:35:59Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  A computationally less intensive and node connectivity aware uniform sampling method is proposed. The advantages of the proposed algorithm become more enhanced when the algorithm is applied to large graphs.
  arXiv  Detail & Related papers  (2021-10-21T19:16:16Z)
• One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objective [86.48094395282546]
  A deep hashing model typically has two main learning objectives: to make the learned binary hash codes discriminative and to minimize a quantization error. We propose a novel deep hashing model with only a single learning objective. Our model is highly effective, outperforming the state-of-the-art multi-loss hashing models on three large-scale instance retrieval benchmarks.
  arXiv  Detail & Related papers  (2021-09-29T14:27:51Z)
• Parameter Efficient Deep Neural Networks with Bilinear Projections [16.628045837101237]
  We address the parameter redundancy problem in deep neural networks (DNNs) by replacing conventional full projections with bilinear projections. For a fully-connected layer with $D$ input nodes and $D$ output nodes, applying bilinear projection can reduce the model space complexity. Experiments on four benchmark datasets show that applying the proposed bilinear projection to deep neural networks can achieve even higher accuracies.
  arXiv  Detail & Related papers  (2020-11-03T00:17:24Z)
• Towards Deep Learning Models Resistant to Large Perturbations [0.0]
  Adversarial robustness has proven to be a required property of machine learning algorithms. We show that the well-established algorithm called "adversarial training" fails to train a deep neural network given a large, but reasonable, perturbation magnitude.
  arXiv  Detail & Related papers  (2020-03-30T12:03:09Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.