Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings

• URL: http://arxiv.org/abs/2109.04526v1
• Date: Thu, 9 Sep 2021 19:24:35 GMT
• Title: Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings
• Authors: Christy Lin, Daniel Sussman, Prakash Ishwar
• Abstract summary: Random walk based node embedding algorithms learn vector representations of nodes by optimizing an objective function of node embedding vectors and skip-bigram statistics computed from random walks on the network. This paper studies properties of random walk based node embeddings in the unsupervised setting of discovering hidden block structure in the network.
• Score: 11.549910517683085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random walk based node embedding algorithms learn vector representations of nodes by optimizing an objective function of node embedding vectors and skip-bigram statistics computed from random walks on the network. They have been applied to many supervised learning problems such as link prediction and node classification and have demonstrated state-of-the-art performance. Yet, their properties remain poorly understood. This paper studies properties of random walk based node embeddings in the unsupervised setting of discovering hidden block structure in the network, i.e., learning node representations whose cluster structure in Euclidean space reflects their adjacency structure within the network. We characterize the ergodic limits of the embedding objective, its generalization, and related convex relaxations to derive corresponding non-randomized versions of the node embedding objectives. We also characterize the optimal node embedding Grammians of the non-randomized objectives for the expected graph of a two-community Stochastic Block Model (SBM). We prove that the solution Grammian has rank $1$ for a suitable nuclear norm relaxation of the non-randomized objective. Comprehensive experimental results on SBM random networks reveal that our non-randomized ergodic objectives yield node embeddings whose distribution is Gaussian-like, centered at the node embeddings of the expected network within each community, and concentrate in the linear degree-scaling regime as the number of nodes increases.

Related papers

• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data. We propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state, rather than just isolated nodes.
  arXiv  Detail & Related papers  (2023-09-29T19:55:56Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Interpolation-based Correlation Reduction Network for Semi-Supervised Graph Learning [49.94816548023729]
  We propose a novel graph contrastive learning method, termed Interpolation-based Correlation Reduction Network (ICRN) In our method, we improve the discriminative capability of the latent feature by enlarging the margin of decision boundaries. By combining the two settings, we extract rich supervision information from both the abundant unlabeled nodes and the rare yet valuable labeled nodes for discnative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• A Variational Edge Partition Model for Supervised Graph Representation Learning [51.30365677476971]
  This paper introduces a graph generative process to model how the observed edges are generated by aggregating the node interactions over a set of overlapping node communities. We partition each edge into the summation of multiple community-specific weighted edges and use them to define community-specific GNNs. A variational inference framework is proposed to jointly learn a GNN based inference network that partitions the edges into different communities, these community-specific GNNs, and a GNN based predictor that combines community-specific GNNs for the end classification task.
  arXiv  Detail & Related papers  (2022-02-07T14:37:50Z)
• Topic-aware latent models for representation learning on networks [5.304857921982132]
  We introduce TNE, a generic framework to enhance the embeddings of nodes acquired by means of random walk-based approaches with topic-based information. We evaluate our methodology in two downstream tasks: node classification and link prediction.
  arXiv  Detail & Related papers  (2021-11-10T08:52:52Z)
• Layer Adaptive Node Selection in Bayesian Neural Networks: Statistical Guarantees and Implementation Details [0.5156484100374059]
  Sparse deep neural networks have proven to be efficient for predictive model building in large-scale studies. We propose a Bayesian sparse solution using spike-and-slab Gaussian priors to allow for node selection during training. We establish the fundamental result of variational posterior consistency together with the characterization of prior parameters.
  arXiv  Detail & Related papers  (2021-08-25T00:48:07Z)
• And/or trade-off in artificial neurons: impact on adversarial robustness [91.3755431537592]
  Presence of sufficient number of OR-like neurons in a network can lead to classification brittleness and increased vulnerability to adversarial attacks. We define AND-like neurons and propose measures to increase their proportion in the network. Experimental results on the MNIST dataset suggest that our approach holds promise as a direction for further exploration.
  arXiv  Detail & Related papers  (2021-02-15T08:19:05Z)
• Consistency of random-walk based network embedding algorithms [13.214230533788932]
  We study the node2vec and DeepWalk algorithms through the perspective of matrix factorization. Our results indicate a subtle interplay between the sparsity of the observed networks, the window sizes of the random walks, and the convergence rates of the node2vec/DeepWalk embedding.
  arXiv  Detail & Related papers  (2021-01-18T22:49:22Z)
• A Self-Attention Network based Node Embedding Model [17.10479440152652]
  We propose SANNE -- a novel unsupervised embedding model. Our SANNE aims to produce plausible embeddings not only for present nodes, but also for newly unseen nodes. Experimental results show that the proposed SANNE obtains state-of-the-art results for the node classification task.
  arXiv  Detail & Related papers  (2020-06-22T09:46:10Z)
• The Effects of Randomness on the Stability of Node Embeddings [5.126380982787905]
  We apply five node embeddings algorithms to graphs and evaluate their stability under randomness. We find significant instabilities in the geometry of embedding spaces independent of the centrality of a node. This suggests that instability effects need to be taken into account when working with node embeddings.
  arXiv  Detail & Related papers  (2020-05-20T13:36:09Z)
• Binarized Graph Neural Network [65.20589262811677]
  We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches. Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
  arXiv  Detail & Related papers  (2020-04-19T09:43:14Z)

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.