Graph Neural Networks

What is a Graph?

• A data structure consisting of vertices (nodes, vertices) and edges (edges, links)

• Edges can be directed or undirected

• May contain loops (edges connecting the same vertex to itself)

• Vertices and edges may have attributes (properties)

  • There are many examples where vertices have attributes (also referred to as Feature Vectors)

• Edges may have weights

  

• y is the attribute of a node

• [2,1]^t etc. is expressed as x, the property

Examples

• Internet, Web
• Transportation networks, purchase data
• Video and music viewing history
• Paper co-authorship relationships
• Proteins
• Molecular structures
• 3D object polygon representations
• etc...

Real-World Examples Representable as Graphs

Representations for Computers to Understand Graphs

• Adjacency matrix

  

• Sparse Matrix

Application of Graphs to Deep Learning

• The rise of deep learning

  • In the image domain

    • In research: from around 2012~

    • In business: from around 2016~

      

  • Practical business deployment begins a few years after cutting-edge research

History of Graph Convolution

• The Graph Neural Network Model (2009)
• Spectral Networks and Locally Connected Networks on Graphs (2013)
  • The first attempt to apply CNNs to graphs
  • Computational processing using Graph Fourier, with constraints such as not handling loops or multi-edges
• Graph Convolutional Networks (GCN)

  • Semi-Supervised Classification with Graph Convolutional Networks (ICRL2017)

    

  • Removed Graph Fourier constraints and introduced simple yet high-performance GCN for graphs

Distributed Representation of Graphs / Graph Embedding

• Vectorization of graphs

  

• A technique analogous to learning distributed representations in natural language processing

Graph NN Appications

• Tasks
  • Node classification
  • Graph classification
  • Linkage prediction
  • Similarity estimation
  • Reference: Graph Embedding Techniques, Applications, and Performance: A Survey
    • https://arxiv.org/abs/1705.02801

Electrical Circuit Applications

• There have been many examples of applying graph theory to electrical circuit design

  • Electrical Networks and Algebraic Graph Theory: Models, Properties, and Applications
    • https://ece.uwaterloo.ca/~jwsimpso/papers/2017k.pdf
  • However, applications of deep learning were nonexistent

• Starting in 2019, examples of applying graph neural networks to electrical circuits have emerged

Application of GCN to Electrical Circuit Design

Circuit-GNN (ICML 2019)

• Learned circuit parameters by reverse-engineering from EM specifications, achieving a 4-order-of-magnitude reduction in time compared to humans
• Designed a terahertz channelizer requiring expert knowledge
  • http://proceedings.mlr.press/v97/zhang19e/zhang19e.pdf

Fault Location in Power Distribution Systems via Deep Graph Convolutional Networks

• Estimating fault locations using GCN

• https://arxiv.org/pdf/1812.09464.pdf

Attempt to Represent Netlists (Electronic Circuit Connectivity) Using Graph Networks

• NHigh Performance Graph Convolutional Networks with Applications in Testability Analysis
  • GCN-based difficult-to-observation nodes prediction. (NVidia)
  • https://research.nvidia.com/sites/default/files/pubs/2019-06_High-Performance-Graph/14_2_Ma_GCN_Testability.pdf

Current Status and Challenges of Deep Learning in the EDA Field

• With the emergence of GCN spreading deep learning to various fields, use cases in the EDA field remain few
  • Given the industry workforce, it is unlikely that no one is working on it
  • Assumed challenges:
    • Dataset sharing is not progressing (conversely, the barrier to entry is high)
    • Circuits are inherently complex, making the difficulty level high
• The latest EDA-related literature has small problem settings
  • The impression is that this is still in the early exploration stage

End