Graphons and Machine Learning: Modeling and Estimation of Sparse Networks at Scale

Abstract

There are numerous examples of sparse network at scale, in particular the Internet, the WWW, online social networks, and large bipartite networks used for recommendations. How do we model and learn these networks? In contrast to conventional learning problems, where we have many independent samples, it is often the case for these networks that we can get only one independent sample. How do we use a single snapshot today to learn a model for the network, and therefore be able to predict a similar, but larger network in the future? In the case of relatively small or moderately sized networks, it’s appropriate to model the network parametrically, and attempt to learn these parameters. For networks at scale, a non-parametric representation is more appropriate. In this talk, we first review the theory of graphons, developed over the 15 years to describe limits of dense graphs, and the more the recent theory describing sparse graphs of unbounded average degree, including power-law graphs. We then show how to use these graphons as non-parametric models for sparse networks. We show how to get consistent estimators of these non-parametric models, and moreover how to do this in a way that protects the privacy of individuals on the network. Finally, we provide algorithms based on these models, for example for recommendation algorithms in sparse bipartite networks such as Netflix.

Short Bio

Jennifer Chayes is Technical Fellow and Managing Director of Microsoft Research New England, New York City, and Montreal. She was previously a Professor of Mathematics at the University of California, Los Angeles. She is the author of over 140 academic papers and the inventor of over 30 patents. Her research areas include: phase transitions in computer science, structural and dynamical properties of networks, graph theory, graph algorithms, and computational biology. Chayes is one of the inventors of the field of graphons, which are widely used for the machine learning of large-scale networks. Her recent work focuses on machine learning, broadly defined, including applications in cancer immunotherapy, ethical decision making, and, most recently, climate change. Chayes is a Fellow of the American Association for the Advancement of Science, the Fields Institute, the Association for Computing Machinery, the American Mathematical Society, and the American Academy of Arts and Sciences. Chayes has received numerous leadership awards including the Anita Borg Institute Women of Vision of Award and the Mass Technology Leadership Council Distinguished Leader Award. She is the winner of the 2015 John von Neumann Lecture Award, the highest honor of the Society for Industrial and Applied Mathematics. Chayes received an Honorary Doctorate from Leiden University in 2016.

Graph Neural Networks and Applications

Abstract

Graph Neural networks (GNNs) and their variants have generalized deep learning methods into non-Euclidean graph data,bringing a substantial improvement on many graph mining tasks. In this talk, I will revisit graph convolutional networks and investigate how to improve their representation capacity. We discover that the performance of GNNs can be significantly improved with several simple and elegant refinements on the neighborhood aggregation and network sampling steps. Importantly, we show that some of the most expressive GNNs, e.g., the graph attention network, can be reformulated as a particular instance of our models. Extensive experiments on different types of graph benchmarks show that our proposed framework can significantly and consistently improve the graph classification accuracy when compared to state-of-the-art baselines.

Short Bio

Jie Tang is a Full Professor and the Vice Chair of the Department of Computer Science and Technology at Tsinghua University. His interests include data mining, social networks, knowledge graph, machine learning, and artificial intelligence. He has been visiting scholar at Cornell University, Hong Kong University of Science and Technology, and Southampton University. He has published more than 300 journal/conference papers and holds 20 patents. His papers have been cited by more than 12,000 times. He served as PC Co-Chair of CIKM’16, WSDM’15, Associate General Chair of KDD’18, and Acting Editor-in-Chief of ACM TKDD, Editors of IEEE TKDE/TBD and ACM TIST. He leads the project AMiner.org for academic social network analysis and mining, which has attracted more than 10 million independent IP accesses from 220 countries/regions in the world. He was honored with the UK Royal Society-Newton Advanced Fellowship Award, CCF Young Scientist Award, NSFC for Distinguished Young Scholar, and KDD’18 Service Award.

Friendship paradox and information bias in networks

Abstract

Individual's decisions, from what product to buy to who to vote for, often depend on what others are doing. People, however, rarely have global information about others, but must estimate it from the local observations they make of their friends. I discuss the counter-intuitive phenomena by which the structure of social networks significantly distorts the observations people make of their friends. The effects include the “friendship paradox,” which states that your friends have more friends than you do, on average, and its many more surprising generalizations. As a result of these paradoxes, a trait that is globally rare may be dramatically over-represented in the local neighborhoods of many people. Friendship paradoxes may lead individuals to systematically overestimate the prevalence of a minority opinion or behavior, and may accelerate the spread of social contagions and adoption of social norms.

Short Bio

Kristina Lerman is a Principal Scientist at the University of Southern California Information Sciences Institute and holds a joint appointment as a Research Associate Professor in the USC Computer Science Department. Trained as a physicist, she now applies network analysis and machine learning to problems in computational social science, including crowdsourcing, social network and social media analysis. Her recent work on modeling and understanding cognitive biases in social networks has been covered by the Washington Post, Wall Street Journal, and MIT Tech Review.