University of Waterloo COVID-19 update

The University of Waterloo is constantly updating its most frequently asked questions.

Questions about buildings and services? Please visit the list of modified services.

Please note: The University of Waterloo is closed for all events until further notice.

CANCELLED • Seminar • Artificial Intelligence — Graph Guided PredictionsExport this event to calendar

Thursday, April 2, 2020 — 10:30 AM EDT

Please note: This seminar has been cancelled

Vikas Garg, Electrical Engineering & Computer Science
Massachusetts Institute of Technology

In this talk I will describe our recent work on effectively using graph structured data. Specifically, I will discuss how to compress graphs to facilitate predictions, understand the capacity of algorithms operating on graphs, and how to infer interaction graphs so as to predict deliberative outcomes.

Our approach to graph compression builds on the idea of optimal transport specifying the cost of mapping a large graph to a smaller one. The cost decomposes as a flow on the edges, and the selection of the subgraph to retain can be optimized via convex relaxations.

Graph neural networks (GNNs) are naturally suited for making predictions based on graphs but they remain poorly understood in terms of what they can and cannot do. We introduce constructions that reveal how GNNs fail to distinguish many graph properties such as cycles, diameter so long as the graphs have similar local structure. We also extend RNN generalization analysis to GNNs via computation trees.

In many cases the graph structure is not given but must be inferred. This is the case, for example, in trying to understand how a set of players arrive at their decisions. We study the role of structure — interaction graph — in the context of predicting outcomes of such deliberative games. We characterize conditions under which players converge to an equilibrium, and when the unknown interaction graph can be identified from a data set of context-dependent outcomes.


Bio: Vikas Garg is a PhD student in Computer Science at MIT, where his research is supervised by Prof. Tommi Jaakkola. His research interests in machine learning include generative models, graphical models, multiagent systems, theory of deep learning, and learning under uncertainty or resource constraints along with their intersections with optimization and game theory.

Location 
cancelled
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2020 (76)
    1. May (3)
    2. April (9)
    3. March (17)
    4. February (25)
    5. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)