Viral information like rumors or fake news is spread over a communication network like a virus infection in a unidirectional manner: entity$i$conveys information to a neighbor$j$, resulting in two equally informed (infected) parties. Existing graph diffusion processes focus only on bidirectional diffusion on an undirected graph. Instead, leveraging recent research in graph signal processing (GSP), we propose a new directed acyclic graph (DAG) diffusion process to estimate the probability$x_{i}(t)$of node$i$'s infection at time$t$given an initial infected source node$s$, where$x_{i}(\infty)=1$. Specifically, given an undirected positive graph modeling node-to-node communication, we first estimate its graph embedding: a latent coordinate for each graph node in an assumed low-dimensional manifold space via extreme eigenvectors computed using LOBPCG. Next, we construct a DAG based on Euclidean distances between latent coordinates. Spectrally, we prove that the asymmetric DAG Laplacian matrix contains real non-negative eigenvalues, and that the DAG diffusion converges to the all-infection vector$\mathbf{x}(\infty)=1$as$t\rightarrow\infty$. Simulations show that our DAG diffusion process accurately estimates the probabilities of node infection over a variety of graph structures at different time instants.

Graph sampling is the problem of choosing a node subset via sampling matrix H ∈ {0, 1}K×Nto collect samples y = Hx ∈ℝK, KNcan be reconstructed in high fidelity. While sampling on undirected graphs is well studied, we propose the first eigen-decomposition-free sampling scheme tailored specifically for directed graphs, leveraging a previous undirected graph sampling method based on Gershgorin disc alignment (GDAS). Concretely, given a directed positive graph ${{\mathcal{G}}^d}$ specified by random-walk graph Laplacian matrix Lrw, we first define reconstruction of a smooth signal x∗from samples y using graph shift variation (GSV) $\left\| {{{\mathbf{L}}_{rw}}{\mathbf{x}}} \right\|_2^2$ as a signal prior. To minimize the worst-case reconstruction error of the linear system solution x∗= C−1H⊤y with symmetric coefficient matrix${\mathbf{C}} = {{\mathbf{H}}^ \top }{\mathbf{H}} + \mu {\mathbf{L}}_{rw}^ \top {{\mathbf{L}}_{rw}}$, the E-optimality sampling objective is to choose H to maximize the smallest eigenvalue λmin(C) of C. To circumvent eigen-decomposition, we maximize instead a lower bound $\lambda _{\min }^ - \left( {{\mathbf{SC}}{{\mathbf{S}}^{ - 1}}} \right)$ of λmin(C)—smallest Gershgorin disc left-end of a similarity transform of C—via a variant of GDAS based on Gershgorin circle theorem (GCT). Experimental results show that our sampling method yielded smaller signal reconstruction errors at a faster speed compared to competing schemes.

Click-through rate (CTR) Prediction is of great importance in real-world online ads systems. One challenge for the CTR prediction task is to capture the real interest of users from their clicked items, which is inherently influenced by presented positions of items, i.e., more front positions tend to obtain higher CTR values. Therefore, It is crucial to make CTR models aware of the exposed position of the items. A popular line of existing works focuses on explicitly model exposed position by result randomization which is expensive and inefficient, or by inverse propensity weighting (IPW) which relies heavily on the quality of the propensity estimation. Another common solution is modeling position as features during offline training and simply adopting fixed value or dropout tricks when serving. However, training-inference inconsistency can lead to sub-optimal performance. This work proposes a simple yet efficient knowledge distillation framework to model the impact of exposed position and leverage position information to improve CTR prediction. We demonstrate the performance of our proposed method on a real-world production dataset and online A/B tests, achieving significant improvements over competing baseline models. The proposed method has been deployed in the real world online ads systems of JD, serving main traffic of hundreds of millions of active users.

Online social networks connect people together and facilitate them to share their experiences and thoughts, while they also enable users with extreme opinions to further publicize their opinions and influence others. Thus, it is critical to study users' opinion formation process and to design effective mechanisms to control the opinion dynamics in social networks. In this work, we consider the scenario where users with extreme opinions may change the network structure, e.g., by adding new links or tuning the edge weights, to further spread their opinions to the public, and theoretically analyze its impact on the network opinions at equilibrium. We also propose a robust opinion control scheme that can reduce the influence of such network structure perturbation on network opinions. Simulations verify the correctness of our analysis and the effectiveness of our proposed opinion control algorithm.

It is common for people to create different types of charts to explore a multi-dimensional dataset (table). However, to recommend commonly composed charts in real world, one should take the challenges of efficiency, imbalanced data and table context into consideration. In this paper, we propose Table2Charts framework which learns common patterns from a large corpus of (table, charts) pairs. Based on deep Q-learning with copying mechanism and heuristic searching, Table2Charts does table-to-sequence generation, where each sequence follows a chart template. On a large spreadsheet corpus with 165k tables and 266k charts, we show that Table2Charts could learn a shared representation of table fields so that recommendation tasks on different chart types could mutually enhance each other. Table2Charts outperforms other chart recommendation systems in both multi-type task (with doubled recall numbers [email protected]=0.61 and [email protected]=0.43) and human evaluations.

In social network, the existence of malicious users can create lots of detrimental consequences. To diminish their negative influences, it is necessary for rational users to identify and interact with each neighbor carefully to protect themselves from malicious ones. Therefore, it is crucial to establish a rule for users’ interaction in order to mitigate malicious users’ influences. In this paper, we propose a smart evolution model based on evolutionary game theory by introducing the reputation mechanism. The model takes into account both current reputation and instant incentives during users’ decision-making process. On the basis of whether users share reputation values with others, we introduce schemes without reciprocity principle and with the indirect reciprocity principle respectively. With the social norm and reputation updating policy, we theoretically analyze the evolutionary dynamics and corresponding ESSs by explicitly considering the effects of malicious users. Finally, simulations based on synthetic networks and real-world data are conducted to validate the effectiveness of the proposed smart evolution model.

In social networks, to better understand the avalanche of information flow over networks and to investigate its impact on economy and our social life, it is of crucial importance to model and analyze the information diffusion process. To address the existence of "super users" in social networks who have higher social status and potentially larger influence, we propose a graphical evolutionary game theoretic framework to investigate the impact of such super users and their strategy update rules on information propagation. We analyze the evolutionary dynamics and the stable states. Simulation results are consistent with our theoretical analysis, and demonstrate that strategy update rule is the critical factor that influences the stable states of the information diffusion process.

Modeling and analysis of information diffusion over networks is of crucial importance to better understand the avalanche of information flow over social networks and to investigate its impact on economy and our social life. Different from prior works that study rational behavior in information diffusion, we focus on "irrational users e.g., those who always intentionally forward fake news even when they know it contains false information. We extend the graphical evolutionary game model for information diffusion, and analyze the impact of such irrational behavior on information propagation. Our simulation results on synthetic networks are consistent with our analytical results, and they show that even a few irrational users can significantly increase the number of users who adopt the forwarding strategy.