# Computing Steiner Trees using Graph Neural Networks

Reyan Ahmed  Md Asadullah Turja  Faryad Darabi Sahneh  Mithun Ghosh  Keaton
Hamm  Stephen Kobourov

###### Abstract

Graph neural networks have been successful in many learning problems and real-
world applications. A recent line of research explores the power of graph
neural networks to solve combinatorial and graph algorithmic problems such as
subgraph isomorphism, detecting cliques, and the traveling salesman problem.
However, many NP-complete problems are as of yet unexplored using this method.
In this paper, we tackle the Steiner Tree Problem. We employ four learning
frameworks to compute low cost Steiner trees: feed-forward neural networks,
graph neural networks, graph convolutional networks, and a graph attention
model. We use these frameworks in two fundamentally different ways: 1) to
train the models to learn the actual Steiner tree nodes, 2) to train the model
to learn good Steiner point candidates to be connected to the constructed tree
using a shortest path in a greedy fashion. We illustrate the robustness of our
heuristics on several random graph generation models as well as the SteinLib
data library. Our finding suggests that the out-of-the-box application of GNN
methods does worse than the classic 2-approximation method. However, when
combined with a greedy shortest path construction, it even does slightly
better than the 2-approximation algorithm. This result sheds light on the
fundamental capabilities and limitations of graph learning techniques on
classical NP-complete problems.

##  1 Introduction

Graphs are one of the most flexible data structures for capturing relational
information. Classical machine learning models such as neural networks or
recurrent neural networks are not designed to handle graph input or output
directly. To learn a flexible data structure like a graph, Gori et al. [14]
introduced the concept of a graph neural network (GNN). They represented the
GNN as a recursive neural network where nodes are treated as state vectors,
and the relationship among these nodes is quantified by the edges. Scarselli
et al. [36] extended the notion of unfolding equivalence that leads to the
transformation of the approximation property of feed-forward networks
(Scarselli and Tsoi [37]) to GNNs.

Many combinatorial problems arise naturally in various applications, many of
which are known to be NP-complete. In 1972, the seminal paper [19] provided a
list of NP-complete problems, many of which are graph-based. GNNs offer an
alternative to traditional heuristic approximation algorithms; indeed the
initial GNN model [36] was used to approximate solutions to two classical
graph-based problems: subgraph isomorphism and clique detection.

An interesting line of research is to explore the capabilities and limitations
of graph neural networks as alternative approaches to existing heuristics and
approximation algorithms to theoretical graph problems. This can open up
modern methods to solve such problems at scale in practice, and also it can
shed light on the fundamental capacity of such learning methods.

###  1.1 Background

Graph neural networks have been a very active area of research during the past
few years. To name a few, Lei et al. [25] introduced recurrent neural
operations for graphs with their associated kernel spaces. The notion of
studying graph neural models as Message Passing Neural Networks is discussed
by Gilmer et al. [13]. Garg et al. [12] generalized the standard message
passing GNNs that rely on the local graph structure, proposing a novel
framework for the GNN through graph-theoretic formalism which provided
insights into the design of more effective GNNs.

Mishra et al. [28] demonstrated state-of-the-art spatial GNNs operations with
theoretical tools. They proposed the node masking concept for better
generalization and scaling in both transductive and inductive settings. Most
recent works on learning the graph structure data focus on the distributed
representation of the substructure of the graph such as nodes and subgraphs.
But for the tasks related to graph clustering or graph classification, models
require the entire graph as fixed-length feature vectors. Graph kernels remain
as one of the most effective ways to obtain these vectors by using some
handcrafted features such as shortest paths or graphlets, but this technique
can also result in poor generalization. Narayanan et al. [29] proposed a
neural embedding formulation named graph2vec to learn data-driven distributed
representations of arbitrary graphs. The embeddings of graph2vec are learned
in an unsupervised manner and are task agnostic. Different explainer models
have been also proposed to understand the reason for decision-making by the
models [7, 44].

###  1.2 Related Works

Graph neural networks have been widely used in many areas including physical
systems [4, 34], protein-protein interaction networks [10], social science
[16, 22], and knowledge graphs [15]. For more information on graph neural
networks, see the survey [45].

Subsequently, other methods have been proposed to solve other combinatorial
problems; for example, Khalil et al. [20] proposed a framework to compute
minimum vertex cover, maximum cut, and traveling salesman problems. The survey
[41] discusses different combinatorial problems that have been approached
using graph neural networks or related methods. Bello et al. [5] studied
machine learning in general and deep reinforcement learning in particular for
the planar traveling salesman problem (TSP). Kool et al. [24] also studied the
TSP problem to make progress in learning heuristics that can be applied to a
broad scope of different practical problems. Prates [32] et al. proposed a
message-passing GNN model to predict the decision TSP problem. Lemos et al.
[26] show that GNNs can be trained to solve fundamental combinatorial
optimization challenges such as the graph coloring problem. Different neural
network models have been proposed to solve other combinatorial problems such
as satisfiability (SAT) problem [38, 27], vertex cover [27, 8], independent
set [27] etc. To the best of our knowledge, there does not exist any work that
considered the Steiner tree problem.

###  1.3 Problem Statement

The Steiner Tree Problem is another classical problem mentioned in Karp’s
initial NP-complete problem list [19]. In this problem, we are given a
weighted graph $G=(V,E)$ and a set of terminals $T\subset V$, and the
objective is to compute a minimum cost tree that spans $T$. Several
approximation algorithms have been proposed for this problem including a
classical 2-approximation algorithm that first computes the metric closure of
$G$ on $T$ and then returns the minimum spanning tree [1].

In this paper we are interested in the following question: can graph neural
networks provide good candidate solutions to the Steiner Tree Problem?

###  1.4 Summary of Contributions

In this paper, we tackle the Steiner Tree Problem from a graph neural network
perspective. Specifically,

  * •

We propose four different models to predict solution nodes for the Steiner
tree problem.

  * •

We propose two heuristics to compute low cost Steiner trees from these models.
In one heuristic we use the model’s predictions to construct a connected
induced graph. We then compute the spanning tree of that induced graph. In the
other heuristic, we predict good Steiner nodes and connect them to the
constructed tree using a greedy shortest path method.

  * •

We generate forty thousand Steiner tree instances using different random graph
generators. We compute the exact solution of these instances, and train and
test the models on this dataset. We also test the models on the SteinLib data
library which is outside of the training set.

Our finding suggests that out-of-the-box application of GNN methods does worse
that the classic 2-approximation method. However, when combined with a greedy
shortest path construction, it even does slightly better than the
2-approximation algorithm.

##  2 Neural network-based models

To begin, we lay out the different learning models that will be tested in
Section 5. The first model is not a graph learning model, but rather a
feedforward model that turns out to not be well-suited for graph problems.
However, we include it to get a baseline for the performance of other models.

###  2.1 Feedforward model

In the Steiner tree problem, given an input graph $G$, we want to determine
which nodes are present in the Steiner tree. The problem can be represented by
a function $f(G)$ that outputs a binary vector $Y$. The value of $Y[i]$ is 1
if and only if the $i$-th node is present in the solution. One can use
feedforward neural networks to approximate this function. A feedforward
network defines a mapping $y=f(x,\theta)$ and learns the value of the
parameters $\theta$ that result in the best function approximation. The input
of a feedforward network is a vector, and one can represent a graph by a
binary vector $x$ where each element corresponds to a pair of nodes. An entry
of $x$ is 1 if and only if there is an edge between the corresponding pair of
nodes. In this representation, we need to assume that the number of node pairs
or number of nodes will not exceed an upper bound. Indeed, we build the model
for the graph’s size of the upper bound and treat any other smaller graph as a
large graph with auxiliary, isolated non-terminal nodes.

###  2.2 Graph neural network model

A GNN model, in a transductive-inductive framework was proposed by [36] using
the TensorFlow platform. The GNN model is capable of handling both directed
and undirected graphs. In this framework, both edges and nodes have attributes
that are called labels (typically vectors in some parameter space). Examples
of node labels are average colors, area, and shape factors, and examples of
edge features are barycenters of two adjacent regions of a triangulation, or
distance between nodes. Each node also has a state, and a computational
process named diffusion updates the states. The input graph topology drives
the computation. The diffusion mechanism forms the computation schema which
updates the state vector at each node as a function of node labels,
neighboring edge labels, and states of the neighboring nodes. The information
relevant to each task will be summarized by the state for each node. The node
states are used to compute the class or target properties.

Let the state and output at node $n\in V$ be $x_{n}\in\mathbb{R}^{s}$ and
$o_{n}\in\mathbb{R}^{m}$, respectively. Also, let $d_{w}$ represents the state
transition function which ultimately drives the diffusion process and $f_{w}$
denotes the output function. The diffusion process can be described by the
following equations:

(2.1) $x_{n}=\sum_{(n,v)\in E}d_{w}(l_{n},l_{(n,v)},x_{v},l_{v}),$

(2.2) $o_{n}=f_{w}(x_{n},l_{n}).$

Where $l_{n}\in\mathbb{R}^{q}$ and $l_{(n,v)}\in\mathbb{R}^{p}$ are the labels
attached to $n$ and $(n,v)$, respectively. The solution of the Jacobi
iterative procedure can be written as

(2.3) $x_{n}(t+1)=\sum_{(n,v)\in E}d_{w}(l_{n},l_{(n,v)}),x_{v}(t),l_{v}).$

Equation (2.3) implements the diffusion process for the state computation.
Simple multilayer perceptrons (MLPs) with a unique hidden layer define the
functions $d_{w}$ and $f_{w}$ in this framework. The unfolding of the encoding
network (Figure 1) is demonstrated by Equation (2.3) by calculating the
$d_{w}$ and $f_{w}$ for each node. Each node represents a replica of
perceptron realizing $d_{w}$ whereas each unit $x_{n}(t)$ represents the state
at time $t$. The next time state at time $t+1$ is computed by the stored
states in all nodes at time $t$. When the state computation converges, $f_{w}$
is applied to each node to compute the output. The error backpropagation is
performed on the unfolding network for the gradient computation. The weights
of the network are adopted such that it reduces the error between the output
of the network and the expected targets on the supervised node sets during the
training. This procedure is discussed further in Section 4.

Figure 1: Encoding network framework corresponding to a given input graph
(from left to right). For each node, $d_{w}$ and $f_{w}$ processing units are
replicated and connected following the graph topology.

###  2.3 Graph Convolution Network

Graph Convolution Networks (GCNs) generalize the notion of convolution from
grid data to graph data. Essentially, a GCN learns a desired set of node
features from it’s own features and the neighboring nodes features. Unlike
GNNs, GCNs stack multiple convolution layers to learn higher order node
representations. We can consider the convolution operation as the
multiplication of a graph signal $x\in\mathbb{R}^{n}$ with a filter
$g_{\theta}=\textnormal{diag}(\theta)$ in the Fourier domain, i.e.,

(2.4) $g_{\theta}*x=Ug_{\theta}U^{T}x.$

Here $U$ is the matrix of eigenvectors of the symmetric normalized graph
Laplacian $L=I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Delta U^{T}$, $U^{T}x$
is a graph Fourier transform of $x$, and $\Delta$ is a diagonal matrix
containing the eigenvalues of $L$ (see, e.g., [39] for more details on graph
Fourier transforms). By comparing $L=U\Delta U^{T}$ with the graph convolution
operator in Equation 2.4, we can interpret $g_{\theta}$ as function of
$\Delta$, i.e, $g_{\theta}(\Delta)$ Computing Equation (2.4) can prohibitively
expensive because computing the spectral decomposition of the graph Laplacian
is computationally expensive for large graphs ($O(n^{3})$ flops). In this
regard, [17] suggested an approximation of $g_{\theta}(\Delta)$ by means of
Chebyshev polynomials $T_{k}(x)$ up to $K^{th}$ order:

(2.5)
$g_{\theta^{\prime}}(\Delta)=\sum_{k=0}^{K}\theta^{\prime}_{k}T_{k}(\hat{\Delta}),$

where $\hat{\Delta}=\frac{2}{\lambda_{max}}\Delta-I_{N}$. $\lambda_{max}$
denotes the largest eigenvalue of $L$ and $\theta^{\prime}\in R^{n}$ is a
vector of Chebyshev coefficients (More details about Chebyshev polynomial can
be found at [17]). Note that $g_{\theta^{\prime}}$ is a $K$-localized filter,
which means it depends only on nodes that are at most $K$ steps away from the
source node, since it is a $K^{th}$ order polynomial. The complexity of
computing (2.5) is linear in the the number of edges in the graph. In [22],
the authors built a layer-wise convolutional neural network of (2.5) assuming
$K=1$. Each layer is followed by a pointwise nonlinearity, i.e., a function
that is nonlinear w.r.t $L$. In our work, we use this version of GCN due to
it’s simplicity and ability to learn a rich class of convolutional filters by
stacking multiple layers. Under this approximation, Equation (2.5) simplifies
to:

(2.6)
$g_{\theta}*x\approx\theta^{\prime}_{0}x+\theta^{\prime}_{1}(L-I_{N})x=\theta^{\prime}_{0}x-\theta^{\prime}_{1}D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x,$

Our GCN model architecture: We stacked two-layers of GCN followed by a multi-
layer perceptron (MLP) with two hidden layers for our Steiner node predictor
network (Figure 2). The size of the hidden layers are 128 for both the GCN and
MLP layers. Finally, we minimized cross-entropy loss to train our network for
500 epochs with a learning rate of 1e-3.

###  2.4 Graph Attention Network

The GCN in Section 2.3 is capable of learning a wide range of kernels.
However, the learned filters depend on the eigenbasis of the graph Laplacian,
which hinders it’s generalization power. For this reason, [40] proposed Graph
Attention Networks (GATs) by stacking layers in which nodes are able to figure
out which neighboring nodes are important to compute it’s updated node
features. GATs enable specifying different weights to different nodes in a
neighborhood without depending on knowing the graph structure up front. The
attention module in a GAT is a single layer feed-forward network followed by a
LeakyReLU nonlinearity. Initially, a linear transformation is applied at each
node feature; then a shared attentional mechanism $a$ computes the attention
coefficient:

(2.7) $e_{ij}=a(Wx_{i},Wx_{j}),$

were $W$ is the learned weight matrix applied to the features $x_{i}$ and
$x_{j}$ of nodes $i$, and $j$, respectively. The quantity $e_{ij}$ is called
the attention score as it arises from the attention module $a$.

In our GAT model, we used a similar architecture as GCN by replacing GCN
modules with GAT (Figure 2). We also used the same hyperparameters and loss
function as for the GCN.

Figure 2: Network Architecture for the GCN and GAT models. Each of them
consists of two layers of GCN/GAT layers followed by a multilayer perceptron
(MLP). The hidden layers of both GCN/GAT and MLP are followed by pointwise
nonlinear ReLU and Dropout layers.

##  3 Two frameworks of using the learning models

###  3.1 The learning-only black-box method

In this method, we just show the model several STP instances and its optimal
solution and see if the model can correctly learn to identify nodes belonging
to Steiner trees.

In this framework, the neural network models provide likelihood scores that
each node is in the Steiner tree solution. Thus, we must determine which edges
should be included to make the node set into a candidate solution for the
Steiner tree. We use two heuristics to do this here. To begin, we first add
the terminal nodes to the solution if they are not already present, and then
compute the induced graph. We keep adding the rest of the nodes one-by-one by
decreasing order of the likelihood score and forming the induced graph until
we have a connected induced graph. In the last step, we compute a minimum
spanning tree of the induced graph and prune non-terminal nodes that have
degree 1. Checking the connectivity of the induced graph can be computed in
$\tilde{O}(m)$, where $m$ is the number of edges [6]. The running time of
computing the minimum spanning tree is also $\tilde{O}(m)$ [6].

###  3.2 A learning-assisted heuristic: combining learning and algorithms

In this approach, we compare the simple heuristic with a classical
$2$-approximation algorithm. In this approximation algorithm, given an input
graph $G=(V,E)$ and a set of terminals $T$, we first compute a complete graph
$G^{\prime}=(T,E^{\prime})$. The edge weights of $G^{\prime}$ are set equal to
the shortest path distance between the terminal endpoints. The graph
$G^{\prime}$ is called the metric closure of $G$. The minimum spanning tree of
the metric closure provides a Steiner tree of $G$ on terminals $T$.

The simple heuristic provides a valid Steiner tree; however, in our numerical
experiments, we find that the approximation ratio for this heuristic (ratio of
the cost of the returned solution and the cost of the optimal solution) is
often larger than that of the $2$-approximation algorithm discussed in Section
5. Therefore, we also tested another heuristic for forming the Steiner tree
from the learning model output as follows.

In Figure 3, A, B and C are the terminal nodes whereas D is not. The
$2$-approximation algorithm will first construct the metric closure by
computing the shortest paths of all pair terminals. Note that the non-terminal
vertex D does not appear in any shortest path. For example, the shortest path
length from A to B is 5, and this is from the direct edge connecting the
terminals. Hence, the non-terminal node will not be present in the
$2$-approximation. Without loss of generality, the $2$-approximation algorithm
will choose the A-C-B path with a total cost of 10. Even though the path
contains all the terminal nodes, this is not the optimal solution in terms of
cost. We update the heuristic with a myopic decision such that the heuristic
chooses the optimal cost that may also include nodes that are not terminal.
For example, the edges AD, DB, and DC form the optimal solution, it contains
all the terminal nodes with the minimum cost of 9. The $2$-approximation
algorithm does not add any node that does not belong to a shortest path
between two terminal nodes. We use our neural network models to predict nodes
that may not belong to any shortest path, but whose inclusion improves the
solution. We include these predicted nodes as terminals and then compute the
$2$-approximation algorithm. Each time we include a new node, we run the
$2$-approximation. How many new nodes will be added can be considered as a
parameter of the heuristic. For our implementation, we keep adding nodes until
the induced graph of the set of current nodes is connected.

Figure 3: Example graph for the heuristic to compute the Steiner tree.

##  4 Model setup and training

In order to train the models, one has to provide training data consisting of
input graphs $G=(V,E)$, edge weights $W:E\rightarrow\mathbb{R}^{+}$, and
terminals $T\subseteq V$. Given $G,W,T$, our goal is to produce a binary label
for each vertex in $G$, such that label 1 indicates that a vertex is in the
Steiner tree and label 0 indicates that it is not. The model is trained with
Stochastic Gradient Descent (SGD) using the ADAM optimizer [21] to minimize
the binary cross-entropy loss between the models’ prediction and the ground-
truth (a boolean vector in $\\{0,1\\}^{|V|}$ indicating whether a node for the
Steiner tree problem is in the solution or not) for each training sample.

###  4.1 Data generation

We produce training instances using several different random graph generation
models: Erdős–Rényi (ER) [9], Watts–Strogatz (WS) [42], Barabási–Albert (BA)
[3], and random geometric (GE) [31] graphs. For (ER), there is an edge
selection probability $p$, which we set to be at least $\frac{2\ln n}{n}$ to
ensure that the generated graphs are connected with high probability. In the
(WS) model, we initially create a ring lattice of constant degree $K=6$. We
then rewire each edge with probability $0\leq p\leq 1$ while avoiding self-
loops or duplicate edges. For our experiments we use $K=6$ and $p=0.2$. In the
(BA) model, a new node is connected to $m=5$ existing nodes. In the random
geometric graph model, we uniformly select $n$ points from the Euclidean cube,
and connect nodes whose Euclidean distance is not larger than a threshold
$r_{c}$, which we choose to be $\sqrt{\frac{(1+\epsilon)\ln n}{\pi n}}$ for
some $\epsilon>0$ to ensure the graph is connected with high probability.

The Steiner tree problem is NP-complete even if the input graph is unweighted
[11]. We generate both unweighted and weighted Steiner tree instances using
the random generators described above. The number of nodes of these instances
is in $\\{10,20,\cdots,200\\}$. For the number of terminals, we use two
distributions. In the first distribution, the percentage of the number of
terminals with respect to the total number of terminals is in
$\\{20\%,40\%,60\%,80\%\\}$. In the second distribution the percentage is in
$\\{3\%,6\%,\cdots,18\%\\}$. These two cases are considered to determine the
behavior of the learning models on large and small terminal sets (compared
with the overall graph size).

###  4.2 Computing optimal solutions

We have generated around 40,000 Steiner tree instances. For each of these
instances, we have computed the exact solution via a known flow-based integer
linear program (ILP) [2]. While there are various ILPs for solving the Steiner
tree problem, our choice of this ILP is due to its fast runtime compared with
others.

We used CPLEX 12.6.2 as an ILP solver in a high-performance computer for all
experiments (Lenovo NeXtScale nx360 M5 system with 400 nodes). Each node has
192 GB of memory. We have used Python for implementing the algorithms and
spanner constructions. Since we have run the experiment on a couple of
thousand instances, we run the solver for four hours to solve each instance.
The exact solution of each instance of ER, WS, and BA random graph generator
was able to finish in four hours. For GE instances, 99.17% of the instances
were able to finish in four hours.

While random graphs can sometimes be ideal, and thus the Steiner tree problem
on them may be easily solved, the SteinLib library [23] provides a catalog of
hard graph instances for solving the Steiner tree problem. For thorough
comparison, we perform experiments on instances from two subsets of SteinLib:
I080 and I160.

###  4.3 Model architectures

For the feedforward model, we have used two hidden layers each having 100
neurons with a ReLU activation function. For the output layer, we have used
the sigmoid activation function. For the graph neural network model, we set
the size of the state dimension equal to 5. For the multi-layer perceptrons
representing $d_{w}$ and $f_{w}$ we have used one hidden layer of size 40 with
the tanh activation function. For the graph convolutional network and
attention model, we have used two hidden layers of size 128. For the GCN
model, we have used the ReLU activation function. For the GAT model, we have
used the ELU activation function.

###  4.4 Feature selection

We have used different properties of input instances as features to train the
neural networks. We provide a list of these features here:

  1. 1.

Shortest paths: For every pair of vertices, we compute the shortest path. We
add the shortest path distance as a feature.

  2. 2.

Vertex degree: For every vertex we use the number of adjacent vertices
(degree) as a feature. We denote the degree of vertex $u$ by $deg(u)$.

  3. 3.

Clustering coefficient: We use the clustering coefficient for every vertex as
a feature. We first define this coefficient for unweighted graphs. We denote
the number of triangles through vertex $u$ as $T(u)$. Then the clustering
coefficient $c_{u}$ of vertex $u$ in an unweighted graph is the fraction of
possible triangles through $u$:

(4.8) $c_{u}=\frac{2T(u)}{deg(u)(deg(u)-1)}$

For weighted graphs, one can define the clustering coefficient in multiple
ways [35]. We rely on the method that computes the geometric average of the
subgraph edge weights [30]:

(4.9)
$c_{u}=\frac{1}{deg(u)(deg(u)-1)}\sum_{vw}(\hat{w}_{uv}\hat{w}_{uw}\hat{w}_{vw})^{1/3}$

Here $\hat{w}_{uv}$ are normalized edge weights, $\hat{w}_{uv}=w_{uv}/max(w)$,
where $max(w)$ is the maximum edge weight in the network.

(a) Erdős–Rényi (ER) model

(b) Watts-Strogatz (WS) model

(c) Barabási–Albert (BA) model

(d) Random geometric graph (GE) model

Figure 4: Density distribution

(a) Erdős–Rényi (ER) model

(b) Watts-Strogatz (WS) model

(c) Barabási–Albert (BA) model

(d) Random geometric graph (GE) model

Figure 5: Radius distribution

##  5 Experimental results and analyses

Before proceeding with the learning experiments, we note some characeristics
of the randomly generated graphs – namely the distributions of the density
(Figure 4) and radius (Figure 5) of the graphs from each generator.

Geometric graphs have much larger radii on average than the others, as the
other generators create high degree nodes that make the radius of the graphs
relatively small. The presence of many high degree nodes makes the Steiner
tree problem simpler, as terminal nodes are closely connected more often, and
there is often no need to include other nodes in the solution. This also
reflects the learning process of the neural network models: after 500 epochs,
the loss decreases significantly for datasets generated from only one of the
Erdős–Rényi, Watts-Strogatz, and Barabási–Albert models, while the training
for datasets generated solely from the geometric model typically requires
around 1000 epochs to significantly reduce the loss. Hence, in the combined
dataset we train the models for 1000 epochs.

We have used $80\%$ of the problem instances for training and the rest for
testing. Table 1 shows the results of testing on unweighted graphs. As a
baseline for comparison with standard algorithms, we compare our learning
results with the 2-approximation algorithm described above. The Steiner tree
problem is well-studied and there are many different approximation algorithms,
see [18, 33, 43], but out of these we choose to compare with the
$2$-approximation algorithm given that it has a straightforward implementation
and performs very well in practice. In the tables below, FF1, GNN1, GCN1, and
GAT1 represent the learning models combined with the simple heuristic of
Section 3.2, and FF2, GNN2, GCN2, and GAT2 represent the learning models
combined with the more advanced heuristic. The numbers in the table represent
the experimental approximation ratios: the ratio of the cost of the heuristic
solution to the cost of the optimal solution. We can see that the simple
heuristic performs relatively poorly. However, it is 5-10 times faster
compared to other heuristics (Table 2). The Erdős–Rényi graphs have the
largest maximum ratio. The Watts-Strogatz graphs have a relatively larger
average ratio. Boldface numbers indicate the best ratio along each column. We
can see that most of the time and for most generators, the second heuristic
provides the best average experimental approximation ratio. However, due to
the complexity of the second heuristic, some of the learning models using it
take somewhat longer to run than the 2-approximation.

Gen. | ER | WS | BA | GE
---|---|---|---|---
Model | Max | Avg | Max | Avg | Max | Avg | Max | Avg
2-approx | 1.4 | 1.04 | 1.28 | 1.05 | 1.6 | 1.006 | 1.28 | 1.01
FF1 | 9.0 | 1.59 | 9.0 | 1.37 | 5.8 | 1.4 | 9.0 | 1.73
GNN1 | 4.54 | 1.36 | 3.71 | 1.15 | 1.5 | 1.01 | 3.94 | 1.68
GCN1 | 4.25 | 1.35 | 2.42 | 1.13 | 3.0 | 1.04 | 4.14 | 1.66
GAT1 | 4.25 | 1.35 | 2.43 | 1.13 | 3.0 | 1.04 | 4.12 | 1.65
FF2 | 1.4 | 1.03 | 1.23 | 1.04 | 1.51 | 1.005 | 1.28 | 1.01
GNN2 | 1.33 | 1.03 | 1.21 | 1.04 | 1.45 | 1.005 | 1.2 | 1.01
GCN2 | 1.3 | 1.03 | 1.23 | 1.04 | 1.48 | 1.005 | 1.25 | 1.01
GAT2 | 1.33 | 1.03 | 1.23 | 1.04 | 1.47 | 1.005 | 1.26 | 1.01
Table 1: Approximation ratio for unweighted graphs. Mod./Gen. | ER | WS | BA | GE
---|---|---|---|---
2-approx | 2484.96 | 1480.52 | 2404.60 | 2014.82
FF1 | 351.91 | 286.31 | 471.58 | 341.14
GNN1 | 767.80 | 685.19 | 1006.67 | 763.62
GCN1 | 385.24 | 188.68 | 741.51 | 280.95
GAT1 | 671.86 | 237.48 | 789.47 | 637.85
FF2 | 3652.59 | 2008.85 | 2676.14 | 2193.26
GNN2 | 5929.94 | 3641.42 | 5826.08 | 4852.91
GCN2 | 3048.39 | 2898.11 | 2922.69 | 3713.09
GAT2 | 5669.98 | 2318.34 | 3656.26 | 4249.00
Table 2: Running time (in seconds) for unweighted graphs.

Results for weighted graphs are shown in Table 3. For the random graph
generators, we draw edge weights uniformly at random from
$\\{1,2,\cdots,10\\}$. We also use the SteinLib library dataset for testing,
as it provides hard instances of the Steiner tree problem. As can be seen from
the table, the SteinLib instances have the largest maximum and average ratios,
which is to be expected. The Watts-Strogatz model has a relatively lower
ratio. Again we compare the different neural network-based models with the
$2$-approximation algorithm. The simple heuristics (FF1, GNN1, GCN1, and GAT1)
provide a relatively larger ratio, though the running time of these methods is
several magnitudes faster compared to the $2$-approximation algorithm. The
best ratio in each column is marked in bold. For most of the graph generators,
GNN2, GCN2, and GAT2 perform better than the other heuristics on average at
the cost of somewhat more computation time.

Gen. | ER | WS | BA | GE | SL
---|---|---|---|---|---
Model | Max | Avg | Max | Avg | Max | Avg | Max | Avg | Max | Avg
2-approx | 1.21 | 1.03 | 1.15 | 1.001 | 1.25 | 1.008 | 1.24 | 1.03 | 1.45 | 1.24
FF1 | 8.77 | 1.67 | 9.08 | 1.39 | 4.62 | 1.39 | 10.30 | 1.87 | 10.29 | 2.23
GNN1 | 4.01 | 1.43 | 3.43 | 1.18 | 1.26 | 1.12 | 3.91 | 1.81 | 4.56 | 2.15
GCN1 | 3.76 | 1.43 | 2.26 | 1.17 | 2.43 | 1.13 | 4.1 | 1.79 | 4.78 | 2.13
GAT1 | 3.76 | 1.43 | 2.27 | 1.17 | 2.43 | 1.14 | 3.29 | 1.78 | 3.83 | 2.14
FF2 | 1.2 | 1.03 | 1.13 | 1.001 | 1.25 | 1.007 | 1.24 | 1.03 | 1.45 | 1.23
GNN2 | 1.19 | 1.02 | 1.12 | 1.001 | 1.23 | 1.006 | 1.23 | 1.02 | 1.43 | 1.21
GCN2 | 1.2 | 1.02 | 1.13 | 1.001 | 1.24 | 1.006 | 1.22 | 1.02 | 1.44 | 1.21
GAT2 | 1.19 | 1.02 | 1.13 | 1.001 | 1.23 | 1.006 | 1.22 | 1.02 | 1.43 | 1.21
Table 3: Approximation ratio for weighted graphs. Mod./Gen. | ER | WS | BA | GE | SL
---|---|---|---|---|---
2-approx | 624.09 | 350.64 | 628.72 | 511.73 | 154.91
FF1 | 46.84 | 32.14 | 48.56 | 44.45 | 13.06
GNN1 | 72.47 | 35.28 | 91.00 | 95.48 | 19.74
GCN1 | 52.99 | 32.65 | 54.77 | 51.64 | 12.62
GAT1 | 85.52 | 33.45 | 71.65 | 69.49 | 15.74
FF2 | 719.30 | 384.06 | 1146.40 | 969.99 | 266.22
GNN2 | 1491.36 | 606.85 | 1273.60 | 842.73 | 248.34
GCN2 | 1245.13 | 582.06 | 1026.96 | 795.15 | 223.80
GAT2 | 1216.86 | 644.32 | 1102.08 | 992.39 | 260.77
Table 4: Running time (in seconds) for weighted graphs.

##  6 Conclusion

We have used different neural network models to compute Steiner trees for
weighted and unweighted graphs, and compared the output to the exact
solutions. We trained the models on a combination of randomly generated graphs
from various models. For testing on weighted graphs, we also added SteinLib
instances. The models here output a binary vector indicating whether a given
node is part of the Steiner tree or not, and therefore we must determine a
rule to include or exclude edges in the final Steiner tree solution. To this
end, we first proposed a simple heuristic that can compute the Steiner tree
faster than the classical $2$-approximation algorithm; however, the
experimental approximation ratio of this heuristic worse than the
$2$-approximation in practice. We then proposed another heuristic that uses
more computation but performs better on average than the $2$-approximation.
Our study shows that the application of different combinatorial techniques
along with neural network prediction can provide better solutions to the
Steiner tree problem.

For future work, we believe that the application of other combinatorial
techniques as a post-processing step as well as other models like
reinforcement learning remain an interesting avenue for exploration.
Additionally, more sophisticated GNN models which output edge information
should be explored, as this could potentially eliminate the need for running a
heuristic after the output of the learning model. Finally, some GNN models
indicate that the use of additional input information, such as a candidate
solution to the Steiner tree problem, into the learning model can yield much
better success. Applying this technique to similar models than those presented
here could lead to significantly better learning models.

## References

  * [1] Ajit Agrawal, Philip Klein, and Ramamoorthi Ravi.  When trees collide: An approximation algorithm for the generalized steiner problem on networks.  SIAM journal on Computing, 24(3):440–456, 1995.
  * [2] Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G Kobourov, Richard Spence, Joseph Watkins, et al.  Multi-level steiner trees.  Journal of Experimental Algorithmics (JEA), 24:1–22, 2019.
  * [3] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [4] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu.  Interaction networks for learning about objects, relations and physics.  In Advances in neural information processing systems, pages 4502–4510, 2016.
  * [5] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning.  In Proceedings of The International Conference on Learning Representations (ICLR), 2016.
  * [6] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [7] Hanjun Dai, Xinshi Chen, Yu Li, Xin Gao, and Le Song.  A framework for differentiable discovery of graph algorithms.  In Proceedings of Neural Information Processing Systems, 2020.
  * [8] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  In Proceedings of Neural Information Processing Systems, 2017.
  * [9] Paul Erdős and Alfréd Rényi.  On random graphs, i.  Publicationes Mathematicae (Debrecen), 6:290–297, 1959.
  * [10] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur.  Protein interface prediction using graph convolutional networks.  In Advances in neural information processing systems, pages 6530–6539, 2017.
  * [11] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [12] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola.  Generalization and representational limits of graph neural networks.  In International Conference on Machine Learning, pages 3419–3430, 2020.
  * [13] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International conference on machine learning, pages 1263–1272, 2017.
  * [14] Marco Gori, Gabriele Monfardini, and Franco Scarselli.  A new model for learning in graph domains.  In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729–734. IEEE, 2005.
  * [15] Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto.  Knowledge transfer for out-of-knowledge-base entities: A graph neural network approach.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence, 2017.
  * [16] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in neural information processing systems, pages 1024–1034, 2017.
  * [17] David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval.  Wavelets on graphs via spectral graph theory.  Applied and Computational Harmonic Analysis, 30(2):129–150, 2011\.
  * [18] Mathias Hauptmann and Marek Karpiński.  A compendium on Steiner tree problems.  Inst. für Informatik, 2013.
  * [19] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * [20] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  In Advances in Neural Information Processing Systems, pages 6348–6358, 2017.
  * [21] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [22] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In Proceedings of The International Conference on Learning Representations (ICLR), 2016.
  * [23] T. Koch, A. Martin, and S. Voß.  SteinLib: An updated library on Steiner tree problems in graphs.  Technical Report ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, Berlin, 2000.
  * [24] Wouter Kool, Herke Van Hoof, and Max Welling.  Attention, learn to solve routing problems!  In Proceedings of The International Conference on Learning Representations (ICLR), 2018.
  * [25] Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Deriving neural architectures from sequence and graph kernels.  In International Conference on Machine Learning, pages 2024–2033, 2017.
  * [26] Henrique Lemos, Marcelo Prates, Pedro Avelar, and Luis Lamb.  Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems.  In 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), pages 879–885. IEEE, 2019.
  * [27] Zhuwen Li, Qifeng Chen, and Vladlen Koltun.  Combinatorial optimization with graph convolutional networks and guided tree search.  In Proceedings of Neural Information Processing Systems, 2018.
  * [28] Pushkar Mishra, Aleksandra Piktus, Gerard Goossen, and Fabrizio Silvestri.  Node masking: Making graph neural networks generalize and scale better.  arXiv preprint arXiv:2001.07524, 2020.
  * [29] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal.  graph2vec: Learning distributed representations of graphs.  arXiv preprint arXiv:1707.05005, 2017.
  * [30] Jukka-Pekka Onnela, Jari Saramäki, János Kertész, and Kimmo Kaski.  Intensity and coherence of motifs in weighted complex networks.  Physical Review E, 71(6):065103, 2005.
  * [31] Mathew Penrose.  Random geometric graphs.  Number 5. Oxford university press, 2003.
  * [32] Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi.  Learning to solve np-complete problems: A graph neural network for decision tsp.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731–4738, 2019.
  * [33] Hans Jürgen Prömel and Angelika Steger.  The Steiner tree problem: a tour through graphs, algorithms, and complexity.  Springer Science & Business Media, 2012.
  * [34] Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia.  Graph networks as learnable physics engines for inference and control.  In International Conference on Machine Learning, 2018.
  * [35] Jari Saramäki, Mikko Kivelä, Jukka-Pekka Onnela, Kimmo Kaski, and Janos Kertesz.  Generalizations of the clustering coefficient to weighted complex networks.  Physical Review E, 75(2):027105, 2007.
  * [36] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE Transactions on Neural Networks, 20(1):61–80, 2008.
  * [37] Franco Scarselli and Ah Chung Tsoi.  Universal approximation using feedforward neural networks: A survey of some existing methods, and some new results.  Neural networks, 11(1):15–37, 1998.
  * [38] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill.  Learning a sat solver from single-bit supervision.  In Proceedings of The International Conference on Learning Representations (ICLR), 2018.
  * [39] David I Shuman, Benjamin Ricaud, and Pierre Vandergheynst.  Vertex-frequency analysis on graphs.  Applied and Computational Harmonic Analysis, 40(2):260–291, 2016\.
  * [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  International Conference on Learning Representations, 2018.
  * [41] Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman.  Learning combinatorial optimization on graphs: A survey with applications to networking.  IEEE Access, 8:120388–120416, 2020.
  * [42] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  Nature, 393(6684):440, 1998.
  * [43] Pawel Winter.  Steiner problem in networks: A survey.  Networks, 17(2):129–167, 1987.
  * [44] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  Advances in neural information processing systems, 32:9240, 2019\.
  * [45] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun.  Graph neural networks: A review of methods and applications.  AI Open, 1:57–81, 2020.


11institutetext:  Universidade Tecnológica Federal do Paraná - UTFPR - DAFIS
Av Monteiro Lobato Km 04, 84016-210, Ponta Grossa, PR, Brazil
Instituto de Física Teórica - UNESP, Rua Dr. Bento T. Ferraz, 271,
Bloco II, 01140-070, São Paulo, SP, Brazil

# Limit on Higgs boson trilinear self-coupling in coupled technicolor models

A. Doff 11 A. A. Natale 221122

###### Abstract

The trilinear self-coupling of the Higgs boson, in a theory in which this
boson is composite, is compared to the experimental bound of this quantity
obtained by the CMS experiment. In the case of a model where technicolor (TC)
is coupled to QCD, we find that the experimental result already constrains the
dynamics of the theory, which is represented by an expression of the
technifermion self-energy ($\Sigma_{tc}$) typical of technicolor coupled
models, and function of the dynamically generated technifermion mass and two
other parameters that describe the technifermion dynamical mass momentum
dependence. The limits imposed on this dynamics allow us to make a simple
determination of pseudo-Goldstone boson masses that appear in these theories,
indicating that these bosons may be expected to be quite massive.

##  1 Introduction

The Higgs boson discovery by the LHC was one of the major breakthrough of
particle physics in the last decades [1, 2]. With regard to this boson, there
is great experimental interest in the possible measurement of its trilinear
self-coupling ($\lambda_{HHH}^{SM}$) [3], as well as knowing whether it is a
fundamental or composite particle [4]. Any difference between the expected
value of the trilinear self-coupling predicted by the standard model (SM) and
that of a future measurement of this quantity may indicate a sign of
composition or new physics, although the composition or new physics may also
arise with the discovery of new particles. In particular, if this boson is
composed by new strongly interacting particles, the most discussed signal of a
possible dynamical breaking mechanism of the SM gauge symmetry would be the
presence of pseudo-Goldstone bosons [5].

Any limit on the Higgs boson trilinear self-coupling, if this is a composite
boson, also means a restriction on the dynamics of the interaction that forms
such a boson. This occurs because the trilinear coupling is directly
proportional to the wave function of the composite state and the number of
fermions that form that state. In this work we will compare the trilinear
Higgs boson self-coupling computed in the case of technicolor coupled models,
showing how the dynamics of the theory is constrained by the experimental data
on this quantity.

We review how the dynamics of coupled strongly interacting theories are
modified compared to an isolated strong interaction theory. In the sequence,
based on the dynamics of these coupled theories, that we assume as QCD and a
non-Abelian TC theory coupled by a non-Abelian ETC or GUT, we estimate the
order of the trilinear Higgs boson coupling. With the limits on the dynamics
(i.e. technifermion self-energy) originated from the comparison with the
experimental data, we are able to compute pseudo-Goldstone bosons masses in a
very simple approximation. The results indicate that these bosons can be quite
massive.

The Lagrangian describing the SM trilinear Higgs boson self-interaction is
parameterized as [3]

${\cal{L}}^{SM}_{HHH}=\frac{m_{H}^{2}}{2v}H^{3}\,,$ (1)

where the SM trilinear coupling with mass dimension is

$\lambda^{SM}_{HHH}=\frac{m_{H}^{2}}{2v}\,.$ (2)

whose SM expected value

$\lambda_{HHH}^{SM}\equiv\frac{m_{H}^{2}}{(2v^{2})}=0.129\,\,.$ (3)

The Lagrangian describing the observed trilinear Higgs boson self-coupling can
be written as

${\cal{L}}_{HHH}=\kappa_{\lambda}\lambda^{SM}_{HHH}vH^{3}\,,$ (4)

where

$\kappa_{\lambda}=\frac{\lambda_{HHH}}{\lambda_{HHH}^{SM}}\,\,,$ (5)

where $\kappa_{\lambda}$ is the observed coupling modifier of the trilinear
Higgs boson self-coupling. Recently the CMS Collaboration reported one
constraint on the observed coupling $\kappa_{\lambda}$ at $95\%$ CL [6]

$-3.3<\kappa_{\lambda}<8.5\,\,,$ (6)

This result can already constrain the dynamics of a composite Higgs boson in
the context of coupled technicolor models [7, 8, 9, 10], and can also be used
to determine limits on the possible masses of pseudo-Goldstone bosons.

##  2 Dynamics of technicolor coupled models

Technicolor coupled models are technicolor (TC) models where QCD and TC
theories are embedded into a larger gauge group, such that technifermions and
ordinary quarks provide masses to each other [7, 8]. In Ref. [7] it was
verified numerically that two strongly interacting theories when coupled by
another interaction, which could be an extended technicolor theory (ETC) or a
grand unified theory (GUT), have their self-energies (or dynamics) modified
when compared to the self-energy of an isolated strong interaction theory.

As the ETC/unified theory should also mediate the interaction of technileptons
and ordinary leptons with quarks and techniquarks, these fermions also acquire
smaller masses than their respective strongly interacting partners (i.e.
quarks and techniquarks) [8], but as we shall see technileptons also turn out
to be quite massive.

An isolated strong non-Abelian interaction is known to generate a dynamical
fermion mass indicated by $\mu$, which is of the order of $\Lambda$, that is
the characteristic scale of the strong interaction. The dynamical fermion
self-energy of this strong interaction theory has the following infrared
behavior (IR) [11, 12]

$\Sigma(p^{2}\rightarrow 0)\propto\mu\,\,,$ (7)

and the ultraviolet behavior (UV) is [13]

$\Sigma(p^{2}\rightarrow\infty)\propto\mu\left(\frac{\mu^{2}}{p^{2}}\right)\,\,.$
(8)

Figure 1: The coupled system of SDEs for TC (Q $\equiv$ technifermions) and
QCD (q $\equiv$ quarks) including ETC and electroweak or other corrections. G
(g) indicates a technigluon (gluon).

We can now consider two coupled strong interactions, QCD and TC, through an
ETC or GUT theory, where the Schwinger-Dyson equations (SDE) for the coupled
system is depicted in Fig.(1). The IR behavior of both theories is not changed
from the one of Eq.(7), where now $\mu$ for technifermions will be indicated
by $\mu_{tc}$ and for quarks by $\mu_{c}$, respectively the TC and QCD
dynamical fermion masses. However, as shown in Ref.[7, 8], the effect of QCD
and TC to technifermions and quarks is to provide “bare” masses to each other.
We stress this effect, that is promoted by the second diagram in the SDE of
Fig.(1) for technifermions. Actually, the effect of this diagram is exactly to
change the boundary conditions of the SDE in the differential form, just as it
would have if we had introduced a bare mass [9]. In this case the UV behavior
of the dynamical self-energy with a “bare” mass $\mu_{0}$ is given by [13]

$\Sigma(p^{2}\rightarrow\infty)\propto\mu_{0}\left[\ln\left(\frac{p^{2}}{\Lambda^{2}}\right)\right]^{-\gamma}\,\,.$
(9)

where $\gamma$ for a $SU(N)$ non-Abelian gauge theory with fermions in the
fundamental representation is

$\gamma=\frac{3(N^{2}-1)}{2N(11N-2n_{f})}\,\,,$ (10)

and $\Lambda$ is the characteristic scale of the theory. The logarithmic
behavior of Eq.(9) is connected to the running of the non-Abelian gauge
coupling constant.

Going back to the coupled SDE system we can notice that the IR behavior of the
technifermion self-energy is still proportional to $\mu_{tc}$, as long as we
assume no other new strong interaction above the TC scale, and the
technifermion bare masses generated by QCD are very small when compared to
$\mu_{tc}$. The actual TC self-energy UV behavior is a combination of a
$1/p^{2}$ component typical of an isolated TC theory, with the UV logarithmic
behavior given by Eq.(9) as soon as we have momenta larger than
$\mu^{2}_{tc}$, characterized by the domination of the QCD diagram to the
dynamical technifermion mass. Therefore, the full TC dynamical self-energy can
be roughly described by

$\Sigma_{tc}(p^{2})\approx\mu_{tc}\left[1+\delta_{1}\ln\left[(p^{2}+\mu_{tc}^{2})/\mu_{tc}^{2}\right]\right]^{-\delta_{2}}\,,$
(11)

Eq.(11) is the simplest interpolation of the numerical result of Ref. [7],
describing the infrared (IR) dynamical mass equal to $\mu_{tc}$ (also
proportional to the technicolor characteristic scale), and a logarithmic
decreasing function of the momentum in the ultraviolet (UV) region originated
by another (QCD, for instance) strong interaction. It is clear that in the IR
region the logarithmic term of Eq.(11) is negligible, and as the momentum
increases above $\mu_{tc}$ the logarithmic term controls the UV behavior.

It is worth to remember that at leading order the fermionic SDE has the same
behavior of the scalar Bethe-Salpeter (BS) equation, what was explicitly shown
in Refs. [14]. However, the full BS amplitude is subjected to a normalization
condition, which, considering Eq.(11), imposes the following constraint on
$\delta_{2}$ [13, 15, 16]

$\delta_{2}>\frac{1}{2}\,.$ (12)

On the other hand, just assuming that
$\Sigma(p^{2}=\mu_{tc}^{2})\approx\mu_{tc}$, and that the self-energy starts
decreasing smoothly for $p^{2}>\mu_{tc}^{2}$, we can assume

$\delta_{1}\leq 1\,\,.$ (13)

This value is also consistent with the expansion of a dynamical self-energy
(e.g. Eq.(9)) at large momentum, where $\delta_{1}$ would be proportional to
the running gauge coupling constant. Ultimately $\delta_{1}$ may have
contributions proportional to $[bg^{2}]_{si}$ where $b$ and $g$ are
respectively the first coefficient of the $\beta$ function and the coupling
constant of the strong interaction ($si$) that provides the “bare” mass to the
technifermions (see the appendix of Ref. [17] to verify the determination of
this quantity in the case of an isolated theory).

A consequence of a self-energy like the one of Eq.(11) is that TC coupled
models must incorporate a family symmetry, in such a way that technifermions
couple at leading order only to the third ordinary fermion family, whereas the
first fermionic family will be coupled at leading order only to QCD [7, 9,
10], i.e. the mass hierarchy between different ordinary fermionic generations
can only be obtained through the introduction of a family (or horizontal)
symmetry, as described in Refs.[7, 9, 10]. We will not touch these aspects
here, and in the following we just verify consequences of Eq.(11) for the
trilinear Higgs boson self-coupling and pseudo-Goldstone masses. The result
will be compared with the recent experimental constraint on the trilinear
Higgs boson coupling [6].

##  3 Trilinear coupling of a composite Higgs boson

Figure 2:  The trilinear composite scalar coupling: The dark (blue) blobs in
this figure represent the coupling of composite Higgs bosons(H) to
fermions(f). The double lines represent the composite Higgs bosons. The full
diagram is the main contribution to the trilinear Higgs boson self-coupling

The trilinear composite scalar coupling is shown in Fig.(2), where the double
lines represent the composite Higgs boson, that is coupled to fermions (single
line) through the dark (blue) blobs. In the SM the composite scalar boson
coupling to fermions (the dark blob) can be determined using Ward identities
to be [18]

$G^{a}(p+q,p)=-\imath\frac{g_{W}}{2M_{W}}\left[\tau^{a}\Sigma(p)P_{R}-\Sigma(p+q)\tau^{a}P_{L}\right]\,,$
(14)

where $P_{R,L}=\frac{1}{2}(1\pm\gamma_{5})$, $\tau^{a}$ is a $SU(2)$
generator, and $\Sigma$ is a matrix of fermionic self-energies in weak-
isodoublet space. At large momenta Eq.(14) is quite well approximated by
$G(p,p)$, and in all situations in which we are interested
$\Sigma(p+q)\approx\Sigma(p)$. Therefore, the coupling given by Eq.(14) that
is dominated by the large momentum running in the loop of Fig.(2) is reduced
to

$\lambda_{Hff}\equiv G(p,p)\sim-\frac{g_{W}}{2M_{W}}\Sigma(p^{2})\,.$ (15)

The loop calculation of Fig.(2), considering Eq.(15) and $n_{F}$
technifermions running in that loop, is given by [19]

$\lambda_{HHH}=\frac{3g^{3}_{W}}{64\pi^{2}}\left(\frac{3n_{F}}{M^{3}_{W}}\right)\int_{0}^{\infty}\frac{\Sigma_{tc}^{4}(p^{2})p^{4}dp^{2}}{(p^{2}+\Sigma_{tc}^{2}(p^{2}))^{3}}\,.$
(16)

Note that, apart a dependence on $n_{F}$, the trilinear coupling is a function
of the variables $\delta_{1}$ and $\delta_{2}$ shown in Eq.(11). Of course, we
do also have a dependence on the scale $\mu_{tc}$, but we cannot forget
another constraint on the technicolor dynamics that comes from

$M_{W}=\frac{1}{2}g_{W}F_{\pi}\,\,,$ (17)

where $F_{\pi}$ is the technipion decay constant, $g_{W}$ is the electroweak
coupling constant, and $F_{\pi}$ can be calculated through [20]

$F_{\pi}^{2}=\frac{N}{(2\pi)^{2}}\int_{0}^{\infty}dp^{2}\frac{p^{2}\left[\Sigma_{tc}^{2}(p^{2})-\frac{1}{2}p^{2}\frac{\Sigma_{tc}(p^{2})}{dp^{2}}\Sigma_{tc}(p^{2})\right]}{[p^{2}+\Sigma_{tc}^{2}(p^{2})]^{2}}\,\,.$
(18)

Therefore, once the number of technicolors ($N$) and technifermions
($n_{F}=2n_{d}$) are specified (where $n_{d}$ is the number of weakdoublets),
the dynamics of the technicolor theory (i.e. $\delta_{1}$ and $\delta_{2}$)
can be constrained using Eqs.(6), (12), (13), (16), (17) and (18).

Eq.(16) was already calculated in Ref. [19] with a different approximation for
Eq.(11). In that case the self-energy was based on a possible walking behavior
[21], where a certain amount of the $1/p^{2}$ behavior for this quantity was
allowed. Moreover the parameter $\delta_{1}$ was chosen in an arbitrary way as
$bg^{2}$, what in a coupled TC scenario does not make sense, due to the many
corrections that may contribute to the $\delta_{i}$ parameters.

##  4 Limit on the trilinear coupling

Figure 3: $3$-dimensional plot of the technipion decay constant ($F_{\pi}$)
given by Eq.(18). This quantity is a function of $(\delta_{1},\delta_{2},N)$,
and we considered $\mu_{tc}$ in the interval $0.5TeV\leq\mu_{tc}\leq 2TeV$.
The yellow region is the allowed one.

In Fig.(3) we present the 3D plot of the technipion decay constant ($F_{\pi}$)
given by Eq.(18). The plot was generated for $F_{\pi}=v/\sqrt{3}$, with
$v=\sqrt{n_{d}}F_{\pi}=246GeV$ assuming $n_{d}=3(n_{F}=6)$ and the following
range of technicolor dynamical masses $0.5TeV\leq\mu_{tc}\leq 2TeV$. The
dependence of the technipion decay constant on $\mu_{tc}$ is not appreciable.
However, there is a large parameter space for the quantities
$(\delta_{1},\delta_{2},N)$ that satisfy the experimental $F_{\pi}$ value. The
main relevant fact is the variation of this quantity with $N$ (the number
associated to the technicolor gauge group). For instance, the figure above
illustrates that in the region where $N\leq SU(5)_{tc}$, we still have a large
volume allowed for $\delta_{1}$ and $\delta_{2}$.

Considering Eqs.(5),(12), (13), (16) and (17), in Fig.(4) we present the
behavior obtained for Eq.(5), calculated assuming the dynamics prescribed in
Eq.(11), $\mu_{tc}=1TeV$ and $n_{f}=2$. We also include in the figure the
upper limit on the observed coupling modifier ($\kappa_{\lambda}$) of the
trilinear Higgs boson self-coupling of Ref. [6], which is indicated by the
dotted-dashed black line.

Figure 4: The region of allowed $(\delta_{1},\delta_{2})$ values obtained for
the coupling modifier $\kappa_{\lambda}$. In this figure we consider
$\mu_{tc}=1TeV$ and $n_{f}=2$, furthermore we assume $N=2$ which allows the
largest region of parameters bounded by Eq.(18). The expected SM value is also
indicated by a continuous line.

In the filled region below the dotted line it is shown the
$(\delta_{1},\delta_{2})$ parameter space allowed by the experimental
constraint on $\kappa_{\lambda}$, which in this case corresponds to
$\delta_{1}\geq 0.074$ and $\delta_{2}\geq 0.53$. In the Fig.(5) we consider
the case where $n_{f}=4$, which is a little bit more restrictive than the
previous one.

Figure 5:  The allowed region of $(\delta_{1},\delta_{2})$ values obtained for
the coupling modifier $\kappa_{\lambda}$. We consider again $\mu_{tc}=1TeV$,
$N=2$ and now we set $n_{f}=4$.

The case corresponding for $n_{f}=6$ is described in Fig.(6). Table 1
summarizes the $(\delta_{1},\delta_{2})$ parameter region allowed by the
observed coupling $\kappa_{\lambda}$ reported by the CMS experiment, and
define the lower limits for $(\delta_{1},\delta_{2})$. Note that we have not
considered $\delta_{2}$ values larger than $2$, which is reasonable if the UV
behavior of the TC self-energy is dominated by QCD with $6$ quarks, although
other corrections to the coupled non-linear SDE system may modify this
quantity.

Figure 6: The allowed region of $(\delta_{1},\delta_{2})$ values obtained for the coupling modifier $\kappa_{\lambda}$, with $\mu_{tc}=1TeV$, $N=2$ and setting $n_{f}=6$.  Table 1:  Parameter region allowed for the technicolor self-energy dynamics given by Eq.(11) (i.e. the $\delta_{1}$ and $\delta_{2}$ values) constrained by the observed coupling $\kappa_{\lambda}$ reported by CMS for $n_{f}=2,4,6$. $n_{F}$ |  $\delta_{1}\geq$ |  $\delta_{2}\geq$ |  $v/F_{\pi}$
---|---|---|---
2 | $0.074$ | $0.53$ | $1$
4 | $0.115$ | $0.72$ | $\sqrt{2}$
6 | $0.145$ | $0.83$ | $\sqrt{3}$

The CMS upper bound on $\kappa_{\lambda}$ is indicated in the above figures by
a dotted-dashed line and is already constraining the dynamics of composite
coupled models for the Higgs boson.

We do not expect major changes in our results in the case of technifermions in
higher dimensional representations, because the parameters $\delta_{1}$ and
$\delta_{2}$ are proportional to to the product of the Casimir operator of a
given representation times the TC coupling constant, and according to the most
attractive channel (MAC) hypothesis the TC chiral symmetry breaking occurs
when this product is of $O(1)$ no matter the representation.

##  5 Pseudo-Goldstone boson masses

In technicolor models it is usual to have a large number of pseudo-Goldstone
bosons (or technipions) resulting from the chiral symmetry breaking of the
technicolor theory. In coupled models like the ones discussed in Refs. [8] and
[10], these technipions, besides the ones absorbed by the $W$’s and $Z$ gauge
bosons, will be of the following type:
a) Charged and neutral color singlets, for example,

$\bar{U}_{i}D^{i}-3\bar{N}E\,,$
$\bar{U}_{i}U^{i}-\bar{D}_{i}D^{i}-3(\bar{N}N-\bar{E}E)\,,$

b) Colored triplets, for example,

$\bar{E}U\,,$

c) Colored octets, for example

$\bar{U}\frac{\lambda^{a}}{2}U\,,$

where $\lambda^{a}$ is a Gell-Mann matrix. The colored triplet and colored
octet technipions may be labeled as $\Pi^{(3)}$ and $\Pi^{(8)}$.

Considering the parameter space of $\delta_{1}$ and $\delta_{2}$ values
allowed by CMS results shown in Table 1, we can discuss what happens with the
limits on the masses for the lightest pseudo-Goldstone bosons expected in the
TC coupled scenario when we use the numbers of that table and Eq.(11) to
compute technifermion masses. The heaviest pseudo-Goldstone bosons carry color
once they have large radiative corrections from QCD, while others may have
only electroweak corrections to their masses. In the coupled scenario the
lightest technifermion will be the neutral one $(N)$. Apart from TC quantum
number the technifermion $N$ has the same quantum numbers of the ordinary
neutrino. Its mass appears due to the diagrams of Fig.(7) in models like the
ones of Ref. [8, 10].

Figure 7:  Contributions to the neutral technifermion mass in the coupled TC
scheme.

The diagram (a) of Fig.(7) provides the usual dynamical TC mass to $N$.
Remembering that it is the diagram ($a_{2}$) of Fig.(1) that modifies the
running of the $N$ technifermion self-energy, wich turn out to be logarithmic
due to the coupling to the QCD self-energy. The diagram (b) of Fig.(7), in
models like the ones of Ref. [8, 10], corresponds to the ETC correction for
$m_{N}$ due to the quark $b$, however, it can be disregarded since
$m_{b}<<\mu_{tc}$. The third diagram of Fig.(7) involves the TC condensate and
a weak correction, and this contribution is independent of any specific ETC
model. In a more general scenario, ETC gauge bosons can generate corrections
similar to that of Fig. (7c), which will not be taken into account in the
present work, since we just intend to present simple limits on the spectrum of
the lightest pseudo-Goldstone bosons that can eventually be produced in the TC
coupled scenario.

Considering Eq.(11), the technilepton ($N$) current mass due to Fig.(7c) can
be estimated. The diagram was calculated at one ETC energy scale
$\Lambda_{ETC}\approx\Lambda_{GUT}$ where
$\alpha_{w}\approx\alpha_{ETC}\approx\alpha_{GUT}\approx 0.032$, and the
result is given by

$\displaystyle
m_{N}\approx\frac{3\alpha_{w}}{4\pi}\frac{\mu_{tc}}{\delta_{1}\delta_{2}}-\frac{3\alpha_{w}\mu_{tc}}{4\pi}\ln(\frac{M^{2}_{Z}}{\mu^{2}_{tc}})$
(19)

Based on this estimate, assuming the limits described in Table 1, as well as
$\mu_{tc}=1TeV$ and $M_{Z}=91.2GeV$ we obtain

$\displaystyle m_{N}\approx 231.4GeV\,\,,\,\,(n_{F}=2)$ $\displaystyle
m_{N}\approx 151.29GeV\,\,,\,\,(n_{F}=4)$ $\displaystyle m_{N}\approx
100GeV\,\,,\,\,(n_{F}=6)$ (20)

The above results for $m_{N}$ follow from the upper limit on
$\kappa_{\lambda}$ reported by CMS and $\delta_{1}$ and $\delta_{2}$ values
presented in Table 1. These are the $m_{N}$ masses obtained in the case of
$(2\leq n_{F}\leq 6)$. However, note that for a realistic ETC model, where new
interactions including $N$ and ETC bosons are accounted, we shall obtain even
higher $m_{N}$ masses. It is important to stress that all other corrections to
colored or charged technifermion masses are larger than this one due to the
larger charges and coupling constants (basically changing $\alpha_{w}$ by
$\alpha_{s}$ and $M_{Z}$ by a dynamical gluon mass in Eq.(19)).

As neutral technifermions may have masses heavier than $100$ GeV we can
determine the mass of the lightest pseudo-Goldstone composed with this neutral
particle ( for instance, $\Pi^{N}\rightarrow{\bar{N}}\gamma_{5}\tau^{i}N$,
where $i$ indicate electroweak indexes). This neutral pseudo-Goldstone boson
will obtain a mass that may be computed with the help of the Gell-Mann-Oakes-
Renner relation

$m_{\Pi}^{N}\approx\sqrt{m_{N}\frac{\left\langle{\bar{N}}N\right\rangle}{2F_{\Pi}^{2}}}\,,$

where $\left\langle{\bar{N}}N\right\rangle\approx(\mu_{tc})^{3}$GeV3 is the TC
condensate. However, we may follow a very simple hypothesis, where the pseudo-
Goldstone masses are determined just as the addition of the current masses of
their constituents [22, 23], which was shown to be satisfactory for QCD
phenomenology. In this case, supposing that the neutral technipion ($\Pi^{N}$)
is composed just by two $N$ particles we have

$m_{\Pi^{N}}\approx 200\,-\,460\,GeV\,.$ (21)

Notice that we assumed that such neutral boson is solely composed by $N$
technifermions. In general the composition is more complex according to the
symmetries of the TC group, and this neutral boson will also be composed by
charged and colored particles increasing the above estimate.

Charged and colored technifermions will not only have larger masses than the
neutral technifermion, but also more radiative corrections to their masses,
and we can expect even larger masses for colored and charged pseudo-Goldstone
bosons. For instance, following the same hypothesis, the colored triplet and
colored octet technipions $\Pi^{(3)}$ and $\Pi^{(8)}$ will obtain masses

$m_{\Pi^{(3)}}\approx m_{U}+m_{E}\,\,,$ (22)

where $m_{U}$ and $m_{E}$ are the current masses of the $U$ and $E$
techniquarks. Along the same proposal a simple estimate of the colored octet
technipion of item c) would be

$m_{\Pi^{(8)}}\approx 2m_{U}\,.$ (23)

Changing the weak coupling by the QCD one in the calculation of the $N$
technifermion mass in order to estimate the $U$ and $E$ masses, we can predict
$\Pi^{(3)}$ and $\Pi^{(8)}$ masses certainly to be above $400$ GeV, only with
the naive assumption the the strong coupling constant is at least twice the
value of the weak one at the TC scale.

##  6 Conclusions

In technicolor coupled models, where TC and QCD are embedded into a large
gauge theory, technifermions and ordinary fermions provide bare masses to each
other. In this case the self-energy dynamics of technifermions can be
described by Eq.(11), as verified in Refs. [7, 9].

With the technifermion self-energy given by Eq.(11) we have computed the
trilinear self-coupling of a composite Higgs boson. This calculation is
compared to the recent limits on this coupling obtained by the CMS experiment.
The comparison with the experimental data can constrain the trilinear coupling
and consequently the dynamics of the TC theory. Once the TC scale ($\mu_{tc}$)
is specified we can obtain limits on the variables $\delta_{1}$ and
$\delta_{2}$ of Eq.(11) describing the TC self-energy. Our main result is that
the recent experimental data about the trilinear Higgs boson self-coupling is
already imposing limits on the TC dynamics, although it is still far from the
expected SM value for this quantity. The Higgs boson coupling has been
determined with high precision in the case of heavy fermions, and it would be
interesting to verify how the composite wave-function (i.e. self-energy)
discussed here is affected by these experimental limits, although in this case
the calculation is much more dependent on the ETC/GUT masses and horizontal
symmetries necessaries for this type of model.

After obtaining a constraint on the parameters of the TC self-energy for one
specific TC scale and number of technifermions we can calculate the
technifermion bare masses. With the values of Table 1, a technicolor mass
scale around $1$ TeV, and assuming the simple hypothesis of Refs. [22, 23],
where the pseudo-Goldstone boson masses are roughly given by the sum of the
particle masses that participate in the boson composition, we can estimate
that pseudo-Goldstone boson masses. If these models are realized in Nature,
the pseudo-Goldstone boson masses may be at the order or above $0.5$ TeV.

###### Acknowledgements.

This research was partially supported by the Conselho Nacional de
Desenvolvimento Científico e Tecnológico (CNPq) under grants No 303588/2018-7
(A.A.N.) and 310015/2020-0 (A. D.).

## References

  * [1] ATLAS Collaboration, Phys. Lett. B 716, 1 (2012).
  * [2] CMS Collaboration, Phys. Lett. B 716, 30 (2012).
  * [3] S. Chang and M. A. Luty, JHEP 03 (2020) 140.
  * [4] G. Cacciapaglia, C. Pica and F. Sannino, Phys. Rept. 877, 1 (2020).
  * [5] B. Bellazzini, C. Csaki and J. Serra, Eur. Phys. J. C 74, 2766 (2014).
  * [6] CMS Collaboration, “Search for nonresonant Higgs boson pair production in final states with two bottom quarks and two photons in proton-proton collisions at $\sqrt{s}=$ 13 TeV”, axXiv:2011.12373.
  * [7] A. C. Aguilar, A. Doff and A. A. Natale, Phys. Rev. D 97, 115035 (2018).
  * [8] A. Doff and A. A. Natale, Phys. Rev. D 99, 055026 (2019).
  * [9] A. Doff and A. A. Natale, Eur. Phys. J. C 78, 872 (2018).
  * [10] A. Doff and A. A. Natale, Eur. Phys. J. C 80, 684 (2020).
  * [11] V. A. Miransky,Dynamical Symmetry Breaking in Quantum Field Theories, World Scientific co, (1993).
  * [12] C. D. Roberts, Few Body Syst. 58, 1 (2017).
  * [13] K. Lane, Phys. Rev. D 10, 2605 (1974).
  * [14] R. Delbourgo and M. D. Scadron, Phys. Rev. Lett. 48, 379 (1982).
  * [15] S. Mandelstam, Proc. R. Soc. A 233, 248 (1955).
  * [16] C. H. Llewellyn Smith, Il Nuovo Cimento A 60, 348 (1969).
  * [17] J. M. Cornwall and R. C. Shellard, Phys. Rev. D 18, 1216 (1978).
  * [18] J. Carpenter, R. Norton, S. Siegemund-Broka and A. Soni, Phys. Rev. Lett. 65, 153 (1990).
  * [19] A. Doff and A. A. Natale, Phys. Lett. B 641, 198 (2006).
  * [20] H. Pagels and S. Stokar, Phys. Rev. D 20, 2947 (1979).
  * [21] K. Yamawaki, Prog. Theor. Phys. Suppl. 167, 127 (2007).
  * [22] M. D. Scadron, F. Kleefed and G. Rupp, EPL 80, 51001 (2007).
  * [23] M. D. Scadron, R. Delbourgo and G. Rupp, J. Phys. G 32, 735 (2006).