Multi-Relation Graph-Kernel Strengthen Network for Graph-Level Clustering
Renda Han 1 1 , Guangzhen Yao 2 5 1 , Mingyuan Li 4 1 , Wenxin Zhang 9 5 1 , Yu Li 6 1 , Wen Xin 1 2 , Huajie Lei 1 3 , Mengfei Li 1 5 4 , Zeyu Zhang 7 1 , Chengze Du 2 1 , and Yahe Tian 8 1 · 2025
Read Multi-Relation Graph-Kernel Strengthen Network for Graph-Level Clustering by Renda Han 1 1 , Guangzhen Yao 2 5 1 , Mingyuan Li 4 1 , Wenxin Zhang 9 5 1 , Yu Li 6 1 , Wen Xin 1 2 , Huajie Lei 1 3 , Mengfei Li 1 5 4 , Zeyu Zhang 7 1 , Chengze Du 2 1 , and Yahe Tian 8 1 (2025) 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-2504-01605.txt.
Introduction
Renda Han and a team of co-authors present a network for grouping whole graphs into clusters, in two thousand twenty-five. Graph-level clustering sorts unlabeled graphs, such as molecules, into like groups. Deep methods often pool away rich structure, while classic kernel methods search substructures in a fixed, costly way.
Their network builds graphs with several kinds of relation between nodes and graphs. Kernel methods then extract similarity features from those richer graphs. A refinement step aligns the relation views and fuses them step by step into stronger graph-level features. Tests on several benchmark sets beat leading methods, which the authors credit to joining both traditions.
Catalog record
| CREATOR | Renda Han 1 1 , Guangzhen Yao 2 5 1 , Mingyuan Li 4 1 , Wenxin Zhang 9 5 1 , Yu Li 6 1 , Wen Xin 1 2 , Huajie Lei 1 3 , Mengfei Li 1 5 4 , Zeyu Zhang 7 1 , Chengze Du 2 1 , and Yahe Tian 8 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01605
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Relation Graph-Kernel Strengthen Network for Graph-Level Clustering Renda Han 1 1 , Guangzhen Yao 2 5 1 , Mingyuan Li 4 1 , Wenxin Zhang 9 5 1 , Yu Li 6 1 , Wen Xin 1 2 , Huajie Lei 1 3 , Mengfei Li 1 5 4 , Zeyu Zhang 7 1 , Chengze Du 2 1 , and Yahe Tian 8 1 Abstract Graph-level clustering is a fundamental task of data mining, aiming at dividing unlabeled graphs into distinct groups. However, existing deep methods that are limited by pooling have difficulty extracting diverse and complex graph structure features, while traditional graph kernel methods rely on exhaustive substructure search, unable to adaptively handle multi-relational data. This limitation hampers producing robust and representative graph-level embeddings. To address this issue, we propose a novel M ulti-Relation G raph-Kernel S trengthen N etwork for Graph-Level Clustering (MGSN), which integrates multi-relation modeling with graph kernel techniques to fully leverage their respective advantages. Specifically, MGSN constructs multi-relation graphs to capture diverse semantic relationships between nodes and graphs, which employ graph kernel methods to extract graph similarity features, enriching the representation space. Moreover, a relation-aware representation refinement strategy is designed, which adaptively aligns multi-relation information across views while enhancing graph-level features through a progressive fusion process. Extensive experiments on multiple benchmark datasets demonstrate the superiority of MGSN over state-of-the-art methods. The results highlight its ability to leverage multi-relation structures and graph kernel features, establishing a new paradigm for robust graph-level clustering. I Introduction Graph-level clustering [ 1 ] plays a pivotal role in understanding complex, high-dimensional data by identifying patterns [ 2 ] and relationships across multi-graphs. This approach is particularly valuable in domains such as bioinformatics [ 3 ] , recommender systems [ 4 ] , and social media analysis [ 5 , 6 ] , where the latent structure of graph-level holds key insights. By focusing on graph-level features, this method more effectively organizes and analyzes complex problems, informing decision-making in areas such as disease prediction [ 7 ] , user behavior [ 8 ] , and content categorization [ 9 ] . Moreover, it is more effective in uncovering latent patterns that are not readily identifiable. The existing graph-level clustering methods are mainly divided into two categories by learning mode: traditional graph kernel methods based on spectral clustering and deep methods based on representation learning. Traditional graph kernel methods [ 10 , 11 , 12 , 13 , 14 ] measure similarity between graphs using predefined structural features, such as random walks or shortest paths. These methods excel in capturing the structural features of smaller graphs and are effective for graphs with well-defined, simple relationships. However, they face significant challenges when applied to large, heterogeneous graphs, especially those with multiple relational types, due to scalability limitations. In contrast, deep learning-based methods have emerged as powerful tools for learning graph representations. Graph Convolutional Networks (GCNs) [ 15 , 16 , 17 ] automatically learn from raw graph data, capturing complex, non-linear relationships between nodes while maintaining scalability, which makes them suitable for a wide range of large-scale applications. These graph-level clustering methods [ 18 , 19 , 20 , 21 ] enhance the robustness of graph representations by leveraging contrastive learning, multi-view clustering, and automated data augmentation techniques, making them well-suited for complex and diverse datasets. They capture both global semantics and local structures within graphs, improving their ability to represent intricate graph relationships. These methods aggregate node-level features into a global graph-level representation, enabling them to scale more effectively and adapt to more complex scenes. However, methods in both categories encounter significant scalability challenges. Traditional graph kernel approaches, which depend on exhaustive substructure searches to assess graph similarity, often fall short in capturing latent dependencies among relational types. These dependencies are crucial for accurately constructing the graph-level representation. By neglecting the intricate multi-relational dynamics within graphs, traditional methods fail to encapsulate their underlying semantics, thereby limiting their effectiveness in processing multi-relational graph data. On the other hand, while deep learning methods have overcome many limitations of traditional approaches by automatically learning important features and relationships in graph structures, they are still constrained by pooling operations. These operations, which reduce dimensionality and aggregate node features, often result in the loss of crucial structural details, hindering the model’s ability to capture complex relational patterns within graphs. To solve this issue, inspired by multi-relation clustering [ 22 ] , we combine deep learning-based methods with graph kernel methods to offer a Multi-relation Graph-kernel Strengthen Network for graph-level clustering (MGSN) to overcome the individual limitations of each approach. Specifically, the model generates graph representations using a GCN, which serves as input for spectral clustering to construct multi-relational graphs. By incorporating various relational types, it captures the semantic relationships between nodes and graphs, effectively identifying the complex interactions within the graph structure. This approach allows for a more accurate representation of the multi-relational features inherent in the graph. Moreover, a relation-aware representation refinement strategy is proposed, which optimizes graph-level features by progressively fusing information from multiple relations to adaptively establish inherent connections, ensuring that the refined embeddings capture complex relational patterns and improve the overall quality of the graph-level embeddings. In summary, our contributions are as follows: • A Multi-relation Graph-kernel Strengthen Network (MGSN) is proposed, which integrates multi-relation modeling and graph kernel techniques to capture diverse semantic relationships and enrich the representation space with graph similarity features, which ensures the consistency and discriminability of the learned representations. • A relation-aware representation refinement strategy is designed, adaptively aligning multi-relation information across views and progressively fusing complementary features through a kernel-guided alignment mechanism, preserving structure nuances. • Extensive experiments on multiple benchmark datasets demonstrate that MGSN achieves superior performance compared to state-of-the-art methods, highlighting its capability to leverage multi-relation structures and dynamic graph kernel features effectively. II Related Work II-A Graph Kernels Method Graph kernels have been fundamental in graph-level analysis, providing a mathematically rigorous measure of graph similarity. Early methods, such as the Random Walk Kernel [ 10 ] and Shortest Path Kernel [ 11 ] , focused on comparing substructures like walks and paths but suffered from high computational complexity and sensitivity to graph size. To address these issues, Graphlet Kernels [ 13 ] and Subtree Kernels [ 23 ] shifted the focus to local patterns, improving efficiency while maintaining expressiveness. However, scalability and effectiveness in handling attributed graphs remained challenges. The Weisfeiler-Lehman (WL) Kernel [ 13 ] introduced an iterative tree aggregation process, significantly enhancing efficiency and adaptability to attributed graphs. Despite its success, WL Kernels rely on fixed-feature engineering and struggle to capture higher-order structures. To overcome these limitations, we propose integrating graph kernels with deep learning, leveraging graph kernels’ ability to capture structural similarities while enhancing representation learning. II-B Deep Graph-level Clustering With the rise of GCN, deep clustering methods based on representation learning have become crucial for graph structure analysis. Early approaches like InfoGraph [ 18 ] captured local and global semantics by maximizing mutual information but struggled with complex graph relationships. GraphCL [ 19 ] introduced multi-view contrastive learning to enhance relational modeling but faced optimization challenges in high-dimensional spaces. To address this, JOAO [ 24 ] automated data augmentation