Optimization-Free Graph Embedding via Distributional Kernel for Community Detection This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ. Manuscript received April 19, 2021; revised August 16, 2021.
Shuaibin Song, Kai Ming Ting, Kaifeng Zhang, Tianrun Liang · 2026
Read Optimization-Free Graph Embedding via Distributional Kernel for Community Detection This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ. Manuscript received April 19, 2021; revised August 16, 2021. by Shuaibin Song, Kai Ming Ting, Kaifeng Zhang, Tianrun Liang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-13634.txt.
Introduction
Graph embedding by neighbor pooling powers graph neural networks and Weisfeiler-Lehman methods, but repeated pooling blurs node identities, a flaw called over-smoothing. This paper traces part of that flaw to two missed network traits: the spreads of nodes and of node degrees, which matter for rich representation. A new weighted spread-aware kernel embeds nodes while respecting those spread traits.
The method has three standout traits. It is the first to plainly include both traits, it requires no tuning, and it eases over-smoothing so Weisfeiler-Lehman methods preserve node distinctness and richness after many iterations. Tests show superior group finding via spectrum grouping over existing graph embedding methods, including deep learning methods, on standard benchmarks. Shuaibin Song leads the work with three co-authors.
Catalog record
| CREATOR | Shuaibin Song, Kai Ming Ting, Kaifeng Zhang, Tianrun Liang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-13634
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimization-Free Graph Embedding via Distributional Kernel for Community Detection This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ. Manuscript received April 19, 2021; revised August 16, 2021. Shuaibin Song, Kai Ming Ting, Kaifeng Zhang, Tianrun Liang 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. I Introduction Community detection or graph clustering of an attributed network aims to partition the network into several disjoint communities in which each community has nodes satisfying structural closeness and attribute homophily [ 3 ] . As a fundamental problem in graph data mining, it has gained traction within the research community. A common framework in community detection consists of two key steps. The first step is graph embedding. It aims to map each node and its associated neighborhood subgraph into a vector in a new embedded space. The second step is clustering, typically applying an existing clustering method like spectral clustering or K-means on the set of embedded vectors produced in the first step. Evidently, the pre-requisite for successful clustering depends critically on an embedding that preserves intra-community similarity while separating inter-community differences. However, existing embedding methods have significant challenges in achieving this aim. One major issue is over-smoothing [ 16 ] , a phenomenon characterized by the loss of node distinguishability as the number of aggregation increases, which in turn severely constrains the depth and expressiveness of of Neighborhood Aggregation Strategy (NAS) [ 45 ] . An associated but less-studied problem is the imbalanced smoothing rates across different nodes, where high-degree or densely connected nodes tend to lose discriminability faster than sparse ones. While over-smoothing has been widely studied [ 14 , 7 , 1 ] , an effective solution remains elusive. The problem of imbalanced smoothing rates has received little attention; only NDLS [ 50 ] offers a partial remedy, but it does not account for the distributional characteristics underlying this imbalance. Furthermore, existing clustering algorithms have difficulty discovering clusters with varying densities—a well-known limitation of spectral clustering and density-based clustering (see e.g., [ 22 , 24 ] ). This limitation becomes particularly problematic when the embedded representation contains clusters of varying densities, a subtlety that existing graph embedding methods often overlook (e.g., [ 50 , 13 , 37 , 49 ] ). We argue that these challenges—of over-smoothing and embedding inadequacy of creating clusters of varying densities—stem from a fundamental oversight: existing embedding methods treat nodes by ignoring two critical distributional characteristics that substantially influence the embedding quality: 1) Distribution of node vectors that are densely populated in some regions while others are sparse in input space. An existing NAS-method propagates and amplify this distributional characteristic into the embedded space with increased embedding iterations. 2) Distribution of node degrees 1 1 1 Note that this distribution is different from the term ‘degree distribution’ used in network science. The latter is the probability distribution of degrees over the whole network, ignoring the input space. such that the high-degree nodes aggregate information from many neighbors, while low-degree nodes aggregate from few neighbors. This imbalance leads to different smoothing rates in different regions in the input and embedded spaces during the NAS iterations. The failure of existing embedding methods to account for these two types of distributions in a network leads to poor community detection results. Inspired by the success of Isolation Graph Kernel (IGK) in incorporating the distributional information in a graph to improve graph classification accuracy [ 46 ] , we investigate whether a distribution-aware embedding approach can simultaneously address the challenges of over-smoothing, differing smoothing rates, and clusters of varying densities in community detection. We are the first to investigate an integrated approach to deal with the impacts of these two types of distributions in community detection which is arguably more challenging than graph classification (studied in many works on graph embedding [ 44 ] because it is unsupervised. The main contributions of this work are: 1. Stipulating two necessary conditions of a graph embedding method (Definition 6 ) such that spectral clustering is free from the above-mentioned issue of clusters of varied densities in an embedded space. 2. Identifying the two types of distributions in a graph that must be taken into consideration in graph embedding such that the embedded space has no clusters of varied densities. We show that existing methods are weaker because they have overlooked these distributions. We are the first to investigate these issues arising from these two types of distributions in a network. 3. Proposing a multi-level weighted distributional kernel, called mWDK, to integrate both types of distributions as a means to graph embedding that satisfies the two conditions mentioned in the first contribution. In addition, mWDK is derived without optimization. 4. Creating a new community detection algorithm based on mWDK to produce better clustering outcomes, on a network with the two types of distributions, than existing graph embedding methods including deep learning based Graph Neural Networks methods. Fig. 1: Neighborhood aggregation in input space (top) vs. distribution-aware space derived from the distributional kernel mWDK (bottom). Standard NAS leads to over-smoothing, merging two subgraphs into indistinguishable representations. In contrast, mWDK preserves discriminability by incorporating their distributional differences. The proposed integrated approach is distinguished from existing approaches in the following ways: • We propose a distribution -oriented graph embedding approach for community detection. Existing graph embedding methods are point -oriented that do not take (a) the distribution of node vectors and (b) the distribution of node degrees into consideration. The distribution-oriented approach via distributional kernel is a more powerful means to differentiate distinct nodes in a network with the two types of distributions, as illustrated in Figure 1 . We show for the first time that WL, which is a NAS, can maintain node discriminability during aggregations, effectively mitigating the adverse effects of over-smoothing. • Isolation Kernel (IK) [ 46 , 33 ] is used as the main tool to effectively handle clusters of varied densities 2 2 2 Although IGK [ 46 ] also employs IK, there are three key differences: (a) IGK uses the Isolation Forest implementation; we uses the Voronoi Diagram implementation [ 24 ] . (b) IGK is designed for supervised graph classification on a dataset of small graphs;