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.

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.

In this article, we propose to study a novel research problem to boost group performance, that is, social-aware diversity-optimized group extraction (SDGE), which takes into consideration the two important factors: 1) group diversity and 2) social tightness. We prove the NP-hardness of SDGE and propose an effective algorithm, named group shrinking for diversity maximization (GSDM) with a performance guarantee, that is, GSDM is a three-approximation algorithm to the SDGE problem studied in this article. We further propose three effective pruning strategies that are able to boost the efficiency of GSDM but do not deteriorate its performance. We conduct extensive experiments on multiple large-scale real datasets to evaluate the performance of GSDM. The experimental results show that our proposed GSDM outperforms the other baseline approaches significantly, in terms of solution quality and efficiency. Moreover, the experimental results also confirm that our proposed pruning strategies indeed boost the efficiency of the algorithm.

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.

Several automobile manufacturers are offering assisted driving systems that use sensors to automatically brake automobiles to avoid collisions. Before extensively deploying these systems, we should determine how they will affect highway capacity. The goal of this paper is to compare the highway capacity when using sensors alone and when using sensors and vehicle-to-vehicle communication. To achieve this goal, the rules for using both technologies to prevent collisions are proposed, and highway capacity is estimated based on these rules. We show that both technologies can increase highway capacity. The increase in capacity is a function of the fraction of the vehicles that use a technology. If all of the vehicles use sensors alone, the increase in highway capacity is about 43%. While if all of the vehicles use both sensors and vehicle-to-vehicle communication, the increase is about 273%.