Launching attacks against community detection to significantly deteriorate its performance has received increasing research attention recently due to the importance and wide applications of community detection. However, we observe that most previous attacks suffer from two major weaknesses: i) the negligence of community structures in their proxy metrics, and ii) limited attack scope. To tackle these issues, we propose a new research problem,Perturbing Community Detection with$\mu$-Triad Minimization ($\mu$-PerCD), based on a new metric proposed in this paper, named$\mu$-triad, to attack community detection more effectively. We first present analysis results to justify the effectiveness of$\mu$-triads by comparing it with many other candidate proxy metrics. Also, we illustrate the rationale behind the formulation of$\mu$-PerCD problem with experiments on real datasets. Then, we analyze the NP-hardness of$\mu$-PerCD and propose two$\frac{1}{4}(1-\frac{1}{e})$-approximation algorithms, named$\mu$-Triad Minimization with Edge Addition ($\mu$MEA)and$\mu$MEA+, where$\mu$MEA+is an efficiency-enhanced version of$\mu$MEAwhile retaining the approximation ratio. Extensive experiments on real datasets demonstrate the effectiveness of the proposed algorithm in attacking various community detection algorithms, significantly outperforming the other state-of-the-art baselines.

Link prediction is one of the most fundamental tasks in graph mining, which motivates the recent studies of leveraging contrastive learning to enhance the performance. However, we observe two major weaknesses of these studies: i) the lack of theoretical analysis for contrastive learning on link prediction, and ii) inadequate consideration of node degrees in contrastive learning. To address the above weaknesses, we provide the first formal theoretical analysis for contrastive learning on link prediction, where our analysis results can generalize to the autoencoder-based link prediction models with contrastive learning. Motivated by our analysis results, we propose a new graph augmentation approach, Edge Balancing Augmentation (EBA), which adjusts the node degrees in the graph as the augmentation. We then propose a new approach, named Contrastive Link Prediction with Edge Balancing Augmentation (CoEBA), that integrates the proposed EBA and the proposed new contrastive losses to improve the model performance. We conduct experiments on 8 benchmark datasets. The results demonstrate that our proposed CoEBA significantly outperforms the other state-of-the-art link prediction models.

A recent line of research on learning to solve graph optimization problems has attracted much research attention. However, most recent machine learning approaches to graph optimization problems usually employ graph generators to randomly generate training graphs, which may lead to overfitting and deteriorate the model's generalization. To tackle this issue, we observe that enhancing the diversity of training graphs is a crucial factor in improving the model's performance. Therefore, in this paper, we formulate a new research problem, named Graph Augmentation for Diversity Maximization (GRAM), to maximize the training graph diversity by performing graph modifications. We first analyze the NP-hardness of GRAM. We then propose a 2-approximation algorithm and formally analyze its performance guarantee. Experimental results on well-known graph optimization problems show that our proposed approach significantly outperforms the baselines, such as graph augmentation and deep learning-based graph generation approaches.

Graph Neural Networks (GNNs) perform well on graph-structured data, but their dependence on graph connectivity limits scalability and efficiency. Kolmogorov-Arnold Networks (KANs), a recent architecture with learnable univariate functions, offer strong nonlinear expressiveness and efficient inference. In this paper, we integrate KANs into three widely used GNN architectures, GAT, SGC, and APPNP, resulting in three new models, KGAT, KSGC, and KAPPNP. We use these KAN-based GNN architectures as teacher models and apply multi-teacher knowledge amalgamation to distill their knowledge into a graph-independent student model, KAN. We evaluate our models on several benchmark datasets, and the results show that the proposed KAN-based models improve performance. The student model, KAN, further benefits from the knowledge amalgamation framework built on these models. Our results demonstrate that KANs enhance the expressiveness of GNNs while enabling efficient, graph-free inference.

With the increasing importance of protecting intellectual property in machine learning, watermarking techniques have gained significant attention. As advanced models are increasingly deployed in domains such as social network analysis, the need for robust model protection becomes even more critical. While existing watermarking methods have demonstrated effectiveness for conventional deep neural networks, they often fail to adapt to the novel architecture, Kolmogorov-Arnold Networks (KAN), which feature learnable activation functions. KAN holds strong potential for modeling complex relationships in network-structured data. However, their unique design also introduces new challenges for watermarking. Therefore, we propose a novel watermarking method, Discrete Cosine Transform-based Activation Watermarking (DCT-AW), tailored for KAN. Leveraging the learnable activation functions of KAN, our method embeds watermarks by perturbing activation outputs using discrete cosine transform, ensuring compatibility with diverse tasks and achieving task independence. Experimental results demonstrate that DCT-AW has a small impact on model performance and provides superior robustness against various watermark removal attacks, including fine-tuning, pruning, and retraining after pruning.

The$k$-plex is a popular definition of communities in networks, offering more flexibility than cliques by allowing each node to miss up to$k$connections. However, finding$k$-plexes in large graphs is a theoretically challenging task due to the large number of possible$k$-plexes. In this article, we propose a novel approach for detecting$k$-plexes under various sizes and time constraints using an automated strategy to learn bounds, called theconstraint learning and bounding (CLB)method. Specifically, our proposedCLBapproach, leverages the concept of constraint learning to develop a mixed integer linear programming (MILP) instance as a model to learn a bounding strategy in the branch-and-bound process. The variables in the MILP instances correspond to the natural properties of the$k$-plex problem. Unlike previous works, we focus on learning the bounding strategy rather than learning the branching strategy. Thus, the strategy learned by our proposed approach avoids visiting infeasible solutions, which accelerates the branch-and-bound algorithm and reduces the computational load. To evaluate our approach, we conduct experiments on various real graphs to validate the superiority and the generality of our proposed approach. In summary, our approach offers an effective and efficient solution for detecting$k$-plexes under various conditions.

Neural network (NN) compression aims at reducing the model size and receives much research attention. Nevertheless, we observe that when compressing convolutional neural networks (CNNs), previous approaches may not well measure the impact of filters to loss, resulting in a significant performance degradation after compression. On the other hand, for compressing the fully connected neural networks (FCNNs), we observe that converting the weight matrix to the block diagonal structure would result in better compression. Therefore, for compressing CNNs, we propose a new pipeline in this article, named Retraining-Aware Pruning (RAP) , with a new self-distillation approach, named High-Level Activation-Guided Attention-Preserving Self-Distillation (HAP) and a novel filter pruning strategy, named Normalized Gradients and Geometric Median (NGGM) to effectively improve the accuracy and reduce the model size. Further, for reducing the model size of FCNNs, we formulate a new research problem, i.e., Compression with Difference-Minimized Block Diagonal Structure (COMIS) , and propose a new algorithm, Memory-Efficient and Structure-Aware Compression (MESA) to effectively prune the weights into a block diagonal structure to significantly boost the compression rate. Extensive experiments on different models show that our approaches significantly outperform the state-of-the-art baselines in terms of compression rate, accuracy, and inference speed-up.

Recently, many machine learning-based approaches that effectively solve graph optimization problems have been proposed. The graph optimization problem is the problem that aims to optimize (maximize or minimize) a quantity that is associated with a graph, such as the Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS) problems. These approaches are usually trained on graphs randomly generated with graph generators or sampled from existing datasets. However, we observe that such training graphs lead to poor testing performance if the testing graphs are not generated analogously, i.e., the generalizability of the models trained on thoserandomly generatedtraining graphs is very limited. To address this critical issue, in this paper, we propose a new framework, namedLearning with Iterative Graph Diversification (LIGD), and formulate a new research problem, namedDiverse Graph Modification Problem (DGMP), that iteratively generate diversified training graphs and train the models that solve graph optimization problems to improve their performance significantly. We propose three approaches to solve DGMP by considering both the performance of the machine learning approaches and the structural properties of the training graphs. In addition, we study a practical case of DGMP, namedDiverse Graph Modification Problem with XOR Diversity (DGMP-XDiv), which considers an XOR-based diversity function. We propose a polynomial-time algorithm namedStructure Diversifying Modification on Edge Score (DMES)to obtain the optimal solution. We also proposeDMES with Efficiency-Boosting Strategies (DMES-EB)to enhance the efficiency of DMES significantly. Experimental results on well-known problems show that our proposed approaches significantly boost the performance of both supervised and reinforcement learning approaches. They produce near-optimal results and significantly outperform the baseline approaches, such as graph augmentation and diffusion-based approaches.

In recent years, the notion of federated learning (FL) has led to the new paradigm of distributed artificial intelligence (AI) with privacy preservation. However, most current FL systems suffer from data privacy issues due to the requirement of a trusted third party. Although some previous works introduce differential privacy to protect the data, however, it may also significantly deteriorate the model performance. To address these issues, we propose a novel decentralized collaborative AI framework, named Auditable Homomorphic-based Decentralised Collaborative AI (AerisAI), to improve security with homomorphic encryption and fine-grained differential privacy. Our proposed AerisAI directly aggregates the encrypted parameters with a blockchain-based smart contract to get rid of the need of a trusted third party. We also propose a brand-new concept for eliminating the negative impacts of differential privacy for model performance. Moreover, the proposed AerisAI also provides the broadcast-aware group key management based on ciphertext-policy attribute-based encryption (CP-ABE) to achieve fine-grained access control based on different service-level agreements. We provide a formal theoretical analysis of the proposed AerisAI as well as the functionality comparison with the other baselines. We also conduct extensive experiments on real datasets to evaluate the proposed approach. The experimental results indicate that our proposed AerisAI significantly outperforms the other state-of-the-art baselines.

This article proposes a machine learning (ML)-based approach to solve a graph optimization problem, named network intervention with limited degradation (NILD), which aims at adding new edges to augment the graph to minimize the local clustering coefficient (LCC) of a target node. The main application of NILD is to performnetwork intervention, to improve the mental well-being of individuals. This article proposes a new framework, named network intervention with self-supervision (NISS), which employs reinforcement learning and self-supervised learning (SSL) to effectively solve the problem. We propose two new effective pretext tasks in SSL,Distance-to-targetprediction task andLCC incrementprediction task to improve the model performance. In addition, we also propose two new embedding approaches, neighborhood embedding (NE) and constraint property embedding (CPE), to capture the structural information of the graph. Extensive experiments on multiple real social networks and synthetic datasets show that our proposed approach significantly outperforms the other state-of-the-art baselines, including ML-based baselines and deterministic algorithms.

While most previous work pays attention onextractingdense subgraphs, such ask-cores, we argue that augmenting the graph to maximize the size of dense subgraphs is also very important and finds many applications. Therefore, in this article, we study the dense subgraph augmentation problem in multilayer graphs. Specifically, we propose the notion of (k,L)-core to model the dense subgraphs in multilayer graphs and propose a new research problem, budgeted maximal (k,L)-core augmentation (BMA) problem, which adds at mostbedges in the multilayer graphs to maximize the size of (k,L)-core. We prove the NP-hardness of the general BMA problem whenk≥ 2 and devise a polynomial-time algorithm to find the optimal solution for a special case of BMA, i.e., (2, 1)-BMA. We then devise an effective algorithm, named search for optimum and reorder adaptively (SORA), with various performance-improving strategies to tackle the general BMA problem. We evaluate the performance of the proposed approaches on multiple large-scale datasets and compare them with the state-of-the-art baselines. Experimental results indicate that our proposed approaches significantly outperform the baselines in terms of solution quality and efficiency.

Many large-scale machine learning approaches and graph algorithms are proposed recently to address a variety of problems in online social networks (OSNs). To evaluate and validate these algorithms and models, the data of ego-centric networks (ego networks) are widely adopted. Therefore, effectively extracting large-scale ego networks from OSNs becomes an important issue, particularly when privacy policies become increasingly strict nowadays. In this paper, we study the problem of extracting ego network data by considering jointly the user willingness, crawling cost, and structure of the network. We formulate a new research problem, namedStructure and Willingness Aware Ego Network Extraction (SWAN)and analyze its NP-hardness. We first propose a$(1-\frac{1}{e})$-approximation algorithm, namedTristar-Optimized Ego Network Identification with Maximum Willingness (TOMW). In addition to the deterministic approximation algorithm, we also propose to automaticallylearnan effective heuristic approach with machine learning, to avoid the huge efforts for human to devise a good algorithm. The learning approach is namedWillingness-maximized and Structure-aware Ego Network Extraction with Reinforcement Learning (WSRL), in which we propose a novel constrastive learning strategy, namedContrastive Learning with Performance-boosting Graph Augmentation. We recruited 1,810 real-world participants and conducted an evaluation study to validate our problem formulation and proposed approaches. Moreover, experimental results on real social network datasets show that the proposed approaches outperform the other baselines significantly.

In this paper, we explore and study the research problem of learning an effective algorithm to extract a goal-oriented subgraph, which finds applications in many graph mining scenarios, such as extracting dense/sparse subgraphs and forming effective therapy groups. Specifically, we study the research problem, Similarity-maximized Subgraph Extraction with Minimum Interaction, which aims at extracting a subgraph in which each node has the minimum numbers of neighbors and common neighbors while maximizing the similarity of the selected nodes. We first propose a reinforcement learning-based approach, named RLFG to effectively identify the resulting subgraphs. Then, we observe that directly applying RLFG on large graphs may incur the neighbor explosion problem, which forbids efficient and effective training of the learning model. To address this issue, we propose a sampling strategy with guaranteed performance, named Similarity-aware Subgraph Sampling (SA2S). Experimental results on multiple datasets show that combining our proposed RLFG and SA2S achieves significantly superior performance compared to other state-of-the-art baselines.