Search

In the past decade, significant strides in deep learning have led to numerous groundbreaking applications. Despite these advancements, the understanding of the high generalizability of deep learning, especially in such an over-parametrized space, remains limited. Successful applications are often considered as empirical rather than scientific achievements. For instance, deep neural networks' (DNNs) internal representations, decision-making mechanism, absence of overfitting in an over-parametrized space, high generalizability, etc., remain less understood. This paper delves into the loss landscape of DNNs through the lens of spin glass in statistical physics, i.e. a system characterized by a complex energy landscape with numerous metastable states, to better understand how DNNs work. We investigated a single hidden layer Rectified Linear Unit (ReLU) neural network model, and introduced several protocols to examine the analogy between DNNs (trained with datasets including MNIST and CIFAR10) and spin glass. Specifically, we used (1) random walk in the parameter space of DNNs to unravel the structures in their loss landscape; (2) a permutation-interpolation protocol to study the connection between copies of identical regions in the loss landscape due to the permutation symmetry in the hidden layers; (3) hierarchical clustering to reveal the hierarchy among trained solutions of DNNs, reminiscent of the so-called Replica Symmetry Breaking (RSB) phenomenon (i.e. the Parisi solution) in analogy to spin glass; (4) finally, we examine the relationship between the degree of the ruggedness of the loss landscape of the DNN and its generalizability, showing an improvement of flattened minima., Comment: 21 pages, 10 figures

Numerous studies have demonstrated the manifold benefits of tennis, such as increasing overall physical and mental health. Unfortunately, many children and youth from low-income families are unable to engage in this sport mainly due to financial constraints such as private lesson expenses as well as logistical concerns to and back from such lessons and clinics. While several tennis self-training systems exist, they are often tailored for professionals and are prohibitively expensive. The present study aims to classify tennis players' skill levels and classify tennis strokes into phases characterized by motion attributes for a future development of an AI-based tennis self-training model for affordable and convenient applications running on devices used in daily life such as an iPhone or an Apple Watch for tennis skill improvement. We collected motion data, including Motion Yaw, Roll and Pitch from inertial measurement units (IMUs) worn by participating junior tennis players. For this pilot study, data from twelve participants were processed using Support Vector Machine (SVM) algorithms. The SVM models demonstrated an overall accuracy of 77% in classifying players as beginners or intermediates, with low rates of false positives and false negatives, effectively distinguishing skill levels. Additionally, the tennis swings were successfully classified into five phases based on the collected motion data. These findings indicate that SVM-based classification can be a reliable foundation for developing an equitable and accessible AI-driven tennis training system., Comment: 21 pages, 9 figures, 1 table

The proliferation of fake news has had far-reaching implications on politics, the economy, and society at large. While Fake news detection methods have been employed to mitigate this issue, they primarily depend on two essential elements: the quality and relevance of the evidence, and the effectiveness of the verdict prediction mechanism. Traditional methods, which often source information from static repositories like Wikipedia, are limited by outdated or incomplete data, particularly for emerging or rare claims. Large Language Models (LLMs), known for their remarkable reasoning and generative capabilities, introduce a new frontier for fake news detection. However, like traditional methods, LLM-based solutions also grapple with the limitations of stale and long-tail knowledge. Additionally, retrieval-enhanced LLMs frequently struggle with issues such as low-quality evidence retrieval and context length constraints. To address these challenges, we introduce a novel, retrieval-augmented LLMs framework--the first of its kind to automatically and strategically extract key evidence from web sources for claim verification. Employing a multi-round retrieval strategy, our framework ensures the acquisition of sufficient, relevant evidence, thereby enhancing performance. Comprehensive experiments across three real-world datasets validate the framework's superiority over existing methods. Importantly, our model not only delivers accurate verdicts but also offers human-readable explanations to improve result interpretability.

Inspired by the exceptional general intelligence of Large Language Models (LLMs), researchers have begun to explore their application in pioneering the next generation of recommender systems - systems that are conversational, explainable, and controllable. However, existing literature primarily concentrates on integrating domain-specific knowledge into LLMs to enhance accuracy, often neglecting the ability to follow instructions. To address this gap, we initially introduce a collection of supervised learning tasks, augmented with labels derived from a conventional recommender model, aimed at explicitly improving LLMs' proficiency in adhering to recommendation-specific instructions. Subsequently, we develop a reinforcement learning-based alignment procedure to further strengthen LLMs' aptitude in responding to users' intentions and mitigating formatting errors. Through extensive experiments on two real-world datasets, our method markedly advances the capability of LLMs to comply with instructions within recommender systems, while sustaining a high level of accuracy performance., Comment: 14 pages; Accepted by ACL 2024 main conference

Test of {macroscopic realism} (MR) is key to understanding the foundation of quantum mechanics. Due to the existence of the {non-invasive measurability} loophole and other interpretation loopholes, however, such test remains an open question. Here we propose a general inequality based on high-order correlations of measurements for a loophole-free test of MR at the weak signal limit. Importantly, the inequality is established using the statistics of \textit{raw data} recorded by classical devices, without requiring a specific model for the measurement process, so its violation would falsify MR without the interpretation loophole. The non-invasive measurability loophole is also closed, since the weak signal limit can be verified solely by measurement data (using the relative scaling behaviors of different orders of correlations). We demonstrate that the inequality can be broken by a quantum spin model. The inequality proposed here provides an unambiguous test of the MR principle and is also useful to characterizing {quantum coherence}.

The ease of spreading false information online enables individuals with malicious intent to manipulate public opinion and destabilize social stability. Recently, fake news detection based on evidence retrieval has gained popularity in an effort to identify fake news reliably and reduce its impact. Evidence retrieval-based methods can improve the reliability of fake news detection by computing the textual consistency between the evidence and the claim in the news. In this paper, we propose a framework for fake news detection based on MUlti-Step Evidence Retrieval enhancement (MUSER), which simulates the steps of human beings in the process of reading news, summarizing, consulting materials, and inferring whether the news is true or fake. Our model can explicitly model dependencies among multiple pieces of evidence, and perform multi-step associations for the evidence required for news verification through multi-step retrieval. In addition, our model is able to automatically collect existing evidence through paragraph retrieval and key evidence selection, which can save the tedious process of manual evidence collection. We conducted extensive experiments on real-world datasets in different languages, and the results demonstrate that our proposed model outperforms state-of-the-art baseline methods for detecting fake news by at least 3% in F1-Macro and 4% in F1-Micro. Furthermore, it provides interpretable evidence for end users., Comment: 12 pages, 5 figures, accepted by KDD '23, ADS track

Explainable recommendation is a technique that combines prediction and generation tasks to produce more persuasive results. Among these tasks, textual generation demands large amounts of data to achieve satisfactory accuracy. However, historical user reviews of items are often insufficient, making it challenging to ensure the precision of generated explanation text. To address this issue, we propose a novel model, ERRA (Explainable Recommendation by personalized Review retrieval and Aspect learning). With retrieval enhancement, ERRA can obtain additional information from the training sets. With this additional information, we can generate more accurate and informative explanations. Furthermore, to better capture users' preferences, we incorporate an aspect enhancement component into our model. By selecting the top-n aspects that users are most concerned about for different items, we can model user representation with more relevant details, making the explanation more persuasive. To verify the effectiveness of our model, extensive experiments on three datasets show that our model outperforms state-of-the-art baselines (for example, 3.4% improvement in prediction and 15.8% improvement in explanation for TripAdvisor).

In this paper, we present an algorithmic study on how to surpass competitors in popularity by strategic promotions in social networks. We first propose a novel model, in which we integrate the Preferential Attachment (PA) model for popularity growth with the Independent Cascade (IC) model for influence propagation in social networks called PA-IC model. In PA-IC, a popular item and a novice item grab shares of popularity from the natural popularity growth via the PA model, while the novice item tries to gain extra popularity via influence cascade in a social network. The {\em popularity ratio} is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate {\em Popularity Ratio Maximization (PRM)} as the problem of selecting seeds in multiple rounds to maximize the popularity ratio in the end. We analyze the popularity ratio and show that it is monotone but not submodular. To provide an effective solution, we devise a surrogate objective function and show that empirically it is very close to the original objective function while theoretically, it is monotone and submodular. We design two efficient algorithms, one for the overlapping influence and non-overlapping seeds (across rounds) setting and the other for the non-overlapping influence and overlapping seed setting, and further discuss how to deal with other models and problem variants. Our empirical evaluation further demonstrates that the proposed PRM-IMM method consistently achieves the best popularity promotion compared to other methods. Our theoretical and empirical analyses shed light on the interplay between influence maximization and preferential attachment in social networks., Comment: 22 pages, 8 figures, to be appear SIGMOD 2023

Recent studies show that Graph Neural Networks(GNNs) are vulnerable and easily fooled by small perturbations, which has raised considerable concerns for adapting GNNs in various safety-critical applications. In this work, we focus on the emerging but critical attack, namely, Graph Injection Attack(GIA), in which the adversary poisons the graph by injecting fake nodes instead of modifying existing structures or node attributes. Inspired by findings that the adversarial attacks are related to the increased heterophily on perturbed graphs (the adversary tends to connect dissimilar nodes), we propose a general defense framework CHAGNN against GIA through cooperative homophilous augmentation of graph data and model. Specifically, the model generates pseudo-labels for unlabeled nodes in each round of training to reduce heterophilous edges of nodes with distinct labels. The cleaner graph is fed back to the model, producing more informative pseudo-labels. In such an iterative manner, model robustness is then promisingly enhanced. We present the theoretical analysis of the effect of homophilous augmentation and provide the guarantee of the proposal's validity. Experimental results empirically demonstrate the effectiveness of CHAGNN in comparison with recent state-of-the-art defense methods on diverse real-world datasets., Comment: The paper has been accepted for presentation at ECML PKDD 2022

The functions of complex networks are usually determined by a small set of vital nodes. Finding the best set of vital nodes (eigenshield nodes) is critical to the network's robustness against rumor spreading and cascading failures, which makes it one of the fundamental problems in network science. The problem is challenging as it requires to maximize the influence of nodes in the set while simultaneously minimizing the redundancies between the set's nodes. However, the redundancy mechanism is rarely investigated by previous studies. Here we introduce the matrix perturbation framework to find a small ``eigenshield" set of nodes that, when removed, lead to the largest drop in the network's spectral radius. We show that finding the ``eigenshield" nodes can be translated into the optimization of an objective function that simultaneously accounts for the individual influence of each node and redundancy between different nodes. We analytically quantify the influence redundancy that explains why an important node might play an insignificant role in the ``eigenshield" node set. Extensive experiments under diverse influence maximization problems, ranging from network dismantling to spreading maximization, demonstrate that the eigenshield detection tends to significantly outperforms state-of-the-art methods across most problems. Our findings shed light on the mechanisms that may lie at the core of the function of vital nodes in complex network., Comment: 24 pages, 16 figures

The detection of fake news often requires sophisticated reasoning skills, such as logically combining information by considering word-level subtle clues. In this paper, we move towards fine-grained reasoning for fake news detection by better reflecting the logical processes of human thinking and enabling the modeling of subtle clues. In particular, we propose a fine-grained reasoning framework by following the human information-processing model, introduce a mutual-reinforcement-based method for incorporating human knowledge about which evidence is more important, and design a prior-aware bi-channel kernel graph network to model subtle differences between pieces of evidence. Extensive experiments show that our model outperforms the state-of-the-art methods and demonstrate the explainability of our approach., Comment: Published as a conference paper at AAAI 2022

Since the beginning of the COVID-19 spreading, the number of studies on the epidemic models increased dramatically. It is important for policymakers to know how the disease will spread and what are the effects of the policies and environment on the spreading. In this paper, we propose two extensions to the standard SIR model: (a) we consider the prevention measures adopted based on the current severity of the infection. Those measures are adaptive and change over time; (b) multiple cities and regions are considered, with population movements between those cities and regions, while taking into account that each region may have different prevention measures. Although the adaptive measures and mobility of the population were often observed during the pandemic, these effects are rarely explicitly modeled and studied in the classical epidemic models. The model we propose gives rise to a plateau phenomenon: the number of people infected by the disease stays at the same level during an extended period of time. We show what are conditions need to be met in order for the spreading to exhibit a plateau period in a single city. In addition, this phenomenon is interdependent when considering multiple cities. We verify from the real-world data that the plateau phenomenon does exist in many regions of the world in the current COVID-19 development. Finally, we provide theoretical analysis on the plateau phenomenon for the single-city model and derive a series of results on the emergence and the ending of the plateau, as well as on the height and length of the plateau. Our theoretical results match well with our experimental findings.

Disinformation has long been regarded as a severe social problem, where fake news is one of the most representative issues. What is worse, today's highly developed social media makes fake news widely spread at incredible speed, bringing in substantial harm to various aspects of human life. Yet, the popularity of social media also provides opportunities to better detect fake news. Unlike conventional means which merely focus on either content or user comments, effective collaboration of heterogeneous social media information, including content and context factors of news, users' comments and the engagement of social media with users, will hopefully give rise to better detection of fake news. Motivated by the above observations, a novel detection framework, namely graph comment-user advanced learning framework (GCAL) is proposed in this paper. User-comment information is crucial but not well studied in fake news detection. Thus, we model user-comment context through network representation learning based on heterogeneous graph neural network. We conduct experiments on two real-world datasets, which demonstrate that the proposed joint model outperforms 8 state-of-the-art baseline methods for fake news detection (at least 4% in Accuracy, 7% in Recall and 5% in F1). Moreover, the proposed method is also explainable.

The goal of the ranking problem in networks is to rank nodes from best to worst, according to a chosen criterion. In this work, we focus on ranking the nodes according to their quality. The problem of ranking the nodes in bipartite networks is valuable for many real-world applications. For instance, high-quality products can be promoted on an online shop or highly reputed restaurants attract more people on venues review platforms. However, many classical ranking algorithms share a common drawback: they tend to rank older movies higher than newer movies, though some newer movies may have a high quality. This time bias originates from the fact that older nodes in a network tend to have more connections than newer ones. In the study, we develop a ranking method using a rebalance approach to diminish the time bias of the rankings in bipartite graphs.

With the rapid development of modern technology, the Web has become an important platform for users to make friends and acquire information. However, since information on the Web is over-abundant, information filtering becomes a key task for online users to obtain relevant suggestions. As most Websites can be ranked according to users' rating and preferences, relevance to queries, and recency, how to extract the most relevant item from the over-abundant information is always a key topic for researchers in various fields. In this paper, we adopt tools used to analyze complex networks to evaluate user reputation and item quality. In our proposed accumulative time-based ranking (ATR) algorithm, we incorporate two behavioral weighting factors which are updated when users select or rate items, to reflect the evolution of user reputation and item quality over time. We showed that our algorithm outperforms state-of-the-art ranking algorithms in terms of precision and robustness on empirical datasets from various online retailers and the citation datasets among research publications.

We propose an original approach to describe the scientific progress in a quantitative way. Using innovative Machine Learning techniques we create a vector representation for the PACS codes and we use them to represent the relative movements of the various domains of Physics in a multi-dimensional space. This methodology unveils about 25 years of scientific trends, enables us to predict innovative couplings of fields, and illustrates how Nobel Prize papers and APS milestones drive the future convergence of previously unrelated fields.

Many major cities suffer from severe traffic congestion. Road expansion in the cites is usually infeasible, and an alternative way to alleviate traffic congestion is to coordinate the route of vehicles. Various path selection and planning algorithms are thus proposed, but most existing methods only plan paths separately and provide un-coordinated solutions. Recently, an analogy between the coordination of vehicular routes and the interaction of polymers is drawn; the spin glass theory in statistical physics is employed to optimally coordinate transportation routes. To further examine the advantages brought by path coordination, we incorporate the link congestion function developed by the Bureau of Public Roads (BPR) into the polymer routing algorithm. We then estimate in simulations the traveling time of all users saved by the polymer-BPR algorithm in randomly generated networks and real transportation networks in major cities including London, New York and Beijing. We found that a large amount of traveling time is saved in all studied networks, suggesting that the approach inspired by polymer physics is effective in minimizing the traveling time via path coordination, which is a promising tool for alleviating traffic congestions.

When investigating the spreading of a piece of information or the diffusion of an innovation, we often lack information on the underlying propagation network. Reconstructing the hidden propagation paths based on the observed diffusion process is a challenging problem which has recently attracted attention from diverse research fields. To address this reconstruction problem, based on static similarity metrics commonly used in the link prediction literature, we introduce new node-node temporal similarity metrics. The new metrics take as input the time-series of multiple independent spreading processes, based on the hypothesis that two nodes are more likely to be connected if they were often infected at similar points in time. This hypothesis is implemented by introducing a time-lag function which penalizes distant infection times. We find that the choice of this time-lag strongly affects the metrics' reconstruction accuracy, depending on the network's clustering coefficient and we provide an extensive comparative analysis of static and temporal similarity metrics for network reconstruction. Our findings shed new light on the notion of similarity between pairs of nodes in complex networks.

Prediction is one of the major challenges in complex systems. The prediction methods have shown to be effective predictors of the evolution of networks. These methods can help policy makers to solve practical problems successfully and make better strategy for the future. In this work, we focus on exporting countries' data of the international trading network. A recommendation system is then used to identify the products corresponding to the production capacity of each individual country, but are somehow overlook by the country. Then, we simulate the evolution of the country's fitness if it would have followed the recommendations. The result of this work is the combination combine these two methods to provide insights to countries on how to enhance the diversification of their exported products in a scientific way and improve national competitiveness significantly, especially for developing countries.