# Net${}^{\text{2}}$: A Graph Attention Network Method
Customized for Pre-Placement Net Length Estimation

Zhiyao Xie†, Rongjian Liang§, Xiaoqing Xu‡, Jiang Hu§, Yixiao Duan†, Yiran
Chen† † Duke University, Durham, NC, USA‡ ARM Inc., Austin, TX, USA§ Texas A&M
University, College Station, TX<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2021)

###### Abstract.

Net length is a key proxy metric for optimizing timing and power across
various stages of a standard digital design flow. However, the bulk of net
length information is not available until cell placement, and hence it is a
significant challenge to explicitly consider net length optimization in design
stages prior to placement, such as logic synthesis. This work addresses this
challenge by proposing a graph attention network method with customization,
called Net${}^{\text{{2}}}$, to estimate individual net length before cell
placement. Its accuracy-oriented version Net${}^{\text{{2a}}}$ achieves about
15% better accuracy than several previous works in identifying both long nets
and long critical paths. Its fast version Net${}^{\text{{2f}}}$ is more than
1000$\times$ faster than placement while still outperforms previous works and
other neural network techniques in terms of various accuracy metrics.

††journalyear: 2021††copyright: acmcopyright††conference: 26th Asia and South
Pacific Design Automation Conference; January 18–21, 2021; Tokyo,
Japan††booktitle: 26th Asia and South Pacific Design Automation Conference
(ASPDAC ’21), January 18–21, 2021, Tokyo, Japan††price: 15.00††doi:
10.1145/3394885.3431562††isbn: 978-1-4503-7999-1/21/01

##  1\. Introduction

For state-of-the-art semiconductor manufacturing technology nodes,
interconnect is a dominating factor for integrated circuit (IC) performance
and power, e.g., it can contribute to over 1/3 of clock period (Hyun et al.,
2019) and about 1/2 of total chip dynamic power (Magen et al., 2004).
Interconnect characteristics are affected by almost every step in a design
flow, but not explicitly quantified and optimized until the layout stage.
Therefore, previous academic studies attempted to address the interconnect
effect in design steps prior to layout, e.g., layout-aware synthesis (Pedram
and Bhat, 1991a, b). Moreover, a recent industrial trend among commercial
implementation tools (Synopsys, 2020; Cadence, 2020) takes an ambitious goal
to explicitly address the interaction between logic synthesis and layout. To
achieve such a goal, an essential element is to enable fast yet accurate pre-
layout net length prediction, which has received significant research
attention in the past(Bodapati and Najm, 2001; Fathi et al., 2009; Liu et al.,
2012; Hu and Marek-Sadowska, 2003; Kahng and Reda, 2005; Liu and Marek-
Sadowska, 2004; Hyun et al., 2019). Some works (Bodapati and Najm, 2001; Fathi
et al., 2009) pre-define numerous features describing each net, then a
polynomial model is built by fitting these features. The work of (Liu et al.,
2012) estimates wirelength by artificial neural networks (ANN), but it is
limited to the total wirelength on an FPGA only, which is easier to estimate
than individual net length. The mutual contraction (MC) (Hu and Marek-
Sadowska, 2003) estimates net length by checking the number of cells in every
neighboring net. The intrinsic shortest path length (ISPL) (Kahng and Reda,
2005) is an interesting heuristic, which finds the shortest path between cells
in the net to be estimated, apart from the net itself. The idea in (Liu and
Marek-Sadowska, 2004) is similar to (Kahng and Reda, 2005) in measuring the
graph distance between cells in the netlist. The recent work (Hyun et al.,
2019) on wirelength prediction can only estimate the wirelength of an entire
path instead of individual nets, and it relies on the results from virtual
placement and routing.

Although net length prediction has been extensively studied previously, we
notice a major limitation in most works. That is, they only focus on the local
topology around each individual net with an over-simplified model. In other
words, when estimating each net, usually their features only include
information from nets one or two-hop away. The big picture, which is the net’s
position in the whole netlist, is largely absent. However, a placer normally
optimizes a cost function defined on the whole netlist. It is not likely to
achieve high accuracy without accessing any global information. Some previous
models indeed attempt to embrace global information like the number of 2-pin
nets in an entire circuit (Bodapati and Najm, 2001; Fathi et al., 2009), or a
few shortest paths (Kahng and Reda, 2005), but such information is either too
sketchy (Bodapati and Najm, 2001; Fathi et al., 2009) or still limited to a
region of several hops (Kahng and Reda, 2005). Since the global or long-range
impact on individual nets is much more complex than local circuit topologies,
it can hardly be captured by simple models or models with only human-defined
parameters that cannot learn from data. To solve this, we propose a new
approach, called Net${}^{\text{{2}}}$, based on graph attention network
(Veličković et al., 2017). Its basic version, Net${}^{\text{{2f}}}$, intends
to be fast yet effective. The other version, which emphasizes more on accuracy
and is denoted as Net${}^{\text{{2a}}}$, captures rich global information with
a highly flexible model through circuit partitioning.

Recently, deep learning has generated a huge impact on many applications where
data is represented in Euclidean space. However, there is a wide range of
applications where data is in the form of graphs. Machine learning on graphs
is much more challenging as there is no fixed neighborhood structure like in
images. All neural network-based methods on graphs are referred to as graph
neural networks (GNN). The most widely-used GNN methods include graph
convolution network (GCN) (Kipf and Welling, 2016), graphSage (GSage)
(Hamilton et al., 2017), and graph attention network (GAT) (Veličković et al.,
2017). They all convolve each node’s representation with its neighbors’
representations, to derive an updated representation for the central node.
Such operation essentially propagates node information along edges and thereby
topology pattern is learned.

Similarly, in Electronic Design Automation (EDA), circuit designs are embedded
in Euclidean space after placement, which inspired many convolutional neural
network (CNN)-based methods (Xie et al., 2018; Fang et al., 2018; Xie et al.,
2020). But before placement, a circuit structure is described as a graph and
spatial information is not yet available. Till recent years, GNN is explored
for EDA applications (Ma et al., 2019; Zhang et al., 2019). The work in (Ma et
al., 2019) predicts observation point candidates with a model similar to GSage
(Hamilton et al., 2017). Graph-CNN (Zhang et al., 2019) predicts the
electromagnetic properties of post-placement circuits. This method is limited
to very small-scale circuit graphs with less than ten nodes. Overall, GNN has
great potential but is much less studied than CNN in EDA.

In this work, our contributions include:

  * •

As far as we know, this is the first work making use of GNN for pre-placement
net length estimation. GNNs (GCN, GSage, GAT) outperform both conventional
heuristics and common machine learning methods in almost all measured metrics.

  * •

We propose to extract global topology information through partitioning. Based
on partition results, we define innovative directional edge features between
nets, which substantially contribute to Net${}^{\text{{2}}}$’s superior
accuracy.

  * •

We propose a GAT-based model named Net${}^{\text{{2}}}$, which is customized
for this net length problem. It includes a fast version Net${}^{\text{{2f}}}$,
which is 1000$\times$ faster than placement, and an accuracy-centric version
Net${}^{\text{{2a}}}$, which effectively extracts global topology information
from unseen netlists and significantly outperforms plug-in use of existing GNN
techniques.

  * •

To focus on nets, we propose a graph construction method that treats nets as
nodes. In designing Net${}^{\text{{2}}}$ architecture, we define different
convolution layers for graph nodes and edges to incorporate both edge and node
features.

  * •

Besides net length, we further apply the proposed methods to estimate path
length. Net${}^{\text{{2}}}$ also proves to be superior in identifying long
paths.

##  2\. Problem Formulation

Figure 1. (a) Part of a netlist. (b) The corresponding graph.

We define terminologies with Figure 1. Figure 1(a) shows part of a netlist,
including five nets {$n_{1}$, $n_{2}$, $n_{3}$, $n_{4}$, $n_{5}$} and 11 cells
{$c_{A}$, $c_{B}$, …, $c_{K}$}. Now we focus on net $n_{3}$, which touches 3
cells {$c_{D}$, $c_{G}$, $c_{H}$} and is referred to as a _3-pin net_. Its
_driver_ is cell $c_{D}$; its _sinks_ are cells {$c_{G}$, $c_{H}$}. We denote
the area of $n_{3}$’s driver cell as $a_{dri}^{3}$. Net $n_{3}$’s _fan-ins_
$N^{3}_{in}=$ {$n_{1}$, $n_{2}$} ; its _fan-outs_ $N^{3}_{out}=$ {$n_{4}$,
$n_{5}$}. Its _fan-in size_ is 2, denoted as $|N^{3}_{in}|=2$. Its _fan-out
size_ (number of sinks) is 2, denoted as $|N^{3}_{out}|=2$. Every net can have
only one driver but multiple sinks. Thus, the number of cells
$=1+|N^{3}_{out}|=3$ for this net. Net $n_{3}$’s one-hop neighbors include
both its fan-in and fan-out: $\mathcal{N}(n_{3})=N_{in}^{3}\cup N_{out}^{3}=$
{$n_{1}$, $n_{2}$, $n_{4}$, $n_{5}$}. The number of its neighbors is also
known as the degree of $n_{3}$: $deg(n_{3})=|\mathcal{N}(n_{3})|=4$.

Table 1. Commonly Used Notations

Notation | Description | Notaion | Description
---|---|---|---
$n_{k}$ | net or node | $O_{k}$ | node features
{$c_{G}$, $c_{H}$} | cells | $E_{b\rightarrow k}$ | edge features
$a^{k}_{dri}$ | driver’s area | $P[c_{H}]$ | cell partition IDs
$N^{k}_{in}$, $N^{k}_{out}$ | fan-in/fan-out nets | $M[n_{k}]$ | node partition IDs
$\mathcal{N}(n_{k})$ | 1-hop neighbors |  $h^{(t-1)}_{k}$, $h^{(t)}_{k}$ | GNN embeddings
$|N^{k}_{in}|$, $|N^{k}_{out}|$ | fan-in/fan-out size |  $W^{(t)}$, $\theta^{(t)}$ | learnable weights
$deg(n_{k})$ | degree of net | $g(\,),\sigma(\,)$ | activation functions
$L^{k}$ | net length label |  $s(\,)$, $\mu(\,)$ | std deviation, mean
$n_{b}\rightarrow n_{k}$ | directional edge | $[\,\,\,||\,\,\,]$ | concat to one list
$c_{kb}$ or $c_{bk}$ | cell on $n_{b}\rightarrow n_{k}$ | $\backslash$ | exclude from list

The net length is the label for training and prediction. Each net’s length is
the half perimeter wirelength (HPWL) of the bounding box of the net after
placement. The length of net $n_{k}$ is $L^{k}$.

To apply graph-based methods, we convert each netlist to one directed graph.
Different from most GNN-based EDA tasks, net length prediction focuses on nets
rather than cells. Thus we represent each net as a node, and use the terms
_node_ and _net_ interchangeably. For each net $n_{k}$, it is connected with
its fan-ins and fan-outs through their common cells by edges in both
directions. The common cell shared by both nets on that edge is called its
_edge cell_. For example, in Figure 1(b), net $n_{3}$ is connected with nets
$n_{4}$ and $n_{5}$ through its sinks $c_{G}$ and $c_{H}$; it is connected
with nets $n_{1}$ and $n_{2}$ through its driver $c_{D}$. The edges through
edge cell $c_{G}$ is denoted as $n_{3}\rightarrow n_{5}$ and $n_{5}\rightarrow
n_{3}$. The edge cell $c_{G}$ can also be referred to as $c_{35}$ or $c_{53}$.
We differentiate edges in different directions because we will assign
different edge features to $n_{3}\rightarrow n_{5}$ and $n_{5}\rightarrow
n_{3}$.

An important concept throughout this paper is global and local topology
information. We use the number of hops to denote the shortest graph distance
between two nodes on a graph. The _information_ of each net refers to its
number of cells and driver’s area. Local information includes the information
about the estimated net itself, or from its one to two-hop neighboring nets.
In contrast, global information means the pattern behind the topology of the
whole netlist or the information from nets far away from the estimated net
$n_{k}$. The range of neighbors that can be accessed by each model is referred
to as the model’s _receptive field_.

##  3\. Challenges

Figure 2. (a) A typical local topology. (b) Predictions on nets with similar
local topology information.

We provide an example to show the challenge in net length prediction and the
importance of global information. Figure 2(a) shows a net $n_{6}$ with a
commonly seen local topology information: $|N^{6}_{in}|=1$, $|N^{6}_{out}|=2$,
$deg(n_{6})=3$. For its neighbors, it has one 2-pin fan-in, one 2-pin fan-out
and one 3-pin fan-out.

In a netlist of design B20 in ITC 99 (Corno et al., 2000), we find 725 nets
with exactly the same driver cell’s area, number of cells and one-hop neighbor
information as $n_{6}$, but their net lengths after placement range from 1
$\mathrm{\SIUnitSymbolMicro m}$ to more than 100 $\mathrm{\SIUnitSymbolMicro
m}$. Distinguishing these similar nets is highly challenging without rich
global information. To prove this, Figure 2(b) shows the prediction from
different methods on these 725 similar nets. These nets are firstly divided
into four different types according to their actual net length, each type with
$432,190,67,36$ nets, respectively. We then plot the scaled averaged
estimation by different methods for each type of net. MC (Hu and Marek-
Sadowska, 2003), which only looks at one-hop neighbors, cannot distinguish
these nets at all. ISPL (Kahng and Reda, 2005), which captures some global
information by searching shortest path, gives a slightly lower estimation on
the shortest type (netLen ¡ 5 $\mathrm{\SIUnitSymbolMicro m}$). By looking at
two-hop neighbors, a polynomial model with pre-defined features (Poly)
(Bodapati and Najm, 2001) (Fathi et al., 2009) captures the trend with a tiny
difference between different types. For Net${}^{\text{{2}}}$, we only train
its edge convolution layer on other designs and present its output. Its
estimations on different net types differ significantly. This example shows
the importance of global information in distinguishing a large number of nets
with similar local information.

##  4\. Algorithm

###  4.1. Node Features on Graph

Algorithm 1 Graph Generation with Node Features

Input: Basic features {$|N_{in}^{k}|$, $|N_{out}^{k}|$, $a_{dri}^{k}$}, net
length label $L^{k}$, the fan-in nets $N_{in}^{k}$ and fan-out nets
$N_{out}^{k}$ of each net $n_{k}$.

Generate Node Features:

1:for each net $n_{k}$ do

2: $a_{all}=[a_{dri}^{k}]$, $in_{in}=[]$, $in_{out}=[]$, $out_{in}=[]$,
$out_{out}=[]$

3: for each net $n_{i}\in N_{in}^{k}$, each net $n_{o}\in N_{out}^{k}$ do

4: $in_{in}$.add ($|N_{in}^{i}|$) ;$in_{out}$.add ($|N_{out}^{i}|$) 5:
$out_{in}$.add ($|N_{in}^{o}|$) ;$out_{out}$.add ($|N_{out}^{o}|$) 6:
$a_{all}$.add($a_{dri}^{o}$)  7: $O_{k}$ = {$|N_{in}^{k}$—, $|N_{out}^{k}|$,
$a_{dri}^{k}$, $\sum{a_{all}}$, $\sum{out_{in}}$, $\sum{out_{out}}$,
$\sum in_{in},\sum in_{out}$, $s(out_{in})$, $s(out_{out})$, $s(in_{in})$,
$s(in_{out})$}

Build Graph:

1:Initiate a graph $G$. Each net is a node.

2:for each net $n_{k}$ do

3: For node $n_{k}$ in $G$, set $O_{k}$ as node feature, $L^{k}$ as label.

4: for each net $n_{b}\in N_{in}^{k}\cup N_{out}^{k}$ do

5: Add directed edge $n_{b}$ →$n_{k}$.

Output: Graph $G$ with node features $O$ and label $L$.

Algorithm 1 shows how we build a directed graph and generate features for each
node with a given netlist. On average, a net with more large cells tends to be
longer. Thus, the most basic net features include the net’s driver’s area,
fan-in and fan-out size {$|N^{k}_{in}|$, $|N^{k}_{out}|$, $a_{dri}^{k}$}.
Feature $\sum a_{all}$ is the sum of areas over all cells in $n_{k}$. It is
calculated by including the drivers of all $n_{k}$’s fan-outs in line 6, which
are the sinks of $n_{k}$. Besides these basic features, we capture the more
complex impact from neighbors. As shown in lines 3, we go through all
neighbors of $n_{k}$ to collect their fan-in and fan-out sizes. The summation
$\sum$ and standard deviation $s()$ of these neighboring information are added
to node features $O_{k}$ in line 7.

###  4.2. Edge Features

Algorithm 2 Define Edge Features on Graph

Input: Cell cluster ID $P[c_{k}]$ for each cell $c_{k}$, net cluster ID
$M[n_{k}]$ and the neighbors $\mathcal{N}(n_{k})$ of each net $n_{k}$.
Directed graph $G$.

1:function measureDiff($c_{bk}$, $n_{b}$, $c_{ok}$, $n_{o}$)

2: $f_{0}=1-(P[c_{bk}]==P[c_{ok}])$

3: $P_{b}=[P[c]$ for $c\in n_{b}]$ // cluster IDs for $n_{b}$’s cells

4: $P_{o}=[P[c]$ for $c\in n_{o}]$ // cluster IDs for $n_{o}$’s cells

5: $P_{b\\_not\\_o}=P_{b}\backslash P_{o}$ // IDs in $P_{b}$ but not in
$P_{o}$

6: $P_{o\\_not\\_b}=P_{o}\backslash P_{b}$ // IDs in $P_{o}$ but not in
$P_{b}$

7: $f_{1}=\frac{|P_{b\\_not\\_o}|}{|P_{b}|}+\frac{|P_{o\\_not\\_b}|}{|P_{o}|}$
// percent of different IDs

8: $f_{2}=1-(M[n_{b}]==M[n_{o}])$

9: return [$f_{0}$, $f_{1}$, $f_{2}$]

10:end function

11:

12:for each net $n_{k}$ do

13: for each net $n_{b}\in\mathcal{N}(n_{k})$ do

14: $F_{0}$ = [], $F_{1}$ = [], $F_{2}$ = []

15: Cell $c_{bk}$ is the edge cell on $n_{b}$ →$n_{k}$

16: Other neighbors $N_{other}^{k}=\mathcal{N}(n_{k})\backslash\\{n_{b}\\}$

17: for each net $n_{o}\in N_{other}^{k}$ do

18: Cell $c_{ok}$ is the edge cell on $n_{o}$ →$n_{k}$

19: $f_{0}$, $f_{1}$, $f_{2}$ = measureDiff ($c_{bk}$, $n_{b}$, $c_{ok}$,
$n_{o}$)

20: $F_{0}$.add($f_{0}$) ; $F_{1}$.add($f_{1}$) ; $F_{2}$.add($f_{2}$)

21: $f_{3}=1-(M[n_{b}]==M[n_{k}])$

22: $E_{b\rightarrow k}$ = {$\sum F_{0}$, $\mu(F_{0})$, $\sum F_{1}$,
$\mu(F_{1})$, $\sum F_{2}$, $\mu(F_{2})$, $f_{3}$}

23: Set $E_{b\rightarrow k}$ as the feature of edge $n_{b}\rightarrow n_{k}$
in $G$.

Output: Graph $G$ with edge features $E$.

In Algorithm 1, node features $O_{k}$ include up to two-hop neighboring
information. The receptive field of the GNN method itself depends on the model
depth, which is usually two to three layers. Thus the model can reach as far
as four to five-hop neighbors, which is already more than previous works. This
work goes beyond that to capture more global information from the whole graph.

To capture global information, we use an efficient multi-level partitioning
method hMETIS (Karypis et al., 1999) to divide one netlist into multiple
clusters / partitions. The partition method minimizes the overall cut between
all clusters, which provides a global perspective. We denote the partition
result as $M$. Each net $n_{k}$ is assigned a cluster ID $M[n_{k}]$, which
denotes the cluster it belongs to. To generate more information, on the same
netlist, we also build a hyper-graph $HG_{c}$ by using cells as nodes. In
$HG_{c}$, each hyper-edge corresponds to a net. Similarly, the partition
result on $HG_{c}$ is denoted as $P$. Each cell $c_{k}$ is assigned a cluster
ID $P[c_{k}]$. Notice that $HG_{c}$ is only used to generate cluster ID for
each cell.

Cluster IDs are not directly useful by themselves. What matters in this
context is the difference in cluster IDs between cells and nets. Algorithm 2
shows how the cluster information is incorporated into GNN models through
novel edge features $F_{0},F_{1},F_{2},f_{3}$. The most important intuition
behind this is: for a high-quality placement solution, on average, the cells
assigned to different clusters tend to be placed far away from each other.

In Algorithm 2, we design the edge features to quantify the source node’s
contribution to the target node’s length. The contribution here means the
source net is “pulling” the edge cell far away from other cells in the target
net. The edge features measure such “pulling” strength. When the edge cell is
“pulled” away, the target net results in a longer length. In Algorithm 2, for
edge $n_{b}$ →$n_{k}$, function measureDiff measures the difference in
assigned clusters between node $n_{b}$ and every other neighboring node
$n_{o}$, which indicates the distance between $c_{bk}$ and $c_{ok}$. If the
distance between edge cell $c_{bk}$ and every other cell $c_{ok}$ in $n_{k}$
is large, it means $c_{bk}$ is placed far away from other cells in net
$n_{k}$. In this case, edges features $F_{0},F_{1},F_{2},f_{3}$ are large.
That is why edge features imply how strong the edge cell is “pulled” away from
the target node.

Figure 3 shows an example of Algorithm 2 using the netlist same as Figure 1.
The number on each cell or net is the cluster ID assigned to it after
partition. Figure 3 measures the edge features of edge $n_{5}$ →$n_{3}$,
representing how strongly edge cell $c_{G}$ is pulled by $n_{5}$ from both
cells {$c_{D}$, $c_{H}$} in $n_{3}$. To calculate this, we measure the
distance between $c_{G}$ and $c_{H}$ by measureDiff($c_{G}$, $n_{5}$, $c_{H}$,
$n_{4}$) in Algorithm 2; and the distance between $c_{G}$ and $c_{D}$ by
measureDiff($c_{G}$, $n_{5}$, $c_{D}$, $n_{1}$) and measureDiff($c_{G}$,
$n_{5}$, $c_{D}$, $n_{2}$).

Take measureDiff($c_{G}$, $n_{5}$, $c_{H}$, $n_{4}$) as an example to show how
it measures distance between $c_{G}$ and $c_{H}$. As shown in line 2, feature
$f_{0}$ measures the difference in $c_{G}$ and $c_{H}$’ cluster IDs,
$f_{0}=1-(P[c_{G}]==P[c_{H}])=1-(3==3)=0$. Feature $f_{1}$ measures the
difference in all cells between $n_{5}$ and $n_{4}$. As shown from line 3 to
7, $P_{5}=[3,6,3]$ and $P_{4}=[3,3]$. Then $P_{5\\_not\\_4}=[6]$ and
$P_{4\\_not\\_5}=[]$. They are normalized by the number of cells $|P_{5}|=3$
and $|P_{4}|=2$, in order to avoid bias toward nets with many cells. Thus,
$f_{1}=\frac{1}{3}+\frac{0}{2}=\frac{1}{3}$. Feature $f_{2}$ measures the
difference between $n_{5}$ and $n_{4}$,
$f_{2}=1-(M[n_{5}]==M[n_{4}])=1-(1==1)=0$. As this example shows, we only
measure whether cells / nets have the same cluster IDs, and the order of IDs
does not matter.

Figure 3. Define edge features by partition results.

After measuring the difference in cluster ID between $c_{G}$ and all other
cells in $n_{3}$, for the edge $n_{5}$ →$n_{3}$, $F_{0}=[1,1,0]$;
$F_{1}=[2,1,\frac{1}{3}]$; $F_{2}=[1,0,0]$. $f_{3}$ measures the difference
between $n_{5}$ and $n_{3}$, $f_{3}=1$. This example shows how we incorporate
global information from partition into edge features. Actually, we generate
multiple different partitioning results $M$, $P$ by requesting different
number of clusters. That results in multiple different {$F_{0}$, $F_{1}$,
$F_{2}$, $f_{3}$}. All these different edge features are processed in line 22
and concatenated together as the final edge features $E_{b\rightarrow k}$.

###  4.3. Common GNN Models

This section introduces how GNN models are applied on the graph G we build.
GNN models are comprised of multiple sequential convolution layers. Each layer
generates a new embedding for every node based on the previous embeddings. For
node $n_{k}$ with node features $O_{k}$, denote its embedding at the
$t^{\text{th}}$ layer as $h_{k}^{(t)}$. Its initial embedding is the node
features $h_{k}^{(0)}=O_{k}$. Sometimes the operation includes both neighbours
and the node itself, we use $n_{\beta}$ to denote it:
$n_{\beta}\in\mathcal{N}(n_{k})\cup\\{n_{k}\\}$. In each layer $t$, GNNs
calculate the updated embedding $h_{k}^{(t)}$ based on the previous embedding
of the node itself $h_{k}^{(t-1)}$ and its neighbors
$h_{b}^{(t-1)}|n_{b}\in\mathcal{N}(n_{k})$.

We show one layer of GCN, GSage, and GAT below. Notice that there exists other
expressions. The two-dimensional learnable weight at layer $t$ is $W^{(t)}$.
In GAT, there is an extra one-dimensional weight $\theta^{(t)}$. The operation
$[\>||\>]$ concatenates two vectors into one longer vector. Functions $\sigma$
and $g$ are sigmoid and Leaky ReLu activation function, respectively.

On GCN (with self-loops), $\mathcal{F}_{GCN}^{(t)}$ (Kipf and Welling, 2016)
is:

$\displaystyle
h_{k}^{(t)}=\sigma(\sum_{n_{\beta}\in{\mathcal{N}(n_{k})\cup\\{n_{k}\\}}}a_{k\beta}W^{(t)}h_{\beta}^{(t-1)})$
$\displaystyle\text{where
}a_{k\beta}=\frac{1}{\sqrt{deg(k)+1}\sqrt{deg(\beta)+1}}\in\mathbb{R}$

On GSage, $\mathcal{F}_{GSage}^{(t)}$ (Hamilton et al., 2017) is:

$\displaystyle
h_{k}^{(t)}=\sigma(W^{(t)}[h_{k}^{(t-1)}||\frac{1}{deg(k)}\sum_{n_{b}\in{\mathcal{N}(n_{k})}}h_{b}^{(t-1)}])$

On GAT, $\mathcal{F}_{GAT}^{(t)}$ (Veličković et al., 2017) is:

$\displaystyle
h_{k}^{(t)}=\sigma(\sum_{n_{\beta}\in{\mathcal{N}(n_{k})\cup\\{n_{k}\\}}}a_{k\beta}W^{(t)}h_{\beta}^{(t-1)})\qquad\qquad$
$\displaystyle\text{where }a_{k\beta}$
$\displaystyle=softmax_{\beta}(r_{k\beta})\text{ \,\; over $n_{k}$ and its
neighbors,}$ $\displaystyle r_{k\beta}$
$\displaystyle=g(\theta^{(t)\intercal}[W^{(t)}h_{\beta}^{(t-1)}||W^{(t)}h_{k}^{(t-1)}])\in\mathbb{R}$

Here we briefly discuss the difference between these methods. GCN scales the
contribution of neighbors by a pre-determined coefficient $a_{k\beta}$,
depending on the node degree. In contrast, GAT uses learnable weights $W$,
$\theta$ to firstly decide node $n_{\beta}$’s contribution $r_{k\beta}$, then
normalize the coefficient $r_{k\beta}$ across $n_{k}$ and its neighbors
through a softmax operation. Such a learnable $a_{k\beta}$ leads to a more
flexible model. GSage does not scale neighbors by any factor. For all these
GNN methods, the last layer ’s output embedding $h_{k}^{(t)}$ is connected to
a multi-layer ANN.

###  4.4. Net${}^{\text{{2}}}$ Model

The node convolution layer of the Net${}^{\text{{2}}}$ is based on GAT,
considering its higher flexibility in deciding neighbors’ contribution
$a_{k\beta}$. Thus node convolution layer is $\mathcal{F}_{GAT}^{(t)}$. In the
final embedding, we concatenate the outputs from all layers, instead of only
using the output of the final layer like most GNN works. This is a
customization, by which the embedding includes contents from different depths.
The shallower one includes more local information, while the deeper one
contains more global information. Such an embedding provides more information
for the ANN model at the end and may lead to better convergence. The idea of
combining shallow and deep layers has inspired many classical deep learning
methods in Euclidian space (He et al., 2016) (Ronneberger et al., 2015), but
it is not widely applied in GNNs for node embeddings. After three layers of
node convolution, the final embedding for each node is
$[h_{k}^{(1)}||h_{k}^{(2)}||h_{k}^{(3)}]$. Without partitioning, this is the
embedding for our fast solution Net${}^{\text{{2f}}}$.

In order to utilize edge features, here we define our own edge convolution
layers $\mathcal{E}$ as customization. For each directed edge $n_{b}$
→$n_{k}$, we concatenate both target and source nodes’ features
$[O_{k}||O_{b}]$ together with its edge features $E_{b\rightarrow k}$ as the
input of edge convolution. Combining node features when processing edge
features enables $\mathcal{E}$ to distinguish different edges with similar
edge features. The output embedding is:

$\displaystyle
e_{k\\_sum}=\sum_{n_{b}\in\mathcal{N}(n_{k})}W_{2}W_{1}[O_{k}||E_{b\rightarrow
k}||O_{b}]$ $\displaystyle e_{k\\_mean}=\frac{1}{deg(k)}e_{k\\_sum}$

The two two-dimensional learnable weights $W_{1}$ and $W_{2}$ can be viewed as
applying a two-layer ANN to the concatenated input. We choose two-layer ANN
rather than one-layer here because the input vector $[O_{k}||E_{b\rightarrow
k}||O_{b}]$ is long and contains heterogeneous information from both edge and
node. We prefer to learn from them with a slightly more complex function.
After the operation, both $e_{k\\_sum}$ and $e_{k\\_mean}$ are on nodes. Then,
we add an extra node convolution using the output from edge convolution as
input. This structure learns from neighbors’ edge embeddings
$e_{b\\_sum},e_{b\\_mean}$.

$h_{k}^{(e)}=\mathcal{F}_{GAT}^{(e)}([e_{k\\_sum}||e_{k\\_mean}],[e_{b\\_sum}||e_{b\\_mean}])$

Inspired by the same idea in Net${}^{\text{{2f}}}$, we combine the contents
from all layers for our accurate solution Net${}^{\text{{2a}}}$. Its final
embedding is
$[h_{k}^{(1)}||h_{k}^{(2)}||h_{k}^{(3)}||e_{k\\_sum}||e_{k\\_mean}||h_{k}^{(e)}]$.
For both Net${}^{\text{{2f}}}$ and Net${}^{\text{{2a}}}$, their final
embeddings are then connected to an ANN.

##  5\. Experimental Results

###  5.1. Experimental Setup

Table 2.  Number of Cells in Netlists for Each Design

| B14 | B15 |  B17 | B18 | B20 |  B21 | B22
---|---|---|---|---|---|---|---
Smallest | 13 K | 5.3 K | 18 K | 54 K | 26 K | 26 K | 39 K
Largest | 34 K | 15 K | 49 K | 138 K | 67 K | 66 K | 99 K

Seven different designs from ITC99 (Corno et al., 2000) are synthesized with
Synopsys Design Compilier® in 45nm NanGate Library, and then placed by Cadence
Innovus™ v17.0. For each design, we synthesize 10 different netlists with
different synthesis parameters. Altogether there are 70 different netlists and
corresponding placement solutions. Table 2 shows the size of these netlists.
When testing ML models on each design, the model is only trained on the 60
netlists from the _other_ six designs to prevent information leakage. Then the
result is averaged over the 10 netlists of the tested design.

All GNNs are built with Pytorch 1.5 (Paszke et al., 2019) and Pytorch-
geometric (Fey and Lenssen, 2019). The partition on graphs is performed by
hMETIS (Karypis et al., 1999) executable files. The experiment is performed on
a machine with a Xeon E5 processor and an Nvidia GTX 1080 graphics card.

Here we introduce the best hyper-parameters after parameter tuning. For all
GNN methods, we use three layers of GNN with two layers ANN. The attention
head number of GAT is two. The size of each node convolution output is 64. The
size of edge convolution output is twice of the input size
$[O_{k}||E_{b\rightarrow k}||O_{b}]$. The size of the first-layer ANN is the
same as its input embedding, and the size of the second-layer ANN is 64. A
batch normalization layer is applied after each GNN layer for better
convergence. Because of the difference in graph size, each batch includes only
one graph, and the training data is shuffled during training. We use
stochastic gradient descent (SGD) with learning rate 0.002 and momentum factor
0.9 for optimization. GNN models converge in 250 epoches.

When partitioning each netlist, we generate seven different cell-based
partitions $P$ by requesting the number of output clusters to be the number of
cells divided by 100, 200, 300, 500, 1000, 2000, and 3000. Because different
partitions are generated in parallel, the overall runtime depends on the
slowest one. Similarly, we generate three net-based partitions $M$ by
requesting the cluster number to be the number of nets divided by 500, 1000,
and 2000. These cluster numbers are achieved by tuning during experiments,
which provides good enough coverage over different cluster sizes.

Representative previous methods MC (Hu and Marek-Sadowska, 2003), ISPL (Kahng
and Reda, 2005), and Poly (Fathi et al., 2009) are implemented for
comparisons. As for traditional ML models, we implement a three-layer ANN
model using node features $O$.

Here we summarize the receptive field of all methods. MC is limited to one-hop
neighbors, while Poly and ANN can reach two-hop neighbors. The receptive field
of ISPL varies among different nodes. According to (Kahng and Reda, 2005),
ISPL for most nets is within several hops. In comparison, all three-layer GNNs
and Net${}^{\text{{2f}}}$ can access five-hop neighbors. Net${}^{\text{{2a}}}$
measures the impact from the whole netlist.

Figure 4. Correlation coefficient R between prediction and label measured in
20 bins. Net${}^{\text{{2a}}}$ is reported in both subplots.

###  5.2. Correlation on Net Length

To measure the correlation between prediction and ground truth, we apply a
classical criterion used in many net length estimation works (Fathi et al.,
2009; Kahng and Reda, 2005; Liu and Marek-Sadowska, 2004). Firstly, we
calculate a range of net length labels [$L_{0\%min}$, $L_{95\%max}$]. It means
from the shortest net length (close to zero) to the 95 percentile largest net
length. The top 5% longest nets are excluded to prevent an extraordinarily
large range. Then, the calculated range is partitioned into 20 equal bins and
the average of both predictions and labels in each bin are calculated. Figure
4 shows the correlation coefficient between these 20 averaged predictions and
labels. Unlike some previous works, we define such 20 bins using labels
instead of predictions for a fair comparison. In this way, the nets assigned
to each bin are kept the same for different methods. On average, the
correlation coefficient for GraphSage and GAT approaches 0.93.
Net${}^{\text{{2f}}}$ further improves it to around 0.95. In comparison, the
best traditional method is ISPL, with correlation equals 0.87. The correlation
for Net${}^{\text{{2a}}}$ is higher than 0.98.

Table 3. Identify 10% Longest Nets in ROC AUC (%)

Methods | B14 | B15 |  B17 | B18 | B20 |  B21 | B22 | Ave
---|---|---|---|---|---|---|---|---
NumCell | 71.5 | 67.5 | 65.7 | 68.8 | 71.5 | 71.7 | 71.8 | 69.8
MC | 73.1 | 70.3 | 71.3 | 72.8 | 75.0 | 74.3 | 74.8 | 73.1
ISPL | 79.9 | 71.9 | 69.2 | 71.1 | 78.6 | 78.9 | 79.3 | 75.6
Poly | 75.4 | 73.0 | 73.5 | 72.8 | 75.9 | 75.2 | 76.4 | 74.6
ANN | 75.9 | 72.7 | 73.6 | 74.6 | 77.1 | 76.6 | 77.8 | 75.5
GCN | 85.1 | 75.5 | 76.1 | 76.1 | 85.0 | 84.6 | 85.5 | 81.1
GSage | 84.9 | 75.9 | 75.3 | 74.6 | 85.6 | 85.2 | 84.8 | 80.9
GAT | 85.5 | 76.5 | 75.4 | 78.0 | 87.0 | 85.7 | 86.0 | 82.0
Net${}^{\text{{2f}}}$ | 86.9 | 80.1 | 80.9 | 79.3 | 88.7 | 88.2 | 87.3 | 84.5
Net${}^{\text{{2a}}}$ | 93.5 | 91.7 | 90.7 | 90.3 | 93.0 | 93.0 | 92.9 | 92.2

###  5.3. Identifying Long Nets

In practice, we are also interested in how different methods can identify
those longer nets. Table 3 shows the accuracy in identifying the top 10%
longest nets. For each netlist, the 10% longest nets are labeled as true, and
the accuracy is measured in ROC curve’s area under curve (AUC). Then, the
accuracy for each design is averaged over its 10 netlists. Since the net with
many cells tends to be long, we add a baseline which directly estimates net
length with the number of cells. On average, ANN, Poly and ISPL outperform MC
and the number of cells with AUC$\sim=$0.76. Models capturing two or more-hop
neighbors outperform models viewing one-hop neighbors only. Then graph methods
(AUC$\sim=$0.82) are better than ANN by learning with a larger receptive field
reaching five-hop neighbors. By combining shallow and deep embeddings,
Net${}^{\text{{2f}}}$ outperforms normal GNN with AUC$\sim=$0.85.
Net${}^{\text{{2a}}}$ significantly outperforms all graph methods by learning
the global information on edge features with its edge convolution layer.

Figure 5. ROC curves in identifying 10% longest nets.

Figure 5 shows a visualization of the ROC curves for identifying the top 10%
longest nets. A few less important methods are omitted for clarity. To
visualize results from 70 netlists on one ROC curve, after prediction
finishes, we put all nets from all 70 netlists together. Then the 10% longest
nets are selected and the ROC curve is measured on all these nets. The
vertical dashed line means when the false positive rate (FPR) equals 0.1. The
AUC measured on all nets for 10% longest nets is fairly consistent with the
average value shown in Table 3. On the right of Figure 5 also shows the true
positive rate (TPR) for each method when FPR = 0.1. Both Net${}^{\text{{2f}}}$
and Net${}^{\text{{2a}}}$ significantly outperform previous works under all
FPR.

###  5.4. Results on Path Length Estimation

In many EDA tools, the pre-placement timing report does not include wire
delay, which hinders identifying critical paths accurately at an early stage.
An application of net length estimation is to predict the length of any given
path, which correlates with post-placement wire delay on the path. The path
length is defined as the summation of the net lengths over all nets on this
path.

Table 4. Identify 10% Longest Paths in ROC AUC (%)

Methods | B14 | B15 |  B17 | B18 | B20 |  B21 | B22 | Ave
---|---|---|---|---|---|---|---|---
ISPL | 58.9 | 57.5 | 56.5 | 74.0 | 72.5 | 63.0 | 75.5 | 65.4
Poly | 65.5 | 80.0 | 78.0 | 68.0 | 82.0 | 85.0 | 84.0 | 77.5
ANN | 68.0 | 76.0 | 80.0 | 69.0 | 78.5 | 82.0 | 75.5 | 75.6
GCN | 63.5 | 75.0 | 86.5 | 56.0 | 82.0 | 81.5 | 85.5 | 75.7
GSage | 65.0 | 88.0 | 93.0 | 77.0 | 81.5 | 67.0 | 80.0 | 78.8
GAT | 63.0 | 92.0 | 95.0 | 83.5 | 83.5 | 76.0 | 89.5 | 83.2
Net${}^{\text{{2f}}}$ | 79.0 | 88.5 | 97.5 | 84.0 | 75.5 | 83.0 | 92.0 | 85.6
Net${}^{\text{{2a}}}$ | 86.5 | 95.0 | 96.0 | 90.5 | 90.5 | 93.5 | 95.5 | 92.5

Table 5. Comparing Pair of Paths by Lengths (%)

Methods | B14 | B15 |  B17 | B18 | B20 |  B21 | B22 | Ave
---|---|---|---|---|---|---|---|---
ISPL | 67.1 | 55.0 | 58.2 | 77.4 | 68.9 | 59.7 | 69.5 | 65.1
Poly | 83.9 | 86.6 | 83.3 | 70.4 | 83.4 | 80.4 | 86.3 | 82.0
ANN | 82.0 | 74.8 | 75.3 | 68.1 | 81.9 | 65.4 | 80.5 | 75.4
GCN | 74.5 | 85.9 | 83.0 | 62.4 | 83.4 | 81.0 | 86.2 | 79.5
GSage | 84.2 | 92.5 | 83.9 | 75.3 | 89.1 | 62.8 | 88.1 | 82.3
GAT | 82.4 | 93.5 | 85.1 | 80.6 | 89.7 | 87.5 | 88.2 | 86.7
Net${}^{\text{{2f}}}$ | 87.3 | 92.7 | 87.6 | 93.1 | 91.1 | 91.2 | 86.9 | 90.0
Net${}^{\text{{2a}}}$ | 96.8 | 97.0 | 91.4 | 95.9 | 92.2 | 94.2 | 94.4 | 94.6

To verify models’ performance on path length, for each netlist, we collect the
timing-critical paths according to the pre-placement timing report. The report
at this stage only includes cell delay. The path’s slack has to be negative.
Among these paths, the longer ones would be even more timing-critical
considering wire delay after placement. Thus we apply models to identify those
longest critical paths. The estimated path length is a summation over the
predicted net lengths among all nets on the path.

Table 4 shows the ROC curve accuracy in identifying 10% longest path. MC is
not supposed to be _linearly_ proportional to actual wire length; thus the
summation over MC is not included as path length estimation. Because the
number of critical paths is much less than the number of nets, the trend on
accuracy is not very consistent on different designs. On average, we can still
observe an obvious trend that Net${}^{\text{{2a}}}$ ¿ Net${}^{\text{{2f}}}$ ¿
GAT ¿ other methods.

In addition to locating the longest paths, we are interested in how models
recognize the longer path when comparing any pair of two paths. To avoid
meaningless comparisons between paths with very similar lengths, for each
path, we compare it with all paths 30% longer or shorter than it in its
netlist. Table 5 shows the percentage of correct comparisons. Poly is the best
method among previous works. The trend in accuracy is similar,
Net${}^{\text{{2a}}}$ ¿ Net${}^{\text{{2f}}}$ ¿ GAT ¿ other methods.

###  5.5. Runtime Comparison

Table 6. Runtime Comparison (In seconds)

Design | Place | Partition | Net${}^{\text{{2f}}}$ | Net${}^{\text{{2a}}}$ | Net${}^{\text{{2f}}}$ | Net${}^{\text{{2a}}}$
---|---|---|---|---|---|---
Infer | Infer | Speedup | Speedup
Ave | 97.8 | 7.0 | 0.05 | 0.07 | 1.7K $\times$ | 14.3$\times$

Table 6 shows the runtime of placement and Net${}^{\text{{2}}}$. The runtime
is averaged over all netlists. For a fair comparison, the runtime of placement
includes the placement algorithm only, without any extra time for file I/O,
floorplanning, or placement optimization. Net${}^{\text{{2a}}}$ takes slightly
longer inference time than Net${}^{\text{{2f}}}$ for its extra edge
convolution layer. The overall runtime of Net${}^{\text{{2a}}}$ includes both
partition and inference. Partitioning takes the majority of the runtime.
Net${}^{\text{{2a}}}$ is more than 10$\times$ faster than placement. The
runtime of Net${}^{\text{{2a}}}$ can be potentially improved by using coarser
but faster partition $P$ and $M$, especially on larger designs. Without
partition, Net${}^{\text{{2f}}}$ is more than 1000$\times$ faster than
placement. In addition, it takes around 30 minutes to train the
Net${}^{\text{{2a}}}$ model.

##  6\. Discussion

In previous sections, we demonstrate the superior accuracy of
Net${}^{\text{{2}}}$ over other methods. Now we decompose
Net${}^{\text{{2a}}}$ to figure out which strategy contributes the most to its
high accuracy. Table 7 and 8 measure the accuracy in identifying 10% longest
nets and 10% longest paths. The ‘Edge ANN’ means using edge features without
GNN. Edge features are aggregated on their target node and processed with ANN
together with node features. The ‘Simple Net’ means using a simplified GNN
structure. There is only one GAT layer for node convolution. The edge
convolution only includes edge features and one layer of weights:
$e_{k\\_simple}=\sum_{b\in\mathcal{N}(k)}W_{1}E_{b\rightarrow k}$. When not
considering edge features, the receptive fields of ‘Edge ANN’ and ‘Simple Net’
are reduced to two hops and three hops, respectively. To analyze the
contribution of different edge features, models ‘F0 Net’, ‘F1 Net’ and ‘F2+f
3 Net’ use only $F0$, $F1$, $F2$ $\&$ $f3$ in edge features, respectively.
The ‘Less $P$ Net’ uses only the 4 coarser-granularity but faster cell
partitions over the 7 partitions $P$ used in Net${}^{\text{{2a}}}$. Thus its
number of clusters equals the number of cells divided by 500, 1000, 2000, and
3000. Its smallest granularity is $5\times$ coarser than $P$. It is
$\sim$1.5$\times$ faster than Net${}^{\text{{2a}}}$ and more than 20$\times$
faster than placement.

All these variations from Net${}^{\text{{2a}}}$ outperform GAT. The ‘Edge ANN’
without GNN architecture is the worst variation, with around 4% performance
degradation. ANN’s receptive filed and flexibility are not as good as
Net${}^{\text{{2a}}}$. But it still demonstrates the effectiveness of edge
features. The ‘Simple Net’ is 1.5-2% worse compared with
Net${}^{\text{{2a}}}$. Among the edge features, $F1$ contributes the most to
accuracy. The model using less cell partitions $P$ is only around 0.6% less
accurate than Net${}^{\text{{2a}}}$. It means using coarser-granularity
partitions will not largely affect the performance of Net${}^{\text{{2a}}}$.

Table 7. Identify 10% Longest Nets in ROC AUC (%)

Methods | B14 | B15 |  B17 | B18 | B20 |  B21 | B22 | Ave
---|---|---|---|---|---|---|---|---
Edge ANN | 90.6 | 83.9 | 85.5 | 87.7 | 89.9 | 89.6 | 90.5 | 88.2
Simple Net | 92.3 | 89.6 | 88.9 | 89.7 | 91.6 | 91.7 | 91.7 | 90.8
F0 Net | 92.4 | 90.8 | 89.7 | 89.0 | 92.0 | 91.7 | 91.6 | 91.0
F1 Net | 93.0 | 91.4 | 90.3 | 89.8 | 92.6 | 92.3 | 92.5 | 91.7
F2+f 3 Net | 91.2 | 88.3 | 85.9 | 85.9 | 91.0 | 90.5 | 90.4 | 89.0
Less $P$ Net | 92.9 | 91.2 | 89.7 | 89.6 | 92.7 | 92.5 | 92.3 | 91.6
Net${}^{\text{{2a}}}$ | 93.5 | 91.7 | 90.7 | 90.3 | 93.0 | 93.0 | 92.9 | 92.2

Table 8. Identify 10% Longest Paths in ROC AUC (%)

Methods | B14 | B15 |  B17 | B18 | B20 |  B21 | B22 | Ave
---|---|---|---|---|---|---|---|---
Edge ANN | 77.0 | 91.0 | 94.5 | 88.0 | 85.0 | 89.5 | 94.0 | 88.4
Simple Net | 83.5 | 93.0 | 94.5 | 89.5 | 87.5 | 92.0 | 94.5 | 90.6
F0 Net | 77.0 | 89.5 | 95.0 | 90.0 | 90.0 | 87.5 | 93.5 | 88.9
F1 Net | 81.5 | 93.0 | 95.5 | 90.5 | 89.5 | 87.5 | 95.0 | 90.4
F2+f 3 Net | 82.0 | 92.5 | 97.0 | 85.5 | 87.5 | 93.5 | 93.5 | 90.2
Less $P$ Net | 84.5 | 94.0 | 96.5 | 88.0 | 91.0 | 94.0 | 95.5 | 91.9
Net${}^{\text{{2a}}}$ | 86.5 | 95.0 | 96.0 | 90.5 | 90.5 | 93.5 | 95.5 | 92.5

##  7\. Conclusion

In this paper, we propose Net${}^{\text{{2}}}$, a graph attention network
method customized for individual net length estimation. It includes a fast
version Net${}^{\text{{2f}}}$ which is 1000 $\times$ faster than placement and
an accuracy-centric version Net${}^{\text{{2a}}}$ which efficiently extracts
global information and outperform all previous methods. In future works, we
will extend it to pre-placement timing analysis.

## Acknowledgments

This work is partially supported by Semiconductor Research Corporation Tasks
2810.021 and 2810.022 through UT Dallas’ Texas Analog Center of Excellence
(TxACE).

## References

  * (1)
  * Bodapati and Najm (2001) Srinivas Bodapati and Farid N Najm. 2001.  Prelayout estimation of individual wire lengths.  _TVLSI_ (2001).
  * Cadence (2020) Cadence. 2020.  Cadence digital full flow optimized to deliver improved quality of results with up to 3X faster throughput.  https://www.cadence.com/en_US/home/company/newsroom/press-releases/pr/2020/cadence-digital-full-flow-optimized-to-deliver-improved-quality-.html
  * Corno et al. (2000) Fulvio Corno, Matteo Sonza Reorda, and Giovanni Squillero. 2000\.  RT-level ITC’99 benchmarks and first ATPG results.  _Design & Test of computers_ (2000).
  * Fang et al. (2018) Yen-Chun Fang et al. 2018\.  Machine-learning-based dynamic IR drop prediction for ECO. In _ICCAD_.
  * Fathi et al. (2009) Bahareh Fathi, Laleh Behjat, and Logan M Rakai. 2009\.  A pre-placement net length estimation technique for mixed-size circuits. In _SLIP_.
  * Fey and Lenssen (2019) Matthias Fey and Jan E. Lenssen. 2019.  Fast graph representation learning with PyTorch Geometric. In _ICLR-W_.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _NeurIPS_.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _CVPR_.
  * Hu and Marek-Sadowska (2003) Bo Hu and Malgorzata Marek-Sadowska. 2003.  Wire length prediction based clustering and its application in placement. In _DAC_.
  * Hyun et al. (2019) Daijoon Hyun, Yuepeng Fan, and Youngsoo Shin. 2019\.  Accurate wirelength prediction for placement-aware synthesis through machine learning. In _DATE_.
  * Kahng and Reda (2005) Andrew B Kahng and Sherief Reda. 2005.  Intrinsic shortest path length: a new, accurate a priori wirelength estimator. In _ICCAD_.
  * Karypis et al. (1999) George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. 1999.  Multilevel hypergraph partitioning: applications in VLSI domain.  _TVLSI_ (1999).
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks. In _ICLR_.
  * Kirby et al. (2019) Robert Kirby et al. 2019\.  CongestionNet: Routing Congestion Prediction Using Deep Graph Neural Networks. In _VLSI-SoC_.
  * Liu et al. (2012) Qiang Liu, Jianguo Ma, and Qijun Zhang. 2012.  Neural network based pre-placement wirelength estimation. In _FPT_.
  * Liu and Marek-Sadowska (2004) Qinghua Liu and Malgorzata Marek-Sadowska. 2004\.  Pre-layout wire length and congestion estimation. In _DAC_.
  * Ma et al. (2019) Yuzhe Ma et al. 2019\.  High performance graph convolutional networks with applications in testability analysis. In _DAC_.
  * Magen et al. (2004) Nir Magen, Avinoam Kolodny, Uri Weiser, and Nachum Shamir. 2004.  Interconnect-power dissipation in a microprocessor. In _SLIP_.
  * Paszke et al. (2019) Adam Paszke et al. 2019\.  PyTorch: An imperative style, high-performance deep learning library. In _NeurIPS_.
  * Pedram and Bhat (1991a) Massoud Pedram and Narasimha Bhat. 1991a.  Layout driven technology mapping. In _DAC_.
  * Pedram and Bhat (1991b) Massoud Pedram and Narasimha B Bhat. 1991b.  Layout driven logic restructuring/decomposition. In _ICCAD_.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox. 2015\.  U-net: Convolutional networks for biomedical image segmentation. In _MICCAI_.
  * Synopsys (2020) Synopsys. 2020.  Fusion Compiler: the singular RTL-to-GDSII digital implementation solution.  https://www.synopsys.com/implementation-and-signoff/physical-implementation/fusion-compiler.html
  * Veličković et al. (2017) Petar Veličković et al. 2017\.  Graph attention networks. In _ICLR_.
  * Xie et al. (2018) Zhiyao Xie et al. 2018\.  RouteNet: Routability prediction for mixed-size designs using convolutional neural network. In _ICCAD_.
  * Xie et al. (2020) Zhiyao Xie, Haoxing Ren, Brucek Khailany, Ye Sheng, Santosh Santosh, Jiang Hu, and Yiran Chen. 2020.  PowerNet: Transferable Dynamic IR Drop Estimation via Maximum Convolutional Neural Network. In _ASPDAC_.
  * Zhang et al. (2019) Guo Zhang, Hao He, and Dina Katabi. 2019.  Circuit-GNN: Graph neural networks for distributed circuit design. In _ICML_.


# Context-Aware Self-Supervised Learning of Whole Slide Images

Milan Aryal and Nasim Yahyasoltani  The authors are with the Department of
Computer Science, Marquette University, Milwaukee, WI, USA (e-mail:
{Milan.aryal, nasim.yahyasoltani}@marquette.edu).Part of this work was
presented at the IEEE ICASSP Conference held in Singapore, during May 7-10,
2022.

###### Abstract

Presenting whole slide images (WSIs) as graph will enable a more efficient and
accurate learning framework for cancer diagnosis. Due to the fact that a
single WSI consists of billions of pixels and there is a lack of vast
annotated datasets required for computational pathology, the problem of
learning from WSIs using typical deep learning approaches such as
convolutional neural network (CNN) is challenging. Additionally, WSIs down-
sampling may lead to the loss of data that is essential for cancer detection.
A novel two-stage learning technique is presented in this work. Since context,
such as topological features in the tumor surroundings, may hold important
information for cancer grading and diagnosis, a graph representation capturing
all dependencies among regions in the WSI is very intuitive. Graph
convolutional network (GCN) is deployed to include context from the tumor and
adjacent tissues, and self-supervised learning is used to enhance training
through unlabeled data. More specifically, the entire slide is presented as a
graph, where the nodes correspond to the patches from the WSI. The proposed
framework is then tested using WSIs from prostate and kidney cancers. To
assess the performance improvement through self-supervised mechanism, the
proposed context-aware model is tested with and without use of pre-trained
self-supervised layer. The overall model is also compared with multi-instance
learning (MIL) based and other existing approaches.

###### Index Terms:

Self-supervised learning, whole slide image, graph convolutional networks,
computational pathology, prostate cancer, kidney cancer.

##  I Introduction

The pathologic assessment of a tissue sample or excision is used to diagnose
cancer. The sample is cut into small layers before being put on a glass slide
and inspected under a microscope to determine the diagnosis. The diagnosis and
prognosis of cancer is done by pathologists using hematoxylin and eosin(H&E)
and other stains slide [1]. The developments of digital scanners in recent
years have enabled the digitization of glass slides into WSIs. The WSIs are
multi-scale, multi-resolution digital images of the tissue slides. Preliminary
diagnosis by machine, obviously, may help pathologists be more efficient in
diagnosis and may assist to avoid certain mistakes. The usage of WSIs in
computational pathology for diagnosis has recently risen dramatically.

In this work we are looking at the classification of the grading of cancer
using deep learning. More specifically, the WSIs of prostate and kidney have
been used for grading the cancer. After lung cancer, prostate cancer is the
second leading cause of mortality among men [2]. On the basis of the grading
of prostate tissue samples, prostate cancer can be diagnosed. The pathologist
grades the samples using the Gleason grading system, which is subsequently
translated into an ISUP score on a scale of 1 to 5.

Kidney cancer falls into top 10 most common cancers for both male and female.
The kidney cancer accounts for 5% of the new cases among male and 3% of the
new cases among female [2]. Renal Cell Carcinoma (RCC), which accounts for 85%
of all occurrences of kidney cancer, is the most prevalent malignant tumor
[3]. Based on the difference in histology, molecular characteristics and
response to therapy RCC can be further classified into subtypes [4]. The major
subtypes of the RCC include ”Clear cell”, ”Papillary cell” and ”Chromophobe”
which account for 75%, 16% and 7% of all the RCC cases, respectively [3]. In
this work, we will look into grading of these subtypes of the kidney cancer.

Deep learning has been used successfully in the field of medical imaging [5],
[6], [7], [8]. These accomplishments, which are largely the result of
supervised learning, are based on a large amount of labeled data. The
availability of annotated datasets in the medical domain is extremely limited.
The lack of annotation in medical data is mainly because the task requires an
expert in the field to go through each data one by one manually to label them.
This makes the labeling process more expensive and time consuming. The use of
transfer learning [9], [10], [11] in medical images is widely considered to
overcome this issue in the dataset. To extract the meaningful representation
of unlabeled data, unsupervised learning techniques might also be recommended.
It is possible to employ self-supervised learning [12], a type of unsupervised
learning to learn from unlabeled data and then apply it to subsequent task.
The application of self-supervised learning in the medical field as a pretext
task has recently increased due to the effectiveness of the technique in other
computer vision applications [13], [14]. Self-supervised learning approaches
benefit from not requiring lots of labeled data.

Figure 1: The proposed model’s system block diagram. Given the WSI, the tissue
is segmented first from the background. On the segmented tissue patches of
size 256$\times$256 are generated. Each patch acts as a node for the the graph
generation. Then, these patches are trained using SSL for representation
learning. From SSL, feature for each patch is generated which is the node
feature for our graph. The WSI graph is then trained using GCN for cancer
grading.

Even though CNN is well adopted in image classification and has cutting-edge
techniques for processing high-resolution pictures, they cannot be effectively
trained for high-resolution WSIs. This is mostly due to the fact that a single
WSI comprises more than a billion pixels at its greatest resolution, and
downsampling WSIs or looking only at regions of interest may result in the
loss of important information in the area surrounding the tumor that is
essential for the cancer diagnosis.

The difficulties of training the WSIs can be summed up as follows:

  * •

Large dimensionality of the WSIs.

  * •

Lack of annotated data.

We address these issues in this work by presenting GCN based self-supervised
learning for WSIs. Self-supervised learning allows to learn the meaningful
representation presented by the data without having to label or annotate the
data. The tumor environment and neighborhood information are employed in
training when presenting WSIs as a graph. In summary the contribution of this
work can be listed as:

  * •

Introduction of context-aware self-supervised learning on patches and graph-
based learning on WSIs.

  * •

Learning the features in patch levels and representation of any arbitrary size
WSIs as a graph in full resolution.

The remaining sections of the paper are organized as follows. The related
research in this area has been covered in Section II. Section III presents our
proposed approach and details about learning methods used for the experiments.
Datasets used for the experiment and details about the parameters used in our
training are discussed in Section IV. The findings of the simulations are
shown in section V. Discussion of the suggested work in Section VI helps to
clarify the findings. Section VII serves as the paper’s conclusion.

Figure 2: Pre-processing of WSI to generate the graph. Top part shows the
graph generation in kidney resection, bottom part represents similar process
in prostate biopsy. a) Whole Slide Image b) Contour separating tissue from
background c) WSI divided into patches d) WSI as a graph.

##  II Related Work

Recently, there has been extensive research efforts in computational
pathology. In order to tackle the difficulty of training models employing
WSIs, weakly supervised learning based on MIL [15] or tile-based patches have
been utilized [16], [17], [18], [19], [20]. Rather than depending on fully
supervised learning which requires manual annotation, the authors have
proposed classifying cancer based on the WSI using MIL approach where the
whole slide is divided into different tiles. The important idea is that if the
WSI is negative, at least one of the tiles must also be negative and not
contain the tumor. Similar to this, for the slide to be positive if the WSI is
positive, the tumor must be present in at least one of the tiles. This
generalizes to the so-called MIL approach.

In [17] the authors have proposed a two-stage network. They began by training
the model with MIL in order to produce tile-level feature representations. On
the basis of these representations, an estimate of the final classification
score was generated with the help of a recurrent neural network (RNN). The
paper focuses on binary classification. More specifically, the authors’
focuses were on prostate, skin and breast cancers. Even though authors
investigate the problem of prostate cancer, the model is not trained for
Gleason grading. In [21], the authors presented multi-resolution MIL, which
can be trained using slide levels for prostate cancer grading. The work
consists of a two-stage cancer detection model. In the initial stage, low
resolution patches were examined to see if they contained any signs of
malignancy. At the second stage, cancer grade classification was carried out
using a higher magnification for the suspicious spots.

In [4] the authors look at the problem of classifying the sub-types in the
kidney RCC. For the classification, they suggest a two-stage process. First
the patches were extracted and a binary classification is performed to
identify the cancerous and non-cancerous patch. A 3-way classification for
patches was carried out using the feature extracted from the first stage in
the second step. In [22], a pyramidal deep learning pipeline with three CNN
and patches of three different sizes were looked into to separate clear cell
RCC from papillary cell RCC.

The methods described above are looking at WSIs in patches and are solving the
cancer classification task only in slide-level. Almost all the above methods
use MIL. They are not context-aware as the outcome of one patch has no effect
on other patches in most of the cases. These methods rely on CNNs and are
unable to capture the context between the patches. At this point, having a
graph structure that is capable of capturing the relation that exists between
the various nodes will come in handy. With recent advancements in graph neural
networks(GNNs), they have been able to make impacts in computer visions and
medical imaging application as well. In [23] authors have discussed about the
various graph-based methods used in computational histopathology. A
combination of MIL and graph-based learning is presented in [24]. The authors
first selected the bag of patches and then the bag representation was
presented for the graph-based MIL. A graph-based framework for the WSI is
provided in [25], where the graph is built via patch selection from certain
areas of WSI. This work further demonstrates that graph-based strategies
perform better than MIL methods.

##  III Method

In Fig. 1, the overall proposed model block diagram is presented. The block
diagram demonstrates how a GCN and a self-supervised learning model are
coupled for the classification of cancer. In this work, we are representing
WSI, a multi-resolution image into graph data structure. The graph data to be
trained into GCN requires the features, so we need to capture the information
embedded in those image pixels when representing the WSI as a graph. To be
more explicit, WSI is shown as a graph with each node being a smaller patch
that was created by subdividing WSI. Pretrained self-supervised learning is
used to encode the features within these patches. These features, along with
the WSI’s entire graph structure, are used to train the GCN for cancer
grading.

The entire graph creation [26] procedure for the WSI is displayed in Fig. 2.
The following sections go over patch generation, graph generation and methods
to learn from them.

###  III-A Patch generation

The dataset contains WSI with multi-scale resolution. In WSIs, the white
background is useless for diagnosing cancer. The first stage in patch
generation from WSI is to separate the tissue from white background. From any
WSI resolution, the white background may be eliminated. The tissue is
separated from the background using the segmentation network based on UNet
[27] style encoder and decoder. For the purpose of training the segmentation
network, the smallest WSI solution was downscaled to a 512$\times$512 image.
OpenCV is utilized to create the contour dividing the tissue region from the
background in the WSI using the segmentation network’s output. From the WSI,
patches of size 256$\times$256 are created with the greatest resolution based
on the contours. These patches are used to train self-supervised learning and
extract meaningful features.

###  III-B Learning from patches

####  III-B1 Self-supervised learning

One of the most well-known unsupervised learning methods for pre-training,
often known as pretext tasks, is self-supervised learning. These pretext tasks
are then adjusted for subsequent tasks [28], [12]. The most widely used form
of self-supervised learning is contrastive learning [29]. Learning the
representation that optimizes the agreement between similar patches and the
disagreement between distinct patches is the aim of contrastive learning. Even
though the similar patches might have different views, using contrastive
learning we want to learn the similar representation for each of them. These
different views are generated by applying the augmentation to the original
patches.

Self-supervised learning techniques are best suited to learn from these
patches because they are not labeled. Fig. 3 illustrates how self-supervised
learning is implemented. The original patch is applied augmentation to obtain
two different views. The different views obtained from the same patch are
positive pair and the the negative pairs are the ones obtained from the
different patch. In this work, encoder, momentum encoder proposed in [28],
[30] is used for the training of the self supervised network. The advantage of
this method over other method such as end-to-end learning [29], memory bank
[12] is that the batch size does not have to be large and there is no need of
memory bank. Also encoder and momentum encoder share the same parameter,
requiring only one model to be trained. In this method dictionary is built as
a queue. The key and query can be seen as dictionary lookup. In contrastive
learning, the positive pair occurs when the key and query patches come from
the same sample but the negative pair comes from a separate sample. We employ
contrastive learning loss in the form of the InfoNCE provided by [31] :

$L_{q}=-log\frac{exp(q\cdot k^{+}/\tau)}{exp(q\cdot
k^{+}/\tau)+\sum_{k^{-}}exp(q\cdot k^{-}/\tau)}$ (1)

where $k^{+}$ is the patch $q$’s positive pair and $k^{-}$ is the patch $q$’s
negative pair, and $\tau$ is the temperature hyper-parameter.

Figure 3: SSL framework applied for learning from the patches. The contrastive
loss is used to train the SSL. The goal is to maximize the similarity between
the different augmented views from the same patch, i.e., positive pairs and
maximize dissimilarity between the negative pairs.

The GCN uses features obtained from patches learnt through contrastive
learning as node features. These features are learned without the need of any
annotation from pathologists. Then, unlike previously used methodologies,
there is no need to locate regions of interest for cancer grading or
concatenate tile patches based on pixel intensity for feature extraction.

###  III-C Representing WSI as a graph

Once patches for each of the WSI are generated and trained with the self-
supervised framework then the WSI graph is generated. The WSI graph node
corresponds to the centroid of each patch. The fast approximate k-nearest
neighbor (K-NN) [32] method can then be used to determine the adjacency matrix
for each node. The feature for each patch is extracted from self-supervised
model trained on the patches of each tissue.

###  III-D Learning on graphs

####  III-D1 Graph Neural Network

Figure 4: Learning from WSI Graph using GCN.

Using graph neural learning, a meaningful representation of the graph is
learned. In GNN the learning is done by passing the message between the nodes
and updating it iteratively. The input graph $G=(V,E)$ with node features
$X\in{R}^{d\times|V|}$, $d$ is the dimension of node feature vector, learns
from graph neighborhood $N(u),\forall u\in V$ through message passing. The
$k^{th}$ iteration message passing update is provided by[33]

$\displaystyle h_{u}^{(k)}$
$\displaystyle=\sigma\left(W_{self}^{(k)}h_{u}^{(k-1)}+W_{neigh}^{(k)}\sum_{v\in
N(u)}h_{v}^{(k-1)}+b^{(k)}\right)$ (2)

where the $W_{self}^{(k)}$,$W_{neigh}^{(k)}$ are trainable parameters, non-
linearity is accounted by $\sigma$ and bias term is given by $b^{(k)}$. Over
the course of the iterations, the embeddings $h_{u}$ are updated and at $k=0$,
$h_{u}^{(0)}=X_{u},\forall u\in V$. The node level equation is given by
equation 2. The graph level equation for message passing is as following:

$H^{(k)}=\sigma\left(AH^{(k-1)}W_{neigh}^{(k)}+H^{(k-1)}W_{self}^{(k)}\right)$
(3)

where $H^{(k)}$ is a $R^{|V|\times d}$ containing feature for all nodes, graph
adjacency matrix is given by $A$. This work makes use of the GCN [34] to learn
from WSIs represented as graphs. Following equation gives message passing
equation for GCN

$h_{u}^{(k)}=\sigma\left(W^{(k)}\sum_{v\in
N(u)}\frac{h_{v}}{\sqrt{|N(u)||N(v)|}}\right)$ (4)

Global average pooling on all nodes is applied, then MLP head, following the
implementation of the GCN layer and the use of the node feature matrix $H$
from the penultimate layer. Multi-layer perceptron is referred to as MLP. The
grading of cancer is done using the cross-entropy loss function. Graph
learning steps for the WSI are depicted in Fig. 4.

####  III-D2 GNN for WSI

The WSIs are depicted as a graph shown in Fig. 2. A tuple $G=(V,E)$ describes
a graph. The nodes are represented by the set $V$, and the edges, represented
by the set $E$, show how connected the nodes are to one another. In section
IIA, the construction of patch is discussed. The patch is represented as the
node and the the connectivity between the patches is represented as the edges.

The WSI is a multi resolution file. We retrieved patches with a size of
256$\times$256 at the maximum resolution possible. All of the WSIs in the
dataset do not have the same dimension. Because of this, there are varying
numbers of nodes in the graphs due to the different numbers of patches
extracted per WSI. Every node also includes a feature matrix that was created
by running a patch through a previously trained self-supervised model.The
acquired features are used to do learning on the graph for WSI.

The tissue and the context of the surrounding cells play a role in the cancer
diagnosis. The cancerous tissue can spread over its neighbor and this
information must be captured in learning. Using messages from its immediate
neighborhood, a node in a GNN can learn the context of its surroundings. In
our cancer grading the message is passed from its neighboring patches making
our network contextually aware of its neighborhood.

##  IV Implementation details

###  IV-A Dataset

####  IV-A1 PANDA Dataset

One of the datasets utilized in this work was obtained from the Kaggle PANDA
challenge [35]. The WSIs of the prostate biopsies are provided by the
challenge to categorize according to the Gleason score. For each biopsy two
Gleason score is given by the pathologists. The most cancerous tissue is given
primary score which ranges from 1-5 and secondary score which also ranges from
1-5 is assigned to other surrounding tissue. The primary and secondary score
add up to give Gleason score range from 2 to 10. The International Society of
Urological Pathology (ISUP) grades prostate cancer based on Gleason score. The
ISUP grade along with Gleason score are displayed in Table I. The PANDA
challenge is to assign the WSIs to one of six ISUP grades. In Fig. 5 the
patches obtained from WSIs with Gleason score for primary and secondary scores
along with ISUP grade are shown. As the glandular or white hole properties in
the tissues are eliminated, as seen in Fig. 5, the primary Gleason score
increases. In PANDA challenge around 10500 WSIs are provided in the dataset.
The resoultion scale of the WSIs in the datasets is 1, 4, 16. The highest
resolution was used for the simulation in this work. The train set for our
experiment contained 9500 WSIs, whereas the validation set contained the
remaining ones.

TABLE I: prostate cancer grading Gleason Score | ISUP Grade
---|---
6 | 1
7 (3+4) | 2
7 (4+3) | 3
8 | 4
9-10 | 5
Figure 5: Patches from WSI showing Gleason and ISUP score for prostate cancer.
Figure 6: Patches from WSI showing the subtype of kidney RCC.

####  IV-A2 TCGA Kidney Dataset

The dataset for Kidney cancer was obtained from the The Cancer Genome Atlas
(TCGA) portal [36], [37], [38]. It consists of a catalog of biomedical data
related to cancer. The main aim of the project is to make the data available
for researchers so that various bio markers of different cancer types can be
discovered. TCGA portal consists of different types of data such as clinical
information, molecular analyze metadata and molecular characterization data,
WSI of the tissue related to same case. In this work, we have looked into WSIs
for kidney cancer.

The TCGA dataset on kidney cancer looks into most common types of tumor in
Kidney cancer i.e., RCC. The project is further grouped into most common types
of RCC subtype. The TCGA consists of 3 projects for each subtype i.e., TCGA-
KIRC (Kidney Renal Clear Cell Carcinoma), TCGA-KIRP (Kidney Renal Papillary
Cell Carcinoma) and TCGA-KICH (Kidney Chromophobe). The most frequent
malignant tumor of the kidney is renal cell carcinoma (RCC). For this work,
the dataset from TCGA portal consists of 519 samples of WSIs for KIRC, 300
samples of WSIs for KIRP, and 121 WSIs sample for KICH. The train set consists
of the 85% of the data and rest is included in validation set. In Fig. 6 the
patches for the subtype of the kidney RCC is shown.

###  IV-B Training the self-supervised model

The first part of of our experiment required training the model for the self-
supervised learning. Before training the self-supervised part patches were
extracted from the WSI and made ready for the self-supervised training. The
patches were extracted after training a small subset around 10% of the dataset
for the segmentation of tissue to separate tissue from white background using
UNet network. The UNet network with EfficientNet as the backbone was trained
for 20 epochs.

The first part of the experiment involved training self-supervised model for
75 epochs. The model was trained using Adam optimizer, the weight decay was 1
$\times$ $10^{-6}$, and the learning rate was 3 $\times$ $10^{-3}$. The
learning rate was modified using the cosine scheduler. The batch size was set
as 256. During training 0.2 was used as the value of parameter $\tau$. The
mocoV3 [30] framework was used to train the self-supervised network with
ResNet50 as backbone. The contrastive learning requires different views of the
same patch which were obtained using the data augmentation while training.
Random Gaussian Blur, random contrast adjustment, and random horizontal and
vertical flip are among data augmentation methods used during training.

###  IV-C Training the graph network

In the second part of the experiment, trained self-supervised model was used
to extract the feature for each patch and create the graphs for the WSI. After
the graphs were constructed for the whole dataset, GCN was trained. For GCN
Adam optimizer was used to train the model for 30 epochs. The learning rate
was modified using cosine scheduler during the training with initial learning
rate 1 $\times 10^{-4}$, weight decay of $10^{-6}$. The model was trained with
batch size of 1.

###  IV-D Evaluation Metrics

In this work we make use of weighted Kappa ($\kappa$) [39] score to measure
the performance of our model. The agreement between both the actual and
projected outcome is measured by the quadratic weighted kappa score. An N
$\times$ N matrix $O$ is formed such that $O_{i,j}$, $i$ is actual and $j$ is
predicted outcome. With a N$\times$N weight matrix as
$w_{i,j}=\frac{(i-j)^{2}}{N-1}$, $\kappa$ is calculated as

$\kappa=1-\frac{\sum_{i,j}w_{i,j}O_{i,j}}{\sum_{i,j}w_{i,j}E_{i,j}}$ (5)

Where, in $O_{i,j}$, $i$ is actual and $j$ is predicted outcome.

##  V Results

We validated our model with two different datasets. First, the model is
validated using the WSIs from the biopsies of the prostate cancer and then the
simulations are run on WSIs from the resection of the kidney. The $\kappa$
score was used to assess the model’s performance.

For the first test, PANDA dataset was used to train the model. Malignant
slides were to be graded from 1 to 5, whereas non-cancerous slides were to be
predicted a score of 0 for each WSI.

Figure 7: Baseline Model. WSI is converted into tiles of patches using Blue
Ratio Selection. Once patches are concatenated, it is passed into EfficientNet
for the classification.

Before using the proposed approach, we trained the model using only a
traditional CNN, ResNet50 [40]. Concatenated tile pooling was used to train
the WSIs. The ResNet50 is trained using the concatenated 36 tiles that are
chosen from each WSI. On validation datase a kappa score of 0.764 was obtained
for this model. Next we tested the dataset with MIL based approach using
EfficientNetB0 [41] as CNN network for training. Kappa score increased to 0.79
using this method. In Fig. 7 we can see the model for this implementation.
From any WSI, 36 patches are selected and bagged together and this bag is
passed as a single image for training. These patches are selected using the
blue ratio(Br) selection given by equation 6. The R,G,B in (6) represent the
Red, Green and Blue channels in the original image. The blue ratio is widely
used in selecting the useful part in the WSI [42].

$Br=\frac{100\times B}{1+R+G}\times\frac{256}{1+R+G+B}$ (6)

The transfer learning based model using EfficientNet was further evaluated
using ensemble method. The model was trained using both EfficientNetB0 and
EfficientNetB4[41]. These models were then ensembled together and the new
kappa score was improved to 0.87. Attention-based MIL based on the model in
[43] was used to compare with the proposed model. The kappa score for
attention-based MIL with this dataset was0.883. The performance of the model
when the features of the graph were extracted with self-supervised model
versus transfer learning through ResNet50 have been further compared. Initial
tests on the proposed graph-based technique were conducted without the use of
any self-supervised learning. ResNet50 was used to extract the features from
the patches for GCN. Each patch was passed through ResNet trained by ImageNet
[44] and the features were extracted. These features were then used as nodes
in the GCN training of the proposed method. The GCN model with features for
nodes extracted from the ResNet achieved a kappa score of 0.785.

Then, the features for patches were extracted using the model trained in self-
supervised learning. For the proposed model we extracted the feature size of
248 and 2048 from the pre-trained self-supervised model. Those features were
extracted from the different layers in the encoder of the self-supervised
model.

The method suggested in this work was assessed using four-fold cross
validation. Since the two graphs for each WSIs represent different node
feature sizes (248 and 2048 features for each node in the graph), two GCN
networks were trained. The kappa score for the proposed model with nodes
having 248 features was 0.871. The GCN model with 2048 features obtained a
kappa score of the 0.891. Next, the goal was to evaluate the performance when
these two models were ensembled. The kappa value of 0.899 was reached by
ensembling the two models. When compared to the simple tile-based technique,
this presents a significant improvement. The results of numerical experiments
are summarised in Table II.

TABLE II: Comparison of Kappa Score for Prostate Cancer dataset. The proposed method is compared with existing MIL-based and attention-based approaches. The proposed GCN-based algorithm has been tested with features extracted from ResNet and the proposed self-supervised approach. Method | PANDA Dataset
---|---
ResNet50[40] | 0.764
MIL with Efficinet Net [45] | 0.79
MIL with Ensembled Efficinet Net | 0.87
Attention based MIL [43] | 0.883
GCN with features from ResNet | 0.785
GCN with 248 Features for each Node (Proposed) | 0.871
GCN with 2048 Features for each Node (Proposed) | 0.891
GCN with Ensembled Model(Proposed) | 0.899

The algorithm was further tested using a dataset from TCGA. The WSI from the
TCGA were kidney resections which consisted of larger resolution scale
compared to the prostate biopsies. The WSIs were converted to graphs with
20$\times$ resolution. All of the overall algorithm steps were repeated for
this dataset as well.

Using kappa score, the performance of different models for Kidney cancer
dataset, is compared in Table III. Similar to prostate dataset, initially the
dataset was modeled using ResNet50. The kappa score of 0.758 was achieved.
This dataset was further evaluated using MIL with EfficientNet. The blue ratio
selection of patches for MIL was used for this dataset and a kappa score of
0.783 was obtained. Similar to the first experiment, multiple MIL-based
methods were ensembled to achieve the kappa score of 0.868. The kappa score
for this data set when tested on attention based MIL was 0.896. Then, the
proposed graph-based methods were evaluated on this dataset. For the GCN model
with ResNet50 used as feature extractor a kappa score of 0.792 was obtained.
The kappa score was improved to 0.887 when self-supervised model was used as
feature extractor with 248 features for each node in GCN. The score improved
to 0.924 with 2048 features for each node. These two models were ensembled to
obtain a score of 0.939. Overall results demonstrate that the proposed self-
supervised methods with GCN show a better performance compared to other
existing approaches.

TABLE III: Comparison of Kappa Score for different method applied to Kidney Cancer dataset Method | Kidney Dataset
---|---
ResNet50 [40] | 0.758
MIL with Efficinet Net [45] | 0.783
MIL with Ensembled Efficinet Net | 0.868
Attention based MIL [43] | 0.896
GCN with features from ResNet | 0.792
GCN with 248 Features for each Node (Proposed) | 0.887
GCN with 2048 Features for each Node (Proposed) | 0.924
GCN with Ensembled Model(Proposed) | 0.939

##  VI Discussion

In this work, GNN-based method that uses self-supervised model to extract
features of the nodes has been developed. The validity of the proposed model
was checked by the utilization of two distinct cancer datasets. To be more
explicit, the performance of the suggested model is assessed by utilizing the
WSIs that were obtained from the biopsies of the prostate as well as the
resections of the kidney. Two different models of the GCN were developed, one
of which is based on the size of the features for each node. The first GCN
model was trained using the WSI graph, which had a feature size of 248 for
each node in the graph. The feature size of the node in the graph for the
second GCN network that was employed in the training of the WSI graph was
2048. After each model had been trained independently, they were brought
together to form an ensemble. The proposed model obtained a kappa score of
0.899 for the grading of prostate cancer and 0.939 for the grading of sub-type
RCC in the diagnosis of kidney cancer.

The absence of data annotation is a significant obstacle for those working in
the medical area, in particular with WSI, due to the fact that it is a
laborious task for the pathologist to provide annotation in detail. We tackled
this issue by extracting features from patches without any annotation using
self-supervised learning. Additionally, the dimensionality of WSI presents
another challenge. The entire WSI cannot be trained because of its enormous
dimension. The training of the WSI using GCN can be accomplished in its
entirety by first subdividing the WSI into smaller patches and then
representing each patch as a node in the graph.

We also compare our model with other traditional models that are commonly used
for the training of the WSI. First, we evaluated an MIL-based method that uses
a certain number of patches selected based on certain rules such as blue ratio
selection. Applying this approach has disadvantages as it cannot capture all
parts of the WSI and only a fixed number of patches are selected to train
using CNN. The grading of the cancer might be different if a single patch of
cancerous tissue is missed. This problem is solved by using the graph data
structure to represent the WSI. Another advantage of using GCN is that it
takes into account the context of the tissues in WSI. Experiments show that
the proposed method outperforms MIL-based approaches in terms of performance.

Using self-supervised learning to extract features for the patches leads to a
considerable improvement in the kappa score. According to the findings from
this study, the GCN that was trained using features obtained through self-
supervised learning performed significantly better than the GCN that was
trained using features derived from the ResNet50. This provides more evidence
that, when using self-supervised learning, there is no requirement to manually
increase the amount of annotated data. This framework is well-motivated for
learning from WSIs and is broad enough to address the issue of insufficient
annotation for other types of medical images.

##  VII Conclusion

The work that is being presented here aimed to achieve the goal of being able
to represent any WSI of arbitrary size and learn from them without having to
make substantial use of the annotations. The use of a self-supervised learning
method in conjunction with a GNN allows for the achievement of these goals.

In this work, we suggested a two-stage model for the classification of cancer
using WSIs. The approach would consist of a self-supervised model and a GCN.
In order to depict WSIs as a graph, it is divided up into smaller patches.
These patches are first trained in self-supervised models. As node features
for the WSI graph, the self-supervised model’s learnt features for the patches
were applied. The reconstructed graph along with features is trained with GCN.
The context of each cell and its surroundings were then included into this
graph by GCN training in order to grade and diagnose cancer. Without further
pathologist annotation, our method enables learning of the features from the
patches. Additionally, the usage of GCN makes it possible to learn WSIs in
their entirety.

## Acknowledgment

The training of models in this work were made possible by Raj High Performance
at Marquette University.

The results published here are in part based upon data generated by the TCGA
Research Network: https://www.cancer.gov/tcga.

## References

  * [1] M. N. Gurcan, L. E. Boucheron, A. Can, A. Madabhushi, N. M. Rajpoot, and B. Yener, “Histopathological image analysis: A review,” _IEEE Reviews in Biomedical Engineering_ , vol. 2, pp. 147–171, 2009.
  * [2] R. L. Siegel, K. D. Miller, H. E. Fuchas, and A. Jemal, “Cancer statistics, 2021,” _CA: A Cancer Journal for Clinicians_ , pp. 7–33, 2021.
  * [3] B. Shuch, A. Amin, A. J. Armstrong, J. N. Eble, V. Ficarra, A. Lopez-Beltran, G. Martignoni, B. I. Rini, and A. Kutikov, “Understanding pathologic variants of renal cell carcinoma: Distilling therapeutic opportunities from biologic complexity,” _European Urology_ , vol. 67, no. 1, pp. 85–97, 2015\.
  * [4] S. Tabibu, P. Vinod, and C. Jawahar, “Pan-renal cell carcinoma classification and survival prediction from histopathology images using deep learning,” _Scientific Reports 9_ , 2019.
  * [5] H. Chen, L. Wu, Q. Dou, J. Qin, S. Li, J. Cheng, D. Ni, and P. Heng, “Ultrasound standard plane detection using a composite neural network framework,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 6, pp. 1576–1586, 2017.
  * [6] X. Yang, L. Yu, L. Wu, Y. Wang, D. Ni, J. Qin, and P. Heng, “Fine-grained recurrent neural networks for automatic prostate segmentation in ultrasound images,” _AAAI Conference on Artificial Intelligence_ , p. 1633–1639, 2017\.
  * [7] H. Chen, C. Shen, J. Qin, D. Ni, L. Shi, J. C. Y. Cheng, and P. Heng, “Automatic localization and identification of vertebrae in spine ct via a joint learning model with deep neural networks,” _Medical Image Computing and Computer-Assisted Intervention (MICCAI)_ , pp. 515–522, 2015.
  * [8] D. C. Cireşan, A. Giusti, L. M. Gambardella, and J. Schmidhuber, “Mitosis detection in breast cancer histology images with deep neural networks,” _Medical Image Computing and Computer-Assisted Intervention (MICCAI)_ , pp. 411–418, 2013.
  * [9] A. Menegola, M. Fornaciali, R. Pires, F. V. Bittencourt, S. Avila, and E. Valle, “Knowledge transfer for melanoma screening with deep learning,” in _2017 IEEE 14th International Symposium on Biomedical Imaging (ISBI 2017)_ , 2017, pp. 297–300.
  * [10] M. Graziani, V. Andrearczyk, and H. Müller, “Visualizing and interpreting feature reuse of pretrained cnns for histopathology,” 08 2019.
  * [11] M. Heker and H. Greenspan, “Joint liver lesion segmentation and classification via transfer learning,” 2020.
  * [12] I. Misra and L. van der Maaten, “Self-supervised learning of pretext-invariant representations,” _Computer Vision and Pattern Recognition (CVPR)_ , pp. 6706–6716, June 2020.
  * [13] S. Azizi, B. Mustafa, F. Ryan, Z. Beaver, J. Freyberg, J. Deaton, A. Loh, A. Karthikesalingam, S. Kornblith, T. Chen, V. Natarajan, and M. Norouzi, “Big self-supervised models advance medical image classification,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , October 2021, pp. 3478–3488.
  * [14] A. Taleb, W. Loetzsch, N. Danz, J. Severin, T. Gaertner, B. Bergner, and C. Lippert, “3d self-supervised methods for medical imaging,” in _Advances in Neural Information Processing Systems_ , H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 18 158–18 172.
  * [15] T. G. Dietterich, R. H. Lathrop, and T. Lozano-Pérez, “Solving the multiple instance problem with axis-parallel rectangles,” _Artificial Intelligence_ , vol. 89, no. 1, pp. 31–71, 1997.
  * [16] C. Mercan, S. Aksoy, E. Mercan, L. G. Shapiro, D. L. Weaver, and J. G. Elmore, “Multi-instance multi-label learning for multi-class classification of whole slide breast histopathology images,” _IEEE Transactions on Medical Imaging_ , vol. 37, no. 1, pp. 316–325, 2018.
  * [17] G. Ampanella, M. Hanna, Geneslaw, A. Miraflor, W. Krauss, V. Silva, K. Busam, E. Brogi, V. Reuter, D. Klimstra, and T. Fuchs, “Clinical-grade computational pathology using weakly supervised deep learning on whole slide images.” _Nature Medicine_ , 2019.
  * [18] M. Lu, R. Chen, J. Wang, D. Dillon, and F. Mahmood, “Semi-supervised histology classification using deep multiple instance learning and contrastive predictive coding,” _Advances in Neural Information Processing Systems (NeurIPS) Workshop in Machine Learning for Health_ , 2019.
  * [19] J. Melendez, B. Ginneken, P. Maduskar, R. Philipsen, H. Ayles, and C. Sanchez, “On combining multiple-instance learning and active learning for computer-aided detection of tuberculosis,” _IEEE Transactions on Medical Imaging_ , vol. 35, pp. 1–1, 12 2015.
  * [20] G. Quellec, M. Lamard, M. Cozic, G. Coatrieux, and G. Cazuguel, “Multiple-instance learning for anomaly detection in digital mammography,” _IEEE Transactions on Medical Imaging_ , vol. 35, no. 7, pp. 1604–1614, 2016\.
  * [21] J. Li, W. Li, A. Sisk, H. Ye, W. D. Wallace, W. Speier, and C. W. Arnold, “A multi-resolution model for histopathology image classification and localization with multiple instance learning,” _Computers in Biology and Medicine_ , vol. 131, p. 104253, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0010482521000470
  * [22] H. Abdeltawab, F. Khalifa, M. Ghazal, L. Cheng, D. Gondim, and A. El-Baz, “A pyramidal deep learning pipeline for kidney whole-slide histology images classification,” _Scientific Reports_ , vol. 11, p. 20189, 10 2021.
  * [23] D. Ahmedt-Aristizabal, M. A. Armin, S. Denman, C. Fookes, and L. Petersson, “A survey on graph-based deep learning for computational histopathology,” _Computerized Medical Imaging and Graphics_ , vol. 95, p. 102027, 2022.
  * [24] Y. Zhao, F. Yang, Y. Fang, H. Liu, N. Zhou, J. Zhang, J. Sun, S. Yang, B. Menze, X. Fan, and J. Yao, “Predicting lymph node metastasis using histopathological images based on multiple instance learning with deep graph convolution,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * [25] M. Adnan, S. Kalra, and H. R. Tizhoosh, “Representation learning of histopathology images using graph neural networks,” _IEEE Conference on Computer Vision and Pattern Recognition(CVPR)_ , 2020.
  * [26] R. J. Chen, M. Y. Lu, M. Shaban, C. Chen, T. Y. Chen, D. F. Williamson, and F. Mahmood, “Whole slide images are 2d point clouds: Context-aware survival prediction using patch-based graph convolutional networks,” in _Medical Image Computing and Computer Assisted Intervention – MICCAI 2021_. Springer International Publishing, 2021, pp. 339–349.
  * [27] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” _Medical Image Computing and Computer-Assisted Intervention (MICCAI)_ , pp. 234–241, 2015.
  * [28] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” _Computer Vision and Pattern Recognition (CVPR)_ , pp. 9726–9735, 2020.
  * [29] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” _Proceedings of the 37th International Conference on Machine Learning_ , vol. 119, pp. 1597–1607, 13–18 Jul 2020.
  * [30] X. Chen*, S. Xie*, and K. He, “An empirical study of training self-supervised vision transformers,” _arXiv preprint arXiv:2104.02057_ , 2021.
  * [31] A.Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _arXiv preprint_ , vol. abs/1807.03748, 2018. [Online]. Available: http://arxiv.org/abs/1807.03748
  * [32] M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” _International Conference on Computer Vision Theory and Applications_ , pp. 331–340, 2009.
  * [33] W. L. Hamilton, “Graph representation learning,” _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , vol. 14, no. 3, pp. 1–159.
  * [34] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. B., T. H., A. A., and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” _Advances in Neural Information Processing Systems_ , vol. 28, 2015.
  * [35] “Prostate cancer grade assessment (panda) challenge,” https://www.kaggle.com/c/prostate-cancer-grade-assessment, 2021. [Online]. Available: https://www.kaggle.com/c/prostate-cancer-grade-assessment
  * [36] O. Akin, P. Heller, M. Jarsosz, B. Kirk, and J. Filippni, “Radiology data from the cancer genome atlas kidney renal clear cell carcinoma [tcga-kirc] collection. the cancer imaging archive.” 2016. [Online]. Available: http://doi.org/10.7937/K9/TCIA.2016.V6PBVTDR
  * [37] M. Linehan, R. Gautam, S. Kirk, Y. Lee, C. Roche, E. Bonaccio, and R. Jarosz, “Radiology data from the cancer genome atlas cervical kidney renal papillary cell carcinoma [kirp] collection. the cancer imaging archive.” 2016. [Online]. Available: http://doi.org/10.7937/K9/TCIA.2016.ACWOGBEF
  * [38] M. Linehan, R. Gautam, C. Sadow, and S. Levine, “Radiology data from the cancer genome atlas kidney chromophobe [tcga-kich] collection. the cancer imaging archive.” 2016. [Online]. Available: http://doi.org/10.7937/K9/TCIA.2016.YU3RBCZN
  * [39] J. Cohen, “Weighted kappa: Nominal scale agreement with provision for scaled disagreement or partial credit.” _Psychological Bulletin 70 (4)_ , pp. 213–220, 1968.
  * [40] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [41] M. Tan and Q. Le, “EfficientNet: Rethinking model scaling for convolutional neural networks,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 6105–6114.
  * [42] O. Jimenez-del Toro, M. Atzori, M. Andersson, K. Euren, M. Hedlund, P. Rönnquist, and H. Müller, “Convolutional neural networks for an automatic classification of prostate tissue slides with high-grade gleason score,” 03 2017.
  * [43] J. Yao, X. Zhu, J. Jonnagaddala, N. Hawkins, and J. Huang, “Whole slide images based cancer survival prediction using attention guided deep multiple instance learning networks,” _Medical Image Analysis_ , vol. 65, p. 101789, 2020.
  * [44] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 2009, pp. 248–255.
  * [45] X. Wang, Y. Yan, P. Tang, X. Bai, and W. Liu, “Revisiting multiple instance neural networks,” _Pattern Recognition_ , vol. 74, p. 15–24, Feb 2018.