Graph theory inspired anomaly detection at the LHC

Technical Summary: Graph Theory Inspired Anomaly Detection at the LHC

Problem Statement
The search for physics Beyond the Standard Model (BSM) at the Large Hadron Collider (LHC) faces a central challenge: designing model-independent anomaly detection algorithms capable of handling the high dimensionality of collider events. Traditional "top-down" searches targeting specific theoretical models risk missing signatures that do not align with those models. While unsupervised machine learning approaches, such as autoencoders, offer a model-agnostic alternative by learning to reconstruct background events and flagging high-reconstruction-loss events as anomalies, they often struggle with the complexity of jet data. Standard approaches utilizing fully connected graphs or dense representations can introduce redundancies and overfitting, particularly when the signal fraction is small. Furthermore, the choice between high-level observables and low-level particle information remains a critical tuning parameter. This work addresses the need for a physically motivated inductive bias that balances information content with geometric structure to improve anomaly detection performance.

Methodology
The authors develop a Graph Autoencoder (GAE) as an unsupervised, model-agnostic tool for anomaly detection, benchmarked against the LHC Olympics 2020 dataset. The methodology introduces two primary innovations in representing jet constituents as graphs:

1. Sparse Graph Constructions via Graph Rigidity: Instead of using fully connected graphs (which scale quadratically, $O(N^2)$), the authors construct sparse graphs where the number of edges scales linearly with the number of constituents ($N$). These constructions are motivated by graph rigidity theory in Euclidean space ($\mathbb{R}^2$):

   • Laman Graphs: Locally rigid graphs with $2N-3$ edges, constructed via Henneberg Type I operations. These ensure local rigidity but may admit multiple discrete realizations.
   • Unique Graphs: Globally rigid graphs that admit a unique embedding (up to isometries) in $\mathbb{R}^2$. The authors construct "unique-$k$" graphs by starting with a fully connected subgraph of the $k+1$ hardest particles and connecting each subsequent particle to its $k$ nearest neighbors in angular distance. For $k \geq 3$, these graphs satisfy Hendrickson's conditions for global rigidity.

2. Subjet Clustering as an Information Throttle: To control the complexity of the input, jet constituents are clustered into a fixed number of exclusive $k_T$ subjets. This allows for a smooth interpolation between low-level (hadron) and high-level (summary statistic) representations. The model inputs consist of the transverse momentum ($p_T$) of nodes and relative angular distances ($\theta_{ij}$) and kinematic variables ($k_{T,ij}, z_{ij}$) of edges, rather than absolute positions, to align with perturbative QCD observables.

The architecture employs a Graph Neural Network (GNN) based autoencoder. The encoder utilizes EdgeConv layers to process node and edge features, compressing the input into a 2-dimensional latent node representation (a "tight bottleneck"). The decoder consists of two branches: one reconstructing node features and another reconstructing edge features. The model is trained to minimize the Mean Squared Error (MSE) of both node and edge reconstructions on background-rich data.

Key Contributions

• Inductive Bias via Rigidity: The paper demonstrates that enforcing graph rigidity (specifically global rigidity via unique graphs) serves as an effective inductive bias, providing sufficient geometric constraints to fix particle positions without the redundancy of fully connected graphs.
• Optimal Information Level: The study identifies that anomaly detection performance peaks at an intermediate level of subjet clustering ($n_{\text{subjets}} \approx 30$), contrasting with jet classification tasks which often benefit from maximal low-level information.
• Superiority of Sparse Unique Graphs: The authors show that specific sparse graph constructions (unique-6) outperform fully connected graphs in anomaly detection tasks.
• Interpretability: By linking graph connectivity to the topological properties of the phase space, the work enhances the interpretability of machine learning tools for collider experiments.

Numerical Results
Using the LHC Olympics dataset (simulating a $Z' \to X Y$ resonance with $m_{Z'} = 3.5$ TeV), the authors evaluated performance using the Area Under the Curve (AUC) and the Significance Improvement Characteristic (SIC) curve.

• Graph Performance: The unique-6 graph construction achieved the best performance, yielding a maximum SIC of 2.94 and an AUC of 0.925 at $n_{\text{subjets}} = 30$. This outperformed fully connected graphs, Laman graphs, and other unique-$k$ variants.
• Sparsity vs. Topology: While increasing sparsity generally improved performance up to a point, the specific connectivity structure of unique graphs was found to be more critical than sparsity alone. "Modified Laman" graphs (which interpolate between Laman and fully connected by adding edges) did not replicate the performance peak of unique graphs, suggesting that the unique graph topology better captures the underlying phase space structure.
• Input Features: Models relying solely on absolute positional information or reconstructing full 3-momenta performed significantly worse, confirming that relative relationships encode the relevant physics information.
• Robustness: The performance remained stable for signal-to-background ratios up to $S/B \lesssim 1\%$, consistent with the unsupervised paradigm.

Significance and Claims
The paper claims that leveraging graph-theoretic insights, specifically the concepts of local and global rigidity, allows for the refinement of machine learning tools for collider experiments. The results suggest that:

1. Physically Motivated Biases: Sparse, rigid graphs provide a natural choice for inductive biases in anomaly detection, retaining essential geometric structure while avoiding the overfitting associated with dense representations.
2. State-of-the-Art Performance: The unique-6 graph construction represents the current state-of-the-art among unsupervised autoencoder-based methods for this specific anomaly detection benchmark.
3. Complementarity: The approach highlights a distinct difference between supervised classification (which benefits from rich, low-level data) and unsupervised anomaly detection (which benefits from structured, intermediate-level information).

The authors conclude that these findings motivate further exploration of the connection between graph theory, computational complexity, and machine learning interpretability in high-energy physics, without claiming immediate discovery potential but rather demonstrating improved sensitivity in model-agnostic searches.