OpenRaiser/Intern-Atlas huggingface dataset:
Recognizing objects in adversarial clutter: Breaking a visual captcha
Authors: Greg Mori, Jitendra Malik
Venue: Conference CVPR 2003
Year: 2003

In this paper we explore object recognition in clutter. We test our object recognition techniques on Gimpy and EZ-Gimpy, examples of visual CAPTCHAs. A CAPTCHA ("Completely Automated Public Turing test to Tell Computers and Humans Apart") is a program that can generate and grade tests that most humans can pass, yet current computer programs can't pass. EZ-Gimpy, currently used by Yahoo, and Gimpy are CAPTCHAs based on word recognition in the presence of clutter. These CAPTCHAs provide excellent test sets since the clutter they contain is adversarial; it is designed to confuse computer programs. We have developed efficient methods based on shape context matching that can identify the word in an EZ-Gimpy image with a success rate of 92%, and the requisite 3 words in a Gimpy image 33% of the time. The problem of identifying words in such severe clutter provides valuable insight into the more general problem of object recognition in scenes. The methods that we present are instances of a framework designed to tackle this general problem.
A generic solver combining unsupervised learning and representation learning for breaking text-based captchas
Authors: Sheng Tian, Tao Xiong
Venue: Conference WWW 2020
Year: 2020

Although there are many alternative captcha schemes available, text-based captchas are still one of the most popular security mechanism to maintain Internet security and prevent malicious attacks, due to the user preferences and ease of design. Over the past decade, different methods of breaking captchas have been proposed, which helps captcha keep evolving and become more robust. However, these previous works generally require heavy expert involvement and gradually become ineffective with the introduction of new security features. This paper proposes a generic solver combining unsupervised learning and representation learning to automatically remove the noisy background of captchas and solve text-based captchas. We introduce a new training scheme for constructing mini-batches, which contain a large number of unlabeled hard examples, to improve the efficiency of representation learning. Unlike existing deep learning algorithms, our method requires significantly fewer labeled samples and surpasses the recognition performance of a fully-supervised model with the same network architecture. Moreover, extensive experiments show that the proposed method outperforms state-of-the-art by delivering a higher accuracy on various captcha schemes. We provide further discussions of potential applications of the proposed unified framework. We hope that our work can inspire the community to enhance the security of text-based captchas.
Personalized re-ranking with item relationships for e-commerce
Authors: Weiwen Liu, Qing Liu, Ruiming Tang, Junyang Chen, Xiuqiang He, Pheng-Ann Heng
Venue: Conference CIKM 2020
Year: 2020

Re-ranking is a critical task for large-scale commercial recommender systems. Given the initial ranked lists, top candidates are re-ranked to improve the accuracy of the ranking results. However, existing re-ranking strategies are sub-optimal due to (i) most prior works do not consider explicit item relationships, like being substitutable or complementary, which may mutually influence the user satisfaction on other items in the lists, and (ii) they usually apply an identical re-ranking strategy for all users, with personalized user preferences and intents ignored. To resolve the problem, we construct a heterogeneous graph to fuse the initial scoring information and item relationships information. We develop a graph neural network based framework, IRGPR, to explicitly model transitive item relationships by recursively aggregating relational information from multi-hop neighborhoods. We also incorporate a novel intent embedding network to embed personalized user intents into the propagation. We conduct extensive experiments on real-world datasets, demonstrating the effectiveness of IRGPR in re-ranking. Further analysis reveals that modeling the item relationships and personalized intents are particularly useful for improving the performance of re-ranking.
Understanding and discovering deliberate self-harm content in social media
Authors: Yilin Wang, Jiliang Tang, Jundong Li, Baoxin Li, Yali Wan, Clayton Mellina, Neil O&apos, Hare, Yi Chang
Venue: Conference WWW 2017
Year: 2017

Studies suggest that self-harm users found it easier to discuss self-harm-related thoughts and behaviors using social media than in the physical world. Given the enormous and increasing volume of social media data, on-line self-harm content is likely to be buried rapidly by other normal content. To enable voices of self-harm users to be heard, it is important to distinguish self-harm content from other types of content. In this paper, we aim to understand self-harm content and provide automatic approaches to its detection. We first perform a comprehensive analysis on self-harm social media using different input cues. Our analysis, the first of its kind in large scale, reveals a number of important findings. Then we propose frameworks that incorporate the findings to discover self-harm content under both supervised and unsupervised settings. Our experimental results on a large social media dataset from Flickr demonstrate the effectiveness of the proposed frameworks and the importance of our findings in discovering self-harm content.
Boolean satisfiability for sequence mining
Authors: Saïd Jabbour, Lakhdar Sais, Yakoub Salhi
Venue: Conference CIKM 2013
Year: 2013

In this paper, we propose a SAT-based encoding for the problem of discovering frequent, closed and maximal patterns in a sequence of items and a sequence of itemsets. Our encoding can be seen as an improvement of the approach proposed in [8] for the sequences of items. In this case, we show experimentally on real world data that our encoding is significantly better. Then we introduce a new extension of the problem to enumerate patterns in a sequence of itemsets. Thanks to the flexibility and to the declarative aspects of our SAT-based approach, an encoding for the sequences of itemsets is obtained by a very slight modification of that for the sequences of items.
Estimating the cardinality of conjunctive queries over rdf data using graph summarisation
Authors: Giorgio Stefanoni, Boris Motik, Egor V. Kostylev
Venue: Conference WWW 2018
Year: 2018

Estimating the cardinality (i.e., the number of answers) of conjunctive queries is particularly difficult in RDF systems: queries over RDF data are navigational and thus tend to involve many joins. We present a new, principled cardinality estimation technique based on graph summarisation. We interpret a summary of an RDF graph using a possible world semantics and formalise the estimation problem as computing the expected cardinality over all RDF graphs represented by the summary, and we present a closed-form formula for computing the expectation of arbitrary queries. We also discuss approaches to RDF graph summarisation. Finally, we show empirically that our cardinality technique is more accurate and more consistent, often by orders of magnitude, than the state of the art.
Towards verified robustness under text deletion interventions
Authors: Johannes Welbl, Po-Sen Huang, Robert Stanforth, Sven Gowal, Krishnamurthy (Dj) Dvijotham, Martin Szummer, Pushmeet Kohli
Venue: Conference ICLR 2020
Year: 2020

Neural networks are widely used in Natural Language Processing, yet despite their empirical successes, their behaviour is brittle: they are both over-sensitive to small input changes, and under-sensitive to deletions of large fractions of input text. This paper aims to tackle under-sensitivity in the context of natural language inference by ensuring that models do not become more confident in their predictions as arbitrary subsets of words from the input text are deleted. We develop a novel technique for formal verification of this specification for models based on the popular decomposable attention mechanism by employing the efficient yet effective interval bound propagation (IBP) approach. Using this method we can efficiently prove, given a model, whether a particular sample is free from the under-sensitivity problem. We compare different training methods to address under-sensitivity, and compare metrics to measure it. In our experiments on the SNLI and MNLI datasets, we observe that IBP training leads to a significantly improved verified accuracy. On the SNLI test set, we can verify 18.4% of samples, a substantial improvement over only 2.8% using standard training.
Auditing for Discrimination in Algorithms Delivering Job Ads
Authors: Basileal Imana, Aleksandra Korolova, John S. Heidemann
Venue: Conference WWW 2021
Year: 2021

Ad platforms such as Facebook, Google and LinkedIn promise value for advertisers through their targeted advertising. However, multiple studies have shown that ad delivery on such platforms can be skewed by gender or race due to hidden algorithmic optimization by the platforms, even when not requested by the advertisers. Building on prior work measuring skew in ad delivery, we develop a new methodology for black-box auditing of algorithms for discrimination in the delivery of job advertisements. Our first contribution is to identify the distinction between skew in ad delivery due to protected categories such as gender or race, from skew due to differences in qualification among people in the targeted audience. This distinction is important in U.S. law, where ads may be targeted based on qualifications, but not on protected categories. Second, we develop an auditing methodology that distinguishes between skew explainable by differences in qualifications from other factors, such as the ad platform’s optimization for engagement or training its algorithms on biased data. Our method controls for job qualification by comparing ad delivery of two concurrent ads for similar jobs, but for a pair of companies with different de facto gender distributions of employees. We describe the careful statistical tests that establish evidence of non-qualification skew in the results. Third, we apply our proposed methodology to two prominent targeted advertising platforms for job ads: Facebook and LinkedIn. We confirm skew by gender in ad delivery on Facebook, and show that it cannot be justified by differences in qualifications. We fail to find skew in ad delivery on LinkedIn. Finally, we suggest improvements to ad platform practices that could make external auditing of their algorithms in the public interest more feasible and accurate.
Cminet: a graph learning framework for content-aware multi-channel influence diffusion
Authors: Hsi-Wen Chen, De-Nian Yang, Wang-Chien Lee, Philip S. Yu, Ming-Syan Chen
Venue: Conference WWW 2023
Year: 2023

The phenomena of influence diffusion on social networks have received tremendous research interests in the past decade. While most prior works mainly focus on predicting the total influence spread on a single network, a marketing campaign that exploits influence diffusion often involves multiple channels with various information disseminated on different media. In this paper, we introduce a new influence estimation problem, namely Content-aware Multi-channel Influence Diffusion (CMID), and accordingly propose CMINet to predict newly influenced users, given a set of seed users with different multimedia contents. In CMINet, we first introduce DiffGNN to encode the influencing power of users (nodes) and Influence-aware Optimal Transport (IOT) to align the embeddings to address the distribution shift across different diffusion channels. Then, we transform CMID into a node classification problem and propose Social-based Multimedia Feature Extractor (SMFE) and Content-aware Multi-channel Influence Propagation (CMIP) to jointly learn the user preferences on multimedia contents and predict the susceptibility of users. Furthermore, we prove that CMINet preserves monotonicity and submodularity, thus enabling (1 − 1/e)-approximate solutions for influence maximization. Experimental results manifest that CMINet outperforms eleven baselines on three public datasets.
A semantic partitioning method for large-scale training of knowledge graph embeddings
Authors: Yuhe Bai
Venue: Conference WWW 2023
Year: 2023

In recent years, knowledge graph embeddings have achieved great success. Many methods have been proposed and achieved state-of-the-art results in various tasks. However, most of the current methods present one or more of the following problems: (i) They only consider fact triplets, while ignoring the ontology information of knowledge graphs. (ii) The obtained embeddings do not contain much semantic information. Therefore, using these embeddings for semantic tasks is problematic. (iii) They do not enable large-scale training. In this paper, we propose a new algorithm that incorporates the ontology of knowledge graphs and partitions the knowledge graph based on classes to include more semantic information for parallel training of large-scale knowledge graph embeddings. Our preliminary results show that our algorithm performs well on several popular benchmarks.
Cross-domain product search with knowledge graph
Authors: Rui Zhu, Yiming Zhao, Wei Qu, Zhongyi Liu, Chenliang Li
Venue: Conference CIKM 2022
Year: 2022

The notion personalization lies on the core of a real-world product search system, whose aim is to understand the user's search intent in a fine-grained level. The existing solutions mainly achieve this purpose through a coarse-grained semantic matching in terms of the query and item's description or the collective click correlations. Besides the issued query, the historical search behaviors of a user would cover lots of her personalized interests, which is a promising avenue to alleviate the semantic gap between users, items and queries. However, as to a specific domain, a user's search behaviors are generally sparse or even unavailable (i.e., cold-start users). How to exploit the search behaviors from the other relevant domain and enable effective fine-grained intent understanding remains largely unexplored for product search. Moreover, the semantic gap could be further aggravated since the properties of an item could evolve over time (e.g., the price adjustment for a mobile phone or the business plan update for a financial item), which is also mainly overlooked by the existing solutions. To this end, we are interested in bridging the semantic gap via a marriage between cross-domain transfer learning and knowledge graph. Specifically, we propose a simple yet effective knowledge graph based information propagation framework for cross-domain product search (named KIPS). In KIPS, we firstly utilize a shared knowledge graph relevant to both source and target domains as a semantic backbone to facilitate the information propagation across domains. Then, we build individual collaborative knowledge graphs to model both long-term interests/characteristics and short-term interests/characteristics of a user/item respectively. In order to harness cross-domain interest correlations, two unsupervised strategies to guide the interest learning and alignment are introduced: maximum mean discrepancy (MMD) and kg-aware contrastive learning. In detail, the MMD is utilized to support a coarse-grained domain alignment over the user's long-term interests across two domains. Then, the kg-aware contrastive learning process conducts a fine-grained interest alignment based on the shared knowledge graph. Experiments over two real-world large-scale datasets demonstrate the effectiveness of KIPS over a series of strong baselines. Our online A/B test also shows substantial performance gain on multiple metrics. Currently, KIPS has been deployed in AliPay for financial product search. Both the code implementation and the two datasets used for evaluation will be released online publicly.
Randomized pricing with deferred acceptance for revenue maximization with submodular objectives
Authors: He Huang, Kai Han, Shuang Cui, Jing Tang
Venue: Conference WWW 2023
Year: 2023

A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee the truthfulness of users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most of the existing BFMs concentrate on maximizing a monotone submodular function subject to a knapsack constraint, which is insufficient for many applications with complex objectives or constraints. Observing this, the recent studies (e.g., [4, 5, 11]) have considered non-monotone submodular objectives or more complex constraints such as a k-system constraint. In this study, we follow this line of research and propose truthful BFMs with improved performance bounds for non-monotone submodular objectives with or without a k-system constraint. Our BFMs leverage the idea of providing random prices to users while deferring the decision on the final winning set, and are also based on a novel randomized algorithm for the canonical constrained submodular maximization problem achieving better performance bounds compared to the state-of-the-art. Finally, the effectiveness and efficiency of our approach are demonstrated by extensive experiments on several applications about social network marketing, crowdsourcing and personalized recommendation.
Rocoursenet: Robust training of a prediction aware recourse model
Authors: Hangzhi Guo, Feiran Jia, Jinghui Chen, Anna Cinzia Squicciarini, Amulya Yadav
Venue: Conference CIKM 2023
Year: 2023

Counterfactual (CF) explanations for machine learning (ML) models are preferred by end-users, as they explain the predictions of ML models by providing a recourse (or contrastive) case to individuals who are adversely impacted by predicted outcomes. Existing CF explanation methods generate recourses under the assumption that the underlying target ML model remains stationary over time. However, due to commonly occurring distributional shifts in training data, ML models constantly get updated in practice, which might render previously generated recourses invalid and diminish end-users trust in our algorithmic framework. To address this problem, we propose RoCourseNet, a training framework that jointly optimizes predictions and recourses that are robust to future data shifts. This work contains four key contributions: (1) We formulate the robust recourse generation problem as a tri-level optimization problem which consists of two sub-problems: (i) a bi-level problem that finds the worst-case adversarial shift in the training data, and (ii) an outer minimization problem to generate robust recourses against this worst-case shift. (2) We leverage adversarial training to solve this tri-level optimization problem by: (i) proposing a novel virtual data shift (VDS) algorithm to find worst-case shifted ML models via explicitly considering the worst-case data shift in the training dataset, and (ii) a block-wise coordinate descent procedure to optimize for prediction and corresponding robust recourses. (3) We evaluate RoCourseNet's performance on three real-world datasets, and show that RoCourseNet consistently achieves more than 96% robust validity and outperforms state-of-the-art baselines by at least 10% in generating robust CF explanations. (4) Finally, we generalize the RoCourseNet framework to accommodate any parametric post-hoc methods for improving robust validity.
Flexible and robust counterfactual explanations with minimal satisfiable perturbations
Authors: Yongjie Wang, Hangwei Qian, Yongjie Liu, Wei Guo, Chunyan Miao
Venue: Conference CIKM 2023
Year: 2023

Counterfactual explanations (CFEs) exemplify how to minimally modify a feature vector to achieve a different prediction for an instance. CFEs can enhance informational fairness and trustworthiness, and provide suggestions for users who receive adverse predictions. However, recent research has shown that multiple CFEs can be offered for the same instance or instances with slight differences. Multiple CFEs provide flexible choices and cover diverse desiderata for user selection. However, individual fairness and model reliability will be damaged if unstable CFEs with different costs are returned. Existing methods fail to exploit flexibility and address the concerns of non-robustness simultaneously. To address these issues, we propose a conceptually simple yet effective solution named Counterfactual Explanations with Minimal Satisfiable Perturbations (CEMSP). Specifically, CEMSP constrains changing values of abnormal features with the help of their semantically meaningful normal ranges. For efficiency, we model the problem as a Boolean satisfiability problem to modify as few features as possible. Additionally, CEMSP is a general framework and can easily accommodate more practical requirements, e.g., casualty and actionability. Compared to existing methods, we conduct comprehensive experiments on both synthetic and real-world datasets to demonstrate that our method provides more robust explanations while preserving flexibility.
Crowdquake: A networked system of low-cost sensors for earthquake detection via deep learning
Authors: Xin Huang 0020, Jangsoo Lee, Young-Woo Kwon 0001, Chul-Ho Lee
Venue: Conference KDD 2020
Year: 2020

Recently, low-cost acceleration sensors have been widely used to detect earthquakes due to the significant development of MEMS technologies. It, however, still requires a high-density network to fully harness the low-cost sensors, especially for real-time earthquake detection. The design of a high-performance and scalable networked system thus becomes essential to be able to process a large amount of sensor data from hundreds to thousands of the sensors. An efficient and accurate earthquake-detection algorithm is also necessary to distinguish earthquake waveforms from various kinds of non-earthquake ones within the huge data in real time. In this paper, we present CrowdQuake, a networked system based on low-cost acceleration sensors, which monitors ground motions and detects earthquakes, by developing a convolutional-recurrent neural network model. This model ensures high detection performance while maintaining false alarms at a negligible level. We also provide detailed case studies on two of a few small earthquakes that have been detected by CrowdQuake during its last one-year operation.
Rgrecsys: A toolkit for robustness evaluation of recommender systems
Authors: Zohreh Ovaisi, Shelby Heinecke, Jia Li, Yongfeng Zhang, Elena Zheleva, Caiming Xiong
Venue: Conference WSDM 2022
Year: 2022

Robust machine learning is an increasingly important topic that focuses on developing models resilient to various forms of imperfect data. Due to the pervasiveness of recommender systems in online technologies, researchers have carried out several robustness studies focusing on data sparsity and profile injection attacks. Instead, we propose a more holistic view of robustness for recommender systems that encompasses multiple dimensions - robustness with respect to sub-populations, transformations, distributional disparity, attack, and data sparsity. While there are several libraries that allow users to compare different recommender system models, there is no software library for comprehensive robustness evaluation of recommender system models under different scenarios. As our main contribution, we present a robustness evaluation toolkit, Robustness Gym for RecSys (RGRecSys -- https://www.github.com/salesforce/RGRecSys), that allows us to quickly and uniformly evaluate the robustness of recommender system models.