17.01.2020

Venue: Seminar room, Arithmeum, Lennéstr. 2

Research Area: C3: Combinatorial optimization, complexity, and chip design

Program:

Abstracts:

Petra Mutzel: The k-dimensional Weisfeiler-Leman Algorithm and its Role in Data Analysis
The Weisfeiler-Leman vertex classification algorithm colors the vertices of a graph. It is often used as a heuristic for the graph isomorphism problem. If two graphs receive different color classes, one can be sure that the two graphs are not isomorphic. A stronger version is its generalization, the k-dimensional Weisfeiler-Leman algorithm, which is an important ingredient for Babai's quasi-polynomial time algorithm for solving the graph isomorphism problem. There are also close connections to the level-k Sherali Adams relaxation of the natural integer linear program for the graph isomorphism problem.

In the analysis of structured data that can be modelled as graphs or networks, graph kernels and graph neural networks related to the Weisfeiler-Leman approach have been suggested. In this talk we will discuss various versions of the k-dimensional Weisfeiler-Leman approach, including a new local version, and point out their strengths and weaknesses for data analysis. We will also report on practical experiments for learning tasks in drug design, social network analysis, and molecular data analysis.

Pietro Saccardi: Continuous global routing
Global routing is a key stage of the chip design workflow, in which millions of Steiner trees must be computed and packed efficiently on the chip, under capacity constraints. Traditionally, global routing operates on a 3D grid graph, arising from coarsening the chip area into rectilinear tiles. However, terminals are implicitly mapped to tile centers, any tile-internal wiring is largely ignored, hindering accurate congestion estimates, and the structure of the nets is altered. To overcome these deficiencies, we propose a new model that always considers exact pin and wire positions. We work with rhomboidal tiles and pack Steiner trees rather into the tiles than into a grid graph. We present new algorithms to design a global router working on rhomboids, starting with computing shortest paths w.r.t. tile prices. We then solve the Steiner tree packing problem using the min-max resource sharing algorithm to approximately minimize the total wire length subject to wire density constraints.