Hong Shen

Hong Shen, Ángel Alexander Cabrera, Adam Perer et al. · cmu

This position paper offers a framework to think about how to better involve human influence in algorithmic decision-making of contentious public policy issues. Drawing from insights in communication literature, we introduce a "public(s)-in-the-loop" approach and enumerates three features that are central to this approach: publics as plural political entities, collective decision-making through deliberation, and the construction of publics. It explores how these features might advance our understanding of stakeholder participation in AI design in contentious public policy domains such as recidivism prediction. Finally, it sketches out part of a research agenda for the HCI community to support this work.

Xianzhe Fan, Qing Xiao, Xuhui Zhou et al. · allen-ai, cmu

AI companions based on large language models can role-play and converse very naturally. When value conflicts arise between the AI companion and the user, it may offend or upset the user. Yet, little research has examined such conflicts. We first conducted a formative study that analyzed 151 user complaints about conflicts with AI companions, providing design implications for our study. Based on these, we created Minion, a technology probe to help users resolve human-AI value conflicts. Minion applies a user-empowerment intervention method that provides suggestions by combining expert-driven and user-driven conflict resolution strategies. We conducted a technology probe study, creating 40 value conflict scenarios on Character.AI and Talkie. 22 participants completed 274 tasks and successfully resolved conflicts 94.16% of the time. We summarize user responses, preferences, and needs in resolving value conflicts, and propose design implications to reduce conflicts and empower users to resolve them more effectively.

Fangzhou Dong, Yifan Zeng, Yingpeng Sang et al.

Large Language Models (LLMs) excel in understanding and generating text but struggle with providing professional literary criticism for works with profound thoughts and complex narratives. This paper proposes GLASS (Greimas Literary Analysis via Semiotic Square), a structured analytical framework based on Greimas Semiotic Square (GSS), to enhance LLMs' ability to conduct in-depth literary analysis. GLASS facilitates the rapid dissection of narrative structures and deep meanings in narrative works. We propose the first dataset for GSS-based literary criticism, featuring detailed analyses of 48 works. Then we propose quantitative metrics for GSS-based literary criticism using the LLM-as-a-judge paradigm. Our framework's results, compared with expert criticism across multiple works and LLMs, show high performance. Finally, we applied GLASS to 39 classic works, producing original and high-quality analyses that address existing research gaps. This research provides an AI-based tool for literary research and education, offering insights into the cognitive mechanisms underlying literary engagement.

Xin Wang, Hong Shen

Coflow is a recently proposed networking abstraction to help improve the communication performance of data-parallel computing jobs. In multi-stage jobs, each job consists of multiple coflows and is represented by a Directed Acyclic Graph (DAG). Efficiently scheduling coflows is critical to improve the data-parallel computing performance in data centers. Compared with hand-tuned scheduling heuristics, existing work DeepWeave [1] utilizes Reinforcement Learning (RL) framework to generate highly-efficient coflow scheduling policies automatically. It employs a graph neural network (GNN) to encode the job information in a set of embedding vectors, and feeds a flat embedding vector containing the whole job information to the policy network. However, this method has poor scalability as it is unable to cope with jobs represented by DAGs of arbitrary sizes and shapes, which requires a large policy network for processing a high-dimensional embedding vector that is difficult to train. In this paper, we first utilize a directed acyclic graph neural network (DAGNN) to process the input and propose a novel Pipelined-DAGNN, which can effectively speed up the feature extraction process of the DAGNN. Next, we feed the embedding sequence composed of schedulable coflows instead of a flat embedding of all coflows to the policy network, and output a priority sequence, which makes the size of the policy network depend on only the dimension of features instead of the product of dimension and number of nodes in the job's DAG.Furthermore, to improve the accuracy of the priority scheduling policy, we incorporate the Self-Attention Mechanism into a deep RL model to capture the interaction between different parts of the embedding sequence to make the output priority scores relevant. Based on this model, we then develop a coflow scheduling algorithm for online multi-stage jobs.

Luodi Xie, Hong Shen, Jiaxin Ren

Network embedding maps the nodes of a given network into a low-dimensional space such that the semantic similarities among the nodes can be effectively inferred. Most existing approaches use inner-product of node embedding to measure the similarity between nodes leading to the fact that they lack the capacity to capture complex relationships among nodes. Besides, they take the path in the network just as structural auxiliary information when inferring node embeddings, while paths in the network are formed with rich user informations which are semantically relevant and cannot be ignored. In this paper, We propose a novel method called Network Embedding on the Metric of Relation, abbreviated as NEMR, which can learn the embeddings of nodes in a relational metric space efficiently. First, our NEMR models the relationships among nodes in a metric space with deep learning methods including variational inference that maps the relationship of nodes to a gaussian distribution so as to capture the uncertainties. Secondly, our NEMR considers not only the equivalence of multiple-paths but also the natural order of a single-path when inferring embeddings of nodes, which makes NEMR can capture the multiple relationships among nodes since multiple paths contain rich user information, e.g., age, hobby and profession. Experimental results on several public datasets show that the NEMR outperforms the state-of-the-art methods on relevant inference tasks including link prediction and node classification.

Zhigang Lu, Hong Shen

Iterative clustering algorithms help us to learn the insights behind the data. Unfortunately, this may allow adversaries to infer the privacy of individuals with some background knowledge. In the worst case, the adversaries know the centroids of an arbitrary iteration and the information of n-1 out of n items. To protect individual privacy against such an inference attack, preserving differential privacy (DP) for the iterative clustering algorithms has been extensively studied in the interactive settings. However, existing interactive differentially private clustering algorithms suffer from a non-convergence problem, i.e., these algorithms may not terminate without a predefined number of iterations. This problem severely impacts the clustering quality and the efficiency of a differentially private algorithm. To resolve this problem, in this paper, we propose a novel differentially private clustering framework in the interactive settings which controls the orientation of the movement of the centroids over the iterations to ensure the convergence by injecting DP noise in a selected area. We prove that, in the expected case, algorithm under our framework converges in at most twice the iterations of Lloyd's algorithm. We perform experimental evaluations on real-world datasets to show that our algorithm outperforms the state-of-the-art of the interactive differentially private clustering algorithms with guaranteed convergence and better clustering quality to meet the same DP requirement.

Zhigang Lu, Hong Shen

Paths in a given network are a generalised form of time-serial chains in many real-world applications, such as trajectories and Internet flows. Differentially private trajectory publishing concerns publishing path information that is usable to the genuine users yet secure against adversaries to reconstruct the path with maximum background knowledge. The exiting studies all assume this knowledge to be all but one vertex on the path. To prevent the adversaries recovering the missing information, they publish a perturbed path where each vertex is sampled from a pre-defined set with differential privacy (DP) to replace the corresponding vertex in the original path. In this paper, we relax this assumption to be all but one edge on the path, and hence consider the scenario of more powerful adversaries with the maximum background knowledge of the entire network topology and the path (including all the vertices) except one (arbitrary) missing edge. Under such an assumption, the perturbed path produced by the existing work is vulnerable, because the adversary can reconstruct the missing edge from the existence of an edge in the perturbed path. To address this vulnerability and effectively protect edge privacy, instead of publishing a perturbed path, we propose a novel scheme of graph-based path publishing to protect the original path by embedding the path in a graph that contains fake edges and replicated vertices applying the differential privacy technique, such that only the legitimate users who have the full knowledge of the network topology are able to recover the exact vertices and edges of the original path with high probability. We theoretically analyse the performance of our algorithm in differential privacy, utility, and execution efficiency. We also conduct extensive experimental evaluations on a high-performance cluster system to validate our analytical results.

Teng Xiao, Shangsong Liang, Hong Shen et al.

Collaborative Filtering (CF) is one of the most used methods for Recommender System. Because of the Bayesian nature and nonlinearity, deep generative models, e.g. Variational Autoencoder (VAE), have been applied into CF task, and have achieved great performance. However, most VAE-based methods suffer from matrix sparsity and consider the prior of users' latent factors to be the same, which leads to poor latent representations of users and items. Additionally, most existing methods model latent factors of users only and but not items, which makes them not be able to recommend items to a new user. To tackle these problems, we propose a Neural Variational Hybrid Collaborative Filtering, NVHCF. Specifically, we consider both the generative processes of users and items, and the prior of latent factors of users and items to be side informationspecific, which enables our model to alleviate matrix sparsity and learn better latent representations of users and items. For inference purpose, we derived a Stochastic Gradient Variational Bayes (SGVB) algorithm to analytically approximate the intractable distributions of latent factors of users and items. Experiments conducted on two large datasets have showed our methods significantly outperform the state-of-the-art CF methods, including the VAE-based methods.

Zaiqiao Meng, Hong Shen

Given a large network and a query node, finding its top-k similar nodes is a primitive operation in many graph-based applications. Recently enhancing search results with diversification have received much attention. In this paper, we explore an novel problem of searching for top-k diversified similar nodes in attributed networks, with the motivation that modeling diversification in an attributed network should consider both the emergence of network links and the attribute features of nodes such as user profile information. We formulate this practical problem as two optimization problems: the Attributed Coverage Diversification (ACD) problem and the r-Dissimilar Attributed Coverage Diversification (r-DACD) problem. Based on the submodularity and the monotonicity of ACD, we propose an efficient greedy algorithm achieving a tight approximation guarantee of 1-1/e. Unlike the expension based methods only considering nodes' neighborhood, ACD generalize the definition of diversification to nodes' own features. To capture diversification in topological structure of networks, the r-DACD problem introduce a dissimilarity constraint. We refer to this problem as the Dissimilarity Constrained Non-monotone Submodular Maximization (DCNSM) problem. We prove that there is no constant-factor approximation for DCNSM, and also present an efficient greedy algorithms achieving $1/ρ$ approximation, where $ρ\leΔ$, $Δ$ is the maximum degree of its dissimilarity based graph. To the best of our knowledge, it is the first approximation algorithm for the Submodular Maximization problem with a distance constraint. The experimental results on real-world attributed network datasets demonstrate the effectiveness of our methods, and confirm that adding dissimilarity constraint can significantly enhance the performance of diversification.

Zhigang Lu, Hong Shen

Neighbourhood-based Collaborative Filtering (CF) has been applied in the industry for several decades, because of the easy implementation and high recommendation accuracy. As the core of neighbourhood-based CF, the task of dynamically maintaining users' similarity list is challenged by cold-start problem and scalability problem. Recently, several methods are presented on solving the two problems. However, these methods applied an $O(n^2)$ algorithm to compute the similarity list in a special case, where the new users, with enough recommendation data, have the same rating list. To address the problem of large computational cost caused by the special case, we design a faster ($O(\frac{1}{125}n^2)$) algorithm, TwinSearch Algorithm, to avoid computing and sorting the similarity list for the new users repeatedly to save the computational resources. Both theoretical and experimental results show that the TwinSearch Algorithm achieves better running time than the traditional method.

Zhigang Lu, Hong Shen

The neighbourhood-based Collaborative Filtering is a widely used method in recommender systems. However, the risks of revealing customers' privacy during the process of filtering have attracted noticeable public concern recently. Specifically, $k$NN attack discloses the target user's sensitive information by creating $k$ fake nearest neighbours by non-sensitive information. Among the current solutions against $k$NN attack, the probabilistic methods showed a powerful privacy preserving effect. However, the existing probabilistic methods neither guarantee enough prediction accuracy due to the global randomness, nor provide assured security enforcement against $k$NN attack. To overcome the problems of current probabilistic methods, we propose a novel approach, Partitioned Probabilistic Neighbour Selection, to ensure a required security guarantee while achieving the optimal prediction accuracy against $k$NN attack. In this paper, we define the sum of $k$ neighbours' similarity as the accuracy metric $α$, the number of user partitions, across which we select the $k$ neighbours, as the security metric $β$. Differing from the present methods that globally selected neighbours, our method selects neighbours from each group with exponential differential privacy to decrease the magnitude of noise. Theoretical and experimental analysis show that to achieve the same security guarantee against $k$NN attack, our approach ensures the optimal prediction accuracy.

Zhigang Lu, Hong Shen

Recommender systems, tool for predicting users' potential preferences by computing history data and users' interests, show an increasing importance in various Internet applications such as online shopping. As a well-known recommendation method, neighbourhood-based collaborative filtering has attracted considerable attention recently. The risk of revealing users' private information during the process of filtering has attracted noticeable research interests. Among the current solutions, the probabilistic techniques have shown a powerful privacy preserving effect. When facing $k$ Nearest Neighbour attack, all the existing methods provide no data utility guarantee, for the introduction of global randomness. In this paper, to overcome the problem of recommendation accuracy loss, we propose a novel approach, Partitioned Probabilistic Neighbour Selection, to ensure a required prediction accuracy while maintaining high security against $k$NN attack. We define the sum of $k$ neighbours' similarity as the accuracy metric alpha, the number of user partitions, across which we select the $k$ neighbours, as the security metric beta. We generalise the $k$ Nearest Neighbour attack to beta k Nearest Neighbours attack. Differing from the existing approach that selects neighbours across the entire candidate list randomly, our method selects neighbours from each exclusive partition of size $k$ with a decreasing probability. Theoretical and experimental analysis show that to provide an accuracy-assured recommendation, our Partitioned Probabilistic Neighbour Selection method yields a better trade-off between the recommendation accuracy and system security.