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.

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.

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.

Multivariate networks are commonly found in real-world data-driven applications. Uncovering and understanding the relations of interest in multivariate networks is not a trivial task. This paper presents a visual analytics workflow for studying multivariate networks to extract associations between different structural and semantic characteristics of the networks (e.g., what are the combinations of attributes largely relating to the density of a social network?). The workflow consists of a neural-network-based learning phase to classify the data based on the chosen input and output attributes, a dimensionality reduction and optimization phase to produce a simplified set of results for examination, and finally an interpreting phase conducted by the user through an interactive visualization interface. A key part of our design is a composite variable construction step that remodels nonlinear features obtained by neural networks into linear features that are intuitive to interpret. We demonstrate the capabilities of this workflow with multiple case studies on networks derived from social media usage and also evaluate the workflow with qualitative feedback from experts.

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.

Graph neural networks (GNNs) enable many novel applications and achieve excellent performance. However, their performance may be significantly degraded by the graph adversarial attacks, which intentionally add small perturbations to the graph. Previous countermeasures usually handle such attacks by enhancing model robustness. However, robust models cannot identify thetarget nodesof the adversarial attacks, and thus we are unable to pinpoint the weak spots and analyze the causes or the targets of the attacks. In this article, we study the important research problem to detect thetarget nodesof graph adversarial attacks under theblack-box detectionscenario, which is particularly challenging because our detection models do not have any knowledge about the attacker, while the attackers usually employ unnoticeability strategies to minimize the chance of being detected. To our best knowledge, this is the first work that aims at detecting thetarget nodesof graph adversarial attacks under theblack-box detectorscenario. We propose two detection models, namedDet-HandDet-RL, which employ different techniques that effectively detect the target nodes under the black-box detection scenario against various graph adversarial attacks. To enhance the generalization of the proposed detectors, we further propose two novel surrogate attackers that are able to generate effective attack examples and camouflage their attack traces for training robust detectors. In addition, we propose three strategies to effectively improve the training efficiency. Experimental results on multiple datasets show that our proposed detectors significantly outperform the other baselines against multiple state-of-the-art graph adversarial attackers with various attack strategies. The proposedDet-RLdetector achieves an averaged area under curve (AUC) of 0.945 against all the attackers, and our efficiency-improving strategies are able save up to 91% of the training time.

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.

Link prediction is a crucial research area for both data mining and machine learning. Despite the success of contrastive learning in node classification tasks, applying it directly to link prediction tasks has revealed two major weaknesses, i.e., single positive sample contrasting and random augmentation, resulting in inferior performance. To overcome these issues, we propose a new contrastive learning approach for link prediction, called Structure-aware Contrastive Representation Learning with Self-discriminating Augmentation (SECRET). Our approach includes a novel data augmentation scheme based on the prediction model itself and takes into account both the contrastive objective and the reconstruction loss, which jointly improve the performance of link prediction. Our experiments on 11 benchmark datasets demonstrate that SECRET significantly outperforms the other state-of-the-art baselines.

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.

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.

Finding a set of suitable experts with minimized communication overhead to perform a complex task finds a wide spectrum of applications in industry, education, and other scenarios. This class of problems, widely formulated as forming a team of experts in social networks (i.e., team formation problem), is very challenging due to its NP-hardness and has attracted much research attention. Although various effective and elegant algorithms have been proposed to address this important problem, the methods are usually manually designed and handcrafted, which require considerable human efforts. In this article, we make our first attempt to automate the algorithm design with a machine learning-based approach, named reinforcement learning-based expert team identification (RELEXT). Moreover, we also propose two novel graph embedding methods to consider two important dimensions of the team formation problem, i.e., the skill and social dimensions. We evaluate the proposed approaches on multiple large-scale real datasets. The experimental results show that our proposed approaches outperform the other baselines in terms of solution quality and efficiency.

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.

Social Anxiety disorder (SAD), one of the most important and common mental disorders, affects a large proportion of individuals around the world. To help identify SAD patients for early intervention, in this study, we bring together computer science and psychology for a new research problem, the automatic identification of SAD patients with online social network data. We extract multiple effective features with the data from 200 online social network users. The effectiveness indicates that our system is promising in identifying SAD patients with online social network data.

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.