OpenRaiser/Intern-Atlas huggingface dataset:
To randomize or not to randomize: space optimal summaries for hyperlink analysis
Authors: Tamás Sarlós, András A. Benczúr, Károly Csalogány, Dániel Fogaras, Balázs Rácz
Venue: Conference WWW 2006
Year: 2006

Personalized PageRank expresses link-based page quality around user selected pages. The only previous personalized PageRank algorithm that can serve on-line queries for an unrestricted choice of pages on large graphs is our Monte Carlo algorithm [WAW 2004]. In this paper we achieve unrestricted personalization by combining rounding and randomized sketching techniques in the dynamic programming algorithm of Jeh and Widom [WWW 2003]. We evaluate the precision of approximation experimentally on large scale real-world data and find significant improvement over previous results. As a key theoretical contribution we show that our algorithms use an optimal amount of space by also improving earlier asymptotic worst-case lower bounds. Our lower bounds and algorithms apply to the SimRank as well; of independent interest is the reduction of the SimRank computation to personalized PageRank.
Improving social bookmark search using personalised latent variable language models
Authors: Morgan Harvey, Ian Ruthven, Mark James Carman
Venue: Conference WSDM 2011
Year: 2011

Social tagging systems have recently become very popular as a method of categorising information online and have been used to annotate a wide range of different resources. In such systems users are free to choose whatever keywords or "tags" they wish to annotate each resource, resulting in a highly personalised, unrestricted vocabulary. While this freedom of choice has several notable advantages, it does come at the cost of making searching of these systems more difficult as the vocabulary problem introduced is more pronounced than in a normal information retrieval setting. In this paper we propose to use hidden topic models as a principled way of reducing the dimensionality of this data to provide more accurate resource rankings with higher recall. We first describe Latent Dirichlet Allocation (LDA), a simple topic model and then introduce 2 extended models which can be used to personalise the results by including information about the user who made each annotation. We test these 3 models and compare them with 3 non-topic model baselines on a large data sample obtained from the Delicious social bookmarking site. Our evaluations show that our methods significantly outperform all of the baselines with the personalised models also improving significantly upon unpersonalised LDA.
A direct formulation for totally-corrective multi-class boosting
Authors: Chunhua Shen, Zhihui Hao
Venue: Conference CVPR 2011
Year: 2011

Boosting combines a set of moderately accurate weak classifiers to form a highly accurate predictor. Compared with binary boosting classification, multi-class boosting received less attention. We propose a novel multi-class boosting formulation here. Unlike most previous multi-class boosting algorithms which decompose a multi-boost problem into multiple independent binary boosting problems, we formulate a direct optimization method for training multi-class boosting. Moreover, by explicitly deriving the La-grange dual of the formulated primal optimization problem, we design totally-corrective boosting using the column generation technique in convex optimization. At each iteration, all weak classifiers' weights are updated. Our experiments on various data sets demonstrate that our direct multi-class boosting achieves competitive test accuracy compared with state-of-the-art multi-class boosting in the literature.
Segmentation by minimal description
Authors: Trevor Darrell, Stan Sclaroff, Alex Pentland
Venue: Conference ICCV 1990
Year: 1990

The authors formulate the segmentation task as a search for a set of descriptions which minimally encodes a scene. A novel framework for cooperative robust estimation is used to estimate descriptions that locally provide the most savings in encoding an image. A modified Hopfield-Tank networks finds the subset of these descriptions which best describes an entire scene, accounting for occlusion and transparent overlap among individual descriptions. Using a part-based 3-D shape model the authors have implemented a system that is able to successfully segment images into their constituent structure.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Discovering discriminative action parts from mid-level video representations
Authors: Michalis Raptis, Iasonas Kokkinos, Stefano Soatto
Venue: Conference CVPR 2012
Year: 2012

We describe a mid-level approach for action recognition. From an input video, we extract salient spatio-temporal structures by forming clusters of trajectories that serve as candidates for the parts of an action. The assembly of these clusters into an action class is governed by a graphical model that incorporates appearance and motion constraints for the individual parts and pairwise constraints for the spatio-temporal dependencies among them. During training, we estimate the model parameters discriminatively. During classification, we efficiently match the model to a video using discrete optimization. We validate the model's classification ability in standard benchmark datasets and illustrate its potential to support a fine-grained analysis that not only gives a label to a video, but also identifies and localizes its constituent parts.
Global diffusion via cascading invitations: Structure, growth, and homophily
Authors: Ashton Anderson, Daniel P. Huttenlocher, Jon M. Kleinberg, Jure Leskovec, Mitul Tiwari
Venue: Conference WWW 2015
Year: 2015

Many of the world's most popular websites catalyze their growth through invitations from existing members. New members can then in turn issue invitations, and so on, creating cascades of member signups that can spread on a global scale. Although these diffusive invitation processes are critical to the popularity and growth of many websites, they have rarely been studied, and their properties remain elusive. For instance, it is not known how viral these cascades structures are, how cascades grow over time, or how diffusive growth affects the resulting distribution of member characteristics present on the site. In this paper, we study the diffusion of LinkedIn, an online professional network comprising over 332 million members, a large fraction of whom joined the site as part of a signup cascade. First we analyze the structural patterns of these signup cascades, and find them to be qualitatively different from previously studied information diffusion cascades. We also examine how signup cascades grow over time, and observe that diffusion via invitations on LinkedIn occurs over much longer timescales than are typically associated with other types of online diffusion. Finally, we connect the cascade structures with rich individual-level attribute data to investigate the interplay between the two. Using novel techniques to study the role of homophily in diffusion, we find striking differences between the local, edge-wise homophily and the global, cascade-level homophily we observe in our data, suggesting that signup cascades form surprisingly coherent groups of members.
Item categorization in the e-commerce domain
Authors: Dan Shen, Jean-David Ruvini, Manas Somaiya, Neel Sundaresan
Venue: Conference CIKM 2011
Year: 2011

Hierarchical classification is a challenging problem yet bears a broad application in real-world tasks. Item categorization in the ecommerce domain is such an example. In a large-scale industrial setting such as eBay, a vast amount of items need to be categorized into a large number of leaf categories, on top of which a complex topic hierarchy is defined. Other than the scale challenges, item data is extremely sparse and skewed distributed over categories, and exhibits heterogeneous characteristics across categories. A common strategy for hierarchical classification is the "gates-and-experts" methods, where a high-level classification is made first (the gates), followed by a low-level distinction (the experts). In this paper, we propose to leverage domain-specific feature generation and modeling techniques to greatly enhance the classification accuracy of the experts. In particular, we innovatively derive features to encode various rich domain knowledge and linguistic hints, and then adapt a SVM-based model to distinguish several very confusing category groups appeared as the performance bottleneck of a currently deployed live system at eBay. We use illustrative examples and empirical results to demonstrate the effectiveness of our approach, particularly the merit of smartly designed domain-specific features.
People of opposing views can share common interests
Authors: Eduardo Graells-Garrido, Mounia Lalmas, Daniele Quercia
Venue: Conference WWW 2014
Year: 2014

In online social networks, people tend to connect with like-minded people and read agreeable information. Direct recommendation of challenging content has not worked well because users do not value diversity and avoid challenging content. In this poster, we investigate the possibility of an indirect approach by introducing intermediary topics, which are topics that are common to people having opposing views on sensitive issues, i.e., those issues that tend to divide people. Through a case study about a sensitive issue discussed in Twitter, we show that such intermediary topics exist, opening a path for future work in recommendation promoting diversity of content to be shared.
Privacy without noise
Authors: Yitao Duan
Venue: Conference CIKM 2009
Year: 2009

This paper presents several results on statistical database privacy. We first point out a serious vulnerability in a widely-accepted approach which perturbs query results with additive noise. We then show that for sum queries which aggregate across all records, when the dataset is sufficiently large, the inherent uncertainty associated with unknown quantities is enough to provide similar perturbation and the same privacy can be obtained without external noise. Sum query is a surprisingly general primitive supporting a large number of data mining algorithms such as SVD, PCA, k-means, ID3, SVM, EM, and all the algorithms in the statistical query model. We derive privacy conditions for sum queries and provide the first mathematical proof for the intuition that aggregates across a large number of individuals is private using a widely accepted notion of privacy. We also show how the results can be used to construct simulatable query auditing algorithms with stronger privacy.
Learning to cluster via same-cluster queries
Authors: Yi Li, Yan Song, Qin Zhang
Venue: Conference CIKM 2021
Year: 2021

We study the problem of learning to cluster data points using an oracle which can answer same-cluster queries. Different from previous approaches, we do not assume that the total number of clusters is known at the beginning and do not require that the true clusters are consistent with a predefined objective function such as the K-means. These relaxations are critical from the practical perspective and, meanwhile, make the problem more challenging. We propose two algorithms with provable theoretical guarantees and verify their effectiveness via an extensive set of experiments on both synthetic and real-world data.
Graph summarization with controlled utility loss
Authors: Mahdi Hajiabadi, Jasbir Singh, Venkatesh Srinivasan, Alex Thomo
Venue: Conference KDD 2021
Year: 2021

We present new algorithms for graph summarization where the loss in utility is fully controllable by the user. Specifically, we make three key contributions. First, we present a utility-driven graph summarization method G-SCIS, based on a clique and independent set decomposition, that produces optimal compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Second, we propose a highly scalable, utility-driven algorithm, T-BUDS, for fully controlled lossy summarization. It achieves high scalability by combining memory reduction using Maximum Spanning Tree with a novel binary search procedure. T-BUDS outperforms state-of-the-art drastically in terms of the quality of summarization and is about two orders of magnitude better in terms of speed. In contrast to the competition, we are able to handle web-scale graphs in a single machine without performance impediment as the utility threshold (and size of summary) decreases. Third, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank and shortest paths.
Graph matching through entropic manifold alignment
Authors: Francisco Escolano, Edwin R. Hancock, Miguel Angel Lozano
Venue: Conference CVPR 2011
Year: 2011

In this paper we cast the problem of graph matching as one of non-rigid manifold alignment. The low dimensional manifolds are from the commute time embedding and are matched though coherent point drift. Although there have been a number of attempts to realise graph matching in this way, in this paper we propose a novel information-theoretic measure of alignment, the so-called symmetrized normalized-entropy-square variation. We successfully test this dissimilarity measure between manifolds on a a challenging database. The measure is estimated by means of the bypass Leonenko entropy functional. In addition we prove that the proposed measure induces a positive definite kernel between the probability density functions associated with the manifolds and hence between graphs after deformation. In our experiments we find that the optimal embedding is associated to the commute time distance and we also find that our approach, which is purely topological, outperforms several state-of-the-art graph-based algorithms for point matching.
Recstudio: Towards a highly-modularized recommender system
Authors: Defu Lian, Xu Huang, Xiaolong Chen, Jin Chen, Xingmei Wang, Yankai Wang, Haoran Jin, Rui Fan, Zheng Liu, Le Wu, Enhong Chen
Venue: Conference SIGIR 2023
Year: 2023

A dozen recommendation libraries have recently been developed to accommodate popular recommendation algorithms for reproducibility. However, they are almost simply a collection of algorithms, overlooking the modularization of recommendation algorithms and their usage in practical scenarios. Algorithmic modularization has the following advantages: 1) helps to understand the effectiveness of each algorithm; 2) easily assembles new algorithms with well-performed modules by either drag-and-drop programming or automatic machine learning; 3) enables reinforcement between algorithms since one algorithm may act as a module of another algorithm. To this end, we develop a highly-modularized recommender system -- RecStudio, in which any recommendation algorithm is categorized into either a ranker or a retriever. In the RecStudio library, we implement 90 recommendation algorithms with the pure Pytorch, covering both common algorithms in other libraries and complex algorithms involving multiple recommendation models. RecStudio is featured from several perspectives, such as index-supported efficient recommendation and evaluation, GPU-accelerated negative sampling, hyperparameter learning on the validation, and cooperation between the retriever and ranker. RecStudio is also equipped with a web service, where the recommendation pipeline can be quickly established and visually evaluated on selected datasets, and the evaluation results are automatically archived and visualized in a leaderboard. The project and documents are released at http://recstudio.org.cn.
Efficient optimization methods for extreme similarity learning with nonlinear embeddings
Authors: Bo-Wen Yuan, Yu-Sheng Li, Pengrui Quan, Chih-Jen Lin
Venue: Conference KDD 2021
Year: 2021

We study the problem of learning similarity by using nonlinear embedding models (e.g., neural networks) from all possible pairs. This problem is well-known for its difficulty of training with the extreme number of pairs. For the special case of using linear embeddings, many studies have addressed this issue of handling all pairs by considering certain loss functions and developing efficient optimization algorithms. This paper aims to extend results for general nonlinear embeddings. First, we finish detailed derivations and provide clean formulations for efficiently calculating some building blocks of optimization algorithms such as function, gradient evaluation, and Hessian-vector product. The result enables the use of many optimization methods for extreme similarity learning with nonlinear embeddings. Second, we study some optimization methods in detail. Due to the use of nonlinear embeddings, implementation issues different from linear cases are addressed. In the end, some methods are shown to be highly efficient for extreme similarity learning with nonlinear embeddings.
Unified question generation with continual lifelong learning
Authors: Wei Yuan, Hongzhi Yin, Tieke He, Tong Chen, Qiufeng Wang, Lizhen Cui
Venue: Conference WWW 2022
Year: 2022

Question Generation (QG), as a challenging Natural Language Processing task, aims at generating questions based on given answers and context. Existing QG methods mainly focus on building or training models for specific QG datasets. These works are subject to two major limitations: (1) They are dedicated to specific QG formats (e.g., answer-extraction or multi-choice QG), therefore, if we want to address a new format of QG, a re-design of the QG model is required. (2) Optimal performance is only achieved on the dataset they were just trained on. As a result, we have to train and keep various QG models for different QG datasets, which is resource-intensive and ungeneralizable. To solve the problems, we propose a model named Unified-QG based on lifelong learning techniques, which can continually learn QG tasks across different datasets and formats. Specifically, we first build a format-convert encoding to transform different kinds of QG formats into a unified representation. Then, a method named \emph{STRIDER} (\emph{S}imilari\emph{T}y \emph{R}egular\emph{I}zed \emph{D}ifficult \emph{E}xample \emph{R}eplay) is built to alleviate catastrophic forgetting in continual QG learning. Extensive experiments were conducted on $8$ QG datasets across $4$ QG formats (answer-extraction, answer-abstraction, multi-choice, and boolean QG) to demonstrate the effectiveness of our approach. Experimental results demonstrate that our Unified-QG can effectively and continually adapt to QG tasks when datasets and formats vary. In addition, we verify the ability of a single trained Unified-QG model in improving $8$ Question Answering (QA) systems' performance through generating synthetic QA data.
A multi-modality framework for drug-drug interaction prediction by harnessing multi-source data
Authors: Qianlong Wen, Jiazheng Li, Chuxu Zhang, Yanfang Ye
Venue: Conference CIKM 2023
Year: 2023

Drug-drug interaction (DDI), as a possible result of drug combination treatment, could lead to adverse physiological reactions and increasing mortality rates of patients. Therefore, predicting potential DDI has always been an important and challenging issue in medical health applications. Owing to the extensive pharmacological research, we can get access to various drug-related features for DDI predictions; however, most of the existing works on DDI prediction do not incorporate comprehensive features to analyze the DDI patterns. Despite the high performance that the existing works have achieved, the incomplete and noisy information generated from limited sources usually leads to sub-optimal performance and poor generalization ability on the unknown DDI pairs. In this work, we propose a holistic framework, namely Multi-modality Feature Optimal Fusion for Drug-Drug Interaction Prediction (MOF-DDI), that incorporates the features from multiple data sources to resolve the DDI predictions. Specifically, the proposed model jointly considers DDIs literature descriptions, biomedical knowledge graphs, and drug molecular structures to make the prediction. To overcome the issue induced by directly aggregating features in different modalities, we bring a new insight by mapping the representations learned from different sources to a unified hidden space before the combination. The empirical results show that MOF-DDI achieves a large performance gain on different DDI datasets compared with multiple state-of-the-art baselines, especially under the inductive setting.
Felicitas: Federated learning in distributed cross device collaborative frameworks
Authors: Qi Zhang, Tiancheng Wu, Peichen Zhou, Shan Zhou, Yuan Yang, Xiulang Jin
Venue: Conference KDD 2022
Year: 2022

Felicitas is a distributed cross-device Federated Learning (FL) framework to solve the industrial difficulties of FL in large-scale device deployment scenarios. In Felicitas, FL-Clients are deployed on mobile or embedded devices, while FL-Server is deployed on the cloud platform. We also summarize the challenges of FL deployment in industrial cross-device scenarios (massively parallel, stateless clients, non-use of client identifiers, highly unreliable, unsteady and complex deployment), and provide reliable solutions. We provide the source code and documents at https://www.mindspore.cn/. In addition, the Felicitas has been deployed on mobile phones in real world. At the end of the paper, we demonstrate the validity of the framework through experiments.
An empirical study of real-world webassembly binaries: Security, languages, use cases
Authors: Aaron Hilbig, Daniel Lehmann, Michael Pradel
Venue: Conference WWW 2021
Year: 2021

WebAssembly has emerged as a low-level language for the web and beyond. Despite its popularity in different domains, little is known about WebAssembly binaries that occur in the wild. This paper presents a comprehensive empirical study of 8,461 unique WebAssembly binaries gathered from a wide range of sources, including source code repositories, package managers, and live websites. We study the security properties, source languages, and use cases of the binaries and how they influence the security of the WebAssembly ecosystem. Our findings update some previously held assumptions about real-world WebAssembly and highlight problems that call for future research. For example, we show that vulnerabilities that propagate from insecure source languages potentially affect a wide range of binaries (e.g., two thirds of the binaries are compiled from memory unsafe languages, such as C and C++) and that 21% of all binaries import potentially dangerous APIs from their host environment. We also show that cryptomining, which once accounted for the majority of all WebAssembly code, has been marginalized (less than 1% of all binaries found on the web) and gives way to a diverse set of use cases. Finally, 29% of all binaries on the web are minified, calling for techniques to decompile and reverse engineer WebAssembly. Overall, our results show that WebAssembly has left its infancy and is growing up into a language that powers a diverse ecosystem, with new challenges and opportunities for security researchers and practitioners. Besides these insights, we also share the dataset underlying our study, which is 58 times larger than the largest previously reported benchmark.
Autobidding auctions in the presence of user costs
Authors: Yuan Deng, Jieming Mao, Vahab Mirrokni, Hanrui Zhang, Song Zuo
Venue: Conference WWW 2023
Year: 2023

We study autobidding ad auctions with user costs, where each bidder is value-maximizing subject to a return-over-investment (ROI) constraint, and the seller aims to maximize the social welfare taking into consideration the user’s cost of viewing an ad. We show that in the worst case, the approximation ratio of social welfare by running the vanilla VCG auctions with user costs could as bad as 0. To improve the performance of VCG, We propose a new variant of VCG based on properly chosen cost multipliers, and prove that there exist auction-dependent and bidder-dependent cost multipliers that guarantee approximation ratios of 1/2 and 1/4 respectively in terms of the social welfare.