Graph Neural Networks (GNNs) have proven to be highly effective in various graph learning tasks. A key characteristic of GNNs is their use of a fixed number of message-passing steps for all nodes in the graph, regardless of each node's diverse computational needs and characteristics. Through empirical real-world data analysis, we demonstrate that the optimal number of message-passing layers varies for nodes with different characteristics. This finding is further supported by experiments conducted on synthetic datasets. To address this, we propose Adaptive Depth Message Passing GNN (ADMP-GNN), a novel framework that dynamically adjusts the number of message passing layers for each node, resulting in improved performance. This approach applies to any model that follows the message passing scheme. We evaluate ADMP-GNN on the node classification task and observe performance improvements over baseline GNN models. Our code is publicly available at: https://github.com/abbahaddou/ADMP-GNN

The Generative AI (AIGC) Day at KDD'24 is a dedicated full-day event for generative AI at KDD. This is an opportunity to bring together researchers, practitioners, and startups to share the insights about the cutting-edge advancements and to discuss the potential societal impacts of LLMs and AIGC. It is exciting that this year, we have invited speakers from both industry (e.g., Amazon, Zhipu AI) and academia (e.g., USC, UCLA). The topics cover various perspectives of generative AI including foundation models, streaming LLMs, LLM training and inference. As demonstrated, data plays a crucial role in developing cutting-edge generative AI models. For example, the Gemini Team has found that "data quality is an important factor for highly-performing models...''. To date, there is still significant room to define design principles and develop methods for improved data collection, selection, and synthetic data generation for the pre-training and alignment of language, vision, and multi-modal models. Therefore, the Day will invite the speakers and KDD audience to discuss the challenges and opportunities for data mining researchers in the era of generative AI.

Finding the seed set that maximizes the influence spread over a network is a well-known NP-hard problem. Though a greedy algorithm can provide near-optimal solutions, the subproblem of influence estimation renders the solutions inefficient. In this work, we propose GLIE, a graph neural network that learns how to estimate the influence spread of the independent cascade. GLIE relies on a theoretical upper bound that is tightened through supervised training. Experiments indicate that it provides accurate influence estimation for real graphs up to 10 times larger than the train set. Subsequently, we incorporate it into two influence maximization techniques. We first utilize Cost Effective Lazy Forward optimization substituting Monte Carlo simulations with GLIE, surpassing the benchmarks albeit with a computational overhead. To improve computational efficiency we develop a provably submodular influence spread based on GLIE's representations, to rank nodes while building the seed set adaptively. The proposed algorithms are inductive, meaning they are trained on graphs with less than 300 nodes and up to 5 seeds, and tested on graphs with millions of nodes and up to 200 seeds. The final method exhibits the most promising combination of time efficiency and influence quality, outperforming several baselines.

Classical recommender systems often assume that historical data are stationary and fail to account for the dynamic nature of user preferences, limiting their ability to provide reliable recommendations in time-sensitive settings. This assumption is particularly problematic in finance, where financial products exhibit continuous changes in valuations, leading to frequent shifts in client interests. These evolving interests, summarized in the past client-product interactions, see their utility fade over time with a degree that might differ from one client to another. To address this challenge, we propose a time-dependent collaborative filtering algorithm that can adaptively discount distant client-product interactions using personalized decay functions. Our approach is designed to handle the non-stationarity of financial data and produce reliable recommendations by modeling the dynamic collaborative signals between clients and products. We evaluate our method using a proprietary dataset from BNP Paribas and demonstrate significant improvements over state-of-the-art benchmarks from relevant literature. Our findings emphasize the importance of incorporating time explicitly in the model to enhance the accuracy of financial product recommendation.

Graph generative models are recently gaining significant interest in current application domains. They are commonly used to model social networks, knowledge graphs, and protein-protein interaction networks. In this talk we will present the potential of graph generative models and our recent relevant efforts in the biomedical domain. More specifically we present a novel architecture that generates medical records as graphs with privacy guarantees. We capitalize and modify the graph Variational autoencoders (VAEs) architecture. We train the generative model with the well known MIMIC medical database and achieve generated data that are very similar to the real ones yet provide privacy guarantees. We also develop new GNNs for predicting antibiotic resistance and other protein related downstream tasks such as enzymes classifications and Gene Ontology classification. We achieve there as well promising results with potential for future application in broader biomedical related tasks. Finally we present future research directions for multi modal generative models involving graphs.

We address the problem of influence maximization when the social network is accompanied by diffusion cascades. In the literature, such information is used to compute influence probabilities, which is utilized by stochastic diffusion models in influence maximization. Motivated by the recent criticism on diffusion models and the galloping advancements in influence learning, we proposeIMINFECTOR(Influence Maximization with INFluencer vECTORs), a method that uses representations learned from diffusion cascades to perform model-independent influence maximization. The first part of our methodology is a multi-task neural network that learns embeddings of nodes that initiate cascades (influencer vectors) and embeddings of nodes that participate in them (susceptible vectors). The norm of an influencer vector captures a node’s aptitude to initiate lengthy cascades and is used to reduce the number of candidate seeds. The combination of influencer and susceptible vectors form the diffusion probabilities between nodes. These are used to reformulate the computation of the influence spread and propose a greedy solution to influence maximization that retains the theoretical guarantees. We apply our method in three sizable datasets and evaluate it using cascades from future time steps.IMINFECTOR’s scalability and accuracy outperform various competitive algorithms and metrics from the diverse landscape of influence maximization.

On an artist’s profile page, music streaming services frequently recommend a ranked list of ”similar artists” that fans also liked. However, implementing such a feature is challenging for new artists, for which usage data on the service (e.g. streams or likes) is not yet available. In this paper, we model this cold start similar artists ranking problem as a link prediction task in a directed and attributed graph, connecting artists to their top-k most similar neighbors and incorporating side musical information. Then, we leverage a graph autoencoder architecture to learn node embedding representations from this graph, and to automatically rank the top-k most similar neighbors of new artists using a gravity-inspired mechanism. We empirically show the flexibility and the effectiveness of our framework, by addressing a real-world cold start similar artists ranking problem on a global music streaming service. Along with this paper, we also publicly release our source code and the industrial data from our experiments.

Many applications require identifying nodes that perform similar functions in a graph. For instance, identifying structurally equivalent nodes can provide insight into the structure of complex networks. Learning latent representations that capture such structural role information about nodes has recently gained a lot of attention. Existing techniques for learning such representations typically rely on manually engineered features or are very expensive in terms of time and memory requirements. In this paper, we propose SEGK, a powerful framework for computing structural node representations. SEGK learns node representations by generating (or approximating) and decomposing a kernel matrix that incorporates structural similarity between nodes. To compute the similarity between two nodes, the proposed framework builds on well-established concepts from graph mining. Specifically, it compares the neighborhood subgraphs of increasing size of two nodes using graph kernels. SEGK is very flexible, and besides unlabeled graphs, it can also handle node-labeled and node-attributed graphs. We evaluate the proposed framework on several synthetic and real-world datasets, and compare its performance to state-of-the-art techniques for learning structural node embeddings. In almost all cases, the instances of the proposed framework outperform the competing methods, while their time complexity remains very attractive.

Some of the most effective influential spreader detection algorithms are unstable to small perturbations of the network structure. Inspired by bagging in Machine Learning, we propose the first Perturb and Combine (P&C) procedure for networks. It (1) creates many perturbed versions of a given graph, (2) applies a node scoring function separately to each graph, and (3) combines the results. Experiments conducted on real-world networks of various sizes with the k-core, generalized k-core, and PageRank algorithms reveal that P&C brings substantial improvements. Moreover, this performance boost can be obtained at almost no extra cost through parallelization. Finally, a bias-variance analysis suggests that P&C works mainly by reducing bias, and that therefore, it should be capable of improving the performance of all vertex scoring functions, including stable ones. An extended version of this paper is provided by [1].

Graph autoencoders (AE) and variational autoencoders (VAE) recently emerged as powerful node embedding methods. In particular, graph AE and VAE were successfully leveraged to tackle the challenging link prediction problem, aiming at figuring out whether some pairs of nodes from a graph are connected by unobserved edges. However, these models focus on undirected graphs and therefore ignore the potential direction of the link, which is limiting for numerous real-life applications. In this paper, we extend the graph AE and VAE frameworks to address link prediction in directed graphs. We present a new gravity-inspired decoder scheme that can effectively reconstruct directed graphs from a node embedding. We empirically evaluate our method on three different directed link prediction tasks, for which standard graph AE and VAE perform poorly. We achieve competitive results on three real-world graphs, outperforming several popular baselines.

Graphs are becoming a dominant structure in current information management with many domains involved, including social networks, chemistry, biology, etc. Many real-world problems require applying machine learning tasks to graph-structured data. Graph kernels have emerged as a promising approach for dealing with these tasks. A graph kernel is a symmetric, positive semidefinite function on the set of graphs. These functions extend the applicability of kernel methods to graphs. Graph kernels have attracted a lot of attention during the last 20 years. The considerable research activity that occurred in the field resulted in the development of dozens of kernels, each focusing on specific structural properties of graphs. The goal of this tutorial is to offer a comprehensive presentation of a wide range of graph kernels, and to describe their key applications. The tutorial will also offer to the participants hands-on experience in applying graph kernels to classification problems.

This paper examines the problem of adaptive influence maximization in social networks. As adaptive decision making is a time-critical task, a realistic feedback model has been considered, called myopic. In this direction, we propose the myopic adaptive greedy policy that is guaranteed to provide a (1 - 1/e) -approximation of the optimal policy under a variant of the independent cascade diffusion model. This strategy maximizes an alternative utility function that has been proven to be adaptive monotone and adaptive submodular. The proposed utility function considers the cumulative number of active nodes through the time, instead of the total number of the active nodes at the end of the diffusion. Our empirical analysis on real-world social networks reveals the benefits of the proposed myopic strategy, validating our theoretical results.

Graph kernels have recently emerged as a promising approach to perform machine learning on graph-structured data. A graph kernel implicitly embedds graphs in a Hilbert space and computes the inner product between these representations. However, the inner product operation greatly limits the representational power of kernels between graphs. In this paper, we propose to perform a series of successive embeddings in order to improve the performance of existing graph kernels and derive more expressive kernels. We first embed the input graphs in a Hilbert space using a graph kernel and then we embed them into another space by employing popular kernels for vector data (e.g., gaussian kernel). Our experiments on several datasets show that by composing kernels, we can achieve significant improvements in classification accuracy.

Graphs have been widely used as modeling tools in Natural Language Processing (NLP), Text Mining (TM) and Information Retrieval (IR). Traditionally, the unigram bag-of-words representation is applied; that way, a document is represented as a multiset of its terms, disregarding dependencies between the terms. Although several variants and extensions of this modeling approach have been proposed, the main weakness comes from the underlying term independence assumption; the order of the terms within a document is completely disregarded and any relationship between terms is not taken into account in the final task. To deal with this problem, the research community has explored various representations, and to this direction, graphs constitute a well-developed model for text representation. The goal of this tutorial is to offer a comprehensive presentation of recent methods that rely on graph-based text representations to deal with various tasks in Text Mining, NLP and IR.

In this paper we present an approach to tackle the problem of event prediction for the purpose of performing predictive maintenance in aviation. Given a collection of recorded events that correspond to equipment failures, our method predicts the next occurrence of one or more events of interest (target events or critical failures). Our objective is to develop an alerting system that would notify aviation engineers well in advance for upcoming aircraft failures, providing enough time to prepare the corresponding maintenance actions. We formulate a regression problem in order to approximate the risk of occurrence of a target event, given the past occurrences of other events. In order to achieve the best results we employed a multiple instance learning scheme (multiple instance regression) along with extensive data preprocessing. We applied our method on data coming from a fleet of aircraft and our predictions involve failures of components onboard, specifically components that are related to the landing gear. The event logs correspond to post flight reports retrieved from multiple aircraft during several years of operation. To the best of our knowledge, this paper is the first attempt on aircraft failure prediction using post flight report data and finally, our findings show high potential impact on the aviation industry.

Community detection constitutes an important task for investigating the internal structure of networks, with a plethora of applications in a wide range of disciplines. A particularly important point, which is rarely taken into account while developing community detection algorithms, is their sensitivity (or stability) to network uncertainty. In many cases, the input graph data is incomplete or noisy (e.g., due to noise introduced during the collection of the data or for privacy preserving reasons). Then, the following question arises: how stable are the results produced by an algorithm with respect to the uncertainty (i.e., noise level) of the input data? In this paper, we propose a quantitative way to address this problem. We have considered several graph perturbation models to introduce uncertainty to the graph. Then, we examine the sensitivity of an algorithm, with respect to functional and structural characteristics of the detected communities under various perturbation levels. We have studied the performance of some of the most widely used community detection algorithms in practice, and our experimental results indicate that random walk based community detection algorithms tend to be robust under various conditions of network uncertainty.

No abstract available.

The first ACM international workshop on big network analytics is held in Indianapolis, Indiana, USA on October 24, 2016 and co-located with the ACM 25th Conference on Information and Knowledge Management (CIKM). The main objective of the workshop is to provide a forum for presenting the most recent advances in mining big networks to unearth rich knowledge. It is related to information retrieval, Web mining, social network analysis, and computational advertising. The anticipated outcome includes a fruitful discussion about the emerging challenges in this field, the development of novel theories for mining big networks, and motivating the interesting applications. The broader anticipated outcome includes: fostering future research directions, publishing high quality papers, attracting new researchers to this field, and concrete solutions to the existing problems.

Graph mining is an important research area with a plethora of practical applications. Core decomposition in networks, is a fundamental operation strongly related to more complex mining tasks such as community detection, dense subgraph discovery, identification of influential nodes, network visualization, text mining, just to name a few. In this tutorial, we present in detail the concept and properties of core decomposition in graphs, the associated algorithms for its efficient computation and some of its most important applications.

Lately, there has been an increased interest in signed networks with applications in trust, security, or social computing. This paper focuses on the issue of defining models and metrics for reciprocity in signed graphs. In unsigned directed networks, reciprocity quantifies the predisposition of network members in creating mutual connections. On the other hand, this concept has not yet been investigated in the case of signed graphs. We capitalize on the graph degeneracy concept to identify subgraphs of the signed network in which reciprocity is more likely to occur. This enables us to assess reciprocity at a global level, rather than at an exclusively local one as in existing approaches. The large scale experiments we perform on real world data sets of trust networks lead to both interesting and intuitive results. We believe these reciprocity measures can be used in various social applications such as trust management, community detection and evaluation of individual nodes. The global reciprocity we define in this paper is closely correlated to the clustering structure of the graph, more than the local reciprocity as it is indicated by the experimental evaluation we conducted.

Given a large social graph, how can we model the engagement properties of nodes? Can we quantify engagement both at node level as well as at graph level? Typically, engagement refers to the degree that an individual participates (or is encouraged to participate) in a community and is closely related to the important property of nodes' departure dynamics, i.e., the tendency of individuals to leave the community. In this paper, we build upon recent work in the field of game theory, where the behavior of individuals (nodes) is modeled by a technology adoption game. That is, the decision of a node to remain engaged in the graph is affected by the decision of its neighbors, and the "best practice" for each individual is captured by its core number - as arises from the k-core decomposition. After modeling and defining the engagement dynamics at node and graph level, we examine whether they depend on structural and topological features of the graph. We perform experiments on a multitude of real graphs, observing interesting connections with other graph characteristics, as well as a clear deviation from the corresponding behavior of random graphs. Furthermore, similar to the well known results about the robustness of real graphs under random and targeted node removals, we discuss the implications of our findings on a special case of robustness - regarding random and targeted node departures based on their engagement level.

In this paper, we introduce novel document representation (graph-of-word) and retrieval model (TW-IDF) for ad hoc IR. Questioning the term independence assumption behind the traditional bag-of-word model, we propose a different representation of a document that captures the relationships between the terms using an unweighted directed graph of terms. From this graph, we extract at indexing time meaningful term weights (TW) that replace traditional term frequencies (TF) and from which we define a novel scoring function, namely TW-IDF, by analogy with TF-IDF. This approach leads to a retrieval model that consistently and significantly outperforms BM25 and in some cases its extension BM25+ on various standard TREC datasets. In particular, experiments show that counting the number of different contexts in which a term occurs inside a document is more effective and relevant to search than considering an overall concave term frequency in the context of ad hoc IR.

Products, services or brands can be advertised alongside the search results in major search engines, while recently smaller displays on devices like tablets and smartphones have imposed the need for smaller ad texts. In this paper, we propose a method that produces in an automated manner compact text ads (promotional text snippets), given as input a product description webpage (landing page). The challenge is to produce a small comprehensive ad while maintaining at the same time relevance, clarity, and attractiveness. Our method includes the following phases. Initially, it extracts relevant and important n-grams (keywords) given the landing page. The keywords reserved must have a positive meaning in order to have a call-to-action style, thus we attempt sentiment analysis on them. Next, we build an Advertising Language Model to evaluate phrases in terms of their marketing appeal. We experiment with two variations of our method and we show that they outperform all the baseline approaches.

Online services such as social care, tax services, bank loans and many others, request individuals to fill in application forms with hundreds of private data items, in order to calibrate their offer. In practice, far too much data is requested, leading to over data disclosure. As shown in our previous works, avoiding this problem would (1) improve the privacy of the applicants and (2) decrease costs for service providers. We demonstrate here a prototype designed and implemented in partnership with the General Council of Yvelines District in France. The prototype targets forms used to calibrate social care for dependant people. To maintain the privacy of the decision process used to calibrate the social care, we propose a smartcard implementation. We will show that a 50% reduction of the items exposed in application forms can be achieved, explore the quality and scalability of our smartcard implementation, and demonstrate its scope.

We present Match the News, a browser extension for real time news recommendation. Our extension works on the client side to recommend in real time recently published articles that are relevant to the web page the user is currently visiting. Match the News is fed from Google News RSS and applies syntactic matching to find the relevant articles. We implement an innovative weighting function to perform the keyword extraction task, BM25H. With BM25H we extract keywords not only relevant to currently browsed web page, but also novel with respect to the user's recent browsing history. The novelty feature in keyword extraction task results in meaningful news recommendations with regards to the web page the users currently visits. Moreover the extension offers a salient visualization of the terms corresponding to the users recent browsing history making thus the extension a comprehensive tool for real time news recommendation and self assessment.

Previous papers in ad hoc IR reported that scoring functions should satisfy a set of heuristic retrieval constraints, providing a mathematical justification for the normalizations historically applied to the term frequency (TF). In this paper, we propose a further level of abstraction, claiming that the successive normalizations are carried out through composition. Thus we introduce a principled framework that fully explains BM25 as a variant of TF-IDF with an inverse order of function composition. Our experiments over standard datasets indicate that the respective orders of composition chosen in the original papers for both TF-IDF and BM25 are the most effective ones. Moreover, since the order is different between the two models, they also demonstrated that the order is instrumental in the design of weighting models. In fact, while considering more complex scoring functions such as BM25+, we discovered a novel weighting model in terms of order of composition that consistently outperforms all the rest. Our contribution here is twofold: we provide a unifying mathematical framework for IR and a novel scoring function discovered using this framework.

Graphs constitute a dominant data structure and appear essentially in all forms of information. Examples are the Web graph, numerous social networks, protein interaction networks, terms dependency graphs and network topologies. The main features of these graphs are their huge volume and rate of change. Presumably, there is important hidden knowledge in the macroscopic topology and features of these graphs. A cornerstone issue here is the detection and evaluation of communities -- bearing multiple and diverse semantics. The tutorial reports the basic models of graph structures for undirected, directed and signed graphs and their properties. Next we offer a thorough review of fundamental methods for graph clustering and community detection, on both undirected and directed graphs. Then we survey community evaluation measures, including both the individual node based ones as well as those that take into account aggregate properties of communities. A special mention is made on approaches that capitalize on the concept of degeneracy (k-cores and extensions), as a novel means of community detection and evaluation. We justify the above foundational framework with applications on citation graphs, trust networks and protein graphs.

We demonstrate a system that supports the visual exploration of collaboration networks. The system leverages the notion of fractional cores introduced in earlier work to rank vertices in a collaboration network and filter vertices' neighborhoods. Fractional cores build on the idea of graph degeneracy as captured by the notion of k-cores in graph theory and extend it to undirected edge-weighted graphs. In a co-authorship network, for instance, the fractional core index of an author intuitively reflects the degree of collaboration with equally or higher-ranked authors. Our system has been deployed on a real-world co-authorship network derived from DBLP, demonstrating that the idea of fractional cores can be applied even to large-scale networks. The system provides an easy-to-use interface to query for the fractional core index of an author, to see who the closest equally or higher-ranked co-authors are, and explore the entire co-authorship network in an incremental manner.

Community sub graphs are characterized by dense connections or interactions among its nodes. Community detection and evaluation is an important task in graph mining. A variety of measures have been proposed to evaluate the quality of such communities. In this paper, we evaluate communities based on the k-core concept, as means of evaluating their collaborative nature - a property not captured by the single node metrics or by the established community evaluation metrics. Based on the k-core, which essentially measures the robustness of a community under degeneracy, we extend it to weighted graphs, devising a novel concept of k-cores on weighted graphs. We applied the k-core approach on large real world graphs - such as DBLP and report interesting results.

In this paper we describe a learning framework enabling ranking predictions for graph nodes based solely on individual local historical data. The two learning algorithms capitalize on the multi feature vectors of nodes in graphs that evolve in time. In the first case we use weighted polynomial regression (LWPR) while in the second we consider the Expectation Maximization (EM) algorithm to fit a mixture of polynomial regression models. The first method uses separate weighted polynomial regression models for each web page, while the second algorithm capitalizes on group behavior, thus taking advantage of the possible interdependence between web pages. The prediction quality is quantified as the similarity between the predicted and the actual rankings and compared to alternative baseline predictor. We performed extensive experiments on a real world data set (the Wikipedia graph). The results are very encouraging.

As search engines, social networks, and the World Wide Web become more popular and widely used, online advertising turns into a very profitable industry. Individuals and companies promote their products or services in search engines through textual ads, alongside the organic search results triggered by a specific query. For this purpose, advertisers must create advertising campaigns. The development of these campaigns is a laborious task involving significant human resources and expertise. In this paper we propose a system for multiword keyword recommendations in the context of developing a web advertising campaign in a semiautomatic manner. Given a landing page, the system extracts relevant terms consisted of two or three words to match a potential search query. Furthermore, it proposes the most relevant keywords and other suggested terms that do not exist in the landing page text using search result snippets. In addition, we present blind testing experiments on real world data indicating that our approach outperforms prominent existing industrial solutions in most of the cases.

Community detection and evaluation is an important task in graph mining. In many cases, a community is defined as a sub graph characterized by dense connections or interactions among its nodes. A large variety of measures have been proposed to evaluate the quality of such communities - in most cases ignoring the directed nature of edges. In this paper, we introduce novel metrics for evaluating the collaborative nature of directed graphs - a property not captured by the single node metrics or by other established community evaluation metrics. In order to accomplish this objective, we capitalize on the concept of graph degeneracy and define a novel D-core framework, extending the classic graph-theoretic notion of k-cores for undirected graphs to directed ones. Based on the D-core, which essentially can be seen as a measure of the robustness of a community under degeneracy, we devise a wealth of novel metrics used to evaluate graph collaboration features of directed graphs. We applied the D-core approach on large real-world graphs such as Wikipedia and DBLP and report interesting results at the graph as well at node level.

Scaling up data mining algorithms for data of both high dimensionality and cardinality has been lately recognized as one of the most challenging problems in data mining research. The reason is that typical data mining tasks, such as clustering, cannot produce high quality results when applied on high-dimensional and/or large (in terms of cardinality) datasets. Data preprocessing and in particular dimensionality reduction constitute promising tools to deal with this problem. However, most of the existing dimensionality reduction algorithms share also the same disadvantages with data mining algorithms, when applied on large datasets of high dimensionality. In this article, we propose a fast and efficient dimensionality reduction algorithm (FEDRA), which is particularly scalable and therefore suitable for challenging datasets. FEDRA follows the landmark-based paradigm for embedding data objects in a low-dimensional projection space. By means of a theoretical analysis, we prove that FEDRA is efficient, while we demonstrate the achieved quality of results through experiments on datasets of higher cardinality and dimensionality than those employed in the evaluation of competitive algorithms. The obtained results prove that FEDRA manages to retain or ameliorate clustering quality while projecting in less than 10% of the initial dimensionality. Moreover, our algorithm produces embeddings that enable the faster convergence of clustering algorithms. Therefore, FEDRA emerges as a powerful and generic tool for data pre-processing, which can be integrated in other data mining algorithms, thus enhancing their performance.

Recently, the problem of efficiently supporting advanced query operators, such as nearest neighbor or range queries, over multidimensional data in widely distributed environments has attracted much attention. In unstructured peer-to-peer (P2P) networks, peers store data in an autonomous manner, thus multidimensional routing indices (MRI) are required, in order to route user queries efficiently to only those peers that may contribute to the query result set. Focusing on a hybrid unstructured P2P network, in this paper, we analyze the parameters for building MRI of high selectivity. In the case where similar data are located at different parts of the network, MRI exhibit extremely poor performance, which renders them ineffective. We present algorithms that boost the query routing performance by detecting similar peers and reassigning these peers to other parts of the hybrid network in a distributed and scalable way. The resulting MRI are able to eagerly discard routing paths during query processing. We demonstrate the advantages of our approach experimentally and show that our framework enhances a state-of-the-art approach for similarity search in terms of reduced network traffic and number of contacted peers.

Data generation increases at highly dynamic rates, making its storage, processing, and update costs at one central location excessive. The P2P paradigm emerges as a powerful model for organizing and searching large data repositories distributed over independent sources. Advanced query operators, such as skyline queries, are necessary in order to help users handle the huge amount of available data. A skyline query retrieves the set of nondominated data points in a multidimensional data set. Skyline query processing in P2P networks poses inherent challenges and demands nontraditional techniques, due to the distribution of content and the lack of global knowledge. Relying on a superpeer architecture, we propose a threshold-based algorithm, called SKYPEER and its variants, for efficient computation of skyline points in arbitrary subspaces, while reducing both computational time and volume of transmitted data. Furthermore, we address the problem of routing skyline queries over the superpeer network and we propose an efficient routing mechanism, namely SKYPEER+, which further improves the performance by reducing the number of contacted superpeers. Finally, we provide an extensive experimental evaluation showing that our approach performs efficiently and provides a viable solution when a large degree of distribution is required.

Traditional routing indices in peer-to-peer (P2P) networks are mainly designed for document retrieval applications and maintain aggregated one-dimensional values representing the number of documents that can be obtained in a certain direction in the network. In this paper, we introduce the concept of multidimensional routing indices (MRIs), which are suitable for handling multidimensional data represented by minimum bounding regions (MBRs). Depending on data distribution on peers, the aggregation of the MBRs may lead to MRIs that exhibit extremely poor performance, which renders them ineffective. Thus, focusing on a hybrid unstructured P2P network, we analyze the parameters for building MRIs of high selectivity. We present techniques that boost the query routing performance by detecting similar peers and grouping and reassigning these peers to other parts of the hybrid network in a distributed and scalable way. We demonstrate the advantages of our approach using large-scale simulations.

Contemporary data-intensive applications generate large datasets of very high dimensionality. Data management in high-dimensional spaces presents problems, such as the degradation of query processing performance, a phenomenon also known as the curse of dimensionality. Dimensionality reduction (DR) tackles this problem, by efficiently embedding data from high dimensional to lower dimensional spaces. However, the large scale and dynamism of generated data calls for methods of low time and space complexity, features that are hardly combined in the majority of existing DR algorithms. Motivated by this fact, in this paper we propose FEDRA, a fast and efficient dimensionality reduction algorithm that uses a set of landmark points to project data to a lower dimensional Euclidean space. FEDRA is both faster and requires less memory than other comparable algorithms, without compromising the projection's quality. We theoretically assess the quality of the resulting projection and provide a bound for the error induced in pairwise distances. Furthermore, we present two extensions of FEDRA that improve the quality of the projection, suitable for applications that can tolerate higher processing costs. We prove the validity of our claims both theoretically and experimentally, by comparing our algorithm against prominent approaches, such as FastMap, LMDS, PCA, SVD and Random Projection.

Due to applications and systems such as sensor networks, data streams, and peer-to-peer (P2P) networks, data generation and storage become increasingly distributed. Therefore a challenging problem is to support best-match query processing in highly distributed environments. In this paper, we present a novel framework for top-k query processing in large- scale P2P networks, where the dataset is horizontally distributed to peers. Our proposed framework returns the exact results to the user, while minimizing the number of queried super-peers and transferred data. Through simulations we demonstrate the feasibility of our approach in terms of overall response time.

Lately the advances in centralized database management systems show a trend towards supporting rank-aware query operators, like top-k, that enable users to retrieve only the most interesting data objects. A challenging problem is to support rank-aware queries in highly distributed environments. In this paper, we present a novel approach, called SPEERTO, for top-k query processing in large-scale peer-to-peer networks, where the dataset is horizontally distributed over the peers. Towards this goal, we explore the applicability of the skyline operator for efficiently routing top-k queries in a large super-peer network. Relying on a thresholding scheme, SPEERTO returns the exact results progressively to the user, while the number of queried super-peers and transferred data is minimized. Finally, we propose different variations of SPEERTO that allow balancing between transferred data volume and response time. Through simulations we demonstrate the feasibility of our approach.

In this paper we propose a method for predicting the ranking position of a Web page. Assuming a set of successive past top-k rankings, we study the evolution of Web pages in terms of ranking trend sequences used for Markov Models training, which are in turn used to predict future rankings. The predictions are highly accurate for all experimental setups and similarity measures.

Clustering, as an unsupervised learning process is a challenging problem, especially in cases of high-dimensional datasets. Clustering result quality can benefit from user constraints and objective validity assessment. In this article, we propose a semisupervised framework for learning the weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on: (i) user constraints; and (ii) the quality of intermediate clustering results in terms of their structural properties. The proposed framework uses the clustering algorithm and the validity measure as its parameters. We develop and discuss algorithms for learning and tuning the weights of contributing dimensions and defining the “best” clustering obtained by satisfying user constraints. Experimental results on benchmark datasets demonstrate the superiority of the proposed approach in terms of improved clustering accuracy.

Skyline query processing has received considerable attention in the recent past. Mainly, the skyline query is used to find a set of non dominated data points in a multidimensional dataset. While most previous work has assumed a centralized setting, in this paper we address the efficient computation of subspace skyline queries in large-scale peer-to-peer (P2P) networks, where the dataset is horizontally distributed across the peers. Relying on a super-peer architecture we propose a threshold based algorithm, called SKYPEER, which forwards the skyline query requests among peers, in such a way that the amount of transferred data is significantly reduced. For efficient subspace skyline processing, we extend the notion of domination by defining the extended skyline set, which contains all data elements that are necessary to answer a skyline query in any arbitrary subspace. We prove that our algorithm provides the exact answers and we present optimization techniques to reduce communication cost and execution time. Finally, we provide an extensive experimental evaluation showing that SKYPEER performs efficiently and provides a viable solution when a large degree of distribution is required.

PageRank is the best known technique for link-based importance ranking. The computed importance scores, however, are not directly comparable across different snapshots of an evolving graph. We present an efficiently computable normalization for PageRank scores that makes them comparable across graphs. Furthermore, we show that the normalized PageRank scores are robust to non-local changes in the graph, unlike the standard PageRank measure.

Ranking methods like PageRank assess the importance of Web pages based on the current state of the rapidly evolving Web graph. The dynamics of the resulting importance scores, however, have not been considered yet, although they provide the key to an understanding of the Zeitgeist on the Web. This paper proposes the BuzzRank method that quantifies trends in time series of importance scores and is based on a relevant growth model of importance scores. We experimentally demonstrate the usefulness of BuzzRank on a bibliographic dataset.

Peer-to-peer (P2P) Web search has gained a lot of interest lately, due to the salient characteristics of P2P systems, namely scalability, fault-tolerance and load-balancing. However, the lack of global knowledge in a vast and dynamically evolving environment like the Web presents a grand challenge for organizing content and providing efficient searching. Semantic overlay networks (SONs) have been proposed as an approach to reduce cost and increase quality of results, and in this paper we present an unsupervised approach for distributed and decentralized SON construction, aiming to support efficient search mechanisms in unstructured P2P systems.

Recommendation algorithms aim at proposing "next" pages to a user based on her current visit and the past users' navigational patterns. In the vast majority of related algorithms, only the usage data are used to produce recommendations, whereas the structural properties of the Web graph are ignored. We claim that taking also into account the Web structure and using link analysis algorithms ameliorates the quality of recommendations. In this paper we present UPR, a novel personalization algorithm which combines usage data and link analysis techniques for ranking and recommending Web pages to the end user. Using the Web site's structure and its usage data we produce personalized navigational graph synopsis (prNG) to be used for applying UPR and produce personalized recommendations. Experimental results show that the accuracy of the recommendations is superior to pure usage-based approaches.

In this paper, we propose a semi-supervised framework for learning a weighted Euclidean subspace, where the best clustering can be achieved. Our approach capitalizes on user-constraints and the quality of intermediate clustering results in terms of its structural properties. It uses the clustering algorithm and the validity measure as parameters.

Mobile terminals (cellular phones, PDAs, palmtops etc.) emerge as a new class of small-scale, ad-hoc service providers that share data and functionality via mobile web services' calls. In mobile service discovery, it is often the case that implicit contextual information such as the location of the requestor, time the query was submitted, capabilities of the involved devices have a significant impact on query evaluation and the quality of the results. On the other hand, lack of scalability and the well-known single point of failure problem call for distribution of service directories into several peers. In this paper, we present an approach for context-aware service discovery where service directories reside in a P2P architecture. We explore the role and benefits of context-awareness and caching query results in the service discovery process. We conduct extensive experiments coming up with guidelines for service directory design in a P2P context.

Several interesting research directions materialize through the convergence of mobile computing and service-oriented computing. As mobile devices keep getting smaller, cheaper and more sophisticated, their use is becoming a commodity. We envision future scenarios that involve mobile devices acting not only as requestors, but as providers of data as well. In order to hide the heterogeneous nature of web data, service-oriented architectures are adopted. Nevertheless, existing service discovery mechanisms usually focus on exact or semantic matching of static attributes, thus ignoring contextual parameters. We argue that context for mobile web services plays an important role in service discovery by increasing the precision and efficiency of the search. We explain our notion of context regarding mobile services and describe query evaluation, updating and merging of context-aware service directories.

With the unstoppable growth of the world wide Web, the great success of Web search engines, such as Google and AltaVista, users now turn to the Web whenever looking for information. However, many users are neophytes when it comes to computer science, yet they are often specialists of a certain domain. These users would like to add more semantics to guide their search through world wide Web material, whereas currently most search features are based on raw lexical content. We show how the use of the incoming links of a page can be used efficiently to classify a page in a concise manner. This enhances the browsing and querying of Web pages. We focus on the tools needed in order to manage the links and their semantics. We further process these links using a hierarchy of concepts, akin to an ontology, and a thesaurus. This work is demonstrated by an prototype system, called THESUS, that organizes thematic Web documents into semantic clusters. Our contributions are the following: 1) a model and language to exploit link semantics information, 2) the THESUS prototype system, 3) its innovative aspects and algorithms, more specifically, the novel similarity measure between Web documents applied to different clustering schemes (DB-Scan and COBWEB), and 4) a thorough experimental evaluation proving the value of our approach.

Web personalization is the process of customizing a Web site to the needs of each specific user or set of users, taking advantage of the knowledge acquired through the analysis of the user's navigational behavior. Integrating usage data with content, structure or user profile data enhances the results of the personalization process. In this paper, we present SEWeP, a system that makes use of both the usage logs and the semantics of a Web site's content in order to personalize it. Web content is semantically annotated using a conceptual hierarchy (taxonomy). We introduce C-logs, an extended form of Web usage logs that encapsulates knowledge derived from the link semantics. C-logs are used as input to the Web usage mining process, resulting in a broader yet semantically focused set of recommendations.

The rapid advances in wireless communications technology and mobile computing have enabled personal mobile devices that we use in everyday life to become information and service providers by complementing or replacing fixed-location hosts connected to the wireline network. Such mobile resources is highly important for other moving users, creating significant opportunities for many interesting and novel applications. The MobiShare architecture provides the infrastructure for ubiquitous mobile access and mechanisms for publishing, discovering and accessing heterogeneous mobile resources in a large area, taking into account the context of both sources and requestors. Any wireless communication technology could be used between a device and the system. Furthermore, the use of XML-related languages and protocols for describing and exchanging metadata gives the system a uniform and easily adaptable interface, allowing a variety of devices to use it. The overall approach is data-centric and service-oriented, implying that all devices are treated as producers or requestors of data wrapped as information services.

Many organizations and enterprises establish distributed working environments, where different users need to exchange information based on a common model. XML is widely used to facilitate this information exchange. The extensibility of XML allows the creation of generic models that integrate data from different sources. For these tasks, several applications are used to import and export information in XML format from the data repositories. In order to support this process for relational repositories we developed the X-Database system. The base of this system is an XML-Schema file that describes the logical model of interchanged information. Initially, the system analyses the syntax of the XML-Schema file and generates the relational database. Then it handles the decomposition of valid XML files according to that Schema and the composition of XML documents from the information in the database. Finally the system offers a flexible mechanism for modifying and querying database contents using only valid XML documents, which are validated over the XML-Schema file's rules.

Clustering is a mostly unsupervised procedure and the majority of clustering algorithms depend on certain assumptions in order to define the subgroups present in a data set. As a consequence, in most applications the resulting clustering scheme requires some sort of evaluation regarding its validity. In this paper we present a clustering validity procedure, which evaluates the results of clustering algorithms on data sets. We define a validity index, S Dbw, based on well-defined clustering criteria enabling the selection of optimal input parameter values for a clustering algorithm that result in the best partitioning of a data set. We evaluate the reliability of our index both theoretically and experimentally, considering three representative clustering algorithms run on synthetic and real data sets. We also carried out an evaluation study to compare S Dbw performance with other known validity indices. Our approach performed favorably in all cases, even those in which other indices failed to indicate the correct partitions in a data set.

We present a system that aims at increasing the flexibility and accuracy of information retrieval tasks in the World Wide Web. The system offers extended searching capabilities by enriching information related to hyperlinks between documents. It offers to document authors the ability to attach additional information to hyperlinks and also provides suggestions on the information to be attached. In an effort to increase the integrity of hyperlink information, a conversion module extracts, from the pages, metadata concerning the linked documents as well as the link itself. The hyperlink metadata is appended to the original document metadata and an XML document is created. Another module allows the end users to query the XML-document base, taking advantage of the enhanced hyperlink information. We present an overview of the system and the solutions it provides in problems found to similar approaches.

Clustering aims at discovering groups and identifying interesting distributions and patterns in data sets. Researchers have extensively studied clustering since it arises in many application domains in engineering and social sciences. In the last years the availability of huge transactional and experimental data sets and the arising requirements for data mining created needs for clustering algorithms that scale and can be applied in diverse domains. The paper surveys clustering methods and approaches available in the literature in a comparative way. It also presents the basic concepts, principles and assumptions upon which the clustering algorithms are based. Another important issue is the validity of the clustering schemes resulting from applying algorithms. This is also related to the inherent features of the data set under concern. We review and compare clustering validity measures available in the literature. Furthermore, we illustrate the issues that are under-addressed by the recent algorithms and we address new research directions.

Spatio-temporal databases deal with geometries changing over time. The goal of our work is to provide a DBMS data model and query language capable of handling such time-dependent geometries, including those changing continuously that describe moving objects . Two fundamental abstractions are moving point and moving region , describing objects for which only the time-dependent position, or position and extent, respectively, are of interest. We propose to present such time-dependent geometries as attribute data types with suitable operations, that is, to provide an abstract data type extension to a DBMS data model and query language. This paper presents a design of such a system of abstract data types. It turns out that besides the main types of interest, moving point and moving region, a relatively large number of auxiliary data types are needed. For example, one needs a line type to represent the projection of a moving point into the plane, or a “moving real” to represent the time-dependent distance of two points. It then becomes crucial to achieve (i) orthogonality in the design of the system, i.e., type constructors can be applied unifomly; (ii) genericity and consistency of operations, i.e., operations range over as many types as possible and behave consistently; and (iii) closure and consistency between structure and operations of nontemporal and related temporal types. Satisfying these goal leads to a simple and expressive system of abstract data types that may be integrated into a query language to yield a powerful language for querying spatio-temporal data, including moving objects. The paper formally defines the types and operations, offers detailed insight into the considerations that went into the design, and exemplifies the use of the abstract data types using SQL. The paper offers a precise and conceptually clean foundation for implementing a spatio-temporal DBMS extension.

It has been recently recognized that fuzzy set theory provides useful concepts and tools for both the representation and analysis of the uncertainty related to geographical data. Hence the incorporation of fuzzy set methodologies into a DBMS repository for the application domain of GIS should be beneficial and will improve its level of intelligence. Focusing in this area the paper addresses both a representation and a reasoning issue. Specifically, it extends a general spatial data model to deal with the uncertainty of geographical entities, and shows how the standard data interpretation operations available in GIS packages may be extended to support the fuzzy spatial reasoning. Representative geographical operations, suchas the fuzzy overlay, fuzzy distance and fuzzy select, are examined, while several real world examples are given.