Community Detection Guarantees Using Embeddings Learned by Node2Vec

• URL: http://arxiv.org/abs/2310.17712v3
• Date: Tue, 22 Oct 2024 01:35:02 GMT
• Title: Community Detection Guarantees Using Embeddings Learned by Node2Vec
• Authors: Andrew Davison, S. Carlyle Morgan, Owen G. Ward,
• Abstract summary: We show that clustering on the embedding produced by node2vec gives weakly consistent community recovery for the nodes in block models. We also discuss the use of these embeddings for node and link prediction tasks.
• Score: 5.530212768657544
• License:
• Abstract: Embedding the nodes of a large network into an Euclidean space is a common objective in modern machine learning, with a variety of tools available. These embeddings can then be used as features for tasks such as community detection/node clustering or link prediction, where they achieve state of the art performance. With the exception of spectral clustering methods, there is little theoretical understanding for commonly used approaches to learning embeddings. In this work we examine the theoretical properties of the embeddings learned by node2vec. Our main result shows that the use of $k$-means clustering on the embedding vectors produced by node2vec gives weakly consistent community recovery for the nodes in (degree corrected) stochastic block models. We also discuss the use of these embeddings for node and link prediction tasks. We demonstrate this result empirically, and examine how this relates to other embedding tools for network data.

Related papers

• Reliable Node Similarity Matrix Guided Contrastive Graph Clustering [51.23437296378319]
  We introduce a new framework, Reliable Node Similarity Matrix Guided Contrastive Graph Clustering (NS4GC) Our method introduces node-neighbor alignment and semantic-aware sparsification, ensuring the node similarity matrix is both accurate and efficiently sparse.
  arXiv  Detail & Related papers  (2024-08-07T13:36:03Z)
• EntailE: Introducing Textual Entailment in Commonsense Knowledge Graph Completion [54.12709176438264]
  Commonsense knowledge graphs (CSKGs) utilize free-form text to represent named entities, short phrases, and events as their nodes. Current methods leverage semantic similarities to increase the graph density, but the semantic plausibility of the nodes and their relations are under-explored. We propose to adopt textual entailment to find implicit entailment relations between CSKG nodes, to effectively densify the subgraph connecting nodes within the same conceptual class.
  arXiv  Detail & Related papers  (2024-02-15T02:27:23Z)
• NODDLE: Node2vec based deep learning model for link prediction [0.0]
  We propose NODDLE (integration of NOde2vec anD Deep Learning mEthod), a deep learning model which incorporates the features extracted by node2vec and feeds them into a hidden neural network. Experimental results show that this method yields better results than the traditional methods on various social network datasets.
  arXiv  Detail & Related papers  (2023-05-25T18:43:52Z)
• Fisher Information Embedding for Node and Graph Learning [5.263910852465186]
  We propose a novel attention-based node embedding framework for graphs. Our framework builds upon a hierarchical kernel for multisets of subgraphs around nodes. We provide theoretical insights into generalizability and expressivity of our embeddings.
  arXiv  Detail & Related papers  (2023-05-12T16:15:30Z)
• STERLING: Synergistic Representation Learning on Bipartite Graphs [78.86064828220613]
  A fundamental challenge of bipartite graph representation learning is how to extract node embeddings. Most recent bipartite graph SSL methods are based on contrastive learning which learns embeddings by discriminating positive and negative node pairs. We introduce a novel synergistic representation learning model (STERLING) to learn node embeddings without negative node pairs.
  arXiv  Detail & Related papers  (2023-01-25T03:21:42Z)
• Deep Embedded Clustering with Distribution Consistency Preservation for Attributed Networks [15.895606627146291]
  In this study, we propose an end-to-end deep embedded clustering model for attributed networks. It utilizes graph autoencoder and node attribute autoencoder to respectively learn node representations and cluster assignments. The proposed model achieves significantly better or competitive performance compared with the state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-28T02:35:34Z)
• Variational Co-embedding Learning for Attributed Network Clustering [30.7006907516984]
  Recent works for attributed network clustering utilize graph convolution to obtain node embeddings and simultaneously perform clustering assignments on the embedding space. We propose a variational co-embedding learning model for attributed network clustering (ANC) ANC is composed of dual variational auto-encoders to simultaneously embed nodes and attributes.
  arXiv  Detail & Related papers  (2021-04-15T08:11:47Z)
• Variational Embeddings for Community Detection and Node Representation [5.197034517903854]
  We propose an efficient generative model called VECoDeR for jointly learning Variational Embeddings for Community Detection and node Representation. We demonstrate on several graph datasets that VECoDeR effectively out-performs many competitive baselines on all three tasks.
  arXiv  Detail & Related papers  (2021-01-11T13:36:29Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• Graph Inference Learning for Semi-supervised Classification [50.55765399527556]
  We propose a Graph Inference Learning framework to boost the performance of semi-supervised node classification. For learning the inference process, we introduce meta-optimization on structure relations from training nodes to validation nodes. Comprehensive evaluations on four benchmark datasets demonstrate the superiority of our proposed GIL when compared against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-17T02:52:30Z)

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.