Graph neural networks (GNNs) have achieved breakthroughs in various real-world downstream tasks due to their powerful expressiveness. As the scale of real-world graphs has been continuously growing, a storage-based approach to GNN training has been studied, which leverages external storage (e.g., NVMe SSDs) to handle such web-scale graphs on a single machine. Although such storage-based GNN training methods have shown promising potential in large-scale GNN training, we observed that they suffer from a severe bottleneck in data preparation since they overlook a critical challenge: how to handle a large number of small storage I/Os. To address the challenge, in this paper, we propose a novel storage-based GNN training framework, named AGNES, that employs a method of block-wise storage I/O processing to fully utilize the I/O bandwidth of high-performance storage devices. Moreover, to further enhance the efficiency of each storage I/O, AGNES employs a simple yet effective strategy, hyperbatch-based processing based on the characteristics of real-world graphs. Comprehensive experiments on five real-world graphs reveal that AGNES consistently outperforms four state-of-the-art methods, up to 4.1× faster than the best competitor.

Conversational recommender systems (CRSs) aim to provide personalized item recommendations along with explanations based on the conversations with users. While advancements in language models (LMs) have facilitated CRSs, limitations remain when LMs lack sufficient knowledge about item features that are essential for accurate recommendations and appropriate explanations. To alleviate this issue, retrieval-augmented language models (RALMs) have been introduced; however, they introduce a new challenge: the inclusion of less-relevant knowledge in retrieved passages. To address this limitation, we propose a novel CRS framework, MOCHA, which enhances RALMs through a multi-stage item/feature selection with Chain-of-Thought (CoT) reasoning. Specifically, MOCHA systematically identifies relevant knowledge by first selecting the item to recommend and then selecting its features to explain; each selection is performed via CoT reasoning. Experimental results on two public CRS datasets demonstrate that MOCHA significantly improves the recommendation accuracy, and provides informative and factually-correct explanations for the recommended items.

Conversational Recommender Systems (CRS) aim to provide tailored recommendation responses via a chat interface, including both the user's preferred item and its accompanying explanation. However, due to its generative nature, CRS are prone to responding with factually incorrect explanations (i.e., hallucinations). To solve this problem, we propose incorporating a passage retrieval module into CRS with the objective of enhancing the factuality and informativeness of system responses. Specifically, we outline essential directions for employing a passage retrieval module in CRS to address the following critical issues: (1) the risk of passage retrieval not aligning with the user preference; (2) the absence of supervision for training a passage retrieval module. As a solution, we introduce ESPRESSO, a novel passage retrieval approach for CRS, to effectively tackle the above issues with two core ideas: adaptive item selection and relevance-based groupwise learning. Our extensive experiments show that ESPRESSO effectively resolves issues, achieving up to 36% higher Hit@3 accuracy than the best of 8 competing methods. Additionally, we verify that leveraging passages retrieved by ESPRESSO significantly improves the response quality of CRS.

We focus on the medication recommendation problem aiming to recommend accurate medications for a patient’s current visit. Most existing methods for this problem utilize the patient’s current health status, medications prescribed at her past visits, and an Electronic Health Records (EHR) graph which represents whether medications have been co-prescribed. However, we point out their two limitations: (1) they have difficulty in utilizing only the medications which have been prescribed in health status similar to the patient’s current health status, regardless of whether they are prescribed at her past visits or at other patients’ visits; (2) for two medications that have ever been co-prescribed, their EHR graph does not consider the degree to which one medication is prescribed together when the other is prescribed. To address these two limitations, we propose a novel medication recommendation framework, named HI-DR (pronounced as ‘Hi Doctor’), composed of following two core ideas: (Idea 1) Health status-aware attentIon; (Idea 2) an electronic health recorDs gRaph+. Extensive experiments on real-world datasets demonstrate the significant superiority of HI-DR (up to 18.69% higher accuracy than the best competitor) and the effectiveness of two core ideas in HI-DR.

Graph Neural Networks (GNNs) have become essential tools for graph representation learning in various domains, such as social media and healthcare. However, they often suffer from fairness issues due to inherent biases in node attributes and graph structure, leading to unfair predictions. To address these challenges, we propose a novel GNN framework, DAB-GNN, that Disentangles, Amplifies, and deBiases attribute, structure, and potential biases in the GNN mechanism. DAB-GNN employs a disentanglement and amplification module that isolates and amplifies each type of bias through specialized disentanglers, followed by a debiasing module that minimizes the distance between subgroup distributions to ensure fairness. Extensive experiments on five datasets demonstrate that DAB-GNN significantly outperforms ten state-of-the-art competitors in terms of achieving an optimal balance between accuracy and fairness.

With the increasing size of real-world networks, efficient analysis of large-scale graphs has become an important research area. To this end, we can consider Processing-in-Memory (PIM), which integrates processing units and main memory into a single chip, as a promising solution. Many studies have focused on enabling highly efficient processing of memory-intensive tasks by using PIM's high internal bandwidth. To the best of our knowledge, however, there have been no studies related to the scenarios where the entire graph does not fit in main memory and data movement across storage, memory, and cache should be considered. Motivated by this, we propose RealGraph PIM, a new PIM-based graph engine, that processes large-scale real-world graphs efficiently on top of the original RealGraph, a state-of-the-art CPU-based graph engine. RealGraph PIM employs (1) asynchronous I/O to reduce wasting time in an idle state and (2) column-wise partitioning to reduce CPU workloads, thereby issuing I/O requests more frequently. Experimental results on real-world datasets show that RealGraph PIM outperforms dramatically state-of-the-art graph engines including a naive version of RealGraphPIM.

Real-world networks have high-order relationships among objects and they evolve over time. To capture such dynamics, many works have been studied in a range of fields. Via an in-depth preliminary analysis, we observe two important characteristics of high-order dynamics in real-world networks: high-order relations tend to (O1) have a structural and temporal influence on other relations in a short term and (O2) periodically re-appear in a long term. In this paper, we propose LINCOLN, a method for Learning hIgh-order dyNamiCs Of reaL-world Networks, that employs (1) bi-interactional hyperedge encoding for short-term patterns, (2) periodic time injection and (3) intermediate node representation for long-term patterns. Via extensive experiments, we show that LINCOLN outperforms nine state-of-the-art methods in the dynamic hyperedge prediction task.

Personalized news recommendation aims to deliver news articles aligned with users' interests, serving as a key solution to alleviate the problem of information overload on online news platforms. While prior work has improved interest matching through refined representations of news and users, the following time-related challenges remain underexplored: (C1) leveraging the age of clicked news to infer users' interest persistence, and (C2) modeling the varying lifetime of news across topics and users. To jointly address these challenges, we propose a novel Lifetime-aware Interest Matching framework for nEws recommendation, named LIME, which incorporates three key strategies: (1) User-Topic lifetime-aware age representation to capture the relative age of news with respect to a user-topic pair, (2) Candidate-aware lifetime attention for generating temporally aligned user representation, and (3) Freshness-guided interest refinement for prioritizing valid candidate news at prediction time. Extensive experiments on two real-world datasets demonstrate that LIME consistently outperforms a wide range of state-of-the-art news recommendation methods, and its model agnostic strategies significantly improve recommendation accuracy.

In the literature, various graph embedding methods have been proposed. Although they have pioneered notable techniques in the field, we point out their four drawbacks as follows: (1) inability to consider global graph structure(2) undermining learning quality(3) impairing in/out-degree distributions in directed graphs, and (4) limited applicability. Inspired by these drawbacks, we first propose LINOW, a recursive LI nk-based similarity measure for graphs by utilizing NO des' Weights, which is applicable to both directed and undirected graphs. Then, we provide a matrix form that dramatically accelerates LINOW's computation without approximation. Furthermore, to enhance its scalability, we provide two variants, LINOW-sn and LINOW-bn, to compute similarity scores w.r.t. a single node and a batch of nodes, respectively. Finally, we propose SIGEM, a simple yet effective self-supervised and contrastive-free SI milarity based Graph EM bedding method that employs LINOW-bn to compute similarity scores of nodes in the graph, thereby ranking them. Then, it tries to preserve the original ranks of nodes in the graph within their corresponding vectors in the embedding space, by employing a single-layer neural network. The results of our extensive experiments with eight real-world datasets and thirteen state-of-the-art and conventional embedding methods demonstrate that (1) LINOW-sn and LINOW-bn successfully improve the scalability of naive LINOW(2) LINOW is beneficial to similarity based graph embedding, and (3) SIGEM consistently achieves the highest accuracy in both graph reconstruction and node classification tasks compared to other methods, while it significantly outperforms them in most cases of the link prediction task.

Beyond using multimodal features of items in addition to user-item interactions, researchers have additionally utilized Contrastive Learning (CL) in recent multimedia recommender systems to highly alleviate the data sparsity problem. CL-based methods generate at least two embeddings (i.e., views) for each instance and enrich the information of each instance from various perspectives via the views, thereby alleviating the data sparsity problem. Therefore, CL-based methods have focused on generating views that effectively represent the characteristics of each instance for their downstream tasks. Similarly, CL-based multimedia recommender systems have made efforts to effectively generate their user/item views by leveraging items' multimodal features. However, we point out the following two limitations that they have overlooked in generating their views: (1) they either have not attempted to identify the influence of each modality feature of an item on user-item interactions, or have identified it by randomly masking or dropping user-item interactions, and (2) they have not attempted to identify non-interactions likely to result in interactions in the future. To overcome these limitations, we propose a novel multimedia recommendation framework, named STARLINE, utilizing contraSTive leARning with modaLIty-aware graph refiNEment. Extensive experiments on five real-world datasets validate the effectiveness and validity of STARLINE, especially showing consistently higher accuracy by up to 13.24% compared to the best competitor.

The problem of career trajectory prediction (CTP) aims to predict one's future employer or job position. While several CTP methods have been developed for this problem, we posit that none of these methods (1) jointly considers the mutual ternary dependency between three key units (i.e., user, position, and company) of a career and (2) captures the characteristic shifts of key units in career over time, leading to an inaccurate understanding of the job movement patterns in the labor market. To address the above challenges, we propose a novel solution, named as CAPER, that solves the challenges via sophisticated temporal knowledge graph (TKG) modeling. It enables the utilization of a graph-structured knowledge base with rich expressiveness, effectively preserving the changes in job movement patterns. Furthermore, we devise an extrapolated career reasoning task on TKG for a realistic evaluation. The experiments on a real-world career trajectory dataset demonstrate that CAPER consistently and significantly outperforms four baselines, two recent TKG reasoning methods, and five state-of-the-art CTP methods in predicting one's future companies and positions--i.e., on average, yielding 6.80% and 34.58% more accurate predictions, respectively. The codebase of CAPER is available at https://github.com/Bigdasgit/CAPER.

Recently, searching for information by using search engines such as Google, Bing, and NAVER has become ubiquitous. While they attempt to provide information based on the search queries that users enter, it is not trivial to accurately capture the search intent of users. Motivated by this situation, NAVER Corp., the largest portal company in Korea, has developed a framework named as CATER (Cluster-based Alternative TErm Recommendation) framework that suggests alternative terms ("al-terms,'' in short) for better search outcomes relevant to a user's search intent. We introduce four design considerations (DCs) that were considered when designing and implementing CATER. Then, we describe how our CATER addresses the four DCs by using a clustering stage that dynamically maintains a pool of topic-oriented clusters containing terms, and a recommendation stage that identifies the top-k clusters (i.e., topics) and the top-k al-terms for each cluster. Furthermore, we present the scalable architecture adopted by CATER. Through various offline and online A/B tests using real-world datasets from NAVER, we validate that CATER successfully incorporates all DCs and that all design choices help improve the recommendation accuracy.

Recent works in multimodal recommendations, which leverage diverse modal information to address data sparsity and enhance recommendation accuracy, have garnered considerable interest. Two key processes in multimodal recommendations are modality fusion and representation learning. Previous approaches in modality fusion often employ simplistic attentive or pre-defined strategies at early or late stages, failing to effectively handle irrelevant information among modalities. In representation learning, prior research has constructed heterogeneous and homogeneous graph structures encapsulating user-item, user-user, and item-item relationships to better capture user interests and item profiles. Modality fusion and representation learning were considered as two independent processes in previous work. This paper reveals that these two processes are complementary and can support each other. Specifically, powerful representation learning enhances modality fusion, while effective fusion improves representation quality. Stemming from these two processes, we introduce a COmposite grapH convolutional nEtwork with dual-stage fuSION for the multimodal recommendation, named COHESION. Specifically, it introduces a dual-stage fusion strategy to reduce the impact of irrelevant information, refining all modalities using behavior modality in the early stage and fusing their representations at the late stage. It also proposes a composite graph convolutional network that utilizes user-item, user-user, and item-item graphs to extract heterogeneous and homogeneous latent relationships within users and items. Besides, it introduces a novel adaptive optimization to ensure balanced and reasonable representations across modalities. Extensive experiments on three public datasets demonstrate the significant superiority of COHESION over various competitive baselines.

Existing multimedia recommender systems have made the best efforts to predict user preferences for items by utilizing behavioral similarities between users and the modality features of items a user has interacted with. However, we identify two key limitations in existing methods regarding preferences for modality features: (L1) although preferences for modality features is an important aspect of users' preferences, existing methods only leverage neighbors with similar interactions and do not consider the neighbors who may have similar preferences for modality features while having different interactions; (L2) although modality features of a user and an item may have a complex geometric relationship in the latent space, existing methods overlook and face challenges in precisely capturing this relationship. To address these two limitations, we propose a novel multimedia recommendation framework, named MELON, which is based on two core ideas: (Idea 1) Modality-cEntered embedding extraction; (Idea 2) reLatiOnship-ceNtered embedding extraction. We validate the effectiveness and validity of MELON through extensive experiments with four real-world datasets, showing 10.51% higher accuracy compared to the best competitor in terms of recall@10. The code and dataset of MELON is available at https://github.com/Bigdasgit/MELON.

The goal of Review-Based Recommendation System (RBRS) is to effectively learn the representations of users and items by utilizing review texts in addition to user-item interactions. From user-item interaction graphs widely employed in recommendation systems, recent RBRS methods using graph neural networks (GNNs) obtain the representations by associating each edge between a user and an item with the review information of the user for that item. However, these GNN-based RBRS methods present two main issues: (1) by con- verting each review text into the weight, i.e., single value, of a edge between a user node and an item node, they lose the rich informa- tion about users and items inherent in the review; and (2) by creating only a single general representation for each user, they cannot repre- sent the individual effects of users' likes and dislikes on their ratings for items they have interacted with. To address these problems, we propose a novel GNN-based RBRS, named LETTER, utilizing homo- geneous graphs, i.e., user-user graphs and an item-item graph, to learn general representations of users and items along with users' like and dislike representations. LETTER can learn user and item representations without losing review information by utilizing the proposed homogeneous graphs. Furthermore, LETTER explicitly designs the influence of users' like and dislike representations on their ratings to perform accurate rating predictions. Through ex- periments on six datasets, we verify that the proposed LETTER out- performs nine state-of-the-art RBRSs by up to 23.1%. Our source code is available at https://github.com/Bigdasgit/LETTER.

In e-commerce platforms, profit-aware recommender systems aim to improve the platform's profits while maintaining high overall accuracy by recommending items with high profits as top-ranked items. We explore two issues faced by existing model-based profit-aware approaches (i.e., MBAs) when training recommendation models for profit enhancement. First, existing MBAs tend to inaccurately infer the item ranking without considering the user's current preference for each item through their profit-based weighting scheme. Second, through the point-wise learning-to-rank (LTR), the model is optimized solely for the preference score of each item independently rather than being directly optimized for the overall ranking of items. To tackle these issues, we propose a novel MBA that involves three key steps: (S1) defining the Current Preference incorporated with Profit (i.e., CPP) for items; (S2) classifying items through CPP; and (S3) training the model by list-wise LTR based on CPP. Extensive experimental results using real-world platform datasets demonstrate that our approach improves accuracy by approximately 4% and profits by about 24% compared to the best-competing method.

Personalized news recommendation aims to assist users in finding news articles that align with their interests, which plays a pivotal role in mitigating users' information overload problem. Despite the breakthrough in personalized news recommendation, the following challenges have been rarely explored: (C1) Comprehending manifold intents coupled within a news article, (C2) Differentiating varying post-read preferences of news articles, and (C3) Addressing the cold-start user problem. To tackle these challenges together, we propose a novel personalized news recommendation framework (CROWN) that employs (1) category-guided intent disentanglement for (C1), (2) consistency-based news representation for (C2), and (3) GNN-enhanced hybrid user representation for (C3). Furthermore, we incorporate a category prediction into the training process of CROWN as an auxiliary task for enhancing intent disentanglement. Extensive experiments on two real-world datasets reveal that (1) CROWN outperforms twelve state-of-the-art news recommendation methods and (2) the proposed strategies significantly improve the accuracy of CROWN.

Hypergraphs can naturally modelgroup-wise relations(e.g., a group of users who co-purchase an item) ashyperedges.Hyperedge predictionis to predict future or unobserved hyperedges, which is a fundamental task in many real-world applications (e.g., group recommendation). Despite the recent breakthrough of hyperedge prediction methods, the following challenges have been rarely studied: (C1)How to aggregate the nodes in each hyperedge candidate for accurate hyperedge prediction?and (C2)How to mitigate the inherent data sparsity problem in hyperedge prediction?To tackle both challenges together, in this paper, we propose a novel hyperedge prediction framework ($\mathsf{CASH}$CASH) that employs (1)context-aware node aggregationto precisely capture complex relations among nodes in each hyperedge for (C1) and (2)self-supervised contrastive learningin the context of hyperedge prediction to enhance hypergraph representations for (C2). Furthermore, as for (C2), we propose ahyperedge-aware augmentationmethod to fully exploit the latent semantics behind the original hypergraph and consider both node-level and group-level contrasts (i.e.,dual contrasts) for better node and hyperedge representations. Extensive experiments on six real-world hypergraphs reveal that$\mathsf{CASH}$consistently outperforms all competing methods in terms of the accuracy in hyperedge prediction and each of the proposed strategies is effective in improving the model accuracy of$\mathsf{CASH}$.

We address the medication recommendation problem, which aims to recommend effective medications for a patient's current visit by utilizing information (e.g., diagnoses and procedures) given at the patient's current and past visits. While there exist a number of recommender systems designed for this problem, we point out that they are challenged in accurately capturing the relation (spec., the degree of relevance) between the current and each of the past visits for the patient when obtaining her current health status, which is the basis for recommending medications. To address this limitation, we propose a novel medication recommendation framework, named VITA, based on the following two novel ideas: (1) relevant-Visit selectIon; (2) Target-aware Attention. Through extensive experiments using real-world datasets, we demonstrate the superiority of VITA (spec., up to 5.67% higher accuracy, in terms of Jaccard, than the best competitor) and the effectiveness of its two core ideas. The code is available at https://github.com/jhheo0123/VITA.

The goal of dynamic signed network embedding (DSNE) is to represent the nodes in a dynamic signed network (DSN) as embeddings that preserve the evolving nature of conflicting relationships between nodes. While existing DSNE methods are useful for understanding polarization between users in diverse domains, they fail to consider the concept of a community boundary that contributes to network-wide polarization and lack inductive ability due to their reliance on homophily bias. To address these limitations, we propose a novel DSNE method, named PolarDSN, which learns the evolution of network POLARization and enhances inductive ability for Dynamic Signed Networks. It leverages node-level community boundaries as well as structural characteristics of nodes such as structural isomorphism and temporal transitivity. Experiments on four real-world DSN datasets demonstrate that PolarDSN consistently and significantly outperforms 12 state-of-the-art methods, achieving up to 31.6% and 21.1% improvement in macro-F1 for transductive and inductive settings, respectively. The code is available at https://github.com/kmj0792/PolarDSN.

The Fair Graph Anomaly Detection (FairGAD) problem aims to accurately detect anomalous nodes in an input graph while avoiding biased predictions against individuals from sensitive subgroups. However, the current literature does not comprehensively discuss this problem, nor does it provide realistic datasets that encompass actual graph structures, anomaly labels, and sensitive attributes. To bridge this gap, we introduce a formal definition of the FairGAD problem and present two novel datasets constructed from the social media platforms Reddit and Twitter. These datasets comprise 1.2 million and 400,000 edges associated with 9,000 and 47,000 nodes, respectively, and leverage political leanings as sensitive attributes and misinformation spreaders as anomaly labels. We demonstrate that our FairGAD datasets significantly differ from the synthetic datasets used by the research community. Using our datasets, we investigate the performance-fairness trade-off in nine existing GAD and non- graph AD methods on five state-of-the-art fairness methods. Code and datasets are available at https://github.com/nigelnnk/FairGAD.

With the prevalence of social media platforms, accurately identifying the same users across different networks through network alignment has become crucial. Existing methods often struggle due to sparse or absent user-identifiable information (node attributes), highlighting the need for augmenting node attributes. However, research on attribute augmentation remains largely under-explored. In this study, we aim to design augmented attributes that enhance network alignment by reflecting three key structural C haracteristics: (C1) global structural characteristic, reflects the global network structure; (C2) seed-based structural characteristic, leverages cross-network structural information associated with seed nodes; (C3) multi-aspect structural characteristic, employs diverse structural relationship measures. To this end, we propose a novel approach for designing trustworthy Augmented Seed-baSed and multI-aspect STructurAl iNformaTion (ASSISTANT) attributes. To enhance alignment performance, we also present a learning module that utilizes a gate mechanism to select the most effective measure dynamically. Extensive experiments across various datasets demonstrate the following: 1) Our network alignment framework, which includes a gate mechanism module, significantly outperforms state-of-the-art methods in alignment accuracy; 2) other state-of-the-art methods using ASSISTANT attributes as input substantially boosts their own alignment accuracy; and 3) using only ASSISTANT attributes without any training process also leads to effective alignment, showcasing their high trustworthiness.

Traffic speed prediction is a crucial task for optimizing navigation systems and reducing traffic congestion. Although there have been efforts to improve the accuracy of speed prediction by incorporating auxiliary features, such as traffic flow, weather, and time, types of auxiliary features are limited and their detailed relationships with speed have not been explored yet. In our study, we present the individual spatio-temporal (IST) dependencies on flow and speed, and characterize three types of IST-dependencies with the flow-to-flow, speed-to-speed, and flow-to-speed graphs. Then, we propose Auxiliary feature-aided Attention Network (ARIAN), a novel approach to judiciously learning the degrees of IST-dependencies with the three graphs and predicting the future speed by leveraging various auxiliary features. Through comprehensive experiments using 3 real-world datasets, we validate the superiority of ARIAN over 10 state-of-the-art methods and the effectiveness of each auxiliary feature and each dependency learner in ARIAN.

In this paper, we focus on multimedia recommender systems using graph convolutional networks (GCNs) where the multimodal features as well as user-item interactions are employed together. Our study aims to exploit multimodal features more effectively in order to accurately capture users' preferences for items. To this end, we point out following two limitations of existing GCN-based multimedia recommender systems: (L1) although multimodal features of interacted items by a user can reveal her preferences on items, existing methods utilize GCN designed to focus only on capturing collaborative signals, resulting in insufficient reflection of the multimodal features in the final user/item embeddings; (L2) although a user decides whether to prefer the target item by considering its multimodal features, existing methods represent her as only a single embedding regardless of the target item's multimodal features and then utilize her embedding to predict her preference for the target item. To address the above issues, we propose a novel multimedia recommender system, named MONET, composed of following two core ideas: modality-embracing GCN (MeGCN) and target-aware attention. Through extensive experiments using four real-world datasets, we demonstrate i) the significant superiority of MONET over seven state-of-the-art competitors (up to 30.32% higher accuracy in terms of recall@20, compared to the best competitor) and ii) the effectiveness of the two core ideas in MONET. All MONET codes are available at https://github.com/Kimyungi/MONET.

To recommend the points of interest (POIs) that a user would check-in next, most deep-learning (DL)-based existing studies have employed random negative (RN) sampling during model training. In this paper, we claim and validate that, as the training proceeds, such an RN sampling in reality performs as sampling easy negative (EN) POIs (i.e., EN sampling) that a user was highly unlikely to check-in at her check-in time point. Furthermore, we verify that EN sampling is more disadvantageous in improving the accuracy than sampling hard negative (HN) POIs (i.e., HN sampling) that a user was highly likely to check-in. To address this limitation, we present the novel concept of the Degree of Positiveness (DoP), which can be formulated by two factors: (i) the degree to which a POI has the characteristics preferred by a user; (ii) the geographical distance between a user and a POI. Then, we propose a new model-training scheme based on HN sampling by using DoP. Using real-world datasets (i.e., NYC, TKY, and Brightkite), we demonstrate that all the state-of-the-art models trained by our scheme showed dramatic improvements in accuracy by up to about 82.8%.

In this paper, we first define information loss that occurs in the hypergraph expansion and then propose a novel framework, named MILEAGE, to evaluate hypergraph expansion methods by measuring their degree of information loss. MILEAGE employs the following four steps: (1) expanding a hypergraph; (2) performing the unsupervised representation learning on the expanded graph; (3) reconstructing a hypergraph based on vector representations obtained; and (4) measuring MILEAGE-score (i.e., mileage) by comparing the reconstructed and the original hypergraphs. To demonstrate the usefulness of MILEAGE, we conduct experiments via downstream tasks on three levels (i.e., node, hyperedge, and hypergraph): node classification, hyperedge prediction, and hypergraph classification on eight real-world hypergraph datasets. Through the extensive experiments, we observe that information loss through hypergraph expansion has a negative impact on downstream tasks and MILEAGE can effectively evaluate hypergraph expansion methods through the information loss and recommend a new method that resolves the problems of existing ones.

Considerable efforts are currently underway to mitigate the negative impacts of echo chambers, such as increased susceptibility to fake news and resistance towards accepting scientific evidence. Prior research has presented the development of computer systems that support the consumption of news information from diverse political perspectives to mitigate the echo chamber effect. However, existing studies still lack the ability to effectively support the key processes of news information consumption and quantitatively identify a political stance towards the information. In this paper, we present HearHere, an AI-based web system designed to help users accommodate information and opinions from diverse perspectives. HearHere facilitates the key processes of news information consumption through two visualizations. Visualization 1 provides political news with quantitative political stance information, derived from our graph-based political classification model, and users can experience diverse perspectives (Hear). Visualization 2 allows users to express their opinions on specific political issues in a comment form and observe the position of their own opinions relative to pro-liberal and pro-conservative comments presented on a map interface (Here). Through a user study with 94 participants, we demonstrate the feasibility of HearHere in supporting the consumption of information from various perspectives. Our findings highlight the importance of providing political stance information and quantifying users' political status as a means to mitigate political polarization. In addition, we propose design implications for system development, including the consideration of demographics such as political interest and providing users with initiatives.

The problem of representing nodes in a signed network as low-dimensional vectors, known as signed network embedding (SNE), has garnered considerable attention in recent years. While several SNE methods based on graph convolutional networks (GCNs) have been proposed for this problem, we point out that they significantly rely on the assumption that the decades-old balance theory always holds in the real-world. To address this limitation, we propose a novel GCN-based SNE approach, named as TrustSGCN, which corrects for incorrect embedding propagation in GCN by utilizing the trustworthiness on edge signs for high-order relationships inferred by the balance theory. The proposed approach consists of three modules: (M1) generation of each node’s extended ego-network; (M2) measurement of trustworthiness on edge signs; and (M3) trustworthiness-aware propagation of embeddings. Specifically, TrustSGCN leverages topological information to measure trustworthiness on edge sign for high-order relationships inferred by balance theory. It then considers structural properties inherent to an input network, such as the ratio of triads, to correct for incorrect embedding propagation. Furthermore, TrustSGCN learns the node embeddings by leveraging two well-known social theories, i.e., balance and status, to jointly preserve the edge sign and direction between nodes connected by existing edges in the embedding space. The experiments on six real-world signed network datasets demonstrate that TrustSGCN consistently outperforms six state-of-the-art GCN-based SNE methods. The code is available at https://github.com/kmj0792/TrustSGCN .

From the observation that users reading news tend to not click outdated news, we propose the notion of 'lifetime' of news, with two hypotheses: (i) news has a shorter lifetime, compared to other types of items such as movies or e-commerce products; (ii) news only competes with other news whose lifetimes have not ended, and which has an overlapping lifetime (i.e., limited competitions). By further developing the characteristics of the lifetime of news, then we present a novel approach for news recommendation, namely, Lifetime-Aware News reCommEndeR System (LANCER) that carefully exploits the lifetime of news during training and recommendation. Using real-world news datasets (e.g., Adressa and MIND), we successfully demonstrate that state-of-the-art news recommendation models can get significantly benefited by integrating the notion of lifetime and LANCER, by up to about 40% increases in recommendation accuracy.

Double-vector embedding methods capture the asymmetric information in directed graphs first, and then preserve them in the embedding space by providingtwo latent vectors, i.e., source and target, per node. Although these methods are known to besuperior to the single-vector ones (i.e., providing asingle latent vector per node), wepoint out their three drawbacks as inability to preserve asymmetry on NU-paths, inability to preserve global nodes similarity, and impairing in/out-degree distributions. To address these, we first proposeCRW, anovel similarity measure for graphs that considers contributions ofboth in-links and out-links in similarity computation,without ignoring their directions. Then, we proposeELTRA, aneffective double-vector embedding method to preserve asymmetric information in directed graphs. ELTRA computesasymmetry preserving proximity scores (AP-scores) by employing CRW in which the contribution of out-links and in-links in similarity computation isupgraded anddowngraded, respectively. Then, for every node u, ELTRA selects its top-tclosest nodes based on AP-scores andconforms theranks of their corresponding target vectors w.r.t u's source vector in the embedding space to theiroriginal ranks. Our extensive experimental results withseven real-world datasets andsixteen embedding methods show that (1) CRWsignificantly outperforms Katz and RWR in computing nodes similarity in graphs, (2) ELTRAoutperforms the existing state-of-the-art methods in graph reconstruction, link prediction, and node classification tasks.

Sparse generalized matrix-matrix multiplication (SpGEMM) is a fundamental operation for real-world network analysis. With the increasing size of real-world networks, the single-machine-based SpGEMM approach cannot perform SpGEMM on large-scale networks, exceeding the size of main memory (i.e., not scalable). Although the distributed-system-based approach could handle large-scale SpGEMM based on multiple machines, it suffers from severe inter-machine communication overhead to aggregate results of multiple machines (i.e., not efficient). To address this dilemma, in this paper, we propose a novel storage-based SpGEMM approach (SAGE) that stores given networks in storage (e.g., SSD) and loads only the necessary parts of the networks into main memory when they are required for processing via a 3-layer architecture. Furthermore, we point out three challenges that could degrade the overall performance of SAGE and propose three effective strategies to address them: (1) block-based workload allocation for balancing workloads across threads, (2) in-memory partial aggregation for reducing the amount of unnecessarily generated storage-memory I/Os, and (3) distribution-aware memory allocation for preventing unexpected buffer overflows in main memory. Via extensive evaluation, we verify the superiority of SAGE over existing SpGEMM methods in terms of scalability and efficiency.

As the number of TV shows increases, designing recommendation systems to provide users with their favorable TV shows becomes more important. In a TV show domain, watching a TV show (i.e., giving implicit feedback to the show) among the TV shows broadcast at the same time frame implies that the currently watching show is the winner in the competition with others (i.e., losers). However, in previous studies, such a notion of limited competitions has not been considered in estimating the user’s preferences for TV shows. In this paper, we propose a new recommendation framework to take this new notion into account based on pair-wise models. Our framework is composed of the following ideas: (i) identify winners and losers by determining pairs of competing TV shows; (ii) learn the pairs of competing TV shows based on the confidence for the pair-wise preference between the winner and the loser; (iii) recommend the most favorable TV shows by considering the time factors with respect to users and TV shows. Using a real-world TV show dataset, our experimental results show that our proposed framework consistently improves the accuracy of recommendation by up to 38%, compared with the best state-of-the-art method. The code and datasets of our framework are available in an external link (https://github.com/hongkyun-bae/tvshow_rs).

Sparse general matrix-matrix multiplication (SpGEMM) is a major kernel in various emerging applications, such as database management systems, deep learning, graph analysis, and recommendation systems. Since SpGEMM requires extensive computation, many SpGEMM techniques have been implemented based on graphics processing units (GPUs) to exploit massive data parallelism completely. However, traditional SpGEMM techniques usually do not fully utilize the GPU because most non-zero elements of the target sparse matrices exist in a few hub nodes, and non-hub nodes barely have non-zero elements. The data-related characteristics (power law) result in a significant degradation in performance because of the load imbalance between the GPU cores and the low utilization of each core. Many attempts have been made through recent implementations to solve this problem using smart pre-/post-processing. However, the net performance hardly improves and sometimes even deteriorates owing to the large overheads. Additionally, non-hub nodes are inherently not suitable for GPU computing, even after optimization. Furthermore, the performance is no longer dominated by kernel execution, but by data transfers such as device-to-host (D2H) data transfers and file I/Os, owing to the rapid growth in the computing power of GPUs and input data size.Therefore, this work proposes a Dynamic Block Distributor (DBD), a novel full-system-level SpGEMM orchestration framework for heterogeneous systems, improving the overall performance by enabling an efficient CPU-GPU collaboration and further minimizing the overhead in data transfer between all the system elements. This framework first divides the target matrix into smaller blocks and then offloads the computation of each block to an appropriate computing unit between a GPU and CPU based on its workload type and the status of resource utilization at runtime. It also minimizes the overhead in data transfer with simple but suitable techniques, such as Row Collecting, I/O Overlapping, and I/O Binding. Our experiments showed that this framework increased the execution latency of SpGEMM, which included both the kernel execution and D2H transfers, by 3.24x on average, and the overall execution time by 2.07x on average, compared to that of the baseline cuSPARSE library.

For high-quality conversational recommender systems (CRS), it is important to recommend the suitable items by capturing the items' features mentioned in the dialog and to explain the appropriate ones among the various features of the recommended item. We argue that the CRS model should be a domain-expert who is (1) knowledgeable about the relationships between items and their various features and (2) able to explain the recommended item with its features relevant to dialog context. To this end, we propose a novel framework, named as LATTE, to pre-train each core module in CRS (i.e., the recommendation and the conversation module) through abundant external data. For the recommendation module, we pre-train the recommendation module to comprehensively understand the relationships between items and their various features by leveraging both multi-reviews and a knowledge graph. For pre-training the conversation module, we create the synthetic dialogs, which contain responses providing the explanation relevant to the dialog context by using all the items' features and dialog templates. Through extensive experiments on two public CRS datasets, we demonstrate that LATTE exhibits (1) the effectiveness of each module in LATTE, (2) the superiority over 7 state-of-the art methods, and (3) the interpretations based on visualization.

The problem of signed network embedding (SNE) aims to represent nodes in a given signed network as low-dimensional vectors. While several SNE methods based on graph convolutional networks (GCN) have been proposed, we point out that they significantly rely on the assumption that the decades-old balance theory always holds in the real world. To address this limitation, we propose a novel GCN-based SNE approach, named as TrustSGCN, which measures the trustworthiness on edge signs for high-order relationships inferred by balance theory and corrects incorrect embedding propagation based on the trustworthiness. The experiments on four real-world signed network datasets demonstrate that TrustSGCN consistently outperforms five state-of-the-art GCN-based SNE methods. The code is available at https://github.com/kmj0792/TrustSGCN.

Similarity-based embedding methods have introduced a new perspective on graph embedding by conforming the similarity distribution of latent vectors in the embedding space to that of nodes in the graph; they show significant effectiveness over conventional embedding methods in various machine learning tasks. In this paper, we first point out the three drawbacks of existing similarity-based embedding methods: inaccurate similarity computation, conflicting optimization goal, and impairing in/out-degree distributions. Then, motivated by these drawbacks, we propose AdaSim*, a novel similarity measure for graphs that is conducive to the similarity-based graph embedding. We finally propose GELTOR, an effective embedding method that employs AdaSim* as a node similarity measure and the concept of learning-to-rank in the embedding process. Contrary to existing methods, GELTOR does not learn the similarity scores distribution; instead, for any target node, GELTOR conforms the ranks of its top-t similar nodes in the embedding space to their original ranks based on AdaSim* scores. We conduct extensive experiments with six real-world datasets to evaluate the effectiveness of GELTOR in graph reconstruction, link prediction, and node classification tasks. Our experimental results show that (1) AdaSim* outperforms AdaSim, RWR, and MCT in computing nodes similarity in graphs, (2) our GETLOR outperforms existing state-of-the-arts and conventional embedding methods in most cases of the above machine learning tasks, thereby implying that learning-to-rank is beneficial to graph embedding.

The political stance prediction for news articles has been widely studied to mitigate the echo chamber effect – people fall into their thoughts and reinforce their pre-existing beliefs. The previous works for the political stance problem focus on (1) identifying political factors that could reflect the political stance of a news article and (2) capturing those factors effectively. Despite their empirical successes, they are not sufficiently justified in terms of how effective their identified factors are in the political stance prediction. Motivated by this, in this work, we conduct a user study to investigate important factors in political stance prediction, and observe that the context and tone of a news article (implicit) and external knowledge for real-world entities appearing in the article (explicit) are important in determining its political stance. Based on this observation, we propose a novel knowledge-aware approach to political stance prediction (KHAN), employing (1) hierarchical attention networks (HAN) to learn the relationships among words and sentences in three different levels and (2) knowledge encoding (KE) to incorporate external knowledge for real-world entities into the process of political stance prediction. Also, to take into account the subtle and important difference between opposite political stances, we build two independent political knowledge graphs (KG) (i.e., KG-lib and KG-con) by ourselves and learn to fuse the different political knowledge. Through extensive evaluations on three real-world datasets, we demonstrate the superiority of KHAN in terms of (1) accuracy, (2) efficiency, and (3) effectiveness.

The goal of directed network embedding is to represent the nodes in a given directed network as embeddings that preserve the asymmetric relationships between nodes. While a number of directed network embedding methods have been proposed, we empirically show that the existing methods lack out-of-distribution generalization abilities against degree-related distributional shifts. To mitigate this problem, we propose ODIN (Out-of-Distribution Generalized Directed Network Embedding), a new directed NE method where we model multiple factors in the formation of directed edges. Then, for each node, ODIN learns multiple embeddings, each of which preserves its corresponding factor, by disentangling interest factors and biases related to in- and out-degrees of nodes. Our experiments on four real-world directed networks demonstrate that disentangling multiple factors enables ODIN to yield out-of-distribution generalized embeddings that are consistently effective under various degrees of shifts in degree distributions. Specifically, ODIN universally outperforms 9 state-of-the-art competitors in 2 LP tasks on 4 real-world datasets under both identical distribution (ID) and non-ID settings. The code is available at https://github.com/hsyoo32/odin.

In this article, we propose a framework for embedding-based community detection on signed networks, namelyAdversarial learning ofBalanced triangle forCommunity detection, in short${{\sf ABC}}$. It first represents all the nodes of a signed network as vectors in low-dimensional embedding space and conducts a clustering algorithm (e.g.,k-means) on vectors, thereby detecting a community structure in the network. When performing the embedding process,${{\sf ABC}}$learns only the edges belonging to balanced triangles whose edge signs follow the balance theory, significantly excluding noise edges in learning. To address the sparsity of balanced triangles in a signed network,${{\sf ABC}}$learns not only the edges in balancedreal-triangles but those in balancedvirtual-triangles that do not actually exist but are produced by our generator. Finally,${{\sf ABC}}$employs adversarial learning to generate more-realistic balanced virtual-triangles with less noise edges. Through extensive experiments using seven real-world networks, we validate the effectiveness of (1) learning edges belonging to balanced real/virtual-triangles and (2) employing adversarial learning for signed network embedding. We show that${{\sf ABC}}$consistently and significantly outperforms the state-of-the-art community detection methods in all datasets.

Many cyberattacks start with disseminating phishing URLs. When clicking these phishing URLs, the victim's private information is leaked to the attacker. There have been proposed several machine learning methods to detect phishing URLs. However, it still remains under-explored to detect phishing URLs with evasion, i.e., phishing URLs that pretend to be benign by manipulating patterns. In many cases, the attacker i) reuses prepared phishing web pages because making a completely brand-new set costs non-trivial expenses, ii) prefers hosting companies that do not require private information and are cheaper than others, iii) prefers shared hosting for cost efficiency, and iv) sometimes uses benign domains, IP addresses, and URL string patterns to evade existing detection methods. Inspired by those behavioral characteristics, we present a network-based inference method to accurately detect phishing URLs camouflaged with legitimate patterns, i.e., robust to evasion. In the network approach, a phishing URL will be still identified as phishy even after evasion unless a majority of its neighbors in the network are evaded at the same time. Our method consistently shows better detection performance throughout various experimental tests than state-of-the-art methods, e.g., F-1 of 0.891 for our method vs. 0.840 for the best feature-based method.

A graph, consisting of vertices and edges, has been widely adopted for network analysis. Recently, with the increasing size of real-world networks, many graph engines have been studied to efficiently process large-scale real-world graphs. RealGraph, one of the state-of-the-art single-machine-based graph engines, efficiently processes storage-to-memory I/Os by considering unique characteristics of real-world graphs. Via an in-depth analysis of RealGraph, however, we found that there is still a chance for more performance improvement in the computation part of RealGraph despite its great I/O processing ability. Motivated by this, in this paper, we propose RealGraphGPU, a GPU-based single-machine graph engine. We design the core components required for GPU-based graph processing and incorporate them into the architecture of RealGraph. Further, we propose two optimizations that successfully address the technical issues that could cause the performance degradation in the GPU-based graph engine: buffer pre-checking and edge-based workload allocation strategies. Through extensive evaluation with 6 real-world datasets, we demonstrate that (1) RealGraphGPU improves RealGraph by up to 546%, (2) RealGraphGPU outperforms existing state-of-the-art graph engines dramatically, and (3) the optimizations are all effective in large-scale graph processing.

This paper focuses on the problem of forecasting daily traffic of new roads, where very little data is available for prediction. We propose a novel prediction model based on Generative Adversarial Networks (GAN) that learns the subtle patterns of the changes in the traffic flow according to the various contextual factors. Then the trained generator makes a prediction via generating a realistic traffic flow data of a target new road given its weather and day type. Both the quantitative and qualitative results of our extensive experiments indicate the effectiveness of our method.

In a news recommender system, a user tends to click on a news article if she is interested in its topic understood by looking at its title. Such a behavior is possible since, when viewing the title, humans naturally think of the contextual meaning of each title word by leveraging their own background knowledge. Motivated by this, we propose a novel personalized news recommendation framework CAST (Context-aware Attention network with a Selection module for Title word representation), which is capable of enriching title words by leveraging body text that fully provides the whole content of a given article as the context. Through extensive experiments, we demonstrate (1) the effectiveness of core modules in CAST, (2) the superiority of CAST over 9 state-of-the-art news recommendation methods, and (3) the interpretability with CAST.

We address the multimedia recommendation problem, which utilizes items' multimodal features, such as visual and textual modalities, in addition to interaction information. While a number of existing multimedia recommender systems have been developed for this problem, we point out that none of these methods individually capture the influence of each modality at the interaction level. More importantly, we experimentally observe that the learning procedures of existing works fail to preserve the intrinsic modality-specific properties of items. To address above limitations, we propose an accurate multimedia recommendation framework, named MARIO, based on modality-aware attention and modality-preserving decoders. MARIO predicts users' preferences by considering the individual influence of each modality on each interaction while obtaining item embeddings that preserve the intrinsic modality-specific properties. The experiments on four real-life datasets demonstrate that MARIO consistently and significantly outperforms seven competitors in terms of the recommendation accuracy: MARIO yields up to 14.61% higher accuracy, compared to the best competitor.

Spatio-temporal models, which combine GNNs (Graph Neural Networks) and RNNs (Recurrent Neural Networks), have shown state-of-the-art accuracy in traffic speed prediction. However, we find that they consider the spatial and temporal dependencies between speeds separately in the two (i.e., space and time) dimensions, thereby unable to exploit the joint-dependencies of speeds in space and time. In this paper, with the evidence via preliminary analysis, we point out the importance of considering individual dependencies between two speeds from all possible points in space and time for accurate traffic speed prediction. Then, we propose an Individual Spatio-Temporal graph (IST-graph) that represents the Individual Spatio-Temporal dependencies (IST-dependencies) very effectively and a Spatio-Temporal Graph ATtention network (ST-GAT), a novel model to predict the future traffic speeds based on the IST-graph and the attention mechanism. The results from our extensive evaluation with five real-world datasets demonstrate (1) the effectiveness of the IST-graph in modeling traffic speed data, (2) the superiority of ST-GAT over 5 state-of-the-art models (i.e., 2-33% gains) in prediction accuracy, and (3) the robustness of our ST-GAT even in abnormal traffic situations.

Many global automakers strive to develop technologies towards the next-generation of intelligent transportation systems (ITS). One of the primary goals of ITS is predicting future traffic speeds to optimize a driver's route, which can lead to not only alleviating traffic flow but also increasing user satisfaction with an ITS service. While prior studies have applied deep learning models to traffic speed prediction and improved model performance, existing models did not well capture abrupt speed changes. In this paper, we propose a novel model, named as adversarial prediction of traffic speed (APOTS), based on adversarial training, data augmentation, and hybrid deep learning modeling. Through the experiments with real traffic data provided by Hyundai Motor Company, we demonstrate that APOTS effectively learns dynamics of traffic speed changes and predicts traffic speed up to 40% higher in accuracy than existing prediction models.

Online news providers such as Google News, Bing News, and NAVER News collect a large number of news articles from a variety of presses and distribute these articles to users via their portals. Dynamic nature of a news domain causes the problem of information overload that makes it difficult for a user to find her preferable news articles. Motivated by this situation, NAVER Corp., the largest portal company in South Korea, identified four design considerations (DCs) for news recommendation that reflect the unique characteristics of a news domain. In this paper, we introduce a large-scale news recommender system named as AiRS, present how it jointly leverages the four DCs for NAVER News service. Specifically, AiRS first generates candidate articles for recommendation to a target user based on collaborative filtering (CF), quality estimation (QE), and social impact (SI) models; then, it ranks the candidate articles based on the scores computed by considering their multi-type feature scores (e.g., user's section preference and article's recency), finally recommending the top-$k$news articles that a target user is likely to prefer. Also, we present how to build the architecture for online deployment of AiRS at NAVER News. Through extensive offline and online A/B tests using the real-world datasets, we validate that AiRS successfully reflects all of the DCs into the news recommendation process, all design choices employed in AiRS help improve the recommendation accuracy, and AiRS significantly outperforms five state-of-the-art news recommendation approaches in terms of accuracy.

The goal of temporal knowledge graph embedding (TKGE) is to represent the entities and relations in a given temporal knowledge graph (TKG) as low-dimensional vectors (i.e., embeddings), which preserve both semantic information and temporal dynamics of the factual information. In this paper, we posit that the intrinsic difficulty of existing TKGE methods lies in the lack of information in KG snapshots with timestamps, each of which contains the facts that co-occur at a specific timestamp. To address this challenge, we propose a novel self-supervised TKGE approach, THOR (Three-tower grapH cOnvolution netwoRks (GCNs)), which extracts latent knowledge from TKGs by jointly leveraging both temporal and atemporal dependencies between entities and the structural dependency between relations. THOR learns the embeddings of entities and relations Our experiments on three real-world datasets demonstrate that THOR significantly outperforms 13 competitors in terms of TKG completion tasks. The codebase of THOR is available at https://github.com/EJHyun/THOR.

There were fierce debates on whether the non-linear embedding propagation of GCNs is appropriate to GCN-based recommender systems. It was recently found that the linear embedding propagation shows better accuracy than the non-linear embedding propagation. Since this phenomenon was discovered especially in recommender systems, it is required that we carefully analyze the linearity and non-linearity issue. In this work, therefore, we revisit the issues of i) which of the linear or non-linear propagation is better and ii) which factors of users/items decide the linearity/non-linearity of the embedding propagation. We propose a novel Hybrid method of linear and non-linear collaborative filtering method (HMLET, pronounced as Hamlet). In our design, there exist both linear and non-linear propagation steps, when processing each user or item node, and our gating module chooses one of them, which results in a hybrid model of the linear and non-linear GCN-based collaborative filtering (CF). The proposed model yields the best accuracy in three public benchmark datasets. Moreover, we classify users/items into the following three classes depending on our gating modules' selections: Full-Non-Linearity (FNL), Partial-Non-Linearity (PNL), and Full-Linearity (FL). We found that there exist strong correlations between nodes' centrality and their class membership, i.e., important user/item nodes exhibit more preferences towards the non-linearity during the propagation steps. To our knowledge, we are the first who design a hybrid method and report the correlation between the graph centrality and the linearity/non-linearity of nodes. All HMLET codes and datasets are available at: https://github.com/qbxlvnf11/HMLET.

Explainable recommendation has gained great attention in recent years. A lot of work in this research line has chosen to use the knowledge graphs (KG) where relations between entities can serve as explanations. However, existing studies have not considered sentiment on relations in KG, although there can be various types of sentiment on relations worth considering (e.g., a user's satisfaction on an item). In this paper, we propose a novel recommendation framework based on KG integrated with sentiment analysis for more accurate recommendation as well as more convincing explanations. To this end, we first construct a Sentiment-Aware Knowledge Graph (namely, SAKG) by analyzing reviews and ratings on items given by users. Then, we perform item recommendation and reasoning over SAKG through our proposed Sentiment-Aware Policy Learning (namely, SAPL) based on a reinforcement learning strategy. To enhance the explainability for end-users, we further developed an interactive user interface presenting textual explanations as well as a collection of reviews related with the discovered sentiment. Experimental results on three real-world datasets verified clear improvements on both the accuracy of recommendation and the quality of explanations.

The directed network embedding problem is to represent the nodes in a given directed network as embeddings (i.e., low-dimensional vectors) that preserve the asymmetric relationships between nodes. While a number of approaches have been developed for this problem, we point out that existing approaches commonly face difficulties in accurately preserving asymmetric proximities between nodes in a sparse network containing a large number of low out- and in-degree nodes. In this paper, we focus on addressing this intrinsic difficulty caused by the lack of information. We first introduce the concept of virtual negative edges (VNEs), which represent latent negative relationships between nodes. Based on the concept, we propose a novel DIrected NE approach with VIrtual Negative Edges, named as DIVINE. DIVINE carefully decides the number and locations of VNEs to be added to the input network. Once VNEs are added, DIVINE learns embeddings by exploiting both the signs and directions of edges. Our experiments on four real-world directed networks demonstrate that adding VNEs alleviates the lack of information about low-degree nodes, thereby enabling DIVINE to yield high-quality embeddings that accurately capture asymmetric proximities between nodes. Specifically, the embeddings obtained by DIVINE lead to up to 10.16% more accurate link prediction, compared to those obtained by state-of-the-art competitors.

A large-batch training with data parallelism is a widely adopted approach to efficiently train a large deep neural network (DNN) model. Large-batch training, however, often suffers from the problem of the model quality degradation because of its fewer iterations. To alleviate this problem, in general, learning rate (lr) scaling methods have been applied, which increases the learning rate to make an update larger at each iteration. Unfortunately, however, we observe that large-batch training with state-of-the-art lr scaling methods still often degrade the model quality when a batch size crosses a specific limit, rendering such lr methods less useful. To this phenomenon, we hypothesize that existing lr scaling methods overlook the subtle but important differences across “layers” in training, which results in the degradation of the overall model quality. From this hypothesis, we propose a novel approach (LENA) toward the learning rate scaling for large-scale DNN training, employing: (1) a layer-wise adaptive lr scaling to adjust lr for each layer individually, and (2) a layer-wise state-aware warm-up to track the state of the training for each layer and finish its warm-up automatically. The comprehensive evaluation with variations of batch sizes demonstrates that LENA achieves the target accuracy (i.e., the accuracy of single-worker training): (1) within the fewest iterations across different batch sizes (up to 45.2% fewer iterations and 44.7% shorter time than the existing state-of-the-art method), and (2) for training very large-batch sizes, surpassing the limits of all baselines.

As an emotion plays an important role in people’s everyday lives and is often mirrored in their social media use, extensive research has been conducted to characterize and model emotions from social media data. However, prior research has not sufficiently considered trends of social media use—the increasing use of images and the decreasing use of text—nor identified the features of images in social media that are likely to be different from those in non-social media. Our study aims to fill this gap by (1) considering the notion of visual hints that depict contextual information of images, (2) presenting their characteristics in positive or negative emotions, and (3) demonstrating their effectiveness in emotion prediction modeling through an in-depth analysis of their relationship with the text in the same posts. The results of our experiments showed that our visual hint-based model achieved 20% improvement in emotion prediction, compared with the baseline. In particular, the performance of our model was comparable with that of the text-based model, highlighting not only a strong relationship between visual hints of the image and emotion, but also the potential of using only images for emotion prediction which well reflects current and future trends of social media use.

Graph engines have been used in many applications to handle big graphs efficiently. The majority of the research to improve their performance has focused primarily on the design of efficient graph processing. This paper claims,however,the focus should be given also to graph storage design. This is because good storage design can improve both CPU performance and I/O performance of graph engines. In this paper,we propose an efficient data layout for single-machine based graph engines. We identify the common node access pattern of the graph algorithms running on single-machine based graph engines. Based on this finding,we propose the breadth-first (BF) data layout which places the nodes processed together in the same or adjacent storage space so that they can be accessed together as much as possible. The experimental results show that the BF data layout improves both CPU and I/O performances significantly in all single-machine based graph engines.

In this demo, we show MANIAC, a MAN-machIne collaborative system for malware Author Classification. It is developed to fight a number of author groups who have been generating lots of new malwares by sharing source code within a group and exploiting evasive schemes such as polymorphism and metamorphism. Notably, MANIAC allows users to intervene in the model's classification of malware authors with high uncertainty. It also provides effective interfaces and visualizations with users to achieve maximum classification accuracy with minimum human labor.

In the literature, various link-based similarity measures such as Adamic/Adar (in short Ada), SimRank, and random walk with restart (RWR) have been proposed. Contrary to SimRank and RWR, Ada is a non-recursive measure, which exploits the local graph structure in similarity computation. Motivated by Ada's promising results in various graph-related tasks, along with the fact that SimRank is a recursive generalization of the co -citation measure, in this paper, we propose AdaSim, a recursive similarity measure based on the Ada philosophy. Our AdaSim provides identical accuracy to that of Ada on the first iteration and it is applicable to both directed and undirected graphs. To accelerate our iterative form, we also propose a matrix form that is dramatically faster while providing the exact AdaSim scores. We conduct extensive experiments with five real-world datasets to evaluate both the effectiveness and efficiency of our AdaSim in comparison with those of existing similarity measures and graph embedding methods in the task of similarity computation of nodes. Our experimental results show that 1) AdaSim significantly improves the effectiveness of Ada and outperforms other competitors, 2) its efficiency is comparable to that of SimRank* while being better than the others, 3) AdaSim is not sensitive to the parameter tuning, and 4) similarity measures are better than embedding methods to compute similarity of nodes.

To speed up the training of massive deep neural network (DNN) models, distributed training has been widely studied. In general, a centralized training, a type of distributed training, suffers from the communication bottleneck between a parameter server (PS) and workers. On the other hand, a decentralized training suffers from increased parameter variance among workers that causes slower model convergence. Addressing this dilemma, in this work, we propose a novel centralized training algorithm, ALADDIN, employing "asymmetric" communication between PS and workers for the PS bottleneck problem and novel updating strategies for both local and global parameters to mitigate the increased variance problem. Through a convergence analysis, we show that the convergence rate of ALADDIN is O(1 ønk ) on the non-convex problem, where n is the number of workers and k is the number of training iterations. The empirical evaluation using ResNet-50 and VGG-16 models demonstrates that (1) ALADDIN shows significantly better training throughput with up to 191% and 34% improvement compared to a synchronous algorithm and the state-of-the-art decentralized algorithm, respectively, (2) models trained by ALADDIN converge to the accuracies, comparable to those of the synchronous algorithm, within the shortest time, and (3) the convergence of ALADDIN is robust under various heterogeneous environments.

In this paper, we propose a framework for embedding-based community detection on signed networks. It first represents all the nodes of a signed network as vectors in low-dimensional embedding space and conducts a clustering algorithm (e.g., k-means) on vectors, thereby detecting a community structure in the network. When performing the embedding process, our framework learns only the edges belonging to balanced triangles whose edge signs follow the balance theory, significantly excluding noise edges in learning. To address the sparsity of balanced triangles in a signed network, our framework learns not only the edges in balanced real-triangles but those in balanced virtual-triangles that are produced by our generator. Finally, our framework employs adversarial learning to generate more-realistic balanced virtual-triangles with less noise edges. Through extensive experiments using seven real-world networks, we validate the effectiveness of (1) learning edges belonging to balanced real/virtual-triangles and (2) employing adversarial learning for signed network embedding. We show that our framework consistently and significantly outperforms the state-of-the-art community detection methods in all datasets.

In recent years, quantization methods have successfully accelerated the training of large deep neural network (DNN) models by reducing the level of precision in computing operations (e.g., forward/backward passes) without sacrificing its accuracy. In this work, therefore, we attempt to apply such a quantization idea to the popular Matrix factorization (MF) methods to deal with the growing scale of models and datasets in recommender systems. However, to our dismay, we observe that the state-of-the-art quantization methods are not effective in the training of MF models, unlike their successes in the training of DNN models. To this phenomenon, we posit that two distinctive features in training MF models could explain the difference: (i) the training of MF models is much more memory-intensive than that of DNN models, and (ii) the quantization errors across users and items in recommendation are not uniform. From these observations, we develop a quantization framework for MF models, named MASCOT, employing novel strategies (i.e., m-quantization and g-switching) to successfully address the aforementioned limitations of quantization in the training of MF models. The comprehensive evaluation using four real-world datasets demonstrates that MASCOT improves the training performance of MF models by about 45%, compared to the training without quantization, while maintaining low model errors, and the strategies and implementation optimizations of MASCOT are quite effective in the training of MF models. For the detailed information about MASCOT, we release the code of MASCOT and the datasets at: https://github.com/Yujaeseo/lCDM-2021_MASCOT.

As the popularity of deep learning in industry rapidly grows, efficient training of deep neural networks (DNNs) becomes important. To train a DNN with a large amount of data, distributed training with data parallelism has been widely adopted. However, the communication overhead limits the scalability of distributed training. To reduce the overhead, a number of distributed training algorithms have been proposed. The model accuracy and training performance of those algorithms can be different depending on various factors such as cluster settings, training models/datasets, and optimization techniques applied. In order for someone to adopt a distributed training algorithm appropriate for her/his situation, it is required for her/him to fully understand the model accuracy and training performance of these algorithms in various settings. Toward this end, this paper reviews and evaluates seven popular distributed training algorithms (BSP, ASP, SSP, EASGD, AR-SGD, GoSGD, and AD-PSGD) in terms of the model accuracy and training performance in various settings. Specifically, we evaluate those algorithms for two CNN models, in different cluster settings, and with three well-known optimization techniques. Through extensive evaluation and analysis, we made several interesting discoveries. For example, we found out that some distributed training algorithms (SSP, EASGD, and GoSGD) have highly negative impact on the model accuracy because they adopt intermittent and asymmetric communication to improve training performance; the communication overhead of some centralized algorithms (ASP and SSP) is much higher than we expected in a cluster setting with limited network bandwidth because of the PS bottleneck problem. These findings, and many more in the paper, can guide the adoption of proper distributed training algorithms in industry; our findings can be useful in academia as well for designing new distributed training algorithms.

In this paper, we address the personalized node ranking (PNR) problem for signed networks, which aims to rank nodes in an order most relevant to a given seed node in a signed network. The recently-proposed PNR methods introduce the concept of the signed random surfer, denoted as SRSurfer, that performs the score propagation between nodes using the balance theory. However, in real settings of signed networks, edge relationships often do not strictly follow the rules of the balance theory. Therefore, SRSurfer-based PNR methods frequently perform incorrect score propagation to nodes, thereby degrading the accuracy of PNR. To address this limitation, we propose a novel random-walk based PNR approach with sign verification, named as OBOE (lOok Before yOu lEap). Specifically, OBOE carefully verifies the score propagation of SRSurfer by using the topological features of nodes. Then, OBOE corrects all incorrect score propagation cases by exploiting the statistics of a given network. The experiments on 3 real-world signed networks show that OBOE consistently and significantly outperforms 5 competing methods with improvement up to 13%, 95%, and 249% in top-k PNR, bottom-k PNR, and troll identification tasks, respectively. All OBOE codes and datasets are available at: http://github.com/wonchang24/OBOE.

In this demo, we present RealGraph Web , a web-based platform that provides various kinds of graph analysis services. RealGraph Web is based on RealGraph, a graph engine that addresses the problem of performance degradation in processing real-world big graphs, achieving great performance improvement up to 44 times over existing state-of-the-art graph engines. RealGraph Web runs on a single machine with a web-based interface, thereby allowing users to easily and conveniently enjoy graph analysis services and perform various graph algorithms anywhere on the web . In this demo, we present how a user can analyze a graph on RealGraph Web in three steps and get the analysis result quickly via a graphical user interface.

If we had the performance information of every application on every SSD, it would be very beneficial to both SSD users and SSD manufacturers. For SSD users, they can buy the SSD that is fastest for the most frequently using applications; for SSD manufacturers, they can figure out the strength and weakness of their SSD for every application. Toward this end, this article proposes a framework named${\sf FORESEE}$FORESEEthat estimates accurately the execution time of a given IO trace (i.e.,query IO trace) of a given application on a target SSDwithout its actual execution.${\sf FORESEE}$is developed based on the observation thatif two IO traces are similar to each other in their IO behavior, their execution times tend to be similar when they are executed on the same SSD. In${\sf FORESEE}$, the execution time of a query IO trace is estimated by using the execution times of the IO traces in a database similar to the query IO trace. Our technical contributions in${\sf FORESEE}$are as follows: (1) we propose a goodness function that efficiently evaluates the quality of sets of features that are used to measure the similarity of IO traces; (2) we propose a DB structure and a searching method for efficiently searching for similar IO traces to a query IO trace; (3) we propose an aggregation method that aggregates the execution times of similar IO traces to a query IO trace for accurately estimating the execution time of the query IO trace; and (4) we verify the effectiveness of${\sf FORESEE}$via extensive experiments by using real-world application IO traces. According to the results, the Pearson correlation coefficient (PCC) of the actual execution time and the estimated execution time by${\sf FORESEE}$is found to be 0.87, indicating${\sf FORESEE}$estimates the execution time accurately.

In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.

For these few decades malwares have been posing a major concern in the cyber security. Recently, a number of "author groups" have been generating lots of newmalwares by sharing source code within a group and exploiting evasive schemes such as polymorphism and metamorphism. This motivates us to study the problem of identifying the author group of a given malware, which would be able to work for not only blocking malwares but also legally punishing suspected malware authors. In this paper, we propose a human-machine collaborative approach for classifying author groups of malwares accurately. We also propose a visualization method for helping human experts to make the decision easily. We verify the superiority of our framework through extensive experiments using real-world malware data.

In this paper, we start by pointing out the limitations on the validation of existing signed network embedding (NE) methods. To address the limitations, we design the two research questions: (1) are signed NE methods consistently more effective in various types of tasks than unsigned NE methods? (2) in signed NE methods, does the utilization of negative links help provide higher accuracy in various tasks? To answer the questions, we present our evaluation framework consisting of three components: (1) five signed network datasets; (2) six signed and two unsigned NE methods; (3) five types of tasks. Through extensive experiments on our evaluation framework, we demonstrate that additional utilization of negative links really helps only in some tasks related to negative links but not in tasks related to positive links.

As social network services (SNS) are expanding from friend-based to interest-based, users form a new type of relationships, namely interest-based relationships, with friends and others through social activities (e.g., likes, comments). Although such relationships are highlighted in the common-identity theory and have important values in theoretical and practical aspects, little evidence exists in the literature pertaining to the explanation of social activities as a central component for social network analysis and an association with friendship. In this paper, we build like networks in Instagram and analyze them through the lens of two salient aspects - friendship and interest - that constitute social networks. Our study results (1) show ambiguous interpretations of the like activities between users who are friends, based on the comparative analysis between friend- and non-friend-based like networks, and (2) demonstrate strong signals of the hashtag characterizing the interest-based relationships in users and content. Our research substantiates and gives insights on the common-identity theory applied in online social networks through data-driven, empirical analysis.

Sparse matrix multiplication (spGEMM) is widely used to analyze the sparse network data, and extract important information based on matrix representation. As it contains a high degree of data parallelism, many efficient implementations using data-parallel programming platforms such as CUDA and OpenCL have been introduced on graphic processing units (GPUs). Several well-known spGEMM techniques, such as cuS- PARSE and CUSP, often do not utilize the GPU resources fully, owing to the load imbalance between threads in the expansion process and high memory contention in the merge process. Furthermore, even though several outer-product-based spGEMM techniques are proposed to solve the load balancing problem on expansion, they still do not utilize the GPU resources fully, because severe computation load variations exist among the multiple thread blocks.To solve these challenges, this paper proposes a new optimization pass called Block Reorganizer, which balances the total computations of each computing unit on target GPUs, based on the outer-product-based expansion process, and reduces the memory pressure during the merge process. For expansion, it first identifies the actual computation amount for each block, and then performs two thread block transformation processes based on their characteristics: 1) B-Splitting to transform a heavy-computation blocks into multiple small blocks and 2) B- Gathering to aggregate multiple small-computation blocks to a larger block. While merging, it improves the overall performance by performing B-Limiting to limit the number of blocks on each computing unit. Experimental results show that it improves the total performance of kernel execution by 1.43x, on an average, when compared to the row-product-based spGEMM, for NVIDIA Titan Xp GPUs on real-world datasets.

Cold-start problems are arguably the biggest challenges faced by collaborative filtering (CF) used in recommender systems. When few ratings are available, CF models typically fail to provide satisfactory recommendations for cold-start users or to display cold-start items on users' top-N recommendation lists. Data imputation has been a popular choice to deal with such problems in the context of CF, filling empty ratings with inferred scores. Different from (and complementary to) data imputation, this paper presents AR-CF, which stands for Augmented Reality CF, a novel framework for addressing the cold-start problems by generating virtual, but plausible neighbors for cold-start users or items and augmenting them to the rating matrix as additional information for CF models. Notably, AR-CF not only directly tackles the cold-start problems, but is also effective in improving overall recommendation qualities. Via extensive experiments on real-world datasets, AR-CF is shown to (1) significantly improve the accuracy of recommendation for cold-start users, (2) provide a meaningful number of the cold-start items to display in top-N lists of users, and (3) achieve the best accuracy as well in the basic top-N recommendations, all of which are compared with recent state-of-the-art methods.

Motivated by a success of generative adversarial networks (GAN) in various domains including information retrieval, we propose a novel signed network embedding framework, ASiNE, which represents each node of a given signed network as a low-dimensional vector based on the adversarial learning. To do this, we first design a generator G+ and a discriminator D+ that consider positive edges, as well as a generator G - and a discriminator D- that consider negative edges: (1) G+/G- aim to generate the most indistinguishable fake positive/negative edges, respectsupively; (2) D+/D aim to discriminate between real positive/negative edges and fake positive/negative edges, respectively. Furthermore, under ASiNE, we propose two new strategies for effective signed network embedding: (1) an embedding space sharing strategy for learning both positive and negative edges; (2) a fake edge generation strategy based on the balance theory. Through extensive experiments using five real-life signed networks, we verify the effectiveness of each of the strategies employed in ASiNE. We also show that ASiNE consistently and significantly outperforms all the state-of-the-art signed network embedding methods in all datasets and with all metrics in terms of accuracy of sign prediction.

Summary Learning and analyzing graph data is one of the most fundamental research areas in machine learning and data mining. Among numerous graph‐based data structures, this paper focuses on a graph bag (simply, bag), which corresponds to a training object containing one or more graphs, and a label is available only for a bag. This type of a bag can represent various real‐world objects such as drugs, web pages, XML documents, and images, among many others, and there have been many researches on models for learning this type of bag data. Within this research context, we define a novel problem of dynamic graph bag classification, and propose an algorithm to solve this problem. Dynamic bag classification aims to build a classification model for bags, which are presented in a streaming fashion, ie, frequent emerging of new bags or graphs over time. Given such changes made to the bag dataset, our proposed algorithm aims to update incrementally the top‐m most discriminative features instead of searching for them from scratch. Incremental gSpan and incremental gScore are proposed as core parts of our algorithm to deal with a stream of bags efficiently. We evaluate our algorithm on two real‐world datasets in terms of both feature selection time and classification accuracy. The experimental results demonstrate that our algorithm derives an informative feature set much faster than the existing one originally designed for targeting static bag data, with little accuracy loss.

As the number of TV channels increases, it is becoming important to recommend TV shows that users prefer to watch. To this end, we investigate the inherent characteristics of implicit feedback given in the TV show domain, and identify the challenges for building an effective TV show recommendation. Based on the unique characteristics, we define a user's watchable interval, the most important and novel concept in understanding users' true preferences. In order to reflect this new concept into the TV show recommendation, we propose a novel framework based on collaborative filtering. Our framework is composed of (1) preference estimation based on a user's watchable interval, (2) preference prediction based on confidence exploiting watchable episodes, and (3) top-N recommendation considering TV show's staying and remaining times. Using a real-world TV show dataset, we demonstrate that our framework effectively solves the challenges and significantly outperforms other existing state-of-the-art methods.

Generative Adversarial Networks (GAN) have not only achieved a big success in various generation tasks such as images, but also boosted the accuracy of classification tasks by generating additional labeled data, which is called data augmentation. In this paper, we propose a Rating Augmentation framework with GAN, named RAGAN, aiming to alleviate the data sparsity problem in collaborative filtering (CF), eventually improving recommendation accuracy significantly. We identify a unique challenge that arises when applying GAN to CF for rating augmentation: naive RAGAN tends to generate values biased towards high ratings. Then, we propose a refined version of RAGAN, named RAGANBT, which addresses this challenge successfully. Via our extensive experiments, we validate that our RAGANBT is really effective to solve the data sparsity problem, thereby providing existing CF models with great improvement in accuracy under various situations such as basic top-N recommendation, long-tail item recommendation, and recommendation to cold-start users.

As the size of real-world graphs has drastically increased in recent years, a wide variety of graph engines have been developed to deal with such big graphs efficiently. However, the majority of graph engines have been designed without considering the power-law degree distribution of real-world graphs seriously. Two problems have been observed when existing graph engines process real-world graphs: inefficient scanning of the sparse indicator and the delay in iteration progress due to uneven workload distribution. In this paper, we propose RealGraph, a single-machine based graph engine equipped with the hierarchical indicator and the block-based workload allocation. Experimental results on real-world datasets show that RealGraph significantly outperforms existing graph engines in terms of both speed and scalability.

We develop a novel framework, named as$l$-injection, to address the sparsity problem of recommender systems. By carefully injecting low values to a selected set of unrated user-item pairs in a user-item matrix, we demonstrate that top-Nrecommendation accuracies of various collaborative filtering (CF) techniques can be significantly and consistently improved. We first adopt the notion ofpre-use preferencesof users toward a vast amount ofunrateditems. Using this notion, we identifyuninterestingitems that have not been rated yet but are likely to receive low ratings from users, and selectively impute them as low values. As our proposed approach is method-agnostic, it can be easily applied to a variety of CF algorithms. Through comprehensive experiments with three real-life datasets (e.g., Movielens, Ciao, and Watcha), we demonstrate that our solution consistently and universally enhances the accuracies of existing CF algorithms (e.g., item-based CF, SVD-based CF, and SVD++) by 2.5 to 5 times on average. Furthermore, our solution improves the running time of those CF methods by 1.2 to 2.3 times when its setting produces the best accuracy. The datasets and codes that we used in the experiments are available at:https://goo.gl/KUrmip.

We investigate how to address the shortcomings of the popular One-Class Collaborative Filtering (OCCF) methods in handling challenging “sparse” dataset in one-class setting (e.g., clicked or bookmarked), and propose a novel graph-theoretic OCCF approach, named as gOCCF, by exploiting both positive preferences (derived from rated items) as well as negative preferences (derived from unrated items). In capturing both positive and negative preferences as a bipartite graph, further, we apply the graph shattering theory to determine the right amount of negative preferences to use. Then, we develop a suite of novel graph-based OCCF methods based on the random walk with restart and belief propagation methods. Through extensive experiments using 3 real-life datasets, we show that our gOCCF effectively addresses the sparsity challenge and significantly outperforms all of 8 competing methods in accuracy on very sparse datasets while providing comparable accuracy to the best performing OCCF methods on less sparse datasets. The datasets and implementations used in the empirical validation are available for access: https://goo.gl/sfiawn.

Generative Adversarial Networks (GAN) have achieved big success in various domains such as image generation, music generation, and natural language generation. In this paper, we propose a novel GAN-based collaborative filtering (CF) framework to provide higher accuracy in recommendation. We first identify a fundamental problem of existing GAN-based methods in CF and highlight it quantitatively via a series of experiments. Next, we suggest a new direction of vector-wise adversarial training to solve the problem and propose our GAN-based CF framework, called CFGAN, based on the direction. We identify a unique challenge that arises when vector-wise adversarial training is employed in CF. We then propose three CF methods realized on top of our CFGAN that are able to address the challenge. Finally, via extensive experiments on real-world datasets, we validate that vector-wise adversarial training employed in CFGAN is really effective to solve the problem of existing GAN-based CF methods. Furthermore, we demonstrate that our proposed CF methods on CFGAN provide recommendation accuracy consistently and universally higher than those of the state-of-the-art recommenders.

With the development of smart devices and the popularization of social media, communication between users is becoming increasingly active in the online space, revitalizing a new relationships formed and developed. Individuals are connecting with various people, which makes many companies actively employ social media to communicate with existing and potential customers for marketing. While social networks comprise a mix of various activities such as liking, commenting, tagging, and following, little is known about the way in which liking and tagging characterize one's social networks. In this paper, we define two types of a like network: tag-based like network, non-tag-based like network and present a comparative analysis with regard to their structural and temporal aspects. Our study results show (1) a significant difference in the network size and the degree of components between the two networks and (2) the potential of the tag-based like network to have more followers than the non-tag-based like network. We highlight how the tag-based like network can be utilized to find users with the same interests, supporting additional, interest based social connection and interaction. Our study insights are expected to be developed and utilized as a web service system.

Data sparsity is one of the biggest problems faced by collaborative filtering used in recommender systems. Data imputation alleviates the data sparsity problem by inferring missing ratings and imputing them to the original rating matrix. In this paper, we identify the limitations of existing data imputation approaches and suggest three new claims that all data imputation approaches should follow to achieve high recommendation accuracy. Furthermore, we propose a deep-learning based approach to compute imputed values that satisfies all three claims. Based on our hypothesis that most pre-use preferences (e.g., impressions) on items lead to their post-use preferences (e.g., ratings), our approach tries to understand via deep learning how pre-use preferences lead to post-use preferences differently depending on the characteristics of users and items. Through extensive experiments on real-world datasets, we verify our three claims and hypothesis, and also demonstrate that our approach significantly outperforms existing state-of-the-art approaches.

Summary Malwares are growing exponentially in number, and authors of malwares are continuously releasing new ones. Malwares developed by the same author group might have similar signatures. For a number of applications including digital forensic and law enforcement, such characteristics can be used to determine which author group is likely to have released a given malware. In this paper, we describe a new type of classification that identifies which group of authors is most likely to have developed a given malware. We identify and verify a set of various features obtained through static and dynamic analyses of malwares and exploit them for classification. We evaluate our approach through extensive experiments with a real‐world dataset labeled by a group of domain experts. The results show that our approach is effective and provides good accuracy in malware classification.

Influence Maximization (IM) is the problem of finding a seed set composed of k nodes that maximize their influence spread over a social network. Kempe et al. showed the problem to be NP-hard and proposed a greedy algorithm (referred to as SimpleGreedy ) that guarantees 63% influence spread of its optimal solution. However, SimpleGreedy has two performance issues: at a micro level , it estimates the influence spread of a single node by running Monte-Carlo (MC) simulations that are fairly expensive; at a macro level, after selecting one seed at each step, it re-evaluates the influence spread of every node in a social network, leading to significant computational overhead. In this paper, we propose Hybrid-IM that addresses the two issues in both micro and macro levels by combining PB-IM (Path Based Influence Maximization) and CB-IM (Community Based Influence Maximization) . Furthermore, we identify two technical issues that could improve the performance of Hybrid-IM more and propose two strategies to address those issues. Through extensive experiments with four real-world datasets, we show that Hybrid-IM achieves great improvement (up to 43 times) in performance over state-of-the-art methods and finds the seed set that provides the influence spread very close to that of the state-of-the-art methods.

With the NAND flash memory technology of solid-state drives (SSDs), the usage of SSDs is expanded to various devices. Due to the cost and time limitations of measuring the actual execution time of each application on SSDs, it is difficult for users to determine the best SSD for their most commonly used applications. In this paper, we propose a framework of estimating the execution time of an application IO trace (i.e., a query IO trace) on a target SSD without its real execution. Our framework is based on the observation that if two IO traces are similar in their IO behavior, their execution times tend to be similar when executed on the same SSD. The performance of the framework is evaluated through extensive experiments on real applications. The results show that our framework is accurate in estimating the execution time of an IO trace on SSDs.

Smart TVs are rapidly replacing conventional TVs. In a number of countries, set-top boxes (STB) are widely used to relay TV channels to smart TVs. In such cases, smart TVs cannot identify which TV channel they are receiving. This situation makes it challenging for smart TVs to provide their users with a variety of personalized services, such as context-aware services and recommendation services. In this paper, we introduce our TV channel matching system that resolves such problems. We propose strategies for scaling-out the matching system and improving its accuracy.

Graphs are very widely used to represent datasets in various real-world applications. Many algorithms dealing with graphs represent them in the form of sparse matrices and process them through sparse matrix operations. Recently, as the size of a graph increases rapidly, a single-machine-based graph engine has emerged as a general framework for effectively performing large-scale sparse matrix operations. Sparse matrices multiplication (SpGEMM) is a core building block for developing a variety of graph algorithms such as all source shortest paths, betweenness centrality, breadth first search from multiple sources, subgraph indexing, and graph construction. This paper addresses how to perform two sparse matrices multiplication (SpGEMM) efficiently on a single-machine-based graph engine. To effectively perform the large-scale SpGEMM, we have two issues: (1) selecting an appropriate type of matrix products (i.e., inner products, outer products, and row-row products), and (2) allocating memory space to matrices according to different types of matrix products. We first formulate the cost models for the three matrix product types by reflecting their characteristics. We observed the commonality in the processes of the matrix multiplication and the join in a relational database. Based on this observation, we propose memory allocation schemes for three matrix products by borrowing the idea of memory allocation employed in join. Finally, we show the effectiveness of our approach via extensive experiments with real-life datasets.

C-Rank (contribution-based ranking) is a state-of-the-art algorithm for ranking web pages. It combines content and link information by introducing the concept of contribution, which implies how much a page contributes to improving the content quality of other pages. However, C-Rank suffers from taking infeasible time to reflect changes in World Wide Web to every page's C-Rank score. In this paper, we propose an effective and efficient method to incrementally maintain C-Rank scores of terms in web pages. Our proposed method is carefully designed to selectively update C-Rank scores of specific pages without any accuracy loss, rather than re-computing all the C-Rank scores of all the terms in all the pages from the scratch. Our experimental results on real-world dataset confirm the effectiveness and efficiency of our proposed method.

E-recruitment sites such as LinkedIn, Reed, and Indeed have a huge number of professional resumes from job seekers and job openings posted by recruiters. In this situation, it is a very time-consuming task for job seekers to find job openings that are well matched to their careers and desired conditions. Accordingly, active studies on job recommendation (JR) have been conducted recently. In this paper, we address the important property of transition patterns in JR that previous studies have overlooked. To incorporate the property into JR, we first propose two data modeling methods of adjacent pairing and all paring that represent a career path of a job seeker as a set of job pairs. Then, we propose frequency-based and graph-based methods of preference inference based on the data modeling methods. Finally, we develop four recommendation approaches, AdjacentFreq, AllFreq, AdjacentGraph, and AllGraph, each of which is a combination of two data modeling methods and two preference inference methods. Through extensive experiments using a real-life dataset, we show that our proposed approaches effectively address the unique property of JR. Also, we show that JR utilizing the transition information provides accuracy higher than JR not using the information.

Given "who-trusts/distrusts-whom" information, how can we propagate the trust and distrust? With the appearance of fraudsters in social network sites, the importance of trust prediction has increased. Most such methods use only explicit and implicit trust information (e.g., if Smith likes several of Johnson's reviews, then Smith implicitly trusts Johnson), but they do not consider distrust.

The size of graphs has dramatically increased. Graph engines for a single machine have been emerged to process these graphs efficiently. However, existing engines have overlooked a data locality which is an imperative factor to improve the performance of these engines in the previous literature. In this paper, we show the importance of data locality with graph algorithms by running on graph engines based on a single machine.

In this paper, we propose a crowdsourcing-based approach to solving skyline queries with incomplete data. Our main idea is to leverage crowds to infer the pair-wise preferences between tuples when the values of tuples in some attributes are unknown. Specifically, our proposed solution considers three key factors used in existing crowd-enabled algorithms: (1) minimizing a monetary cost in identifying a crowdsourced skyline by using a dominating set, (2) reducing the number of rounds for latency by parallelizing the questions asked to crowds, and (3) improving the accuracy of a crowdsourced skyline by dynamically assigning the number of crowd workers per question. We evaluate our solution over both simulated and real crowdsourcing using the Amazon Mechanical Turk. Compared to a sort-based baseline method, our solution significantly minimizes the monetary cost, and reduces the number of rounds up to two orders of magnitude. In addition, our dynamic majority voting method shows higher accuracy than both static majority voting method and the existing solution using unary questions.

We study how to improve the accuracy and running time of top-N recommendation with collaborative filtering (CF). Unlike existing works that use mostly rated items (which is only a small fraction in a rating matrix), we propose the notion of pre-use preferences of users toward a vast amount of unrated items. Using this novel notion, we effectively identify uninteresting items that were not rated yet but are likely to receive very low ratings from users, and impute them as zero. This simple-yet-novel zero-injection method applied to a set of carefully-chosen uninteresting items not only addresses the sparsity problem by enriching a rating matrix but also completely prevents uninteresting items from being recommended as top-N items, thereby improving accuracy greatly. As our proposed idea is method-agnostic, it can be easily applied to a wide variety of popular CF methods. Through comprehensive experiments using the Movielens dataset and MyMediaLite implementation, we successfully demonstrate that our solution consistently and universally improves the accuracies of popular CF methods (e.g., item-based CF, SVD-based CF, and SVD++) by two to five orders of magnitude on average. Furthermore, our approach reduces the running time of those CF methods by 1.2 to 2.3 times when its setting produces the best accuracy. The datasets and codes that we used in experiments are available at: https://goo.gl/KUrmip.

In this paper, we propose SimCC-AT (similarity based on content and citations with automatic parameter tuning) to compute the similarity of scientific papers. As in SimCC, the state-of-the-art method, we exploit a notion of a contribution score in similarity computation. SimCC-AT utilizes an automatic weighting scheme based on SVMrank and thus requires only a smaller number of experiments for parameter tuning than SimCC. Furthermore, our experimental results with a real-world dataset show that the accuracy of SimCC-AT is dramatically higher than that of other existing methods and is comparable to that of SimCC.

Collaborative filtering methods suffer from a data sparsity problem, which indicates that the accuracy of recommendation decreases when the user-item matrix used in recommendation is sparse. To alleviate the data sparsity problem, researches on data imputation have been done. In particular, the zero-injection method, which finds uninteresting items and imputes zero values to those items for collaborative filtering, achieves significant improvement in terms of recommendation accuracy. However, the existing zero-injection method employs the One-Class Collaborative Filtering (OCCF) method that requires a lot of time. In this paper, we propose a fast method that finds uninteresting items rapidly with preserving high recommendation accuracy. Our experimental results show that our method is faster than the existing zero-injection method and also show that the recommendation accuracy using our method is slightly higher than or similar to that of the existing zero-injection method.

DBpia is the largest digital-bibliography service provider in Korea. It provides several convenience functions for researchers. DBpia users (i.e., researchers) can search for papers via several search routes such as publications, publishers, authors, and keywords. Although the researchers can exploit the search functions, they may still have a number of search results as candidate papers to read. Therefore, it is crucial to provide a function of recommending most relevant papers to an individual user. In this paper, we (1) discuss several methods with four datasets of DBpia in the context of paper recommendation using content-based or graph-based recommendation, and (2) propose a hybrid approach suitable for paper recommendation combining the content-based and the graph-based approaches. We lastly conduct extensive experiments by a real-world academic literature dataset in DBpia to verify the effectiveness of our proposed approach.

This paper proposes a novel birthmark, a dynamic API authority vector (DAAV), for detecting software theft. DAAV satisfies four essential requirements for good birthmarks--credibility, resiliency, scalability, and packing-free--while existing birthmarks fail to satisfy all of them together. In particular, existing static birthmarks are unable to handle the packed programs and existing dynamic birthmarks do not satisfy credibility and resiliency. Our experimental results demonstrate that DAAV provides satisfying credibility and resiliency compared with existing dynamic birthmarks and also can cover packed programs.

In this paper, we address how to reduce the amount of page updates in flash-based DBMS equipped with SSD (Solid State Drive). We propose a novel buffering scheme that evicts a dirty page X without flushing it into SSD, and restores the right image of X when X is requested for later access. The restoration of X having previous flushing-less eviction is performed through our online redo actions on X. We call this page-restoring online redo the on-the-fly redo. Although our on-the-fly redo mechanism has some overhead of increasing the number of page reads, this can be compensated by infrequent page updates. Additionally, since the proposed buffering scheme with the on-the-fly redo can easily support the no-steal policy in buffer management, we can enjoy the advantages of smaller logging overhead and faster recovery. Through the TPC-C benchmarks using a Berkeley DB, we show that our scheme shortens the transaction processing times by up to 53%.

As a number of social network services appear online recently, there have been many attempts to analyze social networks for extracting valuable information. Most existing methods first represent a social network as a quite sparse adjacency matrix, and then analyze it through matrix operations such as matrix multiplication. Due to the large scale and high complexity, efficient processing multiplications is an important issue in social network analysis. In this paper, we propose a GPU-based method for efficient sparse matrix multiplication through the parallel computing paradigm. The proposed method aims at balancing the amount of workload both at fine- and coarse-grained levels for maximizing the degree of parallelism in GPU. Through extensive experiments using synthetic and real-world datasets, we show that the proposed method outperforms previous methods by up to three orders-of-magnitude.

The average of customer ratings on a product, which we call a reputation, is one of the key factors in online purchasing decisions. There is, however, no guarantee of the trustworthiness of a reputation since it can be manipulated rather easily. In this paper, we define false reputation as the problem of a reputation being manipulated by unfair ratings and design a general framework that provides trustworthy reputations. For this purpose, we propose TRUE-REPUTATION, an algorithm that iteratively adjusts a reputation based on the confidence of customer ratings. We also show the effectiveness of TRUE-REPUTATION through extensive experiments in comparisons to state-of-the-art approaches.

Let us consider that someone is starting a research on a topic that is unfamiliar to them. Which seminal papers have influenced the topic the most? What is the genealogy of the seminal papers in this topic? These are the questions that they can raise, which we try to answer in this paper. First, we propose an algorithm that finds a set of seminal papers on a given topic. We also address the performance and scalability issues of this sophisticated algorithm. Next, we discuss the measures to decide how much a paper is influenced by another paper. Then, we propose an algorithm that constructs a genealogy of the seminal papers by using the influence measure and citation information. Finally, through extensive experiments with a large volume of a real-world academic literature data, we show the effectiveness and efficiency of our approach.

This paper presents the type-2 micro virtual machine monitor (ViMo-T2) for ARM-based mobile systems. It is implemented as a kernel module of the host operating system (OS) and enables to run multiple OSs on a single mobile device simultaneously. Since ViMo-T2 is layered upon the host OS that was already installed by a device manufacture, it is applicable to the existing mobile system at user's own risk, so that time and cost developing a virtualized mobile system can be reduced.

This paper introduces the notion of intelligent SSDs. First, we present the design considerations of intelligent SSDs, and then examine their potential benefits under various settings in data mining applications.

As plagiarism of software increases rapidly, there are growing needs for software plagiarism detection systems. In this paper, we propose a software plagiarism detection system using an API-labeled control flow graph (A-CFG) that abstracts the functionalities of a program. The A-CFG can reflect both the sequence and the frequency of APIs, while previous work rarely considers both of them together. To perform a scalable comparison of a pair of A-CFGs, we use random walk with restart (RWR) that computes an importance score for each node in a graph. By the RWR, we can generate a single score vector for an A-CFG and can also compare A-CFGs by comparing their score vectors. Extensive evaluations on a set of Windows applications demonstrate the effectiveness and the scalability of our proposed system compared with existing methods.

In computing the similarity of scientific papers, previous text-based and link-based similarity measures look at only a single side of the content and citations. In this paper, we propose a novel approach called SimCC that effectively combines the content and citation information to accurately compute the similarity of scientific papers. Unlike previous approaches, SimCC effectively represents both authority and context of a scientific paper simultaneously in computing similarities. Also, we propose SimCC+A to consider recently-published papers. The effectiveness of our proposed method is demonstrated via extensive experiments on a real-world dataset of scientific papers, with more than 100% improvement in accuracy compared with previous methods.

In a trust network, two users who are connected by a trust relationship tend to have similar interests. Based on this observation, existing trust-aware recommendation methods predict ratings for a target user on unseen items by referencing to ratings of those users who are reachable from the target user in the forward direction of trustor-trustee relationship through the trust network. However, these methods have overlooked the possibility of utilizing the ratings of those users reachable in the backward direction, which may also have similar interests. In this paper, we investigate this possibility by identifying and adding these users to the existing methods when predicting ratings for the target user. We perform a series of experiments and observe that our approach improves the coverage while preserving the accuracy.

The average of the customer ratings on the product, which we call reputation, is one of the key factors in online purchasing decision of a product. There is, however, no guarantee in the trustworthiness of the reputation since it can be manipulated rather easily. In this paper, we define false reputation as the problem of the reputation to be manipulated by unfair ratings, and design a general framework that provides trustable reputation. For this purpose, we propose TRUEREPUTATION, an algorithm that iteratively adjusts the reputation based on the confidence of customer ratings.

Recently, a single-borehole monostatic pulse radar has been developed and operated at a well-suited tunnel test site. The measured B-scan data were severely contaminated by obliquely striped patterns. In this paper, numerical simulations and field experiments are performed to find a proper way of suppressing the unwanted striped patterns. For numerical analysis, the finite-difference time domain is applied to a simplified 2-D model consisting of a water-filled borehole, two different rocks, and a dipole antenna connected to a conducting cable. It can be visualized that a set of oblique lines is generated from the borehole-guided waves reflected at the interface of two different rocks. When the conducting cable is coated by a perfect magnetic conductor (PMC), the oblique lines are nearly eliminated in the simulated B-scan result. In practice, the PMC coating is replaced by a ferrite core loading, and those loading effects on suppressing the borehole-guided waves are measured by operating our single-borehole monostatic pulse radar at a well-suited tunnel test site. Without a ferrite core loading on the connection cable, the borehole-guided waves cause the measured B-scan to be contaminated by the unwanted striped patterns. When a ferrite core is wrapped around the connection cable, the borehole-guided waves are nearly removed in the measured B-scan data. In particular, the unwanted striped patterns can be suppressed over 90% even if the total length of a ferrite core decreases to 0.5 m.

An outlier is an object that is considerably dissimilar with the remainder of the dataset. In this paper, we first propose the notion of centrality and center-proximity as novel outlierness measures which can be considered to represent the characteristics of all of the objects in the dataset. We then propose a graph-based outlier detection method which can solve the problems of local density, micro-cluster, and fringe objects. Finally, through extensive experiments, we show the effectiveness of the proposed method.

The top-n recommendation focuses on finding the top-n items that the target user is likely to purchase rather than predicting his/her ratings on individual items. In this paper, we propose a novel method that provides top-n recommendation by probabilistically determining the target user's preference on items. This method models the purchasing relationships between users and items as a bipartite graph and employs Belief Propagation to compute the preference of the target user on items. We analyze the proposed method in detail by examining the changes in recommendation accuracy under different parameter settings. We also show that the proposed method is up to 40% more accurate than an existing method by comparing it with an RWR-based method via extensive experiments.

A variety of recommendation methods have been proposed to satisfy the performance and accuracy; however, it is fairly difficult to satisfy both of them because there is a trade-off between them. In this paper, we introduce the notion of category experts and propose the recommendation method by exploiting the ratings of category experts instead of those of the users similar to a target user. We also extend the method that uses both the category preference of a target user and his/her similarity to category experts. We show that our method significantly outperforms the existing methods in terms of performance and accuracy through extensive experiments with real-world data.

When a researcher starts with a new topic, it would be very useful if seminal papers in the topic and their relationships are provided in advance. We propose an approach to construct seminal paper genealogy and show the effectiveness and efficiency of our approach.

Color descriptors are one of the important features used in content-based image retrieval. The dominant color descriptor (DCD) represents a few perceptually dominant colors in an image through color quantization. For image retrieval based on DCD, the earth mover's distance and the optimal color composition distance are proposed to measure the dissimilarity between two images. Although providing good retrieval results, both methods are too time-consuming to be used in a large image database. To solve the problem, we propose a new distance function that calculates an approximate earth mover's distance in linear time. To calculate the dissimilarity in linear time, the proposed approach employs the space-filling curve for multidimensional color space. To improve the accuracy, the proposed approach uses multiple curves and adjusts the color positions. As a result, our approach achieves order-of-magnitude time improvement but incurs small errors. We have performed extensive experiments to show the effectiveness and efficiency of the proposed approach. The results reveal that our approach achieves almost the same results with the EMD in linear time.

A blogosphere is a representative example of online social networks. In this paper, we address spectral analysis of a blogosphere. We model a real-world blogosphere as a matrix and a tensor, and then analyze it by using the SVD and PARAFAC decomposition. According to the results, the SVD successfully identified communities, each of which focuses on a specific topic, and also found hub blogs and authoritative posts within each community. The PARAFAC decomposition also succeeded in extracting more communities of finer granules than the SVD. Also, the PARAFAC decomposition could identify the dominant keywords in addition to the hub blogs and authoritative posts honored in each community.

A similar shader retrieval searches for shaders similar to a given query shader, and significantly reduces trial-and-errors and long processing time in a shading process. However, the developing of similarity measure is quite challenging because of the two characteristics of shader: (1) Shaders have different numbers of attributes that are peculiar to each of them, (2) Since the number of attributes in a shader becomes up to hundreds, the 'dimensionality curse' occurs. In this paper, we propose a novel method for extracting perception feature in effective similar shader retrieval. The proposed method finds low-dimensional features by analyzing hundreds attributes in a shader. The characteristics of extracted features are exactly the same with all the shaders, thereby making the similar shader retrieval much simpler. The proposed method constructs the perception features representing a shader by analyzing the meanings and relationships of all the attributes in the shader. Therefore, the method provides accurate results in the similar shader retrieval. To show the effectiveness of the proposed method, we conduct a variety of experiments.

Recently, product review sitesthat contain user ratings and trust statements such as Epinions.com have become popular, and many attempts have been made to analyze user behavior on those sites. In this paper, we first define three different user groups for each user, i.e. Trustee, Trust or, and Irrelevance which describe different kinds of trust statements. Then we investigate the relationship between each user and users in his/her different user groups by comparing how their ratings are similar on Epinions data sets. Most existing works simply ignored Trust or group when considering a certain user. However, our observations suggest that Trust or group still meaningful that should not be simply disregarded.

A blog service company provides a function named BlogCast that exposes quality posts on the blog main page to vitalize a blogosphere. This paper analyzes a new type of information diffusion via BlogCast. We show that there exists a strong halo effect in a blogosphere via thorough investigation on a huge volume of blog data.

The pulse signatures of a deeply located dormant tunnel are measured by operating cross-borehole short-pulse radar in a well-suited tunnel test site in Korea. The relatively fast arrival of the first peak at depth of the empty tunnel, as indicated by data analysis, may play a key role in detecting the tunnel's precise location. Following short-time Fourier transform (STFT) of the data, the arrival time of the first peak is shown to be faster and more distinctive than that without STFTThe pulse signatures of a deeply located dormant tunnel are measured by operating cross-borehole short-pulse radar in a well-suited tunnel test site in Korea. The relatively fast arrival of the first peak at depth of the empty tunnel, as indicated by data analysis, may play a key role in detecting the tunnel's precise location. Following short-time Fourier transform (STFT) of the data, the arrival time of the first peak is shown to be faster and more distinctive than that without STFT if the observation frequency is properly selected. if the observation frequency is properly selected.

In a blog network, there are special users who induce other users to actively utilize blogs. Identifying such influential users is important when establishing business policy and business models for the blog network. This paper defines the users whose contents exhibit significant influence over other users as content power users (CPUs) and proposes a method of identifying them. We analyze the performance of the proposed method by applying it to an actual blog network and comparing its results with those of preexisting methods for determining power users. The experimental results demonstrate that the definition of CPUs is adequate to address the dynamic nature of the blogosphere and the main concerns of the blog industry. We also discuss the business models based on CPUs that could be used to stimulate user activities in a blog network.

A group of documents is called near-duplicates if they are almost the same with just a slight difference. Since near-duplicates are major concerns of Web search engines, it is necessary to identify and filter them effectively. Among existing near-duplicate identification methods, MinHashing is the most well-known one. It identifies near-duplicates regardless of locations of different parts in two documents. In blog environment, however, most near-duplicates differ only in their beginning or end. According to our preliminary experiment, about 99% of near-duplicates differ in the beginning or end (blog-duplicates hereafter) and only 1% of them differ in the middle. Thus, blog-duplicates have a long matched sequence in their central parts. Based on this important observation, we present a novel algorithm, Central Match, to identify blog-duplicates efficiently and accurately. When searching a document database for possible log-duplicates of a given document, Central Match runs50 times faster than MinHashing. In addition, Central Match identifies blog-duplicates more accurately than MinHashing. According to our experiments, when the precisions of Min-Hashing and Central Match are fixed to 0.9, their recalls are around 0.5 and 0.9, respectively, which means Central Match finds 80% more blog-duplicates than MinHashing.

In this paper, we propose a new paper ranking algorithm that gives a high rank to papers which is credited by other authoritative papers or published in premier conferences or journals. Also, the proposed algorithm solves a problem that recent papers are rated poorly due to few citations.

In this paper, we propose a new approach to measure sim-ilarities among academic papers based on their references. Our similarity measure uses both in-link and out-link by transforming in-link and out-link into undirected links.

This paper proposes a new trajectory clustering scheme for objects moving on road networks. A trajectory on road networks can be defined as a sequence of road segments a moving object has passed by. We first propose a similarity measurement scheme that judges the degree of similarity by considering the total length of matched road segments. Then, we propose a new clustering algorithm based on such similarity measurement criteria by modifying and adjusting the FastMap and hierarchical clustering schemes. To evaluate the performance of the proposed clustering scheme, we also develop a trajectory generator considering the fact that most objects tend to move from the starting point to the destination point along their shortest path. The performance result shows that our scheme has the accuracy of over 95%.

A blog network, composed of blogs and their relations, may exhibit two different propensities characterized by the purpose of use: an information-oriented propensity and a friendship-oriented propensity. Both propensities coexist in a blog network, and the degree of these propensities may play an important role in business and policy decisions of blog-related business. In this paper, we propose an automated method for determining the propensity values of a blog network. First, classification is used to judge the propensity values of the relation between two blogs. Then, by adding up the propensity values of all the relations in the network, one determines the propensity values of the whole network. Through extensive experiments using a large volume of real-world blog data, we demonstrate our method achieves a high level of accuracy in determining the propensity values of a relation. The results also suggest the applicability of our approach for determining the propensity values of a network.

In the blogosphere, there exist posts relevant to a particular subject and blogs that show interests in the subject. In this paper, we define a set of such posts and blogs as "blog community" and propose a method for extracting the blog community associated with a particular subject. The proposed method is based on the idea that the blogs who have performed actions to the posts of a particular subject are the ones that have interests in the subject, and that the posts which have received actions from such blogs are the ones that contain the subject. The proposed method selects a small number of seed posts that contain the subject. Then, it selects the blogs that perform actions to the seed posts over some threshold and the posts that have received actions over some threshold. By repeating these two steps, it gradually expands the blog community. The experimental results show that the proposed method exhibits a higher level of accuracy than the methods proposed in prior research.

Blogspace is a primary example of online social networks. In blogspace, there are a number of communities, each of which consists of members having dense relationships with one another. In this paper, we address formation and evolution of blog communities. We first make two claims: (1) a high level of contents similarity of blogs increases the likelihood of their belonging to the same community in a blog network; (2) A high level of contents similarity of communities increases the possibility of their being merged into a bigger community in the future. We verify these claims by analyzing a large volume of real-world blog data of 2 millions bloggers through extensive experiments. Our results provide new insights towards subsequent research on formation and evolution of communities in a blog network.

This paper addresses an approach that recommends investment types to stock investors by discovering useful rules from past changing patterns of stock prices in databases. First, we define a new rule model for recommending stock investment types. For a frequent pattern of stock prices, if its subsequent stock prices are matched to a condition of an investor, the model recommends a corresponding investment type for this stock. The frequent pattern is regarded as a rule head, and the subsequent part a rule body. We observed that the conditions on rule bodies are quite different depending on dispositions of investors while rule heads are independent of characteristics of investors in most cases. With this observation, we propose a new method that discovers and stores only the rule heads rather than the whole rules in a rule discovery process. This allows investors to impose various conditions on rule bodies flexibly, and also improves the performance of a rule discovery process by reducing the number of rules to be discovered. For efficient discovery and matching of rules, we propose methods for discovering frequent patterns, constructing a frequent pattern base, and its indexing. We also suggest a method that finds the rules matched to a query from a frequent pattern base, and a method that recommends an investment type by using the rules. Finally, we verify the effectiveness and the efficiency of our approach through extensive experiments with real-life stock data.

The main memory DBMS (MMDBMS) efficiently supports various database applications that require high performance since it employs main memory rather than disk as a primary storage. In this paper, we discuss the cache-conscious index manager of the Tachyon, a next generation MMDBMS. The index manager is an essential sub-component of a DBMS used to speed up the retrieval of objects from a large volume of a database in response to a certain search condition. Recently, the gap between the CPU processing and main memory access times is becoming much wider due to rapid advance of CPU technology. By devising data structures and algorithms that utilize the behavior of the cache in CPU, we are able to enhance the overall performance of MMDBMSs considerably. In this paper, we address the practical implementation issues and our solutions for them obtained in developing the cache-conscious index manager of the Tachyon. The main issues touched are (1) consideration of the cache behavior, (2) compact representation of an index entry, (3) support of variable-length keys, (4) support of multiple-attribute keys, (5) support of duplicated keys, and (6) definition of the system catalog for indexes. We also show the effectiveness of our approach through extensive experiments.

In this paper we discuss the design and implementation of a concurrency control manager for Tachyon, a main-memory DBMS. Since a main-memory DBMS, unlike a disk-resident DBMS, performs all data updates or data retrievals by accessing main-memory only the portion of the cost for the concurrency control manager in the total cost for a data update or a data retrieval is fairly high. Thus, the development of an efficient concurrency control manager greatly accelerates the performance of the entire main-memory DBMS. Our concurrency control manager employs the two-phase locking protocol, and has the following characteristics. First, it adapts the partition as a locking granule, and thus effectively adjusts the trade-off between system concurrency and locking cost. Second, it enjoys low locking costs by maintaining lock information directly in the partition itself. Third, it provides the latch as a mechanism for physical consistency of system data. Our latch supports both shared and exclusive modes. and maximizes CPU utilization by combining the Bakery algorithm and the Unix semaphore facility. Fourth, for solving the deadlock problem, it periodically examines whether a system is in a deadlock state based on lock waiting information. In addition, we discuss various issues arising in development such as mutual exclusion of a transaction table, mutual exclusion of indexes and system catalogs, and phantom problem handling.

The nearest neighbor search is an important operation widely-used in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large fraction of points in the space. In this paper, we present a new approach for processing nearest neighbor search with the Euclidean metric, which searches over only a small subset of the original space. This approach effectively approximates clusters by encapsulating them into geometrically regular shapes and also computes better upper and lower bounds of the distances from the query point to the clusters. For showing the effectiveness of the proposed approach, we perform extensive experiments. The results reveal that the proposed approach significantly outperforms the X-tree as well as the sequential scan.

This paper discusses an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In our earlier work, we suggested an efficient method for whole matching under time warping. This method constructs a multi-dimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality.In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multi-dimensional index using a feature vector as indexing attributes. For query processing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verify the superiority of our method, we perform extensive experiments. The results reveal that our method achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.

This paper proposes a new novel method for similarity search that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. Previous methods for processing similarity search that supports time warping fail to employ multi-dimensional indexes without false dismissal since the time warping distance does not satisfy the triangular inequality. Our primary goal is to innovate on search performance without permitting any false dismissal. To attain this goal, we devise a new distance function D/sub tw-lb/ that consistently underestimates the time warping distance and also satisfies the triangular inequality D/sub tw-lb/ uses a 4-tuple feature vector that is extracted from each sequence and is invariant to time warping. For efficient processing of similarity search, we employ a multi-dimensional index that uses the 4-tuple feature vector as indexing attributes and D/sub tw-lb/ as a distance function. The extensive experimental results reveal that our method achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.

In this paper, w epropose a subsequence matching algorithm that supports normalization transform in timeseries databases.Normalization transform enables nding sequences with similar uctuation patterns although they are not close to each other before the normalization transform.Application of the existing whole matching algorithm supporting normalization transform to the subsequence matching is feasible, but requires an index for ev ery possible length of the query sequence causing serious overhead on both storage space and update time.The proposed algorithm generates indexes only for a small number of dierent lengths of query sequences.F or subsequence matching it selects the most appropriate index among them.We can obtain better searc h performance by using more indexes.We c a l l o u r approach index interp olation.We formally pro ve t h a t the proposed algorithm does not cause false dismissal.F or performance evaluation, we h a ve conducted experiments using the indexes for only ve dierent lengths out of the lengths 256 512 of the query sequence.The results show that the proposed algorithm outperforms the sequential scan by up to 14.6 times on the average when the selectivity of the query is 10 ;5 .

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. A number of spatial join algorithms have recently been proposed in the literature. Most of them, however, perform the join in the original space. Joining in the original space has a drawback of dealing with sizes of objects and thus has difficulty in developing a formal algorithm that does not rely on heuristics. In this paper, we propose a spatial join algorithm based on the transformation technique. An object having a size in the two-dimensional original space is transformed into a point in the four-dimensional transform space, and the join is performed on these point objects. This can be easily extended to n-dimensional cases. We show the excellence of the proposed approach through analysis and extensive experiments. The results show that the proposed algorithm has a performance generally better than that of the R*-based algorithm proposed by Brinkhoff et al. This is a strong indicating that corner transformation preserves clustering among objects and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely affect clustering. We believe that our result will provide a new insight towards transformation-based spatial query processing.

Spatial access methods (SAMs) are often used as clustering indexes in spatial database systems. Therefore, a SAM should have the clustering property both in the index and in the data file. In this paper we argue that corner transformation preserves the clustering property such that objects having similar sizes and positions in the original space tend to be placed in the same region in the transform space. We then show that SAMs based on corner transformation are able to maintain clustering both in the index and in the data file for storage systems with fixed object positions and propose the MBR-MLGF as an example to implement such an index. Extensive experiments comparing with the R*-tree show that corner transformation indeed preserves the clustering property. This result reverses the common belief that transformation will adversely affect the clustering.

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations.

In this paper, we discuss the errors in selectivity estimation using the multilevel grid file (MLGF), a multidimensional file structure. We first analyze the cause of the estimation errors, and then investigate five factors affecting the accuracy of estimation: (1) the data distribution in a region, (2) the number of records stored in the MLGF, (3) the page size, (4) the query region size, and (5) the level of the MLGF directory. Next, we present through extensive experiments the tendency of estimation errors when the value for each factor changes. The results show that the errors decrease when (1) the distribution of records in a region becomes closer to the uniform one, (2) the number of records in the MLGF increases, (3) the page size decreases, (4) the query region size increases, and (5) the level of the MLGF directory containing data distribution information becomes lower. We define the granule ratio, the core formula representing the basic relationship between the estimation error and the above five factors, and finally examine the change of estimation errors in relation with the change of the granule ratio through experiments. The results indicate that with a specific value for the granule ratio, errors tend to be similar regardless of different values for the five factors.