Claudio Pinhanez, Paulo Cavalin, Victor Henrique Alves Ribeiro, Ana Appel, Heloisa Candello, Julio Nogima, Mauro Pichiliani, Melina Guerra, Maira de Bayser, Gabriel Malfatti, Henrique Ferreira. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

This paper describes how machine learning training data and symbolic knowledge from curators of conversational systems can be used together to improve the accuracy of those systems and to enable better curatorial tools. This is done in the context of a real-world practice of curators of conversational systems who often embed taxonomically-structured meta-knowledge into their documentation. The paper provides evidence that the practice is quite common among curators, that is used as part of their collaborative practices, and that the embedded knowledge can be mined by algorithms. Further, this meta-knowledge can be integrated, using neuro-symbolic algorithms, to the machine learning-based conversational system, to improve its run-time accuracy and to enable tools to support curatorial tasks. Those results point towards new ways of designing development tools which explore an integrated use of code and documentation by machines.

This paper explores how intent classification can be improved by representing the class labels not as a discrete set of symbols but as a space where the word graphs associated to each class are mapped using typical graph embedding techniques.The approach, inspired by a previous algorithm used for an inverse dictionary task, allows the classification algorithm to take in account inter-class similarities provided by the repeated occurrence of some words in the training examples of the different classes.The classification is carried out by mapping text embeddings to the word graph embeddings of the classes.Focusing solely on improving the representation of the class label set, we show in experiments conducted in both private and public intent classification datasets, that better detection of out-of-scope examples (OOS) is achieved and, as a consequence, that the overall accuracy of intent classification is also improved.In particular, using the recently-released Larson dataset, an error of about 9.9% has been achieved for OOS detection, beating the previous state-of-the-art result by more than 31 percentage points.

Given large, multimillion-node graphs (e.g., Facebook, Web-crawls, etc.), how do they evolve over time? How are they connected? What are the central nodes and the outliers? In this article we define the Radius plot of a graph and show how it can answer these questions. However, computing the Radius plot is prohibitively expensive for graphs reaching the planetary scale. There are two major contributions in this article: (a) We propose HADI (HAdoop DIameter and radii estimator), a carefully designed and fine-tuned algorithm to compute the radii and the diameter of massive graphs, that runs on the top of the Hadoop / MapReduce system, with excellent scale-up on the number of available machines (b) We run HADI on several real world datasets including YahooWeb (6B edges, 1/8 of a Terabyte), one of the largest public graphs ever analyzed. Thanks to HADI, we report fascinating patterns on large networks, like the surprisingly small effective diameter, the multimodal/bimodal shape of the Radius plot, and its palindrome motion over time.

Given large, multi-million node graphs (e.g., FaceBook, web-crawls, etc.), how do they evolve over time? How are they connected? What are the central nodes and the outliers of the graphs? We show that the Radius Plot (pdf of node radii) can answer these questions. However, computing the Radius Plot is prohibitively expensive for graphs reaching the planetary scale. There are two major contributions in this paper: (a) We propose HADI (HAdoop DIameter and radii estimator), a carefully designed and fine-tuned algorithm to compute the diameter of massive graphs, that runs on the top of the Hadoop/MapReduce system, with excellent scale-up on the number of available machines (b) We run HADI on several real world datasets including YahooWeb (6B edges, 1/8 of a Terabyte), one of the largest public graphs ever analyzed. Thanks to HADI, we report fascinating patterns on large networks, like the surprisingly small effective diameter, the multi-modal/bi-modal shape of the Radius Plot, and its palindrome motion over time.

Graphs appear in several settings, like social networks, recommendation systems, computer communication networks, gene/protein biological networks, among others. A deep, recurring question is “What do real graphs look like?” That is, how can we separate real ones from synthetic or real graphs with masked portions? The main contribution of this paper is ShatterPlots, a simple and powerful algorithm to extract patterns from real graphs that help us spot fake/masked graphs. The idea is to shatter a graph, by deleting edges, force it to reach a critical (“Shattering”) point, and study the properties at that point. One of the most striking patterns is the “30-per-cent“: at the Shattering point, all real and synthetic graphs have about 30% more nodes than edges. One of our most discriminative patterns is the “NodeShatteringRatio“, which can almost perfectly separate the real graphs from the synthetic ones of our extensive collection. Additional contributions of this paper are (a) the careful, scalable design of the algorithm, which requires only O(E) time, (b) extensive experiments in a large collection of graphs (19 in total), with up to hundreds of thousands of nodes and million edges, and (c) a wealth of observations and patterns, which show how to distinguish synthetic or masked graphs from real ones.