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.

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.

In recent years, artificial intelligence (AI) has emerged as a significant topic, spurring numerous novel and innovative applications leveraging AI technology. As AI relies on large-scale datasets, the collection of such data is crucial for these applications. However, large-scale data acquisition in the physical world can be both expensive and time-consuming. To address this challenge, we introduce a new computational problem called the k-data retriever problem (k-DRP), which aims to minimize the traversal length of the longest walk by a set ofkdata retrievers within a road network. We establish the NP-hardness of k-DRP and propose a constant-ratio approximation algorithm named collective search walk planning (CSP) to tackle this problem. Additionally, we enhance CSP’s efficiency through GPU acceleration and a pruning strategy. Furthermore, we observe that CSP may result in retrievers traversing more duplicate or unnecessary routes. To address these instances, we propose the weight-balance collective search walk planning (WBCSP) algorithm. Through extensive experimental evaluations, we demonstrate that our proposed CSP and WBCSP algorithms surpass other baseline methods in both solution quality and efficiency.

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.

Virtual Reality (VR) has emerged due to advancements in hardware and computer graphics. During the pandemic, conferences and exhibitions leveraging VR have gained attention. However, large-scale VR conferences, face a significant problem not yet studied in the literature -- displaying too many irrelevant users on the screen which may negatively impact the user experience. To address this issue, we formulate a new research problem, Social-Aware VR Conference Group Display Configuration (SVGD). Accordingly, we design the Social Utility-Aware VR Conference Group Formation (SVC) algorithm, which is a 2-approximation algorithm to SVGD. SVC iteratively selects either the P-Configuration or S-Configuration based on their effective ratios. This ensures that in each iteration, SVC identifies and chooses the solution with the highest current effectiveness. Experiments on real metaverse datasets show that the proposed SVC outperforms 11 baselines by 75% in terms of solution quality.

Deep learning on graphs has shown to be powerful in modeling graph-structured data and learning representations for graphs, which involves aggregating information from graph neighborhoods to derive effective node representations. Although graph neural networks (GNNs) can be trained from scratch, pretraining GNNs to learn transferable knowledge for downstream tasks has been used recently to improve performance. However, using pre-training and fine-tuning to model each subtask can sometimes ignore the relationships, conflicts, and constraints between tasks, resulting in worse performance. In this paper, we propose a novel framework called Self-supervised Multi-Task Learning for Generative Graph Convolutional Network (SMT-GGCN) to enhance graph-based neural network models. SMT-GGCN combines self-supervised learning pretext tasks with supervised learning to train Graph Convolutional Networks (GCN) for graph structure understanding. We demonstrate that self-supervised multi-task learning can improve GCN’s generalization ability and enhance feature learning.

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.

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.

Egocentric network (ego network) data are very important for evaluating algorithms and machine learning approaches in Online Social Networks (OSNs). Nevertheless, obtaining the ego network data from OSNs is not a trivial task. Conventional manual approaches are time-consuming, and sometimes the ego network data are quite incomplete because only a small number of users would agree to provide their data. This is because there are two important factors that should be considered simultaneously for this data acquisition task: i) users’ willingness to provide their data, and ii) the structure of the ego network. However, addressing the above two factors to obtain the more complete ego network data has not received much research attention. Therefore, in this paper, we address this issue by proposing a family of new research problems. The first proposed problem, namedWillingness Maximization for Ego Network Extraction in Online Social Networks (WMEgo), identifies a set of ego networks from a single OSN, such that the willingness of the users to provide their data is maximized. We prove that WMEgo is NP-hard and propose a$\frac{1}{2}(1-\frac{1}{e})$-approximation algorithm, namedEgo Network Identification with Maximum Willingness (EIMW). Furthermore, we extend the idea of WMEgo to multiple social networks and formulate a new research problem, namedWillingness Maximization on Multiple Social Networks for Ego Network Extraction (WM$^{2}$2Ego), which is able to effectively obtain ego network data from multiple social networkssimultaneously. We propose a$\frac{1}{2}$-approximation algorithm, namedMaximum Expansion forUNifiedEXpenses (MUNEX)for a special case of WM$^{2}$Ego and then design a constant-ratio approximation algorithm to the general WM$^{2}$Ego problem, namedMaximum Expansion with Expense Examination (M3E). We conduct two evaluation studies with 672 and 1,052 volunteers to validate the proposed WMEgo and WM$^{2}$Ego problems, respectively, and show that they are able to obtain much more complete ego network data compared to other baselines. We also perform extensive experiments on multiple real datasets to demonstrate that the proposed approaches significantly outperform the other baselines.

According to the literature in psychology, the existence of small dense subgroups is closely related to many mental illnesses, such as depression, bullying, and psychotic disorders. Here, small dense subgroups refer to the small groups in the social network in which members are socially dense but have no or few links to other individuals outside the group. Therefore, in this article, we make the first attempt to address the issue of small dense subgroups with the concept of network intervention from Psychology. We first introduce the new notion of Δ-Subgroups (Δ-SGs) to quantify the small dense subgroups. Then, following the concept of network intervention, we formulate a new research problem, Small Subgroup Maximum Reduction Problem (SSMP), to reduce the number of small dense subgroups (i.e., Δ-SGs) in the social network. We prove that SSMP is NP-Hard and propose a linear-time algorithm, namely 3-SMMTG, to find the optimal solution for a special case of SSMP with = 3Δ=3. We then devise a 1/2(1-1/e)-approximation algorithm, namely ESGR, for the general SSMP and enhance its efficiency with effective pruning methods. We conduct a 8-week evaluation study with 812 participants to validate the proposed SSMP and ESGR. The results show that the participants with the network intervention recommended by ESGR have significant improvements on Internet addiction and depression, as compared to those individuals without any intervention. We also perform experiments on 7 real datasets, and the experimental results manifest that the proposed algorithms outperform the other baselines in both efficiency and solution quality.

The data of egocentric networks (ego networks) are very important for evaluating and validating the algorithms and machine learning approaches in Online Social Networks (OSNs). Nevertheless, obtaining the ego network data from OSNs is not a trivial task. Conventional manual approaches are time-consuming, and only a small number of users would agree to contribute their data. This is because there are two important factors that should be considered simultaneously for this data acquisition task: i) users' willingness to contribute their data, and ii) the structure of the ego network. However, addressing the above two factors to obtain the more complete ego network data has not received much research attention. Therefore, in this paper, we make our first attempt to address this issue by proposing a new research problem, named Willingness Maximization for Ego Network Extraction in Online Social Networks (WMEgo), to identify a set of ego networks from the OSN such that the willingness of the users to contribute their data is maximized. We prove that WMEgo is NP-hard and propose a 1/2*(1 1/e)-approximation algorithm, named Ego Network Identification with Maximum Willingness (EIMW). We conduct an evaluation study with 672 volunteers to validate the proposed WMEgo and EIMW, and perform extensive experiments on multiple real datasets to demonstrate the effectiveness and efficiency of our approach.

Many novel and exhilarating applications emerged in the past decade, thanks to the ubiquity and the volume of data in this big data era. However, large-scale data collection is often expensive and time-consuming, especially in the physical world. To address this issue, in this paper, we study a new research problem, named k-Collector Problem (k- CP), which considers to minimize the data collection time for a set of k data collectors in the road network. We propose a constant- ratio approximation algorithm, called Collective Search Walk Planning (CSP). Moreover, we also discuss different strategies to boost the efficiency of CSP. Experimental results on 3 real datasets show that our proposed CSP algorithm outperforms other baselines in both solution quality and efficiency.

Studies in Management and Sociology indicate that the diversity of job-related attributes of group members (group diversity) is crucial for boosting the group performance, because the diversity brings different knowledge and enables more innovative ideas and solutions. In addition, the social tightness of the group members is also important for effective communication, which is also an important factor for group performance. In this paper, we propose a new research problem, named Social-aware Diversity-optimized Group Extraction (SDGE), which considers the above two important factors jointly to extract a socially tight group with optimized group diversity from the social network. We formally formulate the SDGE problem and propose algorithm Group Shrinking for Diversity Maximization (GSDM), which is a 3-approximation algorithm for SDGE. We prove the performance guarantee of GSDM and conduct extensive experiments on real datasets to evaluate the performance of GSDM. The results indicate that GSDM outperforms the other baselines in both solution quality and efficiency.

Group therapy is one of the major clinical interventions to help patients with mental disorders. However, finding an effective therapy group is very challenging, since there are three crucial criteria that should be carefully considered simultaneously: 1) avoidance of isolation and loneliness; 2) unfamiliarity of patients; and 3) size of the therapy group. Manual selection of therapy group members, which is the common approach for most psychiatrists and mental health professionals today, may incur human bias and is very time-consuming. Therefore, we propose a new research problem, namely, Unfamiliarity-Aware Therapy Group Selection with Noah's Ark Principle (UTNA) for automatic selections of therapy group members from the social network while addressing the three crucial criteria mentioned above. In this paper, we first analyze the NP-hardness and inapproximability of the UTNA problem. Then, we consider a special case of UTNA on trees, namely, Tree-based UTNA, and propose a linear-time dynamic programming algorithm to find the optimal solution. We then design an efficient algorithm, Effective Therapy Group Discovery, to select suitable members efficiently and effectively for the general UTNA problem. We invite 10 psychiatrists and clinical psychologists to conduct an expert study for validating our problem formulation, where all experts agree that our problem formulation is helpful for them, and the groups selected by our proposed approach are better than or similar to their manual configurations. In addition, we also conduct extensive experiments on three real data sets. Experimental results show that our proposed algorithms outperform other baselines in both efficiency and solution quality.

MOTIVATION: Structural alignment of RNA is found to be a useful computational technique for idenitfying non-coding RNAs (ncRNAs). However, existing tools do not handle structures with pseudoknots. Although algorithms exist that can handle structural alignment for different types of pseudoknots, no software tools are available and users have to determine the type of pseudoknots to select the appropriate algoirthm to use which limits the usage of structural alignment in identifying novel ncRNAs. RESULTS: We implemented the first web server, RNASAlign, which can automatically identify the pseudoknot type of a secondary structure and perform structural alignment of a folded RNA with every region of a target DNA/RNA sequence. Regions with high similarity scores and low e-values, together with the detailed alignments will be reported to the user. Experiments on more than 350 ncRNA families show that RNASAlign is effective. AVAILABILITY: http://www.bio8.cs.hku.hk/RNASAlign.