Workshop on Graph Learning

A workshop on Graph Learning will be held at LINCS on May 14h, 2018:

https://www.lincs.fr/workshop-on-graph-learning/

The objective of this workshop is to bring together people from industry and academia for presenting and discussing the most recent learning techniques based on graphs, from both theoretical and practical perspectives.

The workshop will cover the following aspects:

  • Graph clustering
  • Topic detection
  • Recommender systems
  • Graph-based classification
  • Link prediction
  • Graph alignment
  • Social networks
  • Dynamic graphs
  • Graph signal processing

Speakers
Oana Balalau (Max-Planck Institute)
Alexis Benichoux (Deezer)
Pierre Borgnat (ENS Lyon)
Stephan Clémençon (Telecom ParisTech)
Vincent Cohen-Addad (CNRS / UPMC)
Matthias Grossglauser (EPFL)
Alexandre Hollocou (Inria)
Hervé Jegou (Facebook)
Renaud Lambiotte (University of Oxford)
Matthieu Latapy (CNRS / UPMC)
Dimitrios Milioris (Nokia Bell Labs)
Eric Siboni (Shift Technologies)
Michal Valko (Inria)

Organizers

Thomas Bonald (Telecom ParisTech)
Marc Lelarge (Inria)
Laurent Massoulié (Inria / Microsoft)

LTCI Chercheur en vue : Fabian Suchanek

Article appeared at LTCI Chercheur en vue on 

Fabian Suchanek

Fabian Suchanek est professeur à Télécom ParisTech. Il a rejoint l’école en 2013. Au sein du LTCI, le travail du chercheur porte sur les graphes et plus particulièrement sur les bases de connaissance. Il s’occupe à la fois de la construction automatique des bases de connaissance mais aussi de la fouille de données dans ces bases. Cette fouille de données trouve des motifs ; par exemple, si une personne est mariée et réside dans une certaine ville, il est fort probable que son époux/se y vive également etc. La fouille de données peut également trouver quels sont les attributs obligatoires d’une classe d’entités (tel que l’âge pour une personne) et quels sont les attributs optionnels (tel que l’époux d’une personne). Et un travail de recherche, mené avec ParisSud, le centre Inra de Montpellier et Inria Rennes, porte sur la fouille de clés, à savoir une clé est une combinaison d’attributs qui identifie une entité de manière unique (pour une personne, cela va être son prénom, son nom et sa date de naissance par exemple). Pour le chercheur, il s’agit à chaque fois d’établir des « contraintes » qui vont servir à nettoyer les bases de données. Fabian Suchanek travaille également sur les trends historiques, en collaboration avec l’Université de Stockholm : ces travaux permettent notamment de tracer l’évolution de l’espérance de vie à travers les âges.

 

Elvis Presley dans la base de connaissance Yago

En parallèle, depuis 2013, Fabian Suchanek a principalement continué à développer la base de connaissance dont il est le fondateur, Yago. Fruit d’une collaboration avec l’Institut Max Planck, celle-ci est aujourd’hui l’une des plus grandes bases publiques de connaissance créée à partir de Wikipédia, et son code source a été dévoilé en 2017, année du dixième anniversaire de sa création (voir notre interview). Le chercheur et son équipe ont par ailleurs été distingués en 2017 par le “Prominent Paper Award”, qui récompense chaque année une publication exceptionnelle en termes de contenu et d’impact de la revue The Artificial Intelligence Journal. Ils travaillent à présent à une nouvelle version de Yago, toujours aux côtés de l’Institut Max Planck.

 

Un extrait de base de connaissance

 

En 2016, le chercheur a travaillé avec l’Université de Montpellier et la start-up Stim, incubée à ParisTech Entrepreneurs, à améliorer la créativité des ordinateurs, afin que ces derniers inventent des concepts et proposent automatiquement de nouvelles idées.

Ses travaux récents incluent également une collaboration avec Inria et Paris-Saclay sur le concept des bases de connaissance privées. Fabian Suchaneck a ainsi participé à l’élaboration d’un système permettant de rapatrier toutes les données des réseaux sociaux sur une base de données privée.

SWERC 2017 (South-Western Europe Regional Contest)

Antoine Amarilli was the Director of SWERC 2017 (South-Western Europe Regional Contest), a prestigious international programming contest organised with the support of the scientific organisation ACM (Association for Computing Machinery) by researchers from Télécom ParisTech and from École Normale Supérieure.

The 2017 edition of the ACM-ICPC-SWERC programming contest ended with the victory of a team from ENS Ulm Paris, followed closely by a team from ETH Zürich. These two teams will represent Southwestern Europe at the World Finals, to be held in Beijing next April. With 76 teams registered and 228 students from 48 universities, the 2017 edition broke participation records. The contestants competed on eleven problems and received one balloon for each solved exercise. More than 300 balloons were distributed.

SWERC 2017 was organized on Nov. 25-26 by Télécom ParisTech and Ecole normale supérieure. The contest was supported by the ICPC Foundation, Criteo Labs, Palantir, Société Générale (Gold sponsors), Télécom ParisTech and Almerys (Silver sponsors), Google and Inria (Bronze sponsors).

LTCI Chercheur en vue : Thomas Bonald

Article appeared at LTCI Chercheur en vue on 

Thomas Bonald

Enseignant-chercheur à Télécom ParisTech depuis 2009, Thomas Bonald  mène ses activités de recherche au sein des laboratoires LTCI et LINCS. Ses travaux portent sur la fouille de graphes, sur les techniques d’apprentissage et sur l’analyse de performance des réseaux et des centres de données.

Les graphes, qui servent à représenter des relations entre tous types d’objets physiques ou virtuels, sont devenus incontournables dans l’analyse des grandes masses de données. Par exemple, l’encyclopédie Wikipedia peut être représentée par un graphe correspondant aux liens hypertextes entre les millions de pages qui la composent ; les ventes réalisées par une entreprise forment un graphe liant produits et clients ; un corpus de textes peut être représenté par un graphe de similarité entre les textes. Pour faciliter diverses tâches de détection, de prédiction et de recommandation sur ces données, il est important d’avoir des représentations compactes des graphes, en associant par exemple à chaque nœud du graphe un point dans un espace métrique de faible dimension. Le chercheur s’intéresse à ce type de représentations, dans le cadre de collaborations avec Inria et Thalès notamment.

Clustering hiérarchique des principaux aéroports internationaux basé sur une représentation spectrale du graphe openflight

 

Un autre axe de recherche de Thomas Bonald concerne l’apprentissage automatique de données multi-variées, comme celles issues de capteurs d’un moteur d’avion ou d’hélicoptère. Comment détecter un état d’usure anormal du moteur et prédire le besoin d’une opération de maintenance ? Diverses techniques sont explorées, comme les réseaux de neurones récurrents. Ces travaux sont menés dans le cadre d’une collaboration avec Safran.

 

Extrait des données d’un vol d’hélicoptère (source : Safran)

Enfin, l’enseignant-chercheur s’intéresse à la performance des réseaux et des centres de données. Il s’agit ici de concevoir des modèles simples mais réalistes du partage dynamique des ressources (bande passante, CPU, RAM, etc.) entre les utilisateurs, afin de proposer des règles de dimensionnement efficaces et de nouveaux algorithmes d’allocation de ressources. Thomas Bonald a publié avec Mathieu Feuillet un livre sur les principales techniques d’analyse de performance des réseaux et a reçu en 2013 la médaille Blondel pour ses travaux sur le sujet, développés notamment dans les laboratoires d’Orange. Ses travaux actuels sont menés dans le cadre de collaborations avec Nokia et Cisco.

 

The fundamentals of language: why do we talk? – Jean-Louis Dessalles, Télécom ParisTech

Article appeared at IMT Live Labs on   https://www.imt.fr/en/entrailles-langage-parlons/

Human language is a mystery. In a society where information is so valuable, why do we talk to others without expecting anything in return? Even more intriguing than this are the processes determining communication, whether that be a profound debate or a spontaneous conversation with an acquaintance. These are the questions driving Jean-Louis Dessalles’ current project, a researcher in computing at Télécom ParisTech. His work has led him to reconsider the perspective on information adopted by Claude Shannon, a pioneer in the field. He has devised original theories and conversational models which explain trivial discussions just as well as heated debates.

Why do we talk? And what do we talk about? Fueled with the optimism of a young researcher, Jean-Louis Dessalles hoped to find the answer to these two questions in just a few months after finishing his thesis in 1993. Nearly 24 years have now passed, and the subject of his research has not changed. From his office in the Computing and Networks department at Télécom ParisTech, he continues to have an interest in Language. His work breaks away from the classic approach adopted by researchers in information science and communication. “The discipline mainly focuses on ways we can convey messages, but not about what is conveyed or why”, he explains, contradicting the approach to communication described by Claude Shannon in 1948.

 

The reasons for communication, along with the underlying motives for these information exchanges, are however very legitimate and complex questions. As the researcher explains in the film “Le Grand Roman de l’Homme”, which came out in 2014, communication is contradictory of various behavioral theories. Game theory for example, sometimes used in economy to describe and analyze behavioral mechanisms, struggles to justify the role of communication between humans. According to this theory, and by attaching value to all information, expected communication situations would consist in each participant providing the minimum information possible, whilst trying to glean the maximum from the other person. However this logic is not followed by humans in everyday discussions. “We need to consider the role of communication in a social context” deduces Jean-Louis Dessalles.

By dissecting the scientific elements in communication situations (i.e. interviews, attitudes in online forums, discussions, etc.) he has tried to find an explanation for people offering up useful information. The hypothesis he is putting forward today is compatible with all observable communication types; for him, offering up quality information is not motivated by economic gain, as game theory assumes, but rather by a gain in social reputation. “In technical online forums for example, experts don’t respond out of altruism, or for monetary gain. They are competing to give the most complete response in order to assert their status as an expert. In this way they gain social significance”, explains the researcher. Talking and showing our ability to stay informed is therefore synonymous with positioning ourselves in a social hierarchy.

When the unexpected liberates language

With the question of “why do we talk” cleared up, we still need to find out what it is we are talking about. Jean-Louis Dessalles isn’t interested in the subject of discussions per-say, but rather the general mechanisms dominating the act of communication. After having analyzed in detail tens of hours of recordings, he has come to the conclusion that a large part of spontaneous exchange is structured around the unexpected. The triggers of spontaneous conversation are often events that humans would consider unlikely or abnormal, in other words, when the normality of a situation is broken. For example, seeing a person over 2m tall, a series of cars of the same color all parked in a row or a lotto draw where all the numbers follow on from one another; these are all instances which are likely to provoke surprise in an individual, and encourage them to engage in spontaneous conversation with an interlocutor.

In order to explain this engagement based on the unexpected, Jean-Louis Dessalles has developed Simplicity Theory. According to him, the unexpected corresponds above all else to things which are simple to describe. He says “simple” because it is always easy to describe an out-of-the-ordinary situation, simply by placing the focus on the unexpected thing. For example, describing a person that is 2m tall is easy because this criterion alone is enough to establish a narration point. In contrast, describing a person of normal height and weight with standard clothes and a face with no distinctive features in particular would require a more complex description to achieve a successful definition.

Although simplicity may be a driver for spontaneous conversation, another significant discussion category also exists: that of argumentative conversation. In this case, the unexpected no longer applies. This kind of exchange follows a model defined by Jean-Louis Dessalles, called CAN (Conflict, Abduction, and Negation). “To start an argument, there has to be a conflict, opposing points of view. Abduction is the following stage, which consists in going back to the cause of the conflict in order to shift this and deploy arguments. Finally, negation allows the participants to progress to counterfactuals in order to reflect on solutions which would allow them to resolve the conflict.” Beyond that simple description, the CAN model could allow the development of artificial intelligence to progress (see text box).

In the hours of conversation recorded by the researcher, the distribution of spontaneous discussions induced by unexpected elements and arguments was respectively 25% and 75%. He remarks however that the line separating the two is not necessarily strict, since spontaneous narration can lead to a more profound debate, which would dramatically change the basis of the CAN model. These results offer a response to the question “what do we talk about?” and solidify years of research. For Jean-Louis Dessalles, it’s proof that “it pays to be naïve”. His recklessness at the beginning eventually led him to theorize various models throughout his career, on which humans base their communication, and will probably continue to do so for a long time to come.

When artificial intelligence looks at language theories

“Machines should be able to have a reasonable conversation in order to appear intelligent”, assures Jean-Louis Dessalle. For the researcher, the test invented by Alan Turing, consisting in claiming that a machine is intelligent if a human can’t tell the difference between it and another human when having a conversation, is completely legitimate. Because of this, his work has found a place in the development of artificial intelligence that is able to pass this test. It is therefore absolutely essential to understand human communication mechanisms in order to transfer these to machines. A machine integrating the CAN model would be more able to have a debate with a human. In the case of a GPS, it would allow the device to plan routes whilst incorporating factors other than simply time or distance. Discussing with a GPS what we expect from a journey – such as beautiful scenery for example – in a logical manner, would significantly extend the quality of the human machine interface.

Jean-Louis Dessalles, human language specialist

Jean-Louis Dessalles a travaillé sur le langage.

A Polytechnique and Télécom ParisTech graduate, Jean-Louis Dessalles became a researcher in computing after obtaining his PhD in 1993. It is therefore difficult to see the link to questions regarding human language and its origins, something normally reserved for linguists or ethnologists. “I chose to focus on a subject relevant to the resources I had available to me, which were computer sciences”, he argues. He then carried out research which contradicts the probabilistic approach of Claude Shannon, which is how he presented it to a conference at the Insitut Henri Poincaré in October 2016 for the centenary of the father of information theory. His reflections on information have been the subject of a book, “Le fil de la vie”, published by Odile Jacob in 2016. He is also the author of several books about the question of language emergence.