Patent Description:
"<NPL>) discloses an approach to detect anomalous graphs in a stream of directed and labeled heterogeneous edges. The stream consists of a sequence of edges derived from different graphs. Each of these dynamic graphs represents the evolution of a specific activity in a monitored system whose events are acquired in real-time. The disclosed approach is based on graph clustering and uses a graph embedding based on substructures and graph edit distance. The graph representation updates incrementally the graph vectors when a new edge arrives. This allows the detection of anomalies in real-time to facilitate sensitive applications such as cyber-security.

<CIT> discloses a lateral movement application identifies lateral movement (LM) candidates that potentially represent a security threat. Security platforms generate event data when performing security-related functions, such as authenticating a user account. The disclosed technology identifies lateral movement (LM) candidates by refining a population of LM candidates based on an analysis of a time constrained graph in which nodes represent entities, and edges between nodes represent a time sequence of login or other association activities between the entities. The graph is created based on an analysis of the event data, including time sequences of the event data.

Various embodiments of an approach for anomaly detection based on graph embeddings are herein described with reference to the accompanying drawings, in which:.

Disclosed herein is an approach to detecting anomalies in a time series of interaction events between a set of resources and a set of entities accessing the resources, e.g., in a computer network. The interaction events each involve an access, or at least an attempted access, by one of the accessing entities (herein also "accessing nodes") to one of the resources (herein also resource nodes"), and are therefore herein also referred to as "access events. " The term "resources" as used herein can refer to both hardware resources (e.g., devices like computers, data storage devices, peripheral devices, sensors, etc.) and any kind of data or software (e.g., in the form of files or documents), such as, without limitation, web sites, text documents, images, video, audio files, multimedia files, computer programs, etc. The term "accessing node" is herein understood broadly to encompass human users as well as machines or programs that act as automated agents accessing resources (such as, e.g., client devices accessing resources on servers, or mobile devices accessing cloud services). In the following description, the disclosed approach is in various places illustrated, for specificity and ease of reference, with the example of users accessing resources; it is to be understood, however, that other types of accessing nodes can generally be substituted for the users.

Anomalies in access events can be indicative of security threats, such as, for example, a compromised user account or a user that presents an insider risk. Accordingly, the described systems and methods for monitoring accesses to resources for anomalies can help discover security threats, in some embodiments triggering some type of mitigating action (e.g., raising an alert to a network administrator or curtailing network access). In addition, the systems and method for anomaly monitoring and detection may be used to provide context to an investigation of already known threats by highlighting specific abnormal behaviors of an accessing node. For example, in the event of compromised user credentials, user behavior within the network may be monitored for malicious exploitation of the stolen credentials as distinct from ordinary use of the credentials by the authorized user.

Anomaly detection in accordance herewith is based on the notion that regular and benign resource utilization tends to be clustered around groups of accessing nodes collectively accessing generally the same sets of resource nodes, and conversely, that malicious activity, e.g., by a compromised user account, likely involves accesses to resource nodes for which there is no historical precedent. Accordingly, access events are evaluated, in accordance herewith, based on their similarity to prior access events, and flagged as suspicious if their dissimilarity from those other events exceeds a pre-defined threshold.

In the disclosed approach, access events in a network are represented as a bipartite graph in which accessing nodes (like users) and resource nodes are represented by two distinct types of nodes (or vertices) of the graph, and (actual and/or attempted) accesses of resource nodes by accessing nodes are each represented by a time-stamped edge between a respective pair of nodes of both types. Conventional anomaly detection approaches for graph data usually involve representing the nodes in a feature space, and as such rely heavily on feature engineering; in these approaches, the quality of the engineered features directly affects the effectiveness of anomaly detection. In the approach disclosed herein, by contrast, representations of the nodes are learned directly from the graph structure, using bipartite graph embedding techniques.

"Graph embeddings" is the general name for a class of algorithms that learn vector representations of the network nodes which reflect the connection patterns of the nodes. Nodes with similar connection patterns are embedded close together, and those which are dissimilar are embedded far apart. Several algorithms that achieve such embeddings are known to those of ordinary skill in the art, and include, without limitation, techniques based on random walks (e.g., deepwalk , node2vec), deep learning, and matrix factorization. One particular approach, known as spectral embedding, employs the spectral decomposition of a matrix representation of the graph. There are many variants involving different matrix representations, regularization to improve performance, and degree-correction to remove the dependence of degree from the embeddings. These methods are well-understood from a statistical perspective, and tend to render the embeddings fast to compute. Bipartite graph embedding algorithms are adaptations of general graph embedding algorithms to bipartite graphs, and result in separate sets of graph embeddings for the two sets of nodes that allow similarity to be evaluated among nodes of the same type based on their connections to the nodes of the respective other type. Nodes of a given type that are similar in that they overlap in the nodes of the other type with which they are connected are embedded closer together than nodes that do not overlap, or overlap less, in the nodes of the other type with which they are connected.

The description that follows and the accompanying drawings further illustrate the use of bipartite graphs and associated graph embeddings in monitoring access to resource nodes in a network for anomalies, in accordance with various embodiments.

<FIG> is a block diagram of an example computing system <NUM> for monitoring access events within a computer network <NUM> for anomalies, in accordance with an embodiment. The computing system <NUM>, herein also "anomaly detection system," may be implemented with software executed and data structures stored on one or more computing machines each including one or more (e.g., general-purpose) processors and associated volatile memory as well as one or more non-volatile data storage devices; an example computing machine is described in more detail below with reference to <FIG>. Although depicted as outside the computer network <NUM>, the computing machines executing the software components of anomaly detection system <NUM> may be integrated with and thus form part of the monitored computer network <NUM>. The monitored computer network <NUM> itself likewise includes computing machines <NUM> (e.g., as described in <FIG>) that are interconnected via wired or wireless network connections (e.g., Ethernet, Wi-Fi, optical fiber, etc.) to form, e.g., a local area network (LAN) or wide area network (WAN); such a network may serve, for instance, as the intranet of an organization. The computing machines <NUM> of the computing network <NUM> generally host computer programs (e.g., web services) and/or data (e.g., text documents, images and video, multimedia files, databases, etc.), all depicted as files <NUM>. Users <NUM> may access these resources, that is, the computing machines <NUM> and the program or data files <NUM> executed and/or stored thereon. In addition to human users <NUM>, the computing machines <NUM> and/or computer programs themselves may access other machines and programs or data. For example, a web service or other software application may have the ability to call other programs, e.g., via suitable application programming interfaces (APIs).

For purposes of the disclosed anomaly detection approach, the computing machines <NUM> and their components (e.g., processors or data storage devices) and associated peripheral hardware (e.g., input/output devices like printers and microphones, sensors, etc.) as well as the hosted computer-program and data files <NUM> are all examples of resource nodes of the computer network <NUM>, and both users <NUM> and computing machines <NUM> or programs accessing those resources are examples of accessing nodes of (or associated with) the computer network <NUM>. As will by understood by those of ordinary skill in the art, in some embodiments, the same computing machine <NUM> or computer program can serve, alternatingly or even simultaneously, both as a resource node and an accessing node.

The anomaly detection system <NUM> generally includes multiple distinct components such as computational blocks and data structures, which may be integrated in a single software application or utilize functionality from multiple intercommunicating programs. An access event monitoring component <NUM> monitors interactions between users <NUM> and the hardware, software, and/or data resources within the network <NUM>, or between computing machines <NUM> and programs accessing other computing machines <NUM> and programs within the network, and writes time-stamped records of the observed access events to a database <NUM>. Each access event record includes, in addition to the timestamp, at least an identifier of the accessed resource node (e.g., a machine identifier like a MAC address, a program name or process identifier, a file name and location, etc.) and an identifier of the respective accessing node (e.g., a user account identifier or process identifier). The access event records may include records of both actual, successful accesses to resources and of access attempts that were thwarted by cyber security products associated with the computer network <NUM>. Alternatively, the recorded access events may be limited to successful accesses. Various cyber security products that provide the functionality for implementing the access event monitoring component <NUM> exist in the market and may be utilized for this purpose in some embodiments.

The anomaly detection system <NUM> further includes a graph-based access event representation component <NUM> that reads the access event records from the database <NUM> to create and maintain a bipartite graph representing the accessing nodes and the resource nodes as two distinct sets of nodes and the access events as edges between pairs of nodes of both sets. To the extent the same machine or program serves in the roles of both accessing node and resource node, it is represented twice in the graph. The graph-based access event representation component <NUM> further processes the bipartite graph to compute graph embeddings for the accessing nodes, the resource nodes, or both, and typically stores the graph embeddings in a database <NUM> for future use.

In addition to storing records of access events, the access event monitoring component <NUM> also forwards access events of interest to the anomaly detection component <NUM> for determination whether or not each forwarded event is anomalous. In some embodiments, all access events, or alternatively all access events that are new in the sense that the associated accessing node has not previously accessed the associated resource node, are evaluated for anomalies. In other embodiments, only selected access events, such as accesses of resources marked as particularly sensitive or access events that raise suspicion of posing a security threat, are further analyzed. For example, a security breach, such as a theft of login or authentication credentials or installation of malware, may be discovered independently from the anomaly detection approach disclosed herein, and trigger heightened scrutiny of all subsequent access events that are associated with the breach in some way (e.g., by involving use of the stolen credentials or access to machines where the malware was installed).

For any access event of interest, herein also "current access event," the anomaly detection component <NUM> retrieves, from the database <NUM>, the graph embeddings of the accessing and resource nodes of the current access event and the graph embeddings of accessing nodes that are linked to the resource node of the current access event and/or of resource nodes that are linked to the accessing node of the current access event in the bipartite graph, and computes an anomaly score from the embeddings, as detailed further with reference to <FIG>. In the event that either of the accessing node and the resource node of the current access event was not previously represented in the bipartite graph, the graph embedding of such missing node may be induced from other graph embeddings, or the embeddings of all nodes may be recomputed after the bipartite graph has been updated to include the new node. Upon computation of the anomaly score, the anomaly detection component <NUM> compares the score against the pre-defined anomaly threshold to make a determination whether the current access event is anomalous. If the anomaly detection component <NUM> finds the current access event to be anomalous, it may then communicate this determination to a threat mitigation component <NUM> to thereby cause some type of threat-mitigating action.

The threat mitigation component <NUM> may, for instance, notify a system administrator or security analyst <NUM> of the anomaly, e.g., by sending a push notification via email, text, or some other messaging system, or by listing the access event in an anomaly or security-alert log that can be accessed by the system administrator or security analyst <NUM> via an administrator console or similar user interface. Alternatively or additionally, the threat mitigation component <NUM> may trigger an automated action, such as presenting a logon challenge (e.g., multi-factor authentication) to a user associated with the current access event prior to granting access to the requested resource, denying access to the resource outright, or even revoking the credentials of the user to prevent future accesses to the same or other resources. The severity of the mitigating action taken may depend, in some instances, on the computed anomaly score. Additional mitigating actions will occur to those of ordinary skill in the art. Like the access event monitoring component <NUM>, the functionality of the threat mitigation component <NUM> may, in some embodiments, be provided by existing cyber security products.

<FIG> is a flow chart of an example method <NUM> of monitoring access events within a computer network <NUM> for anomalies, summarizing the operation of the anomaly detection system <NUM>. Upon commencement of the method <NUM> (at <NUM>), the computer network <NUM> is monitored for access events (act <NUM>), typically continuously, and time-stamped records of the access events are stored (act <NUM>). These access events are processed in two general stages, which may be referred to as training and scoring stages. In the training stage, the stored records are used to create a time-dependent bipartite graph, and after initial creation to maintain the graph via updates reflecting subsequent access events, and graph embeddings for accessing nodes and/or resource nodes are computed from the (most up-to-date) time-dependent graph (act <NUM>). In the scoring stage, access events of interest (also "current access events") are evaluated based on the respective previously computed graph embeddings to detect anomalies (act <NUM>), usually triggering performance of some mitigation action (in act <NUM>), which concludes the method (at <NUM>). Note that the training and scoring stages, while sequential from the perspective of a particular current access event, are, of course, generally concurrent from the viewpoint of monitoring the computer network for anomalous access events over time. That is, as access events are observed, they may be scored for purposes of anomaly detection, and used to update the bipartite graph and resulting embeddings, more or less in parallel.

In some embodiments, the bipartite graph is updated, and the graph embeddings are recomputed based on the updated graph, periodically, for instance, hourly, daily, weekly, monthly, or at some other regular time intervals. In other embodiments, the bipartite graph is updated at irregular intervals, e.g., responsive to some kind of update trigger event. For example, in applications where anomaly detection is not performed by default, but only once a security breach has already occurred (e.g., to provide further insight into the nature of the threat and the resulting damage), discovery of the security breach may constitute an update trigger event. As another example, in circumstances where embeddings tend to be stable over prolonged periods of time because access patterns do not change much, updates may be performed infrequently and triggered by some indicator that the graph has become "stale;" an example such indicator may be the increase of the anomaly detection rate above a certain trigger threshold. It is also possible, at least in principle, that the bipartite graphs and graph embeddings are updated continuously, responsive to each observed access event. Continuous updates ensure the highest anomaly detection accuracy, but come at significant computational cost; they may be feasible for smaller monitored computer networks <NUM>, but can become prohibitively costly for very large computer networks <NUM>.

Regardless of the update frequency, for a given point in time, the bipartite graph reflects, in some embodiments, all access events up the most recent update time, that is, any pair of an accessing node and a resource node in the graph is connected by an edge if and only if the accessing node has accessed the resource node at some point in the past (up to the most recent update time). In other embodiments, the time-dependent bipartite graph reflects access events in a rolling time window of specified duration, meaning that, for any given point in time, any pair of an accessing node and a resource node is connected by an edge if and only if the accessing node has accessed the resource within the specified time window preceding the most recent update time.

The determination whether a current event is anomalous may be made immediately upon detection of the access event ("in real time") based on the most recent update of the graph embeddings. In some embodiments, however, it may be beneficial to evaluate access events for anomalies in batches, e.g., to optimize the use of computational resources. In that case, it is possible that the graph embeddings at the time of batch processing are more current than some of the access events to be evaluated. For those older access events of interest, the anomaly scores may be determined based in part on access events in the future (relatively speaking), as they could be computed using embeddings of accessing nodes that accessed the resource node of interest, or of resource nodes that were accessed by the accessing node of interest, after the respective access events at issue occurred.

<FIG> is a schematic diagram of an example bipartite graph <NUM> representing access events within a computer network, in accordance with an embodiment. The bipartite graph <NUM> includes a set of accessing nodes (e.g., corresponding to users), depicted by circles and labeled <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and a set of resource nodes, depicted by squares and labeled <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. An access event that involves an (actual or attempted) access by one of the accessing nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM> to one of the resource nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> is represented by an edge between these two nodes. (To indicate the asymmetry of the interaction, the edges are depicted with arrows in <FIG>). As can be seen, accessing nodes may overlap in the resources they access, and conversely, resource nodes may overlap in the accessing nodes by which they are accessed, which results in a natural grouping. To illustrate, in the depicted example, accessing nodes <NUM> and <NUM> have collectively accessed resource nodes <NUM>, <NUM>, <NUM>, with nodes <NUM> and <NUM> accessed by both accessing nodes <NUM>, <NUM>, and accessing nodes <NUM>, <NUM>, <NUM> have collectively accessed resource nodes <NUM>, <NUM>, <NUM>, <NUM>, with nodes <NUM>, <NUM>, <NUM> each accessed by at least two of the accessing nodes. Contrast this, however, with the edge between accessing node <NUM> and resource node <NUM>: this resource node <NUM> has not been accessed by any other node within the group (i.e., node <NUM>) to which accessing node <NUM> belongs, nor has accessing node <NUM> accessed any other resources within the group to which resource node <NUM> belongs. As such, this edge, and the access event it represents, can be deemed an anomaly.

As will be appreciated, <FIG> depicts a very small, and thus simple, bipartite graph for ease of illustration. In practice, when representing network access events in a bipartite graph in accordance herewith, the number of nodes and edges will generally be much larger, and the network structure much more complex. Graph embedding techniques allow condensing much of the rich information inherent in the graph structure into low-dimensional representations (the graph embeddings) that are computationally tractable, yet meaningful.

<FIG> is a flow chart of an example method <NUM> of determining graph embeddings for resources and accessing nodes, illustrating the training stage in more detail for an individual iteration associated with a bipartite graph and graph embeddings for a given point in time. Depending on whether a bipartite graph already exists at the start (<NUM>) of the method <NUM>, the method <NUM> involves either creating a bipartite graph from scratch, or updating an already existing bipartite graph, based on the access events. Generating the graph involves creating edges to indicate for each pair of an accessing node and a resource node whether the accessing node has accessed the resource node at any time up to the current point in time, or within a finite time window of specified length preceding the current point in time, depending on the particular embodiment. The edges may be binary or weighted. In the latter case, edge weights may be determined, e.g., as functions of the number of access events between the pair of nodes that the edge connects. In the case of an update to an already existing graph with binary edges, only access events since the most recent update need be considered when creating new edges. However, if the time-based bipartite graph is to reflect only access events within a certain time window preceding the current point in time, an additional check may be used to identify any edges that are based on access events that all precede the time window, and these "expired" edges are removed from the graph. Alternatively, the updated bipartite graph can be created from scratch based on the access events that fall within the time window. Creating the graph and edges can, in practice, take the form of populating a bi-adjacency matrix whose rows correspond to the accessing nodes and whose columns correspond to the resource nodes, or vice versa.

Following assignment of edges to pairs of nodes, the graph may, optionally, be pruned by removing nodes connected to a number of nodes of the other type that is in excess of a specified upper threshold number or below a specified lower threshold number (act <NUM>). For example, resource nodes that have been accessed by more than a pre-defined number (e.g., <NUM>) of users (or other accessing nodes) are likely commonly referenced and unlikely to contain sensitive information, and may therefore be deemed public for all practical purposes, obviating any need for further monitoring them. Resource nodes connected to fewer than a lower threshold number of users (or other accessing nodes) may be removed for the sake of avoiding false positives that are otherwise likely to be raised whenever a new user accesses the resource.

Once the graph has been updated and/or pruned, a bipartite graph embedding algorithm is performed to learn low-dimensional vector representations, called embeddings, of the accessing nodes, the resource nodes, or both in a common vector space (act <NUM>). Suitable graph embedding algorithms are known to those of ordinary skill in the art (for an example graph embedding algorithm, see <NPL>). Following computation of the graph embeddings, the method <NUM> ends (at <NUM>). The distance between the embeddings of any two accessing nodes or any two resource nodes, as computed with a distance function or metric as the terms are commonly understood in mathematics, represents a measure of dissimilarity between them. Distances between the graph embeddings computed in the training stage are determined and used subsequently in the scoring stage.

<FIG> is a flow chart of an example method <NUM> of detecting anomalies in network accesses based on graph embeddings of resource and accessing nodes, illustrating the scoring stage for a given access event of interest. Broadly speaking, the storing stage involves computing an anomaly score that aims to quantify the level of surprise at the particular access event, such as, from the perspective of the accessed resource node, the surprise at receiving an access request from the accessing node (e.g., user) in question. For a user (or other accessing node) u accessing a resource r, consider the set Ur of the embeddings of the users who have accessed resource r in the pre-defined time window (which may be finite or extend all the way to the beginning of monitoring access events). Upon start of the method <NUM> (at <NUM>), the first step in determining the anomaly score is to compute the pairwise dissimilarities between user u and each of the users who have accessed resource r in the pre-defined time window in terms of their embedding distances (in act <NUM>). Any metric operating on vectors can generally be used for this purpose; example metrics include the Euclidian distance and the cosine distance.

The anomaly score for the access event is determined from the pairwise embedding distances between user u and each of the users who have previously accessed the same resource r (in act <NUM>). In some embodiments, the anomaly score is taken to be the minimum of these distances, that is, the distance between the embeddings of user u and its nearest neighbor in <IMG>. In other embodiments, the anomaly score is the distance between the embeddings of user u and its second-nearest neighbor. The anomaly score may also be computed as some combination of the individual distances of the user embeddings within <IMG> from the embedding of user u. For example, the Mahalanobis distance may be used to measure the distance between the embedding of user u and the mean of the user embeddings within <IMG>, e.g., normalized by the standard deviation of the distribution of user embeddings in <IMG> around the mean.

In some embodiments, the roles of the accessing nodes (e.g., users) and resources are exchanged, so that the level of surprise at an access is evaluated from the perspective of the user rather than the resource. In that case, the pairwise embedding distances between the resource r in question and the set of other resources previously accessed by the user u are computed (in <NUM>), and the anomaly score is determined based on these distances (in <NUM>). Both perspectives may also be combined to produce a single, stronger score. For example, partial anomaly scores computed separately based on distances between user embeddings and distances between resource embeddings may be averaged, optionally in a weighted manner, to form the overall anomaly score.

To make a decision whether the access event is anomalous, the computed anomaly score is compared against a pre-defined anomaly threshold (at <NUM>), and access events with an anomaly score greater than the threshold are flagged as anomalous (in <NUM>), which concludes the method <NUM> (at <NUM>). If the anomaly score represents the nearest-neighbor distance, setting the threshold at zero is equivalent to flagging all access events for which the user has not previously used the resource. Using, e.g., the second-nearest-neighbor distance provides some robustness of the anomaly detection method to previous anomalous events.

To describe anomaly detection based on graph embeddings of accessing nodes and/or resources nodes more formally, consider a dynamic bipartite graph with m accessing nodes (e.g., users) Vu, n resource nodes Vr, and time-stamped edges <MAT>. Here, an edge (u, r, t) ∈ E represents an access event involving accessing node u accessing (or attempting to access) resource r at time t. For a time <MAT>, let A(t) ∈ {<NUM>,<NUM>}m×n denote the bi-adjacency matrix of a snapshot of the graph up to time t, where <MAT>if (u, r, s) ∈ E for any s < t (or, if only prior access attempts within a finite time window Δt are considered, for any t - Δt < s < t), and <MAT> otherwise. Considering, for specificity, the case of anomaly scoring based on dissimilarity between u and other accessing nodes that have previously accessed r, the general framework for scoring a new edge (u, r, t) is as follows:.

In one embodiment, the graph embeddings are computed as spectral embeddings using the regularized bi-Laplacian matrix, and subsequently projected. The regularized bi-Laplacian matrix Lr with regularization parameter <MAT> is defined as: <MAT> where D(u) and D(r) are the diagonal user (or accessing-node) and resource degree matrices with <MAT> and <MAT>, and In is the n × n identity matrix. Given the regularized bi-Laplacian matrix and the embedding dimension d, the embedding algorithm is as follows:.

The vectors <MAT> are embeddings of the accessing nodes, and the vectors <MAT>are embeddings of the resources. In the approach outlined above, only the accessing-node embeddings are used. However, as previously indicated, it is also possible to use, instead, only the resource embeddings, or both accessing-node and resource embeddings for a combined anomaly score.

The embedding dimension (or "dimensionality") d is a hyper-parameter, which may be chosen to balance the conflicting goals of keeping computational cost low while retaining enough of the complexity and richness of the graph data for the embeddings to be useful in anomaly detection. Both computational cost and the amount of information captured in the embeddings increase with the embedding dimension d, but the added benefit of further increasing d tends to diminish at a certain point. In some embodiments, this point is determined (in an approximate manner) based on examination of a plot of the singular values of the graph bi-adjacency matrix, known as a scree plot.

<FIG> is an example scree plot of singular values as may be used in selecting an embedding dimension for the graph embeddings, in accordance with an embodiment. As shown, in a scree plot, the singular values are provided along the ordinate as a function of rank (the position in an ordered listed of the singular values) plotted along the abscissa. The singular values up to a certain rank can serve as a proxy for the richness of the information retained in graph embeddings of a dimension equal to that rank. Therefore, the point of diminishing returns from increasing the dimension d can be found by identification of an "elbow" <NUM> in the scree plot where the singular values level off. The elbow identification can be done by eye or using an automated method such as the profile likelihood method.

The regularization parameter may be set to the average in-degree. Regularization improves the performance of spectral embeddings by delocalizing the principle singular vectors which otherwise tend to localize on low-degree nodes. The second stage of the algorithm performs degree correction-that is, it removes the dependence of a node's degree from its position in the embedding space. This is important in the instant application, where the types of users that tend to access a resource are of interest, not the number of people.

In one embodiment, the edges (u, r, t) are scored using simple nearest-neighbor anomaly detection. Let Xr = {Xν(ν,r, s),s < t} denote the set of embeddings for accessing nodes who have accessed resource r before time t. The anomaly score for an edge is given by the distance from Xu to its nearest neighbor in Xr. If an accessing node u has previously accessed a resource r (before time t), the edge (u, r, t) will receive an anomaly score s(u,r,s) = <NUM>, since Xu ∈ Xr. Otherwise, s(u,r,s) > <NUM>. An edge may be flagged as anomalous if its anomaly score is greater than a pre-defined anomaly threshold <MAT>. Setting α = <NUM> is equivalent to flagging an edge whenever a user accesses a resource for the first time.

The disclosed approach to monitoring network accesses for anomalies based on bipartite graph embeddings provides multiple benefits. Deriving representations of the accessing nodes (like users) and resources directly from the structure of the bipartite graph inherently captures and takes advantage of the information about access patterns that the graphs contains, and obviates the need for hand-designed representations. Further, the use of graph embeddings to represent the nodes allows condensing the rich graph information in a manner that retains enough of its complexity in the multi-dimensional representations while at the same reducing the dimensionality of the problem significantly for computational tractability. For example, in a typical security application, the bipartite graph of access events may include thousands, tens of thousands, or hundreds of thousands of nodes of each type, whereas typical useful graph embedding dimensions may be on the order of ten, which very efficiently compresses the relevant information within the (usually sparse) bipartite graph. The embedding dimension may, further, be tuned (e.g., based on a scree plot as described above) to optimize the tradeoff between low computational cost and relevant information content. With these benefits and characteristics, the disclosed approach renders continuously monitoring large networks for anomalies feasible and scalable, complementing other means of discovering security threats.

To illustrate the anomaly detection potential of the above-described anomaly-detection method with an example, <FIG> provide data associated with its application to a set of <NUM>,<NUM> Sharepoint sites accessed by a total of <NUM>,<NUM> users (each site accessed by between <NUM> and <NUM> of the users) of an organization. An edge represents an interaction between a user and a Sharepoint site. In the training stage, a bipartite graph and its associated bi-adjacency matrix were generated based on <NUM> days of logs. <FIG> shows the scree plot of the top one hundred ordered singular values of the bi-adjacency matrix for this period. An embedding dimension d = <NUM> was chosen based on the elbow <NUM> in the scree plot. Following initial training, user-site interactions during the subsequent <NUM> days were scored using the described approach, and embeddings were updated daily. A total of <NUM>,<NUM>,<NUM> edges were scored. Of these, <NUM>% received a score of zero, indicating that the edge had occurred previously. <FIG> is a graph showing the distribution of the non-zero anomaly scores computed based on graph embeddings. For comparison, two alternative anomaly detection methods were applied to the same data: (<NUM>) In a "naive" approach, an anomaly was raised whenever a user accessed a resource that he had not previously accessed. (<NUM>) In an "organizational," at a specified level of the organizational hierarchy, an anomaly was raised whenever a user accessed a site which no other member of his respective user group had previously visited. The first alternative approach is equivalent to the graph-based anomaly detection with a detection threshold set to zero, and produces a large amount of anomalies. The second approach uses a notion of similarity between users, but rather than being learned from data, similarity is determined based simply on whether two users belong to the same organization. This approach raised <NUM>,<NUM> anomalies, a similar amount to the graph-based approach when a threshold of <NUM> is applied.

<FIG> shows the distribution of the anomaly scores computed with the graph-based approach for the edges flagged based on organizational anomaly detection. As can be seen, anomalies raised by the organizational approach tend to be assigned high anomaly scores using graph-based anomaly detection. An advantage of anomaly detection via graph embeddings compared with a pure organizational approach is that, if users regularly behave as if they belong to a different organization (e.g., because they work on an inter-organizational project), the former approach can learn this behavior, while the latter approach, which is based on fixed metadata, cannot.

The anomaly detection approach described herein can be implemented with a combination of computing hardware and software, e.g., with software executing on a general-purpose computer, or with a combination of special-purpose processors (such as hardware accelerators adapted for certain computational operations) and software executed on general-purpose processors.

<FIG> illustrates a block diagram of an example machine <NUM> upon which any one or more of the techniques (e.g., methodologies) discussed herein may perform. The machine <NUM> may be a personal computer (PC), a tablet PC, a set-top box (STB), a personal digital assistant (PDA), a mobile telephone, a smart phone, a web appliance, a network router, switch or bridge, a server computer, a database, conference room equipment, or any machine capable of executing instructions (sequential or otherwise) that specify actions to be taken by that machine.

The storage device <NUM> may include a machine-readable medium <NUM> on which is stored one or more sets of data structures or instructions <NUM> (e.g., software) embodying or utilized by any one or more of the techniques or functions described herein. In an example, one or any combination of the hardware processor <NUM>, the main memory <NUM>, the static memory <NUM>, or the storage device <NUM> may constitute machine-readable media.

While the machine-readable medium <NUM> is illustrated as a single medium, the term "machine-readable medium" may include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) configured to store the one or more instructions <NUM>.

The term "machine-readable medium" may include any medium that is capable of storing, encoding, or carrying instructions for execution by the machine <NUM> and that cause the machine <NUM> to perform any one or more of the techniques of the present disclosure, or that is capable of storing, encoding or carrying data structures used by or associated with such instructions. In some embodiments, machine-readable media include transitory propagating signals. In some embodiments, machine-readable media include non-transitory machine-readable media, such as data storage devices. Non-limiting machine-readable medium examples include solid-state memories, and optical and magnetic media. Specific examples of machine-readable media may include: non-volatile memory, such as semiconductor memory devices (e.g., Electrically Programmable Read-Only Memory (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM)) and flash memory devices; magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; Random Access Memory (RAM); Solid State Drives (SSD); and CD-ROM and DVD-ROM disks. In some examples, machine-readable media are non-transitory machine-readable media.

Claim 1:
A system (<NUM>) for monitoring accesses to resource nodes (<NUM>, <NUM>, <NUM>-<NUM>) in a computer network (<NUM>) for anomalies, the system comprising:
one or more computer processors (<NUM>); and
one or more computer-readable media (<NUM>, <NUM>, <NUM>) storing instructions (<NUM>) which, when executed by the one or more computer processors, cause the one or more computer processors to perform operations comprising:
monitoring the computer network for access events each involving an access or attempted access by one of a plurality of accessing nodes (<NUM>, <NUM>, <NUM>-<NUM>) to one of a plurality of resource nodes (<NUM>, <NUM>, <NUM>-<NUM>);
storing time-stamped records (<NUM>) of the access events;
creating and maintaining, based on the stored records, a time-dependent bipartite graph (<NUM>) that represents the plurality of accessing nodes and the plurality of resource nodes as two distinct sets of nodes and the access events as edges between the nodes;
computing time-dependent multi-dimensional graph embeddings (<NUM>) of at least one of the plurality of accessing nodes or the plurality of resource nodes from the time-dependent bipartite graph;
computing an anomaly score for a current access event based on at least one of:
distances of graph embeddings of an accessing node associated with the current access event from graph embeddings of accessing nodes that previously accessed a resource node associated with the current access event, or
distances of a graph embedding of the resource node associated with the current access event from graph embeddings of resource nodes previously accessed by the accessing node associated with the current access event;
determining, based on comparison of the anomaly score against a specified anomaly threshold, that the current access event is anomalous; and
responsive to determining that the current access event is anomalous, causing at least one mitigating action.