the graph transformation, all vertices from $\mathcal{B}_{i}$ causing an edge
to appear can be stored, as illustrated in Figure 7.2. Nonetheless, in this
setting, no external information about $u$, $v$, or any vertex from
$\mathcal{B}_{i}$ is available. For this purpose, we designed a set of
graphical features that can be directly computed from bipartite graphs and
their transformations. They are summarized in Table 7.1 and can be either
precomputed during the construction of a transformed graph, or computed on
demand in linear time with respect to the number of vertices in a bipartite
graph at worst. All features apart from label of the neighbor obtained from
the blacklist $v\in L$, which is binary, are in range $[1,\infty)$, and are
further transformed with mapping $x\mapsto\log(x)+1$. For the label, we used
one-hot encoding. This feature mapping is an example of mapping $h$ as
explained in Section 3.2.1, which in this case maps from edges in a
transformed graph to a Euclidean space of dimension $9$. Table 7.1:
Specification of graphical features used in experiments to describe edge
$\mathopen{}\mathclose{{}\left\\{u,v}\right\\}$, where $v$ is the current
vertex for inference. $\mathcal{G}$ and $G$ denote bipartite and transformed
graphs, and $\mathcal{N}_{\mathcal{G}}(v)$ and $\mathcal{N}_{G}(v)$
neighborhoods of $v$ in $\mathcal{G}$ and $G$, respectively. feature
definition property of
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{G}(v)}\right|$ $v$
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(v)}\right|$ $v$
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)}\right|$ $u$
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)\cap\mathcal{N}_{\mathcal{G}}(v)}\right|$
{$u$, $v$}
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)\cup\mathcal{N}_{\mathcal{G}}(v)}\right|$
{$u$, $v$} ${\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)\cap\
\mathcal{N}_{\mathcal{G}}(v)}\right|}/{\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)\cup\
\mathcal{N}_{\mathcal{G}}(v)}\right|}$ {$u$, $v$}
$\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(u)}\right|\mathopen{}\mathclose{{}\left|\mathcal{N}_{\mathcal{G}}(v)}\right|$
{$u$, $v$} $u\in L$ $u$

####  7.2.4 Method merits

Using the method, we are able to learn merely from the behavior of the objects
of interest in any system (e.g. computer network). This is done by a set of
simple and efficiently computable features, which are obtained simply from
input graphs representing interactions. We claim that this ‘relation-based’
representation generalizes better as well and adapts well in rapidly changing
environments. In the experiments below, we add more relations than only
domain-client and domain-binary relations. Besides others, we also used
domain-TLS authority, which assigns to each SLD a certificate authority that
issued its TLS certificate. One possibility to model the fact that an SLD uses
a certificate issued by an authority is to use one-hot encoding. However, this
may lead to overparametrization once the set of authorities becomes too large.
Moreover, this approach also does not allow for the future, when new
authorities may arise—to capture this occurrence, one needs to either resize
the one-hot encoded vector, thus having to retrain all models on new data, or
unify all entities arising in the future into one class, which leads to
information loss. Also, if the adversary changes the authority for their
malicious domains, but everything else stays the same, the model will obtain a
different input in the feature-based approach. Instead, if relations are
modelled, the transformed graph will in this case contain a clique consisting
of all SLD s with a certificate obtained from the same authority. If the
adversary changes the authority used, the clique remains intact. With the
proposed approach, one can smoothly transition between two different
approaches to learning, the first one based on collecting ‘hard’ data about
entities in the form of features (or structured raw data in case of HMill),
and the second one based on simply describing relationships between entities.
Both approaches can be arbitrarily combined using the same tools from the
framework, independently on the circumstances and the nature of available
data. For example, in the computer security domain, informative features are
either hard to define or unobservable, however, as discussed later, binary
relations are easily obtainable and require no feature engineering. If on the
other hand, information about vertices or edges is available, modelling
structured data with HMill is simple, as discussed earlier. Also, the issue of
missing data, which in this case can happen, when the current vertex $v$ is
not present in some of input bipartite graphs, is solved. All these properties
lead to a richer and more accurate description of the application domain and
consequently, higher accuracy of learned models. Finally, due to the fact that
a bag may contain an arbitrary number of instances, the method is designed to
deal with any degree distribution in the graph. This is a substantial
difficulty in the transformed graphs, where the size of the neighborhood of a
domain varies greatly for different vertices. For instance, frequently visited
SLD s are neighbors of a majority of vertices in the transformed domain-client
graph. Thanks to the relative simplicity of graphical features and their
effective computation, together with the possibility to use importance
sampling technique, a (weighted) bag data vertex representation of
neighborhoods are obtained fast, and we can perform inference on graphs with a
large number of vertices and edges. In our previous work [Mandlík, 2018], we
consider a less general setting, where only one bipartite graph is on the
input ($n=1$), whereas here, we extend this approach to work with multiple
graphs. On the other hand, the cited work provides more details on a domain-
specific graph pruning techniques and evaluation methodology, both applicable
here as well.

###  7.3 Modelling Internet communication (use case)

In this section, we demonstrate how the proposed method performs on the real-
world task of extending a known blacklist of (second-level) domains by
modelling Internet communication. The problem specifics are huge input
bipartite graphs, heavy-tailed degree distributions in transformed graphs, and
a very low ratio of positive domains with respect to the total number.

####  7.3.1 Data description

The data was kindly provided by Cisco Cognitive Intelligence and describes
relations between (second-level) domains and other network entities in several
bipartite graphs. Three following relations, two of which were used for the
examples above, were collected from a subset of anonymized web proxy (W3C)
logs processed by Cisco Cognitive Intelligence111https://cognitive.cisco.com,
and Cisco AMP
telemetry222https://www.cisco.com/c/en/us/products/security/advanced-malware-
protection/index.html: • domain-client — an edge signifies that a client has
communicated with (issued an HTTP/HTTPS request to) the domain. • domain-
binary — an edge indicates that a process has communicated with a given
domain. • domain-IP address — an edge signifies that the domain hostname was
resolved to the IP address using DNS. These relations are of the many-to-many
(M2M) cardinality type meaning that one domain may be connected with an edge
to multiple clients/binaries/IP s and vice versa. All bipartite graphs
representing these relations were constructed from interactions observed
during one week. Bipartite graphs collected during the same week were linked
into the same dataset, and we identify them by a starting date of the time
window. Hence, here we call a ‘dataset’ a collection of bipartite graphs, each
for one relation. During three months of year 2019, we assembled twelve
datasets altogether—05-23, 06-03, 06-10, 06-17, 06-24, 06-26, 06-27, 07-01,
07-08, 07-15, 07-22 and 07-29. The model was first trained on a subset of
these dates, and then labels were inferred for domains from the remaining
dates and the performance was evaluated. Specifically, we used 06-10, 06-27
and 07-22 for testing, 06-24 for validation, and the rest for training. The
datasets were further enriched with following three relations (bipartite
graphs) extracted from fields in (the latest) TLS certificate issued to the
domain333more specifically one of its hostnames: • domain-TLS issuer — a
relation connecting domains to the issuer of the TLS certificate. The
cardinality type is many-to-one (M2O) and therefore the transformed graph
contains a fully connected component for each of the issuers. • domain-TLS
hash — a M2O relation connecting a domain to the hash of the TLS certificate.
In the transformed graph, domains using the same certificate are connected. •
domain-TLS issue time — domain and the time when validity period of the
certificate starts, stored as a Unix timestamp. Lastly, we also leveraged
information publicly available in WHOIS registries, and extracted relations
domain-WHOIS email, domain-WHOIS nameserver, domain-WHOIS registrar name,
domain-WHOIS country, domain-WHOIS registrar id, and domain-WHOIS timestamp.
All of these are of the M2O cardinality type. For further information, please
refer to the WHOIS specification. Thus, we had twelve datasets altogether,
each containing eleven bipartite graphs. All relations used in our experiments
are summarized with several examples in Table D.4 in Appendix D. To gain an
idea about the size of the input graphs, we provide Tables D.1 and D.2 in
Appendix D. On average, the bipartite graphs we are dealing with contain
around $7\cdot 10^{6}$ vertices and $3\cdot 10^{8}$ edges. On the first three
relations mentioned (domain-client, domain-binary and domain-IP), the pruning
preprocessing step was performed as described in [Mandlík, 2018]. A blacklist
of malicious domains, $L,$ was also provided by Cisco Cognitive Intelligence.
At the time of data collection, the blacklist tracked $335$ malicious
campaigns, each representing a different threat type, such as ransomware,
trojans or click frauds. For each dataset, we used the current version of
blacklist available at the time to reflect the real situation. Around five
hundred domains from the blacklist were observed during each of the weeks:
this is due to the fact that many domains did not appear in any communication
during the week-long time window. All domains outside of the blacklist were
considered benign. Precise numbers of malicious domains in each of the
datasets together with ratios to all observed domains are listed in Table D.3
in Apendix D.

####  7.3.2 Experimental setting

For this experiment, we have decided to train a model for performing only one-
step inference in each of the transformed graphs. Firstly, in cybersecurity
transformed graphs are dense with a lot of cliques due to vertices of large
degrees in bipartite graphs. As a result, neighborhoods of vertices in the
transformed graph are huge, and it is possible to traverse between two
arbitrary vertices in several hops. It has also been discussed in [Yu et al.,
2010] that malicious entities in computer networks tend to form dense
communities. For these reasons, we believe that one-step inference is
sufficient for this task and leave the exploration of multi-step inference for
future work. Secondly, the model for one-step inference in this task has a
less complicated structure compared to models for both previous use cases in
this thesis. This enables us to further investigate to which extent the
results depend on the architecture of inner neural network components, which
we have so far always defined using a trivial procedure. Every sample tree was
constructed in the same way as illustrated in Figure 7.3. A product data node
is used to merge together multi-modal information contained in transformed
graphs. Each instance in a bag-data-node representation of neighborhoods is
described by an array data node with a vector of real-valued features from
Table 7.1. As a result, every sample tree and also every corresponding model
tree has a depth of three. Let us now turn our attention to the model’s
architecture. Recall that the topmost product model node in the corresponding
model will consist of eleven model (sub)trees, each for processing one of the
transformed graphs, and one more mapping we denote here by $f$ that is applied
on the concatenation of results from each of the submodels. This is
illustrated in Figure 7.4. Each of the submodels
$f_{pm}^{(1)},f_{pm}^{(2)},\ldots,f_{pm}^{(11)}$ itself is a bag model node,
consisting of an instance model $f_{I}^{(i)}$, an aggregation function
$g^{(i)}$ and a bag model $f_{B}^{(i)}$. Instances models $f_{I}^{(i)}$ are in
this case array models for the initial transformation of graphical features
with neural-network mappings $f_{am}^{(i)}$. Figure 7.4: A tree structure of
models used in this use case. Colors distinguish distinct submodels. See text
for details. For simplicity, we have defined all bag model nodes
$f_{pm}^{(i)}$ in the same way. This means that all $f_{am}^{(i)}$ and
$f_{B}^{(i)}$ are neural-network components with constant architecture across
different indexes $i$. However, parameters are not shared so that each bag
model node can learn different representations. We constructed three distinct
models—a ‘baseline’ model $m_{b}$, a ‘wider’ model $m_{w}$, and a ‘deeper’
model $m_{d}$. Numbers of neurons in layers of components $f_{am}^{(i)}$ and
$f_{B}^{(i)}$ for each $i$, as well as $f$ in the topmost product model node,
are in Table 7.2. For activation functions, we used again $\tanh$ in last
layers before aggregations $g^{(i)}$, and $\operatorname{ReLu}$ otherwise. For
aggregations $g^{(i)}$, we used a concatenation of all four functions
presented in Section 4.2. Table 7.2: Numbers of neurons in models $m_{b}$,
$m_{w}$ and $m_{d}$. Each number in tuples represent one feedforward layer
with the given number of neurons. The length of the tuple specifies a number
of layers in the component. Note that all neural-network components
$f_{am}^{(i)}$ contain $9$ input neurons, which corresponds to an input
dimension for edge (instance) representation. Also, the first layer of
$f_{B}^{(i)}$ contains four times as many neurons as the last layer of
$f_{am}^{(i)}$, which is due to a concatenation of four aggregation functions.
The input layer of $f$ is eleven times wider than the output layer of
$f_{B}^{(i)}$, because there are eleven relations altogether. model
$f_{am}^{(i)}$ $f_{B}^{(i)}$ $f$ $m_{b}$ $(9,30,30)$ $(120,60,20)$
$(220,100,2)$ $m_{w}$ $(9,60)$ $(240,120)$ $(1320,2)$ $m_{d}$
$(9,15,15,15,15)$ $(60,60,30,20)$ $(220,60,60,2)$ For various reasons, it may
happen that for a particular domain some relations are not available at all,
or the domain has no neighbors in some of the transformed graphs. This leads
to empty bags, which we handle as described in Section 4.3. On the other hand,
as some of the bags may be very large (millions of instances), we also
employed a sampling procedure (Section 4.1). Because positive domains usually
emit a stronger signal, and there is also a very low number of malicious
domains in input graphs, we include all edges incident to positive vertices to
the bag representing the neighborhood of $v$. From instances corresponding to
edges incident to a negative neighbor of $v$, we sample $K$ instances without
replacement and put them to the bag as well. Of course, all instances are
appropriately reweighted again. In all experiments presented here, we set
$K=100$.

We used weighted binary cross entropy (6.6) for loss function, Adam [Kingma
and Ba, 2014] optimizer with the default parameters, the Glorot normal
initialization [Glorot and Bengio, 2010] for weights, and zero initialization
for biases. During training, we first loaded one of the eight datasets (dates)
for training into the memory, and sampled one thousand balanced minibatches
each containing $256$ vertices (sampled without repetition). After all
minibatches were processed by the model, we loaded another dataset and
repeated the whole process, until this was done for each of the training
datasets five times.

##### Evaluation metrics

Recall that the primary goal of the proposed method is to find unknown
malicious domains not present in the blacklist $L$. To simulate this goal as
realistically as possible, one has to be aware of the interdependence between
domains while splitting the blacklist into a part disclosed to the classifier
and a part tested on. Moreover, the split should reflect the situation in
real-life, when some recently registered or simply hard-to-detect domains are
not in the blacklist, but appear on the input. As malicious domains tend to
group into dense clusters (communities) of the same family (malware campaign),
it is less complicated to merely extend a cluster of known domains than to
discover a completely unknown family. Taking all of the above into account, we
use the following procedure to evaluate performance. Once the training on the
whole blacklist is finished, we first randomly split domains in each blacklist
cluster into $k$ disjunctive parts of approximately the same size. Then, the
whole blacklist is divided into $k$ folds, always using one of the parts for
every threat category. This yields $k$ disjunctive folds and every threat
category is represented equally frequently in each of the folds. The accuracy
of the method is estimated from $k$ separate inference runs in each of which
one of the folds is left out and the remaining $k-1$ folds are used as tips
(seeds). With this procedure, we obtain an estimate of the maliciousness for
all domains in the blacklist—the estimate is taken from the only inference run
when the domain was not seeded. For domains that are not in the blacklist and
therefore treated as benign, $k$ estimates of the maliciousness are acquired,
one from each of $k$ runs. These were aggregated with maximum function, which
corresponds to the worst case. Eventually, each domain is assigned a single
scalar value, which can be subsequently used in the standard evaluation of the
performance of a binary classifier. Here, this is realized with PR and
($\log$) ROC curves. For more elaborate discussion on evaluation in these
circumstances and blacklist seeding procedure, please refer to [Mandlík,
2018].

####  7.3.3 Experimental results

We will now present the results we achieved with our models $m_{b}$, $m_{w}$,
$m_{d}$ in different circumstances. The experimental setting (training
procedure, hyperparameters, initialization and others) is the same in every
section unless stated otherwise. Recall, that we used eight datasets (dates)
for training and three for testing. For every model and every dataset, we plot
a PR curve and an ROC curve with logarithmically scaled $x$-axis. We do not
show ROC curves with linear $x$-axis, as in this problem they offer little to
none insight. However, both AUPRC and AUROC are provided. Full results can be
found in Appendices D.1, D.2, D.3, and D.4.

##### Comparison to PTP

In the first experiment, we compare to the PTP method. We used the
implementation from the Cisco Cognitive Intelligence pipeline, which performs
$20$ iterations of the algorithm. Further details are in [Jusko, 2017]. The
PTP method expects only on a single (bipartite) graph and no extensions for
multiple input graphs are known. To achieve a fair comparison, we used in this
experiment only the domain-client bipartite graph, even though the ability to
handle more such graphs is one of the main advantages of the proposed HMill-
based approach. For this purpose, we define another three models $m_{B}$,
$m_{W}$, and $m_{D}$, which are built in the same way as $m_{b}$, $m_{w}$ and
$m_{d}$, respectively, however, their topmost product model node contains only
one child for the domain-client graph processing instead of the original
eleven children. Judging from the results listed in Table D.5  and Figures D.1
and D.2 , it is safe to say that the proposed method performs at least as well
as the PTP algorithm and even surpasses it by a larger margin in some cases.
Note, however, that as we explained in Section 6.3.3, the difference (measured
by the AUPRC metric) between the best-performing model $m_{W}$ and other
models is not that significant, since a lot of area is measured in rather
irrelevant parts of the plotted curve. The differences in the AUROC are
minuscule. We further discuss the influence of ‘baseline’, ‘wide’, and ‘deep’
architectures in the next section.

##### Additional relations

In Table D.6  and Figures D.3  and D.4 , we present the results of the HMill-
based inference performed by models $m_{b}$, $m_{w}$ and $m_{d}$, this time
using all eleven relations. For evaluation, we used only domains from the
domain-client graph, using the remaining ten relations merely to enrich
information about these domains. This way, we can compare the results to the
instance of the experiment presented in the previous section. Nevertheless,
with the proposed method we can obtain estimates of the maliciousness for
every domain ever observed (denoted above by $\mathcal{A}$), since when a
domain is not present in the domain-client graph (or any other graph), we
treat this information as a missing value and HMill copes with it. With more
data, models perform approximately three times better than before in terms of
the AUPRC metric. This confirms again, that a quick performance boost can be
oftentimes attained merely by feeding more data to the model, which HMill
excels at. Despite the fact, that the wider architecture $m_{w}$ helped in the
previous experiment, here we observe that the width of the layers plays little
to no role as $m_{b}$ and $m_{w}$ perform more or less the same. On the other
hand, when a higher number of thinner layers is employed, the performance
severely decreases.

##### Fewer datasets trained on

To assess the generalizing capabilities of the method and also its resilience
to the potential concept drift, in this experiment, we trained the models
exactly in the same way, however, with less data. Specifically, we sorted the
datasets by date and used only the first $D$ of them for training, where
$D\in\mathopen{}\mathclose{{}\left\\{1,3,5,8}\right\\}$. Thus, in the first
instance we train the model on the data observed during only week (05-23) and
in the last instance on all of the data available. Because the testing dates
are dispersed over the whole range of considered dates, this enables us to
study the decline in the models’ performance over time (aging). In each of the
examples, the training procedure was prolonged appropriately so that the total
number of sampled minibatches remained the same as in the case when we iterate
over all training datasets five times. We used only ‘baseline’ model $m_{b}$
in this experiment for simplicity. Results are presented in Table D.7  and
Figures D.5  and D.6 . We can see that in this case, even a lower number of
datasets is sufficient to learn a reasonable model, probably because the
network traffic observed during different weeks is highly correlated, and the
concept drift present in the data (if any) is not significant enough to alter
the performance.

##### Grill test

In spite of being one of the defining characteristics of the proposed method,
the ability to learn messages and the whole inference procedure actually
introduces one additional concern. When the same domain appears in both the
data for training and the data for testing, the methods that employ learning
may come up with a model that simply memorizes the domains in the training
set, gaining an unfair advantage. This does not happen with methods that do
not contain a training phase, such as PTP, since the formulas involved are
fixed, regardless of the input data. Even though it is certainly not possible
to be able to fully differentiate between all distinct domains, as the mapping
to the representation in the form of several bipartite graphs is noisy and
thus not injective (also, the same domain will have different neighborhoods in
graphs corresponding to different dates), this phenomena may still occur to
some extent. To investigate further whether this occurs in our case, we
carried out one more experiment, where we leveraged a technique from [Grill
and Pevný, 2016], which we refer to here as Grill test. First, we sampled a
subset of malicious domains from the blacklist proportionally to the size of
each cluster. During the training phase, we consider these domains benign so
that the model cannot memorize them specifically. For evaluation, we use all
negative domains as before, however, only positive domains that the model did
not see during training are picked (around one tenth of all positive domains
in the dataset). This way, we make sure that a specific malicious domain is
first seen during the testing phase. Moreover, adding noise to labels by
inverting some positive domains in the blacklist during training simulates the
situation, when some positive domains are undiscovered and thus not present in
the blacklist, but they are observed. Again, for simplicity, we did this
procedure only for the baseline model $m_{b}$. We trained it in the Grill test
‘mode’ and compared it on all three testing datasets to the case when $m_{b}$
is trained on (and evaluated) on all domains. Unsurprisingly, the performance
drops, as can be seen in Table D.8  and Figures D.7  and D.8 . Nevertheless,
let us emphasize that with Grill test, both training and testing data follow
the different distributions and therefore, the task being solved is slightly
different.

In this chapter, we showed that it is possible to estimate the maliciousness
of the domain merely from its behavior in the network. The proposed solution
implemented with the HMill framework and the popular PTP algorithm performed
comparably when on only one relation was used. Nonetheless, the HMill-based
solution achieved approximately three times better results with more input
data.

##  Chapter 8 Conclusion and future work

###  8.1 Tying loose ends together

In this thesis, we proposed a novel general-purpose machine learning framework
for sample representation and model definition based on the multi-instance
learning paradigm. The main defining characteristic of the HMill framework is
its versatility. It excels at modelling data sources with attributes typical
for real-world data, such as heterogeneity, incompleteness and hierarchical
structure, elegantly dealing with all of them. As a result, raw observations
can be input into models with little to no preprocessing required. HMill
models are able to discover relevant and informative features and extract them
at different levels of abstraction, which effectively mitigates the need to
design a mapping from complex input data types to vectors, with which the
majority of current ML methods operate. In our opinion, valuable domain
expertise should be used to decide what discriminative data to collect and
feed to the models instead of how to do it, and the framework helps with that.
Moreover, we investigated the approximation capabilities of the framework at
the theoretical level. We showed that the design of the framework is well-
founded by extending the Universal approximation theorem to functions realized
by the HMill model nodes. Thanks to the explicit structure of HMill model
trees derived directly from input data in the form of a schema, learned models
are natural to interpret and decisions easier to explain. We also discussed
how HMill models deal with missing data, how effective sampling techniques can
be leveraged to make inference scalable, and how effective minibatching is
implemented. We have demonstrated the flexibility of the framework in three
different tasks from the computer security domain, which gained notoriety for
containing many problems that are not solvable by machine learning methods in
a straightforward manner. The prime example are data-serialization formats
used for information exchange over the Internet, such as XML or JSON
documents, which may be structured in a complex, hierarchical way.
Specifically, we attempted to solve the IoT device identification problem, in
which every IoT device is described by a JSON document containing data that
can be queried in the network. Furthermore, we have also shown how to learn
from graphs containing dependent observations and how to implement HMill-based
message-passing graph inference using bag nodes for neighborhood
representation. This was accompanied by the practical example of how
executable files can be classified as malicious or benign from the snapshot of
the operating system represented as a graph. In this example, both vertices
and edges in the graph stored useful information, which in the vertex case was
encoded as an XML document. We demonstrated that the processing of features on
edges and vertices as well as the message-passing procedure can be jointly
optimized and tailored to the corresponding problem as a single HMill model.
In the last part of the thesis we discussed the task, in which no data is
observable in vertices or edges, and the only available information is in the
structure of the graph. We then investigated the real-world task of blacklist
extension based on the behavioral patterns in the network. This represents a
different approach to the problem, in which we describe interactions between
observed entities, rather than attributes of individuals. With the framework,
both approaches can be fluently transitioned between. In all three tasks,
‘baseline’ HMill models achieved comparable or even better performance than
current specialized algorithms, which suggests that high modelling flexibility
is not traded for compromises in performance. The only downside is the
relatively high computational complexity of training caused by demanding
gradient computation in possibly deep and broad model trees. We note that this
issue is of little concern with ever-increasing computing power. To conclude,
we firmly believe that the flexibility in modelling coupled with the
straightforward out-of-the-box application of the framework will enable
application in problems, where current methods may have struggled.

###  8.2 Future work

Since feature selection and decision explaining are considered two tasks
similar in many regards, and we have shown that HMill deals with the former
one well, we believe that explanations for HMill models are possible. Although
explainability is not specifically addressed in this text, we assume that the
hierarchical structure of the model and the fact that it has to learn to
extract relevant information in each layer of the tree makes precise
explanations feasible. Also, as models from the framework can process raw
data, the outputs can be explained directly using data from the input-level as
well as from higher-level representations. If a model is trained on manually
extracted features, this opportunity is lost. Moreover, in some cases,
explaining at the lowest level may be much more useful. Consider the IoT
device identification task. We could produce an explanation of a device type
prediction involving a specific protocol being used at a specific port, which
seems reasonable. However, this is not possible if this information is somehow
flattened into a feature vector beforehand. Other than that, we would like to
investigate further, how the performance increases once we make more than one
step in graph inference, and how the exponential growth in sizes of the
neighborhood can be tackled. One possible approach is to use attention
mechanisms [Bahdanau et al., 2014, Vaswani et al., 2017, Ilse et al., 2018] in
an aggregation function in bag model nodes, which would allow models to first
examine many neighbors and pay attention to those which seem most relevant. In
spite of competitive performance achieved in all three tasks, the models
presented here are rather basic and do not make use of any recent discoveries
in deep learning, for example, residual learning [He et al., 2015] or batch
normalization layers [Ioffe and Szegedy, 2015]. This presents another possible
research direction for the future. Last but not least, we aim to apply the
HMill framework on other datasets not from the cybersecurity domain alone.

Appendices

##  Appendix A Proofs

######  Statement 3.

For any $k\in\mathbb{N}$, $\alpha\in\mathbb{R}$, any $r>0$ and all
$x_{i}\in\mathbb{R}$, it holds
$g_{\operatorname{lse}}(\\{x_{1},\ldots,x_{k}\\};r)=\alpha+g_{\operatorname{lse}}(\\{x_{1}-\alpha,\ldots,x_{k}-\alpha\\};r)$
where
$g_{\operatorname{lse}}(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\};r)=\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right).$

######  Proof.

$\displaystyle g_{\operatorname{lse}}(\\{x_{i}\\}_{i=1}^{k};r)$
$\displaystyle=\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right)=\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot\mathopen{}\mathclose{{}\left(x_{i}+\alpha-\alpha}\right)})}\right)$
$\displaystyle=\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\exp(r\alpha)\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot(x_{i}-\alpha)})}\right)=\frac{1}{r}\log\exp(r\alpha)+\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot(x_{i}-\alpha)})}\right)$
$\displaystyle=\alpha+\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot(x_{i}-\alpha)})}\right)=\alpha+g_{\operatorname{lse}}(\\{x_{i}-\alpha\\}_{i=1}^{k};r)$

######  Statement 4.

For any $\beta>0$, $p\geq 1$, and $c\in\mathbb{R}$, it holds
$g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{1},\ldots,x_{k}\\};p,c)=\beta\cdot
g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{1}/\beta,\ldots,x_{k}/\beta\\};p,c/\beta)$
where
$g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{1},\ldots,x_{k}\\};p,c)=\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}.$

######  Proof.

$\displaystyle
g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{i}\\}_{i=1}^{k};p,c)$
$\displaystyle=\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}=\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\frac{\beta^{p}}{\beta^{p}}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}$
$\displaystyle=\beta\cdot\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\mathopen{}\mathclose{{}\left|\frac{x_{i}-c}{\beta}}\right|^{p}}\right)^{\frac{1}{p}}=\beta\cdot
g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{i}/\beta\\}_{i=1}^{k};p,c/\beta)$

######  Statement 5.

For any $k\in\mathbb{N}$ and all $x_{i}\in\mathbb{R}$, it holds $\lim_{r\to
0}g_{\operatorname{lse}}(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\};r)=\lim_{r\to
0}\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right)=g_{\operatorname{mean}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\}}\right)=\frac{1}{k}\sum_{i=1}^{k}x_{i}.$

######  Proof.

$\displaystyle\lim_{r\to
0}\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right)$ $\displaystyle\overset{\shortstack{\tiny L'Hospital's,\\\
\tiny Rule}}{=}\lim_{r\to 0}\frac{\sum_{i=1}^{k}x_{i}\exp(r\cdot
x_{i})}{\sum_{i=1}^{k}\exp(r\cdot x_{i})}=\frac{1}{k}\sum_{i=1}^{k}x_{i}$

######  Statement 6.

For any $k\in\mathbb{N}$ and all $x_{i}\in\mathbb{R}$, it holds
$\lim_{r\to\infty}g_{\operatorname{lse}}(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\};r)=\lim_{r\to\infty}\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right)=g_{\max}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\}}\right)=\max_{i=1,\ldots,k}x_{i}.$

######  Proof.

Using Statement 3 $\displaystyle\lim_{r\to
0}\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\exp({r\cdot
x_{i}})}\right)$
$\displaystyle=\max_{i=1,\ldots,k}x_{i}+\underbrace{\lim_{r\to\infty}\frac{1}{r}\log\frac{1}{k}}_{=0}+\lim_{r\to\infty}\frac{1}{r}\log\mathopen{}\mathclose{{}\left(\sum_{i=1}^{k}\exp({r\cdot(\underbrace{x_{i}-\max_{i=1,\ldots,k}x_{i}}_{\leq
0})})}\right)$
$\displaystyle=\max_{i=1,\ldots,k}x_{i}+\underbrace{\lim_{r\to\infty}\frac{1}{r}\log(\exp(1))}_{=0}=\max_{i=1,\ldots,k}x_{i}$

######  Statement 7.

For any $k\in\mathbb{N}$, $c\in\mathbb{R}$ and all $x_{i}\in\mathbb{R}$, it
holds
$\lim_{p\to\infty}g_{\operatorname{\mathnormal{p}-norm}}(\mathopen{}\mathclose{{}\left\\{x_{1},\ldots,x_{k}}\right\\};p,c)=\max_{i=1,\ldots,k}\lvert
x_{i}-c\rvert$ where
$g_{\operatorname{\mathnormal{p}-norm}}(\\{x_{1},\ldots,x_{k}\\};p,c)=\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}.$

######  Proof.

Assume that $\widetilde{x}=\max\limits_{i=1,\ldots,k}|x_{i}-c|$. Then for
$p\geq 1$,
$\displaystyle\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}\leq\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}\widetilde{x}^{p}}\right)^{\frac{1}{p}}=\mathopen{}\mathclose{{}\left(\frac{1}{k}k\widetilde{x}^{p}}\right)^{\frac{1}{p}}=\widetilde{x}$
and
$\displaystyle\mathopen{}\mathclose{{}\left(\frac{1}{k}\sum_{i=1}^{k}|x_{i}-c|^{p}}\right)^{\frac{1}{p}}\geq\mathopen{}\mathclose{{}\left(\frac{1}{k}\widetilde{x}^{p}}\right)^{\frac{1}{p}}=\mathopen{}\mathclose{{}\left(\frac{1}{k}}\right)^{\frac{1}{p}}\widetilde{x}$
Using the squeeze theorem
$\displaystyle\lim_{p\to\infty}\mathopen{}\mathclose{{}\left(\frac{1}{k}}\right)^{\frac{1}{p}}\widetilde{x}=\widetilde{x}\leq\lim_{p\to\infty}g_{\operatorname{\mathnormal{p}-norm}}(\mathopen{}\mathclose{{}\left\\{x_{i}}\right\\}_{i=1}^{k};p,c)\leq\lim_{p\to\infty}\widetilde{x}=\widetilde{x}$

##  Appendix B IoT device identification (use case)

Figure B.1: A (shortened) schema deduced from $57\,906$ training JSON
documents for the device identification task from the dataset downloaded from
Kaggle. Each entry is accompanied by at most two numbers. The first one
specifies the number of times the entry was updated summed over all samples
(for a single sample, this can range from zero in case of missing values to
any natural number in the presence of arrays) and the second number is the
number of unique values of the given field for identification of categorical
variables. This is not measured for composite entries, such as dictionaries
(JSON objects) or lists (JSON arrays). If there are too many unique values,
JsonGrinder.jl stops the count to save memory and represents this with inf.
From this schema we can learn, for example, that only device_class, device_id,
ip and mac fields are specified for every sample, that dhcp entry (if
specified) always contains an array of a single element, and all JSON arrays
representing ssdp scans consist of JSON objects with no missing keys. Figure
B.2: An example of one observation for the device identification task. Figure
B.3: An example of one observation for the device identification task.

##  Appendix C Behavior-based malware classification in graphs (use case)

Figure C.1: A drawing of the largest (weakly) connected component in one of
the IDP graphs from the training set. For demonstration purposes, we cherry-
picked one of the smallest graphs with a smaller number of nodes and smaller
degree values. Blue squares represent executable nodes and red circles process
nodes. This figure should provide a rough idea of the structure of IDP graphs.
For a more detailed description of smaller subgraphs, refer to Figures C.2 and
C.4. Process nodes with large degrees in the middle of most prominent
‘clusters’ in this particular graph correspond to explorer.exe (left) and
services.exe (right) processes.

Figure C.2: One of the (weakly) connected components of an IDP graph
representation of the system. Red rectangles with rounded corners represent
processes, and blue rectangles represent executable files. The document icon
signifies that each vertex is further described by an XML document. For two
nodes (number $6$ and $17$), the documents are shown specifically. To remain
consistent with the rest of the thesis, we use the equivalent JSON
representation of these documents (see Section 6.3.1). Fully qualified names
are in Figure C.3. This connected component captures a launch of the Grand
Theft Auto 5 computer game. In this case, there is no ongoing malicious
activity—INJECT relationships usually signify the presence of an external
(anti)cheat tool.

Figure C.3: Fully qualified names of executables and processes in Figure C.4.
Generic username "ANNA" was used for anonymization of the original user.

Figure C.4: One (weakly) connected component of an IDP graph representation of
a system most probably infected through EternalBlue exploit. Red rectangles
with rounded corners represent processes, and blue rectangles represent
executable files. The document icon signifies that each vertex is further
described by an XML document. Fully qualified names are in Figure C.5. In this
specific example, malicious payload is present in node number $19$. The binary
mimicks the standard Local Security Authority Subsystem Service (LSASS) system
file. However, the malicious binary is stored in a different directory than
%WINDIR%\System32.

Figure C.5: Fully qualified names of executables and processes in Figure C.4.
Generic username "BOB" was used for anonymization of the original user.

Figure C.6: A (shortened) schema inferred from $7\,886\,274$ vertices present
in graphs in the dataset. See Figure B.1 for the exact interpretation of the
format. From the schema we can deduce that missing data is not an issue for
IDP graphs, since all top-level entries are updated same number of times. The
keys describing individual characteristics are shortened for brevity.

Table C.1: Examples of characteristics extracted from patents [Williamson and
Gorelik, 2014a, Williamson and Gorelik, 2014b]. Note that some characteristics
function as controls for the whole engine. We filtered these out. name
description SURVIVE_REBOOT The executable is configured to automatically
restart. Malicious programs generally need to survive reboot in order to be
effective at stealing information from the user. WINDOW_NOT_VISIBLE The
executable does not display a window on the screen. This implies that the
program is trying to prevent user from seeing its activity. PROCESS_IS_HIDDEN
The process is hidden from the Windows Task Manager. A malicious program can
use this technique to remain hidden from the user. SMALL_IMAGE_SIZE The size
of the executable file image is very small. Malicious programs try to be
stealthy, and one way to remain invisible is to minimize the impact on the
underlying system. WRITES_TO_WINDIR The executable attempted to write to the
Windows directory. Often, malicious programs install themselves in the Windows
directory, as that directory contains many executables, and it is easy to
remain unnoticed there. WRITES_TO_PGM_FILES The executable attempted to write
to the Program Files directory. Some malicious programs (particularly adware)
install themselves in this directory. EXEC_FROM_CACHE The executable is
executed from a cached area. EXEC_FROM_WINDIR The executable is executed from
the Windows directory. EXEC_FROM_PGM_FILES The executable is executed from the
Program Files directory. IS_SHADOW The executable has the same name as a
legitimate executable. This is evidence of a common mechanism that trojans and
other malicious code use to hide themselves on a computer. P2P_CODE_INJECTION
The executable attempted to inject code into the address space of another
process. This is generally evidence of malicious activity as the injected code
could be the malicious payload or a rootkit trying to hide the real malicious
process from detection. TURNS_OFF_FIREWALL The executable attempted to turn
off the Windows firewall. HAS_DOUBLE_EXTENSION The file name of the executable
has a double extension. Windows is configured by default to hide known file
extensions and this might fool an unsuspecting user into opening a harmful
executable. TERMINATE_PROCESS The executable terminates another running
process. Some malicious programs attempt to terminate security programs (such
as anti-virus, anti-spyware) running on the machine in order to avoid
detection. KEYLOGGER_HOOK The executable attempted to install a keylogger by a
legitimate mechanism. Malicious programs install keyloggers to capture
keystrokes and steal logins, passwords and credit card numbers.
MODIFIES_HOSTS_FILE The executable attempted to modify the hosts file.
MODIFIES_AUTOEXEC_BAT The executable attempted to modify the autoexec.bat
file. MODIFIES_CONFIG_SYS The executable attempted to modify the default set
of drivers loaded at startup time. INSTALLED_VIA_IM The executable was
installed by an instant messaging program. INSTALLED_VIA_EMAIL The executable
was installed via an email reader. INSTALLED_VIA_BROWSER The executable was
installed by a browser.

##  Appendix D Modelling Internet communication (use case)

Table D.1: Sizes of vertex sets sorted by date, when bipartite graphs were
observed. Here, $\mathcal{A}_{d}$ in the second column denotes all vertices
assembled from all bipartite graphs. The rest of the columns specify sizes of
‘right’ sets in bipartite graphs. $\mathcal{B}_{c}$ denotes clients,
$\mathcal{B}_{b}$ binary files, $\mathcal{B}_{IP}$ IP addresses,
$\mathcal{B}_{ta}$ TLS issuer authorities, $\mathcal{B}_{th}$ TLS certificate
hashes, $\mathcal{B}_{ti}$ TLS issue times, $\mathcal{B}_{we}$ WHOIS entry
emails, $\mathcal{B}_{wn}$ WHOIS nameservers, $\mathcal{B}_{wr}$ WHOIS
registrar names, $\mathcal{B}_{wc}$ WHOIS country, $\mathcal{B}_{wi}$ WHOIS
registrar id, and finally, $\mathcal{B}_{wt}$ WHOIS timestamp. date
$|\mathcal{A}_{d}|$ $|\mathcal{B}_{c}|$ $|\mathcal{B}_{b}|$
$|\mathcal{B}_{IP}|$ $|\mathcal{B}_{ta}|$ $|\mathcal{B}_{th}|$
$|\mathcal{B}_{ti}|$ $|\mathcal{B}_{we}|$ $|\mathcal{B}_{wn}|$
$|\mathcal{B}_{wr}|$ $|\mathcal{B}_{wc}|$ $|\mathcal{B}_{wi}|$
$|\mathcal{B}_{wt}|$ 05-23 $710\,167$ $3\,419\,758$ $245\,999$ $2\,357\,441$
$6\,217$ $374\,531$ $160\,343$ $18\,537$ $15\,972$ $1\,111$ $160$ $959$ $901$
06-03 $631\,828$ $3\,151\,105$ $232\,507$ $2\,247\,940$ $5\,631$ $337\,558$
$142\,944$ $16\,442$ $14\,803$ $989$ $157$ $849$ $901$ 06-10 $644\,868$
$3\,140\,231$ $236\,052$ $2\,268\,276$ $5\,745$ $348\,298$ $148\,844$
$16\,834$ $14\,913$ $969$ $160$ $833$ $904$ 06-17 $630\,532$ $3\,114\,985$
$242\,696$ $2\,305\,323$ $5\,618$ $340\,934$ $145\,032$ $16\,808$ $14\,973$
$945$ $161$ $806$ $904$ 06-26 $648\,960$ $3\,175\,500$ $238\,535$
$2\,316\,943$ $5\,732$ $350\,155$ $149\,609$ $17\,519$ $15\,454$ $954$ $160$
$805$ $902$ 06-27 $616\,958$ $3\,106\,120$ $240\,931$ $2\,256\,445$ $5\,484$
$334\,996$ $142\,453$ $16\,468$ $14\,942$ $909$ $158$ $763$ $901$ 07-01
$613\,601$ $3\,055\,840$ $240\,909$ $2\,277\,775$ $5\,433$ $332\,991$
$141\,471$ $16\,373$ $14\,866$ $894$ $157$ $743$ $897$ 07-08 $557\,253$
$2\,894\,017$ $224\,571$ $2\,117\,016$ $5\,077$ $307\,541$ $129\,249$
$14\,319$ $13\,756$ $810$ $160$ $665$ $890$ 07-15 $608\,327$ $2\,943\,900$
$241\,631$ $2\,222\,769$ $5\,504$ $330\,853$ $140\,718$ $16\,168$ $14\,834$
$861$ $158$ $717$ $899$ 07-22 $600\,814$ $2\,929\,311$ $239\,520$
$2\,193\,113$ $5\,423$ $326\,592$ $138\,604$ $16\,214$ $14\,764$ $842$ $156$
$693$ $898$ 07-29 $588\,039$ $2\,873\,682$ $237\,436$ $2\,162\,197$ $5\,194$
$320\,663$ $135\,980$ $15\,785$ $14\,475$ $806$ $150$ $656$ $898$ Table D.2:
Numbers of edges in bipartite graphs sorted by date, when the graph was
observed. The meaning of the abbreviations in subscripts is the same as in
Table D.1. Note that TLS issuer authority, TLS certificate hash and TLS issue
time contain the same number of edges for each of the dates. This is not
caused by a typo, but by the fact, that these three relation types, if
obtainable, were obtained together. date $|\mathcal{E}_{c}|$
$|\mathcal{E}_{b}|$ $|\mathcal{E}_{IP}|$ $|\mathcal{E}_{ta}|$
$|\mathcal{E}_{th}|$ $|\mathcal{E}_{ti}|$ $|\mathcal{E}_{we}|$
$|\mathcal{E}_{wn}|$ $|\mathcal{E}_{wr}|$ $|\mathcal{E}_{wc}|$
$|\mathcal{E}_{wi}|$ $|\mathcal{E}_{wt}|$ 05-23 $334\,320\,003$ $4\,073\,050$
$9\,314\,998$ $465\,879$ $465\,879$ $465\,879$ $44\,613$ $122\,231$ $42\,804$
$39\,506$ $46\,589$ $46\,603$ 06-03 $292\,659\,940$ $3\,639\,635$
$8\,356\,254$ $419\,035$ $419\,035$ $419\,035$ $38\,974$ $108\,077$ $37\,349$
$34\,538$ $40\,690$ $40\,704$ 06-10 $299\,532\,603$ $3\,785\,134$
$8\,902\,097$ $430\,878$ $430\,878$ $430\,878$ $39\,766$ $110\,423$ $38\,213$
$35\,321$ $41\,543$ $41\,555$ 06-17 $293\,466\,696$ $3\,813\,715$
$8\,803\,587$ $420\,926$ $420\,926$ $420\,926$ $39\,322$ $109\,466$ $37\,741$
$34\,906$ $41\,072$ $41\,088$ 06-26 $306\,114\,224$ $3\,846\,992$
$9\,141\,868$ $431\,772$ $431\,772$ $431\,772$ $41\,035$ $114\,242$ $39\,370$
$36\,328$ $42\,832$ $42\,845$ 06-27 $291\,065\,433$ $3\,821\,056$
$8\,740\,732$ $412\,836$ $412\,836$ $412\,836$ $38\,296$ $107\,202$ $36\,775$
$33\,943$ $39\,996$ $40\,009$ 07-01 $285\,920\,746$ $3\,789\,277$
$8\,649\,546$ $410\,419$ $410\,419$ $410\,419$ $37\,797$ $106\,055$ $36\,256$
$33\,520$ $39\,480$ $39\,494$ 07-08 $251\,616\,117$ $3\,361\,849$
$7\,917\,765$ $376\,934$ $376\,934$ $376\,934$ $33\,028$ $936\,23$ $317\,36$
$292\,40$ $345\,25$ $345\,34$ 07-15 $278\,227\,235$ $3\,693\,630$
$8\,869\,060$ $406\,339$ $406\,339$ $406\,339$ $37\,536$ $105\,356$ $36\,008$
$33\,288$ $39\,180$ $39\,193$ 07-22 $278\,975\,786$ $3\,765\,391$
$8\,627\,468$ $400\,566$ $400\,566$ $400\,566$ $37\,407$ $104\,908$ $35\,844$
$33\,015$ $39\,017$ $39\,031$ 07-29 $274\,507\,944$ $3\,701\,055$
$8\,475\,127$ $392\,479$ $392\,479$ $392\,479$ $36\,473$ $102\,514$ $35\,002$
$32\,228$ $38\,021$ $38\,034$ Table D.3: Numbers of malicious domains in each
of the datasetes. In the first row, there is the number of domains that are
both in the blacklist and in the observed dataset, and in the second row, we
give the ratio of the number of blacklisted domains to the total number of
domains in the dataset. 05-23 06-03 06-10 06-17 06-24 06-26 06-27 07-01 07-08
07-15 07-22 07-29 $\lvert L\cap\mathcal{A}\rvert$ $656$ $578$ $535$ $557$
$538$ $557$ $552$ $555$ $512$ $557$ $577$ $548$ $\lvert
L\cap\mathcal{A}\rvert/{\lvert\mathcal{A}\rvert}$ $0.924$‰ $0.915$‰ $0.830$‰
$0.883$‰ $0.865$‰ $0.858$‰ $0.895$‰ $0.904$‰ $0.919$‰ $0.916$‰ $0.960$‰
$0.932$‰ Table D.4: All relations used in our experiments, with their
cardinality type and several examples of specific relation pairs (edges in a
bipartite graph). Each edge is specified as $(u;v)$ to avoid confusion as
commas may be used in $u$ or $v$. M2M stands for many-to-many and M2O for
many-to-one cardinality type. Longer names are for shortened using ellipsis
(…). name (domain-*) card. type examples *-client M2M (tottenhamhotspur.com;
S8g) (loanstreet.com.my; 2Pu3) (healthlabtesting.com; 2WLu) *-binary M2M
(kotonoha-jiten.com; 15CBF8…) (wonderslim.com; B41781…)
(pythonprogramming.net; CF6ACB…) *-IP address M2M (quickpayportal.com;
208.78.141.18) (jobwinner.ch; 217.71.91.48) (tottenhamhotspur.com;
104.16.54.111) *-TLS issuer M2O (cratejoy.com; CN=Amazon, OU=Server CA 1B,
O=Amazon, C=US) (creative-serving.com; CN=COMODO RSA Domain Validation Secure
Server…) (healthlabtesting.com; CN=Symantec Class 3 Secure Server CA…) *-TLS
hash M2O (timeoutdubai.com; 90c093…) (boomerang.com; e577e6…)
(quickpayportal.com; 85bdd8…) *-TLS issue time M2O (jobwinner.ch; 1496041693)
(healthlabtesting.com; 1445558400) (flatmates.com.au; 1502150400) *-WHOIS
email M2O (unstableunicorns.com<EMAIL_ADDRESS>(albertlee.biz<EMAIL_ADDRESS>(crowneplazalondonthecity.com;
<EMAIL_ADDRESS>) *-WHOIS nameserver M2O
(grd779.com; ns2.hover.com) (celeritascdn.com; lady.ns.cloudflare.com)
(smeresources.org; ns-495.awsdns-61.com) *-WHOIS registrar name M2O
(unblocked.how; eNom, Inc.) (rev-stripe.com; Amazon Registrar, Inc.)
(chisaintjosephhealth.org; Register.com, Inc.) *-WHOIS country M2O
(thefriscostl.com; CANADA) (getwsone.com; UNITED STATES) (notify.support;
PANAMA) *-WHOIS registrar id M2O (lo3trk.com; 468) (watchcrichd.org; 472)
(bozsh.com; 1479) *-WHOIS timestamp M2O (unblocked.how; 15293)
(comicplanet.net; 15159) (unpublishedflight.com; 15553)

###  D.1 Comparison to PTP

Table D.5 : Values of the AUPRC and the AUROC metrics for three HMill-based
models and the PTP algorithm, rounded to 4 decimal places. Results on all
three testing datasets are displayed and correspond to curves in Figures D.1
and D.2 . The greatest number in every column is written in bold. 06-10 06-27
07-22 AUPRC AUROC AUPRC AUROC AUPRC AUROC PTP $0.1561$ $\mathbf{0.9621}$
$0.1243$ $0.9584$ $0.1442$ $0.9544$ $m_{B}$ $0.1242$ $0.9579$ $0.1561$
$0.9590$ $0.1544$ $0.9545$ $m_{W}$ $\mathbf{0.2248}$ $0.9560$
$\mathbf{0.2402}$ $0.9663$ $\mathbf{0.2220}$ $0.9574$ $m_{D}$ $0.1684$
$0.9557$ $0.1912$ $\mathbf{0.9667}$ $0.2047$ $\mathbf{0.9580}$

Figure D.1 : PR curves comparing the performance of three HMill-based models
$m_{B}$, $m_{W}$ and $m_{D}$ to the PTP algorithm. Three figures are plotted,
each corresponds to one of the testing datasets.

Figure D.2 : ROC curves comparing the performance of three HMill-based models
$m_{B}$, $m_{W}$ and $m_{D}$ to the PTP algorithm. Three figures are plotted,
each corresponds to one of the training datasets. The logarithmic scale is
used for $x$-axis.

###  D.2 Additional relations

Table D.6 : Values of the AUPRC and the AUROC metrics for three HMill-based
models, rounded to 4 decimal places. Here, all eleven relations are employed.
Results on all three testing datasets are displayed and correspond to curves
in Figures D.3  and D.4 . The greatest number in every column is written in
bold. 06-10 06-27 07-22 AUPRC AUROC AUPRC AUROC AUPRC AUROC $m_{b}$ $0.6419$
0.9884 0.6905 0.9899 0.6595 0.9880 $m_{w}$ 0.6422 $0.9840$ $0.6823$ $0.9818$
$0.6590$ $0.9804$ $m_{d}$ $0.4498$ $0.9780$ $0.5031$ $0.9831$ $0.4719$
$0.9796$

Figure D.3 : PR curves comparing the performance of three HMill-based models
$m_{b}$, $m_{w}$ and $m_{d}$ when all eleven relations are used. Three figures
are plotted, each corresponds to one of the testing datasets.

Figure D.4 : ROC curves comparing the performance of three HMill-based models
$m_{b}$, $m_{w}$ and $m_{d}$ when all eleven relations are used. Three figures
are plotted, each corresponds to one of the training datasets. The logarithmic
scale is used for $x$-axis.

###  D.3 Fewer datasets trained on

Table D.7 : Values of the AUPRC and the AUROC metrics rounded to 4 decimal
places for the baseline HMill model $m_{b}$, in cases, where a different
number of datasets is used. Specifically, in the first row, we used only the
first dataset (date 05-23), in the second row the first three of them and
first five in the next row. In the last row, there is a performance of the
model trained on all available training datasets, which is the identical
setting to the one in Section 7.3.3. Hence, the first row is identical to the
first row in Table D.6 . Results on all three testing datasets are displayed
and correspond to curves in Figures D.5  and D.6 . The greatest number in
every column is written in bold. 06-10 06-27 07-22 AUPRC AUROC AUPRC AUROC
AUPRC AUROC $m_{b}$ ($1$ dataset) 0.6933 $0.9739$ $0.7005$ $0.9796$ $0.6708$
$0.9750$ $m_{b}$ ($3$ datasets) $0.6834$ $0.9825$ 0.7030 $0.9843$ 0.6753
$0.9810$ $m_{b}$ ($5$ datasets) $0.6381$ $0.9762$ $0.6760$ $0.9839$ $0.6363$
$0.9774$ $m_{b}$ ($8$ datasets) $0.6419$ 0.9884 $0.6905$ 0.9899 $0.6595$
0.9880

Figure D.5 : PR curves comparing the performance of the ‘baseline’ HMill model
$m_{b}$, when a different number of datasets is used for training. Three
figures are plotted, each corresponds to one of the testing datasets.

Figure D.6 : ROC curves comparing the performance of the ‘baseline’ HMill
model $m_{b}$, when a different number of datasets is used for training. Three
figures are plotted, each corresponds to one of the training datasets. The
logarithmic scale is used for $x$-axis.

###  D.4 Grill test

Table D.8 : Values of the AUPRC and the AUROC metrics rounded to 4 decimal
places, for the baseline HMill model $m_{b}$ with and without Grill test. The
first row is identical to the first row in Table D.6 . Results on all three
testing datasets are displayed and correspond to curves in Figures D.7  and
D.8 . The greatest number in every column is written in bold. 06-10 06-27
07-22 AUPRC AUROC AUPRC AUROC AUPRC AUROC $m_{b}$ 0.6419 0.9884 0.6905 0.9899
0.6595 0.9880 $m_{b}$ (Grill) $0.4503$ $0.9509$ $0.4745$ $0.9662$ $0.4735$
$0.9593$

Figure D.7 : PR curves comparing the performance of the ‘baseline’ HMill model
$m_{b}$, when the Grill test is (not) used. Three figures are plotted, each
corresponds to one of the training datasets.

Figure D.8 : ROC curves comparing the performance of the ‘baseline’ HMill
model $m_{b}$, when the Grill test is (not) used. Three figures are plotted,
each corresponds to one of the training datasets. The logarithmic scale is
used for $x$-axis.

##

## References

  * [ABI Research, 2013] ABI Research (2013).  More Than 30 Billion Devices Will Wirelessly Connect to the Internet of Everything in 2020.  https://www.abiresearch.com/press/more-than-30-billion-devices-will-wirelessly-conne/.
  * [Ahuja et al., 2019] Ahuja, A., Gandhi, H., Shorey, R., Kulkarni, D., and Tew, J. (2019).  Plumewalk: Towards threat provenance localization for iot networks.  In 2019 11th International Conference on Communication Systems Networks (COMSNETS), pages 383–390.
  * [Amit et al., 2019] Amit, I., Matherly, J., Hewlett, W., Xu, Z., Meshi, Y., and Weinberger, Y. (2019).  Machine Learning in Cyber-Security-Problems, Challenges and Data Sets.  Technical report.
  * [Amit and Geman, 1997] Amit, Y. and Geman, D. (1997).  Shape quantization and recognition with randomized trees.  Neural Computation, 9(7):1545–1588.
  * [Amodei et al., 2016] Amodei, D., Ananthanarayanan, S., Anubhai, R., Bai, J., Battenberg, E., Case, C., Casper, J., Catanzaro, B., Cheng, Q., Chen, G., Chen, J., Chen, J., Chen, Z., Chrzanowski, M., Coates, A., Diamos, G., Ding, K., Du, N., Elsen, E., Engel, J., Fang, W., Fan, L., Fougner, C., Gao, L., Gong, C., Hannun, A. N., Han, T., Johannes, L. V., Jiang, B., Ju, C., Jun, B., Legresley, P., Lin, L., Liu, J., Liu, Y., Li, W., Li, X., Ma, D., Narang, S., Ng, A., Ozair, S., Peng, Y., Prenger, R., Qian, S., Quan, Z., Raiman, J., Rao, V., Satheesh, S., Seetapun, D., Sengupta, S., Srinet, K., Sriram, A., Tang, H., Tang, L., Wang, C., Wang, J., Wang, K., Wang, Y., Wang, Z., Wang, Z., Wu, S., Wei, L., Xiao, B., Xie, W., Xie, Y., Yogatama, D., Yuan, B., Zhan, J., and Zhu, Z. (2016).  Deep speech 2: End-to-end speech recognition in English and Mandarin.  In 33rd Int. Conf. Mach. Learn. ICML 2016, volume 1, pages 312–321. International Machine Learning Society (IMLS).
  * [Amores, 2013] Amores, J. (2013).  Multiple instance classification: Review, taxonomy and comparative study.
  * [Andrews et al., 2003] Andrews, S., Tsochantaridis, I., and Hofmann, T. (2003).  Support Vector Machines for Multiple-Instance Learning.  In Becker, S., Thrun, S., and Obermayer, K., editors, Adv. Neural Inf. Process. Syst. 15, pages 577–584. MIT Press.
  * [Antonakakis et al., 2017] Antonakakis, M., April, T., Bailey, M., Bernhard, M., Bursztein, E., Cochran, J., Durumeric, Z., Halderman, J. A., Invernizzi, L., Kallitsis, M., Kumar, D., Lever, C., Ma, Z., Mason, J., Menscher, D., Seaman, C., Sullivan, N., Thomas, K., and Zhou, Y. (2017).  Understanding the mirai botnet.  In USENIX Security Symposium.
  * [Antonakakis et al., 2010] Antonakakis, M., Perdisci, R., Dagon, D., Lee, W., and Feamster, N. (2010).  Building a dynamic reputation system for dns.  In USENIX Security Symposium.
  * [Assael et al., 2016] Assael, Y. M., Shillingford, B., Whiteson, S., and de Freitas, N. (2016).  LipNet: End-to-End Sentence-level Lipreading.
  * [Auer and Ortner, 2004] Auer, P. and Ortner, R. (2004).  A boosting approach to multiple instance learning.  In Lect. Notes Artif. Intell. (Subseries Lect. Notes Comput. Sci., volume 3201, pages 63–74. Springer, Berlin, Heidelberg.
  * [Bahdanau et al., 2014] Bahdanau, D., Cho, K., and Bengio, Y. (2014).  Neural machine translation by jointly learning to align and translate.
  * [Baum and Petrie, 1966] Baum, L. E. and Petrie, T. (1966).  Statistical Inference for Probabilistic Functions of Finite State Markov Chains.  Ann. Math. Stat., 37(6):1554–1563.
  * [Bezanson et al., 2014] Bezanson, J., Edelman, A., Karpinski, S., and Shah, V. B. (2014).  Julia: A Fresh Approach to Numerical Computing.  SIAM Rev., 59(1):65–98.
  * [Bilge et al., 2011] Bilge, L., Kirda, E., Kruegel, C., and Balduzzi, M. (2011).  Exposure: Finding malicious domains using passive dns analysis.
  * [Bishop, 2006] Bishop, C. M. (2006).  Pattern Recognition and Machine Learning (Information Science and Statistics).  Springer-Verlag, Berlin, Heidelberg.
  * [Blockeel et al., 2005] Blockeel, H., Page, D., and Srinivasan, A. (2005).  Multi-instance tree learning.  In ICML 2005 - Proc. 22nd Int. Conf. Mach. Learn., pages 57–64, New York, New York, USA. ACM Press.
  * [Bronstein et al., 2016] Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Vandergheynst, P. (2016).  Geometric deep learning: going beyond Euclidean data.
  * [Bruna et al., 2013] Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. (2013).  Spectral Networks and Locally Connected Networks on Graphs.  2nd Int. Conf. Learn. Represent. ICLR 2014 - Conf. Track Proc.
  * [Bunescu and Mooney, 2007] Bunescu, R. C. and Mooney, R. J. (2007).  Multiple instance learning for sparse positive bags.  In ACM Int. Conf. Proceeding Ser., volume 227, pages 105–112, New York, New York, USA. ACM Press.
  * [Campbell et al., 2002] Campbell, M., Hoane, A., and hsiung Hsu, F. (2002).  Deep blue.  Artificial Intelligence, 134(1):57 – 83.
  * [Carter et al., 2013] Carter, K. M., Idika, N., and Streilein, W. W. (2013).  Probabilistic threat propagation for malicious activity detection.  In ICASSP, IEEE Int. Conf. Acoust. Speech Signal Process. - Proc., pages 2940–2944.
  * [Carter et al., 2014] Carter, K. M., Idika, N., and Streilein, W. W. (2014).  Probabilistic threat propagation for network security.  IEEE Trans. Inf. Forensics Secur., 9(9):1394–1405.
  * [Chang et al., 2015] Chang, S., Han, W., Tang, J., Qi, G.-J., Aggarwal, C. C., and Huang, T. S. (2015).  Heterogeneous Network Embedding via Deep Architectures.
  * [Chen et al., 2006] Chen, Y., Bi, J., and Wang, J. Z. (2006).  MILES: Multiple-instance learning via embedded instance selection.  IEEE Trans. Pattern Anal. Mach. Intell., 28(12):1931–1947.
  * [Chevaleyre and Zucker, 2001] Chevaleyre, Y. and Zucker, J. D. (2001).  Solving multiple-instance and multiple-part learning problems with decision trees and rule sets. Application to the mutagenesis problem.  In Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), volume 2056, pages 204–214. Springer Verlag.
  * [Christmann and Steinwart, 2010] Christmann, A. and Steinwart, I. (2010).  Universal Kernels on Non-Standard Input Spaces.  Technical report.
  * [Cisco Systems, 2017] Cisco Systems (2017).  Cisco 2017 Annual Cybersecurity Report.  https://www.cisco.com/c/m/en_au/products/security/offers/annual-cybersecurity-report-2017.html.
  * [Collins et al., 2007] Collins, M. P., Shimeall, T. J., Faber, S., Janies, J., Weaver, R., De Shon, M., and Kadane, J. (2007).  Using uncleanliness to predict future botnet addresses.  In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pages 93–104.
  * [Cortes and Vapnik, 1995] Cortes, C. and Vapnik, V. (1995).  Support-vector networks.  Mach. Learn., 20(3):273–297.
  * [Coskun et al., 2010] Coskun, B., Dietrich, S., and Memon, N. (2010).  Friends of an enemy: identifying local members of peer-to-peer botnets using mutual contacts.  In Proceedings of the 26th Annual Computer Security Applications Conference, pages 131–140.
  * [Cybenko, 1989] Cybenko, G. (1989).  Approximation by superpositions of a sigmoidal function.  Mathematics of Control, Signals and Systems, 2:303–314.
  * [Dasarathy, 1991] Dasarathy, B. (1991).  Nearest Neighbor (NN) Norms : NN Pattern Clasification Techniques.  IEEE Computer Society Press, Los Alamitos (Cal.).
  * [Devlin et al., 2018] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. (2018).  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.
  * [Dietterich et al., 1997] Dietterich, T. G., Lathrop, R. H., and Lozano-Pérez, T. (1997).  Solving the multiple instance problem with axis-parallel rectangles.  Technical report.
  * [Dong, 2006] Dong, L. (2006).  A Comparison of Multi-instance Learning Algorithms.  Technical report.
  * [Dong et al., 2017] Dong, Y., Chawla, N. V., and Swami, A. (2017).  metapath2vec: Scalable Representation Learning for Heterogeneous Networks.
  * [Dooly et al., 2001] Dooly, D. R., Dooly, D. R., Zhang, Q., Goldman, S. A., Amar, R. A., Brodley, E., and Danyluk, A. (2001).  Multiple-instance learning of real-valued data.  J. Mach. Learn. Res., 3:3—-10.
  * [Dulac-Arnold et al., 2019] Dulac-Arnold, G., Mankowitz, D., and Hester, T. (2019).  Challenges of Real-World Reinforcement Learning.  Technical report.
  * [Edwards and Storkey, 2016] Edwards, H. and Storkey, A. (2016).  Towards a Neural Statistician.
  * [Fan et al., 2019] Fan, S., Zhu, J., Han, X., Shi, C., Hu, L., Ma, B., and Li, Y. (2019).  Metapath-guided Heterogeneous Graph Neural Network for Intent Recommendation (MEIRec).
  * [Fisher, 1936] Fisher, R. A. (1936).  The Use of Multiple Measurements in Taxonomic Problems.  Ann. Eugen., 7(2):179–188.
  * [Foulds, 2007] Foulds, J. (2007).  Learning Instance Weights in Multi-Instance Learning.  Technical report.
  * [Foulds and Frank, 2010] Foulds, J. and Frank, E. (2010).  A review of multi-instance learning assumptions.
  * [Frank and Xu, 2003] Frank, E. and Xu, X. (2003).  Applying propositional learning algorithms to multi-instance data.  Technical report.
  * [Frey and MacKay, 1998] Frey, B. J. and MacKay, D. J. C. (1998).  A revolution: Belief propagation in graphs with cycles.  In Jordan, M. I., Kearns, M. J., and Solla, S. A., editors, Advances in Neural Information Processing Systems 10, pages 479–485. MIT Press.
  * [Fu et al., 2017] Fu, T.-Y., Lee, W.-C., and Lei, Z. (2017).  HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning.
  * [Fukunaga, 1990] Fukunaga, K. (1990).  Introduction to Statistical Pattern Recognition (2nd Ed.).  Academic Press Professional, Inc., USA.
  * [Gärtner et al., 2002] Gärtner, T., Flach, P. A., Kowalczyk, A., Smola AlexSmola, A. J., and Rsise, A. (2002).  Multi-Instance Kernels.  Technical report.
  * [Gilmer et al., 2017] Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017).  Neural Message Passing for Quantum Chemistry.  Technical report.
  * [Glorot and Bengio, 2010] Glorot, X. and Bengio, Y. (2010).  Understanding the difficulty of training deep feedforward neural networks.  In AISTATS.
  * [Grill and Pevný, 2016] Grill, M. and Pevný, T. (2016).  Learning combination of anomaly detectors for security domain.  Comput. Networks, 107:55–63.
  * [Gui et al., 2016] Gui, H., Liu, J., Tao, F., Jiang, M., Norick, B., and Han, J. (2016).  Large-Scale Embedding Learning in Heterogeneous Event Data (HEBE).  Technical report.
  * [Gulcehre et al., 2014] Gulcehre, C., Cho, K., Pascanu, R., and Bengio, Y. (2014).  Learned-Norm Pooling for Deep Feedforward and Recurrent Neural Networks.  In Calders, T., Esposito, F., Hüllermeier, E., and Meo, R., editors, Mach. Learn. Knowl. Discov. Databases, pages 530–546, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * [Hamilton et al., 2017] Hamilton, W. L., Ying, R., and Leskovec, J. (2017).  Inductive Representation Learning on Large Graphs (GraphSAGE).
  * [Hammer et al., 2004] Hammer, B., Micheli, A., Sperduti, A., and Strickert, M. (2004).  Recursive self-organizing network models.  Neural networks : the official journal of the International Neural Network Society, 17:1061–85.
  * [Hammersley, 1971] Hammersley, J. M.; Clifford, P. (1971).  Markov fields on finite graphs and lattices.
  * [He et al., 2015] He, K., Zhang, X., Ren, S., and Sun, J. (2015).  Deep residual learning for image recognition.
  * [Hernandez and Buentello, 2014] Hernandez, G. and Buentello, D. (2014).  Smart nest thermostat a smart spy in your home.
  * [Hoeffding, 1963] Hoeffding, W. (1963).  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30.
  * [Hornik, 1991] Hornik, K. (1991).  Approximation capabilities of multilayer feedforward networks.  Neural Networks, 4:251–257.
  * [Iizuka et al., 2016] Iizuka, S., Simo-Serra, E., and Ishikawa, H. (2016).  Let there be color!: Joint end-to-end learning of global and local image priors for automatic image colorization with simultaneous classification.  In ACM Trans. Graph., volume 35. Association for Computing Machinery.
  * [Ilse et al., 2018] Ilse, M., Tomczak, J. M., and Welling, M. (2018).  Attention-based deep multiple instance learning.
  * [Innes, 2018a] Innes, M. (2018a).  Don’t Unroll Adjoint: Differentiating SSA-Form Programs.
  * [Innes, 2018b] Innes, M. (2018b).  Flux: Elegant machine learning with Julia.  J. Open Source Softw., 3(25):602.
  * [Innes et al., 2018] Innes, M., Saba, E., Fischer, K., Gandhi, D., Rudilosso, M. C., Joy, N. M., Karmali, T., Pal, A., and Shah, V. (2018).  Fashionable Modelling with Flux.
  * [Internet Live Stats, 2020] Internet Live Stats (2020).  Twitter Usage Statistics.  https://www.internetlivestats.com/twitter-statistics/.
  * [Ioffe and Szegedy, 2015] Ioffe, S. and Szegedy, C. (2015).  Batch normalization: Accelerating deep network training by reducing internal covariate shift.
  * [Irsoy and Cardie, 2014] Irsoy, O. and Cardie, C. (2014).  Deep recursive neural networks for compositionality in language.  Advances in Neural Information Processing Systems, 3:2096–2104.
  * [Janisch et al., 2019] Janisch, J., Pevný, T., and Lisý, V. (2019).  Classification with Costly Features Using Deep Reinforcement Learning.  Proc. AAAI Conf. Artif. Intell., 33:3959–3966.
  * [Janisch et al., 2020] Janisch, J., Pevný, T., and Lisý, V. (2020).  Classification with costly features as a sequential decision-making problem.  Machine Learning.
  * [Jordan, 2004] Jordan, M. (2004).  Graphical models.  Statistical Science, 19.
  * [Jusko, 2017] Jusko, J. (2017).  Graph-based Detection of Malicious Network Communities.  Technical report.
  * [Kazato et al., 2016] Kazato, Y., Sugawara, T., and Fukuda, K. (2016).  Detecting malicious domains with probabilistic threat propagation on DNS graph.  Comput. Softw., 33(3):16–28.
  * [Kingma and Ba, 2014] Kingma, D. P. and Ba, J. (2014).  Adam: A method for stochastic optimization.
  * [Kipf and Welling, 2016] Kipf, T. N. and Welling, M. (2016).  Semi-supervised classification with graph convolutional networks.
  * [Kit Smith, 2019] Kit Smith, B. (2019).  53 Incredible Facebook Statistics and Facts.  https://www.brandwatch.com/blog/facebook-statistics/.
  * [Kohli and Torr, 2005] Kohli, P. and Torr, P. H. S. (2005).  Efficiently solving dynamic markov random fields using graph cuts.  In Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, volume 2, pages 922–929 Vol. 2.
  * [Kokkinos and Potamianos, 2017] Kokkinos, F. and Potamianos, A. (2017).  Structural attention neural networks for improved sentiment analysis.
  * [Kraus et al., 2015] Kraus, O. Z., Ba, L. J., and Frey, B. (2015).  Classifying and Segmenting Microscopy Images Using Convolutional Multiple Instance Learning.
  * [Krizhevsky et al., 2012] Krizhevsky, A., Sutskever, I., and Hinton, G. (2012).  Imagenet classification with deep convolutional neural networks.  Neural Information Processing Systems, 25.
  * [Kschischang et al., 2001] Kschischang, F. R., Frey, B. J., and Loeliger, H. A. (2001).  Factor graphs and the sum-product algorithm.  IEEE Transactions on Information Theory, 47(2):498–519.
  * [Kumar et al., 2018] Kumar, D., Paccagnella, R., Murley, P., Hennenfent, E., Mason, J., Bates, A., and Bailey, M. (2018).  Skill squatting attacks on amazon alexa.  In USENIX Security Symposium.
  * [Kumar et al., 2019] Kumar, D., Shen, K., Case, B., Garg, D., Alperovich, G., Kuznetsov, D., Gupta, R., and Durumeric, Z. (2019).  All things considered: An analysis of iot devices on home networks.  In USENIX Security Symposium.
  * [Leshno et al., 1991] Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. (1991).  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  Neural Networks, 6:861–867.
  * [L’Heureux et al., 2017] L’Heureux, A., Grolinger, K., Elyamany, H. F., and Capretz, M. A. (2017).  Machine Learning with Big Data: Challenges and Approaches.  IEEE Access, 5:7776–7797.
  * [Lin et al., 2015] Lin, G., Shen, C., Hengel, A. v. d., and Reid, I. (2015).  Efficient piecewise training of deep structured models for semantic segmentation.  ArXiv e-prints.
  * [Liu et al., 2014] Liu, L., Saha, S., Torres, R., Xu, J., Tan, P. N., Nucci, A., and Mellia, M. (2014).  Detecting malicious clients in ISP networks using HTTP connectivity graph and flow information.  In ASONAM 2014 - Proc. 2014 IEEE/ACM Int. Conf. Adv. Soc. Networks Anal. Min., pages 150–157. Institute of Electrical and Electronics Engineers Inc.
  * [Lowe, 2001] Lowe, D. (2001).  Object recognition from local scale-invariant features.  Proceedings of the IEEE International Conference on Computer Vision, 2.
  * [Malik, 2020] Malik, M. M. (2020).  A Hierarchy of Limitations in Machine Learning.  Technical report.
  * [Manadhata et al., 2014] Manadhata, P. K., Yadav, S., Rao, P., and Horne, W. (2014).  Detecting Malicious Domains via Graph Inference.  pages 1–18.
  * [Mandlík, 2018] Mandlík, Š. (2018).  Inference on a graph representing a computer network (bachelor thesis).  https://dspace.cvut.cz/handle/10467/76129.
  * [Mangasarian and Wild, 2008] Mangasarian, O. L. and Wild, E. W. (2008).  Multiple instance classification via successive linear programming.  J. Optim. Theory Appl., 137(3):555–568.
  * [Mark Beyer, 2012] Mark Beyer, D. L. (2012).  The Importance of ‘Big Data’: A Definition.
  * [Maron and Lozano-Pérez, 1998] Maron, O. and Lozano-Pérez, T. (1998).  A Framework for Multiple-Instance Learning.  In Jordan, M. I., Kearns, M. J., and Solla, S. A., editors, Adv. Neural Inf. Process. Syst. 10, pages 570–576. MIT Press.
  * [Mikolov et al., 2013] Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013).  Efficient estimation of word representations in vector space.
  * [Muandet et al., 2012] Muandet, K., Fukumizu, K., Dinuzzo, F., and Schölkopf, B. (2012).  Learning from Distributions via Support Measure Machines.  Technical report.
  * [Najafabadi et al., 2015] Najafabadi, M. M., Villanustre, F., Khoshgoftaar, T. M., Seliya, N., Wald, R., and Muharemagic, E. (2015).  Deep learning applications and challenges in big data analytics.  J. Big Data, 2(1).
  * [Opelt et al., 2006] Opelt, A., Pinz, A., Fussenegger, M., and Auer, P. (2006).  Generic object recognition with boosting.  IEEE Trans. Pattern Anal. Mach. Intell., 28(3):416–431.
  * [Oprea et al., 2015] Oprea, A., Li, Z., Yen, T.-F., Chin, S., and Alrwais, S. (2015).  Detection of early-stage enterprise infection by mining large-scale log data.  pages 45–56.
  * [Pearl, 1988] Pearl, J. (1988).  Probabilistic Reasoning in Intelligent Systems.  Elsevier.
  * [Pearl, 2013] Pearl, J. (2013).  A probabilistic calculus of actions.
  * [Pennington et al., 2014] Pennington, J., Socher, R., and Manning, C. (2014).  Glove: Global vectors for word representation.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543, Doha, Qatar. Association for Computational Linguistics.
  * [Pevný and Dedič, 2020] Pevný, T. and Dedič, M. (2020).  Nested Multiple Instance Learning in Modelling of HTTP network traffic.
  * [Pevný and Kovařík, 2019] Pevný, T. and Kovařík, V. (2019).  Approximation Capability of Neural Networks on Spaces of Probability Measures and Tree-Structured Domains.  Technical report.
  * [Pevný and Mandlík, 2018] Pevný, T. and Mandlík, Š. (2018).  Mill.jl framework.  https://github.com/pevnak/Mill.jl.
  * [Pevný and Račinský, 2019] Pevný, T. and Račinský, M. (2019).  JsonGrinder.jl library.  https://github.com/pevnak/JsonGrinder.jl.
  * [Pevný and Somol, 2016] Pevný, T. and Somol, P. (2016).  Discriminative models for multi-instance problems with tree structure.  In AISec 2016 - Proc. 2016 ACM Work. Artif. Intell. Secur. co-located with CCS 2016.
  * [Pevný and Somol, 2017] Pevný, T. and Somol, P. (2017).  Using neural network formalism to solve multiple-instance problems.  Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 10261 LNCS(Mil):135–142.
  * [Philips et al., 2012] Philips, S., Yee, M., Kao, E., and Anderson, C. (2012).  Detecting activity-based communities using dynamic membership propagation.  In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2085–2088. IEEE.
  * [R. Kindermann, 1980] R. Kindermann, J. S. (1980).  Markov Random Fields and Their Applications.  American Mathematical Society.
  * [Radford et al., 2018] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2018).  Language Models are Unsupervised Multitask Learners.
  * [Ramon et al., 2000] Ramon, J., Ramon, J., and De Raedt, L. (2000).  Multi Instance Neural Networks.
  * [Rezvani et al., 2015] Rezvani, M., Sekulic, V., Ignjatovic, A., Bertino, E., and Jha, S. (2015).  Interdependent security risk analysis of hosts and flows.  IEEE Transactions on Information Forensics and Security, 10(11):2325–2339.
  * [Ross et al., 2011] Ross, S., Munoz, D., Hebert, M., and Andrew Bagnell, J. (2011).  Learning message-passing inference machines for structured prediction.
  * [Rubner et al., 2000] Rubner, Y., Tomasi, C., and Guibas, L. J. (2000).  The Earth Mover’s Distance as a Metric for Image Retrieval.  Technical report.
  * [Rumelhart et al., 1986] Rumelhart, D. E., Hinton, G. E., and Williams, R. J. (1986).  Learning representations by back-propagating errors.  Nature.
  * [Scarselli et al., 2009] Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. (2009).  The graph neural network model.  IEEE Transactions on Neural Networks, 20(1):61–80.
  * [Schwing and Urtasun, 2015] Schwing, A. G. and Urtasun, R. (2015).  Fully Connected Deep Structured Networks.  ArXiv e-prints.
  * [Shi et al., 2017] Shi, C., Hu, B., Xin, W., Member, Z., and Yu, P. S. (2017).  Heterogeneous Information Network Embedding for Recommendation (HERec).  Technical report.
  * [Silver et al., 2018] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. (2018).  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  Science, 362(6419):1140–1144.
  * [Sivic and Zisserman, 2003] Sivic, J. and Zisserman, A. (2003).  Video google: A text retrieval approach to object matching in videos.  In Proc. IEEE Int. Conf. Comput. Vis., volume 2, pages 1470–1477.
  * [Somol et al., 2010] Somol, P., Novovicova, J., and Pudil, P. (2010).  Efficient feature subset selection and subset size optimization.  In Herout, A., editor, Pattern Recognition, chapter 4. IntechOpen, Rijeka.
  * [Srivastava et al., 2014] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. (2014).  Dropout: A simple way to prevent neural networks from overfitting.  Journal of Machine Learning Research, 15:1929–1958.
  * [Sun et al., 2018] Sun, L., He, L., Huang, Z., Cao, B., Xia, C., Wei, X., and Yu, P. S. (2018).  Joint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks (MEGA).  Technical report.
  * [Sutton, 2019] Sutton, R. S. (2019).  The bitter lesson.  Incomplete Ideas.
  * [Suwajanakorn et al., 2017] Suwajanakorn, S., Seitz, S. M., Kemelmacher-shlizerman, I., and Kemelmacher-Shlizerman, I. (2017).  Synthesizing Obama: Learning Lip Sync from Audio.  ACM Trans. Graph, 36.
  * [Tang et al., 2014] Tang, J., Alelyani, S., and Liu, H. (2014).  Feature selection for classification: A review.  Data Classification: Algorithms and Applications, pages 37–64.
  * [Van Den Oord et al., 2016] Van Den Oord, A., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., and Kavukcuoglu, K. (2016).  Wavenet: A Generative Model for Raw Audio.  Technical report.
  * [Van Gemert et al., 2010] Van Gemert, J. C., Veenman, C. J., Smeulders, A. W., and Geusebroek, J. M. (2010).  Visual word ambiguity.  IEEE Trans. Pattern Anal. Mach. Intell., 32(7):1271–1283.
  * [Vapnik and Izmailov, 2015] Vapnik, V. and Izmailov, R. (2015).  Learning with intelligent teacher: Similarity control and knowledge transfer.  pages 3–32.
  * [Vaswani et al., 2017] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017).  Attention Is All You Need.
  * [Wang et al., 2017] Wang, J., Zhang, Z., Xie, C., Zhou, Y., Premachandran, V., Zhu, J., Xie, L., and Yuille, A. (2017).  Visual Concepts and Compositional Voting.  Ann. Math. Sci. Appl., 3(1):151–188.
  * [Wang et al., 2000a] Wang, J., Zucker, J.-D., and Fr, J.-D. Z. (2000a).  Solving the Multiple-Instance Problem: A Lazy Learning Approach.  Technical report.
  * [Wang et al., 2000b] Wang, L., Liu, J., and Li, S. Z. (2000b).  MRF parameter estimation by MCMC method.  Pattern Recognit., 33(11):1919–1925.
  * [Wang et al., 2019] Wang, X., Ji, H., Shi, C., Wang, B., Cui, P., Yu, P., and Ye, Y. (2019).  Heterogeneous Graph Attention Network (HAN).  Technical report.
  * [Webb, 2003] Webb, A. (2003).  Statistical Pattern Recognition: Second Edition.
  * [Williamson and Gorelik, 2014b] Williamson, M. and Gorelik, V. (U.S. Patent US8646080B2, Feb. 2014b).  Method and apparatus for removing harmful software.
  * [Williamson and Gorelik, 2014a] Williamson, M. and Gorelik, V. (U.S. Patent US8719924B1, May 2014a).  Method and apparatus for detecting harmful software.
  * [Woof and Chen, 2020] Woof, W. and Chen, K. (2020).  A framework for end-to-end learning on semantic tree-structured data.
  * [Wu et al., 2019] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. (2019).  A Comprehensive Survey on Graph Neural Networks.
  * [Yoon et al., 2019] Yoon, K., Liao, R., Xiong, Y., Zhang, L., Fetaya, E., Urtasun, R., Zemel, R., and Pitkow, X. (2019).  Inference in Probabilistic Graphical Models by Graph Neural Networks.  Technical report.
  * [Yu et al., 2010] Yu, T., Lippmann, R., Riordan, J., and Boyer, S. (2010).  EMBER: A global perspective on extreme malicious behavior.  In ACM Int. Conf. Proceeding Ser., pages 1–12.
  * [Yuan et al., 2017] Yuan, X., He, P., Zhu, Q., and Li, X. (2017).  Adversarial examples: Attacks and defenses for deep learning.
  * [Zaheer et al., 2017] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., and Smola, A. (2017).  Deep Sets.  Adv. Neural Inf. Process. Syst., 2017-Decem:3392–3402.
  * [Zhang et al., 2018a] Zhang, H., Wang, S., Xu, X., Chow, T. W. S., and Wu, Q. M. J. (2018a).  Tree2vector: Learning a vectorial representation for tree-structured data.  IEEE Transactions on Neural Networks and Learning Systems, 29(11):5304–5318.
  * [Zhang et al., 2018b] Zhang, H., Wang, S., Xu, X., Chow, T. W. S., and Wu, Q. M. J. (2018b).  Tree2vector: Learning a vectorial representation for tree-structured data.  IEEE Transactions on Neural Networks and Learning Systems, 29(11):5304–5318.
  * [Zhang et al., 2008] Zhang, J., Porras, P., and Ullrich, J. (2008).  Highly predictive blacklisting.  pages 107–122.
  * [Zhang and Zhou, 2008] Zhang, M.-L. and Zhou, Z.-H. (2008).  Multi-Instance Clustering with Applications to Multi-Instance Prediction.  Technical report.
  * [Zhang and Goldman, 2002] Zhang, Q. and Goldman, S. A. (2002).  EM-DD: An Improved Multiple-Instance Learning Technique.  In Dietterich, T. G., Becker, S., and Ghahramani, Z., editors, Adv. Neural Inf. Process. Syst. 14, pages 1073–1080. MIT Press.
  * [Zhang et al., 2018a] Zhang, Y., Xiong, Y., Kong, X., Li, S., Mi, J., Zhu, Y., and Mi, J.-H. (2018a).  Deep Collective Classification in Heterogeneous Information Networks (GraphInception).  page 10.
  * [Zhang et al., 2018b] Zhang, Z., Cui, P., and Zhu, W. (2018b).  Deep Learning on Graphs: A Survey.
  * [Zheng et al., 2015] Zheng, S., Jayasumana, S., Romera-Paredes, B., Vineet, V., Su, Z., Du, D., Huang, C., and Torr, P. H. S. (2015).  Conditional Random Fields as Recurrent Neural Networks.  ArXiv e-prints.
  * [Zhou et al., 2014a] Zhou, B., Khosla, A., Lapedriza, A., Oliva, A., and Torralba, A. (2014a).  Object detectors emerge in deep scene cnns.
  * [Zhou et al., 2018] Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. (2018).  Graph Neural Networks: A Review of Methods and Applications.
  * [Zhou et al., 2014b] Zhou, Z. H., Chawla, N. V., Jin, Y., and Williams, G. J. (2014b).  Big data opportunities and challenges: Discussions from data analytics perspectives [Discussion Forum].
  * [Zhou et al., 2008] Zhou, Z.-H., Sun, Y.-Y., and Li, Y.-F. (2008).  Multi-Instance Learning by Treating Instances As Non-I.I.D. Samples.  Technical report.
  * [Zhou and Zhang, 2002] Zhou, Z.-H. and Zhang, M.-L. (2002).  Neural Networks for Multi-Instance Learning.  Technical report.