1 of 85

Tracking with Graph �Neural Networks

DANIEL MURNANE�BERKELEY LAB, CERN

1

Part 1: Fundamentals

HIGHRR LECTURE WEEK, HEIDELBERG UNIVERSITY

SEPTEMBER 13, 2023

HighRR Lecture Week - Heidelberg University - September 13, 2023

2 of 85

OVERVIEW

  • The importance of tracking in the LHC discovery pipeline
  • How have we done tracking in the past
  • Tracking with graphs
  • Overview of graphs and GNNs
  • Construction of graphs
  • GNN4ITk project and pipeline

2

  • ATLAS ITk data
  • Graph construction in ITk
  • The Interaction Network in GNN4ITk
  • Graph segmentation techniques
  • Track building in GNN4ITk
  • Measuring tracking performance
  • Track fitting

HighRR Lecture Week - Heidelberg University - September 13, 2023

3 of 85

WARNING: BIAS AHEAD

  • I chair the GNN4ITk project in the ATLAS experiment
  • I will have a bias towards tracking in ATLAS
  • I will also have a bias towards the GNN4ITk “solution” to the ATLAS tracking problem
  • However: This approach is the de facto standard way to use GNNs for tracking, since it was first proposed by the HepTrkx project in arxiv:1810.06111

3

HighRR Lecture Week - Heidelberg University - September 13, 2023

4 of 85

HIGH LUMINOSITY TRACK RECONSTRUCTION

4

HighRR Lecture Week - Heidelberg University - September 13, 2023

5 of 85

DATA SCIENCE IN THE DISCOVERY PIPELINE

Simulation

Reconstruction

Analysis

Matrix-element Calculation

Parton-shower / Hadronization

Detector�Simulation

Digitization

Topoclusters�& Spacepoints

Track Finding�& Fitting

Jet Tagging�& Vertexing

Particle ID�& Particle Flow

Calibration

Likelihood Fitting

Unfolding

Statistical Techniques, Bayesian Inference

Numerical �Integration

Markov Chain�Monte Carlo

Topological clustering

Kalman Filtering�& Fitting

Conformal Fits�& Hough Transform

HighRR Lecture Week - Heidelberg University - September 13, 2023

6 of 85

ML TODAY & TOMORROW IN THE DISCOVERY PIPELINE

Simulation

Reconstruction

Analysis

Matrix-element Calculation

Parton-shower / Hadronization

Detector�Simulation

Digitization

Topoclusters�& Spacepoints

Track Finding�& Fitting

Jet Tagging�& Vertexing

Particle ID�& Particle Flow

Calibration

Likelihood Fitting

Unfolding

Omnifold and Likelihood-free Inference

Generative Models:�GANs, VAEs, Normalizing Flows and Diffusion

Metric Learning, Object Condensation

Deep Full Event Reconstruction

CNNs, Graph Neural Networks & Transformers

Autoencoders�& Anomaly Detection

Symmetric ML�& Equivariance

HighRR Lecture Week - Heidelberg University - September 13, 2023

7 of 85

TASKS IN AN HL-LHC DETECTOR

  • In order to perform the analysis that leads to discovery (e.g. of dark matter, extra dimensions, SUSY, …), need to make sense of the detector read-out
  • There are many tasks required to reconstruct the physics event behind the read-out

7

Vertex Reconstruction

Jet Tagging

Pile-up Removal

Missing Energy Reconstruction

HighRR Lecture Week - Heidelberg University - September 13, 2023

8 of 85

TASKS IN AN HL-LHC DETECTOR

  • In order to perform the analysis that leads to discovery (e.g. of dark matter, extra dimensions, SUSY, …), need to make sense of the detector read-out
  • There are many tasks required to reconstruct the physics event behind the read-out

8

Vertex Reconstruction

Jet Tagging

Pile-up Removal

Missing Energy Reconstruction

These all require accurate �track reconstruction

HighRR Lecture Week - Heidelberg University - September 13, 2023

9 of 85

WHAT IS TRACK RECONSTRUCTION

9

  • Protons collide in center of detector, “shattering” into thousands of particles
  • The charged particles travel in curved tracks through detector’s magnetic field (Lorentz force)
  • A track is defined by the hits left as energy deposits in the detector material, when the particle interacts with material
  • The goal of track reconstruction:

Given set of hits from particles in a detector, assign label(s) to each hit.

Perfect classification: All hits from a particle (and only those hits) share the same label

HighRR Lecture Week - Heidelberg University - September 13, 2023

10 of 85

THE IMPORTANCE OF TRACKING

  • Finding and fitting tracks accurately is essential for most downstream tasks in ATLAS and many other experiments
  • Classic example is b-tagging (which itself is necessary for Higgs searches, top physics, and BSM searches)
  • The current ATLAS GNN tagger takes 2 overall jet features, and 21 track features

10

ATL-PHYS-SLIDE-2023-048

HighRR Lecture Week - Heidelberg University - September 13, 2023

11 of 85

THE COST OF TRACKING

  • Over half the current ATLAS computing budget is spent on generating and reconstructing simulated data
  • In Run 2 in 2018, a typical event (in data) required 1693 HS06-seconds, of which 67% was spent on tracking
  • TL;DR: Tracking is an expensive piece of reconstruction, and is therefore an expensive piece of any experiment that has a tracking subdetector

11

https://cds.cern.ch/record/2729668/files/LHCC-G-178.pdf

HighRR Lecture Week - Heidelberg University - September 13, 2023

12 of 85

COMPUTE SCALING FOR HIGH LUMINOSITY

12

ATLAS Computing Requirements Over Time

In other words…

Computing power

Time, Energy, Number of Collisions

Predicted

capacity

Traditional

methods

(scale quadratically)

HL-LHC, 14 TeV

2027

3 billion collision/second

HighRR Lecture Week - Heidelberg University - September 13, 2023

13 of 85

WHY HIGH LUMINOSITY PHYSICS?

  •  

13

HighRR Lecture Week - Heidelberg University - September 13, 2023

14 of 85

TRACKING 101

14

HighRR Lecture Week - Heidelberg University - September 13, 2023

15 of 85

THE GOAL OF TRACKING

The following slides have material borrowed from Heather Gray’s excellent talk @ Zurich: https://indico.cern.ch/event/504284/

15

HighRR Lecture Week - Heidelberg University - September 13, 2023

16 of 85

WITHOUT A DETECTOR...

Particles are well-described by helices in a magnetic field

But once they are in a detector…

16

HighRR Lecture Week - Heidelberg University - September 13, 2023

17 of 85

TYPES OF INTERACTION

17

HighRR Lecture Week - Heidelberg University - September 13, 2023

18 of 85

REPRESENTING A HELIX

18

HighRR Lecture Week - Heidelberg University - September 13, 2023

19 of 85

TRACKING TERMINOLOGY

  • Tracking typically happens in silicon: channels lie on flat-ish modules
  • Like a set of millions of cameras, arranged in layers
  • Particles curve out, depositing energy in “clusters” or “spacepoints” or “hits”
  • Sequence of hits is a “track”
  • A prediction of a track is a “track candidate”

19

HighRR Lecture Week - Heidelberg University - September 13, 2023

20 of 85

TRADITIONAL TECHNIQUES FOR TRACKING

20

HighRR Lecture Week - Heidelberg University - September 13, 2023

21 of 85

KALMAN FILTER: TRACKING AS NAVIGATION

  • A recurrent sequence of predictions and corrections according to measurement

21

https://www.kalmanfilter.net/multiSummary.html

HighRR Lecture Week - Heidelberg University - September 13, 2023

22 of 85

KALMAN FILTER: TRACKING AS NAVIGATION

  • The optimal algorithm for any linear system with independent measurements with Gaussian uncertainty
  • Self-driving cars are the perfect use-case of this: many independent sensor measurements, with a planned trajectory that is updated in time
  • Tracking looks a lot like driving a car…

22

HighRR Lecture Week - Heidelberg University - September 13, 2023

23 of 85

KALMAN FILTER: TRACKING AS NAVIGATION

  • Begin with a seed of 3 or 4 spacepoints
  • Produce a prediction of the helix parameters, and the covariance matrix
    • Look at where this helix would intersect with the next layer(s)
    • Look for a nearby hit to this prediction
    • Use the most likely hit to update the model
  • Repeat!
  • We can also hypothesise a “hole” (missing hit) to handle a skipped layer

23

https://cds.cern.ch/record/1281363/files/ATLAS-CONF-2010-072.pdf

HighRR Lecture Week - Heidelberg University - September 13, 2023

24 of 85

COMBINATORIAL KALMAN FILTER

  •  

24

https://www.researchgate.net/publication/344039130_Pattern_Recognition_and_Reconstruction

HighRR Lecture Week - Heidelberg University - September 13, 2023

25 of 85

TRACKING AS GRAPH SEGMENTATION

25

HighRR Lecture Week - Heidelberg University - September 13, 2023

26 of 85

COMPUTE SCALING FOR HIGH LUMINOSITY

26

ATLAS Computing Requirements Over Time

ML Image Classification Efficiency Over Time

62 million�parameters

5 million�parameters

HighRR Lecture Week - Heidelberg University - September 13, 2023

27 of 85

TEASER: GRAPH-BASED PIPELINE FOR TRACK RECONSTRUCTION

  • Using graph-based ML, can perform track reconstruction on High Luminosity detector events
  • Comparable efficiency and fake rates to traditional algorithms
  • Scaling that is approximately linear in event size (on open-source TrackML dataset)

27

HighRR Lecture Week - Heidelberg University - September 13, 2023

28 of 85

HOW SHOULD WE REPRESENT PARTICLE COLLISIONS?

Assuming we want to use deep learning, how can we represent a particle collision?

28

Image?

Sequence?

Set/Point Cloud?

For event collision as point cloud, with relationships between points, this is a graph.

HighRR Lecture Week - Heidelberg University - September 13, 2023

29 of 85

A COLLECTION OF NODES

29

NODE

WHAT IS A GRAPH?

HighRR Lecture Week - Heidelberg University - September 13, 2023

30 of 85

AND EDGES

30

EDGE

WHAT IS A GRAPH?

HighRR Lecture Week - Heidelberg University - September 13, 2023

31 of 85

NODES + EDGES = DOUBLETS

31

DOUBLET

WHAT IS A GRAPH?

HighRR Lecture Week - Heidelberg University - September 13, 2023

32 of 85

NODES CAN HAVE FEATURES

32

NODE FEATURE

e.g. “West Oakland”

WHAT IS A GRAPH?

HighRR Lecture Week - Heidelberg University - September 13, 2023

33 of 85

EDGES CAN HAVE FEATURES

33

EDGE FEATURE

e.g. “Under Maintenance

– Single Track”

WHAT IS A GRAPH?

HighRR Lecture Week - Heidelberg University - September 13, 2023

34 of 85

THE WHOLE GRAPH CAN HAVE FEATURES

34

GRAPH FEATURE

e.g. “Sunday Timetable”

HighRR Lecture Week - Heidelberg University - September 13, 2023

35 of 85

GRAPHS ARE A NATURAL WAY TO REPRESENT TRACKS

35

Given hits on �layers of a detector

x direction

y direction

HighRR Lecture Week - Heidelberg University - September 13, 2023

36 of 85

GRAPHS ARE A NATURAL WAY TO REPRESENT TRACKS

36

Connect the

hits in some way

x direction

y direction

HighRR Lecture Week - Heidelberg University - September 13, 2023

37 of 85

GRAPHS ARE A NATURAL WAY TO REPRESENT TRACKS

37

  • Tracks should be found�amongst the connected�nodes.
  • Note the trade-off: Rather than needing to classify or cluster nodes with many labels, we only need binary classification of edges
  • However, introduce the extra step of building tracks from classified edges�

x direction

y direction

HighRR Lecture Week - Heidelberg University - September 13, 2023

38 of 85

INTRO TO GRAPH NEURAL NETWORKS

38

HighRR Lecture Week - Heidelberg University - September 13, 2023

39 of 85

GRAPH NEURAL NETWORK APPLICATIONS

39

Travelling Salesman Problem

Knowledge Graph Comprehension

Image �Comprehension

Molecular �Chemistry

Protein�Comprehension

HighRR Lecture Week - Heidelberg University - September 13, 2023

40 of 85

GRAPH NEURAL NETWORK PROCEDURE

40

Node features

Encoder

Node channels

Message passing

Node Aggregation

Messages

Node channels

Task output layer

Node channels

HighRR Lecture Week - Heidelberg University - September 13, 2023

41 of 85

STEP 1: MESSAGE PASSING MECHANISM

  •  

41

0

2

1

3

4

Figure inspired by Koshi et. al.

0

2

1

3

4

Input channels

Encoded channels

HighRR Lecture Week - Heidelberg University - September 13, 2023

42 of 85

STEP 2: AGGREGATION

At each node:

Sum all messages

Note: Called isotropic �message passing. �Introduced as “Graph Convolution Network”

42

Figure inspired by Koshi et. al.

0

2

1

3

4

0

2

1

3

4

+

+

=

Encoded channels

Input channels

+

 

HighRR Lecture Week - Heidelberg University - September 13, 2023

43 of 85

EDGE CHANNELS

  •  

43

0

2

1

3

4

0

2

1

3

4

Encoded channels

Pre-encoded channels

HighRR Lecture Week - Heidelberg University - September 13, 2023

44 of 85

EDGE CHANNELS

  • Can access contextual relationships

44

0

2

1

3

4

0

2

1

3

4

Encoded channels

Pre-encoded channels

Paris

Hilton

France

Texas

Socialite

Small town

Capital

HighRR Lecture Week - Heidelberg University - September 13, 2023

45 of 85

THE LANDSCAPE OF GNNS

45

GNNs

CNNs

RNNs

Cellular

Automata

Transformers

Grid �adjacency

MLP + 1-pixel�Equivalency

Fully-�Connected

Linearly�Connected

= reduces to

Graphical

Automata

MLP + 1-pixel�Equivalency

Grid adjacency

46 of 85

GNNS IN TRACKING

  • As mentioned in the introduction, the “HepTrkX” formulation of GNN tracking is the de facto standard
  • A workshop last year on GNN Tracking 🡪
  • Almost all contributions are affiliated with Exatrkx, or use a codebase forked from or motivated by the Exatrkx approach
  • A variety of experiments are applying this fully supervised, edge-classification pipeline

46

HighRR Lecture Week - Heidelberg University - September 13, 2023

47 of 85

GNNS IN TRACKING

  • As mentioned in the introduction, the “HepTrkX” formulation of GNN tracking is the de facto standard
  • A workshop last year on GNN Tracking 🡪
  • Almost all contributions are affiliated with Exatrkx, or use a codebase forked from or motivated by the Exatrkx approach
  • A variety of experiments are applying this fully supervised, edge-classification pipeline
  • Another promising approach is reinforcement learning, which may or may not use deep geometric learning (i.e. graph techniques)

47

Tobias Kortus , Ralf Keidel and Nicolas R. Gauger, 2022

Våge, Liv CTD Proceedings 2022

HighRR Lecture Week - Heidelberg University - September 13, 2023

48 of 85

GNNS ELSEWHERE IN PARTICLE PHYSICS

  • Very large and active field of study!
  • Comprehensive review of GNNs for Track Reconstruction - arXiv:2012.01249
  • White paper on progress and future of the field – arXiv:2203.12852

48

HighRR Lecture Week - Heidelberg University - September 13, 2023

49 of 85

THE TOPOLOGY PROBLEM

49

HighRR Lecture Week - Heidelberg University - September 13, 2023

50 of 85

TRACKING WITH GRAPHS VS. POINT CLOUD

  •  

50

https://arxiv.org/pdf/2012.09164.pdf

HighRR Lecture Week - Heidelberg University - September 13, 2023

51 of 85

TOPOLOGY FOR MESSAGE PASSING AND SEGMENTATION

  • In tracking, the graph structure (“topology”) has two purposes:
    1. To pass hidden features (“messages”) from hit to hit, to minimise the loss, presumably solving an N-step combinatorial problem across tracklets
    2. As “possible connections” between hits, therefore the edges need to be classified as true of fake
  • No inherent reason the two structures have to be the same. E.g. could pass messages totally randomly, but still try to classify the edges between likely hits
  • For simplicity, we create a single graph that serves both purposes: Edges transmit messages, and they are the target of the classification model

51

Message 0-1

Message 0-2

0

1

2

Probability 0-1

Probability 0-2

0

1

2

Topology for message passing

Topology for edge classification

HighRR Lecture Week - Heidelberg University - September 13, 2023

52 of 85

THREE WAYS TO BUILD A GRAPH

52

https://arxiv.org/abs/2103.16701

MODULE MAP

  1. Build a module-to-module map from data
  2. Apply some hard geometric cuts for each module-to-module possible connection

r

Embed into learned �latent space

Connect all spacepoints�within radius r

All spacepoint pairs�joined into graph

METRIC LEARNING

GEOMETRIC HEURISTICS

  1. Consider all connections on sequential layers
  2. Apply some hard geometric cuts according to heuristic knowledge of particles of interest

HighRR Lecture Week - Heidelberg University - September 13, 2023

53 of 85

THE GNN4ITK PIPELINE

53

HighRR Lecture Week - Heidelberg University - September 13, 2023

54 of 85

WHO IS INVOLVED?

  • Two groups worked on the results in this presentation, and both first tested methods on TrackML, based on the GNN-based reconstruction introduced in arxiv:1810.06111 and arxiv:2003.11603
  • L2IT: Laboratoire des deux Infinis, institute based at the University of Toulouse, within the Institute of Nuclear Physics and Particle Physics
  • Exa.Trkx: A DoE Office of Science-funded collaboration of LBNL, Caltech, FNAL, SLAC and a collaboration of US institutions including Cincinnati, Princeton, Urbana-Champaign, Youngstown State, and others
  • Now, other groups have joined the effort, or are applying the R&D to particular applications, such as ATLAS trigger: Heidelberg University, Niels Bohr Institute, UC Irvine

54

HighRR Lecture Week - Heidelberg University - September 13, 2023

55 of 85

GRAPH REPRESENTATION OF AN EVENT

  • The goal of track reconstruction:

Given set of hits in a detector from particles, assign label(s) to each hit.

Perfect classification: All hits from a particle (and only those hits) share the same label

55

  • What does it mean to represent an event with a graph?
    • Treat each hit as a node
    • A node can have features (e.g. position, energy deposit, etc.)
    • Nodes can be connected by edges, that represent the possibility of belonging to the same track
  • Goal: Use ML and/or graph techniques to segment or cluster the nodes to match particle tracks
  • Proof-of-concept: TrackML community challenge dataset with simplified simulation

HighRR Lecture Week - Heidelberg University - September 13, 2023

56 of 85

PIPELINE OVERVIEW

  • Current pipeline of the L2IT-Exatrkx collaborative effort
  • Each stage offers multiple independent choices, depending on hardware and time constraints

56

1

2

3

Metric �Learning

Module�Map

or

Graph Neural�Network

Connected�Components

Connected�Components�+ Walkthrough

or

 

 

 

 

 

 

 

 

 

Graph�Construction

Edge�Classification

Graph�Segmentation

Hits

Graph

Edge Scores

Track Candidates

HighRR Lecture Week - Heidelberg University - September 13, 2023

57 of 85

DATASETS

  • Two datasets used to study this pipeline. For absolute clarity, when citing a result specific to one dataset, will place the badge of TrackML or ATLAS ITk on slide:

57

TrackML

ATLAS ITk

  • Mean number of spacepoints: 110k
  • Simplified simulation: No secondaries and optimistic charge information
  • Mean number of spacepoints: 310k
  • Full simulation

HighRR Lecture Week - Heidelberg University - September 13, 2023

58 of 85

ATLAS ITK GEOMETRY

  •  

58

Cluster

Spacepoint

Silicon

Track

 

 

 

 

 

 

 

Pixel is trivial: Each spacepoint maps to one cluster, which can map to many particles

Strip: Each spacepoint maps to two clusters – one on either side of strip, which can map to many particles

*Thanks Noemi Calace

0: Pixel barrel

1: Pixel endcap

2: Strip barrel

3: Strip endcap

ATLAS ITk

2

3

0

1

HighRR Lecture Week - Heidelberg University - September 13, 2023

59 of 85

ATLAS ITK GEOMETRY

  •  

59

Cluster

Spacepoint

Silicon

Track

Ghost spacepoint: Incorrectly constructed from �clusters left by different particles

Cluster A

Cluster B

Cluster C

Cluster D

 

 

 

 

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

60 of 85

60

Metric �Learning

Module�Map

or

Graph Construction

Hits

Graph

1

HighRR Lecture Week - Heidelberg University - September 13, 2023

61 of 85

EDGE TRUTH DEFINITIONS

61

All Edges

 

 

 

 

 

 

Target particle

Non-target particle

 

 

 

 

 

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

62 of 85

MODULE MAP - DOUBLETS

  • The idea: Build a map of detector modules, where a connection from module A �to module B means that at least one true track has passed sequentially through A to B
  • Step 1: Build all combinations of sequential doublets for an event, register an A-to-B entry if a doublet passes through. O(90k) events used to build these combinations
  • Step 2: For each A-to-B entry, also register/update the max and min values of a set of geometric observables. Apply these cuts when building the graph in inference

62

Metric �Learning

Module�Map

or

Graph Construction

Hits

Graph

1

 

Modules

 

 

 

 

 

 

HighRR Lecture Week - Heidelberg University - September 13, 2023

63 of 85

MODULE MAP – TRIPLETS

  • The idea: Build a map of detector modules, where a connection from module A �to module B to module C means that at least one true track has passed sequentially through A to B to C
  • Step 1: Build all combinations of sequential triplets for an event, register an A-to-B-to-C entry if a triplet passes through
  • Step 2: For each A-to-B-to-C entry, also register/update the max and min values of a set of geometric observables. Apply these cuts when building the graph in inference

63

Step 1

Step 2

Metric �Learning

Module�Map

or

Graph Construction

Hits

Graph

1

HighRR Lecture Week - Heidelberg University - September 13, 2023

64 of 85

METRIC LEARNING �INTUITION

  • Encode / embed input into N-dimensional space
  • Reward (low loss) matching pairs within unit distance
  • Punish (high loss) mismatching pairs within unit distance
  • Repeat for many pairs

64

MLP

MLP

Repulsive training

Source

Target

Source

Target

Attractive training

cat

cat

cat

dog

“Contrastive” hinge loss

 

 

 

 

 

 

HighRR Lecture Week - Heidelberg University - September 13, 2023

65 of 85

METRIC LEARNING

  •  

65

r

Embed into learned �latent space

Connect all space points�within radius r

All spacepoint pairs�joined into graph

Metric �Learning

Module�Map

or

Graph Construction

Hits

Graph

1

 

 

 

HighRR Lecture Week - Heidelberg University - September 13, 2023

66 of 85

METRIC LEARNING - FILTERING

  • Output graph of metric learning is impure: 0.2%
  • Can pass edges through a simple MLP filter to filter out the easy fakes
  • Improves purity to 2%, so graph can be trained entirely on a single GPU

66

Metric �Learning

Module�Map

or

Graph Construction

Hits

Graph

1

512

Radius

Graph

512

512

512

512

8

 

cell

Hinge Loss

512

512

512

Cross Entropy Loss

Metric Learning

Filtering

GNN

norm

norm

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

67 of 85

GRAPH CONSTRUCTION RESULTS

67

 

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

68 of 85

68

Graph

2

Graph Neural�Network

 

 

 

 

 

 

 

 

Edge Labeling

Edge Scores

HighRR Lecture Week - Heidelberg University - September 13, 2023

69 of 85

EDGE CLASSIFICATION WITH�GRAPH NEURAL NETWORK

  1. Node features (spatial position) are encoded
  2. Encoded features are concatenated and encoded to create edge features
  3. Edge features are aggregated around nodes to create next round of encoded node features (i.e. message passing)
  4. Each iteration of message passing improves discrimination power

69

 

 

 

 

 

 

 

 

 

 

INTERACTION

NETWORK

HighRR Lecture Week - Heidelberg University - September 13, 2023

70 of 85

LOSS FUNCTION DESIGN

  •  

70

Graph

2

Graph Neural�Network

 

 

 

 

 

 

 

 

Edge Labeling

Edge Scores

HighRR Lecture Week - Heidelberg University - September 13, 2023

71 of 85

GNN EDGE CLASSIFICATION RESULTS

  • Edge cut of 0.5 on output of GNN edge classifier

71

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

72 of 85

GNN EDGE CLASSIFICATION RESULTS

  •  

72

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

73 of 85

73

3

Connected�Components

Connected�Components�+ Walkthrough

or

Graph Segmentation

Edge Scores

Track Candidates

HighRR Lecture Week - Heidelberg University - September 13, 2023

74 of 85

GRAPH PARTITIONING 101

  • Graph: given a graph with expected “components” or “communities”, how can we partition into those likely components
  • Potentially a very (i.e. NP-hard) expensive step
  • Typical partitioning approaches try to cut the fewest edges, to produce the most densely connected communities
  • But this is not really aligned with track finding, since tracks ideally only have one incoming, one outgoing edge per node

74

3

Connected�Components

Connected�Components�+ Walkthrough

or

Graph Segmentation

Edge Scores

Track Candidates

HighRR Lecture Week - Heidelberg University - September 13, 2023

75 of 85

  • We now have labelled edges. Want to now label each node depending on connectivity.
  • Two distinct approaches: component-based segmentation, or path-based segmentation.

75

Component-based

Classified edges

Ignore cut edges

Label connected

components

Track #1

Track #2

1

1

1

2

2

2

E.g. connected components algorithm:

 

Path-based

E.g. walkthrough algorithm:

Classified edges,

Starting node

Choose high�score junctions

Remove a high-�scoring path

Track #1

1

1

1

 

1

2

2

3

3

3

Connected�Components

Connected�Components�+ Walkthrough

or

Graph Segmentation

Edge Scores

Track Candidates

TRACK CANDIDATES CONSTRUCTION

HighRR Lecture Week - Heidelberg University - September 13, 2023

76 of 85

  • We now have labelled edges. Want to now label each node depending on connectivity.
  • Two distinct approaches: component-based segmentation, or path-based segmentation.

76

Component-based

Classified edges

Ignore cut edges

Label connected

components

Track #1

Track #2

1

1

1

2

2

2

E.g. connected components algorithm:

 

Path-based

E.g. walkthrough algorithm:

Classified edges,

Starting node

Choose high�score junctions

Remove a high-�scoring path

Track #1

1

1

1

 

1

2

2

3

3

3

Connected�Components

Connected�Components�+ Walkthrough

or

Graph Segmentation

Edge Scores

Track Candidates

Both methods by construction�associate each hit with only one track

TRACK CANDIDATES CONSTRUCTION

HighRR Lecture Week - Heidelberg University - September 13, 2023

77 of 85

  • One can combine the good features of each approach:

77

1. Connected Components

2. Walkthrough, a.k.a “Wrangler”

Classified edges

Cut score < 0.2

Track #1

Track #2

1

2

2

3

4

 

 

Label simple

candidates

 

 

Track #3

Assign longest path�as candidate

3

Connected�Components

Connected�Components�+ Walkthrough

or

Graph Segmentation

Edge Scores

Track Candidates

3

TRACK CANDIDATES CONSTRUCTION

HighRR Lecture Week - Heidelberg University - September 13, 2023

78 of 85

FINDING & FITTING PERFORMANCE

78

HighRR Lecture Week - Heidelberg University - September 13, 2023

79 of 85

TRACK MATCHING DEFINITIONS

  •  

79

 

Particle 1

Particle 2

Candidate 1

HighRR Lecture Week - Heidelberg University - September 13, 2023

80 of 85

TRACK RECONSTRUCTION RESULTS

80

 

 

ATLAS ITk

HighRR Lecture Week - Heidelberg University - September 13, 2023

81 of 85

TRACK RECONSTRUCTION RESULTS

81

ATLAS ITk

Observe that the GNN track candidates have fewer hits than CKF. Will return to this!

HighRR Lecture Week - Heidelberg University - September 13, 2023

82 of 85

TRACK FITTING 101

  • Why do we fit?
  • Many downstream tasks need the momentum and “impact parameters”
  • Can use the fitted parameters to “tidy up” the track finding

82

HighRR Lecture Week - Heidelberg University - September 13, 2023

83 of 85

 

  • We can propose a shape of the track – a helix
  • We can then simply minimise the sum of the square of the residuals of the measurements to produce the set of five track parameters

83

  • This can be done very efficiently by:
  • Mapping to the conformal plane 🡪
  • Making the assumption that the impact parameters (the point of closest approach of the helix to the origin) is very small

HighRR Lecture Week - Heidelberg University - September 13, 2023

84 of 85

TRACK FITTING 101: FITTING WITH KALMAN FILTER

  • Recall that the Kalman Filter track finding produces a prediction of the helical parameters in order to find the next hit
  • We can thus use the same model to fit to a track
  • However, to get good performance: First run KF forwards to build the model, then run it back from out-to-in: called “smoothing”

84

http://physik.uibk.ac.at/hephy/theses/diss_as.pdf

HighRR Lecture Week - Heidelberg University - September 13, 2023

85 of 85

FITTING PERFORMANCE OF TRACK CANDIDATES

  • We see that the tracks found by the GNN are within 30% of the “quality” of the tracks found by the CKF
  • Quite promising, given that the CKF assumes helicity, while the GNN makes no such assumption

85

HighRR Lecture Week - Heidelberg University - September 13, 2023