Principal Graph Encoder Embedding and Principal Community Detection

• URL: http://arxiv.org/abs/2501.14939v1
• Date: Fri, 24 Jan 2025 21:55:04 GMT
• Title: Principal Graph Encoder Embedding and Principal Community Detection
• Authors: Cencheng Shen, Yuexiao Dong, Carey E. Priebe, Jonathan Larson, Ha Trinh, Youngser Park,
• Abstract summary: We introduce the concept of principal communities and propose a principal graph encoder embedding method that concurrently detects these communities.<n>The method computes a sample community score for each community, ranking them to measure community importance and estimate a set of principal communities.
• Score: 15.747768357012488
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce the concept of principal communities and propose a principal graph encoder embedding method that concurrently detects these communities and achieves vertex embedding. Given a graph adjacency matrix with vertex labels, the method computes a sample community score for each community, ranking them to measure community importance and estimate a set of principal communities. The method then produces a vertex embedding by retaining only the dimensions corresponding to these principal communities. Theoretically, we define the population version of the encoder embedding and the community score based on a random Bernoulli graph distribution. We prove that the population principal graph encoder embedding preserves the conditional density of the vertex labels and that the population community score successfully distinguishes the principal communities. We conduct a variety of simulations to demonstrate the finite-sample accuracy in detecting ground-truth principal communities, as well as the advantages in embedding visualization and subsequent vertex classification. The method is further applied to a set of real-world graphs, showcasing its numerical advantages, including robustness to label noise and computational scalability.

Related papers

• PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities [7.130067003076749]
  PieClam is a graph autoencoder for representing any graph as overlapping generalized communities. We show that PieClam is a universal autoencoder, able to uniformly approximately reconstruct any graph.
  arXiv  Detail & Related papers  (2024-09-18T00:49:42Z)
• A multi-core periphery perspective: Ranking via relative centrality [4.33459568143131]
  Community and core-periphery are two widely studied graph structures. The impact of inferring the core-periphery structure of a graph on understanding its community structure is not well utilized. We introduce a novel for graphs with ground truth communities, where each community has a densely connected part (the core) and the rest is more sparse (the periphery)
  arXiv  Detail & Related papers  (2024-06-06T20:21:27Z)
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery [16.209340214884776]
  This paper introduces a refined graph encoder embedding method, enhancing the original graph encoder embedding through linear transformation, self-training, and hidden community recovery. We show how our proposed method can effectively identify useful hidden communities under block models.
  arXiv  Detail & Related papers  (2024-05-21T13:48:07Z)
• 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)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection [16.743897700396218]
  We introduce a novel and computationally efficient method for embedding, community detection, and community size determination. Our approach leverages a normalized one-hot graph encoder and a rank-based cluster size measure. Through extensive simulations, we demonstrate the excellent numerical performance of our proposed graph encoder ensemble algorithm.
  arXiv  Detail & Related papers  (2023-01-18T14:49:43Z)
• Hub-aware Random Walk Graph Embedding Methods for Classification [44.99833362998488]
  We propose two novel graph embedding algorithms based on random walks that are specifically designed for the node classification problem. The proposed methods are experimentally evaluated by analyzing the classification performance of three classification algorithms trained on embeddings of real-world networks.
  arXiv  Detail & Related papers  (2022-09-15T20:41:18Z)
• Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling [8.931361895613646]
  Graph representation learning (also called graph embeddings) is a popular technique for incorporating network structure into machine learning models. We provide an empirical and theoretical analysis for the performance of a class of embeddings on the common task of pairwise community labeling. We prove that popular low-dimensional factorization methods either cannot produce community structure, or can only produce unstable" communities.
  arXiv  Detail & Related papers  (2022-01-20T22:43:37Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Amortized Probabilistic Detection of Communities in Graphs [39.56798207634738]
  We propose a simple framework for amortized community detection. We combine the expressive power of GNNs with recent methods for amortized clustering. We evaluate several models from our framework on synthetic and real datasets.
  arXiv  Detail & Related papers  (2020-10-29T16:18:48Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)

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.