Week 12.a
CS7670
11/21 2022
https://naizhengtan.github.io/22fall/
---


Motivation: understanding NN4Sys
  -- makes sense

  Approach: decision tree + hypergraph
     [is it really hypergraph?
      or simply bivariate mappings?]

  Q: what's the different between local and global systems?


* Decision tree:

  Q: Why they use decision trees?
     [read S3.1]
     Are these arguments convincing?

  Q: decision tree conversion method for local systems
    * WHY local systems? what is local systems?

    -- challenge: too many branches
    -- pruning branches
    -- differnet input-output pairs

  How it work?
    -- collecting traces from NNs
    -- training decision tree
        (using CART algorithm)
    -- resampling 
        (using [7] Verifiable Reinforcement Learning via Policy Extraction)
    -- pruning
        (using cost complexity pruning)

  Read S7: why not train a decision tree on the original dataset?


* Hypergraph:

  background: hypergraph
    -- vertices
    -- hyperedges

    [an example]

  app: RouteNet
    [Read S4.1, "case study: SDN routing optimization"]
    NN outputs: a routing path for a src-dst pair

   [RouteNet, Fig2]
    topology       ->
    traffic matrix -> [GNN] -> perf metrics
    routing scheme ->          (per-path delays, jitter)

    Abstract:
    "...In this paper we propose a novel Graph Neural Network (GNN) model
    able to understand the complex relationship between topology, routing
    and input traffic to produce accurate estimates of the
    per-source/destination pair mean delay and jitter."


  [write equation (4)--(8) on board]

  Q: what is:
      I?
      W?
      Y_I and Y_W?


  Another app: Decima (job scheduling)

    * recall decima

      -- inputs: job DAGs; nodes with attributes
                 three types of embeddings:
                  (1) per-node embeddings
                  (2) per-job embeddings
                  (3) global embedings

      -- ouputs:
          (1) a stage to schedule next
          (2) #executors to use


    * read "#4" in table 2

    * read appx B.3


  S4.1, "capability of hypergraph representation"
  hypergraph for global systems
    -- either input is a graph [okay]
       or mapping two vars     [WHY?]