Optimization-Free Graph Embedding via Distributional Kernel for Community Detection

• URL: http://arxiv.org/abs/2602.13634v1
• Date: Sat, 14 Feb 2026 06:56:40 GMT
• Title: Optimization-Free Graph Embedding via Distributional Kernel for Community Detection
• Authors: Shuaibin Song, Kai Ming Ting, Kaifeng Zhang, Tianrun Liang,
• Abstract summary: Neighborhood Aggregation Strategy (NAS) is a widely used approach in graph embedding, underpinning both Graph Neural Networks (GNNs) and Weisfeiler-Lehman (WL) methods.<n>This paper identifies two characteristics in a network, i.e., the distributions of nodes and node degrees that are critical for expressive representation but have been overlooked in existing methods.<n>We propose a novel weighted distribution-aware kernel that embeds nodes while taking their distributional characteristics into consideration.
• Score: 7.023830532843621
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neighborhood Aggregation Strategy (NAS) is a widely used approach in graph embedding, underpinning both Graph Neural Networks (GNNs) and Weisfeiler-Lehman (WL) methods. However, NAS-based methods are identified to be prone to over-smoothing-the loss of node distinguishability with increased iterations-thereby limiting their effectiveness. This paper identifies two characteristics in a network, i.e., the distributions of nodes and node degrees that are critical for expressive representation but have been overlooked in existing methods. We show that these overlooked characteristics contribute significantly to over-smoothing of NAS-methods. To address this, we propose a novel weighted distribution-aware kernel that embeds nodes while taking their distributional characteristics into consideration. Our method has three distinguishing features: (1) it is the first method to explicitly incorporate both distributional characteristics; (2) it requires no optimization; and (3) it effectively mitigates the adverse effects of over-smoothing, allowing WL to preserve node distinguishability and expressiveness even after many iterations of embedding. Experiments demonstrate that our method achieves superior community detection performance via spectral clustering, outperforming existing graph embedding methods, including deep learning methods, on standard benchmarks.

Related papers

• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks [16.5175121704107]
  Graph Neural Networks learn on graph-structured data by iteratively aggregating local neighborhood information.<n>In this work we inject randomized global embeddings of node features into standard GNNs, enabling them to efficiently capture long-range dependencies.<n> Experimental results on real-world graph learning tasks confirm that this strategy consistently improves performance over baseline GNNs.
  arXiv  Detail & Related papers  (2025-11-05T19:41:56Z)
• Graph-Sequential Alignment and Uniformity: Toward Enhanced Recommendation Systems [51.716704243764994]
  Our framework uses Graph Neural Network (GNN)-based and sequential recommenders as separate submodules while sharing a unified embedding space optimized jointly.<n> Experiments on three real-world datasets demonstrate that the proposed method significantly outperforms using either approach alone.
  arXiv  Detail & Related papers  (2024-12-05T15:59:05Z)
• Degree-Conscious Spiking Graph for Cross-Domain Adaptation [51.58506501415558]
  Spiking Graph Networks (SGNs) have demonstrated significant potential in graph classification.<n>We introduce a novel framework named Degree-Consicious Spiking Graph for Cross-Domain Adaptation (DeSGraDA)<n>DeSGraDA enhances generalization across domains with three key components.
  arXiv  Detail & Related papers  (2024-10-09T13:45:54Z)
• Robust Node Representation Learning via Graph Variational Diffusion Networks [7.335425547621226]
  In recent years, compelling evidence has revealed that GNN-based node representation learning can be substantially deteriorated by perturbations in a graph structure. To learn robust node representation in the presence of perturbations, various works have been proposed to safeguard GNNs. We propose the Graph Variational Diffusion Network (GVDN), a new node encoder that effectively manipulates Gaussian noise to safeguard robustness on perturbed graphs.
  arXiv  Detail & Related papers  (2023-12-18T03:18:53Z)
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networks [46.14626839260314]
  We show that current Graph Neural Networks (GNNs) are potentially a problematic factor underlying all GNN models for learning on certain datasets. We augment the aggregation operations with their dual, i.e. diversification operators that make the node more distinct and preserve the identity. Such augmentation replaces the aggregation with a two-channel filtering process that, in theory, is beneficial for enriching the node representations. In the experiments, we observe desired characteristics of the models and significant performance boost upon the baselines on 9 node classification tasks.
  arXiv  Detail & Related papers  (2022-12-21T07:24:03Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)
• 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)
• Anisotropic Graph Convolutional Network for Semi-supervised Learning [7.843067454030999]
  Graph convolutional networks learn effective node embeddings that have proven to be useful in achieving high-accuracy prediction results. These networks suffer from the issue of over-smoothing and shrinking effect of the graph due in large part to the fact that they diffuse features across the edges of the graph using a linear Laplacian flow. We propose an anisotropic graph convolutional network for semi-supervised node classification by introducing a nonlinear function that captures informative features from nodes, while preventing oversmoothing.
  arXiv  Detail & Related papers  (2020-10-20T13:56:03Z)
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks [46.14626839260314]
  We show that current Graph Neural Networks (GNNs) are potentially a problematic factor underlying all GNN methods for learning on certain datasets. We augment the aggregation operations with their dual, i.e. diversification operators that make the node more distinct and preserve the identity. Such augmentation replaces the aggregation with a two-channel filtering process that, in theory, is beneficial for enriching the node representations. In the experiments, we observe desired characteristics of the models and significant performance boost upon the baselines on 9 node classification tasks.
  arXiv  Detail & Related papers  (2020-08-20T08:45:16Z)
• 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.