Although Graph Neural Networks (GNNs) have shown promising potential in fake news detection, they remain highly vulnerable to adversarial manipulations within social networks. Existing methods primarily establish connections between malicious accounts and individual target news to investigate the vulnerability of graph-based detectors, while they neglect the structural relationships surrounding targets, limiting their effectiveness in robustness evaluation. In this work, we propose a novel Structural Information principles-guided Adversarial Attack Framework, namely SI2AF, which effectively challenges graph-based detectors and further probes their detection robustness. Specifically, structural entropy is introduced to quantify the dynamic uncertainty in social engagements and identify hierarchical communities that encompass all user accounts and news posts. An influence metric is presented to measure each account's probability of engaging in random interactions, facilitating the design of multiple agents that manage distinct malicious accounts. For each target news, three attack strategies are developed through multi-agent collaboration within the associated subgraph to optimize evasion against black-box detectors. By incorporating the adversarial manipulations generated by SI2AF, we enrich the original network structure and refine graph-based detectors to improve their robustness against adversarial attacks. Extensive evaluations demonstrate that SI2AF significantly outperforms state-of-the-art baselines in attack effectiveness with an average improvement of 16.71%, and enhances GNN-based detection robustness by 41.54% on average.

Multi-agent cooperation is essential for tasks that require collaboration to achieve optimal performance or cannot be completed by individual agents alone. These tasks often necessitate a divide-and-conquer strategy, where subgoals are allocated to individual agents or groups. By integrating coalition formation concepts from cooperative game theory, we demonstrate the implicit learning of coalition formation and task assignments, resulting in emergent cooperative behavior. We propose a novel COaLition LABeling technique for Multi-Agent Reinforcement Learning (COLLAB-MARL) to encourage coalition formation and introduce a structural entropy measure to detect the emergence of coalitions and cooperative behavior. Compared to classical MARL methods, COLLAB-MARL is more effective, explainable, and easier to implement. Experiments on state-of-the-art cooperative MARL benchmarks show that our method’s mean return outperforms the strongest baselines by 8.4% on average. Additionally, visualization and structural entropy analysis reveal that COLLAB-MARL effectively learns meaningful cooperative behavior. The source code is available at https://github.com/SELGroup/collab.

Graph kernels have been regarded as a successful tool for handling a variety of graph applications since they were proposed. However, most of the proposed graph kernels are based on the R-convolution framework, which decomposes graphs into a set of substructures at the same abstraction level and compares all substructure pairs equally; these methods inherently overlook the utility of the hierarchical structural information embedded in graphs. In this paper, we proposeHierarchicalAbstractingGraphKernels (HAGK), a novel set of graph kernels that compare graphs’ hierarchical substructures to capture and utilize the latent hierarchical structural information fully. Instead of generating non-structural substructures, we reveal each graph’s hierarchical substructures by constructing itshierarchical abstracting, specifically, the hierarchically organized nested node sets adhering to the principle of structural entropy minimization. To compare a pair of hierarchical abstractings, we propose two novel substructure matching approaches,Local Optimal Matching(LOM) andPriority Ordering Matching(POM), to find appropriate matching between the substructures by different strategies recursively. Extensive experiments demonstrate that the proposed kernels are highly competitive with the existing state-of-the-art graph kernels, and verify that the hierarchical abstracting plays a significant role in the improvement of the kernel performance.

Semi-supervised clustering leverages prior information in the form of constraints to achieve higher-quality clustering outcomes. However, most existing methods struggle with large-scale datasets owing to their high time and space complexity. Moreover, they encounter the challenge of seamlessly integrating various constraints, thereby limiting their applicability. In this paper, we presentScalableSemi-supervised clustering viaStructuralEntropy (SSSE), a novel method that tackles scalable datasets with different types of constraints from diverse sources to perform both semi-supervised partitioning and hierarchical clustering, which is fully explainable compared to deep learning-based methods. Specifically, we design objectives based on structural entropy, integrating constraints for semi-supervised partitioning and hierarchical clustering. To achieve scalability on data size, we develop efficient algorithms based on graph sampling to reduce the time and space complexity. To achieve generalization on constraint types, we formulate a uniform view for widely used pairwise and label constraints. Extensive experiments on real-world clustering datasets at different scales demonstrate the superiority of SSSE in clustering accuracy and scalability with different constraints. Additionally, Cell clustering experiments on single-cell RNA-seq datasets demonstrate the functionality of SSSE for biological data analysis.

Semi-supervised clustering techniques have emerged as valuable tools for leveraging prior information in the form of constraints to improve the quality of clustering outcomes. Despite the proliferation of such methods, the ability to seamlessly integrate various types of constraints remains limited. While structural entropy has proven to be a powerful clustering approach with wide-ranging applications, it has lacked a variant capable of accommodating these constraints. In this work, we present Semi-supervised clustering via Structural Entropy (SSE), a novel method that can incorporate different types of constraints from diverse sources to perform both partitioning and hierarchical clustering. Specifically, we formulate a uniform view for the commonly used pairwise and label constraints for both types of clustering. Then, we design objectives that incorporate these constraints into structural entropy and develop tailored algorithms for their optimization. We evaluate SSE on nine clustering datasets and compare it with eleven semi-supervised partitioning and hierarchical clustering methods. Experimental results demonstrate the superiority of SSE on clustering accuracy with different types of constraints. Additionally, the functionality of SSE for biological data analysis is demonstrated by cell clustering experiments conducted on four single-cell RNA-seq datasets.

Research on social bot detection plays a crucial role in maintaining the order and reliability of information dissemination while increasing trust in social interactions. The current mainstream social bot detection models rely on black-box neural network technology, for example, Graph Neural Network, Transformer, and so on, which lacks interpretability. In this work, we present UnDBot, a novel unsupervised, interpretable, yet effective, and practical framework for detecting social bots. This framework is built upon structural information theory. We begin by designing three social relationship metrics that capture various aspects of social bot behaviors: posting type distribution , posting influence , and follow-to-follower ratio . Three new relationships are utilized to construct a new, unified, and weighted social multi-relational graph, aiming to model the relevance of social user behaviors and discover long-distance correlations between users. Second, we introduce a novel method for optimizing heterogeneous structural entropy. This method involves the personalized aggregation of edge information from the social multi-relational graph to generate a two-dimensional encoding tree. The heterogeneous structural entropy facilitates decoding of the substantial structure of the social bots network and enables hierarchical clustering of social bots. Third, a new community labeling method is presented to distinguish social bot communities by computing the user’s stationary distribution, measuring user contributions to network structure, and counting the intensity of user aggregation within the community. Compared with 10 representative social bot detection approaches, comprehensive experiments demonstrate the advantages of effectiveness and interpretability of UnDBot on 4 real social network datasets.

Skin lesion segmentation is a fundamental task in dermoscopic image analysis. The complex features of pixels in the lesion region impede the lesion segmentation accuracy, and existing deep learning-based methods often lack interpretability to this problem. In this work, we propose a novel unsupervised Skin Lesion sEgmentation framework based on structural entropy and isolation forest outlier Detection, namely SLED. Specifically, skin lesions are segmented by minimizing the structural entropy of a superpixel graph constructed from the dermoscopic image. Then, we characterize the consistency of healthy skin features and devise a novel multi-scale segmentation mechanism by outlier detection, which enhances the segmentation accuracy by leveraging the superpixel features from multiple scales. We conduct experiments on four skin lesion benchmarks and compare SLED with nine representative unsupervised segmentation methods. Experimental results demonstrate the superiority of the proposed framework. Additionally, some case studies are analyzed to demonstrate the effectiveness of SLED.

Graph neural networks (GNNs) are now the mainstream method for mining graph-structured data and learning low-dimensional node- and graph-level embeddings to serve downstream tasks. However, limited by the bottleneck of interpretability that deep neural networks present, existing GNNs have ignored the issue of estimating the appropriate number of dimensions for the embeddings. Hence, we propose a novel framework called Minimum Graph Entropy principle-guided Dimension Estimation, i.e. MGEDE, that learns the appropriate embedding dimensions for both node and graph representations. In terms of node-level estimation, a minimum entropy function that counts both structure and attribute entropy, appraises the appropriate number of dimensions. In terms of graph-level estimation, each graph is assigned a customized embedding dimension from a candidate set based on the number of dimensions estimated for the node-level embeddings. Comprehensive experiments with node and graph classification tasks and nine benchmark datasets verify the effectiveness and generalizability of MGEDE.