A Multi-Perspective View on Model-Based Exceptional Link Analysis on Complex Interaction Networks

The detection of anomalies and exceptional patterns in the context of link analysis on complex interaction networks is a prominent research direction in complexity and network science. Applications include, e.g., fraud detection in online social networks, discovering events or unusual topics in heterogeneous network data, or identifying specific interesting or outstanding behavior, for example, considering influential or "central" actors. Taking an abstract view, an anomaly can be considered as a pattern that does not conform to some notion of the expected, normal behavior. A straightforward general anomaly detection approach first defines a range covering the expected behavior, and then identifies any observation in the data that does not belong to this range as an anomaly. However, there is usually no clear formalization of the "normal behavior". In addition, the notion of an anomaly includes other factors compared to a mere outlier which is typically defined by statistical criteria. The concept of an anomaly typically captures more complex criteria, including semantics, (user) expectations and complex data-driven structures. Thus, it is difficult to formalize anomalies with a complex structure, e.g., relating to a group structure instead of considering isolated points. Therefore, such complex (collective) anomaly patterns are often not detected if the individual contained points seem normal and only their interaction causes an anomaly. In addition, the complexity of anomaly detection is further enhanced by multi-relational and multi-dimensional data. This poster presents model-based approaches and methods for addressing and formalizing these issues in the context of complex interaction networks, and exemplifies promising directions for its implementation. We basically distinguish between approaches that require an explicit formalization, i. e., theory-based, knowledge-based and preference-based modeling, and those that rely on data-driven and structure driven criteria, i. e., behavior-based and structure-based modeling. Then, we specifically consider exceptional pattern mining and link prediction. Exceptional pattern mining can be applied, e.g., for subgroup discovery and community detection. The typical focus of link prediction targets the dynamics and mechanisms in the creation of links between nodes in complex networks. Then, the goal is to learn a model for predicting the links accurately. However, such a model can also be applied for identifying anomalous links. For the sketched model-based approaches, we exemplify theory-based models (e.g., exploiting homophily), knowledge-based models (e.g., utilizing logical formalisms such as answer set programming), preference-based models (using user preferences/expectations), as well as behaviorbased and structure-based models (utilizing data-driven interestingness functions and structural/topological network criteria).