pwc-archive/papers-with-abstracts huggingface dataset:
Walking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness
Authors: Yongkun Li, Zhiyong Wu, Shuai Lin, Hong Xie, Min Lv, Yinlong Xu, John C. S. Lui
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Computational Efficiency

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient "unbiased sampling" schemes. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms. Furthermore, to achieve the same estimation accuracy, our approach reduces the query cost (a measure of sampling budget) significantly. Lastly, we also use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.
NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching
Authors: Dingqi Yang, Paolo Rosso, Bin Li, Philippe Cudre-Mauroux
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5

Embeddings have become a key paradigm to learn graph represen-tations and facilitate downstream graph analysis tasks. Existinggraph embedding techniques either sample a large number of nodepairs from a graph to learn node embeddings via stochastic op-timization, or factorize a high-order proximity/adjacency matrixof the graph via expensive matrix factorization. However, thesetechniques usually require significant computational resources forthe learning process, which hinders their applications on large-scale graphs. Moreover, the cosine similarity preserved by thesetechniques shows suboptimal efficiency in downstream graph anal-ysis tasks, compared to Hamming similarity, for example. To ad-dress these issues, we propose NodeSketch, a highly-efficient graphembedding technique preserving high-order node proximity viarecursive sketching. Specifically, built on top of an efficient data-independent hashing/sketching technique, NodeSketch generatesnode embeddings in Hamming space. For an input graph, it starts bysketching the self-loop-augmented adjacency matrix of the graphto output low-order node embeddings, and then recursively gener-atesk-order node embeddings based on the self-loop-augmentedadjacency matrix and (k-1)-order node embeddings. Our extensiveevaluation compares NodeSketch against a sizable collection ofstate-of-the-art techniques using five real-world graphs on twograph analysis tasks. The results show that NodeSketch achievesstate-of-the-art performance compared to these techniques, whileshowing significant speedup of 9x-372x in the embedding learningprocess and 1.19x-1.68x speedup when performing downstreamgraph analysis tasks
Asymmetric Transitivity Preserving Graph Embedding
Authors: Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, Wenwu Zhu
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Graph Embedding, Link Prediction

Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity well, which is a critical property of directed graphs. Asymmetric transitivity depicts the correlation among directed edges, that is, if there is a directed path from u to v, then there is likely a directed edge from u to v. Asymmetric transitivity can help in capturing structures of graphs and recovering from partially observed graphs. To tackle this challenge, we propose the idea of preserving asymmetric transitivity by approximating high-order proximity which are based on asymmetric transitivity. In particular, we develop a novel graph embedding algorithm, High-Order Proximity preserved Embedding (HOPE for short), which is scalable to preserve high-order proximities of large scale graphs and capable of capturing the asymmetric transitivity. More specifically, we first derive a general formulation that cover multiple popular high-order proximity measurements, then propose a scalable embedding algorithm to approximate the high-order proximity measurements based on their general formulation. Moreover, we provide a theoretical upper bound on the RMSE (Root Mean Squared Error) of the approximation. Our empirical experiments on a synthetic dataset and three real-world datasets demonstrate that HOPE can approximate the high-order proximities significantly better than the state-of-art algorithms and outperform the state-of-art algorithms in tasks of reconstruction, link prediction and vertex recommendation.
Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
Authors: Mikhail Belkin and Partha Niyogi
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Clustering, Dimensionality Reduction

One of the central problems in machine learning and pattern recognition is to develop appropriate representations for complex data. We consider the problem of constructing a representation for data lying on a low-dimensional manifold embedded in a high-dimensional space. Drawing on the correspondence between the graph Laplacian, the Laplace Beltrami operator on the manifold, and the connections to the heat equation, we propose a geometrically motivated algorithm for representing the high-dimensional data. The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality-preserving properties and a natural connection to clustering. Some potential applications and illustrative examples are discussed.
Fast Network Embedding Enhancement via High Order Proximity Approximation
Authors: Cheng Yang, Maosong Sun, Zhiyuan Liu, Cunchao Tu
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Dimensionality Reduction, Link Prediction, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Network Embedding, Representation Learning, Vocal Bursts Intensity Prediction

Many Network Representation Learning (NRL) methods have been proposed to learn vector representations for vertices in a network recently. In this paper, we summarize most existing NRL methods into a unified two-step framework, including proximity matrix construction and dimension reduction. We focus on the analysis of proximity matrix construction step and conclude that an NRL method can be improved by exploring higher order proximities when building the proximity matrix. We propose Network Embedding Update (NEU) algorithm which implicitly approximates higher order proximities with theoretical approximation bound and can be applied on any NRL methods to enhance their performances. We conduct experiments on multi-label classification and link prediction tasks. Experimental results show that NEU can make a consistent and significant improvement over a number of NRL methods with almost negligible running time on all three publicly available datasets.
LeNER-Br: a Dataset for Named Entity Recognition in Brazilian Legal Text
Authors: Pedro H. Luz de Araujo, Teófilo E. de Campos, Renato R. R. de Oliveira, Matheus Stauffer, Samuel Couto, Paulo Bermejo
Date: 2018-09-24 00:00:00
Proceeding: International Conference on the Computational Processing of Portuguese (PROPOR) 2018 9
Tasks: Decision Making, Information Retrieval, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), Retrieval

Named entity recognition systems have the untapped potential to extract information from legal documents, which can improve
information retrieval and decision-making processes. In this paper, a dataset for named entity recognition in Brazilian legal documents is presented. Unlike other Portuguese language datasets, this dataset is composed entirely of legal documents. In addition to tags for persons, locations, time entities and organizations, the dataset contains specific tags for law and legal cases entities. To establish a set of baseline results, we first performed experiments on another Portuguese dataset: Paramopama. This evaluation demonstrate that LSTM-CRF gives results that are significantly better than those previously reported. We then retrained LSTM-CRF, on our dataset and obtained F 1 scores of 97.04% and 88.82% for Legislation and Legal case entities, respectively.
These results show the viability of the proposed dataset for legal applications.
Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations
Authors: Jure Leskovec, Jon Kleinberg, Christos Faloutsos
Date: 2020-05-13 00:00:00
Proceeding: ‎‎‏‏‎ ‎ 2020 5
Tasks: Graph Generation

How do real graphs evolve over time? What are "normal" growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)). Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a "forest fire" spreading process, that has a simple, intuitive justification, requires very few parameters (like the "flammability" of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.
Metropolis Algorithms for Representative Subgraph Sampling
Authors: Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, Zoubin Ghahramani
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5

While data mining in chemoinformatics studied graph data with dozens of nodes, systems biology and the Internet are now generating graph data with thousands and millions of nodes. Hence data mining faces the algorithmic challenge of coping with this significant increase in graph size: Classic algorithms for data analysis are often too expensive and too slow on large graphs. While one strategy to overcome this problem is to design novel efficient algorithms, the other is to 'reduce' the size of the large graph by sampling. This is the scope of this paper: We will present novel Metropolis algorithms for sampling a 'representative' small subgraph from the original large graph, with 'representative' describing the requirement that the sample shall preserve crucial graph properties of the original graph. In our experiments, we improve over the pioneering work of Leskovec and Faloutsos (KDD 2006), by producing representative subgraph samples that are both smaller and of higher quality than those produced by other methods from the literature.
Walking in Facebook: A Case Study of Unbiased Sampling of OSNs
Authors: Minas Gjoka, Maciej Kurant, Carter T. Butts, Athina Markopoulou
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5

With more than 250 million active users, Facebook (FB) is currently one of the most important online social networks. Our goal in this paper is to obtain a representative (unbiased) sample of Facebook users by crawling its social graph. In this quest, we consider and implement several candidate techniques. Two approaches that are found to perform well are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW). Both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground-truth" (UNI - obtained through true uniform sampling of FB userIDs). In contrast, the traditional Breadth-First-Search (BFS) and Random Walk (RW) perform quite poorly, producing substantially biased results. In addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. We show how these can be used to effectively determine when a random walk sample is of adequate size and quality for subsequent use (i.e., when it is safe to cease sampling). Using these methods, we collect the first, to the best of our knowledge, unbiased sample of Facebook. Finally, we use one of our representative datasets, collected through MHRW, to characterize several key properties of Facebook.
Sampling Community Structure
Authors: Arun S. Maiya, Tanya Y. Berger-Wolf
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Community Detection, Relational Reasoning

We propose a novel method, based on concepts from expander graphs, to sample communities in networks. We show that our sampling method, unlike previous techniques, produces subgraphs representative of community structure in the original network. These generated subgraphs may be viewed as stratified samples in that they consist of members from most or all communities in the network. Using samples produced by our method, we show that the problem of community detection may be recast into a case of statistical relational learning. We empirically evaluate our approach against several real-world datasets and demonstrate that our sampling method can effectively be used to infer and approximate community affiliation in the larger network.
AI Augmentation of Radiologist Performance in Distinguishing COVID-19 from Pneumonia of Other Etiology on Chest CT
Authors: Harrison X. Bai, Robin Wang, Zeng Xiong, Ben Hsieh, Ken Chang, Kasey Halsey, Thi My Linh Tran, Ji Whae Choi, Dong-Cui Wang, Lin-Bo Shi, Ji Mei, Xiao-Long Jiang, Ian Pan, Qiu-Hua Zeng, Ping-Feng Hu, Yi-Hui Li, Fei-Xian Fu, Raymond Y. Huang, Ronnie Sebro, Qi-Zhi Yu, Michael K. Atalay, Wei-Hua Liao
Date: 2020-04-27 00:00:00
Proceeding: RSNA 2020 4
Tasks: COVID-19 Diagnosis, COVID-19 Image Segmentation, Sensitivity, Specificity

Background
COVID-19 and pneumonia of other etiology share similar CT characteristics, contributing to the challenges in differentiating them with high accuracy.

Purpose
To establish and evaluate an artificial intelligence (AI) system in differentiating COVID-19 and other pneumonia on chest CT and assess radiologist performance without and with AI assistance.

Methods
521 patients with positive RT-PCR for COVID-19 and abnormal chest CT findings were retrospectively identified from ten hospitals from January 2020 to April 2020. 665 patients with non-COVID-19 pneumonia and definite evidence of pneumonia on chest CT were retrospectively selected from three hospitals between 2017 and 2019. To classify COVID-19 versus other pneumonia for each patient, abnormal CT slices were input into the EfficientNet B4 deep neural network architecture after lung segmentation, followed by two-layer fully-connected neural network to pool slices together. Our final cohort of 1,186 patients (132,583 CT slices) was divided into training, validation and test sets in a 7:2:1 and equal ratio. Independent testing was performed by evaluating model performance on separate hospitals. Studies were blindly reviewed by six radiologists without and then with AI assistance.

Results
Our final model achieved a test accuracy of 96% (95% CI: 90-98%), sensitivity 95% (95% CI: 83-100%) and specificity of 96% (95% CI: 88-99%) with Receiver Operating Characteristic (ROC) AUC of 0.95 and Precision-Recall (PR) AUC of 0.90. On independent testing, our model achieved an accuracy of 87% (95% CI: 82-90%), sensitivity of 89% (95% CI: 81-94%) and specificity of 86% (95% CI: 80-90%) with ROC AUC of 0.90 and PR AUC of 0.87. Assisted by the models’ probabilities, the radiologists achieved a higher average test accuracy (90% vs. 85%, Δ=5, p<0.001), sensitivity (88% vs. 79%, Δ=9, p<0.001) and specificity (91% vs. 88%, Δ=3, p=0.001).

Conclusion
AI assistance improved radiologists' performance in distinguishing COVID-19 from non-COVID-19 pneumonia on chest CT.

Summary
AI assistance improved radiologists’ performance in distinguishing COVID-19 from pneumonia of other etiology on chest CT.
On Random Walk Based Graph Sampling
Authors: Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, Tan Ji
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5
Tasks: Graph Sampling

Random walk based graph sampling has been recognized as a fundamental technique to collect uniform node samples from a large graph. In this paper, we first present a comprehensive analysis of the drawbacks of three widely-used random walk based graph sampling algorithms, called re-weighted random walk (RW) algorithm, Metropolis-Hastings random walk (MH) algorithm and maximum-degree random walk (MD) algorithm. Then, to address the limitations of these algorithms, we propose two general random walk based algorithms, named rejection-controlled Metropolis-Hastings (RCMH) algorithm and generalized maximum-degree random walk (GMD) algorithm. We show that RCMH balances the tradeoff between the limitations of RW and MH, and GMD balances the tradeoff between the drawbacks of RW and MD. To further improve the performance of our algorithms, we integrate the so-called delayed acceptance technique and the non-backtracking random walk technique into RCMH and GMD respectively. We conduct extensive experiments over four real-world datasets, and the results demonstrate the effectiveness of the proposed algorithms.
Leveraging History for Faster Sampling of Online Social Networks
Authors: Zhuojie Zhou, Nan Zhang, Gautam Das
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5

With a vast amount of data available on online social networks, how to enable efficient analytics over such data has been an increasingly important research problem. Given the sheer size of such social networks, many existing studies resort to sampling techniques that draw random nodes from an online social network through its restrictive web/API interface. While these studies differ widely in analytics tasks supported and algorithmic design, almost all of them use the exact same underlying technique of random walk - a Markov Chain Monte Carlo based method which iteratively transits from one node to its random neighbor.

Random walk fits naturally with this problem because, for most online social networks, the only query we can issue through the interface is to retrieve the neighbors of a given node (i.e., no access to the full graph topology). A problem with random walks, however, is the "burn-in" period which requires a large number of transitions/queries before the sampling distribution converges to a stationary value that enables the drawing of samples in a statistically valid manner.

In this paper, we consider a novel problem of speeding up the fundamental design of random walks (i.e., reducing the number of queries it requires) without changing the stationary distribution it achieves - thereby enabling a more efficient "drop-in" replacement for existing sampling-based analytics techniques over online social networks. Technically, our main idea is to leverage the history of random walks to construct a higher-ordered Markov chain. We develop two algorithms, Circulated Neighbors and Groupby Neighbors Random Walk (CNRW and GNRW) and rigidly prove that, no matter what the social network topology is, CNRW and GNRW offer better efficiency than baseline random walks while achieving the same stationary distribution. We demonstrate through extensive experiments on real-world social networks and synthetic graphs the superiority of our techniques over the existing ones.
Sampling Social Networks Using Shortest Paths
Authors: Alireza Rezvanian, Mohammad Reza Meybodi
Date: 2020-05-13 00:00:00
Proceeding: ‏‏‎ ‎ 2020 5

In recent years, online social networks (OSN) have emerged as a platform of sharing variety of information about people, and their interests, activities, events and news from real worlds. Due to the large scale and access limitations (e.g., privacy policies) of online social network services such as Facebook and Twitter, it is difficult to access the whole public network in a limited amount of time. For this reason researchers try to study and characterize OSN by taking appropriate and reliable samples from the network. In this paper, we propose to use the concept of shortest path for sampling social networks. The proposed sampling method first finds the shortest paths between several pairs of nodes selected according to some criteria. Then the edges in these shortest paths are ranked according to the number of times that each edge has appeared in the set of found shortest paths. The sampled network is then computed as a subgraph of the social network which contains a percentage of highly ranked edges. In order to investigate the performance of the proposed sampling method, we provide a number of experiments on synthetic and real networks. Experimental results show that the proposed sampling method outperforms the existing method such as random edge sampling, random node sampling, random walk sampling and Metropolis–Hastings random walk sampling in terms of relative error (RE), normalized root mean square error (NMSE), and Kolmogorov–Smirnov (KS) test.
Domain Adaptation for Image Dehazing
Authors: Yuanjie Shao, Lerenhan Li, Wenqi Ren, Changxin Gao, Nong Sang
Date: 2020-05-10 00:00:00
Proceeding: CVPR 2020 6
Tasks: Domain Adaptation, Image Dehazing, Translation

Image dehazing using learning-based methods has achieved state-of-the-art performance in recent years. However, most existing methods train a dehazing model on synthetic hazy images, which are less able to generalize well to real hazy images due to domain shift. To address this issue, we propose a domain adaptation paradigm, which consists of an image translation module and two image dehazing modules. Specifically, we first apply a bidirectional translation network to bridge the gap between the synthetic and real domains by translating images from one domain to another. And then, we use images before and after translation to train the proposed two image dehazing networks with a consistency constraint. In this phase, we incorporate the real hazy image into the dehazing training via exploiting the properties of the clear image (e.g., dark channel prior and image gradient smoothing) to further improve the domain adaptivity. By training image translation and dehazing network in an end-to-end manner, we can obtain better effects of both image translation and dehazing. Experimental results on both synthetic and real-world images demonstrate that our model performs favorably against the state-of-the-art dehazing algorithms.