OpenRaiser/Intern-Atlas huggingface dataset:
Identifying Top-K Influential Nodes in Networks
Authors: Sara Mumtaz, Xiaoyang Wang
Venue: CIKM
Year: 2017

Network Centrality is one of the core concepts in network analysis, which ranks the importance of a node in a network. A considerably extensive range of centrality measures exist that serve the purpose of quantifying the importance of a node according to its application and domain. One such measure is the Betweenness Centrality (BC) which computes the importance of a node in terms of total number of shortest paths that pass through that node. However, these computations are very expensive and pose different challenges for large scale networks. With an attempt to deal with these challenges, our paper presents an approximate algorithm for BC maximization problem, which tries to find a set of nodes with largest BC. The core of our algorithm is the estimation technique, which is based on progressive sampling with early stopping conditions. The reduction in sample size results not only in small computations overhead, but also scales well with large networks. We experimentally evaluate our technique using different datasets to confirm the performance of the developed techniques.
Discovering Graph Temporal Association Rules
Authors: Mohammad Hossein Namaki, Yinghui Wu, Qi Song, Peng Lin, Tingjian Ge
Venue: CIKM
Year: 2017

Detecting regularities between complex events in temporal graphs is critical for emerging applications. This paper proposes graph temporal association rules (GTAR). A GTAR extends traditional association rules to discover temporal associations for complex events captured by a class of temporal pattern queries. We introduce notions of support and confidence for GTARS and formalize the discovery problem for GTARS. We show that despite the enhanced expressive power, GTARS discovery is feasible over large temporal graphs. We develop an effective rule discovery algorithm, which integrates event mining and rule discovery as a single process, and reduces the redundant computation by leveraging their interaction. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms. Our case study also verifies that GTARS demonstrate highly interpretable associations in real-world networks.
Fully Dynamic Algorithm for Top-k Densest Subgraphs
Authors: Muhammad Anis Uddin Nasir, Aristides Gionis, Gianmarco De Francisci Morales, Sarunas Girdzijauskas
Venue: CIKM
Year: 2017

Given a large graph,the densest-subgraph problem asks to find a subgraph with maximum average degree. When considering the top-k version of this problem, a naïve solution is to iteratively find the densest subgraph and remove it in each iteration. However, such a solution is impractical due to high processing cost. The problem is further complicated when dealing with dynamic graphs, since adding or removing an edge requires re-running the algorithm. In this paper, we study the top-k densest-subgraph problem in the sliding-window model and propose an efficient fully-dynamic algorithm. The input of our algorithm consists of an edge stream, and the goal is to find the node-disjoint subgraphs that maximize the sum of their densities. In contrast to existing state-of-the-art solutions that require iterating over the entire graph upon any update, our algorithm profits from the observation that updates only affect a limited region of the graph. Therefore, the top-k densest subgraphs are maintained by only applying local updates. We provide a theoretical analysis of the proposed algorithm and show empirically that the algorithm often generates denser subgraphs than state-of-the-art competitors. Experiments show an improvement in efficiency of up to five orders of magnitude compared to state-of-the-art solutions.
J-REED: Joint Relation Extraction and Entity Disambiguation
Authors: Dat Ba Nguyen, Martin Theobald, Gerhard Weikum
Venue: CIKM
Year: 2017

Information extraction (IE) from text sources can either be performed as Model-based IE (i.e, by using a pre-specified domain of target entities and relations) or as Open IE (i.e., with no particular assumptions about the target domain). While Model-based IE has limited coverage, Open IE merely yields triples of surface phrases which are usually not disambiguated into a canonical set of entities and relations. This paper presents J-REED: a joint approach for entity disambiguation and relation extraction that is based on probabilistic graphical models. J-REED merges ideas from both Model-based and Open IE by mapping surface names to a background knowledge base, and by making surface relations as crisp as possible.
Analysis of Telegram, An Instant Messaging Service
Authors: Arash Dargahi Nobari, Negar Reshadatmand, Mahmood Neshati
Venue: CIKM
Year: 2017

Telegram has become one of the most successful instant messaging services in recent years. In this paper, we developed a crawler to gather its public data. To the best of our knowledge, this paper is the first attempt to analyze the structural and topical aspects of messages published in Telegram instant messaging service using crawled data. We also extracted the mention graph and page rank of our data collection which indicates important differences between linking patterns of Telegram nodes and other usual networks. We also classified messages to detect advertisement and spam messages.
Balancing Speed and Quality in Online Learning to Rank for Information Retrieval
Authors: Harrie Oosterhuis, Maarten de Rijke
Venue: CIKM
Year: 2017

In Online Learning to Rank (OLTR) the aim is to find an optimal ranking model by interacting with users. When learning from user behavior, systems must interact with users while simultaneously learning from those interactions. Unlike other Learning to Rank (LTR) settings, existing research in this field has been limited to linear models. This is due to the speed-quality tradeoff that arises when selecting models: complex models are more expressive and can find the best rankings but need more user interactions to do so, a requirement that risks frustrating users during training. Conversely, simpler models can be optimized on fewer interactions and thus provide a better user experience, but they will converge towards suboptimal rankings. This tradeoff creates a deadlock, since novel models will not be able to improve either the user experience or the final convergence point, without sacrificing the other. Our contribution is twofold. First, we introduce a fast OLTR model called Sim-MGD that addresses the speed aspect of the speed-quality tradeoff. Sim-MGD ranks documents based on similarities with reference documents. It converges rapidly and, hence, gives a better user experience but it does not converge towards the optimal rankings. Second, we contribute Cascading Multileave Gradient De- scent (C-MGD) for OLTR that directly addresses the speed-quality tradeoff by using a cascade that enables combinations of the best of two worlds: fast learning and high quality final convergence. C-MGD can provide the better user experience of Sim-MGD while maintaining the same convergence as the state-of-the-art MGD model. This opens the door for future work to design new models for OLTR without having to deal with the speed-quality tradeoff.
Boolean Matrix Decomposition by Formal Concept Sampling
Authors: Petr Osicka, Martin Trnecka
Venue: CIKM
Year: 2017

Finding interesting patterns is a classical problem in data mining. Boolean matrix decomposition is nowadays a standard tool that can find a set of patterns-also called factors-in Boolean data that explain the data well. We describe and experimentally evaluate a probabilistic algorithm for Boolean matrix decomposition problem. The algorithm is derived from GreCon algorithm which uses formal concepts-maximal rectangles or tiles-as factors in order to find a decomposition. We change the core of GreCon by substituting a sampling procedure for a deterministic computation of suitable formal concepts. This allows us to alleviate the greedy nature of GreCon, creates a possibility to bypass some of the its pitfalls and to preserve its features, e.g. an ability to explain the entire data.
Enhancing Knowledge Graph Completion By Embedding Correlations
Authors: Soumajit Pal, Jacopo Urbani
Venue: CIKM
Year: 2017

Despite their large sizes, modern Knowledge Graphs (KGs) are still highly incomplete. Statistical relational learning methods can detect missing links by "embedding" the nodes and relations into latent feature tensors. Unfortunately, these methods are unable to learn good embeddings if the nodes are not well-connected. Our proposal is to learn embeddings for correlations between subgraphs and add a post-prediction phase to counter the lack of training data. This technique, applied on top of methods like TransE or HolE, can significantly increase the predictions on realistic KGs.
Robust Heterogeneous Discriminative Analysis for Single Sample Per Person Face Recognition
Authors: Meng Pang, Yiu-ming Cheung, Binghui Wang, Risheng Liu
Venue: CIKM
Year: 2017

Single sample face recognition is one of the most challenging problems in face recognition (FR), where only one single sample per person (SSPP) is enrolled in the gallery set for training. Although patch-based methods have achieved great success in FR with SSPP, they still have significant limitations. In this work, we propose a new patch-based method, namely Robust Heterogeneous Discriminative Analysis (RHDA), to tackle FR with SSPP. Compared with the existing patch-based methods, RHDA can enhance the robustness against complex facial variations from two aspects. First, we develop a novel Fisher-like criterion, which incorporates two manifold embeddings, to learn heterogeneous discriminative representations of image patches. Specifically, for each patch, the Fisher-like criterion is able to preserve the reconstruction relationship of neighboring patches from the same person, while suppressing neighboring patches from different persons. Second, we present two distance metrics, i.e., patch-to-patch distance and patch-to-manifold distance, and develop a fusion strategy to combine the recognition outputs of above two distance metrics via joint majority voting for identification. Experimental results on the AR and FERET benchmark datasets demonstrate the efficacy of the proposed method.
Deep Neural Networks for News Recommendations
Authors: Keunchan Park, Jisoo Lee, Jaeho Choi
Venue: CIKM
Year: 2017

A fundamental role of news websites is to recommend articles that are interesting to read. The key challenge of news recommendation is to recommend newly published articles. Unlike other domains, outdated items are considered to be irrelevant in the news recommendation task. Another challenge is that the recommendation candidates are not seen in the training phase. In this paper, we introduce deep neural network models to overcome these challenges. we propose a modified session-based Recurrent Neural Network (RNN) model tailored to news recommendation as well as a history-based RNN model that spans the whole user's past histories. Finally, we propose a Convolutional Neural Network (CNN) model to capture user preferences and to personalize recommendation results. Experimental results on real-world news dataset shows that our model outperforms competitive baselines.
An Interactive Framework for Video Surveillance Event Detection and Modeling
Authors: Fabio Persia, Fabio Bettini, Sven Helmer
Venue: CIKM
Year: 2017

We present a framework for high-level event detection in video streams based on a novel temporal extension of relational algebra. With the help of intuitive and interactive graphical user interfaces, a user can have a look at the different layers of our system to gain insights into the inner workings of the system, as well as create new events on the fly and track their processing through the system. As a proof-of-concept we have predefined events on three video surveillance data sets, but we also plan to run a demo with a live video stream generated by a local webcam.
A Two-Stage Framework for Computing Entity Relatedness in Wikipedia
Authors: Marco Ponza, Paolo Ferragina, Soumen Chakrabarti
Venue: CIKM
Year: 2017

Introducing a new dataset with human judgments of entity relatedness, we present a thorough study of all entity relatedness measures in recent literature based on Wikipedia as the knowledge graph. No clear dominance is seen between measures based on textual similarity and graph proximity. Some of the better measures involve expensive global graph computations. We then propose a new, space-efficient, computationally lightweight, two-stage framework for relatedness computation. In the first stage, a small weighted subgraph is dynamically grown around the two query entities; in the second stage, relatedness is derived based on computations on this subgraph. Our system shows better agreement with human judgment than existing proposals both on the new dataset and on an established one. We also plug our relatedness algorithm into a state-of-the-art entity linker and observe an increase in its accuracy and robustness.
Efficient Document Filtering Using Vector Space Topic Expansion and Pattern-Mining: The Case of Event Detection in Microposts
Authors: Julia Proskurnia, Ruslan Mavlyutov, Carlos Castillo, Karl Aberer, Philippe Cudré-Mauroux
Venue: CIKM
Year: 2017

Automatically extracting information from social media is challenging given that social content is often noisy, ambiguous, and inconsistent. However, as many stories break on social channels first before being picked up by mainstream media, developing methods to better handle social content is of utmost importance. In this paper, we propose a robust and effective approach to automatically identify microposts related to a specific topic defined by a small sample of reference documents. Our framework extracts clusters of semantically similar microposts that overlap with the reference documents, by extracting combinations of key features that define those clusters through frequent pattern mining. This allows us to construct compact and interpretable representations of the topic, dramatically decreasing the computational burden compared to classical clustering and k-NN-based machine learning techniques and producing highly-competitive results even with small training sets (less than 1'000 training objects). Our method is efficient and scales gracefully with large sets of incoming microposts. We experimentally validate our approach on a large corpus of over 60M microposts, showing that it significantly outperforms state-of-the-art techniques.
Active Learning for Large-Scale Entity Resolution
Authors: Kun Qian, Lucian Popa, Prithviraj Sen
Venue: CIKM
Year: 2017

Entity resolution (ER) is the task of identifying different representations of the same real-world object across datasets. Designing and tuning ER algorithms is an error-prone, labor-intensive process, which can significantly benefit from data-driven, automated learning methods. Our focus is on "big data'' scenarios where the primary challenges include 1) identifying, out of a potentially massive set, a small subset of informative examples to be labeled by the user, 2) using the labeled examples to efficiently learn ER algorithms that achieve both high precision and high recall, and 3) executing the learned algorithm to determine duplicates at scale. Recent work on learning ER algorithms has employed active learning to partially address the above challenges by aiming to learn ER rules in the form of conjunctions of matching predicates, under precision guarantees. While successful in learning a single rule, prior work has been less successful in learning multiple rules that are sufficiently different from each other, thus missing opportunities for improving recall. In this paper, we introduce an active learning system that learns, at scale, multiple rules each having significant coverage of the space of duplicates, thus leading to high recall, in addition to high-precision. We show the superiority of our system on real-world ER scenarios of sizes up to tens of millions of records, over state-of-the-art active learning methods that learn either rules or committees of statistical classifiers for ER, and even over sophisticated methods based on first-order probabilistic models.
An Attention-based Collaboration Framework for Multi-View Network Representation Learning
Authors: Meng Qu, Jian Tang, Jingbo Shang, Xiang Ren, Ming Zhang, Jiawei Han
Venue: CIKM
Year: 2017

Learning distributed node representations in networks has been attracting increasing attention recently due to its effectiveness in a variety of applications. Existing approaches usually study networks with a single type of proximity between nodes, which defines a single view of a network. However, in reality there usually exists multiple types of proximities between nodes, yielding networks with multiple views. This paper studies learning node representations for networks with multiple views, which aims to infer robust node representations across different views. We propose a multi-view representation learning approach, which promotes the collaboration of different views and lets them vote for the robust representations. During the voting process, an attention mechanism is introduced, which enables each node to focus on the most informative views. Experimental results on real-world networks show that the proposed approach outperforms existing state-of-the-art approaches for network representation learning with a single view and other competitive approaches with multiple views.
Efficient Computation of Subspace Skyline over Categorical Domains
Authors: Md Farhadur Rahman, Abolfazl Asudeh, Nick Koudas, Gautam Das
Venue: CIKM
Year: 2017

Platforms such as AirBnB, Zillow, Yelp, and related sites have transformed the way we search for accommodation, restaurants, etc. The underlying datasets in such applications have numerous attributes that are mostly Boolean or Categorical. Discovering the skyline of such datasets over a subset of attributes would identify entries that stand out while enabling numerous applications. There are only a few algorithms designed to compute the skyline over categorical attributes, yet are applicable only when the number of attributes is small. In this paper, we place the problem of skyline discovery over categorical attributes into perspective and design efficient algorithms for two cases. (i) In the absence of indices, we propose two algorithms, ST-S and ST-P, that exploit the categorical characteristics of the datasets, organizing tuples in a tree data structure, supporting efficient dominance tests over the candidate set. (ii) We then consider the existence of widely used precomputed sorted lists. After discussing several approaches, and studying their limitations, we propose TA-SKY, a novel threshold style algorithm that utilizes sorted lists. Moreover, we further optimize TA-SKY and explore its progressive nature, making it suitable for applications with strict interactive requirements. In addition to the extensive theoretical analysis of the proposed algorithms, we conduct a comprehensive experimental evaluation of the combination of real (including the entire AirBnB data collection) and synthetic datasets to study the practicality of the proposed algorithms. The results showcase the superior performance of our techniques, outperforming applicable approaches by orders of magnitude.
Talking to Your TV: Context-Aware Voice Search with Hierarchical Recurrent Neural Networks
Authors: Jinfeng Rao, Ferhan Türe, Hua He, Oliver Jojic, Jimmy Lin
Venue: CIKM
Year: 2017

We tackle the novel problem of navigational voice queries posed against an entertainment system, where viewers interact with a voice-enabled remote controller to specify the TV program to watch. This is a difficult problem for several reasons: such queries are short, even shorter than comparable voice queries in other domains, which offers fewer opportunities for deciphering user intent. Furthermore, ambiguity is exacerbated by underlying speech recognition errors. We address these challenges by integrating word- and character-level query representations and by modeling voice search sessions to capture the contextual dependencies in query sequences. Both are accomplished with a probabilistic framework in which recurrent and feedforward neural network modules are organized in a hierarchical manner. From a raw dataset of 32M voice queries from 2.5M viewers on the Comcast Xfinity X1 entertainment system, we extracted data to train and test our models. We demonstrate the benefits of our hybrid representation and context-aware model, which significantly outperforms competitive baselines that use learning to rank as well as neural networks.
Machine Learning @ Amazon
Authors: Rajeev Rastogi
Venue: CIKM
Year: 2017

In this talk, I will first provide an overview of key problem areas where we are applying Machine Learning (ML) techniques within Amazon such as product demand forecasting, product search, and information extraction from reviews, and associated technical challenges. I will then talk about three specific applications where we use a variety of methods to learn semantically rich representations of data: question answering where we use deep learning techniques, product size recommendations where we use probabilistic models, and fake reviews detection where we use tensor factorization algorithms.
Storyfinder: Personalized Knowledge Base Construction and Management by Browsing the Web
Authors: Steffen Remus, Manuel Kaufmann, Kathrin Ballweg, Tatiana von Landesberger, Chris Biemann
Venue: CIKM
Year: 2017

This paper presents Storyfinder, an application which consists of a browser plugin and a web server backend with the goal to highlight and manage the information contained in web pages by combining techniques from natural language processing and visual analytics. Webpages are analyzed while visiting them by means of natural language processing components, and metadata in the form of named entities and keywords are extracted and stored for further reference. The extracted information is instantaneously highlighted in the web page and stored in a graph of entities and relations. The graph can be inspected and modified. The investigational scope can be set to a single web page, multiple web pages, or the complete set of analyzed web pages in a user's history. The graph view is designed to adhere to standards of visual analytics and information visualization. Storyfinder is available as an open source application. Its benefit for information access is evaluated in a small user study.