As AI and web agents become pervasive in decision-making, it is critical to design intelligent systems that not only support sustainability efforts but also guard against misinformation. Greenwashing, i.e., misleading corporate sustainability claims, poses a major challenge to environmental progress. To address this challenge, we introduce EmeraldMind, a fact-centric framework integrating a domain-specific knowledge graph with retrieval-augmented generation to automate greenwashing detection. EmeraldMind builds the EmeraldGraph from diverse corporate ESG (environmental, social, and governance) reports, surfacing verifiable evidence, often missing in generic knowledge bases, and supporting large language models in claim assessment. The framework delivers justification-centric classifications, presenting transparent, evidence-backed verdicts and abstaining responsibly when claims cannot be verified. Experiments on a new greenwashing claims dataset demonstrate that EmeraldMind achieves competitive accuracy, greater coverage, and superior explanation quality compared to generic LLMs, without the need for fine-tuning or retraining.

Detecting meaningful communities in networks is essential for understanding complex social, biological, and information systems. Modularity effectively captures the quality of communities by comparing the observed and expected edge densities, but it often overlooks fairness with regards to the connectivity of different groups of nodes within the communities. In this work, we address this limitation by proposing fairness-aware community detection algorithms that incorporate group-sensitive connectivity into the modularity framework. Our approach is based on optimizing distinct sub-matrices of the modularity matrix that isolate intra-group and inter-group connections. We introduce two algorithmic families: (a) Input-based methods, including fair spectral and deep learning algorithms that directly operate on these sub-matrices; and (b) Loss-based methods, which integrate fairness-aware sub-matrix information into the learning objective of deep community detection models. Our experiments on synthetic and real-world networks demonstrate that our algorithms significantly improve group connectivity fairness without compromising community quality.

Communities in networks are groups of nodes that are more densely connected to each other than to the rest of the network, forming clusters with strong internal relationships. When nodes have sensitive attributes, such as demographic groups in social networks, a key question is whether nodes in each group are equally well-connected within each community. We model connectivity fairness using group modularity, an adaptation of modularity that accounts for group structures. We introduce two versions of group modularity, each grounded on a different null model, and propose fairness-aware community detection algorithms. Finally, we provide experimental results on real and synthetic networks, evaluating both the connectivity fairness of community structures in networks and the performance of our fairness-aware algorithms.

Abstract CounterFair is a group counterfactual search algorithm that detects and minimizes biases among sensitive groups and identifies relevant subgroups inside these sensitive groups based on shared counterfactual instances. We investigate the latter capability, analyzing the found subgroups from the perspective of fairness based on counterfactual reasoning, in order to evaluate whether they present different biases with respect to each other and to the sensitive feature groups they belong to. We perform these measurements on the subgroups extracted by CounterFair over six binary classification datasets, providing figures and their respective analysis on the presence of bias.

No abstract available.

Counterfactual explanations can be used as a means to explain a models decision process and to provide recommendations to users on how to improve their current status. The difficulty to apply these counterfactual recommendations from the users perspective, also known as burden, may be used to assess the models algorithmic fairness and to provide fair recommendations among different sensitive feature groups. We propose a novel model-agnostic, mathematical programming-based, group counterfactual algorithm that can: (1) detect biases via group counterfactual burden, (2) produce fair recommendations among sensitive groups and (3) identify relevant subgroups of instances through shared counterfactuals. We analyze these capabilities from the perspective of recourse fairness, and empirically compare our proposed method with the state-of-the-art algorithms for group counterfactual generation in order to assess the bias identification and the capabilities in group counterfactual effectiveness and burden minimization.

Integrity 2024 is the fifth edition of the Workshop on Integrity in Social Networks and Media, held in conjunction with the ACM Conference on Web Search and Data Mining (WSDM) since the 2020 edition [1-4]. The goal of the workshop is to bring together academic and industry researchers working on integrity, fairness, trust and safety in social networks to discuss the most pressing risks and cutting-edge technologies to reliably measure and mitigate them. The event consists of invited talks from academic experts and industry leaders as well as peer-reviewed papers and posters through an open call-for-papers.

Integrity 2023 is the fourth edition of the successful Workshop on Integrity in Social Networks and Media, held in conjunction with the ACM Conference on Web Search and Data Mining (WSDM) in the past three years. The goal of the workshop is to bring together researchers and practitioners to discuss content and interaction integrity challenges in social networks and social media platforms. The event consists of a combination of invited talks by reputed members of the Integrity community from both academia and industry and peer-reviewed contributed talks and posters solicited via an open call-for-papers.

Network algorithms play a critical role in various applications, such as recommendations, diffusion maximization, and web search. In this paper, we focus on the fairness of such algorithms and in particular of PageRank. PageRank fairness refers to a fair allocation of the PageRank weights among the nodes. We consider the effect of the network structure on PageRank fairness. Concretely, we provide analytical formulas for computing the effect of edge additions on fairness and for the conditions that an edge must satisfy so that its addition improves fairness. We also provide analytical formulas for evaluating the role of existing edges in fairness. We use our findings to propose efficient linear time link recommendation algorithms for maximizing fairness, and we evaluate them on real datasets. Our approach can be seen as an effort towards making the network itself fairer as opposed to making fairer the network algorithms, or their outputs.

Temporal interaction networks capture the history of activities between entities along a timeline. At each interaction, some quantity of data (money, information, traffic) flows from one vertex of the network to another. Flow-based analysis can reveal important information, such as unusually large money transfers in a part of a financial transaction network. In this paper, we introduce the flow computation problem between two vertrices in an interaction network. We propose and study two models of flow computation, one based on a greedy flow transfer assumption and one that finds the maximum possible flow. We show that the greedy flow computation problem can be easily solved by a single scan of the interactions in time order. For the harder maximum flow problem, we propose precomputation and simplification approaches that can greatly reduce its complexity in practice. We also approach the problem of flow pattern enumeration in interaction networks and propose an effective path indexing technique. We evaluate our algorithms using real datasets. The results demonstrate the efficiency and scalability of our algorithms.

Algorithmic fairness has attracted significant attention in the past years. In this paper, we consider fairness for link analysis and in particular for the celebrated Pagerank algorithm. Given that the nodes in a network belong to groups (for example, based on demographic or other characteristics), we provide a parity-based definition of fairness that imposes constraints on the proportion of Pagerank allocated to the members of each group. We propose two families of fair Pagerank algorithms: the first (Fairness-Sensitive Pagerank) modifies the jump vector of the Pagerank algorithm to enforce fairness; the second (Locally Fair Pagerank) imposes a fair behavior per node. We then define a stronger fairness requirement, termed universal personalized fairness, that asks that the derived personalized pageranks of all nodes are fair. We prove that the locally fair algorithms achieve also universal personalized fairness, and furthermore, we prove that this is the only family of algorithms with this property, establishing an equivalence between universal personalized fairness and local fairness. We also consider the problem of achieving fairness while minimizing the utility loss with respect to the original Pagerank algorithm. We present experiments with real and synthetic networks that examine the fairness of the original Pagerank and demonstrate qualitatively and quantitatively the properties of our algorithms.

The team-formation problem on social networks asks for a team of individuals that collectively possess the skills to perform a task and have low communication cost, as measured by their distances in the social network. Most related work assumes a flat structure in the team, where team members are all indistinguishable. However, in practice, teams often have complex structures and deep hierarchies, and members with distinct roles in these structures. In this paper, we consider the Template-Driven Team Formation problem, where given a fixed template structure for the team, in the form of a graph, and a designated role for each node in the template, we ask for workers that can fill the roles in the template, while minimizing the communication cost along the template edges. Although the problem is in general NP-hard, there are variants of the problem that can be solved optimally using dynamic programming. For the general case, we provide approximation and heuristic polynomial-time algorithms. We experiment on real data and we demonstrate that our heuristic algorithms perform well in practice while being significantly more efficient. Our case studies highlight the quality of the teams produced by our algorithms.

Teams that bring together experts with different expertise are important for solving complex problems. However, research shows that teaming up people simply based on their ability is not enough. Team members need to have clear roles, and they should mutually endorse and respect their teammates for the role they assume on the team. In this paper, we define the MaxMutualRespect problem, a novel team-formation problem that asks for a set of experts, each assigned to a distinct role, such that the total respect that the individuals receive by the rest of the team members for their assigned role is maximized. We show that the problem is NP-complete and we consider approximation and heuristic algorithms. Experiments with real datasets demonstrate that our problem definitions and algorithms work well in practice and yield intuitive results.

The first Workshop on Integrity in Social Networks and Media is held in conjunction with the 13th ACM Conference on Web Search and Data Mining (WSDM) in Houston, Texas, USA. The goal of the workshop is to bring together researchers and practitioners to discuss content and interaction integrity challenges in social networks and social media platforms.

Traditional recommender systems aim to satisfy individual users by providing them with recommendations that match their preferences. Such recommender systems don't take into consideration how the number of users recommended to use a particular item affects the users' experience. For example, a highly-recommended restaurant may match the preferences of many users. However, increasing its popularity via recommendations may make the experience unsatisfactory due to high volume of customers, long lines and inevitably slow service. In this paper, we develop a new recommendation-system paradigm that we call collective recommendations. Collective recommendations take into consideration not only the user preferences, but also the effect of the popularity of a venue to the overall user experience. We formally define the algorithmic problems motivated by collective recommendations and develop an algorithmic framework for solving them effectively. Our experiments with real data demonstrate the effectiveness of our methods in practice. Nobody goes there any more. It's too crowded — Yogi Berra

Recommending packages of items to groups of users has several applications, including recommending vacation packages to groups of tourists, entertainment packages to groups of friends, or sets of courses to groups of students. In this paper, we focus on a novel aspect of package-to-group recommendations, that of fairness. Specifically, when we recommend a package to a group of people, we ask that this recommendation is fair in the sense that every group member is satisfied by a sufficient number of items in the package. We explore two definitions of fairness and show that for either definition the problem of finding the most fair package is NP-hard. We exploit the fact that our problem can be modeled as a coverage problem, and we propose greedy algorithms that find approximate solutions within reasonable time. In addition, we study two extensions of the problem, where we impose category or spatial constraints on the items to be included in the recommended packages. We evaluate the appropriateness of the fairness models and the performance of the proposed algorithms using real data from Yelp, and a user study.

In this paper we study the temporal evolution of review ratings. We observe that on average ratings tend to become more polarized over time. To explain this phenomenon we propose a simple model that captures the tendency of users for rating manipulation. Simulations with our model demonstrate that it is successful in capturing the aggregate behavior of the users.

Trolling describes a range of antisocial online behaviors that aim at disrupting the normal operation of online social networks and media. Combating trolling is an important problem in the online world. Existing approaches rely on human-based or automatic mechanisms for identifying trolls and troll posts. In this paper we take a novel approach to the trolling problem: our goal is to identify the targets of the trolls, so as to prevent trolling before it happens. We thus define the troll vulnerability prediction problem, where given a post we aim at predicting whether it is vulnerable to trolling. Towards this end, we define a novel troll vulnerability metric of how likely a post is to be attacked by trolls, and we construct models for predicting troll-vulnerable posts, using features from the content and the history of the post. Our experiments with real data from Reddit demonstrate that our approach is successful in recalling a large fraction of the troll-vulnerable posts.

The success of recommender systems has made them the focus of a massive research effort in both industry and academia. Recent work has generalized recommendations to suggest packages of items to single users, or single items to groups of users. However, to the best of our knowledge, the interesting problem of recommending a package to a group of users (P2G) has not been studied to date. This is a problem with several practical applications, such as recommending vacation packages to tourist groups, entertainment packages to groups of friends, or sets of courses to groups of students. In this paper, we formulate the P2G problem, and we propose probabilistic models that capture the preference of a group towards a package, incorporating factors such as user impact and package viability. We also investigate the issue of recommendation fairness. This is a novel consideration that arises in our setting, where we require that no user is consistently slighted by the item selection in the package. We present aggregation algorithms for finding the best packages and compare our suggested models with baseline approaches stemming from previous work. The results show that our models find packages of high quality which consider all special requirements of P2G recommendation.

Link recommendations are critical for both improving the utility and expediting the growth of social networks. Most previous approaches focus on suggesting links that are highly likely to be adopted. In this paper, we add a different perspective to the problem by aiming at recommending links that also improve specific properties of the network. In particular, our goal is to recommend to users links that if adopted would improve their centrality in the network. Specifically, we introduce the centrality-aware link recommendation problem as the problem of recommending to a user u, k links from a pool of recommended links so as to maximize the expected decrease of the sum of the shortest path distances of $u$ to all other nodes in the network. We show that the problem is NP-hard, but our optimization function is monotone and sub-modular which guarantees a constant approximation ratio for the greedy algorithm. We present a fast algorithm for computing the expected decrease caused by a set of recommendations which we use as a building block in our algorithms. We provide experimental results that evaluate the performance of our algorithms with respect to both the accuracy of the prediction and the improvement in the centrality of the nodes, and we study the tradeoff between the two.

In this paper, we consider large graphs that evolve over time, such as graphs that model social networks. Given two instances of the graph at two points in time, we ask to identify the top pairs of nodes whose shortest path dis-tance has decreased the most. We call these pairs converg-ing. The straightforward way to address this problem is by computing the shortest path distances of all pairs at both instances and keeping the ones with the largest differences. Since for large networks this is computationally infeasible, we consider a budgeted version of the problem, where given a fixed budget of single-source shortest path computations, we seek to identify nodes that participate in as many con-verging pairs as possible. We evaluate a number of different approaches for our problem, that employ centrality-based, dispersion-based, and landmark-based distance estimation metrics. We also consider a classification-based approach that builds a classifier that combines the above features for predicting whether a node participates in one of the top con-verging pairs. We present experimental results using real-world datasets that show that we are able to identify the large majority of the top converging pairs on a very small budget.

The small world phenomenon is a desirable property of social networks, since it guarantees short paths between the nodes of the social graph and thus efficient information spread on the network. It is thus in the benefit of both network users and network owners to enforce and maintain this property. In this work, we study the problem of finding a subset of k edges from a set of candidate edges whose addition to a network leads to the greatest reduction in its average shortest path length. We formulate the problem as a combinatorial optimization problem, and show that it is NP-hard and that known approximation techniques are not applicable. We describe an efficient method for computing the exact effect of a single edge insertion on the average shortest path length, as well as several heuristics for efficiently estimating this effect. We perform experiments on real data to study the performance of our algorithms in practice.

Micro-reviews is a new type of user-generated content arising from the prevalence of mobile devices and social media in the past few years. Micro-reviews are bite-size reviews (usually under 200 characters), commonly posted on social media or check-in services, using a mobile device. They capture the immediate reaction of users, and they are rich in information, concise, and to the point. However, the abundance of micro-reviews, and their telegraphic nature make it increasingly difficult to go through them and extract the useful information, especially on a mobile device. In this paper, we address the problem of summarizing the micro-reviews of an entity, such that the summary is representative, compact, and readable. We formulate the summarization problem as that of synthesizing a new ``review'' using snippets of full-text reviews. To produce a summary that naturally balances compactness and representativeness, we work within the Minimum Description Length framework. We show that finding the optimal summary is NP-hard, and we consider approximation and heuristic algorithms. We perform a thorough evaluation of our methodology on real-life data collected from Foursquare and Yelp. We demonstrate that our summaries outperform individual reviews, as well as existing summarization approaches.

Given the proliferation of review content, and the fact that reviews are highly diverse and often unnecessarily verbose, users frequently face the problem of selecting the appropriate reviews to consume. Micro-reviews are emerging as a new type of online review content in the social media. Micro-reviews are posted by users of check-in services such as Foursquare. They are concise (up to 200 characters long) and highly focused, in contrast to the comprehensive and verbose reviews. In this paper, we propose a novel mining problem, which brings together these two disparate sources of review content. Specifically, we use coverage of micro-reviews as an objective for selecting a set of reviews that cover efficiently the salient aspects of an entity. Our approach consists of a two-step process: matching review sentences to micro-reviews, and selecting a small set of reviews that cover as many micro-reviews as possible, with few sentences. We formulate this objective as a combinatorial optimization problem, and show how to derive an optimal solution using Integer Linear Programming. We also propose an efficient heuristic algorithm that approximates the optimal solution. Finally, we perform a detailed evaluation of all the steps of our methodology using data collected from Foursquare and Yelp.

In online labor marketplaces employers post job openings and re-ceive applications by workers interested in them. The employers decide which applicant to hire and then they work with the selected worker to accomplish the job requirements. At the end of the con-tract, an employer can provide his worker with some rating that becomes visible in the online worker profile and can guide future hiring decisions of other employers. In this paper, we discuss some of the shortcomings of the existing reputation system and we pro-pose a new reputation mechanism that combines employer implicit feedback signals in a link-analysis-based approach. The new sys-tem addresses the shortcomings of the existing one while yielding similar or better signal for the worker quality. 1.

In the past few years there has been an explosion of social networks in the online world. Users flock these networks, creating profiles and linking themselves to other individuals. Connecting online has a small cost compared to the physical world, leading to a proliferation of connections, many of which carry little value or importance. Understanding the strength and nature of these relationships is paramount to anyone interesting in making use of the online social network data. In this paper, we use the principle of Strong Triadic Closure to characterize the strength of relationships in social networks. The Strong Triadic Closure principle stipulates that it is not possible for two individuals to have a strong relationship with a common friend and not know each other. We consider the problem of labeling the ties of a social network as strong or weak so as to enforce the Strong Triadic Closure property. We formulate the problem as a novel combinatorial optimization problem, and we study it theoretically. Although the problem is NP-hard, we are able to identify cases where there exist efficient algorithms with provable approximation guarantees. We perform experiments on real data, and we show that there is a correlation between the labeling we obtain and empirical metrics of tie strength, and that weak edges act as bridges between different communities in the network. Finally, we study extensions and variations of our problem both theoretically and experimentally.

Link structure in online networks carries varying semantics. For example, Facebook links carry social semantics while LinkedIn links carry professional semantics. It has been shown that online networks are useful for predicting users' future activities. In this paper, we introduce a new related problem: given a collection of networks, how can we determine the relative importance of each network for predicting user activities? We propose a framework that allows us to quantify the relative predictive value of each network in a setting where multiple networks are available. We give an ɛ-net algorithm to solve the problem and prove that it finds a solution that is arbitrarily close to the optimal solution. Experimentally, we focus our study on the prediction of ad clicks, where it is already known that a single social network improves prediction. The networks we study are implicit affiliations networks, which are based on users' browsing history rather than declared relationships between the users. We create two networks based on covisitation to pages in the Facebook domain and Wikipedia domain. The learned relative weighting of these networks demonstrates covisitation networks are indeed useful for prediction, but that no single network is predictive of all kinds of ads. Rather, each category of ads calls for a significantly different weighting of these networks.

Online reviews are an invaluable resource for web users trying to make decisions regarding products or services. However, the abundance of review content, as well as the unstructured, lengthy, and verbose nature of reviews make it hard for users to locate the appropriate reviews, and distill the useful information. With the recent growth of social networking and micro-blogging services, we observe the emergence of a new type of online review content, consisting of bite-sized, 140 character-long reviews often posted reactively on the spot via mobile devices. These micro-reviews are short, concise, and focused, nicely complementing the lengthy, elaborate, and verbose nature of full-text reviews.

The process of opinion formation through synthesis and contrast of different viewpoints has been the subject of many studies in economics and social sciences. Today, this process manifests itself also in online social networks and social media. The key characteristic of successful promotion campaigns is that they take into consideration such opinion-formation dynamics in order to create a overall favorable opinion about a specific information item, such as a person, a product, or an idea. In this paper, we adopt a well-established model for social-opinion dynamics and formalize the campaigndesign problem as the problem of identifying a set of target individuals whose positive opinion about an information item will maximize the overall positive opinion for the item in the social network. We call this problem CAMPAIGN. We study the complexity of the CAMPAIGN problem, and design algorithms for solving it. Our experiments on real data demonstrate the efficiency and practical utility of our algorithms.

A fundamental data integration task faced by online commercial portals and commerce search engines is the integration of products coming from multiple providers to their product catalogs. In this scenario, the commercial portal has its own taxonomy (the “master taxonomy”), while each data provider organizes its products into a different taxonomy (the “provider taxonomy”). In this paper, we consider the problem of categorizing products from the data providers into the master taxonomy, while making use of the provider taxonomy information. Our approach is based on a taxonomy-aware processing step that adjusts the results of a text-based classifier to ensure that products that are close together in the provider taxonomy remain close in the master taxonomy. We formulate this intuition as a structured prediction optimization problem. To the best of our knowledge, this is the first approach that leverages the structure of taxonomies in order to enhance catalog integration. We propose algorithms that are scalable and thus applicable to the large data sets that are typical on the web. We evaluate our algorithms on real-world data and we show that taxonomy-aware classification provides a significant improvement over existing approaches.

Advertisers typically have a fairly accurate idea of the interests of their target audience. However, today's online advertising systems are unable to leverage this information. The reasons are two-fold. First, there is no agreed upon vocabulary of interests for advertisers and advertising systems to communicate. More importantly, advertising systems lack a mechanism for mapping users to the interest vocabulary.

Online user reviews play a central role in the decision-making process of users for a variety of tasks, ranging from entertainment and shopping to medical services. As user-generated reviews proliferate, it becomes critical to have a mechanism for helping the users (information consumers) deal with the information overload, and presenting them with a small comprehensive set of reviews that satisfies their information need. This is particularly important for mobile phone users, who need to make decisions quickly, and have a device with limited screen real-estate for displaying the reviews. Previous approaches have addressed the problem by ranking reviews according to their (estimated) helpfulness. However, such approaches do not account for the fact that the top few high-quality reviews may be highly redundant, repeating the same information, or presenting the same positive (or negative) perspective. In this work, we focus on the problem of selecting a comprehensive set of few high-quality reviews that cover many different aspects of the reviewed item. We formulate the problem as a maximum coverage problem, and we present a generic formalism that can model the different variants of review-set selection. We describe algorithms for the different variants we consider, and, whenever possible, we provide approximation guarantees with respect to the optimal solution. We also perform an experimental evaluation on real data in order to understand the value of coverage for users.

In recent years, there has been a strong trend of incorporating results from structured data sources into keyword-based web search systems such as Bing or Amazon. When presenting structured data, facets are a powerful tool for navigating, refining, and grouping the results. For a given structured data source, a fundamental problem in supporting faceted search is finding an ordered selection of attributes and values that will populate the facets. This creates two sets of challenges. First, because of the limited screen real-estate, it is important that the top facets best match the anticipated user intent. Second, the huge scale of available data to such engines demands an automated unsupervised solution.

Queries asked on web search engines often target structured data, such as commercial products, movie showtimes, or airline schedules. However, surfacing relevant results from such data is a highly challenging problem, due to the unstructured language of the web queries, and the imposing scalability and speed requirements of web search. In this paper, we discover latent structured semantics in web queries and produce Structured Annotations for them. We consider an annotation as a mapping of a query to a table of structured data and attributes of this table. Given a collection of structured tables, we present a fast and scalable tagging mechanism for obtaining all possible annotations of a query over these tables. However, we observe that for a given query only few are sensible for the user needs. We thus propose a principled probabilistic scoring mechanism, using a generative model, for assessing the likelihood of a structured annotation, and we define a dynamic threshold for filtering out misinterpreted query annotations. Our techniques are completely unsupervised, obviating the need for costly manual labeling effort. We evaluated our techniques using real world queries and data and present promising experimental results.

Online reviews in which users publish detailed commentary about their experiences and opinions with products, services, or events are extremely valuable to users who rely on them to make informed decisions. However, reviews vary greatly in quality and are con-stantly increasing in number, therefore, automatic assessment of review helpfulness is of growing importance. Previous work has addressed the problem by treating a review as a stand-alone docu-ment, extracting features from the review text, and learning a func-tion based on these features for predicting the review quality. In this work, we exploit contextual information about authors ’ iden-tities and social networks for improving review quality prediction. We propose a generic framework for incorporating social context information by adding regularization constraints to the text-based predictor. Our approach can effectively use the social context infor-mation available for large quantities of unlabeled reviews. It also has the advantage that the resulting predictor is usable even when social context is unavailable. We validate our framework within a real commerce portal and experimentally demonstrate that using social context information can help improve the accuracy of re-view quality prediction especially when the available training data is sparse.

Classification is a core task in knowledge discovery and data mining, and there has been substantial research effort in developing sophisticated classification models. In a parallel thread, recent work from the NLP community suggests that for tasks such as natural language disambiguation even a simple algorithm can outperform a sophisticated one, if it is provided with large quantities of high quality training data. In those applications, training data occurs naturally in text corpora, and high quality training data sets running into billions of words have been reportedly used.

The ranking function used by search engines to order results is learned from labeled training data. Each training point is a (query, URL) pair that is labeled by a human judge who assigns a score of Perfect, Excellent, etc., depending on how well the URL matches the query. In this paper, we study whether clicks can be used to automatically generate good labels. Intuitively, documents that are clicked (resp., skipped) in aggregate can indicate relevance (resp., lack of relevance). We give a novel way of transforming clicks into weighted, directed graphs inspired by eye-tracking studies and then devise an objective function for finding cuts in these graphs that induce a good labeling. In its full generality, the problem is NP-hard, but we show that, in the case of two labels, an optimum labeling can be found in linear time. For the more general case, we propose heuristic solutions. Experiments on real click logs show that click-based labels align with the opinion of a panel of judges, especially as the consensus of the panel grows stronger.

In the sponsored search model, search engines are paid by businesses that are interested in displaying ads for their site alongside the search results. Businesses bid for keywords, and their ad is displayed when the keyword is queried to the search engine. An important problem in this process is keyword generation: given a business that is interested in launching a campaign, suggest keywords that are related to that campaign. We address this problem by making use of the query logs of the search engine. We identify queries re-lated to a campaign by exploiting the associations between queries and URLs as they are captured by the user’s clicks. These queries form good keyword suggestions since they cap-ture the “wisdom of the crowd ” as to what is related to a site. We formulate the problem as a semi-supervised learn-ing problem, and propose algorithms within the Markov Random Field model. We perform experiments with real query logs, and we demonstrate that our algorithms scale to large query logs and produce meaningful results.

The problem of assessing the significance of data mining results on high-dimensional 0--1 datasets has been studied extensively in the literature. For problems such as mining frequent sets and finding correlations, significance testing can be done by standard statistical tests such as chi-square, or other methods. However, the results of such tests depend only on the specific attributes and not on the dataset as a whole. Moreover, the tests are difficult to apply to sets of patterns or other complex results of data mining algorithms. In this article, we consider a simple randomization technique that deals with this shortcoming. The approach consists of producing random datasets that have the same row and column margins as the given dataset, computing the results of interest on the randomized instances and comparing them to the results on the actual data. This randomization technique can be used to assess the results of many different types of data mining algorithms, such as frequent sets, clustering, and spectral analysis. To generate random datasets with given margins, we use variations of a Markov chain approach which is based on a simple swap operation. We give theoretical results on the efficiency of different randomization methods, and apply the swap randomization method to several well-known datasets. Our results indicate that for some datasets the structure discovered by the data mining algorithms is expected, given the row and column margins of the datasets, while for other datasets the discovered structure conveys information that is not captured by the margin counts.

We consider the following problem: given a set of clusterings, find a single clustering that agrees as much as possible with the input clusterings. This problem, clustering aggregation , appears naturally in various contexts. For example, clustering categorical data is an instance of the clustering aggregation problem; each categorical attribute can be viewed as a clustering of the input rows where rows are grouped together if they take the same value on that attribute. Clustering aggregation can also be used as a metaclustering method to improve the robustness of clustering by combining the output of multiple algorithms. Furthermore, the problem formulation does not require a priori information about the number of clusters; it is naturally determined by the optimization function. In this article, we give a formal statement of the clustering aggregation problem, and we propose a number of algorithms. Our algorithms make use of the connection between clustering aggregation and the problem of correlation clustering . Although the problems we consider are NP-hard, for several of our methods, we provide theoretical guarantees on the quality of the solutions. Our work provides the best deterministic approximation algorithm for the variation of the correlation clustering problem we consider. We also show how sampling can be used to scale the algorithms for large datasets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.

The problem of assessing the significance of data mining results on high-dimensional 0-1 data sets has been studied extensively in the literature. For problems such as mining frequent sets and finding correlations, significance testing can be done by, e.g., chi-square tests, or many other methods. However, the results of such tests depend only on the specific attributes and not on the dataset as a whole. Moreover, the tests are more difficult to apply to sets of patterns or other complex results of data mining. In this paper, we consider a simple randomization technique that deals with this shortcoming. The approach consists of producing random datasets that have the same row and column margins with the given dataset, computing the results of interest on the randomized instances, and comparing them against the results on the actual data. This randomization technique can be used to assess the results of many different types of data mining algorithms, such as frequent sets, clustering, and rankings. To generate random datasets with given margins, we use variations of a Markov chain approach, which is based on a simple swap operation. We give theoretical results on the efficiency of different randomization methods, and apply the swap randomization method to several well-known datasets. Our results indicate that for some datasets the structure discovered by the data mining algorithms is a random artifact, while for other datasets the discovered structure conveys meaningful information.

Partitions of sequential data exist either per se or as a result of sequence segmentation algorithms. It is often the case that the same timeline is partitioned in many different ways. For example, different segmentation algorithms produce different partitions of the same underlying data points. In such cases, we are interested in producing an aggregate partition, i.e., a segmentation that agrees as much as possible with the input segmentations. Each partition is defined as a set of continuous non-overlapping segments of the timeline. We show that this problem can be solved optimally in polynomial time using dynamic programming. We also propose faster greedy heuristics that work well in practice. We experiment with our algorithms and we demonstrate their utility in clustering the behavior of mobile-phone users and combining the results of different segmentation algorithms on genomic sequences.

The sequence segmentation problem asks for a partition of the sequence into k non-overlapping segments that cover all data points such that each segment is as homogeneous as possible.This problem can be solved optimally using dynamic programming in O(n 2 k) time, where n is the length of the sequence.Given that sequences in practice are too long, a quadratic algorithm is not an adequately fast solution.Here, we present an alternative constantfactor approximation algorithm with running time O(n 4/3 k 5/3 ).We call this algorithm the DNS algorithm.We also consider the recursive application of the DNS algorithm, that results in a faster algorithm (O(n log log n) running time) with O(log n) approximation factor, and study the accuracy/efficiency tradeoff.Extensive experimental results show that these algorithms outperform other widely-used heuristics.The same algorithms can speed up solutions for other variants of the basic segmentation problem while maintaining constant their approximation factors.Our techniques can also be used in a streaming setting, with sublinear memory requirements.

We consider the following problem: given a set of clusterings, find a clustering that agrees as much as possible with the given clusterings. This problem, clustering aggregation, appears naturally in various contexts. For example, clustering categorical data is an instance of the problem: each categorical variable can be viewed as a clustering of the input rows. Moreover, clustering aggregation can be used as a meta-clustering method to improve the robustness of clusterings. The problem formulation does not require a-priori information about the number of clusters, and it gives a natural way for handling missing values. We give a formal statement of the clustering-aggregation problem, we discuss related work, and we suggest a number of algorithms. For several of the methods we provide theoretical guarantees on the quality of the solutions. We also show how sampling can be used to scale the algorithms for large data sets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.

Traditional data mining applications consider the problem of mining a single relation between two attributes. For example, in a scientific bibliography database, authors are related to papers, and we may be interested in discovering association rules between authors. However, in real life, we often have multiple attributes related though chains of relations. For example, authors write papers, and papers concern one or more topics. Mining such relational chains poses additional challenges. In this paper we consider the following problem: given a chain of two relations R/sub 1/ (A, P) and R/sub 2/(P, T) we want to find selectors for the objects in T such that the projected relation between A and P satisfies a specific property. The motivation for our approach is that a given property might not hold on the whole dataset, but it might hold when projecting the data on a selector set. We discuss various algorithms and we examine the conditions under which the a priori technique can be used. We experimentally demonstrate the effectiveness of our methods.

Consider spatial data consisting of a set of binary features taking values over a collection of spatial extents (grid cells). We propose a method that simultaneously finds spatial correlation and feature co-occurrence patterns, without any parameters. In particular, we employ the minimum description length (MDL) principle coupled with a natural way of compressing regions. This defines what "good" means: a feature co-occurrence pattern is good, if it helps us better compress the set of locations for these features. Conversely, a spatial correlation is good, if it helps us better compress the set of features in the corresponding region. Our approach is scalable for large datasets (both number of locations and of features). We evaluate our method on both real and synthetic datasets.

It is commonly assumed that high-dimensional datasets contain points most of which are located in low-dimensional manifolds. Detection of low-dimensional clusters is an extremely useful task for performing operations such as clustering and classification, however, it is a challenging computational problem. In this paper we study the problem of finding subsets of points with low intrinsic dimensionality. Our main contribution is to extend the definition of fractal correlation dimension, which measures average volume growth rate, in order to estimate the intrinsic dimensionality of the data in local neighborhoods. We provide a careful analysis of several key examples in order to demonstrate the properties of our measure. Based on our proposed measure, we introduce a novel approach to discover clusters with low dimensionality. The resulting algorithms extend previous density based measures, which have been successfully used for clustering. We demonstrate the effectiveness of our algorithms for discovering low-dimensional m-flats embedded in high dimensional spaces, and for detecting low-rank sub-matrices.

In the recent years there has been a surge of research activity in the area of information retrieval on the World Wide Web, using link analysis of the underlying hypertext graph topology. Most of the algorithms in the literature can be described as dynamical systems, that is, the repetitive application of a function on a set of weights. Algorithms that rely on eigenvector computations, such as HITS and PAGERANK, correspond to linear dynamical systems. In this work we consider two families of link analysis ranking algorithms that no longer enjoy the linearity property of the previous approaches. We study in depth an interesting special case of these two families. We prove that the corresponding non-linear dynamical system converges for any initialization, and we provide a rigorous characterization of the combinatorial properties of the stationary weights. The study of the weights provides a clear and insightful view of the mechanics of the algorithm. We also present extensive experimental results that demonstrate that our algorithm performs well in practice.

Data design has been characterized as a process of arriving at a design that maximizes the information content of each piece of data (or equivalently, one that minimizes redundancy). Information content (or redundancy) is measured with respect to a prescribed model for the data, a model that is often expressed as a set of constraints. In this work, we consider the problem of doing data redesign in an environment where the prescribed model is unknown or incomplete. Specifically, we consider the problem of finding structural clues in an instance of data, an instance which may contain errors, missing values, and duplicate records. We propose a set of information-theoretic tools for finding structural summaries that are useful in characterizing the information content of the data, and ultimately useful in data design. We provide algorithms for creating these summaries over large, categorical data sets. We study the use of these summaries in one specific physical design task, that of ranking functional dependencies based on their data redundancy. We show how our ranking can be used by a physical data-design tool to find good vertical decompositions of a relation (decompositions that improve the information content of the design). We present an evaluation of the approach on real data sets.

A plethora of data sources contain data entities that could be ordered according to a variety of attributes associated with the entities. Such orderings result effectively in a ranking of the entities according to the values in the attribute domain. Commonly, users correlate such sources for query processing purposes through join operations. In query processing, it is desirable to incorporate user preferences towards specific attributes or their values. A way to incorporate such preferences is by utilizing scoring functions that combine user preferences and attribute values and return a numerical score for each tuple in the join result. Then, a target query, which we refer to as top-k join query, seeks to identify the k tuples in the join result with the highest scores. We propose a novel technique, which we refer to as ranked join index, to efficiently answer top-k join queries for arbitrary, user specified, preferences and a large class of scoring functions. Our rank join index requires small space (compared to the entire join result) and provides guarantees for its performance. Moreover, our proposal provides a graceful tradeoff between its space requirements and worst case search performance. We supplement our analytical results with a thorough experimental evaluation using a variety of real and synthetic data sets, demonstrating that, in comparison to other viable approaches, our technique offers significant performance benefits.

Mining large-scale text corpora is an essential step in extracting the key themes in a corpus. We motivate a quantitative measure for significant associations through the distributions of pairs and triplets of co-occurring words. We consider the algorithmic problem of efficiently enumerating such significant associations and present pruning algorithms for these problems, with theoretical as well as empirical analyses. Our algorithms make use of two novel mining methods: (1) matrix mining, and (2) shortened documents. We present evidence from a diverse set of documents that our measure does in fact elicit interesting co-occurrences.

Recently, ther have been a number of algorH#-9 prC osed for analyzing hyperDCC link str5#TDso as todeterCDthe best "authorODHUM for a given topic or quer . While such analysis is usually combined with content analysis, ther is a sense in which some algorUO-9 ar deemed to be"mor balanced" andother "mor focused". WeunderDe a compar --C e study of hyperDTD link analysisalgor-CDCO Guided by some experD#C tal quer5CD we prD ose somefor-C crC5O r for evaluating and comparTlink analysisalgor-CUH5 Keywords link analysis, websear hing, hubs, author-9TD5 SALSA, KleinberMU algor9T#5 thrCHHE-9 Bayesian 1.