Gaining a deep understanding of descriptive positive and negative norms, such as their propagation speed, is crucial due to their significant impact on shaping individuals' attitudes and actions towards specific beliefs. Unfortunately, conducting in-depth analysis related to the diffusion of descriptive norms is a complex and context-dependent phenomenon that is influenced by various factors over time. To address this gap, this paper presents a comprehensive analysis of norm propagation in online communities. The study encompasses structural and temporal analyses. Through these analyses, our objective is to uncover the dynamics of norm diffusion, comprehend the patterns of different norms within communities. This will provide valuable insights into the social context and dynamics surrounding positive and negative norms, ultimately enhancing our understanding of norm diffusion and social influence processes. This understanding also offers valuable insights for developing effective campaigns that promote positive norms.

Vertical Federated Learning (VFL) stands out as a promising approach to safeguard privacy in collaborative machine learning, allowing multiple entities to jointly train models on vertically partitioned datasets without revealing private information. While recent years have seen substantial research on privacy vulnerabilities and defense strategies for VFL, the focus has primarily been on passive scenarios where attackers adhere to the protocol. This perspective undermines the practical threats since the attackers can deviate from the protocol to improve their inference capabilities. To address this gap, our study introduces two innovative data reconstruction attacks designed to compromise data privacy in an active setting. Essentially, both attacks modify the gradients computed during the training phase of VFL to breach privacy. Our first attack uses an Active Inversion Network exploiting a small portion of known data in the training set to coerce the passive participants into training an auto-encoder for the reconstruction of their private data. The second attack, Active Generative Network, utilizes the knowledge of the training data distribution to guide the system into training a conditional generative network (C-GAN) for feature inferences. Our experiments confirm the efficacy of both attacks in inferring private features from real-world datasets.

Recently, there has been significant interest in Temporal Graph Neural Networks (TGNN) because of their capability to learn from time-evolving graph-related data. However, similar to Graph Neural Network (GNN), explaining the predictions of TGNN is non-trivial due to its black-box and complex nature. A major approach for this problem in GNNs is by analyzing the model’s responses to some perturbations of the model’s inputs, called perturbation-based explanation methods. These methods are convenient and flexible as they do not require access to the model’s internals. However, a question arises: Does the lack of internal access limit these methods from uncovering crucial information about the predictions? Motivated by the question, this study explores the limitations of some popular classes of perturbation-based explanation methods. By constructing specific instances of TGNNs, we show (i) Node-perturbation is not reliable for identifying the paths that carry out the prediction, (ii) Edgeperturbation cannot reliably determine all the nodes contributing to the prediction and (iii) perturbing both nodes and edges does not consistently help identify the graph components responsible for the temporal aggregation in TGNNs. Our experimental results further demonstrate situations for failures of explanations can occur frequently in both synthetic and real-world scenarios. Thus, they emphasize the importance of perturbation choices and the internal information of the explained model in determining faithful explanations of the model’s predictions.

Graph neural networks (GNNs) are susceptible to privacy inference attacks (PIAS) given their ability to learn joint representation from features and edges among nodes in graph data. To prevent privacy leakages in GNNs, we propose a novel heterogeneous randomized response (HeteroRR) mechanism to protect nodes’ features and edges against PIAS under differential privacy (DP) guarantees, without an undue cost of data and model utility in training GNNs. Our idea is to balance the importance and sensitivity of nodes’ features and edges in redistributing the privacy budgets since some features and edges are more sensitive or important to the model utility than others. As a result, we derive significantly better randomization probabilities and tighter error bounds at both levels of nodes’ features and edges departing from existing approaches, thus enabling us to maintain high data utility for training GNNs. An extensive theoretical and empirical analysis using benchmark datasets shows that HeteroRR significantly outperforms various baselines in terms of model utility under rigorous privacy protection for both nodes’ features and edges. That enables us to defend PIAs in DP-preserving GNNs effectively.

Ranking nodes based on their centrality stands a fundamental, yet, challenging problem in large-scale networks. Approximate methods can quickly estimate nodes' centrality and identify the most central nodes, but the ranking for the majority of remaining nodes may be meaningless. For example, ranking for less-known websites in search queries is known to be noisy and unstable. To this end, we investigate a new node ranking problem with two important distinctions: a) ranking quality, rather than the centrality estimation quality, as the primary objective; and b) ranking only nodes of interest, e.g., websites that matched search criteria. We propose Sample space Partitloning Hypothesis Ranking, or SaPHyRa, that transforms node rankinginto a hy-pothesis ranking in machine learning. This transformation maps nodes' centrality to the expected risks of hypotheses, opening doors for theoretical machine learning (ML) tools. The key of SaPHyRa is to partition the sample space into exact and approx-imate subspaces. The exact subspace contains samples related to the nodes of interest, increasing both estimation and ranking qualities. The approximate space can be efficiently sampled with ML-based techniques to provide theoretical guarantees on the estimation error. Lastly, we present SaPHyRabo an illustration of SaPHyRa on ranking nodes' betweenness centrality (BC). By combining a novel bi-component sampling, a 2-hop sample partitioning, and improved bounds on the Vapnik-Chervonenkis dimension, SaPHyRas., can effectively rank any node subset in BC. Its performance is up to 200x faster than state-of-the-art methods in approximating BC, while its rank correlation to the ground truth is improved by multifold.

Despite recent studies on understanding deep neural networks (DNNs), there exists numerous questions on how DNNs generate their predictions. Especially, given similar predictions on different inputs, are the underlying mechanisms generating those predictions the same? In this work, we propose NeuCEPT, a method to identify critical neurons that are important to the model’s local predictions and learn their underlying mechanisms. We first formulate a critical neurons identification problem as maximizing a sequence of mutual-information objectives and provide a theoretical framework to efficiently solve for critical neurons while keeping the precision under control. NeuCEPT next heuristically learns different model’s mechanisms in an unsupervised manner. Our experiments and case studies show that neurons identified by NeuCEPT not only have strong influence on the model’s predictions but also hold meaningful information about model’s mechanisms.

Knowledge Distillation (KD) has been considered as a key solution in model compression and acceleration in recent years. In KD, a small student model is generally trained from a large teacher model by minimizing the divergence between the probabilistic outputs of the two. However, as demonstrated in our experiments, existing KD methods might not transfer critical explainable knowledge of the teacher to the student, i.e. the explanations of predictions made by the two models are not consistent. In this paper, we propose a novel explainable knowledge distillation model, called XDistillation, through which both the performance the explanations’ information are transferred from the teacher model to the student model. The XDistillation model leverages the idea of convolutional autoencoders to approximate the teacher explanations. Our experiments shows that models trained by XDistillation outperform those trained by conventional KD methods not only in term of predictive accuracy but also faithfulness to the teacher models.

In many image-classification applications, understanding the reasons of model’s prediction can be as critical as the prediction’s accuracy itself. Various feature-based local explainers have been designed to provide explanations on the decision of complex classifiers. Nevertheless, there is no consensus on evaluating the quality of different explanations. In response to this lack of comprehensive evaluation, we introduce the c-Eval metric and its corresponding framework to quantify the feature-based local explanation’s quality. Given a classifier’s prediction and the corresponding explanation on that prediction, c-Eval is the minimum-distortion perturbation that successfully alters the prediction while keeping the explanation’s features unchanged. To show that c-Eval captures the importance of input’s features, we establish a connection between c-Eval and the features returned by explainers in affine and nearly-affine classifiers. We then introduce the c-Eval plot, which not only displays a strong connection between c-Eval and explainers’ quality, but also helps automatically determine explainer’s parameters.

Fake news and rumors constitute a major problem in social networks recently. Due to the fast information propagation in social networks, it is inefficient to use human labor to detect suspicious news. Automatic rumor detection is thus necessary to prevent devastating effects of rumors on the individuals and society. Previous work has shown that in addition to the content of the news/posts and their contexts (i.e., replies), the relations or connections among those components are important to boost the rumor detection performance. In order to induce such relations between posts and contexts, the prior work has mainly relied on the inherent structures of the social networks (e.g., direct replies), ignoring the potential semantic connections between those objects. In this work, we demonstrate that such semantic relations are also helpful as they can reveal the implicit structures to better capture the patterns in the contexts for rumor detection. We propose to employ the self-attention mechanism in neural text modeling to achieve the semantic structure induction for this problem. In addition, we introduce a novel method to preserve the important information of the main news/posts in the final representations of the entire threads to further improve the performance for rumor detection. Our method matches the main post representations and the thread representations by ensuring that they predict the same latent labels in a multitask learning framework. The extensive experiments demonstrate the effectiveness of the proposed model for rumor detection, yielding the state-of-the-art performance on recent datasets for this problem.

Bayesian optimization (BO) is concerned with efficient optimization using probabilistic methods. Predictive entropy search (PES) is a popular and successful BO strategy to find a point that maximizes the information gained about the optima location of an unknown function. Since the PES analytical form is intractable, it requires approximations and is computationally expensive. These approximations may degrade PES performance in terms of accuracy and efficiency. In this paper, we propose an alternative scheme - predictive variance reduction search (PVRS) - to find a point that maximally reduces the uncertainty at the perceived optima locations. The optimization converges to the true optimum when the uncertainty at all perceived optima locations is vanished. Our novel modification is beneficial in two ways. First, PVRS can be computed in closed-form, unlike the approximations made in PES. Second, PVRS is simple and easy to implement. As a result, the proposed PVRS gains huge speed up for scalable BO whilst showing favorable optimization efficiency. Furthermore, we extend our PVRS framework for batch setting where we select multiple experiments for parallel evaluations at each iteration. Empirically, we demonstrate the effectiveness of the PVRS on both benchmark functions and real-world applications in standard and batch BO settings.

While online social networks (OSNs) have become an important platform for information exchange, the abuse of OSNs to spread misinformation has become a significant threat to our society. To restrain the propagation of misinformation in its early stages, we study the Distance-constrained Misinformation Combat under Uncertainty problem, which aims to both reduce the spread of misinformation and enhance the spread of correct information within a given propagation distance. The problem formulation considers the competitive diffusion of misinformation and correct information. It also accounts for the uncertainty in identifying initial misinformation adopters. For competitive propagation with major-threshold activation, we propose a solution based on stochastic programming and provide an upper-bound in the presence of uncertainty. We propose an efficient Combat Seed Selection algorithm to tackle general-threshold activation, in which we define a measure, “effectiveness”, to evaluate the contribution of nodes to the fight against misinformation. Through extensive experiments, we validate that our algorithm outputs high-quality solution with very fast computation.

Motivated by the relevance of clustering or transitivity to a variety of network applications, we study the Triangle Interdiction Problem (TIP), which is to find a minimum-size set of edges that intersects all triangles of a network. As existing approximation algorithms for this NP-hard problem either do not scale well to massive networks or have poor solution quality, we formulate two algorithms, TARL and DART, with worst-case guarantees 5/2 and 3 with respect to optimal, respectively. Furthermore, DART is able to efficiently maintain its worst-case guarantee under dynamic edge insertion and removal to the network. In our comprehensive experimental evaluation, we demonstrate that DART is able to run on networks with billions of triangles within 2 hours and is able to dynamically update its solution in microseconds.

Online Social Networks (OSNs) are effective platforms for viral marketing. Due to their importance, viral marketing related problems in OSNs have been extensively studied in the past decade. However, none of the existing works can cope with the situation that the propagation rate dynamically increases for popular topics, as they all assume known propagation rates. In this paper, to better describe realistic information propagation in OSNs, we propose a novel model, Dynamic Influence Propagation (DIP), that allows propagation rate to change during the diffusion. We then define a new research problem: Threshold Activation Problem under DIP (TAP-DIP) to study the impact of DIP. TAP-DIP adds extra complexity on the already #P-hard TAP problem. Despite it hardness, we are able to approximate TAP-DIP with O(log|V|) ratio. Sitting in the core of our algorithm are the Lipschitz optimization technique and a novel solution to the general version of TAP, the Multi-TAP problem. Using various real OSN datasets, we experimentally demonstrate the impact of DIP and that our solution not only generates high-quality seed sets when being aware of the rate increase, but also is scalable.

While online social networks provide access to a massive information source, they also enable wide dissemination of false or inaccurate content. Undesirable results caused by misinformation propagation make its timely detection very imperative. An important question is how many monitors are required to detect all misinformation cascades at their early stage. To answer this question, we define a Time Constrained Misinformation Detection (TCMD) problem. As we have proved, there is no polynomial time (1 - ε) ln n-approximation for the TCMD problem. The large number of independent misinformation cascades and heterogeneous delays make misinformation detection more challenging. Our approach includes stochastic programming and an O(ln(1 + n)) approximation algorithm for one-hop detection. This approach can provide a lower bound on the number of required monitors for general detection. Furthermore, we propose a network-compression based solution, whose effectiveness is validated by extensive experimental results.

Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same (1-1/e-ε) approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM.

A reconnaissance attack, in which attackers lure targets into becoming their friends in order to extract victims' sensitive information for sale or use in future attacks, is one of the most dangerous attacks in social networks. The core of this attack lies in intelligently sending friend requests to a small subset of users, called Critical Friending Set (CFS), so that the attacker can evade current defense mechanisms. Motivated by the above, we present a new paradigm to measure OSN vulnerability in light of reconnaissance attacks. Specifically, we introduce a new optimization problem, namely Min-Friending, which identifies a minimum CFS to friend in order to obtain at least Q benefit, in terms of personal information. A significant challenge of this problem is that network information (i.e. who friends with whom) is generally unknown to attackers. In this paper, we show that Min-Friending is inapproximable within a factor of (1 - o(1)) ln Q and present an adaptive algorithm which has a tight performance bound of (1+ln Q) using adaptive stochastic optimization. The key feature of our solution lies in the adaptive method, where partial network topology is revealed during each successful friend request. Thus the decision of sending each friend request is made taking into account observation about the outcomes of past decisions.

Online social networks have become an effective and important social platform for communication, opinions exchange, and information sharing. However, they also make it possible for rapid and wide misinformation diffusion, which may lead to pernicious influences on individuals or society. Hence, it is extremely important and necessary to detect the misinformation propagation by placing monitors. In this article, we first define a general misinformation-detection problem for the case where the knowledge about misinformation sources is lacking, and show its equivalence to the influence-maximization problem in the reverse graph. Furthermore, considering node vulnerability, we aim to detect the misinformation reaching to a specific user. Therefore, we study a τ-Monitor Placement problem for cases where partial knowledge of misinformation sources is available and prove its # P complexity. We formulate a corresponding integer program, tackle exponential constraints, and propose a Minimum Monitor Set Construction (MMSC) algorithm, in which the cut-set 2 has been exploited in the estimation of reachability of node pairs. Moreover, we generalize the problem from a single target to multiple central nodes and propose another algorithm based on a Monte Carlo sampling technique. Extensive experiments on real-world networks show the effectiveness of proposed algorithms with respect to minimizing the number of monitors.

Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a little understood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we provide a rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.

Many complex systems, from World Wide Web and online social networks to mobile networks, exhibit community structure in which nodes can be grouped into densely interconnected communities. This special structure has been exploited extensively to design better solutions for many operations and applications such as routing in wireless networks, worm containment and interest prediction in social networks. The outcome of these solutions are sensitive to the network structures, which raises an important question: can communities be broken easily in a network? To answer this question, we introduce a density-based problem formulation for analyzing the vulnerability of communities. Our approach includes the NP-completeness and a O(log k) approximation algorithm for solving the problem where k is the number of communities to be broken. Additionally, we analyze the vulnerability of communities in the context of arbitrary community detection algorithms. The empirical results show that communities are vulnerable to edge removal and in some cases the removal of a small fraction of edges can break the community structure.

We introduce Community structure Vulnerability Assessment (CVA) problem to assess the network vulnerability under a community structure point of view. Given a positive number k, CVA aims to find out the k most vulnerable nodes whose removals maximally transform the current network community structure to a different one. As the first attempt, we suggest an approximation algorithm for the special case k = 1, and propose multiple greedy algorithms for CVA problem. To certify the effectiveness of suggested approaches, we test them on not only synthesized networks with known community structures but also on real-world social traces.

The least cost influence (LCI) problem, which asks to identify a minimum number of seed users who can eventually influence a large number of users, has become one of the central research topics recently in online social networks (OSNs). However, existing works mostly focused on a single network while users nowadays often join several OSNs. Thus, it is crucial to investigate the influence in multiplex networks, i.e. the influence is diffused across a set of networks via shared users, in order to obtain the best set of seed users.In this paper, we propose a unified framework to represent and analyze the influence diffusion in multiplex networks. More specifically, we tackle the LCI problem in multiplex OSNs by reducing multiplex networks to a single network via various coupling schemes while preserving the most influence propagation properties. Besides the coupling schemes to represent the diffusion process, the framework also includes the influence relay, a new metric to measure the flow of influence inside and between networks. The experiments on both real and synthesized datasets validate the effectiveness of the coupling schemes as well as provide some interesting insights into the process of influence propagation in multiplex networks.

With a rapid expansion of online social networks (OSNs), millions of users are tweeting and sharing their personal status daily without being aware of where that information eventually travels to. Likewise, with a huge magnitude of data available on OSNs, it poses a substantial challenge to track how a piece of information leaks to specific targets. In this paper, we study the problem of smartly sharing information to control the propagation of sensitive information in OSNs.

Online social networks have become an imperative channel for extremely fast information propagation and influence. Thus, the problem of finding a minimum number of seed users who can eventually influence as many users in the network as possible has become one of the central research topics recently. Unfortunately, most of related works have only focused on the network topologies and largely ignored many other important factors such as the users' engagements and the negative or positive impacts between users. More challengingly, the behavior of information propagation across multiple networks simultaneously remains an untrodden area and becomes an urgent need. Our work is the first attempt to tackle the above problem in multiple networks, considering these lacking important factors. In order to capture the users' engagement, we propose to targeting the set of interest-matching users whose interests are similar to what we try to propagate. Then, we develop our Iterative Semi-Supervising Learning based approach to identify the minimum seed users. We validate the effectiveness of our solution by using real-world Twitter-Foursquare networks and academic collaboration multiple networks.