OpenRaiser/Intern-Atlas huggingface dataset:
Neighbor- Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics
Authors: Sourav Dutta, Pratik Nayek, Arnab Bhattacharya
Venue: Conference WWW 2017
Year: 2017

Labeled graphs provide a natural way of representing entities, relationships and structures within real datasets such as knowledge graphs and protein interactions. Applications such as question answering, semantic search, and motif discovery entail efficient approaches for subgraph matching involving both label and structural similarities. Given the NP-completeness of subgraph isomorphism and the presence of noise, approximate graph matching techniques are required to handle queries in a robust and real-time manner. This paper presents a novel technique to characterize the subgraph similarity based on statistical significance captured by chi-square statistic. The statistical significance model takes into account the background structure and label distribution in the neighborhood of vertices to obtain the best matching subgraph and, therefore, robustly handles partial label and structural mismatches. Based on the model, we propose two algorithms, VELSET and NAGA, that, given a query graph, return the top-k most similar subgraphs from a (large) database graph. While VELSET is more accurate and robust to noise, NAGA is faster and more applicable for scenarios with low label noise. Experiments on large real-life graph datasets depict significant improvements in terms of accuracy and running time in comparison to the state-of-the-art methods.
Large maximal cliques enumeration in sparse graphs
Authors: Natwar Modani, Kuntal Dey
Venue: Conference CIKM 2008
Year: 2008

Here we study a variant of maximal clique enumeration problem by incorporating a minimum size criterion. We describe preprocessing techniques to reduce the graph size. This is of practical interest since enumerating maximal cliques is a computationally hard problem and the execution time increases rapidly with the input size. We discuss basics of an algorithm for enumerating large maximal cliques which exploits the constraint on minimum size of the desired maximal cliques. Social networks are prime examples of large sparse graphs where enumerating large maximal cliques is of interest. We present experimental results on the social network formed by the call detail records of one of the world's largest telecom service providers. Our results show that the preprocessing methods achieve significant reduction in the graph size. We also characterize the execution behaviour of our large maximal clique enumeration algorithm.
Babel: A platform for facilitating research in scholarly article discovery
Authors: Ian Wesley-Smith, Jevin D. West
Venue: Conference WWW 2016
Year: 2016

The body of scientific literature is growing at an exponential rate. This expansion of scientific knowledge has increased the need for tools to help users find relevant articles. However, researchers developing new scholarly article recommendation algorithms face two substantial hurdles: acquiring high-quality, large-scale scholarly metadata and mechanisms for evaluating their recommendation algorithms. To address these problems we created Babel---an open-source platform uniting publisher, researchers, and users. Babel includes tens of millions of scholarly articles, several recommendation algorithms, and tools for integrating recommendations into publisher websites and other scholarly platforms.
Hidden topic sentiment model
Authors: Md. Mustafizur Rahman, Hongning Wang
Venue: Conference WWW 2016
Year: 2016

Various topic models have been developed for sentiment analysis tasks. But the simple topic-sentiment mixture assumption prohibits them from finding fine-grained dependency between topical aspects and sentiments. In this paper, we build a Hidden Topic Sentiment Model (HTSM) to explicitly capture topic coherence and sentiment consistency in an opinionated text document to accurately extract latent aspects and corresponding sentiment polarities. In HTSM, 1) topic coherence is achieved by enforcing words in the same sentence to share the same topic assignment and modeling topic transition between successive sentences; 2) sentiment consistency is imposed by constraining topic transitions via tracking sentiment changes; and 3) both topic transition and sentiment transition are guided by a parameterized logistic function based on the linguistic signals directly observable in a document. Extensive experiments on four categories of product reviews from both Amazon and NewEgg validate the effectiveness of the proposed model.
Learning visual features from snapshots for web search
Authors: Yixing Fan, Jiafeng Guo, Yanyan Lan, Jun Xu, Liang Pang, Xueqi Cheng
Venue: Conference CIKM 2017
Year: 2017

When applying learning to rank algorithms to Web search, a large number of features are usually designed to capture the relevance signals. Most of these features are computed based on the extracted textual elements, link analysis, and user logs. However, Web pages are not solely linked texts, but have structured layout organizing a large variety of elements in different styles. Such layout itself can convey useful visual information, indicating the relevance of a Web page. For example, the query-independent layout (i.e., raw page layout) can help identify the page quality, while the query-dependent layout (i.e., page rendered with matched query words) can further tell rich structural information (e.g., size, position and proximity) of the matching signals. However, such visual information of layout has been seldom utilized in Web search in the past. In this work, we propose to learn rich visual features automatically from the layout of Web pages (i.e., Web page snapshots) for relevance ranking. Both query-independent and query-dependent snapshots are considered as the new inputs. We then propose a novel visual perception model inspired by human's visual search behaviors on page viewing to extract the visual features. This model can be learned end-to-end together with traditional human-crafted features. We also show that such visual features can be efficiently acquired in the online setting with an extended inverted indexing scheme. Experiments on benchmark collections demonstrate that learning visual features from Web page snapshots can significantly improve the performance of relevance ranking in ad-hoc Web retrieval tasks.
Label aggregation for crowdsourcing with bi-layer clustering
Authors: Jing Zhang, Victor S. Sheng, Tao Li
Venue: Conference SIGIR 2017
Year: 2017

This paper proposes a novel general label aggregation method for both binary and multi-class labeling in crowdsourcing, namely Bi-Layer Clustering (BLC), which clusters two layers of features - the conceptual-level and the physical-level features - to infer true labels of instances. BLC first clusters the instances using the conceptual-level features extracted from their multiple noisy labels and then performs clustering again using the physical-level features. It can facilitate tracking the uncertainty changes of the instances, so that the integrated labels that are likely to be falsely inferred on the conceptual layer can be easily corrected using the estimated labels on the physical layer. Experimental results on two real-world crowdsourcing data sets show that BLC outperforms seven state-of-the-art methods.
Top-k subgraph matching query in a large graph
Authors: Lei Zou, Lei Chen, Yansheng Lu
Venue: Conference CIKM 2007
Year: 2007

Recently, due to its wide applications, subgraph search has attracted a lot of attention from database and data mining community. Sub-graph search is defined as follows: given a query graph Q, we report all data graphs containing Q in the database. However, there is little work about sub-graph search in a single large graph, which has been used in many applications, such as biological network and social network.
Predicting response in mobile advertising with hierarchical importance-aware factorization machine
Authors: Richard Jayadi Oentaryo, Ee-Peng Lim, Jia-Wei Low, David Lo, Michael Finegold
Venue: Conference WSDM 2014
Year: 2014

Mobile advertising has recently seen dramatic growth, fueled by the global proliferation of mobile phones and devices. The task of predicting ad response is thus crucial for maximizing business revenue. However, ad response data change dynamically over time, and are subject to cold-start situations in which limited history hinders reliable prediction. There is also a need for a robust regression estimation for high prediction accuracy, and good ranking to distinguish the impacts of different ads. To this end, we develop a Hierarchical Importance-aware Factorization Machine (HIFM), which provides an effective generic latent factor framework that incorporates importance weights and hierarchical learning. Comprehensive empirical studies on a real-world mobile advertising dataset show that HIFM outperforms the contemporary temporal latent factor models. The results also demonstrate the efficacy of the HIFM's importance-aware and hierarchical learning in improving the overall prediction and prediction in cold-start scenarios, respectively.
Auditing the partisanship of google search snippets
Authors: Desheng Hu, Shan Jiang, Ronald E. Robertson, Christo Wilson
Venue: Conference WWW 2019
Year: 2019

The text snippets presented in web search results provide users with a slice of page content that they can quickly scan to help inform their click decisions. However, little is known about how these snippets are generated or how they relate to a user's search query. Motivated by the growing body of evidence suggesting that search engine rankings can influence undecided voters, we conducted an algorithm audit of the political partisanship of Google Search snippets relative to the webpages they are extracted from. To accomplish this, we constructed lexicon of partisan cues to measure partisanship and construct a set of left- and right-leaning search queries. Then, we collected a large dataset of Search Engine Results Pages (SERPs) by running our partisan queries and their autocomplete suggestions on Google Search. After using our lexicon to score the machine-coded partisanship of snippets and webpages, we found that Google Search's snippets generally amplify partisanship, and that this effect is robust across different types of webpages, query topics, and partisan (left- and right-leaning) queries.
A sequential test for selecting the better variant: Online a/b testing, adaptive allocation, and continuous monitoring
Authors: Nianqiao Ju, Diane Hu, Adam Henderson, Liangjie Hong
Venue: Conference WSDM 2019
Year: 2019

Online A/B tests play an instrumental role for Internet companies to improve products and technologies in a data-driven manner. An online A/B test, in its most straightforward form, can be treated as a static hypothesis test where traditional statistical tools such as p-values and power analysis might be applied to help decision makers determine which variant performs better. However, a static A/B test presents both time cost and the opportunity cost for rapid product iterations. For time cost, a fast-paced product evolution pushes its shareholders to consistently monitor results from online A/B experiments, which usually invites peeking and altering experimental designs as data collected. It is recognized that this flexibility might harm statistical guarantees if not introduced in the right way, especially when online tests are considered as static hypothesis tests. For opportunity cost, a static test usually entails a static allocation of users into different variants, which prevents an immediate roll-out of the better version to larger audience or risks of alienating users who may suffer from a bad experience. While some works try to tackle these challenges, no prior method focuses on a holistic solution to both issues. In this paper, we propose a unified framework utilizing sequential analysis and multi-armed bandit to address time cost and the opportunity cost of static online tests simultaneously. In particular, we present an imputed sequential Girshick test that accommodates online data and dynamic allocation of data. The unobserved potential outcomes are treated as missing data and are imputed using empirical averages. Focusing on the binomial model, we demonstrate that the proposed imputed Girshick test achieves Type-I error and power control with both a fixed allocation ratio and an adaptive allocation such as Thompson Sampling through extensive experiments. In addition, we also run experiments on historical Etsy.com A/B tests to show the reduction in opportunity cost when using the proposed method.
Discovering models from structural and behavioral brain imaging data
Authors: Zilong Bai, Buyue Qian, Ian Davidson
Venue: Conference KDD 2018
Year: 2018

Block models of graphs are used in a wide variety of domains as they find not only clusters (the blocks) but also interaction within and between the blocks. However, existing approaches primarily focus on either structural graphs (i.e. for MRI scans) or behavioral graphs (i.e. for fMRI scans). In both cases the block model's interaction or mixing matrix can be useful for understanding potential interaction (for structural graphs) and actual interaction (for behavioral graphs) between the blocks. In this paper we explore finding block models where there is both a structural network and multiple behavioral graphs. This provides significant modeling challenges, consider if there is strong behavioral connectivity but no structural connectivity between two nodes. We show why existing multi-graph settings such as multi-view learning are insufficient and instead propose a novel model to address the problem. Our method not only learns structurally and behaviorally cohesive blocks of nodes but also finds structurally and behaviorally feasible block interactions. We show in numerical evaluations on synthetic data that our method outperforms baseline approaches in recovering the ground-truth factor matrices in increasingly complex situations. We further apply our method to real-world datasets from two different domains (1) brain imaging data (a multi-cohort fMRI study) and to show its versatility (2) Twitter (following network and retweet behavior) and gain insights into the information flow and underlying generating mechanisms of these complex data.
Surrogate maximization/minimization algorithms for adaboost and the logistic regression model
Authors: Zhihua Zhang 0004, James T. Kwok, Dit-Yan Yeung
Venue: Conference ICML 2004
Year: 2004

Surrogate maximization (or minimization) (SM) algorithms are a family of algorithm that can be regarded as a generalization of expectation-maximization (EM) algorithms. There are three major approaches to the construction of surrogate function, all relying on the convexity of some function. In this paper, we solve the boosting problem by proposing SM algorithms for the corresponding optimization problem. Specifically, for AdaBoost, we derive an SM algorithm that can be shown to be identical to the algorithm proposed by Collins et al. (2002) based on Bregman distance. More importantly, for LogitBoost (or logistic boosting), we use several methods to construct different surrogate functions which result in different SM algorithms. By combining multiple methods, we are able to derive an SM algorithm that is also the same as an algorithm derived by Collins et al. (2002). Our approach based on SM algorithms is much simpler and convergence results follow naturally.
Identifying facet mismatches in search via micrographs
Authors: Sriram Srinivasan, Nikhil S. Rao, Karthik Subbian, Lise Getoor
Venue: Conference CIKM 2019
Year: 2019

E-commerce search engines are the primary means by which customers shop for products online. Each customer query contains multiple facets such as product type, color, brand, etc. A successful search engine retrieves products that are relevant to the query along each of these attributes. However, due to lexical (erroneous title, description, etc.) and behavioral irregularities (clicks or purchases of products that do not belong to the same facet as the query), some mismatched products are often included in search results. These irregularities can be detected using simple binary classifiers like gradient boosted decision trees or logistic regression. Typically, these binary classifiers use strong independence assumptions between the results and ignore structural relationships available in the data, such as the connections between products and queries. In this paper, we use the connections that exist between products and query to identify a special kind of structure we refer to as a micrograph. Further, we make use of Statistical Relational Learning (SRL) to incorporate these micrographs in the data and pose the problem as a structured prediction problem. We refer to this approach as structured mismatch classification (\SMC). In addition, we show that naive addition of structure does not improve the performance of the model and hence introduce a variation of \SMC, strong \SMC~(\SSMC), which improves over the baseline by passing information from high-confidence predictions to lower confidence predictions. In our empirical evaluation we show that our proposed approach outperforms the baseline classification methods by up to 12% in precision. Furthermore, we use quasi-Newton methods to make our method viable for real-time inference in a search engine and show that our approach is up to 150 times faster than existing ADMM-based solvers.
Sustain: Scalable unsupervised scoring for tensors and its application to phenotyping
Authors: Ioakeim Perros, Evangelos E. Papalexakis, Haesun Park, Richard W. Vuduc, Xiaowei Yan, Christopher deFilippi, Walter F. Stewart, Jimeng Sun
Venue: Conference KDD 2018
Year: 2018

This paper presents a new method, which we call SUSTain, that extends real-valued matrix and tensor factorizations to data where values are integers. Such data are common when the values correspond to event counts or ordinal measures. The conventional approach is to treat integer data as real, and then apply real-valued factorizations. However, doing so fails to preserve important characteristics of the original data, thereby making it hard to interpret the results. Instead, our approach extracts factor values from integer datasets as scores that are constrained to take values from a small integer set. These scores are easy to interpret: a score of zero indicates no feature contribution and higher scores indicate distinct levels of feature importance. At its core, SUSTain relies on: a) a problem partitioning into integer-constrained subproblems, so that they can be optimally solved in an efficient manner; and b) organizing the order of the subproblems' solution, to promote reuse of shared intermediate results. We propose two variants, SUSTain_M and SUSTain_T, to handle both matrix and tensor inputs, respectively. We evaluate SUSTain against several state-of-the-art baselines on both synthetic and real Electronic Health Record (EHR) datasets. Comparing to those baselines, SUSTain shows either significantly better fit or orders of magnitude speedups that achieve a comparable fit (up to 425× faster). We apply SUSTain to EHR datasets to extract patient phenotypes (i.e., clinically meaningful patient clusters). Furthermore, 87% of them were validated as clinically meaningful phenotypes related to heart failure by a cardiologist.
Improving personalized services in mobile commerce by a novel multicriteria rating approach
Authors: Qiudan Li, Chunheng Wang, Guanggang Geng
Venue: Conference WWW 2008
Year: 2008

With the rapid growth of wireless technologies and mobile devices, there is a great demand for personalized services in m-commerce. Collaborative filtering (CF) is one of successful techniques to produce personalized recommendations for users. This paper proposes a novel approach to improve CF algorithms, where the contextual information of a user and the multicriteria ratings of an item are considered besides the typical information on users and items. The multilinear singular value decomposition (MSVD) technique is utilized to explore both explicit relations and implicit relations among user, item and criterion. We implement the approach in an existing m-commerce platform, and encouraging experimental results demonstrate its effectiveness.
Monitoring, Recognizing and Discovering Social Networks
Authors: Ting Yu 0003, Ser-Nam Lim, Kedar A. Patwardhan, Nils Krahnstoever
Venue: Conference CVPR 2009
Year: 2009

This work addresses the important problem of the discovery and analysis of social networks from surveillance video. A computer vision approach to this problem is made possible by the proliferation of video data obtained from camera networks, particularly state-of-the-art Pan-Tilt-Zoom (PTZ) and tracking camera systems that have the capability to acquire high-resolution face images as well as tracks of people under challenging conditions. We perform “opportunistic” face recognition on captured images and compute motion similarities between tracks of people on the ground plane. To deal with the unknown correspondences between faces and tracks, we present a novel graph-cut based algorithm to solve this association problem. It enables the robust estimation of a social network that captures the interactions between individuals in spite of large amounts of noise in the datasets. We also introduce an algorithm that we call “modularity-cut”, which is an Eigen-analysis based approach for discovering community and leadership structure in the estimated social network. Our approach is illustrated with promising results from a fully integrated multi-camera system under challenging conditions over long period of time.
Who controls the internet? analyzing global threats using property graph traversals
Authors: Milivoj Simeonovski, Giancarlo Pellegrino, Christian Rossow, Michael Backes
Venue: Conference WWW 2017
Year: 2017

The Internet is built on top of intertwined network services, e.g., email, DNS, and content distribution networks operated by private or governmental organizations. Recent events have shown that these organizations may, knowingly or unknowingly, be part of global-scale security incidents including state-sponsored mass surveillance programs and large-scale DDoS attacks. For example, in March 2015 the Great Cannon attack has shown that an Internet service provider can weaponize millions of Web browsers and turn them into DDoS bots by injecting malicious JavaScript code into transiting TCP connections.
Generating Liquid Simulations with Deformation-aware Neural Networks
Authors: Lukas Prantl, Boris Bonev, Nils Thuerey
Venue: Conference ICLR 2019
Year: 2019

We propose a novel approach for deformation-aware neural networks that learn the weighting and synthesis of dense volumetric deformation fields. Our method specifically targets the space-time representation of physical surfaces from liquid simulations. Liquids exhibit highly complex, non-linear behavior under changing simulation conditions such as different initial conditions. Our algorithm captures these complex phenomena in two stages: a first neural network computes a weighting function for a set of pre-computed deformations, while a second network directly generates a deformation field for refining the surface. Key for successful training runs in this setting is a suitable loss function that encodes the effect of the deformations, and a robust calculation of the corresponding gradients. To demonstrate the effectiveness of our approach, we showcase our method with several complex examples of flowing liquids with topology changes. Our representation makes it possible to rapidly generate the desired implicit surfaces. We have implemented a mobile application to demonstrate that real-time interactions with complex liquid effects are possible with our approach.