Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Behrouz, Ali
Master of Science - MSc
University of British Columbia
The problem of identifying anomalies in dynamic networks is a fundamental task with a wide range of applications from understanding brain diseases/disorders to fraud detection in financial networks. However, it raises critical challenges due to the complex nature of anomalies, lack of ground truth knowledge, and complex and dynamic interactions in the network. Most existing approaches usually study simple networks with a single type of connection. However many complex systems exhibit natural relationships with different types of connections, yielding multiplex networks. We first propose ANOMULY, a graph neural network-based unsupervised edge anomaly detection framework for multiplex dynamic networks. ANOMULY learns node encodings in different relation types, separately, and then uses an attention mechanism that incorporates information across different types of relations. To improve generalizability and scalability, we further propose ADMIRE, an inductive and unsupervised anomaly detection method that extracts the causality of the existence of connections by temporal network motifs. To extract the temporal network motifs, ADMIRE uses two different casual multiplex walks, inter-view and intra-view that automatically extract and learn temporal multiplex network motifs. Despite the outstanding performance of ADMIRE, using it in sensitive decision-making tasks requires explanations for the model's predictions. Accordingly, we introduce an interpretable, weighted optimal sparse decision tree model, ADMIRE++, that mimics ADMIRE, to provide explanations for ADMIRE's predictions. With extensive experiments, we show the efficiency and effectiveness of our approaches in detecting anomalous connections in various domains, including social and financial networks. We further focus on understanding abnormal human brain activity of people living with Parkinson’s Disease, Attention Deficit Hyperactivity Disorder, and Autism Spectrum Disorder to show how these methods can assist in understanding the biomarkers for these diseases.
Anomaly Detection in Multiplex Networks: From HumanBrain Activity to Financial NetworksbyAli BehrouzB.Sc. Computer Engineering, Sharif University of Technology, 2020A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)August 2023© Ali Behrouz, 2023The following individuals certify that they have read, and recommend to the Facultyof Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Anomaly Detection in Multiplex Networks: From Human Brain Activityto Financial Networkssubmitted by Ali Behrouz in partial fulfillment of the requirements for the degreeof Master of Science in Computer Science.Examining Committee:Margo Seltzer, Professor, Computer Science, UBCSupervisorLaks V.S. Lakshmanan, Professor, Computer Science, UBCSupervisory CommitteeiiAbstractThe problem of identifying anomalies in dynamic networks is a fundamental taskwith a wide range of applications from understanding brain diseases/disorders tofraud detection in financial networks. However, it raises critical challenges dueto the complex nature of anomalies, lack of ground truth knowledge, and com-plex and dynamic interactions in the network. Most existing approaches usuallystudy simple networks with a single type of connection. However many complexsystems exhibit natural relationships with different types of connections, yieldingmultiplex networks. We first propose ANOMULY, a graph neural network-basedunsupervised edge anomaly detection framework for multiplex dynamic networks.ANOMULY learns node encodings in different relation types, separately, and thenuses an attention mechanism that incorporates information across different typesof relations. To improve generalizability and scalability, we further propose AD-MIRE, an inductive and unsupervised anomaly detection method that extracts thecausality of the existence of connections by temporal network motifs. To extractthe temporal network motifs, ADMIRE uses two different casual multiplex walks,inter-view and intra-view that automatically extract and learn temporal multiplexnetwork motifs. Despite the outstanding performance of ADMIRE, using it insensitive decision-making tasks requires explanations for the model’s predictions.Accordingly, we introduce an interpretable, weighted optimal sparse decision treemodel, ADMIRE++, that mimics ADMIRE, to provide explanations for ADMIRE’spredictions. With extensive experiments, we show the efficiency and effectivenessof our approaches in detecting anomalous connections in various domains, includ-ing social and financial networks. We further focus on understanding abnormalhuman brain activity of people living with Parkinson’s Disease, Attention DeficitiiiHyperactivity Disorder, and Autism Spectrum Disorder to show how these methodscan assist in understanding the biomarkers for these diseases.ivLay SummaryThis thesis focuses on the detection of abnormal connections or interactions in com-plex systems. Identifying unexpected connections is a fundamental problem withbroad applications, ranging from understanding brain diseases/disorders to identify-ing fraudulent transactions in financial networks. Existing approaches apply only tosimple systems in which participants in a system interact in only one way. However,there are many different types of interactions in the real world. We introduce twomachine learning-based methods that identify abnormal patterns without havingaccess to examples of such abnormal patterns. We then present a technique thatexplains why our method made the predictions it did. This explainability procedureis crucial for fostering transparency and trust in decision-making processes, enablinghumans to understand the basis of AI-driven decisions. Finally, we demonstratehow the proposed methods contribute to understanding abnormal brain activity thatmight underlie brain diseases/disorders.vPrefaceThe work presented in this thesis is an original work done by Ali Behrouz under thesupervision of Prof. Margo Seltzer. A version of chapters 4, 5, and 6 of this workhave been published as:1. Ali Behrouz and Margo Seltzer. “Anomaly Detection in Multiplex DynamicNetworks: from Blockchain Security to Brain Disease Prediction.” TemporalGraph Learning Workshop in NeurIPS 2022 [17].2. Ali Behrouz and Margo Seltzer. “Anomaly Detection in Human Brain viaInductive Learning on Temporal Multiplex Networks” Machine Learning forHealthcare Conference 2023 [18].3. Ali Behrouz and Margo Seltzer. “ADMIRE++: Explainable Anomaly De-tection in the Human Brain via Inductive Learning on Temporal MultiplexNetworks” Interpretable Machine Learning in Healthcare Workshop in ICML2023 [19].viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Preliminaries and background . . . . . . . . . . . . . . . . . . . . . 62.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . . . 72.3 GRU Cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Skip-connections . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 MLP-Mixer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10vii2.6 (Weighted) Optimal Sparse Decision Trees . . . . . . . . . . . . . 112.7 Brain Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1 Anomaly Detection in Dynamic Networks . . . . . . . . . . . . . 143.2 Dynamic Graph Neural Networks . . . . . . . . . . . . . . . . . 153.3 Multiplex Graph Learning . . . . . . . . . . . . . . . . . . . . . 163.4 Anomaly Detection in Multiplex Networks . . . . . . . . . . . . . 164 ANOMULY: Edge Anomaly Detection Framework in Multiplex Dy-namic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 ANOMULY: Anomaly Detection in Multiplex Dynamic Networks 194.2.1 GNN Architecture . . . . . . . . . . . . . . . . . . . . . 214.2.2 Update Modules . . . . . . . . . . . . . . . . . . . . . . 214.2.3 Attention Mechanism . . . . . . . . . . . . . . . . . . . . 224.2.4 view-dependent Embedding . . . . . . . . . . . . . . . . 224.2.5 Anomaly Score Computation . . . . . . . . . . . . . . . . 234.2.6 Training and Loss Function . . . . . . . . . . . . . . . . 234.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.3.1 Experimental Setup and Metrics . . . . . . . . . . . . . . 254.3.2 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.3.3 Inject Anomalous Edges in Multiplex Networks . . . . . . 274.3.4 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 ADMIRE: Inductive and Scalable Anomaly Detection in MultiplexDynamic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.2 ADMIRE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.2.1 Anonymous Multiplex Temporal Walk . . . . . . . . . . . 355.2.2 Neural Encoding . . . . . . . . . . . . . . . . . . . . . . 405.2.3 ADMIRE Framework . . . . . . . . . . . . . . . . . . . . 43viii5.3 ADMIRE++: Explainable Anomaly Detection in Multiplex Dy-namic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . 465.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.4.3 Ablation Study . . . . . . . . . . . . . . . . . . . . . . . 485.4.4 How Well Does ADMIRE++ Mimic ADMIRE? . . . . . . 505.4.5 What Does the Generated Tree Look Like? . . . . . . . . 505.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516 Anomaly Detection in the Human Brain . . . . . . . . . . . . . . . . 546.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.2 Related Work on Machine Learning for Brain Networks . . . . . . 566.3 Why/How to Model Human Brain as a Multiplex Network . . . . 576.4 Modified Attention Mechanism For Multiplex Brain Networks . . 586.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.5.1 Experimental Setting Details . . . . . . . . . . . . . . . . 596.5.2 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.5.3 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . 616.5.4 Experimental Setup . . . . . . . . . . . . . . . . . . . . . 616.5.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 626.5.6 Results on Real-world Datasets . . . . . . . . . . . . . . 666.5.7 ADMIRE++ Explanations . . . . . . . . . . . . . . . . . 697 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73A Supporting Materials . . . . . . . . . . . . . . . . . . . . . . . . . . 96A.1 Performance of the Modified Attention on General Datasets . . . . 96ixList of TablesTable 4.1 The value of hyper-parameters of ANOMULY. Here, η and µcontrol how close the encodings of two nodes should be so theirconnection is normal. Also, λ controls the tradeoff between themargin-based pairwise loss function and the regularization term. 25Table 4.2 Network Statistics. Here |V| is the number of nodes, |E| is thenumber of edges in all views, and |L| is the number of views. . 26Table 4.3 Performance comparison of ANOMULY and baselines in multi-plex networks (AUC). . . . . . . . . . . . . . . . . . . . . . . 28Table 4.4 Performance comparison of ANOMULY and baselines in single-layer networks (AUC). . . . . . . . . . . . . . . . . . . . . . . 29Table 4.5 Ablation study on ANOMULY (AUC). The first row replacesthe GRU with an MLP. The second row removes the attentionmechanism, and the third row replaces the attention mechanismwith SUM(.). . . . . . . . . . . . . . . . . . . . . . . . . . . 29Table 5.1 Performance comparison of ADMIRE and baselines in multiplexnetworks (AUC). . . . . . . . . . . . . . . . . . . . . . . . . . 47Table 5.2 Performance comparison of ADMIRE and baselines in single-layer networks (AUC). . . . . . . . . . . . . . . . . . . . . . . 47Table 5.3 Ablation study on ADMIRE (AUC). In each row, we remove/re-place one of the ADMIRE’s components and keep the othersunchanged. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49xTable 5.4 Accuracy (%) of generated tree explanation on Amazon, DBLPand Ethereum. This table shows how well ADMIRE++ mimicsADMIRE predictions. We embolden the best results for eachdepth and use an underline to show the best performance foreach dataset. . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Table 6.1 Performance comparison of ADMIRE and baselines in multiplexbrain networks (AUC). . . . . . . . . . . . . . . . . . . . . . . 63Table 6.2 Ablation study of ADMIRE on brain network datasets. (AUC). 63Table 6.3 Accuracy (%) of generated tree explanation. This table showshow well ADMIRE++ mimics ADMIRE predictions. . . . . . 70Table A.1 Performance of the modified attention on general datasets (AUC). 97xiList of FiguresFigure 2.1 GNN Message passing from the perspective of node x0. First,each node passes a message to each of its neighbors. Aftersending messages, each node receives the messages from itsneighbors. Then each node aggregates its received messagesand updates its node encoding. . . . . . . . . . . . . . . . . . 9Figure 4.1 Framework and design of ANOMULY model. ANOMULY firstencodes nodes in each snapshot of the network and updatesthem with a GRU cell (embedding update module). Finally, totrain the model in an unsupervised manner, it uses a negativesampling approach that corrupts normal connections to generatenegative samples. . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 4.2 Stability over different training ratios on Ripple. . . . . . . . 30Figure 4.3 Event detection in Ethereum network. The top-4 local maxi-mums all coincide with major events annotated in the figure . 30Figure 4.4 Anomalous edges in the brain network of a sampled individual. 31Figure 4.5 Distribution of anomalous edges in ADHD group. . . . . . . . 32Figure 5.1 Schematic of the ADMIRE model. ADMIRE consists of fourmain stages called (1) Walk Sampling, (2) Anonymization, (3)Walk Encoding, and (4) Training via generating negative samples. 36xiiFigure 5.2 (Top) Motif clusters and example of an extracted motif in eachcluster. (Bottom) The ADMIRE++ tree explanation on theAmazon dataset (depth=4). Different colors in the motif ex-amples show the changes in views. Here, P j i are the featuresconstructed in Equation 5.20. . . . . . . . . . . . . . . . . . . 51Figure 5.3 3D visualization of clusters using t-SNE (k = 4). While clus-ters of walks in the Amazon dataset are simply distinguishable,clusters in DBLP and Ethereum datasets are hard to distinguish,which is the reason for the worse performance of ADMIRE++(see Table 5.4) on these two datasets. . . . . . . . . . . . . . 52Figure 6.1 The effect of hyperparameters on the performance (a-c), and λevolution (d). . . . . . . . . . . . . . . . . . . . . . . . . . . 65Figure 6.2 The advantage of multiplex brain networks over monoplex brainnetworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Figure 6.3 The distribution of anomalous edges in PD group. . . . . . . . 67Figure 6.4 The distribution of anomalous edges in ADHD group. . . . . 67Figure 6.5 The distribution of anomalous edges in ASD group. . . . . . . 68Figure 6.6 (Left) Motif clusters and example of an extracted motif ineach cluster. (Right) The ADMIRE++ tree explanation on PDdataset (depth=3). Different colors in the motif examples showthe changes in views. Here, P j i are the features constructed inEquation 5.20. . . . . . . . . . . . . . . . . . . . . . . . . . 69xiiiList of AbbreviationsABIDE Autism Brain Imaging Data ExchangeADHD Attention Deficit Hyperactivity DisorderANOMULY Anomaly Detection in Multiplex Dynamic NetworksANT Attention Network TestASD Autism Spectrum DisorderAUC Area Under the ROC CurveCNN Convolutional Neural NetworkDMRI Diffusion Magnetic Resonance ImagingFMRI Functional Magnetic Resonance ImagingGCN Graph Convolutional NetworksGELU Gaussian Error Linear UnitsGNN Graph Neural NetworksGRU Gated Recurrent UnitLDA Latent Dirichlet AllocationMLP Multilayer PerceptronNS Negative SamplingPD Parkinson’s DiseaseRNN Recurrent Neural NetworkROI Region of InterestxivSMRI Structural Magnetic Resonance ImagingTD Typically DevelopedxvAcknowledgmentsFirst of all, I would like to deeply thank my advisor Professor Margo Seltzer forguiding me throughout my M.Sc. study. I learned so much about research from herover the past three years, and I would like to deeply thank her for giving me theopportunity to be a member of the Systopia Lab and learn from her.I am also grateful to Professor Laks V.S. Lakshmanan, whose research inspiredme in many of my research projects. I am fortunate to have had the chance tocollaborate with and learn from him during my M.Sc. study.I would like to thank Professor Cynthia Rudin and Professor Mathias Lécuyer,who I have the chance to work with and learn from. I learned a lot from them whichalso inspired me for a part of this thesis.I would like to thank my parents and my sister for supporting me throughoutthis way. Despite being on the opposite side of the earth, I could still feel the loveand care of them.Finally, I would like to thank my collaborator, my projects partner, my bestfriend, and my love, Farnoosh, whose support, love, and care have been unwaveringthroughout this journey. Having her as a collaborator, friend, and partner, I feelfortunate to have the chance to share every moment of this journey with her.xviChapter 1Introduction1.1 MotivationIdentifying anomalous activities in networks is a long-standing and vital prob-lem with a wide variety of applications in different domains, e.g., finance, socialnetworks, security, and public health [2, 8, 9, 115, 141]. While several anomalydetection approaches focus on the topological properties of networks [63, 64, 110,133, 134, 157], detecting anomalies in real-world networks also requires attentionto their dynamic nature [141]. Anomalies might appear as malware in computersystems [77], social bots and social spammers in social networks [51], or finan-cial fraud in financial systems [7, 8]. Accordingly, anomaly detection in dynamic(evolving) complex systems has recently attracted much attention.Most prior work focuses on detecting anomalies in dynamic networks whoseedges are all of the same type [24, 32, 40, 65, 66, 141, 180, 188]; these networksare called single-layer, dynamic networks. However, in many complex dynamicsystems, such as social, transportation, and financial networks, there are manydifferent kinds of interactions between objects. For example, interactions betweenpeople can be social or professional, and professional interactions can differ ac-cording to topics. We model graphs with different kinds of edges as Multilayer orMultiplex networks [98], where nodes can interact in multiple views, each of whichis associated with a specific type of connection. In these networks, the differenttypes of connections are complementary to each other, providing more complex and1richer information than simple graphs. Surprisingly, anomaly detection in multiplexnetworks is relatively less explored and has only recently attracted attention.Existing approaches to anomaly detection in multiplex networks suffer fromthree main limitations: 1 Structure and feature inflexibility: existing methodsassume pre-defined anomaly patterns or man-made features. Such approaches areapplication dependent and do not easily generalize to different domains. Moreover,in real-world networks, anomalies might be more complex in nature, and it is nearlyimpossible to detect anomalies with high accuracy using pre-defined patterns/roles.2 Same importance for all types of connections: these methods treat each viewidentically, assigning the same importance to each view. However, real-world multi-plex networks can contain noisy/insignificant views [71, 79]. Moreover, all verticesmight not participate equally in all layers, so which layers are noisy/insignificantcan be different for each vertex [71, 79]. 3 Lack of edge anomaly detection: pre-vious methods for anomaly detection in multiplex networks focus on identifyinganomalous nodes, subgraphs, or events. However, in many real-world applications,a connection between two vertices might be an anomaly [24, 40, 180, 188]. Thisanomalous connection might be a suspicious transaction in a financial network, afake follower in a social network, or an abnormal functional correlation betweentwo regions of the brain.In addition to the limitations of existing anomaly detection methods in multiplexnetworks, existing methods for anomaly detection in single-layer dynamic graphsalso exhibit limitations. i Structure inflexibility: even in single-layer networks,most existing anomaly detection methods for dynamic networks rely on pre-definedpatterns or heuristic rules (see [142, 160]). These heuristic rules are usually contentfeatures or long-term temporal factors. However, these factors are not flexible andare restricted to specific patterns, while real-world anomalies have complex natureand a fixed description of an anomaly does not apply in all situations. ii Memoryusage: deep learning-based methods [180, 188], which are commonly proposed, re-quire storing entire snapshots of the network at each time window, consuming largeand increasing amounts of memory. iii Discrete timestamps: existing anomalydetection methods consider time as a discrete variable, while in many complexdynamic systems, interactions are continuous. Accordingly, modeling their con-nections’ timestamps as discrete variables misses temporal properties and patterns.2That is, these methods consider discrete approximations of dynamic systems, butthis discretization fails if we have irregularly observed data [96].To overcome the above limitations, we study the problem of anomaly detectionin multiplex, dynamic networks. Since multiplex networks provide richer and morecomplex information than simple networks, they also improve anomaly detection insimple dynamic graphs [9, 115, 141], delivering better solutions. Next, we discusstwo of anomaly detection that apply only to multiplex networks.Applications: Brain Networks. Monitoring functional systems in the human brainis a fundamental task in neuroscience [26, 139]. Each node in a brain networkrepresents a region of interest (ROI), which is responsible for a specific function,and edges represent an association between two ROIs. For example, one commonmode of analysis is to construct a brain network from functional magnetic resonanceimaging (FMRI), where edges represent high functional correlation between twoROIs. A temporal brain network lets us measure the statistical association betweenthe functionality of ROIs over time. Since a (dynamic) brain network generatedfrom an individual can be noisy and/or incomplete [6, 20, 101, 185], prior workused the average of brain networks from many individuals [1, 42]. However, thesemethods ignore the complex relationships in each individual’s brain. We can capturethese missing relationships by modeling the network as a multiplex (dynamic)network [59], where each view represents an individual’s brain network. An edgeanomaly detection approach in multiplex networks can be used to reveal abnormalbrain activity patterns that might cause or be indicative of a brain disease or disorder.In Chapter 6, we discuss this application in more detail.Applications: Fraud Detection in Multiple Blockchain Networks. Anomalydetection in (dynamic) blockchain transaction networks has recently attracted enor-mous attention [39, 62, 81, 116, 135, 137], due to the emergence of a huge assort-ment of financial systems’ applications [36, 76, 90]. While most existing workfocuses on detecting illicit activity in a single blockchain network, recent researchshows that cryptocurrency criminals increasingly use cross-cryptocurrency tradesto hide their identity [125, 127]. Accordingly, Yousaf et al. [175] recently showedthat analyzing links across several blockchain networks is critical for identifyingemerging criminal activity on the blockchain. An edge anomaly detection approach3in multiplex networks can be used to detect suspicious transactions and identifycriminal activity across several blockchain transaction networks more accurately.1.2 ContributionsThe contributions of this work are:1. We address the lack of edge anomaly detection in multiplex networks, byintroducing ANOMULY, an end-to-end unsupervised framework for detectingedge anomalies in dynamic multiplex networks. ANOMULY uses a novellayer-aware node embedding approach in multiplex dynamic networks, Snap-shot Encoder, which uses an attention mechanism to incorporate both tempo-ral and structural information on different relation types. Next, ANOMULYuses a GRU cell to incorporate the outputs of Snapshot Encoder for differentsnapshots, keeping node encodings updated over time. Finally, it uses anegative sampling approach in the training phase to overcome the lack ofground truth data (Chapter 4).2. While ANOMULY shows outstanding performance in experiments on ninereal-world multiplex and simple networks, it exhibits poor scalability, lackof generalizability to abnormal connections whose endpoints have not beenseen in the training, and imprecise temporal modeling using a discrete ap-proximation of network dynamics. To address these limitations, we presentADMIRE, an end-to-end inductive unsupervised learning method. ADMIREuses inter-view and intra-view temporal walks to implicitly extract networkmotifs and causal relationships across different views and within a view,respectively. Next, ADMIRE adopts a novel anonymization process basedon the correlation between multiplex network motifs to hide the identity ofnodes and views. Next, it uses an MLP-Mixer to encode the sequence ofnodes and views in a walk. By aggregating all the walks started from a node,ADMIRE encodes nodes’ neighborhoods. Encoded neighborhoods are fed toa classifier to detect anomalous connections (Chapter 5).3. Decision-making in sensitive domains (e.g., healthcare), requires models thatexplain the reason for each prediction to experts. To this end, we design4a post-hoc decision-tree-based explanation method to explain ADMIRE’spredictions based on its extracted motifs. ADMIRE++ first uses inter-viewand intra-view walks to extract network motifs around each node, and thenconstructs a feature vector that describes the neighborhood of each nodebased on the counting of extracted motifs. Finally, it trains an interpretableweighted optimal sparse decision tree model that gets these features as inputsand mimics ADMIRE predictions (Section 5.3).4. We demonstrate a new application of edge-anomaly detection in dynamicmultiplex networks and present several case studies on the brain networkof people living with Attention Deficit Hyperactivity Disorder, Parkinson’sDisease, and Autism Spectrum Disorder. The results show the potential ofADMIRE and ANOMULY in detecting abnormal brain activity that mightreveal a disease or disorder (Chapter 6).5. We further conduct extensive experiments on nine real-world multiplex andsimple networks to evaluate the performance of ANOMULY and ADMIREin different domains, varying from social, co-purchasing, co-authorship, andhuman mobility networks to financial networks. These experimental resultsare reported at the end of each chapter.5Chapter 2Preliminaries and backgroundWe first describe the terminology used in this thesis for describing multiplex dynamicnetworks and the problem of anomaly detection. Next, we discuss the preliminarybackground on graph neural networks, GRU cells, skip-connections, MLP-Mixer,optimal sparse decision trees, and brain networks.2.1 TerminologyThere are two types of representation for dynamic networks, so we begin by formallydescribing them.Definition 1 (Multiplex Temporal Networks). Let G = {Gr}Lr=1 = (V, E ,X )denotes a multiplex temporal network, where Gr = (V, Er,X ) is a graph of therelation type r ∈ L (also known as view), V is the set of nodes, E = ⋃Lr=1 Er is theset of edges such that each edge is associated with a timestamp τe and X ∈ R|V|×fis a matrix that encodes node attribute information for nodes in V . Here, f is thenumber of available features for each node.In temporal multiplex networks, we assume that each node and each edge isassociated with a timestamp, which shows the time that a node/edge first appears inthe network. In the literature, there are two ways to process temporal multiplex net-works based on whether time is a discrete or continuous variable. In Chapter 4, weconsider time as a discrete variable and take a snapshot-based anomaly detection ap-proach for multiplex dynamic networks: a multiplex dynamic graph G = {G(t)}Tt=16can be represented as a sequence of multiplex network snapshots, where eachsnapshot is a static multiplex graph G(t) = {G(t)r }Lr=1 = (V(t), E(t),X (t)) withV(t) = {v ∈ V|τv = t} and E(t) = {e ∈ E|τe = t}. Our goal is to detect anoma-lous edges in E(t). Note that, here, a snapshot of the network, G(t), represents thestate of a graph at time t.In Chapter 5, we consider time as a continuous variable and take a streaminganomaly detection approach for multiplex dynamic networks:Definition 2 (Stream Temporal Multiplex Networks). A temporal stream multiplexnetwork G = {Gr}Lr=1 = (V, E ,X ), can be represented as a sequence of connec-tions with different types that arrive over time, i.e., E = {(e1, t1), (e2, t2), . . . },where V is the set of nodes, L is the set of relation types (views), {e1, e2, . . . } ⊆V × V × L, and X ∈ R|V|×f is a matrix that encodes node attribute informationfor nodes in V .Given a relation type r, we use Gr = (V, Er,X ) to denote the correspondinggraph of the relation type r (also known as the r-th view of the graph), and wedenote the set of vertices in the neighborhood of u ∈ V in relation r as Nr(u).Given time t, we use E tr(u) = {(e, t′) ∈ Er|u ∈ e and t′ < t} to represent the set ofconnections attached to a node u in relation type r before a given time t.2.2 Graph Neural NetworksMessage-passing Graph Neural Networks (GNNs) are a class of neural networkmodels designed to operate on graph-structured data. The core idea behind message-passing GNNs is to iteratively update the node representations by aggregatingand exchanging information with neighboring nodes. This process allows nodesto gather and propagate information across the graph, capturing both local andglobal structural patterns. We can mathematically formulate the process of message-passing as follows:7h(0)v = xv ∀v ∈ V (2.1)m(k)v = AGGREGATE(k)({h(k−1)u : u ∈ N (v)})(2.2)h(k)v = COMBINE(k)(h(k−1)v ,m(k)v)(2.3)h(k)v = UPDATE(k)(h(k−1)v)(2.4)In the above equations, xv represents the input feature vector for node v inthe graph. h(k)v denotes the representation of node v at iteration k, and m(k)vrepresents the aggregated message from neighboring nodes of v at iteration k.The functions AGGREGATE(k)(.), COMBINE(k)(.), and UPDATE(k)(.) representthe aggregation, combination, and update functions used in the message-passingprocess, respectively. The specific choices of these functions can vary dependingon the design of the GNN model. Common aggregation functions include SUM(.),MEAN(.), or MAXPOOLING(.), while combination functions typically involveconcatenation or element-wise operations. The update function can be a simplefeed-forward neural network or a more complex recurrent or attention mechanism.By iteratively applying the message-passing equations, GNNs capture increas-ingly refined representations of the graph structure and learn node embeddings thatencode both local and global information. These learned node representations canthen be used for various downstream tasks, including anomaly detection.Figure 2.1 shows an example of message passing in a simple graph. Each nodepasses messages to its neighbors and when a node receives all messages from itsneighbors, aggregate them to update its own encoding.2.3 GRU CellThe Gated Recurrent Unit (GRU) is a type of recurrent neural network (RNN) thathas been widely used for modeling sequential data [48]. It is known for its ability tocapture long-term dependencies in the data while mitigating the vanishing gradientproblem that can occur in traditional RNNs [48]. The GRU cell consists of variousgates that control the flow of information within the network. These gates include8Figure 2.1: GNN Message passing from the perspective of node x0. First, eachnode passes a message to each of its neighbors. After sending messages,each node receives the messages from its neighbors. Then each nodeaggregates its received messages and updates its node encoding.an update gate, a reset gate, and an output gate. The update gate determines howmuch of the past information should be retained, the reset gate decides how much ofthe past information should be forgotten, and the output gate regulates the amountof information to be outputted. The mathematical formulation of the GRU cell canbe represented as follows:zt = σ (Wz · [ht−1, xt]) (2.5)rt = σ (Wr · [ht−1, xt]) (2.6)h˜t = tanh (Wh · [rt ⊙ ht−1, xt]) (2.7)ht = (1− zt)⊙ ht−1 + zt ⊙ h˜t. (2.8)In the above equations, xt represents the input at time step t, ht−1 is the hiddenstate of the previous time step, and ht is the updated hidden state at time step t.Wz,Wr and Wh are weight matrices specific to each gate. σ(.) denotes the sigmoidactivation function, ⊙ represents element-wise multiplication, and [a, b] denotesconcatenation of vectors a and b. The update gate zt controls how much of theprevious hidden state to retain and how much of the new information to incorporate.The reset gate rt determines how much of the previous hidden state should beforgotten. The input and previous hidden state are combined with the reset gate9to compute an intermediate hidden state h˜t. Finally, the new hidden state ht isobtained by combining the previous hidden state with the updated information fromh˜t based on the update gate zt. This formulation allows the GRU cell to selectivelyretain or forget information, making it well-suited for tasks involving sequentialdata, such as language modeling, machine translation, and speech recognition.2.4 Skip-connectionsA skip connection [104], also known as residual connection, is a technique com-monly used in deep machine learning methods to improve the flow of informationand alleviate the vanishing gradient problem [104]. They allow the network to retainand propagate important information from earlier layers to later layers.Mathematically, in GNNs, skip connections can be represented as follows [104]:h(k)v = AGGREGATE({h(k)u : u ∈ N (v)})+ h(k−1)v (2.9)h(k+1)v = COMBINE(h(k)v ,h(k+1)v)(2.10)In the above equations, h(k)v represents the hidden state of node v at layer k.The first equation combines the aggregated information from neighboring nodeswith the hidden state of the previous layer, allowing the current layer to have directaccess to both local and global information. The second equation combines the skipconnection output with the output of the current layer using a combining function.The skip connections enable GNNs to effectively handle deep architectures byfacilitating the flow of gradients during training. By retaining information fromearlier layers, the network can mitigate the vanishing gradient problem and improvethe learning of long-range dependencies. Furthermore, skip connections also helppreserve and propagate important features throughout the network.2.5 MLP-MixerMLP-Mixer, an all-Multilayer Perceptron (MLP) architecture, is a type of neuralnetwork architecture that has gained attention in the field of computer vision. It is10designed as an alternative approach to traditional convolutional neural networks(CNNs) and Transformers [153]. Each layer in the architecture of MLP-Mixer con-sists of two distinct sub-layers: a token-mixing layer and a channel-mixing layer.Channels refer to pixel values in an image. The token-mixing layer processes the spa-tial information within each channel independently, while the channel-mixing layerintegrates the information across different channels. This mixing of informationhelps capture both local and global dependencies within the image.The mathematical formulation of MLP-Mixer can be represented as follows:1 Token Mixer:Htoken = E+W(2)tokenσ(W(1)tokenLayerNorm (E)T)T, (2.11)1 Channel Mixer:Hchannel = Htoken +W(2)channelσ(W(1)channelLayerNorm (Htoken)), (2.12)In the above equations, E is the input matrix and σ(.) is a nonlinear activationfunction (usually Gaussian Error Linear Units (GELU) [84]). The main advantage ofMLP-Mixer is its simplicity as well as its ability to capture cross-feature and cross-sample dependencies. That is, the Token-Mixer phase captures the dependenciesbetween all samples across each feature, while the Channel-Mixer phase learns thedependencies of features in each sample. This combination produces promisingadvantages in various domains such as graph learning [22, 49], computer vision [151,177], and natural language processing [70].2.6 (Weighted) Optimal Sparse Decision TreesDecision trees are one of the most popular forms of interpretable models [144].While full decision tree optimization is NP-hard [102], it is possible to makeassumptions, e.g., feature independence, that simplifies the hard optimization tocases where greedy methods suffice [99]. However, these assumptions are unrealisticin practice, causing suboptimal performance in real-world scenarios. More recentlythere have been several approaches that fully optimize sparse trees to yield thebest combination of performance and interpretability [23, 68, 75, 126]. This work11leverages the fact that the loss takes on a discrete number of values to enable efficientcomputation [4, 5, 107, 120]. Although in real-world applications, samples mightdiffer in their importance, none of these methods handle weighted samples. Toaddress this limitation, Behrouz et al. [21] extend the decision tree optimizationproblem to include weighted samples.Let T be a decision tree that gives predictions {yˆTi }Ni=1. The weighted loss ofT is:Lw(T , x˜,y) = 1∑Ni=1wiN∑i=11[yi ̸= yˆTi ]× wi . (2.13)Building on the work of McTavish et al. [120], Behrouz et al. [21] providesthe option to use either soft sparsity regularization on the number of leaves, hardregularization on the tree depth, or both:minimizeTLw(T , x˜,y) + λHT s.t. depth(T ) ≤ d , (2.14)where HT is the number of leaves in T and λ is a per-leaf regularization parameter.Behrouz et al. [21] develop three algorithms to find the optimal weighted tree.The first approach directly optimizes the weighted loss function by the dynamicprogramming algorithm of Lin et al. [107], which requires using floating pointvector operations, rather than bit vector operations, leading to poor scalability. Thesecond approach scales better by transforming weights to integer values and usingdata duplication to transform the weighted decision tree optimization problem intoan unweighted problem with more data samples. The third algorithm, which scalesto much larger datasets, uses a randomized procedure that samples each data pointwith a probability proportional to its weight.2.7 Brain NetworksBrain networks refer to interconnected patterns of neural activity or structuralconnections within the human brain. These networks provide valuable insights intobrain organization, function, and information processing. They are often studiedusing neuroimaging techniques such as functional magnetic resonance imaging(FMRI) and structural magnetic resonance imaging (SMRI) [191].12Mathematically, brain networks can be represented as graphs, where the brainregions are nodes, and the connections or any other association between themare edges. To obtain brain networks from fMRI data, a common approach is toextract the time series of activity from different brain regions and then calculatethe correlation or coherence between the time series of different brain regions. Theresulting correlation matrix represents the functional connectivity network of thebrain. In the case of sMRI data, the goal is to map the structural connections betweendifferent brain regions, which can be done using diffusion MRI (DMRI) and thenestimating the white matter pathways connecting different brain regions [57]. Thestudy of brain networks has contributed to our understanding of brain function [14,20, 80, 152], cognitive processes [15, 145], and neurological disorders [42, 109].In Chapter 6, we provide more detail on how to obtain the brain network fromneuroimaging data.13Chapter 3Related WorkWe begin with a review of anomaly detection algorithms in dynamic simple net-works, then discuss methods for dynamic and multiplex graph learning, and finallypresent the state of the art in anomaly detection in multiplex networks. For additionalrelated work, we refer the reader to the extensive survey by Ma et al. [115].3.1 Anomaly Detection in Dynamic NetworksThere has been much work in anomaly detection for single-layer dynamic networks.That work falls in four categories: (1) Probabilistic methods [3, 24, 43, 83, 131,156, 178] that identify anomalies based on deviations from regular communicationpatterns. (2) Distance-based methods [65, 66, 142, 160, 172] that use certaintime-evolving measures of dynamic network structures and use their changes todetect anomalies. (3) Density-based methods [31, 85, 168] that view anomalies assubgraphs with high density or as subgraphs with sudden changes in their density.(4) Matrix factorization methods [117, 147, 148, 150, 179] that use the low-rankproperty of network structures and define anomalies as breakers of this property.All approaches in these four groups are based on pre-defined patterns/rules andcannot learn unforseen anomalous patterns, which limits their application. Learning-based methods that combine the graph embedding method into the anomaly de-tection approach [33, 87, 111, 180, 188, 189] address this shortcoming. Theselearning-based models assume the dynamic nature of these graphs is accurately14modeled as a sequence of graph snapshots. Here, each snapshot represents the stateof the graph at a specific timestamp. These methods must store the entire snapshot,which requires large memory, limiting their ability to scale to large graphs. Also, allthese methods apply to single-layer networks only and do not naturally extend tomultiplex networks. That is, these methods are not able to consider different typesof connections, missing the semantics of the interactions.3.2 Dynamic Graph Neural NetworksThe problem of learning from dynamic networks has been extensively studied in theliterature [22, 45, 72, 80, 105, 106, 128, 132, 149, 171]. The first group of existingmethods uses Recurrent Neural Networks (RNN) and then replaces the linear layerwith a graph convolution layer [106, 146, 187]. The second group uses a GraphNeural Network (GNN) as a feature encoder and then deploys a sequence modelon top of the GNN to encode temporal properties [132, 162, 176]. To address thescalability and model design issue of these methods, You et al. [174] presentedROLAND, a graph learning framework for dynamic graphs that can re-purpose anystatic GNN to dynamic graphs. Recently, more sophisticated learning methods fortemporal graphs have been designed based on temporal random walks [22, 88, 163],line graphs [41], GraphMixer [49], neighborhood representation [113], and subgraphsketching [37]. However, all these methods differ from ADMIRE and ANOMULYas they are designed for temporal graphs with only a single view and cannot easilybe extended to multiplex networks.The Snapshot Encoder in ANOMULY can be seen as the extension of ROLANDto multiplex networks. However, natural attempts to use multiplex graph neuralnetworks [16, 35, 47, 136, 169, 182] in the ROLAND framework (e.g., replacingthe GNN block with a multiplex GNN) ignore historical data in other views. Forexample, assume that we want to use ANOMULY’s attention mechanism (see Sec-tion 4.2.3) in the ROLAND framework. Then, we need to use the attention mecha-nism in the GNN block, which means we incorporate information about differentrelation types before the Embedding update module. Accordingly, for each times-tamp, we do not incorporate historical data on other relation types, which couldproduce undesirable performance. By introducing an attention mechanism that15incorporates relation-specific hierarchical node states in each snapshot after eachEmbedding update, ANOMULY takes advantage of both multiplex and temporalinformation.3.3 Multiplex Graph LearningIn a multiplex network, also known as multilayer, multi-view, or multi-dimensionalnetworks, all nodes have the same type, but edges (relations) have multiple types [98].Several methods have been proposed to learn network embeddings on multiplexnetworks by integrating information from individual relation types [35, 38, 136, 161,166, 169]. Other work proposed Graph Convolutional Networks (GCN) methodsfor multiplex networks [16, 47, 182]. Inspired by Deep Graph Infomax [155], Parket al. [130] and Jing et al. [89] proposed unsupervised approaches to learn nodeembeddings by maximizing the mutual information between local patches and theglobal representation of the entire graph. Zhang et al. [183] proposed a method thatuses a latent space to integrate the information across multiple views. Recently,Wang et al. [159] proposed DPMNE to learn from incomplete multiplex networks.Several methods have been proposed for learning on heterogeneous networks(networks with multiple vertex and edge types) [38, 166, 170]. Although multi-plex networks can be seen as a special case of heterogeneous networks (with asingle type of nodes), these learning methods on heterogeneous graphs emphasizeheterogeneous types of entities connected by different relationships, which is differ-ent from the concept of multiplex networks [130]. That is, these methods do nottake advantage of the complementary information provided by different types ofconnections among the same type of nodes, missing their complex interactions.Existing methods for multiplex networks differ from ADMIRE and ANOMULYas they ignore the temporal properties of the graph.3.4 Anomaly Detection in Multiplex NetworksThe problem of anomaly detection in multiplex networks has recently attractedattention. Mittal and Bhatia [122] use eigenvector centrality, page rank centrality,and degree centrality as handcrafted features for nodes to detect anomalies instatic multiplex networks. Bindu et al. [25] proposed a node anomaly detection16algorithm in static multiplex networks that uses handcrafted features based onclique/near-clique and star/near-star structures. Bansal and Sharma [12] defineda quality measure, Multi-Normality, which employs the structure and attributestogether of each layer to detect attribute coherence in neighborhoods between layers.Maulana and Atzmueller [119] use centrality of all nodes in each layer and applymany-objective optimization with full enumeration based on minimization to obtainPareto Front. Then, they use Pareto Front as a basis for finding suspected anomalynodes. Chen et al. [46] proposed ANOMMAN that uses an auto-encoder moduleand a GCN-based decoder to detect node anomalies in static multiplex networks.Although this model can learn from the data, it is limited to static networks, andit treats each layer equally in the Structure Reconstruction step. Finally, Ofori-Boateng et al. [127] developed a new persistence summary and used it to detectevents in dynamic multiplex blockchain networks.All of these approaches are designed to detect topological anomalous subgraphs,nodes, or events, and cannot identify anomalous edges. Moreover, as we discussedin Section 4.1, these methods, except ANOMAN [46], are based on pre-defined pat-terns/roles or handcrafted features, while real-world network anomalies have com-plex nature and have varied and unknown patterns that preclude pre-identification.Therefore, these models cannot be generalized to different domains, limiting theirapplication.17Chapter 4ANOMULY: Edge AnomalyDetection Framework inMultiplex Dynamic NetworksWe present ANOMULY, an unsupervised generic graph neural network-based frame-work for anomaly detection in multiplex dynamic networks. ANOMULYlearnsthe low-dimensional representation of vertices in graphs by taking advantage ofhistorical data and complementary information provided by different views of thenetwork. Then, we use the vertex encodings to classify future connections as normalor abnormal.4.1 IntroductionAs discussed in Chapter 1, existing approaches to anomaly detection in multiplexnetworks suffer from three main limitations: 1 Structure and feature inflexibility 2Same importance for all types of connections. 3 Lack of edge anomaly detection.We introduce ANOMULY (Anomaly Detection in Multiplex Dynamic Networks),which mitigates all of these limitations. ANOMULY extends the idea of hierarchicalnode states [174] to multiplex dynamic networks by using an attention mechanismthat incorporates information about different relation types to take advantage of bothtemporal properties and complementary information present in multiple relation18types. Next, it uses selective negative sampling to learn anomalous edges in anunsupervised manner. To the best of our knowledge, ANOMULY is the first edge-anomaly detection method for multiplex networks. Further, when it is possible tomodel a simple network as a multiplex network, ANOMULY outperforms existingsimple network approaches, because the multiplex network provides richer andmore complex information than does a simple network [9, 115, 141].4.2 ANOMULY: Anomaly Detection in Multiplex DynamicNetworksANOMULY is a snapshot-based anomaly detection approach for multiplex dynamicnetworks. Accordingly, we model the multiplex dynamic network as a sequence ofmultiplex network snapshots as we described in Chapter 2: a multiplex dynamicgraph G = {G(t)}Tt=1 can be represented as a sequence of multiplex networksnapshots, where each snapshot is a static multiplex graph G(t) = {G(t)r }Lr=1 =(V(t), E(t),X (t)) with V(t) = {v ∈ V|τv = t} and E(t) = {e ∈ E|τe = t}. Our goalis to detect anomalous edges in E(t). Specifically, for each edge e = (u, v, r) ∈ E(t),we produce a view-dependent anomalous probability φr(e) in view r ∈ L.Figure 4.1 provides an overview of our framework for edge anomaly detectionin dynamic networks with multiple types of interactions. To learn the pattern ofnormal edges, ANOMULY uses the Snapshot Encoder architecture to encode eachsnapshot of the network. The Snapshot Encoder is a GNN that takes as input asnapshot of the graph and produces, for each view of the graph, an embedding foreach vertex. It incorporates both structural and temporal properties of each snapshot,as well as node features in each view. Next, it uses an attention mechanism totake advantage of complementary information from different views. The attentionmechanism is a module that learns the importance of each view for each node andthen uses these weights in a weighted sum to obtain the node encodings. Sincethe graph is dynamically changing, the node embeddings can change over time, soSnapshot Encoder uses a GRU cell [48] (see Chapter 2 for more explanation aboutGRU cells) to update the node states over time. Finally, we use the hierarchical nodestates at each timestamp to calculate the view-dependent anomalous probabilities ofan existing edge and a negative sampled edge and use them as inputs to a margin19GNN Layer1GNN Layer1GNN Layer1Attention Embeddingupdate EmbeddingupdateEmbeddingupdateGNN Layer2GNN Layer2GNN Layer2Attention Embeddingupdate EmbeddingupdateEmbeddingupdateABC DF GHIJKABC DEF GIJKBDEF GHIJK Snapshot(a) Architecture of the Snapshot Encoder SnapshotEncoder SnapshotEncoder Score Function Margin Loss (b) ANOMULY FrameworkFigure 4.1: Framework and design of ANOMULY model. ANOMULY firstencodes nodes in each snapshot of the network and updates them with aGRU cell (embedding update module). Finally, to train the model in anunsupervised manner, it uses a negative sampling approach that corruptsnormal connections to generate negative samples.20loss computation. Next, we explain each part in more detail.4.2.1 GNN ArchitectureA GNN iteratively aggregates messages from the local neighborhood of nodes tolearn node embeddings. For a given type of relation r, we use the embedding matrixH˜(ℓ)r = {h˜(ℓ)ru }u∈V to denote the embedding of all vertices in relation type r afterapplying the ℓ-th GNN layer. Given a relation type r, the ℓ-th layer of the GNN,H˜(ℓ)r = GNNr(H˜(ℓ−1)r ), is defined as:mℓr(v→u) =W(ℓ)r CONCAT(h˜(ℓ−1)rv , h˜(ℓ−1)ru , τ(v,u,r)),h˜(l)ru = AGG(ℓ)({mℓr(v→u) |v ∈ Nr(u)})+ h˜(ℓ−1)ru .(4.1)In our experiments, we follow You et al. [174], and use summation as the aggre-gation function, i.e., AGG(.) = SUM(.). We also use skip-connections [104] (seeChapter 2) after aggregation.4.2.2 Update ModulesGiven the snapshot G(t) = (V(t), E(t),X (t)) at time t and a relation type r, wedenote the embedding matrix in relation r after the ℓ-th GNN layer at time t byH˜(t)(ℓ)r = {h˜(t)(ℓ)ru }u∈V . To take advantage of historical data and update the nodeembeddings at each timestamp, in the Embedding update block (see Figure 4.1),we use a GRU cell [48]. Given a relation type r, the output of the ℓ-th Embeddingupdate, Hˆ(t)(ℓ)r = {hˆ(t)(ℓ)ru }u∈V , is:Hˆ(t)(ℓ)r = GRUr(H˜(t)(ℓ)r , H(t−1)(ℓ)r), (4.2)where H˜(t)(ℓ)r is the output of the ℓ-th GNN layer, and H(t−1)(ℓ)r is the view-dependent embedding matrix at time t− 1. The view-dependent embedding matrix,H(t)(ℓ)r , is defined later in this section (see Equation 4.5).214.2.3 Attention MechanismThe role of our attention mechanism is to incorporate information from differentrelation types in a weighted manner. As discussed in Chapter 1, the importance of aview can differ for different nodes, so we cannot calculate a single weight for eachview. Accordingly, we introduce an attention mechanism that learns the importanceof view r for an arbitrary node u ∈ V . Let ζ(t)(ℓ)u be the aggregated hidden featureof node u ∈ V after the ℓ-th attention layer at time t, we call it a network-levelembedding, and α(ℓ)ru indicates the importance of relation type r for vertex u, then:ζ(t)(ℓ)u =L∑r=1α(ℓ)ru hˆ(t)(ℓ)ru , (4.3)where hˆ(t)(ℓ)ru is the output of ℓ-th Embedding update for node u at time t. Followingthe recent attention-based models [11, 130], we use the Softmax(.) function todefine the importance weight of relation type r for node u:α(ℓ)ru =exp(σ(s(t)(ℓ)rTWattr hˆ(t)(ℓ)ru))∑Lk=1 exp(σ(s(t)(ℓ)kTWattk hˆ(t)(ℓ)k)) , (4.4)where s(t)(ℓ)r is a summary of the network in relation type r at time t, i.e., s(t)(ℓ)r =∑u∈V hˆ(t)(ℓ)ru , and Wattr is a trainable weight matrix. In our experiments, we usetanh(.) as the activation function σ(.). The main intuition behind this attentionmechanism is that the numerator of Equation 4.4 captures how much a specific nodeencoding (e.g., hˆ(t)(ℓ)ru ) contributes to the encoding of a view (e.g., s(t)(ℓ)r ). That is,it uses the inner product of these two vectors followed by a multiplication by alearnable matrix Wattr which captures the weighted similarity of these two vectors.4.2.4 view-dependent EmbeddingThe output of the attention mechanism is a network-level node embedding matrix,which summarizes the properties of nodes over all relation types. Given a relationtype r, to obtain the view-dependent node embedding of a vertex u ∈ V , we22aggregate the output of the Embedding update block, i.e. hˆ(t)(ℓ)ru , and this network-level node embedding, i.e. ζ(t)(ℓ)u . That is:h(t)(ℓ)ru = AGG(ℓ)(hˆ(t)(ℓ)ru , ζ(t)(ℓ)u). (4.5)Based on Equation 4.5, we obtain the view-dependent node embedding matrix,H(t)(ℓ)r = {h(t)(ℓ)ru }u∈V , for any relation type r. Note that we use the view-dependentnode embedding matrix at time t − 1, H(t−1)(ℓ)r , in Equation 4.2 to update nodeembeddings after the ℓ-layer GNN.4.2.5 Anomaly Score ComputationNow, we get the view-dependent node embedding matrix H(t)r = H(t)(L)r at time t,for each relation type r. Here L is the number of GNN layers. Inspired by Zhenget al. [188], for an edge (u, v) ∈ Er, we define its anomaly score as follows:φ(t)r (u, v) = σ(η.(||a⊙ h(t)ru + b⊙ h(t)rv ||22 − µ)), (4.6)where σ(.) is an activation function, a and b are trainable vectors, and η and µ arehyperparameters.4.2.6 Training and Loss FunctionIn the training phase, we use a negative sampling approach to corrupt edges and gen-erate anomalous connections. Inspired by the negative sampling methods proposedby Wang et al. [164] and Zheng et al. [188], given a relation type r, and a normaledge (u, v) ∈ Er, we use a Bernoulli distribution such that we replace u (resp. v)with probability degr(u)degr(u)+degr(v) (resp.degr(v)degr(u)+degr(v)) in relation type r to generaterandom negative samples. The main intuition is: changing one endpoint of an edgemight result in another valid connection, and to avoid this, we prefer to replace anendpoint with a larger degree and keep the endpoint with a smaller degree. Sincethe corrupted edges might be normal, a strict loss function (e.g., cross-entropy) canaffect the performance. Accordingly, we use the margin-based pairwise loss [28]in each relation type r. Given a relation type r, we also use a L2-regularizationloss,L regr , which is the summation of the L2 norm of all trainable parameters, to23Algorithm 1 ANOMULY Training AlgorithmInput: A multiplex dynamic network G = {G(t)}Tt=1Output: Node embeddings for all relation types {H(T )r }Lr=11: Initialize{{H(0)(ℓ)r}Lℓ=1}Lr=1with features or one-hot encoding;2: while not converged do3: for t = 1, . . . , T do4: for r = 1, . . . ,L do5: LetL (t)r = 0;6: for ℓ = 1, . . . , L do7: H˜(t)(ℓ)r = GNNr(H(ℓ−1)r);8: Hˆ(t)(ℓ)r = GRUr(H˜(t)(ℓ)r , H(t−1)(ℓ)r);9: Z(t)(ℓ)r = {ζ(t)(ℓ)u }u∈V ={∑Lr=1 α(ℓ)ru hˆ(t)(ℓ)ru}u∈V;10: H(t)(ℓ)r = AGG(ℓ)(Hˆ(t)(ℓ)r , Z(t)(ℓ)r)11: for (u, v) ∈ E(t)r do12: Sample (u′, v′) for φ(t)r (u, v);13: L(t)r = L(t)r +max{0, γ + φ(t)r (u, v)− φ(t)r (u′, v′)};14: L(t)r = L(t)r + λLregr ;15: L (t) = 1L(∑Lr=1L(t)r);16: MinimizeL (t);return {H(T )r }Lr=1avoid overfitting. Finally, to aggregate the loss function over all relation types in themultiplex networks, we use the average of loss functions, i.e.:L =1|L| L∑r=1∑(u,v)∈Er∑(u′,v′ )̸∈Ermax{0, γ + φr(u, v)− φr(u′, v′)}+ λL regr .(4.7)Here, 0 ≤ γ ≤ 1 is the margin between normal and corrupted edges.ANOMULY’s training algorithm appears in detail in Algorithm 1.244.3 Experiments4.3.1 Experimental Setup and MetricsThe Snapshot Encoder uses a GNN with 200 hidden dimensions for node states, lay-ers with skip-connection, sum aggregation, and batch-normalization. We tune hyper-parameters by cross-validation on a rolling basis and search the hyper-parametersover (i) the numbers of GNN layers (1 to 5); (ii) the learning rate (0.001 to 0.01);and (iii) the margin γ (in increments of 0.05 in the range 0.3 to 0.7). The values ofother hyper-parameters are reported in Table 4.1. The hidden dimension of GNN isfine-tuned by searching in {32, 64, 100, 200, 320}.Table 4.1: The value of hyper-parameters of ANOMULY. Here, η and µ con-trol how close the encodings of two nodes should be so their connection isnormal. Also, λ controls the tradeoff between the margin-based pairwiseloss function and the regularization term.DatasetMultiplex Networks Single-layer NetworksDKPol RM Amazon DBLP Ethereum Ripple Bitcoin Amazon-S DBLP-Sη 1 1 1 3 1 1 1 1 3µ 0.3 0.25 0.5 0.5 0.3 0.3 0.3 0.5 0.5λ 5× 10−7 5× 10−7 5× 10−7 5× 10−7 5× 10−7 5× 10−7 5× 10−7 5× 10−7 5× 10−7We implement ANOMULY with the GraphGym library [173] and use anNVIDIA V100 GPU in the experiments. We use the AUC (the area under theROC curve) as the metric of comparison. The higher the AUC value, the higher thequality of the method.4.3.2 DatasetsWe use nine real-world public datasets [20, 78, 82, 97, 100, 127] whose domainscover social, brain, co-authorship, blockchain, and co-purchasing networks. Wesummarize their statistics in Table 4.2.Social Networks. RM [97] has 10 networks, each with 91 nodes. Nodes representphones and an edge exists if two phones detect each other in a mobile network.Each network describes connections between phones in a month. DKPol [78] is25Table 4.2: Network Statistics. Here |V| is the number of nodes, |E| is thenumber of edges in all views, and |L| is the number of views.DatasetMultiplex Networks Single-layer NetworksRM DKPol Amazon Ethereum Ripple DBLP Bitcoin Amazon-S DBLP-S|V| 91 490 17.5K 221K 54K 513K 3.7K 8.6K 23K|E| 14K 20K 282K 473K 837K 1M 24.1K 90K 95.2K|L| 10 3 2 6 5 10 1 1 1Twitter dataset collected during the month leading up to the 2015 Danish parliamen-tary election. Nodes are Twitter accounts of Danish politicians, and relations are"Retweet", "Reply", and "Topical Interaction" [78].Co-purchasing Network. Amazon [82] is a co-purchasing network, where eachnode is an item and the type of connections are "Also-view" and "Also-bought". Wefocused on items with four categories, i.e., Beauty, Automotive, Patio Lawn andGarden, and Baby.Co-authorship Network. DBLP is a co-authorship network until 2014 from dblpteam [58] and pre-processed by Behrouz et al. [20]. In this dataset, each node isa researcher, an edge shows co-authorship, and each type of connection is a topicof research. For each collaboration, we consider the bag of words drawn from thetitles of the paper and apply Latent Dirichlet Allocation (LDA) topic modeling [27]to automatically identify 240 topics. We then cluster their non-zero elements intoten known research topics. Each view in the network represents connections in oneof the ten topics.Blockchain Networks. Ethereum [127] is a blockchain transaction network over576 days, where views are different tokens, nodes are addresses of investors, andedges denote the transferred token values. Since the same address may trade multipletokens, the address appears in networks of all the tokens it has traded. Ripple [127]is derived from the Ripple Credit Network and covers a timeline of Oct-2016 toMar-2020. Similar to the Ethereum dataset, nodes are investors and edges representtransactions. Here views (relation types) correspond to the five most issued fiatcurrencies on the Ripple network: JPY, USD, EUR, CCK, and CNY.26Single-layer Networks. DBLP-S is a subgraph of the multiplex DBLP network,where we collect a subset of researchers who work on data mining and related areas.Amozon-S, is a subgraph of the multiplex Amazon network, where we focus on the"Also-view" relation type. The Bitcoin dataset contains who-trusts-whom networkof people who trade on the Alpha platforms [100].Note that all of the datasets are anonymized and do not contain any personallyidentifiable information or offensive content.4.3.3 Inject Anomalous Edges in Multiplex NetworksSince the ground truth for anomaly detection is difficult to obtain [9], we followthe methodology used in existing studies[9, 180, 188] and inject anomalous edgesinto our datasets. However, existing methods inject anomalous edges only insingle-layer networks and cannot add complex anomalies in multiplex networks.Accordingly, here we divide injected edges into two groups (50% each), (1) view-independent anomalies, and (2) view-dependent anomalies. For the first group,we use existing methods [9], which randomly change one of the endpoints ofsome existing connections. In multiplex networks, the rich information about nodeconnections leads to repetitions, meaning edges between the same pair of nodesrepeatedly appear in multiple views. Repeated connections are more likely torepresent a strong tie and may even suggest that the nodes in comprising theseconnections belong to the same community [20, 181]. Accordingly, in the secondtype of injected anomalies, we inject random connections that do not appear in anyrelation type. That is, we first choose a random edge (u, v) such that (u, v) ̸∈ Ekfor all k ∈ L, and then we inject this edge to a random relation type r ∈ L. Sincethis connection does not appear in any relation type, it is more likely to be ananomaly. This type of anomaly helps us to understand whether ANOMULY cantake advantage of complementary information of different relation types.4.3.4 BaselinesSince there is no prior work on edge anomaly detection in multiplex networks,we first compare ANOMULY with single-layer edge anomaly detection methods:GOutlier [3] builds a generative model for edges in a node cluster. CM-Sketch [142]27Table 4.3: Performance comparison of ANOMULY and baselines in multiplexnetworks (AUC).Methods RM DKPol Amazon DBLP Ethereum RippleAnomaly % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 %Single-layer MethodsGOUTLIER 0.7138 0.6982 0.6844 0.6597 0.6973 0.6672 0.7059 0.6901 0.7017 0.6799 0.7036 0.6851CM-SKETCH 0.7127 0.7012 0.7058 0.6930 0.6881 0.6719 0.7186 0.6915 0.7408 0.7277 0.7360 0.7194NETWALK 0.7739 0.7641 0.7706 0.7581 0.7228 0.7122 0.7742 0.7523 0.7956 0.7885 0.7904 0.7823ADDGRAPH 0.8005 0.8093 0.8149 0.8087 0.7796 0.7735 0.8024 0.7995 0.8133 0.8090 0.8205 0.8217Multiplex MethodsMNE 0.7994 0.7955 0.8050 0.7913 0.7108 0.7017 0.7532 0.7499 0.7541 0.7495 0.7813 0.7754ML-GCN 0.7921 0.7886 0.7915 0.7907 0.7344 0.7263 0.7519 0.7439 0.7940 0.7918 0.8115 0.8072ANOMULY 0.8783 0.8729 0.8694 0.8610 0.8289 0.8195 0.8825 0.8754 0.8906 0.8852 0.8938 0.8871Improvement 9.71% 7.85% 6.68% 6.46% 6.32% 5.92% 9.98% 9.49% 9.50% 9.41% 8.93% 7.96%uses a Count-Min sketch for approximating global and local structural properties.NetWalk [180] uses a random walk to learn a unified embedding for each node andthen dynamically clusters the nodes’ embeddings. AddGraph [188] is an end-to-endapproach that uses an extended GCN in temporal networks. Finally, we comparewith two multiplex network embedding baselines, ML-GCN [16] and MNE [183].We apply K-means clustering on their obtained node embeddings for anomalydetection [180].4.3.5 ResultsResults on Multiplex Networks. We compare ANOMULY with the baseline meth-ods on both dynamic and static multiplex networks with different percentages ofanomalous edges (i.e., 1%, 5%). Table 4.3 reports the AUC for both the base-lines and ANOMULY. Our method outperforms all baselines in all datasets andimproves the best baseline results by 8.18% on average. There are three reasonsfor ANOMULY’s superior performance: (1) it outperforms competitors for staticdatasets, because it can learn structural anomaly patterns in the network, rather thandepending on pre-defined patterns/roles. (2) ANOMULY outperforms single-layermethods due to its attention mechanism that incorporates complementary informa-tion from different relation types. (3) ANOMULY outperforms multiplex methodsas it is an end-to-end method and is optimized for anomaly detection. It is also a28Table 4.4: Performance comparison of ANOMULY and baselines in single-layer networks (AUC).Methods Bitcoin Amazon-S DBLP-SAnomaly % 1% 5 % 1% 5 % 1% 5 %GOUTLIER 0.7143 0.7091 0.6923 0.6614 0.7108 0.6995CM-SKETCH 0.7146 0.7015 0.7049 0.6621 0.7084 0.6877NETWALK 0.8375 0.8367 0.7483 0.7302 0.7779 0.7590ADDGRAPH 0.8534 0.8416 0.7872 0.7828 0.7911 0.7932ANOMULY 0.8707 0.8661 0.8014 0.7943 0.8129 0.8236Improvement 2.03% 2.91% 1.80% 1.47% 2.76% 3.83%Table 4.5: Ablation study on ANOMULY (AUC). The first row replaces theGRU with an MLP. The second row removes the attention mechanism,and the third row replaces the attention mechanism with SUM(.).Methods Amazon DBLP EthereumANOMULY 0.8289 0.8825 0.8906w/ MLP 0.8023 0.8606 0.8718w/o Attention 0.7831 0.8219 0.8275w/ Summation 0.8007 0.8571 0.8688dynamic method and can take advantage of the temporal properties of the network.The ablation study below illustrates these effects in more detail.Results on Single-layer Dynamic Networks. We also compare ANOMULY withsingle-layer method baselines on single-layer dynamic datasets. Table 4.4 summa-rizes the results. Once again, we see that ANOMULY outperforms all the baselines,even in single-layer graphs, by 2.46% on average. This is mainly due to SnapshotEncoder’s architecture, which enables our method to incorporate the outputs ofGNN layers after each view and recurrently update them over time using a GRUcell.Parameter Sensitivity. We evaluate the effect of the training ratio of the dataset:2960% 50% 40% 30% 20%Training Ratio0.80.91.0AUCFigure 4.2: Stability over different training ratios on Ripple.Dec '17 Jan '18 Feb '18 March '18 Apr '18 May '18 0.40.50.60.70.80.91Average Anomaly ScoreBitcoin reaches a new all-time high price of $19,783.06South Korea bans anonymous trading of cryptocurrenciesVisa and Mastercard re-classify cryptocurrencies purchases Twitter announces a ban on cryptocurrencies advertisingsFigure 4.3: Event detection in Ethereum network. The top-4 local maximumsall coincide with major events annotated in the figurewe change the training ratio from 60% to 20% and report the results on the Rippledataset in Figure 4.2. Decreasing the training ratio tends to increase both the averageand maximum AUC, except for the 20% case, and decreases the minimum AUCfor all training ratios. These results show that performance stays relatively stable,which demonstrates that our framework is robust in the presence of a small amountof training data.Ablation Study. Next, we conduct experiments to show that the ANOMULYarchitecture design is effective in boosting performance. We examine the effect ofGRU cells by replacing them with a 2-layer MLP. We also investigate the effect ofthe attention mechanism by (1) removing the attention, learning node embeddingsin each relation-type separately, and (2) aggregating the information of differentrelation types by summation (without weights). Table 4.5 summarizes the results.We found that both our attention mechanism and the GRU cells are important for30Figure 4.4: Anomalous edges in the brain network of a sampled individual.ANOMULY, producing significant performance boosts.Effectiveness in Detecting Events. Next, we evaluate how well ANOMULY detectsevents in the Ethereum transaction network. In each timestamp, we calculate theanomaly score for all the edges in the snapshot. We then compute the average of thetop-15 edge anomaly scores and report them in Figure 4.3. We find that the top-4local maximums all coincide with major events annotated in the figure.Case Study of Brain Networks. Behavioral disturbances in Attention DeficitHyperactivity Disorder (ADHD) are thought to be caused by the dysfunction ofspatially distributed, interconnected neural systems [74]. We used ANOMULY todetect anomalous connections in the brain network of people with ADHD. Weuse the ADHD-Brain dataset [30] derived from the functional magnetic resonanceimaging (fMRI) of 40 individuals–20 individuals in the condition group, labeledADHD, and 20 individuals in the control group, labeled Typically Developed(TD)–using the same methodology used by Lanciano et al. [101]. Here, each view(relation type) is the brain network of an individual person, where nodes are brainregions, and each edge measures the statistical association between the functionalityof its endpoints.Anomalous functional correlations between the brain network of people with31ADHD compared to those without can help us understand which brain regions areinvolved in ADHD. We present two results: (1) 74% of all detected anomaliesare connections in the brain networks of people in the ADHD group. (2) 69% ofall found anomalies in the ADHD group correspond to edges in the frontal andoccipital cortex of the brain. Figure 4.4 illustrates the anomalous edges in the brainnetwork of an individual in the ADHD group. These findings show an unexpectedfunctional correlation of occipital and frontal lobes regions with other parts, whichare consistent with previous studies on ADHD [42, 158].(a) Left View (b) Right View(c) Up ViewFigure 4.5: Distribution of anomalous edges in ADHD group.Next, we investigate how anomalous edges found by ANOMULY are distributedin the brain. Figure 4.5 reports the average distribution of anomalous edges inthe brain networks of people living with ADHD. Most anomalous edges found byANOMULY have a vertex in the Occipital lobes. Moreover, the Temporal lobes arethe brain regions with the most anomalous connections with the Occipital lobes.These findings can help to reveal new insights into understanding ADHD and theregions of the brain that are connected to its symptoms. These findings also showthe potential of ANOMULY to extract features that can help predict brain diseases32or disorders.In Chapter 6, we further discuss the application of anomaly detection in under-standing the abnormal brain activities that might cause a brain disease or disorder.4.4 ConclusionWe present ANOMULY, an end-to-end unsupervised framework for detecting edgeanomalies in dynamic multiplex networks. ANOMULY is based on a new architec-ture that uses GNN and GRU cells to take advantage of both temporal and structuralproperties and adds an attention mechanism that effectively incorporates informationacross different types of connections. Finally, it uses a negative sampling approachin training to overcome the lack of ground truth data. Extensive experiments showthe power of ANOMULY to effectively identify temporal and structural anomaliesin both single-layer and multiplex networks. Our case studies on brain networksand blockchain transaction networks show the usefulness of ANOMULY in widelyvarying domains.33Chapter 5ADMIRE: Inductive and ScalableAnomaly Detection in MultiplexDynamic Networks5.1 IntroductionWhile ANOMULY achieves state-of-the-art performance in all datasets, it suffersfrom several limitations: 1 Transductive learning: The ANOMULY framework isdesigned in a transductive setting and cannot be applied to unseen nodes/patterns.That is, ANOMULY in the message-passing procedure uses the identity of nodesin training, limiting its ability to predict anomalous connections between nodesthat are unseen in the training phase. 2 Memory and scalability: The ANOMULYframework is snapshot-based. That is, it requires storing the entire snapshot ofthe temporal network at each timestamp, which consumes a great deal of memory.Moreover, since it uses different GNN modules for each type of connection, itcannot be used for multiplex networks with a large number of views. 3 Lackof generalizability: The ANOMULY framework uses a simple negative samplingmethod by randomly changing one endpoint of a connection to learn anomalousinteractions. While this negative sampling method is fast and lets the model betrained in an unsupervised manner, these negative sample generator methods are34too simple and can cause poor performance in more complicated datasets [138].We now present ADMIRE, an inductive, scalable, unsupervised method thatlearns the underlying dynamic laws of the multiplex dynamic networks to detectanomalous patterns, thus addressing the limitation of ANOMULY. ADMIRE usestwo different casual multiplex walks, inter-view and intra-view, to automaticallyextract and learn temporal network motifs. It then uses an anonymization strategyto hide node and relation type identities, making the model inductive. ADMIRE is astreaming method, requiring only constant memory (see Section 5.2.1). Moreover,its random walk encoder scales to multiplex networks with more than 100 views.ADMIRE introduces a novel negative sampling method for multiplex networks thataddresses the generalizability issue in ANOMULY.5.2 ADMIREThe main intuition behind ADMIRE is to use multiplex temporal walks as a proxyfor temporal motifs in multiplex networks and extract the causality of the existenceof an edge in a specific type of connection. After extracting temporal multiplexmotifs, we use an anonymization process to hide nodes’ identities in walks, keepingthe model inductive in the training phase. Next, we design a simple yet effectivewalk encoding method to encode each walk. Using encoded walks, we define thenode encoding of a vertex u as the aggregation of all walks started from u. Usingthe obtained node encoding, we classify connections based on the encoding of theirendpoints.5.2.1 Anonymous Multiplex Temporal WalkWe define the multiplex temporal walk as a walk that starts from a connectionof interest and backtracks over time by traversing adjacent edges. By traversingadjacent edges in reverse time sequence, this allow us to discover and encode theunderlying causality of network dynamics. The main challenge in extracting thecausality of an edge in multiplex networks is determining whether there is a causalrelationship between different views. In multiplex networks, different views providecomplementary information about the network and each vertex. However, this doesnot always mean that there is a causal relationship between different views. For35View 1ViewIntra-view walksInter-view walksView EncodingNode EncodingTime EncodingTraining via negative samples...Views hidden IDsAnonymizationWalk Sampling Walk Encoding via MLP-MixerNodes hidden IDs...Figure 5.1: Schematic of the ADMIRE model. ADMIRE consists of fourmain stages called (1) Walk Sampling, (2) Anonymization, (3) WalkEncoding, and (4) Training via generating negative samples.example, consider the flight transportation network [34], where each node showsa city, and each view shows flights operated by a specific airline. Two cities inview r are connected if there is a flight between them operated by airline r. Inthis example, there is no causal relationship between different views, as flights indifferent views are operated by different airlines. To address this challenge, wedesign two multiplex temporal walks, intra-view, and inter-view walks, to extractthe causality within a specific view and across different views, respectively. Whenthere is no causal relationship between different views, we expect the model toignore inter-view walks.Intra-view Temporal Walk. An intra-view walk is a time-ordered random walkamong edges of a specific type (i.e., within a single view). Given a type of relationr, an intra-view temporal walk W rintra on a view of a temporal multiplex networkcan be represented as:W rintra = ((u0, r, t0), (u1, r, t1), . . . , (um, r, tm)) ; t0 ≥ t1 ≥ · · · ≥ tm, (5.1)where (ui, ui+1, r, t+ 1) ∈ E . Note that we only allow walks that progress back-ward in time, to limit ourselves to possible sources of causality. Since differentviews still provide complementary information about the global property of thenetwork as well as the local structure around each node, in Section 5.2.2, we usean attention mechanism that incorporates the information provided by intra-view36walks in different types of connections.Inter-view Temporal Walk. To capture the correlation between different viewsand extract the causality of an edge from different views of the network, in theinter-view temporal walk, we let the walker walk across views. Accordingly, aninter-view temporal walk Winter on temporal multiplex networks can be representedas:Winter = ((u0, r0, t0), (u1, r1, t1), . . . , (um, rm, tm)) ; t0 ≥ t1 ≥ · · · ≥ tm, (5.2)where (ui, ui+1, ri+1, t+ 1) ∈ E . That is, not only does the walker walk over timeand capture the temporal causality of an edge, but also can walk over different viewsto capture the dependencies of connections in different views, taking advantage ofcomplementary information provided by different types of relations. Note that risare not necessarily distinct. We let Winter(i) denote the i-th element of the temporalmultiplex walk, (ui, ri, ti). Also, we use Winter(i, 0),Winter(i, 1), and Winter(i, 2) torefer to ui, ri, and ti, respectively.How to sample temporal multiplex walk? As discussed in previous studies,newer connections in temporal networks are often more informative [88, 163]. Tothis end, we use a biased sampling method with hyperparameter µ to control theimportance of recent connections. Given the time of a previously sampled edge,t0, we sample an adjacent edge at time t < t0 with probability proportional toexp (µ(t− t0)). In multiplex networks, the correlation of different pairs of viewscan be different [17, 130] and for connections in a given view r, a subset of viewsmight play more important roles in causality extraction. Accordingly, in inter-viewtemporal walks, we use a biased sampling method and sample link (u′1, u′2, r′, t′)after previously sampled link (u1, u2, r, t) with probability proportional to φ(r, r′).In fact, φ(r, r′) shows the importance of view r for view r′. In §5.2.2, we discusshow to calculate φ(r, r′).The first step in our sampling is to compute the sampling probability of anincoming connection in relation type r. For an incoming edge e = (u, v, r, t) we37Algorithm 2 Temporal multiplex walk sampling procedureInput: The edge set E , previously sampled node wp in view rp at time t, andhyperparameter µOutput: Next sampled connection (wn, wp, rn, tn)1: for e = (wn, wp, rn, tn) ∈ E tp(wp) do2: Sample b ∼ UNIFORM(0, 1);3: if b < qtprp(wp, e)× φ(rp, rn) then4: return e = (wn, wp, rn, tn);5: return (eX , tX ); ▷ (eX , rX , tX ) is a dummy empty edge signaling the end ofthe algorithm.compute the probabilities qtr(w) for w ∈ {u, v} as follows:qtr(w, e) =exp (µt)∑(w0,t′)∈N tr (w) exp (µt′), (5.3)where N tr (w) represents the set of w’s neighbor in view r and before time t. Thisprobability needs to be computed one time when the connection arrives and doesnot need to be updated anymore. Also, for calculating the probability of samplingthis connection after a connection from another relation type r′, we simply multiplythis probability by φ(r, r′).Algorithm 2 shows the sampling procedure. Given a previously sampled con-nection in view r at time t, we sample the next connection in view r′ at time t′ < twith a probability proportional to exp (µ(t′ − t))× φ(r, r′). It is not hard to showthat Algorithm 2 samples the next connection with a probability proportional toexp (µ(tn − tp))×φ(rp, rn). Inspired by Wang et al. [163], in our experiments, westore the k most recent connections with k ∝ O(1µ). The intuition is that if we sortconnections in E t(wp) by their timestamp {ti}hi=1, and assume that exp (µ(ti − t))are i.i.d., the probability of sampling the j-th connection is:P[sampling j-th connection] =∏ji=1 exp (µ(ti − t))× φ(rp, ri)∑hi=1∏is=1 exp (µ(ts − t))× φ(rp, rs).This probability decreases when we increase the value of j. Accordingly, in practice,we need to store only a constant number of the most recent connections at each38time.Given a (potential) link (u, v, r, t), we use the above procedure to generate Minter-view and M ′ intra-view walks with m steps starting from each of nodes u andv. We use Sinter(u), Sintra(u), Sinter(v), and Sintra(v) to store started walks from uand v, respectively.Anonymization Process. Recent studies argue that traditional anonymizationmethods (e.g., [121]), where we assign node IDs based on only one walk, suffer fromseveral limitations (e.g., missing the correlation of different walks) and suggest usingan anonymization process that assigns hidden node IDs based on the correlation ofsampled walks [88, 163]. On the other hand, in multiplex networks, we need to hidethe identity of both nodes and views (e.g., relation types) to keep the model inductive.Given a (potential) link (u, v, r, t), letw0 ∈ {u, v}. To capture the correlation acrossdifferent walks, which could be a key to reflecting the network dynamics [163], fora given node w that appears on at least one walk in Sinter(u) ∪ Sinter(v), we usea relative vector C(Sinter(w0), w) ∈ Zm+1 that represents the number of times inSinter(w0) that node w appears at certain positions. That is,Ci (Sinter(w0), w) = |{Winter|Winter ∈ Sinter(w0), w =Winter(i, 0)}| , ∀0 ≤ i ≤ m.(5.4)Similarly, we define C(Sintra(w0), w) over intra-view temporal walks. Until now,node identities were accessible, but we now remove node identities and use onlythese four vectors in the training phase to represent each node, thereby hiding theiridentity:ID(w) = {C(Sinter(u), w), C(Sinter(v), w), C(Sintra(u), w), C(Sintra(v), w)} .(5.5)We hide the identity of relations, r, in a similar manner. Given a set of walks(e.g., Sinter(w0)), we count the number of times we see a relation type at eachposition when we start from a specific relation type; this captures the correla-tion among different views. For a given relation type r, we use a relative vectorCview(Sinter(w0), r) ∈ Zm+1 that counts times in Sinter(w0) that a relation with type39r appears at each position:Cviewi (Sinter(w0), r) = |{Winter|Winter ∈ Sinter(w0), r =Winter(i, 1)}| , ∀0 ≤ i ≤ m.(5.6)In this way, IDview(r) = {Cview (Sinter(u), r) , Cview (Sinter(v), r)} hides the identityof view r. Note that, although intra-view walks are within a single view, we stillneed to hide the identity of that view, and we use the same IDview(r) as above.5.2.2 Neural EncodingWe next present our fast and simple, yet effective and generalizable, neural networkto encode temporal multiplex walks so that we can extract structural and temporalinformation from the network. The intuition of this neural encoding is to useanonymous temporal multiplex walks to learn the structural and temporal propertiesas well as casual rules of the network in an inductive manner.Most existing methods on walk encoding treat a walk as a sequence of verticesand use sequence encoders such as RNNs or TRANSFORMERs to encode each walk.The main drawback of these methods is that they fail to directly process temporalwalks with irregular gaps between timestamps. That is, sequential encoders can beseen as discrete approximations of dynamic systems; however, this discretizationoften fails if we have irregularly observed data [96]. We present a neural networkto encode temporal multiplex walks so that we can extract structural and temporalinformation from the network with continuous time dynamics. The process consistsof 1 a time encoding module to encode the time, 2 a node encoding module toencode the position of vertices, 3 a view encoding module to encode relation type,and 4 a walk encoding module to encode each extracted motif.Time Encoding. Existing methods in temporal graph learning [49, 163] use ran-dom Fourier features [95] to encode time. However, this approach captures onlyperiodicity in the data, while in many domains, e.g., brain activity patterns, we alsoneed to learn non-periodic patterns dependent on the progression of time (e.g., intask-based fMRI). We address this need by adding a learnable linear term to thefeature representation of time encoding. That is, we encode a given time t as:T (t) = (ωlt+ bl) || cos(tω), (5.7)40where ωl,bl ∈ R and ω ∈ Rd are learnable parameters, and || denotes concatena-tion.Node Encoding. We now define a node encoding function ζ(.) that encodeseach node w based on ID(w). Since the concept and task of intra-view and inter-view walks are different, we first break the ζ(.) function into ζintra(.) and ζinter(.),respectively, and then interpolate between them by a learnable parameter λ to obtainζ(.).For each node w that appears on at least one walk in Sinter(u) ∪ Sinter(v), weuse one simple MLP to encode the w’s hidden identities:ζinter(w) = MLP (C(Sinter(u), w)) + MLP (C(Sinter(v), w)) . (5.8)While inter-view walks naturally capture the causal relationship and correlationbetween different types of connections, intra-view walks have a different roleand capture causality within a single view. However, we need to aggregate theinformation provided by inter-view walks in different views to take advantage ofcomplementary information in multiplex networks. As discussed in Section 4.2.3,the importance of each view for each vertex can be different; we use the attentionmechanism introduced in Section 4.2.3 to learn the importance of views r for vertexu, ψ(w, r).ψ(w, r) =exp(σ(srTWatt ζrintra(w)))∑Lk=1 exp(σ(skTWatt ζkintra(w))) , (5.9)where sr is a summary of the network in relation type r, i.e., sr =∑u∈V ζrintra(u),and Watt is a trainable weight matrix. In our experiments, we use tanh(.) as theactivation function σ(.). Similarly, we define the importance of node w for view ras follows:ψ(r, w) =exp(σ(srTWatt ζrintra(w)))∑w0∈V exp(σ(srTWatt ζrintra(w0))) , (5.10)In these equations, ζrintra(w) is the view-based node encoding of w in view r, whichwe define as follows: Given a relation type r′ ∈ L, we define view-based node41encoding ζr′intra(w) as:ζr′intra(w) = MLP(C(Sr′intra(u), w))+ MLP(C(Sr′intra(v), w)). (5.11)Next, we aggregate these node embeddings to incorporate information from differentviews and obtain ζintra(w):ζintra(w) =∑r′∈Lψ(w, r′)ζr′intra(w). (5.12)Now, we use a learnable parameter λ to automatically learn the importance of eachζintra(w) and ζinter(w) based on the data. This formulation lets our model learn tointerpolate between Equation 5.8 and Equation 5.12, which enables it to be flexiblein whether causal relationship between views exists or not. Therefore, ζ(w) isdefined as:ζ(w) = ζintra(w) + λ× ζinter(w). (5.13)When there is no causal relation between different views, our model is expected toset λ ≈ 0 (see §5.4).View Encoding. For each view r ∈ L, we use one simple MLP to encode the r’shidden identities:η(r) = MLP(Cview(Sinter(u), r))+ MLP (Cview(Sinter(v), r)) . (5.14)As discussed in Section 5.2, we use the importance of view r for view r′, φ(r, r′),to sample the next connection in inter-view walks. In fact, φ(r, r′) measures howsimilar these two views are. Given the vector representation of views, we usethe inner product to measure the similarity of different views. Now based on theobtained view encoding, η(r), we define:φ(r, r′) =η(r).η(r′)∑rˆ∈L η(r).η(rˆ). (5.15)Walk Encoding. Given a walk Wˆ ∈ {Winter,Wintra}, we use node encodingfunction ζ(.) : Z(m+1)×4 → Rk1 to encode hidden node identities and η(.) :42Z(m+1)×2 → Rk2 to encode hidden view identities. We then concatenate theiroutputs with the embedding of the node’s corresponding timestamp. Finally, we usean MLP-Mixer [151] to mix these encodings to obtain the walk encoding:ENC(Wˆ ) = MEAN(Htoken +W(2)σ(LayerNorm (Htoken)W(1))), (5.16)where the i-th row of Htoken is defined as:Hitoken =[ζ(ID(Wˆ (i, 0)))|| η(IDview(Wˆ (i, 1)))||T (ti)]. (5.17)In the above equations, W(1),W(2),W(1)token, and W(2)token are learnable parameters,LayerNorm is layer normalization [10] and σ(.) is a nonlinear function (e.g.,Gaussian error linear units, GeLU [84]).Anomaly Score. To assign an anomaly score to a given link e = (u, v, r, t) ∈ E , wefirst sample temporal multiplex walks and then encode each walk W ∈ Sinter(u) ∪Sinter(v)∪Sintra(u)∪Sintra(v) as described above. Next, we use an AGG(.) function(e.g., mean-pooling) to aggregate walks’ encodings and encode link e. Finally, weuse a 2-layer perceptron to make the anomaly score:Υ(e) = MLP 1M +M ′∑WˆENC(Wˆ ) , (5.18)where M and M ′ are the numbers of inter-view and intra-view walks.5.2.3 ADMIRE FrameworkWe next explain how we use the view-aware edge encoding method to detectanomalous interactions. Figure 5.1 illustrates the ADMIRE framework.Negative Sample Generator. We generate negative samples (NS) to train ADMIREin an unsupervised manner. Previous anomaly detection methods mostly use (simpleor biased) random negative samples [17, 188], which limit their generalizability toreal anomalous patterns [138]. Moreover, these methods are designed for simplenetworks and cannot generalize to anomalous patterns in multiplex networks. In-spired by Poursafaei et al. [138], we design a novel negative sampling method for43temporal multiplex networks.Let Etrain and Et ⊆ Etrain be the set of edges in the training set and in timestampt, respectively. For each edge in the training set e = (u, v, r, t) ∈ E , we generatethree types of negative samples: 1 Inter-view negative samples: We use thesenegative samples so our model learns to detect connections that are anomalous acrossdifferent views. We randomly generate a negative connection with relation type rwith probability inversely proportional to the number of views (or the summation ofviews’ weight, in the case that the importance of views are different) in which thisconnection appears. The intuition is that if two nodes are already connected withseveral types of connections, a connection of yet another type is unlikely to be ananomalous connection. 2 Intra-view negative samples: Here, we follow previousnegative sampling generation methods [17, 188] and randomly change one endpointof a connection to another node and keep the type of connection unchanged. 3Historical negative samples: we generate negative edges from the set of edgesthat have been observed during previous timestamps but are absent in the currenttimestamp. That is, we randomly sample an edge e ∈ Etrain ∩ E¯t.Training and Loss Function. Let Etrain be the set of edges in the training set andEneg be the set of generated negative samples. For each edge e ∈ Etrain ∪ Eneg wegenerate temporal multiplex walks to find a view-aware edge encoding of e. Next,we use the margin-based pairwise loss [28] to train the model. To avoid overfitting,we also use an L2-regularization loss, L regr , which is the summation of the L2norm of all trainable parameters. This produces the loss function:L =∑(u,v,r,t)∈Etrain∑(u′,v′,r,t)∈Enegmax{0, γ +Υ(u, v, r, t)−Υ(u′, v′, r, t)}+λL reg,(5.19)where 0 ≤ γ ≤ 1 is the margin between normal and negative sampled edges.445.3 ADMIRE++: Explainable Anomaly Detection inMultiplex Dynamic NetworksTo apply ADMIRE in real-world sensitive applications (e.g., health-related domainsor financial networks), it is not sufficient to simply make accurate predictions;domain experts often want to understand why the given model made the predictionit did. We design a post-hoc explainability method to mimic the predictions ofADMIRE. Recall that the main intuition behind ADMIRE is to extract the causalityof network dynamics by backtracking over time, extracting network multiplexmotifs. We use these extracted motifs to describe the neighborhood of each nodeand then use this data to train a decision tree model. Our goal is that the decisiontree can explain why a connection is abnormal based on the neighborhoods of itsendpoints.The main challenge is that we have diverse network motifs in large and densenetworks, so we need many features to accurately describe the neighborhood ofeach node. We use k-mean clustering [112] on the walk embeddings obtained inSection 5.2.2, grouping network motifs based on their similarity. Clearly, biggervalues for k produce better explanations.Let Minter and Mintra be the set of sampled walks started from the endpoints ofall connections in the training set. We encode all walks w ∈Minter∪Mintra by usingthe procedure introduced in Section 5.2.2. Next, we apply k-mean clustering [112]to obtain C1, . . . , and Ck. Then, for each connection e = (u1, u2, r) ∈ Etrain, weconstruct feature vector ve = (vu1 vu2) as follows:ve =p11 p12 . . . p1k︸ ︷︷ ︸vu1p21 p22 . . . p2k︸ ︷︷ ︸vu2 , (5.20)where p1i and p2i are normalized counting number of sampled walks (motifs) startingfrom u1 and u2 in cluster i. That is, p1i =C1iC , where C1i is the number of sampledwalks starting from u1 that are in cluster Ci, and C is the total number of sampledwalks. Similarly, p2i =C2iC , where C2i is the number of sampled walks startingfrom u2 that are in cluster i. Therefore, in this design, p1i s and p2i s describe thedistribution of motifs in the neighborhoods of nodes u1 and u2, respectively.45Given the set of connections in the training set Etrain, let V = {ve|e ∈ Etrain},and M be the ADMIRE model trained on Etrain. We use M(e) to represent theprediction of ADMIRE for e. We use ψ(r, u) to denote the importance of nodeu for view r (see Equation 5.10), and based on that, we define the importance ofconnection e = (u, v, r) as ψ(e) = ψ(r,u)+ψ(r,v)2 . Finally, we use Ψ to denote theset of ψ(e) for e inEtrain. Let y = {ye ∈ {“Normal”, “Anomaly”}|M(e) = ye},we construct a dataset Dtree = (V,y,Ψ) to train a weighted optimal decision tree.Here, the constructed feature for each connection is a data sample, the prediction ofADMIRE for this data sample is the label, and ψ(e) is the weight of each sample.Finally, we train our decision tree on this dataset via the algorithm from Behrouzet al. [21]; the sparsity in optimal sparse decision trees guarantees interoperabilityand the algorithm guarantees the performance quality of the model [21].To choose the value of k, we need to consider the number of walks, the numberof samples, and the computing resources. That is, larger k leads to more accurateclustering and better performance, accordingly; however, it can significantly affectthe running time of the weighted sparse decision tree algorithm. To this end, wetune 2× k as the maximum number of features that the weighted sparse decisiontree algorithm can find the optimal solution in less than a time threshold.Inference. In the inference phase, for each connection e = (u, v, r) we first sampleinter-view and intra-view walks starting from u and v. Based on the sampled walks,we construct the feature ve using Equation 5.20. Finally, we use the constructedfeature vector to make a prediction for e by the trained optimal tree. Since the modelis an interpretable tree the path of prediction explains ADMIRE’s prediction.5.4 Experiments5.4.1 Experimental SetupWe tune hyper-parameters by cross-validation and search the hyper-parameters over1 µ ∈ {0.5, 1, 2, 4}×10−5, 2 Inter-view sampling numberM ∈ {32, 64, 128, 256},3 Intra-view sampling number per view M ′ ∈ {8, 16, 32, 64}, 4 Walk lengthm ∈ {2, 4, 8, 12}. In training, we use a learning rate of 0.0001, hidden dimension100 in MLP-Mixer, and batch size of 600.46Table 5.1: Performance comparison of ADMIRE and baselines in multiplexnetworks (AUC).Methods RM DKPol Amazon DBLP Ethereum RippleAnomaly % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 %Single-layer MethodsGOUTLIER 0.7138 0.6982 0.6844 0.6597 0.6973 0.6672 0.7059 0.6901 0.7017 0.6799 0.7036 0.6851CM-SKETCH 0.7127 0.7012 0.7058 0.6930 0.6881 0.6719 0.7186 0.6915 0.7408 0.7277 0.7360 0.7194NETWALK 0.7739 0.7641 0.7706 0.7581 0.7228 0.7122 0.7742 0.7523 0.7956 0.7885 0.7904 0.7823ADDGRAPH 0.8005 0.8093 0.8149 0.8087 0.7796 0.7735 0.8024 0.7995 0.8133 0.8090 0.8205 0.8217Multiplex MethodsMNE 0.7994 0.7955 0.8050 0.7913 0.7108 0.7017 0.7532 0.7499 0.7541 0.7495 0.7813 0.7754ML-GCN 0.7921 0.7886 0.7915 0.7907 0.7344 0.7263 0.7519 0.7439 0.7940 0.7918 0.8115 0.8072ANOMULY 0.8783 0.8729 0.8694 0.8610 0.8289 0.8195 0.8825 0.8754 0.8906 0.8852 0.8938 0.8871ADMIRE 0.9016 0.9125 0.9093 0.8952 0.8097 0.8041 0.8873 0.8824 0.8416 0.8392 0.9160 0.8899Improvement 2.65% 4.53% 4.59% 3.97% -2.31% -1.88% 0.54% 0.79% -5.50% -5.19% 2.48% 0.32%Table 5.2: Performance comparison of ADMIRE and baselines in single-layernetworks (AUC).Methods Bitcoin Amazon-S DBLP-SAnomaly % 1% 5 % 1% 5 % 1% 5 %GOUTLIER 0.7143 0.7091 0.6923 0.6614 0.7108 0.6995CM-SKETCH 0.7146 0.7015 0.7049 0.6621 0.7084 0.6877NETWALK 0.8375 0.8367 0.7483 0.7302 0.7779 0.7590ADDGRAPH 0.8534 0.8416 0.7872 0.7828 0.7911 0.7932ANOMULY 0.8707 0.8661 0.8014 0.7943 0.8129 0.8236ADMIRE 0.8996 0.8902 0.7935 0.8007 0.8521 0.8509Improvement 3.32% 2.78% 0.99% 0.81% 4.82% 3.31%The experimental setup, datasets, baselines, and anomaly injection approach areall the same as what we used for ANOMULY as described in Section 4.3.5.4.2 ResultsWe compare ADMIRE with the baseline methods as well as ANOMULY on bothdynamic and static multiplex networks with different percentages of anomalous47edges (i.e., 1%, 5%). Table 5.1 reports the AUC for ADMIRE and both the baselinesand ANOMULY. ADMIRE outperforms all baselines in all datasets and outper-forms ANOMULY in four out of six multiplex network datasets. It improves theANOMULY results by 2.48%, on average, in the four datasets. There are threereasons for ADMIRE’s superior performance: (1) ADMIRE is an inductive methodand does not rely on node identities, which makes it a powerful tool for the detectionof complex patterns. (2) ADMIRE uses a time encoder module that can capturethe temporal patterns in continuous timestamps, instead of approximating time bydiscrete snapshots. (3) ADMIRE uses a novel negative sample generator that allowsit to learn more complex anomalous patterns.ANOMULY outperforms ADMIRE in two datasets: Amazon and Ethereum.These datasets have discrete timestamps and are naturally snapshot-based, soANOMULY correctly captures their temporal properties; ADMIRE’s continuoustime modeling is not useful. Also, these two datasets are particularly sparse, andrandom-walk-based methods might not be able to capture neighborhoods properly.This sparsity might cause the inter-view and intra-view walks in ADMIRE to treatfar nodes as neighbors.Table 5.2 reports the AUC for both the baselines and ANOMULY on single-layernetworks. Results show the same pattern as in Table 5.1. The only exception isAmazon-S data when we have 5% anomalous connections. ADMIRE’s ability todetect more complex anomalous patterns coupled with the relatively large percentageof anomalous connections makes this task more difficult for ANOMULY than forADMIRE, leading to ADMIRE outperforming ANOMULY.5.4.3 Ablation StudyWe next conduct ablation studies on the Amazon, DBLP, and Ethereum datasets tovalidate the effectiveness of ADMIRE’s critical components. Table 5.3 shows AUCresults for the anomaly detection task in multiplex networks with an anomaly rate of1%. The first row reports the performance of the complete ADMIRE implementation.Each subsequent row shows results for ADMIRE with one module modification: thesecond row removes inter-view walks, the third row removes intra-view walks, andthe fourth row removes learnable parameter λ and uses the summation of inter-view48Table 5.3: Ablation study on ADMIRE (AUC). In each row, we remove/re-place one of the ADMIRE’s components and keep the others unchanged.Methods Amazon DBLP Ethereum1 ADMIRE 0.8097 0.8873 0.84162 w/o inter-view 0.7901 0.8699 0.82543 w/o intra-view 0.7619 0.8307 0.83524 w/o λ (λ = 1) 0.7946 0.8651 0.83905 w/o attention 0.7953 0.8612 0.82086 w/o time encoding 0.7615 0.8644 0.80257 w/o inter-view NS 0.7998 0.8819 0.82118 w/o intra-view NS 0.8032 0.8794 0.83879 w/o historical NS 0.8055 0.8537 0.837610 w/ RNN 0.7812 0.7929 0.8341Table 5.4: Accuracy (%) of generated tree explanation on Amazon, DBLPand Ethereum. This table shows how well ADMIRE++ mimics ADMIREpredictions. We embolden the best results for each depth and use anunderline to show the best performance for each dataset.Depth Amazon DBLP Ethereumk = 3 k = 4 k = 5 k = 6 k = 3 k = 4 k = 5 k = 6 k = 3 k = 4 k = 5 k = 64 67.04 74.19 75.73 75.54 65.33 67.15 69.78 70.12 65.23 67.91 68.52 70.365 71.95 79.47 81.28 82.56 70.49 71.62 73.91 75.35 66.07 70.24 74.50 79.486 72.62 82.80 84.36 86.71 71.15 75.86 76.02 78.11 69.19 75.09 82.39 84.05and interview encodings. The fifth row removes the attention module, the sixth rowmoves the time encoding module, the seventh to ninth rows remove different typesof negative samples in the training, and the last row replaces MLP-Mixer with anRNN. The results show that each component contributes to ADMIRE’s performance.The greatest contribution comes from intra-view, MLP-Mixer, and time encodingmodule.495.4.4 How Well Does ADMIRE++ Mimic ADMIRE?We evaluate how well ADMIRE++ mimics ADMIRE by reporting the accuracyof ADMIRE++ on the Amazon, DBLP, and Ethereum datasets in Table 5.4. Asexpected, considering more features (larger k) results in better performance, becauseincreasing the k allows ADMIRE to more accurately distinguish different networkmotifs. However, even with a small number of features, k = 4, we can achieve goodperformance (Acc ≥ 75%) on mimicking ADMIRE’s prediction.5.4.5 What Does the Generated Tree Look Like?We now examine how to use ADMIRE++ to interpret predictions. Figure 5.2 showsthe generated tree by ADMIRE++ and the motif clusters with an extracted motifin each cluster when k = 3 and depth= 4. One can interpret the decision treeprediction as: a link is abnormal if one of its endpoints has some connections inonly one view. However, if both of its endpoints have the same status (both haveneighbors in either only one view or different views), the connection is normal.That is, given the fact that the Amazon dataset has only two views, clusters 1 and3 represent the neighborhood of a node where most of its connections are in oneview. Cluster 2 represents the neighborhood of a node where its connections withneighbors have diverse types. Therefore, for a normal connection, we expect tosee the same distribution of clusters 1 and 3 in sampled walks started from theconnection endpoints.What Do the Clusters Look Like? As discussed in Table 5.4, the number ofclusters (i.e., k) can directly affect the performance of ADMIRE++. However, itis not the only factor as the distribution of the walk encodings in the embeddingspace is also important. That is, if walk encodings in the embedding space are hardto distinguish, the decision tree might not be able to distinguish them either. Tothis end, we use t-SNE and visualize the walk encodings in a 3D space. The resultsare shown in Figure 5.3. While clusters of walks in the Amazon dataset are easilydistinguishable, clusters in DBLP and Ethereum datasets are harder to distinguish.Accordingly, it is harder for the decision tree to mimic ADMIRE on the DBLP andEthereum than on the Amazon dataset, which explains ADMIRE++’s performancein Table 5.4.50Motif ClustersCluster 1:Cluster 2:Cluster 3:Normal NormalNormalNormal Anomaly AnomalyFigure 5.2: (Top) Motif clusters and example of an extracted motif in eachcluster. (Bottom) The ADMIRE++ tree explanation on the Amazondataset (depth=4). Different colors in the motif examples show thechanges in views. Here, P j i are the features constructed in Equa-tion 5.20.We further discuss ADMIRE++ for analyzing the human brain in Chapter 6.5.5 ConclusionWe present ADMIRE, an end-to-end inductive unsupervised learning methodon multiplex networks to detect anomalous connections. ADMIRE uses inter-view (resp. intra-view) temporal walks to implicitly extract network motifs andcausal relationships across different views (resp. within a view) and adopts novelanonymization based on the correlation between multiplex network motifs to hidethe identity of nodes and views. Next, it uses an MLP-Mixer to encode the sequenceof nodes and views in a walk. By aggregating all the walks starting from a node,51(a) Amazon (b) DBLP(c) EthereumFigure 5.3: 3D visualization of clusters using t-SNE (k = 4). While clustersof walks in the Amazon dataset are simply distinguishable, clusters inDBLP and Ethereum datasets are hard to distinguish, which is the reasonfor the worse performance of ADMIRE++ (see Table 5.4) on these twodatasets.52ADMIRE encodes its neighborhood. Finally, it uses a classifier that labels con-nections as normal/abnormal based on their endpoints’ neighborhood. To explainADMIRE’s prediction in sensitive domains, we present ADMIRE++ that leveragesthe extracted inter-view and intra-view walks in ADMIRE to explain why a con-nection is predicted as abnormal. It uses a weighted optimal sparse decision treemodel, which is a provably powerful interpretable model, to mimic ADMIRE’spredictions. Our experimental results show the superior performance of ADMIREagainst ANOMULY and baselines.53Chapter 6Anomaly Detection in the HumanBrainWe now turn to a particularly interesting application of ANOMULY and ADMIRE atthe intersection of health and neuroscience. We discuss three different approaches tomodeling multimodal neuroimaging data as multiplex networks and show howANOMULY and ADMIRE can address the limitations of existing methods inanomaly detection in human brain networks. Our experiments on Parkinson’sDisease (PD), Attention Deficit Hyperactivity Disorder (ADHD), and Autism Spec-trum Disorder (ASD) show the efficiency and effectiveness of our approach indetecting anomalous brain activity in people living with these diseases or disorders.6.1 IntroductionRecently, the fields of neuroscience and brain imaging research have undergone asignificant shift in focus from region-specific analyses to network models [13, 123],largely due to the rapid development of modern neuroimaging technology. Networkmodels of the brain represent regions of interest (ROIs) as nodes and calculatepairwise similarities between regions to form edges [69], usually derived fromfunctional Magnetic Resonance Imaging (fMRI) or structural Magnetic ResonanceImaging (sMRI). These models have been helpful in enhancing our understanding ofbrain diseases and disorders [42, 140]. As a result, empirical data on brain networks54has substantially increased in size and complexity, leading to a strong demand forappropriate tools and methods to model and analyze it [140].At the same time, there has been significant interest in machine learning methodsfor analyzing graph-structured data in various domains, such as drug discovery [167],neuroscience [1], and biology [73]. While several studies demonstrated the effi-cacy of machine learning on graphs for analyzing human brain networks, mostfocus on graph or node classification tasks [54, 94]. These tasks involve detectingdiseases [190], predicting biological features [94], and identifying functional sys-tems [16]. However, detecting abnormal brain activity in people with neurologicaldisorders is a crucial step in understanding the causal mechanisms of symptoms,facilitating early detection and the development of medical treatments. Most ex-isting studies consider a single brain network (from a single type of neuroimageor a single subject), which can be noisy or incomplete [6, 185]. To address thislimitation, De Domenico [59] suggests using static multiplex networks. Multiplexnetworks are graphs where nodes can be connected by different types of edges [98].Edge types can be the brain networks of different subjects or different neuroimagingmodalities.Limitation of Previous Methods. Although anomaly detection in graphs is awell-studied problem, brain networks have five unique traits that make directlyapplying existing graph anomaly detection models impractical: 1 Noisy data:a single neuroimaging data sample can be extremely noisy and inaccurate [6],which hinders the identification of biological insights into the structure of brainnetworks. Existing general anomaly detection methods can use only a singlebrain image, making them sensitive to noise, or one must aggregate differentneuroimages as a pre-processing step, missing complex brain activity in eachbrain image. 2 Multimodal neuroimaging: while several studies discussed theimportance of using different neuroimage types (e.g., fMRI, sMRI, etc.), becausedifferent modalities provide complementary information [186, 191], existing worksare limited to a single type of neuroimage and are unable to incorporate informationabout different modalities. 3 Complex activity: brain activities are complex andpotentially different in different subjects, while existing methods are designed in thetransductive setting, which limits their generalizability to unseen nodes or patterns.554 Time alignment: existing methods assume that the timestamps in different graphsare meaningfully related. However, while modeling neuroimage data as temporalbrain networks, the timestamps might be shifted and are unlikely to be alignedacross brain images of different subjects. 5 Explainability: decision making onhealth-related data, which is sensitive, requires explainable models, but existingmethods are uninterpretable black boxes.There are two other limitations that plague existing studies: i These studiesassume pre-defined anomaly patterns or man-made features. Such approaches donot easily generalize to the brain activity of different individuals. Moreover, in areal-world scenario, brain activity might be more complex in nature, and it is nearlyimpossible to detect anomalies with high accuracy using pre-defined patterns/roles.ii These methods are designed for static brain networks, missing the dynamics ofbrain activity over time.6.2 Related Work on Machine Learning for BrainNetworksFeature Learning in Brain Networks. In recent years, several studies focusedon analyzing brain networks to understand and distinguish healthy and diseasedhuman brains [44, 86, 165]. Recently, due to the success of GNNs in analyzinggraph-structured data, deep models have been proposed to predict brain diseasesby learning the graph structures of brain networks [52, 54, 91, 92, 190]. All thesemethods are designed for either graph or node classification and cannot easily beextended to edge-anomaly detection.Anomaly Detection in Brain Networks. Several recent studies focus on analyzingbrain networks to distinguish healthy and diseased human brains [44, 86, 165].Due to the success of GNNs in analyzing graph-structured data, deep models havebeen proposed to predict brain diseases by learning the brain network structure [52,54, 91, 92, 190]. Several anomaly detection methods have been proposed to findanomalous regions or subgraphs in the brain, which might indicate the presenceof a disease [42, 109, 184]. All these methods are designed for node or subgraphanomaly detection tasks in single brain networks and cannot easily be extended todetect anomalous edges in multiplex brain networks. Also, these methods do not56learn anomalous patterns; they find only pre-defined patterns/rules for anomalies.6.3 Why/How to Model Human Brain as a MultiplexNetworkGiven a neuroimaging dataset, we answer the following three questions:Q1: How does multiplex modeling improve upon modeling a single network? Whilemodeling the human brain as a network has gained much attention in the neuro-science community in recent years [108, 114], most studies have focused on a singletype of simple brain networks [42, 109]. However, recent research on brain networkanalysis suggests that different modalities of brain networks provide complementaryinformation [186, 191]. The fusion of multiple modalities can lead to consistentimprovements in brain analysis. Additionally, several studies suggest that brainnetworks generated from an individual can be noisy and incomplete [6, 101, 185].Consequently, researchers are exploring the possibility of studying the human brainwithout necessarily discarding or aggregating the vast amount of data available [59].Multiplex brain networks, where each view represents a type of neuroimagingdata or the neuroimage of an individual, are accurate models that can capture thecomplementary information provided by different neuroimaging data and increasethe model’s robustness to noise and incompleteness in individual neuroimages.Q2: How can neuroimaging data be modeled as (temporal) multiplex networks? Wefocus on three ways to model neuroimaging data as multiplex networks.1 Activity in different frequency bands: in the context of fMRI images, previouswork utilizes filtering procedures to extract signals within a particular frequencyrange, typically between 0.01 and 0.1 Hz [59, 61]. However, the selection of thefrequency band carries significant implications for the functional representation ofthe brain. In fact, existing methods do not distinguish the contributions coming fromdifferent frequency bands, overlooking the contributions of different ranges, andinstead, concentrate on a single frequency range. To this end, De Domenico et al.[60] shows that brain signals in a range between 0.01 and 0.25 Hz, in steps of 0.02Hz, provide unique information and should be neither aggregated nor neglected. Wesuggest using multiplex brain networks, where each view represents the graph ofsignals in a specific range.572 Multimodal brain networks: Recently, several studies discussed the importanceof using different neuroimage types (e.g., fMRI, sMRI, Diffusion Tensor Imaging(DTI), etc.) in brain network analysis, as different modalities of brain networksprovide complementary information [186, 191]. A multiplex brain network canrepresent a multimodal brain network, where each view models the brain networkproduced from a specific type of neuroimage (e.g., fMRI or sMRI).3 Different subjects: Previous studies discuss the challenges of the existence ofnoise in a brain network generated from an individual [101, 185]. Most existingmethods aggregate (e.g., averaging) the data from different individuals to mitigatethe noise in the dataset [1, 42]. However, this aggregation discards complex patternsin each individual’s brain activity, causing missing information. Moreover, inbrain network disease/disorder analysis, it is known that individuals having the samedisease or disorder share similar patterns [55, 93], which means that disorder/disease-specific anomalous activity requires consideration of the brain networks of differentsubjects. In a multiplex brain network, each view can represent the brain networkof an individual.6.4 Modified Attention Mechanism For Multiplex BrainNetworksAs we discussed in Chapter 1 and Section 4.2.3, different views might exhibit differ-ent importance. For example, one disease might be more correlated with functionalconnectivity than structural connectivity, or a brain network of an individual can benoisy, and we need to automatically ignore it in the training process. We addressedthis in Section 4.2.3 by using an attention mechanism that learns the importance ofeach view for each node. While this attention mechanism is designed for generalmultiplex networks, assuming that the importance of each view for each node isdifferent, it is not the best approach to balance the trade-off between scalability andperformance. That is, although this mechanism is more general, it requires learningmany parameters, limiting its scalability to large networks with a large number ofviews. In our experimental evaluations on multiplex brain networks, we observethat the importance of one view for different nodes is almost the same. Therefore,we design a more efficient and scalable attention mechanism for multiplex brain58networks that learns the importance of each view for other views (independent ofnodes), because in a multiplex brain network we might have a large number ofviews (e.g., a large number of subjects, a large number of image modalities, or alarge number of frequency bands). One can interpret this attention mechanism as amodel that learns the correlation between each pair of views.Given two arbitrary views r1, r2, let η(r1) and η(r2) be the learned encodingof r1 and r2 (see Section 5.2.2). Inspired by Graph Attention Networks [154], wedefine the importance of r2 for r1, ψ(r1, r2), as:ψ(r1, r2) =exp(σ(a⃗T .[Watt η(r1) || Watt η(r2)]))∑r′∈L exp (σ (⃗aT .[Watt η(r1) || Watt η(r′)])),where a⃗ and Watt are learnable parameters and σ(.) is an activation function (e.g.,ReLU). The main intuition of this attention mechanism is to (1) use learnable matrixWatt to project view encodings to the same embedding space, and (2) use a⃗ to learnthe importance of each view in the concatenation. Note that the softmax function isused to normalize weights.6.5 Experiments6.5.1 Experimental Setting DetailsWe tune hyper-parameters by cross-validation, and search the hyper-parameters over1 µ ∈ {0.5, 1, 2, 4}×10−5, 2 Inter-view sampling numberM ∈ {32, 64, 128, 256},3 Intra-view sampling number per view M ′ ∈ {8, 16, 32, 64}, 4 Walk lengthm ∈ {2, 4, 8, 12}. Also, in the training, following the previous chapters, we usea learning rate of 0.0001, hidden dimension 100 in MLP-Mixer, and batch size of600.To visualize the average distribution of anomalous connections, we use Brain-Painter [118] with the Desikan-Killiany atlas.6.5.2 DatasetsWe evaluate ADMIRE and ANOMULY on multiplex brain networks using threereal-world datasets, PD [57], ADHD [29], and ASD [50]. Each of the datasets59represents one type of multiplex brain network modeling proposed in Section 6.3.PD Dataset. Attention dysfunction is a common symptom of Parkinson’s disease(PD) and has a significant impact on quality of life. This dataset [57] uses theAttention Network Test (ANT) [67] and is designed to study three aspects of atten-tion: alerting (maintaining an alert state), executive control (resolving conflict), andorienting. It consists of both structural and functional MRI images of participantswith and without PD, with six repetitions of the ANT task [67]. It contains data for25 subjects (7 female, age = 66.1± 10.0 yrs, years since disease onset = 8.4± 4.8)in the PD group and 21 subjects (12 female, age = 62.1 ± 9.9 yrs) in the healthycontrol group. We model the data using a temporal multiplex brain network withtwo views, 114 ROIs, and six timestamps (fMRI during each task). The first viewrepresents the brain network obtained from fMRI, while the second view representsthat generated from T1-weighted structural MRI.ADHD Dataset. This dataset consists of resting fMRI data taken from the USCMultimodal Connectivity Database [29]. The dataset contains data for 50 subjects(27 female, age = 9.84± 3.57 yrs) in the ADHD group and 50 subjects (25 female,age = 12.74± 4.1 yrs) in the typically developed (TD) control group. This datasetis preprocessed (https://ccraddock.github.io/cluster_roi/atlases.html). We modelthis data using a temporal multiplex brain network with 50 views, 190 ROIs, and 10timestamps; each view represents the brain network of an individual.ASD Dataset. This dataset consists of resting fMRI data taken from the AutismBrain Imaging Data Exchange (ABIDE) [50]; it contains data for 45 subjects (23female, age = 23.1± 8.1 yrs) in the ASD group and 45 subjects (22 female, age= 25.4± 8.9 yrs) in the typically developed control group. We have followed thefive pre-processing strategies denoted as DPARSF, followed by Band-Pass Filteringwith different filters in a range between 0.01 and 0.25 Hz, in steps of 0.02 Hz. Thisrange and steps are previously motivated by De Domenico et al. [60]. We modelthis data using a temporal multiplex brain network with 12 views, 116 ROIs, and10 timestamps; the i-th view represents the brain network obtained by filtering thefMRI values in the range [0.01 + (i− 1)× 0.02, 0.01 + i× 0.02] Hz.Synthetic Anomalies. In addition to real-world case studies on PD, ADHD, and60ASD, we use these datasets and inject anomalies (as we have done in Section 4.3) toinvestigate the parameter sensitivity of ADMIRE and also compare the performanceof ADMIRE and ANOMULY in inductive and transductive setting on the brainnetwork analysis domain.Pre-pocessing. Unless stated otherwise, for preprocessing and constructing brainnetworks from original fMRI and DTI data, we use the FSL toolbox and BrainGB [53].6.5.3 BaselinesWe evalute both ANOMULY and ADMIRE in the transductive setting and thenfurther evaluate ADMIRE in the inductive setting. Accordingly, in addition tothe baselines we used in Sections 4.3 and 5.4, we use three new methods that arespecifically designed for inductive settings, because none of the existing methods foranomaly detection are designed for inductive settings. These new baselines help usto investigate the performance of ADMIRE in the inductive setting. CAW-N [163]is an inductive method that uses causal anonymous walks to extract network motifsand a novel set-based anonymization process that keeps the model inductive byhiding the identity of nodes during the training phase. EvolveGCN [129] usesa RNN to estimate the GCN parameters for future snapshots. TGAT [56] usesGAT [154] to extract node representations where the nodes’ neighbors are sampledfrom the history and then encode temporal information via random Fourier features.We exclude ANOMULY in the inductive setting as it is designed for the transductivesetting and cannot generalize to unseen patterns or nodes.6.5.4 Experimental SetupIn each real-world experiment, we use the neuroimages of people in the controlgroup (either healthy or TD) to train the models. Once the models are trained, wetest them by using the neuroimages of people in the condition group (living withPD, ADHD, or ASD). In the inductive setting, we follow previous work [88, 163]and randomly hide 10% of nodes in the training phase.616.5.5 ResultsEffectiveness Evaluation. We first compare the effectiveness of ADMIRE andANOMULY with baselines on the task of detecting synthetic anomalous connec-tions. Table 6.1 reports the AUC of all the methods on different datasets. ADMIREoutperforms ANOMULY and all baselines by a significant margin (min = 6.42%and max = 18.04% performance improvement over the ANOMULY performance)in the transductive setting. There are four reasons for ADMIRE’s superior perfor-mance: 1 ADMIRE outperforms monoplex methods as it is a multiplex methodand is able to learn from different data sources, image modalities, or frequencybands by using inter-view walks and attention mechanism over intra-view walks thatincorporates complementary information from different views. 2 It outperformsmultiplex methods as it can capture the complex underlying rules of brain activitiesthrough its two causal walks over time. Also, its anonymization process hides theidentity of nodes and views and captures the correlation between walks, increasingits ability to generalize better to unseen patterns in the test data. ANOMULY usesGRU cells to update node embeddings in discretized time steps, limiting its abilityto model time as a continuous variable, which misses some continuous temporalpatterns in brain activity. That is, ADMIRE is a stream-based method and uses atime encoding module to capture time information, while ANOMULY is snapshot-based and aggregates edges into network snapshots, which remove some usefultime information [163]. 3 ADMIRE is scalable with respect to the number ofviews and can be trained on many data sources, image modalities, or frequencybands. ANOMULY, as well as ML-GCN, use different GNN modules for eachview, making them infeasible for large networks with a large number of views (e.g.,ADHD dataset with 50 subjects).Table 6.1 reports the performance of ADMIRE and inductive baselines in theinductive setting. We attribute ADMIRE’s superior performance (with min =11.08% and max = 26.89% improvement over the best baseline) to two mainreasons: 1 ADMIRE is an end-to-end anomaly detection method with an exclusive62Table 6.1: Performance comparison of ADMIRE and baselines in multiplexbrain networks (AUC).Methods PD ADHD ASDAnomaly % 1% 5 % 1% 5 % 1% 5 %TransductiveMonoplex MethodsGOUTLIER 61.42 59.98 65.37 64.70 60.85 59.13NETWALK 69.71 0.6902 70.29 69.86 69.07 68.52ADDGRAPH 71.94 70.33 71.89 70.11 71.30 70.96Multiplex MethodsMNE 70.39 70.54 73.78 72.31 70.19 69.94ML-GCN 68.50 68.33 -∗ -∗ 69.56 69.35ANOMULY 78.07 79.85 -∗ -∗ 77.14 77.08ADMIRE 85.09 84.98 88.67 88.53 91.06 89.95Inductive EvolveGCN 55.18 55.06 57.23 57.41 56.89 56.21TGAT 59.34 58.72 60.19 60.10 60.28 59.93CAW-N 75.85 75.90 71.64 71.02 71.31 71.96ADMIRE 84.72 84.31 88.03 88.97 90.49 90.28∗ Training time exceeds the threshold.Table 6.2: Ablation study of ADMIRE on brain network datasets. (AUC).Methods PD ADHD ASD1 ADMIRE 85.09 88.67∗ 91.062 w/o inter-view 78.59 88.73∗ 80.653 w/o intra-view 77.14 69.59 79.624 w/o λ (λ = 1) 80.42 80.36 89.305 w/o attention 84.79 86.14 86.576 w/o time encoding 84.16 82.78 85.927 w/o inter-view NS 84.77 84.28 83.468 w/o intra-view NS 79.91 78.75 81.099 w/o historical NS 84.68 84.16 84.3110 w/ RNN 83.90 85.32 89.1311 Monoplex-ADMIRE 76.52 72.07 74.15∗ There is no causal relation between views.63design of generating negative samples and training process, while baselines aredesigned to learn the temporal and structural properties of the network. 2 ADMIREis a multiplex method, while baselines are monoplex methods.Ablation Studies. We further conduct ablation studies to validate the effectivenessof each component of ADMIRE. The results are summarized in Table 6.2. Rows2 and 3 show the effectiveness of inter-view and intra-view walks. The onlyexception is removing the inter-view walks in the ADHD dataset. As we discussedin Section 5.2.2, when there is no causal relation between views, inter-view walksare not informative and our model is expected to learn to ignore these walks (setλ = 0). Accordingly, removing these walks from ADMIRE does not hurt theperformance on the ADHD dataset, because there is no causal relation betweenviews. Rows 4 and 5 show the importance of the learnable parameter λ and theattention mechanism that incorporates information from different views. Rows 7,8, and 9 show the importance of our new negative sample generator. When usingRNN instead of MLP-Mixer in the walk encoding phase (row 10), we gain betterperformance due to its ability to learn the dependency of nodes’ encoding in awalk. Finally, the last row shows the superior performance of multiplex ADMIREover monoplex ADMIRE, when using only one brain network generated from anindividual, image modality, or frequency band. These results show the importanceof multiplex modeling of neuroimages.Why Modified Attention Mechanism? Given a view r and a node u, we useΩ(u, r)to show the importance of view r for node u. We use the attention mechanismproposed in Section 4.2.3 and train the model on PD, ADHD, and ASD datasets.We observe that Ω(u, r) ≈ Ω(v, r) for any given view r and arbitrary nodes u andv. That is, given a view r, the maximum variance of Ω(u, r) for different nodes u is0.02, 0.05, and 0.02 in PD, ADHD, and ASD datasets, respectively.Our experimental evaluation shows that this attention mechanism, on average,requires ≈ 45% less training time on PD, ADHD, and ASD datasets.Parameter Sensitivity. We systematically analyze the effect of hyperparametersused in ADMIRE on the performance. Figure 6.1(a) shows that only a small numberof intra-view walks are enough to achieve competitive performance. While moreinter-walks improve the performance until some point, the performance gain is6422 24 26Number of inter-view walks (M)0.8000.8250.8500.8750.900AUCPD ADHD ASD(a) Intra-view walks22 24 26Number of intra-view walks (per view)0.8000.8250.8500.8750.900AUCPD ADHD ASD(b) Inter-view walks2 4 6 8 10Sampling Length m0.700.750.800.850.90AUCPD ADHD ASD(c) Walk Length0 200 400 600 800 1000Epochs0.00.20.40.60.81.0λvaluePD ADHD ASD(d) Evolution of λFigure 6.1: The effect of hyperparameters on the performance (a-c), and λevolution (d).saturated after that. A similar pattern can be seen for increasing the number of intra-view walks (Figure 6.1(b)). Note that this figure reports the number of intra-viewwalks per view. Accordingly, we expect to see more performance gain on datasetswith a fewer views (e.g., PD). Figure 6.1(c) shows that ADMIRE might achievethe best performance at a certain walk length, while the exact value depends on thecomplexity of higher-order motifs that are required to learn the underlying networkdynamics as well as the number of views. Networks with a large number of viewsmight need longer walks to learn the causal relation in different views, because ittakes more steps to visit all the interrelated views. Finally, Figure 6.1(d) showsthe evolution of λ in training. As expected, in datasets with no causal relationship65between different views (e.g., ADHD), ADMIRE learns to set λ ≤ 0.1 after onlya few epochs. For other datasets, it shows that ADMIRE converges quickly to thebest value of λ.Is Multiplex Modeling Robust to Noise? As discussed in Section 6.3, one ofthe main motivations for modeling neuroimaging datasets as multiplex networksis to make the model more robust to noise in each brain image. To validate theefficacy of this approach, we add Gaussian noise to a subset of brain images(5%, 10%, 20%, 30% and 40%) in the ADHD dataset. We model the noisy datasetas a multiplex brain network and use it to train ADMIRE. Next, as a baseline,following previous methods [101, 185], we take the average of all brain images inthe noisy dataset and use it to train the monoplex ADMIRE. Figure 6.2 reports theperformance of ADMIRE and monoplex ADMIRE with a varying fraction of noisysamples. Not only does ADMIRE achieve superior performance by a significantmargin, but it is more robust to noise than monoplex ADMIRE. This experimentshows the importance of multiplex modeling and also the efficacy of the proposedattention mechanism that learns to ignore noisy samples.6.5.6 Results on Real-world DatasetsWe next report findings from applying ADMIRE to real-world datasets. We train ourmodel on the healthy control group and then test it on the condition group (livingwith PD, ADHD, ASD) to find anomalous brain activity of people in the conditiongroup.Parkinson’s Disease. We focus on abnormal brain structure and functional activityof PD patients. Since the brain of each individual in each task might also haveunique complex activity, we need to focus on common or more frequently appearedanomalous connections between ROIs over different subjects to capture abnormalactivity that might be correlated to PD. To this end, we show how anomalousconnections found by ADMIRE are distributed in the brain of people living withPD. Figure 6.3 reports the average distribution of anomalous edges in the brainnetworks of people living with PD. Most anomalous edges found by ADMIREhave a vertex in either Posterior Cingulate, Superior Parietal, Medial Orbitofrontal,665% 10% 20% 30% 40%Noisy Data0.70.80.9AUC(a) Performance of ADMIRE5% 10% 20% 30% 40%Noisy Data0.50.60.7AUC(b) Performance of monoplex ADMIREFigure 6.2: The advantage of multiplex brain networks over monoplex brainnetworks.Figure 6.3: The distribution of anomalous edges in PD group.Figure 6.4: The distribution of anomalous edges in ADHD group.67Figure 6.5: The distribution of anomalous edges in ASD group.Pars Opercularis, or Supramarginal Gyrus (≥ 95% of all found anomalies). Mostanomalous edges found by ANOMULY have a vertex in the same brain regions.Next, we apply ADMIRE and ANOMULY on the healthy control group to seewhether these findings are exclusive to the PD group and to identify possible noisein the dataset. We observe that ADMIRE finds 94.2% fewer anomalous connectionsin the healthy control group, most of which have a node in either Temporal Poleor Anterior Insula. ANOMULY finds 85.91% fewer anomalous connections in thehealthy control group, most of which have a node in Temporal Pole.Attention Deficit Hyperactivity Disorder. Following the previous experiment, wefirst focus on abnormal brain activity in subjects in the ADHD group. Figure 6.4shows the average distribution of anomalous edges in the brain networks of subjectsin the condition ADHD group. Most abnormal connections found by ADMIREhave an endpoint in either Frontal Pole, Right Lateral Occipital Cortex, LingualGyrus, Left Temporal Pole, or Right Superior Parietal Lobule (≥ 95% of all foundanomalies). Interestingly, these findings are consistent with previous studies onADHD, using voxel-wise estimation of regional tissue volume changes [158], ab-normality in DTI images [103], and Forman–Ricci curvature changes [42], whichshows the potential of ADMIRE in revealing abnormal connections that might becorrelated to a brain disease or disorder. ANOMULY misses abnormal activities inLingual Gyrus, Left Temporal Pole, and Right Superior Parietal Lobule.Applying ADMIRE on the healthy control group, we observe that ADMIREfinds 89.6% fewer anomalous connections in the healthy control group, most ofwhich have an endpoint in either Planum Polare or Angular Gyrus. ANOMULYfinds 74.36% fewer anomalous connections in the healthy control group, most ofwhich have a node in either Frontal Pole or Angular Gyrus.68CA#P11 > 0.55#P31 > 0.39 #P12 > 0.51#P32 > 0.50 NormalNormal#P22 > 0.47#P42 > 0.39Normal Anomaly NormalAnomalyAnomalyCluster 1:Motif ClustersCluster 2:Cluster 3:Cluster 4:ABABABA A DDA B C EHow well does ADMIRE++ mimic ADMIRE?Figure 6.6: (Left) Motif clusters and example of an extracted motif in eachcluster. (Right) The ADMIRE++ tree explanation on PD dataset(depth=3). Different colors in the motif examples show the changesin views. Here, P j i are the features constructed in Equation 5.20.Autism Spectrum Disorder. Figure 6.5 shows the average distribution of anoma-lous edges in the brain networks of subjects in the condition ASD group. Mostabnormal connections found by ADMIRE have an endpoint in either Right SuperiorTemporal Gyrus, Right Cerebellum Cortex, Right Precuneus, Frontal Pole, Left Lat-eral Occipital (≥ 95% of all found anomalies). Although several studies about ASDfound different abnormality patterns, there is still no known ASD biomarker [124].However, part of our findings about abnormal activity in the cerebellum cortex isconsistent with previous studies [143]. ANOMULY misses abnormal activities inLeft Lateral Occipital and Right Cerebellum Cortex.Applying ADMIRE on the healthy control group, ADMIRE finds 93.7% feweranomalous connections in the healthy control group, most of which have an endpointin either Temporal Pole or Posterior Cingulate Cortex. ANOMULY finds 79.14%fewer anomalous connections in the healthy control group, most of which have anode in Temporal Pole.6.5.7 ADMIRE++ ExplanationsTo evaluate the quality of ADMIRE++, we use the PD dataset and set k = 4, so wehave 4 clusters and 8 features for each edge (4 features for each of its endpoints).Figure 6.6 (left) and (middle) show an example of motifs in each cluster and adecision tree with depth 3 that mimics the ADMIRE’s predictions. While motifs incluster 1 and 2 shows that the neighborhood of a node is sparse, motifs in cluster3 and 4 show that the neighborhood of the node is dense. One can interpret thedecision tree prediction as: a link is normal if the neighborhoods of its endpoints69Table 6.3: Accuracy (%) of generated tree explanation. This table shows howwell ADMIRE++ mimics ADMIRE predictions.Depth PD ADHD ASD3 75.43 74.98 83.394 81.76 77.15 90.285 87.52 83.17 91.06are both sparse or dense and is abnormal otherwise.The Table 6.3 reports the accuracy of how well ADMIRE++ mimics ADMIRE’spredictions. Even with small depths, ADMIRE++ produces explanations with highaccuracy.70Chapter 7ConclusionsWe introduced two novel frameworks, ANOMULY and ADMIRE, for detecting edgeanomalies in dynamic multiplex networks. ANOMULY utilizes a combination ofGNN layers and GRU cells, incorporating temporal and structural properties, alongwith an attention mechanism that integrates information across different types ofconnections. It further uses negative sampling during training to learn the anomalouspatterns in an unsupervised manner. While ANOMULY achieves good performanceand outperforms baselines, it suffers from poor scalability and memory usage andan inability to generalize to unseen nodes.To address these limitatons, we introduced ADMIRE, which leverages inter-viewand intra-view temporal walks to capture network motifs and causal relationshipswithin and across different views, respectively. ADMIRE uses an anonymizationtechnique to hide node and view identities, keeping the model inductive. Next,it utilizes an MLP-Mixer to encode the sequence of nodes and views in a walk.By aggregating walks from a node, ADMIRE encodes its neighborhood and usea classifier to label connections as normal or abnormal based on their endpoints’neighborhoods. We then introduced ADMIRE++ to explain ADMIRE’s predictionsusing weighted optimal sparse decision trees.We demonstrate the efficacy of ANOMULY and ADMIRE in analyzing theabnormal brain activity that might cause a brain disease/disorder. We conductcase studies on brain networks of individuals with Attention Deficit HyperactivityDisorder, Parkinson’s Disease, and Autism Spectrum Disorder. The results highlight71the potential of these frameworks to identify abnormal brain activity associated withvarious diseases and disorders. Overall, these frameworks provide valuable toolsfor analyzing dynamic multiplex networks and detecting anomalies with potentialapplications in diverse domains.72Bibliography[1] C. Abrate and F. Bonchi. Counterfactual graphs for explainableclassification of brain networks. In Proceedings of the 27th ACM SIGKDDConference on Knowledge Discovery; Data Mining, KDD ’21, page2495–2504, New York, NY, USA, 2021. Association for ComputingMachinery. ISBN 9781450383325. doi:10.1145/3447548.3467154. URLhttps://doi.org/10.1145/3447548.3467154. → pages 3, 55, 58[2] C. C. Aggarwal. Outlier analysis. In EDBT. Springer Cham, 2019. ISBN978-3-319-83772-7. doi:https://doi.org/10.1007/978-3-319-47578-3. →page 1[3] C. C. Aggarwal, Y. Zhao, and P. S. Yu. Outlier detection in graph streams. In2011 IEEE 27th International Conference on Data Engineering, pages399–409, 2011. doi:10.1109/ICDE.2011.5767885. → pages 14, 27[4] S. Aghaei, M. J. Azizi, and P. Vayanos. Learning optimal and fair decisiontrees for non-discriminative decision-making. Proceedings of the AAAIConference on Artificial Intelligence, 33(01):1418–1426, Jul. 2019.doi:10.1609/aaai.v33i01.33011418. URLhttps://ojs.aaai.org/index.php/AAAI/article/view/3943. → page 12[5] S. Aghaei, A. Gómez, and P. Vayanos. Strong optimal classification trees.arXiv preprint arXiv:2103.15965, 2021. → page 12[6] U. Agrawal, E. N. Brown, and L. D. Lewis. Model-based physiologicalnoise removal in fast fmri. NeuroImage, 205:116231, 2020. ISSN1053-8119. doi:https://doi.org/10.1016/j.neuroimage.2019.116231. URLhttps://www.sciencedirect.com/science/article/pii/S1053811919308225. →pages 3, 55, 57[7] M. Ahmed, A. N. Mahmood, and M. R. Islam. A survey of anomalydetection techniques in financial domain. Future Generation ComputerSystems, 55:278–288, 2016. → page 173[8] L. Akoglu and C. Faloutsos. Anomaly, event, and fraud detection in largenetwork datasets. In Proceedings of the Sixth ACM International Conferenceon Web Search and Data Mining, WSDM ’13, page 773–774, New York, NY,USA, 2013. Association for Computing Machinery. ISBN 9781450318693.doi:10.1145/2433396.2433496. URLhttps://doi.org/10.1145/2433396.2433496. → page 1[9] L. Akoglu, H. Tong, and D. Koutra. Graph based anomaly detection anddescription: a survey. Data Mining and Knowledge Discovery, 29(3):626–688, May 2015. ISSN 1573-756X. doi:10.1007/s10618-014-0365-y.URL https://doi.org/10.1007/s10618-014-0365-y. → pages 1, 3, 19, 27[10] J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization, 2016. → page43[11] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointlylearning to align and translate. In Y. Bengio and Y. LeCun, editors, 3rdInternational Conference on Learning Representations, ICLR 2015, SanDiego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URLhttp://arxiv.org/abs/1409.0473. → page 22[12] M. Bansal and D. Sharma. Ranking and discovering anomalousneighborhoods in attributed multiplex networks. In Proceedings of the 7thACM IKDD CoDS and 25th COMAD, CoDS COMAD 2020, page 46–54,New York, NY, USA, 2020. Association for Computing Machinery. ISBN9781450377386. doi:10.1145/3371158.3371164. URLhttps://doi.org/10.1145/3371158.3371164. → page 17[13] D. S. Bassett and O. Sporns. Network neuroscience. Nature Neuroscience,20(3):353–364, Mar 2017. ISSN 1546-1726. doi:10.1038/nn.4502. URLhttps://doi.org/10.1038/nn.4502. → page 54[14] R. E. Beaty, M. Benedek, P. J. Silvia, and D. L. Schacter. Creative cognitionand brain network dynamics. Trends in cognitive sciences, 20(2):87–95,2016. → page 13[15] R. E. Beaty, M. Benedek, P. J. Silvia, and D. L. Schacter. Creative cognitionand brain network dynamics. Trends in cognitive sciences, 20(2):87–95,2016. → page 13[16] A. Behrouz and F. Hashemi. Cs-mlgcn: Multiplex graph convolutionalnetworks for community search in multiplex networks. In Proceedings of the31st ACM International Conference on Information and Knowledge74Management, CIKM ’22, page 3828–3832, New York, NY, USA, 2022.Association for Computing Machinery. ISBN 9781450392365.doi:10.1145/3511808.3557572. URLhttps://doi.org/10.1145/3511808.3557572. → pages 15, 16, 28, 55[17] A. Behrouz and M. Seltzer. Anomaly detection in multiplex dynamicnetworks: from blockchain security to brain disease prediction. In NeurIPS2022 Temporal Graph Learning Workshop, 2022. URLhttps://openreview.net/forum?id=UDGZDfwmay. → pages vi, 37, 43, 44[18] A. Behrouz and M. Seltzer. Anomaly detection in human brain via inductivelearning on temporal multiplex networks. In Machine Learning forHealthcare Conference. PMLR, 2023. → page vi[19] A. Behrouz and M. Seltzer. ADMIRE++: Explainable anomaly detection inthe human brain via inductive learning on temporal multiplex networks. InICML 3rd Workshop on Interpretable Machine Learning in Healthcare(IMLH), 2023. URL https://openreview.net/forum?id=t4H8acYudJ. → pagevi[20] A. Behrouz, F. Hashemi, and L. V. S. Lakshmanan. Firmtruss communitysearch in multilayer networks. Proc. VLDB Endow., 16(3):505–518, nov2022. ISSN 2150-8097. doi:10.14778/3570690.3570700. URLhttps://doi.org/10.14778/3570690.3570700. → pages 3, 13, 25, 26, 27[21] A. Behrouz, M. Lécuyer, C. Rudin, and M. Seltzer. Fast optimization ofweighted sparse decision trees for use in optimal treatment regimes andoptimal policy design. CEUR Workshop Proc, 3318, Oct. 2022. → pages12, 46[22] A. Behrouz, F. Hashemi, S. Sadeghian, and M. Seltzer. Cat-walk: Inductivehypergraph learning via set walks, 2023. → pages 11, 15[23] D. Bertsimas and J. Dunn. Optimal classification trees. Machine Learning,106(7):1039–1082, 2017. → page 11[24] S. Bhatia, B. Hooi, M. Yoon, K. Shin, and C. Faloutsos. Midas:Microcluster-based detector of anomalies in edge streams. Proceedings ofthe AAAI Conference on Artificial Intelligence, 34(04):3242–3249, Apr.2020. doi:10.1609/aaai.v34i04.5724. URLhttps://ojs.aaai.org/index.php/AAAI/article/view/5724. → pages 1, 2, 1475[25] P. Bindu, P. S. Thilagam, and D. Ahuja. Discovering suspicious behavior inmultilayer social networks. Computers in Human Behavior, 73:568–582,2017. ISSN 0747-5632. doi:https://doi.org/10.1016/j.chb.2017.04.001. URLhttps://www.sciencedirect.com/science/article/pii/S0747563217302303. →page 16[26] B. B. Biswal, M. Mennes, X.-N. Zuo, S. Gohel, C. Kelly, S. M. Smith, C. F.Beckmann, J. S. Adelstein, R. L. Buckner, S. Colcombe, et al. Towarddiscovery science of human brain function. Proceedings of the NationalAcademy of Sciences, 107(10):4734–4739, 2010. → page 3[27] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. J. Mach.Learn. Res., 3(null):993–1022, mar 2003. ISSN 1532-4435. → page 26[28] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko.Translating embeddings for modeling multi-relational data. Advances inneural information processing systems, 26, 2013. → pages 23, 44[29] J. A. Brown, J. D. Rudie, A. Bandrowski, J. D. Van Horn, and S. Y.Bookheimer. The UCLA multimodal connectivity database: a web-basedplatform for brain connectivity matrix sharing and analysis. FrontNeuroinform, 6:28, Nov. 2012. → pages 59, 60[30] J. A. Brown, J. D. Rudie, A. Bandrowski, J. D. Van Horn, and S. Y.Bookheimer. The ucla multimodal connectivity database: a web-basedplatform for brain connectivity matrix sharing and analysis. Frontiers inneuroinformatics, 6:28, 2012. → page 31[31] J. Cadena, F. Chen, and A. Vullikanti. Graph anomaly detection based onsteiner connectivity and density. Proceedings of the IEEE, 106(5):829–845,2018. → page 14[32] J. Cadena, F. Chen, and A. Vullikanti. Graph anomaly detection based onsteiner connectivity and density. Proceedings of the IEEE, 106(5):829–845,2018. doi:10.1109/JPROC.2018.2813311. → page 1[33] L. Cai, Z. Chen, C. Luo, J. Gui, J. Ni, D. Li, and H. Chen. Structuraltemporal graph neural networks for anomaly detection in dynamic graphs. InProceedings of the 30th ACM international conference on Information &Knowledge Management, pages 3747–3756, 2021. → page 14[34] A. Cardillo, J. Gómez-Gardenes, M. Zanin, M. Romance, D. Papo, F. d.Pozo, and S. Boccaletti. Emergence of network features from multiplexity.Scientific reports, 3(1):1344, 2013. → page 3676[35] Y. Cen, X. Zou, J. Zhang, H. Yang, J. Zhou, and J. Tang. Representationlearning for attributed multiplex heterogeneous network. In Proceedings ofthe 25th ACM SIGKDD International Conference on Knowledge Discovery& Data Mining, pages 1358–1368, 2019. → pages 15, 16[36] S. Chakraborty, S. Aich, S. J. Seong, and H.-C. Kim. A blockchain basedcredit analysis framework for efficient financial systems. In 2019 21stInternational Conference on Advanced Communication Technology (ICACT),pages 56–60. IEEE, 2019. → page 3[37] B. P. Chamberlain, S. Shirobokov, E. Rossi, F. Frasca, T. Markovich, N. Y.Hammerla, M. M. Bronstein, and M. Hansmire. Graph neural networks forlink prediction with subgraph sketching. In The Eleventh InternationalConference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=m1oqEOAozQU. → page 15[38] S. Chang, W. Han, J. Tang, G.-J. Qi, C. C. Aggarwal, and T. S. Huang.Heterogeneous network embedding via deep architectures. In Proceedings ofthe 21th ACM SIGKDD international conference on knowledge discoveryand data mining, pages 119–128, 2015. → page 16[39] T.-H. Chang and D. Svetinovic. Improving bitcoin ownership identificationusing transaction patterns analysis. IEEE Transactions on Systems, Man, andCybernetics: Systems, 50(1):9–20, 2018. → page 3[40] Y.-Y. Chang, P. Li, R. Sosic, M. H. Afifi, M. Schweighauser, and J. Leskovec.F-fade: Frequency factorization for anomaly detection in edge streams. InProceedings of the 14th ACM International Conference on Web Search andData Mining, WSDM ’21, page 589–597, New York, NY, USA, 2021.Association for Computing Machinery. ISBN 9781450382977.doi:10.1145/3437963.3441806. URLhttps://doi.org/10.1145/3437963.3441806. → pages 1, 2[41] S. Chanpuriya, R. A. Rossi, S. Kim, T. Yu, J. Hoffswell, N. Lipka, S. Guo,and C. N. Musco. Direct embedding of temporal network edges viatime-decayed line graphs. In The Eleventh International Conference onLearning Representations, 2023. URLhttps://openreview.net/forum?id=Qamz7Q_Ta1k. → page 15[42] T. Chatterjee, R. Albert, S. Thapliyal, N. Azarhooshang, and B. DasGupta.Detecting network anomalies using forman–ricci curvature and a case studyfor human brain networks. Scientific Reports, 11(1):8121, Apr 2021. ISSN772045-2322. doi:10.1038/s41598-021-87587-z. URLhttps://doi.org/10.1038/s41598-021-87587-z. → pages3, 13, 32, 54, 56, 57, 58, 68[43] F. Chen and D. B. Neill. Non-parametric scan statistics for event detectionand forecasting in heterogeneous social media graphs. In Proceedings of the20th ACM SIGKDD international conference on Knowledge discovery anddata mining, pages 1166–1175, 2014. → page 14[44] G. Chen, B. D. Ward, C. Xie, W. Li, Z. Wu, J. L. Jones, M. Franczak,P. Antuono, and S.-J. Li. Classification of alzheimer disease, mild cognitiveimpairment, and normal cognitive status with large-scale network analysisbased on resting-state functional mr imaging. Radiology, 259(1):213, 2011.→ page 56[45] J. Chen, X. Wang, and X. Xu. Gc-lstm: Graph convolution embedded lstmfor dynamic link prediction. arXiv preprint arXiv:1812.04206, 2018. →page 15[46] L.-H. Chen, H. Li, and W. Yang. Anomman: Detect anomaly on multi-viewattributed networks, 2022. URL https://arxiv.org/abs/2201.02822. → page17[47] J. Cheng, Q. Wang, Z. Tao, D. Xie, and Q. Gao. Multi-view attribute graphconvolution networks for clustering. In Proceedings of the Twenty-NinthInternational Conference on International Joint Conferences on ArtificialIntelligence, pages 2973–2979, 2021. → pages 15, 16[48] J. Chung, C. Gulcehre, K. Cho, and Y. Bengio. Empirical evaluation of gatedrecurrent neural networks on sequence modeling. arXiv preprintarXiv:1412.3555, 2014. → pages 8, 19, 21[49] W. Cong, S. Zhang, J. Kang, B. Yuan, H. Wu, X. Zhou, H. Tong, andM. Mahdavi. Do we really need complicated model architectures fortemporal networks? In The Eleventh International Conference on LearningRepresentations, 2023. URL https://openreview.net/forum?id=ayPPc0SyLv1.→ pages 11, 15, 40[50] C. Craddock, Y. Benhajali, C. Chu, F. Chouinard, A. Evans, A. Jakab, B. S.Khundrakpam, J. D. Lewis, Q. Li, M. Milham, et al. The neuro bureaupreprocessing initiative: open sharing of preprocessed neuroimaging dataand derivatives. Frontiers in Neuroinformatics, 7:27, 2013. → pages 59, 6078[51] S. Cresci. A decade of social bot detection. Communications of the ACM, 63(10):72–83, 2020. → page 1[52] H. Cui, W. Dai, Y. Zhu, X. Li, L. He, and C. Yang. Brainnnexplainer: Aninterpretable graph neural network framework for brain network baseddisease analysis. arXiv preprint arXiv:2107.05097, 2021. → page 56[53] H. Cui, W. Dai, Y. Zhu, X. Kan, A. A. Chen Gu, J. Lukemire, L. Zhan,L. He, Y. Guo, and C. Yang. BrainGB: A Benchmark for Brain NetworkAnalysis with Graph Neural Networks. IEEE Transactions on MedicalImaging (TMI), 2022. → page 61[54] H. Cui, W. Dai, Y. Zhu, X. Li, L. He, and C. Yang. Interpretable graph neuralnetworks for connectome-based brain disorder analysis. In InternationalConference on Medical Image Computing and Computer-AssistedIntervention, pages 375–385. Springer, 2022. → pages 55, 56[55] H. Cui, W. Dai, Y. Zhu, X. Li, L. He, and C. Yang. Interpretable graph neuralnetworks for connectome-based brain disorder analysis. In L. Wang, Q. Dou,P. T. Fletcher, S. Speidel, and S. Li, editors, Medical Image Computing andComputer Assisted Intervention – MICCAI 2022, pages 375–385, Cham,2022. Springer Nature Switzerland. ISBN 978-3-031-16452-1. → page 58[56] da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan.Inductive representation learning on temporal graphs. In InternationalConference on Learning Representations, 2020. URLhttps://openreview.net/forum?id=rJeW1yHYwH. → page 61[57] T. K. M. Day, T. M. Madhyastha, M. K. Askren, P. Boord, T. J. Montine, andT. J. Grabowski. Attention network test fMRI data for participants withparkinson’s disease and healthy elderly. F1000Res, 8:780, June 2019. →pages 13, 59, 60[58] T. dblp team. dblp computer science bibliography. https://dblp.uni-trier.de,2014. → page 26[59] M. De Domenico. Multilayer modeling and analysis of human brainnetworks. GigaScience, 6(5), 02 2017. ISSN 2047-217X.doi:10.1093/gigascience/gix004. URLhttps://doi.org/10.1093/gigascience/gix004. gix004. → pages 3, 55, 57[60] M. De Domenico, S. Sasai, and A. Arenas. Mapping multiplex hubs inhuman functional brain networks. Front Neurosci, 10:326, July 2016. →pages 57, 6079[61] F. De Vico Fallani, J. Richiardi, M. Chavez, and S. Achard. Graph analysisof functional brain networks: practical issues in translational neuroscience.Philos Trans R Soc Lond B Biol Sci, 369(1653), Oct. 2014. → page 57[62] S. Dey. Securing majority-attack in blockchain using machine learning andalgorithmic game theory: A proof of work. In 2018 10th computer scienceand electronic engineering (CEEC), pages 7–10. IEEE, 2018. → page 3[63] K. Ding, J. Li, R. Bhanushali, and H. Liu. Deep anomaly detection onattributed networks. In Proceedings of the 2019 SIAM InternationalConference on Data Mining, pages 594–602. SIAM, 2019. → page 1[64] K. Ding, Q. Zhou, H. Tong, and H. Liu. Few-shot network anomalydetection via cross-network meta-learning. In Proceedings of the WebConference 2021, WWW ’21, page 2448–2456, New York, NY, USA, 2021.Association for Computing Machinery. ISBN 9781450383127.doi:10.1145/3442381.3449922. URLhttps://doi.org/10.1145/3442381.3449922. → page 1[65] D. Eswaran and C. Faloutsos. Sedanspot: Detecting anomalies in edgestreams. In 2018 IEEE International conference on data mining (ICDM),pages 953–958. IEEE, 2018. → pages 1, 14[66] D. Eswaran, C. Faloutsos, S. Guha, and N. Mishra. Spotlight: Detectinganomalies in streaming graphs. In Proceedings of the 24th ACM SIGKDDInternational Conference on Knowledge Discovery & Data Mining, pages1378–1386, 2018. → pages 1, 14[67] J. Fan, B. D. McCandliss, J. Fossella, J. I. Flombaum, and M. I. Posner. Theactivation of attentional networks. Neuroimage, 26(2):471–479, 2005. →page 60[68] A. Farhangfar, R. Greiner, and M. Zinkevich. A fast way to producenear-optimal fixed-depth decision trees. In Proceedings of the 10thInternational Symposium on Artificial Intelligence and Mathematics(ISAIM-2008), 2008. → page 11[69] E. S. Finn, X. Shen, D. Scheinost, M. D. Rosenberg, J. Huang, M. M. Chun,X. Papademetris, and R. T. Constable. Functional connectome fingerprinting:identifying individuals using patterns of brain connectivity. NatureNeuroscience, 18(11):1664–1671, Nov 2015. ISSN 1546-1726.doi:10.1038/nn.4135. URL https://doi.org/10.1038/nn.4135. → page 5480[70] F. Fusco, D. Pascual, and P. Staar. pnlp-mixer: an efficient all-mlparchitecture for language. arXiv preprint arXiv:2202.04350, 2022. → page11[71] E. Galimberti, F. Bonchi, F. Gullo, and T. Lanciano. Core decomposition inmultilayer networks: Theory, algorithms, and applications. ACM Trans.Knowl. Discov. Data, 14(1), 2020. ISSN 1556-4681. doi:10.1145/3369872.→ page 2[72] J. Gao and B. Ribeiro. On the equivalence between temporal and staticequivariant graph representations. In K. Chaudhuri, S. Jegelka, L. Song,C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39thInternational Conference on Machine Learning, volume 162 of Proceedingsof Machine Learning Research, pages 7052–7076. PMLR, 17–23 Jul 2022.URL https://proceedings.mlr.press/v162/gao22e.html. → page 15[73] Z. Gao, C. Jiang, J. Zhang, X. Jiang, L. Li, P. Zhao, H. Yang, Y. Huang, andJ. Li. Hierarchical graph learning for protein–protein interaction. NatureCommunications, 14(1):1093, 2023. → page 55[74] K. R. Griffiths, T. A. Braund, M. R. Kohn, S. Clarke, L. M. Williams, andM. S. Korgaonkar. Structural brain network topology underpinning adhd andresponse to methylphenidate treatment. Translational Psychiatry, 11(1):150,Mar 2021. ISSN 2158-3188. doi:10.1038/s41398-021-01278-x. URLhttps://doi.org/10.1038/s41398-021-01278-x. → page 31[75] O. Günlük, J. Kalagnanam, M. Li, M. Menickelly, and K. Scheinberg.Optimal decision trees for categorical data via integer programming. Journalof Global Optimization, pages 1–28, 2021. → page 11[76] Y. Guo and C. Liang. Blockchain application and outlook in the bankingindustry. Financial innovation, 2(1):1–12, 2016. → page 3[77] X. Han, T. F. J. Pasquier, A. Bates, J. Mickens, and M. I. Seltzer. Unicorn:Runtime provenance-based detector for advanced persistent threats. In 27thAnnual Network and Distributed System Security Symposium, NDSS 2020,San Diego, California, USA, February 23-26, 2020. The Internet Society,2020. URL https://www.ndss-symposium.org/ndss-paper/unicorn-runtime-provenance-based-detector-for-advanced-persistent-threats/.→ page 1[78] O. Hanteer, L. Rossi, D. V. D’Aurelio, and M. Magnani. From interaction toparticipation: The role of the imagined audience in social media community81detection and an application to political communication on twitter. InProceedings of the 2018 IEEE/ACM International Conference on Advancesin Social Networks Analysis and Mining, ASONAM ’18, page 531–534.IEEE Press, 2018. ISBN 9781538660515. → pages 25, 26[79] F. Hashemi, A. Behrouz, and L. V. Lakshmanan. Firmcore decomposition ofmultilayer networks. In Proceedings of the ACM Web Conference 2022,WWW ’22, page 1589–1600, New York, NY, USA, 2022. Association forComputing Machinery. ISBN 9781450390965.doi:10.1145/3485447.3512205. URLhttps://doi.org/10.1145/3485447.3512205. → page 2[80] F. Hashemi, A. Behrouz, and M. R. Hajidehi. Cs-tgn: Community search viatemporal graph neural networks. In Companion Proceedings of the WebConference 2023, WWW ’23, New York, NY, USA, 2023. Association forComputing Machinery. doi:10.1145/3543873.3587654. URLhttps://doi.org/10.1145/3543873.3587654. → pages 13, 15[81] M. U. Hassan, M. H. Rehmani, and J. Chen. Anomaly detection inblockchain networks: A comprehensive survey. IEEE CommunicationsSurveys & Tutorials, 2022. → page 3[82] R. He and J. McAuley. Ups and downs: Modeling the visual evolution offashion trends with one-class collaborative filtering. In proceedings of the25th international conference on world wide web, pages 507–517, 2016. →pages 25, 26[83] N. A. Heard, D. J. Weston, K. Platanioti, and D. J. Hand. Bayesian anomalydetection methods for social networks. The Annals of Applied Statistics, 4(2):645–662, 2010. → page 14[84] D. Hendrycks and K. Gimpel. Gaussian error linear units (gelus), 2020. →pages 11, 43[85] B. Hooi, H. A. Song, A. Beutel, N. Shah, K. Shin, and C. Faloutsos. Fraudar:Bounding graph fraud in the face of camouflage. In Proceedings of the 22ndACM SIGKDD international conference on knowledge discovery and datamining, pages 895–904, 2016. → page 14[86] B. Jie, M. Liu, X. Jiang, and D. Zhang. Sub-network based kernels for brainnetwork classification. In Proceedings of the 7th ACM InternationalConference on Bioinformatics, Computational Biology, and HealthInformatics, pages 622–629, 2016. → page 5682[87] M. Jin, Y. Liu, Y. Zheng, L. Chi, Y.-F. Li, and S. Pan. Anemone: Graphanomaly detection with multi-scale contrastive learning. In Proceedings ofthe 30th ACM International Conference on Information & KnowledgeManagement, CIKM ’21, page 3122–3126, New York, NY, USA, 2021.Association for Computing Machinery. ISBN 9781450384469.doi:10.1145/3459637.3482057. URLhttps://doi.org/10.1145/3459637.3482057. → page 14[88] M. Jin, Y.-F. Li, and S. Pan. Neural temporal walks: Motif-awarerepresentation learning on continuous-time dynamic graphs. In A. H. Oh,A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in NeuralInformation Processing Systems, 2022. URLhttps://openreview.net/forum?id=NqbktPUkZf7. → pages 15, 37, 39, 61[89] B. Jing, C. Park, and H. Tong. Hdmi: High-order deep multiplex infomax.In Proceedings of the Web Conference 2021, pages 2414–2424, 2021. →page 16[90] A. Kafshdar Goharshady, A. Behrouz, and K. Chatteriee. Secure creditreporting on the blockchain. In 2018 IEEE International Conference onInternet of Things (iThings) and IEEE Green Computing andCommunications (GreenCom) and IEEE Cyber, Physical and SocialComputing (CPSCom) and IEEE Smart Data (SmartData), pages1343–1348, 2018. doi:10.1109/Cybermatics_2018.2018.00231. → page 3[91] X. Kan, H. Cui, Y. Guo, and C. Yang. Effective and interpretable fmrianalysis via functional brain network generation. arXiv preprintarXiv:2107.11247, 2021. → page 56[92] X. Kan, H. Cui, J. Lukemire, Y. Guo, and C. Yang. Fbnetgen: Task-awaregnn-based fmri analysis via functional brain network generation. arXivpreprint arXiv:2205.12465, 2022. → page 56[93] X. Kan, H. Cui, J. Lukemire, Y. Guo, and C. Yang. FBNETGEN:Task-aware GNN-based fMRI analysis via functional brain networkgeneration. In Medical Imaging with Deep Learning, 2022. URLhttps://openreview.net/forum?id=oWFphg2IKon. → page 58[94] X. Kan, W. Dai, H. Cui, Z. Zhang, Y. Guo, and C. Yang. Brain networktransformer. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors,Advances in Neural Information Processing Systems, 2022. URLhttps://openreview.net/forum?id=1cJ1cbA6NLN. → page 5583[95] S. M. Kazemi, R. Goel, S. Eghbali, J. Ramanan, J. Sahota, S. Thakur, S. Wu,C. Smyth, P. Poupart, and M. Brubaker. Time2vec: Learning a vectorrepresentation of time. arXiv preprint arXiv:1907.05321, 2019. → page 40[96] P. Kidger, J. Morrill, J. Foster, and T. Lyons. Neural controlled differentialequations for irregular time series. Advances in Neural InformationProcessing Systems, 33:6696–6707, 2020. → pages 3, 40[97] J. Kim and J.-G. Lee. Community detection in multi-layer graphs: A survey.SIGMOD Rec., 44(3):37–48, dec 2015. ISSN 0163-5808.doi:10.1145/2854006.2854013. URLhttps://doi.org/10.1145/2854006.2854013. → page 25[98] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A.Porter. Multilayer networks. Journal of Complex Networks, 2(3):203–271,07 2014. ISSN 2051-1310. doi:10.1093/comnet/cnu016. → pages 1, 16, 55[99] A. R. Klivans, R. A. Servedio, and D. Ron. Toward attribute efficientlearning of decision lists and parities. Journal of Machine LearningResearch, 7(4), 2006. → page 11[100] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, andV. Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. InProceedings of the Eleventh ACM International Conference on Web Searchand Data Mining, pages 333–341, 2018. → pages 25, 27[101] T. Lanciano, F. Bonchi, and A. Gionis. Explainable classification of brainnetworks via contrast subgraphs. In Proceedings of the 26th ACM SIGKDDInternational Conference on Knowledge Discovery; Data Mining, KDD ’20,page 3308–3318, New York, NY, USA, 2020. Association for ComputingMachinery. ISBN 9781450379984. doi:10.1145/3394486.3403383. URLhttps://doi.org/10.1145/3394486.3403383. → pages 3, 31, 57, 58, 66[102] H. Laurent and R. L. Rivest. Constructing optimal binary decision trees isnp-complete. Information Processing Letters, 5(1):15–17, 1976. → page 11[103] D. Lei, J. Ma, X. Du, G. Shen, X. Jin, and Q. Gong. Microstructuralabnormalities in the combined and inattentive subtypes of attention deficithyperactivity disorder: a diffusion tensor imaging study. Scientific reports, 4(1):6875, 2014. → page 68[104] G. Li, M. Muller, A. Thabet, and B. Ghanem. Deepgcns: Can gcns go asdeep as cnns? In Proceedings of the IEEE/CVF international conference oncomputer vision, pages 9267–9276, 2019. → pages 10, 2184[105] J. Li, Z. Han, H. Cheng, J. Su, P. Wang, J. Zhang, and L. Pan. Predictingpath failure in time-evolving graphs. In Proceedings of the 25th ACMSIGKDD International Conference on Knowledge Discovery & Data Mining,pages 1279–1289, 2019. → page 15[106] Y. Li, R. Yu, C. Shahabi, and Y. Liu. Diffusion convolutional recurrentneural network: Data-driven traffic forecasting. In International Conferenceon Learning Representations, 2018. URLhttps://openreview.net/forum?id=SJiHXGWAZ. → page 15[107] J. Lin, C. Zhong, D. Hu, C. Rudin, and M. Seltzer. Generalized and scalableoptimal sparse decision trees. In International Conference on MachineLearning (ICML), pages 6150–6160, 2020. → page 12[108] J. Liu, M. Li, Y. Pan, W. Lan, R. Zheng, F.-X. Wu, and J. Wang. Complexbrain network analysis and its applications to brain disorders: A survey.Complexity, 2017:8362741, Oct 2017. ISSN 1076-2787.doi:10.1155/2017/8362741. URL https://doi.org/10.1155/2017/8362741. →page 57[109] J. Liu, W. Zhao, Y. Hong, S. Gao, X. Huang, Y. Zhou, A. D. N. Initiative,et al. Learning features of brain network for anomaly detection. In IEEEINFOCOM 2020-IEEE Conference on Computer CommunicationsWorkshops (INFOCOM WKSHPS), pages 900–905. IEEE, 2020. → pages13, 56, 57[110] N. Liu, X. Huang, and X. Hu. Accelerated local anomaly detection viaresolving attributed networks. In Proceedings of the Twenty-SixthInternational Joint Conference on Artificial Intelligence, IJCAI-17, pages2337–2343, 2017. doi:10.24963/ijcai.2017/325. URLhttps://doi.org/10.24963/ijcai.2017/325. → page 1[111] Y. Liu, S. Pan, Y. G. Wang, F. Xiong, L. Wang, Q. Chen, and V. C. Lee.Anomaly detection in dynamic graphs via transformer. IEEE Transactionson Knowledge and Data Engineering, pages 1–1, 2021.doi:10.1109/TKDE.2021.3124061. → page 14[112] S. Lloyd. Least squares quantization in pcm. IEEE transactions oninformation theory, 28(2):129–137, 1982. → page 45[113] Y. Luo and P. Li. Neighborhood-aware scalable temporal networkrepresentation learning. In The First Learning on Graphs Conference, 2022.URL https://openreview.net/forum?id=EPUtNe7a9ta. → page 1585[114] C. W. Lynn and D. S. Bassett. The physics of brain network structure,function and control. Nature Reviews Physics, 1(5):318–332, May 2019.ISSN 2522-5820. doi:10.1038/s42254-019-0040-8. URLhttps://doi.org/10.1038/s42254-019-0040-8. → page 57[115] X. Ma, J. Wu, S. Xue, J. Yang, C. Zhou, Q. Z. Sheng, H. Xiong, andL. Akoglu. A comprehensive survey on graph anomaly detection with deeplearning. IEEE Transactions on Knowledge and Data Engineering, pages1–1, 2021. doi:10.1109/TKDE.2021.3118815. → pages 1, 3, 14, 19[116] D. D. F. Maesa, A. Marino, and L. Ricci. Detecting artificial behaviours inthe bitcoin users graph. Online Social Networks and Media, 3:63–74, 2017.→ page 3[117] M. Mardani, G. Mateos, and G. B. Giannakis. Dynamic anomalography:Tracking network anomalies via sparsity and low rank. IEEE Journal ofSelected Topics in Signal Processing, 7(1):50–66, 2012. → page 14[118] R. Marinescu, A. Eshaghi, D. Alexander, and P. Golland. Brainpainter: Asoftware for the visualisation of brain structures, biomarkers and associatedpathological processes. arXiv preprint arXiv:1905.08627, 2019. → page 59[119] A. Maulana and M. Atzmueller. Centrality-based anomaly detection onmulti-layer networks using many-objective optimization. In 2020 7thInternational Conference on Control, Decision and InformationTechnologies (CoDIT), volume 1, pages 633–638, 2020.doi:10.1109/CoDIT49905.2020.9263819. → page 17[120] H. McTavish, C. Zhong, R. Achermann, I. Karimalis, J. Chen, C. Rudin, andM. Seltzer. Fast sparse decision tree optimization via reference ensembles.In AAAI Conference on Artificial Intelligence, volume 36, 2022. → page 12[121] S. Micali and Z. A. Zhu. Reconstructing markov processes fromindependent and anonymous experiments. Discrete Applied Mathematics,200:108–122, 2016. → page 39[122] R. Mittal and M. Bhatia. Anomaly detection in multiplex networks.Procedia Computer Science, 125:609–616, 2018. → page 16[123] B. Mišic´ and O. Sporns. From regions to connections and networks: newbridges between brain and behavior. Current Opinion in Neurobiology, 40:1–7, 2016. ISSN 0959-4388. doi:https://doi.org/10.1016/j.conb.2016.05.003.URL86https://www.sciencedirect.com/science/article/pii/S095943881630054X.Systems neuroscience. → page 54[124] R.-A. Müller and A. Linke. Functional connectivity in autism spectrumdisorders: Challenges and perspectives. Brain Network Dysfunction inNeuropsychiatric Illness: Methods, Applications, and Implications, pages239–272, 2021. → page 69[125] D. Nelson. Crypto criminals have already stolen $1.4b in 2020, saysciphertrace, June 2020. URL https://www.coindesk.com/policy/2020/06/02/crypto-criminals-have-already-stolen-14b-in-2020-says-ciphertrace/. →page 3[126] S. Nijssen and E. Fromont. Mining optimal decision trees from itemsetlattices. In 13th ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining, pages 530–539, 2007. → page 11[127] D. Ofori-Boateng, I. S. Dominguez, C. Akcora, M. Kantarcioglu, and Y. R.Gel. Topological anomaly detection in dynamic multilayer blockchainnetworks. In Joint European Conference on Machine Learning andKnowledge Discovery in Databases, pages 788–804. Springer, 2021. →pages 3, 17, 25, 26[128] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi,T. Kaler, T. Schardl, and C. Leiserson. Evolvegcn: Evolving graphconvolutional networks for dynamic graphs. In Proceedings of the AAAIConference on Artificial Intelligence, volume 34, pages 5363–5370, 2020.→ page 15[129] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, H. Kanezashi,T. Kaler, T. Schardl, and C. Leiserson. Evolvegcn: Evolving graphconvolutional networks for dynamic graphs. In Proceedings of the AAAIconference on artificial intelligence, volume 34, pages 5363–5370, 2020. →page 61[130] C. Park, D. Kim, J. Han, and H. Yu. Unsupervised attributed multiplexnetwork embedding. In Proceedings of the AAAI Conference on ArtificialIntelligence, volume 34, pages 5371–5378, 2020. → pages 16, 22, 37[131] L. Peel and A. Clauset. Detecting change points in the large-scale structureof evolving networks. In Twenty-Ninth AAAI Conference on ArtificialIntelligence, 2015. → page 1487[132] H. Peng, H. Wang, B. Du, M. Z. A. Bhuiyan, H. Ma, J. Liu, L. Wang,Z. Yang, L. Du, S. Wang, et al. Spatial temporal incidence dynamic graphneural networks for traffic flow forecasting. Information Sciences, 521:277–290, 2020. → page 15[133] Z. Peng, M. Luo, J. Li, H. Liu, and Q. Zheng. Anomalous: A joint modelingapproach for anomaly detection on attributed networks. In Proceedings ofthe Twenty-Seventh International Joint Conference on Artificial Intelligence,IJCAI-18, pages 3513–3519. International Joint Conferences on ArtificialIntelligence Organization, 7 2018. doi:10.24963/ijcai.2018/488. URLhttps://doi.org/10.24963/ijcai.2018/488. → page 1[134] Z. Peng, M. Luo, J. Li, L. Xue, and Q. Zheng. A deep multi-view frameworkfor anomaly detection on attributed networks. IEEE Transactions onKnowledge and Data Engineering, 34(6):2539–2552, 2022.doi:10.1109/TKDE.2020.3015098. → page 1[135] T. Pham and S. Lee. Anomaly detection in bitcoin network usingunsupervised learning methods. arXiv preprint arXiv:1611.03941, 2016. →page 3[136] L. Pio-Lopez, A. Valdeolivas, L. Tichit, É. Remy, and A. Baudot. Multiverse:a multiplex and multiplex-heterogeneous network embedding approach.Scientific Reports, 11(1):1–20, 2021. → pages 15, 16[137] B. Podgorelec, M. Turkanovic´, and S. Karakaticˇ. A machine learning-basedmethod for automated blockchain transaction signing including personalizedanomaly detection. Sensors, 20(1):147, 2019. → page 3[138] F. Poursafaei, A. Huang, K. Pelrine, and R. Rabbany. Towards betterevaluation for dynamic link prediction. In Thirty-sixth Conference on NeuralInformation Processing Systems Datasets and Benchmarks Track, 2022.URL https://openreview.net/forum?id=1GVpwr2Tfdg. → pages 35, 43[139] J. D. Power, A. L. Cohen, S. M. Nelson, G. S. Wig, K. A. Barnes, J. A.Church, A. C. Vogel, T. O. Laumann, F. M. Miezin, B. L. Schlaggar, andS. E. Petersen. Functional network organization of the human brain. Neuron,72(4):665–678, Nov 2011. ISSN 1097-4199.doi:10.1016/j.neuron.2011.09.006. URLhttps://pubmed.ncbi.nlm.nih.gov/22099467. S0896-6273(11)00792-6[PII].→ page 388[140] M. G. Preti, T. A. Bolton, and D. Van De Ville. The dynamic functionalconnectome: State-of-the-art and perspectives. Neuroimage, 160:41–54,2017. → pages 54, 55[141] S. Ranshous, S. Shen, D. Koutra, S. Harenberg, C. Faloutsos, and N. F.Samatova. Anomaly detection in dynamic networks: A survey. WIREsComput. Stat., 7(3):223–247, may 2015. ISSN 1939-5108.doi:10.1002/wics.1347. URL https://doi.org/10.1002/wics.1347. → pages1, 3, 19[142] S. Ranshous, S. Harenberg, K. Sharma, and N. F. Samatova. A scalableapproach for outlier detection in edge streams using sketch-basedapproximations. In Proceedings of the 2016 SIAM international conferenceon data mining, pages 189–197. SIAM, 2016. → pages 2, 14, 27[143] T. D. Rogers, E. McKimm, P. E. Dickson, D. Goldowitz, C. D. Blaha, andG. Mittleman. Is autism a disease of the cerebellum? an integration ofclinical and pre-clinical research. Front Syst Neurosci, 7:15, May 2013. →page 69[144] C. Rudin, C. Chen, Z. Chen, H. Huang, L. Semenova, and C. Zhong.Interpretable machine learning: Fundamental principles and 10 grandchallenges. Statistics Surveys, 16:1–85, 2022. → page 11[145] D. A. Seminowicz and K. D. Davis. Pain enhances functional connectivityof a brain network evoked by performance of a cognitive task. Journal ofneurophysiology, 97(5):3651–3659, 2007. → page 13[146] Y. Seo, M. Defferrard, P. Vandergheynst, and X. Bresson. Structuredsequence modeling with graph convolutional recurrent networks. InInternational conference on neural information processing, pages 362–373.Springer, 2018. → page 15[147] J. Sun, D. Tao, and C. Faloutsos. Beyond streams and graphs: dynamictensor analysis. In Proceedings of the 12th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages 374–383, 2006.→ page 14[148] J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is more: Compact matrixdecomposition for large sparse graphs. In Proceedings of the 2007 SIAMInternational Conference on Data Mining, pages 366–377. SIAM, 2007. →page 1489[149] A. Taheri, K. Gimpel, and T. Berger-Wolf. Learning to represent theevolution of dynamic graphs with recurrent models. In Companionproceedings of the 2019 world wide web conference, pages 301–307, 2019.→ page 15[150] X. Teng, Y.-R. Lin, and X. Wen. Anomaly detection in dynamic networksusing multi-view time-series hypersphere learning. In Proceedings of the2017 ACM on Conference on Information and Knowledge Management,pages 827–836, 2017. → page 14[151] I. Tolstikhin, N. Houlsby, A. Kolesnikov, L. Beyer, X. Zhai, T. Unterthiner,J. Yung, A. P. Steiner, D. Keysers, J. Uszkoreit, M. Lucic, andA. Dosovitskiy. MLP-mixer: An all-MLP architecture for vision. InA. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advancesin Neural Information Processing Systems, 2021. URLhttps://openreview.net/forum?id=EI2KOXKdnP. → pages 11, 43[152] M. P. Van Den Heuvel and H. E. H. Pol. Exploring the brain network: areview on resting-state fmri functional connectivity. Europeanneuropsychopharmacology, 20(8):519–534, 2010. → page 13[153] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez,Ł. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neuralinformation processing systems, 30, 2017. → page 11[154] P. Velicˇkovic´, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.Graph attention networks. In International Conference on LearningRepresentations, 2018. URL https://openreview.net/forum?id=rJXMpikCZ.→ pages 59, 61[155] P. Velicˇkovic´, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm.Deep graph infomax. In International Conference on LearningRepresentations, 2019. URL https://openreview.net/forum?id=rklz9iAcKQ.→ page 16[156] H. Wang, M. Tang, Y. Park, and C. E. Priebe. Locality statistics for anomalydetection in time series of graphs. IEEE Transactions on Signal Processing,62(3):703–717, 2013. → page 14[157] J. Wang, R. Wen, C. Wu, Y. Huang, and J. Xiong. Fdgars: Fraudsterdetection via graph convolutional networks in online app review system. InCompanion Proceedings of The 2019 World Wide Web Conference, WWW’19, page 310–316, New York, NY, USA, 2019. Association for Computing90Machinery. ISBN 9781450366755. doi:10.1145/3308560.3316586. URLhttps://doi.org/10.1145/3308560.3316586. → page 1[158] J.-z. Wang, T.-z. Jiang, Q.-j. Cao, and Y. Wang. Characterizing anatomicdifferences in boys with attention-deficit/hyperactivity disorder with the useof deformation-based morphometry. American Journal of Neuroradiology,28(3):543–547, 2007. → pages 32, 68[159] Q. Wang, Y. Fang, A. Ravula, R. He, B. Shen, J. Wang, X. Quan, and D. Liu.Deep partial multiplex network embedding. In Companion Proceedings ofthe Web Conference 2022, WWW ’22, page 1053–1062, New York, NY,USA, 2022. Association for Computing Machinery. ISBN 9781450391306.doi:10.1145/3487553.3524717. URLhttps://doi.org/10.1145/3487553.3524717. → page 16[160] T. Wang, C. Fang, D. Lin, and S. F. Wu. Localizing temporal anomalies inlarge evolving graphs. In Proceedings of the 2015 SIAM InternationalConference on Data Mining, pages 927–935. SIAM, 2015. → pages 2, 14[161] X. Wang, Y. Lu, C. Shi, R. Wang, P. Cui, and S. Mou. Dynamicheterogeneous information network embedding with meta-path basedproximity. IEEE Transactions on Knowledge and Data Engineering, 2020.→ page 16[162] X. Wang, Y. Ma, Y. Wang, W. Jin, X. Wang, J. Tang, C. Jia, and J. Yu. Trafficflow prediction via spatial temporal graph neural network. In Proceedings ofThe Web Conference 2020, pages 1082–1092, 2020. → page 15[163] Y. Wang, Y.-Y. Chang, Y. Liu, J. Leskovec, and P. Li. Inductiverepresentation learning in temporal networks via causal anonymous walks.In International Conference on Learning Representations, 2021. URLhttps://openreview.net/forum?id=KYPz4YsCPj. → pages15, 37, 38, 39, 40, 61, 62[164] Z. Wang, J. Zhang, J. Feng, and Z. Chen. Knowledge graph embedding bytranslating on hyperplanes. In Proceedings of the AAAI conference onartificial intelligence, volume 28, 2014. → page 23[165] C.-Y. Wee, P.-T. Yap, W. Li, K. Denny, J. N. Browndyke, G. G. Potter, K. A.Welsh-Bohmer, L. Wang, and D. Shen. Enriched white matter connectivitynetworks for accurate identification of mci patients. Neuroimage, 54(3):1812–1822, 2011. → page 5691[166] Y. Xie, Z. Ou, L. Chen, Y. Liu, K. Xu, C. Yang, and Z. Zheng. Learning andupdating node embedding on dynamic heterogeneous information network.In Proceedings of the 14th ACM International Conference on Web Searchand Data Mining, WSDM ’21, page 184–192, New York, NY, USA, 2021.Association for Computing Machinery. ISBN 9781450382977.doi:10.1145/3437963.3441745. URLhttps://doi.org/10.1145/3437963.3441745. → page 16[167] Z. Xiong, D. Wang, X. Liu, F. Zhong, X. Wan, X. Li, Z. Li, X. Luo, K. Chen,H. Jiang, et al. Pushing the boundaries of molecular representation for drugdiscovery with the graph attention mechanism. Journal of medicinalchemistry, 63(16):8749–8760, 2019. → page 55[168] H. Yan, Q. Zhang, D. Mao, Z. Lu, D. Guo, and S. Chen. Anomaly detectionof network streams via dense subgraph discovery. In 2021 InternationalConference on Computer Communications and Networks (ICCCN), pages1–9. IEEE, 2021. → page 14[169] Y. Yan, S. Zhang, and H. Tong. Bright: A bridging algorithm for networkalignment. In Proceedings of the Web Conference 2021, pages 3907–3917,2021. → pages 15, 16[170] C. Yang, Y. Xiao, Y. Zhang, Y. Sun, and J. Han. Heterogeneous networkrepresentation learning: Survey, benchmark, evaluation, and beyond. CoRR,abs/2004.00216, 2020. URL https://arxiv.org/abs/2004.00216. → page 16[171] C. Yang, C. Wang, Y. Lu, X. Gong, C. Shi, W. Wang, and X. Zhang.Few-shot link prediction in dynamic networks. In Proceedings of theFifteenth ACM International Conference on Web Search and Data Mining,pages 1245–1255, 2022. → page 15[172] M. Yoon, B. Hooi, K. Shin, and C. Faloutsos. Fast and accurate anomalydetection in dynamic graphs with a two-pronged approach. In Proceedingsof the 25th ACM SIGKDD International Conference on KnowledgeDiscovery & Data Mining, pages 647–657, 2019. → page 14[173] J. You, R. Ying, and J. Leskovec. Design space for graph neural networks.In NeurIPS, 2020. → page 25[174] J. You, T. Du, and J. Leskovec. Roland: Graph learning framework fordynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference onKnowledge Discovery and Data Mining, KDD ’22, page 2358–2366, NewYork, NY, USA, 2022. Association for Computing Machinery. ISBN929781450393850. doi:10.1145/3534678.3539300. URLhttps://doi.org/10.1145/3534678.3539300. → pages 15, 18, 21[175] H. Yousaf, G. Kappos, and S. Meiklejohn. Tracing transactions acrosscryptocurrency ledgers. In 28th USENIX Security Symposium (USENIXSecurity 19), pages 837–850, 2019. → page 3[176] B. Yu, H. Yin, and Z. Zhu. Spatio-temporal graph convolutional networks: Adeep learning framework for traffic forecasting. In IJCAI, pages 3634–3640,2018. URL https://doi.org/10.24963/ijcai.2018/505. → page 15[177] T. Yu, X. Li, Y. Cai, M. Sun, and P. Li. S2-mlp: Spatial-shift mlparchitecture for vision. In Proceedings of the IEEE/CVF winter conferenceon applications of computer vision, pages 297–306, 2022. → page 11[178] W. Yu, C. C. Aggarwal, S. Ma, and H. Wang. On anomalous hotspotdiscovery in graph streams. In 2013 IEEE 13th International Conference onData Mining, pages 1271–1276. IEEE, 2013. → page 14[179] W. Yu, C. C. Aggarwal, and W. Wang. Temporally factorized networkmodeling for evolutionary network analysis. In Proceedings of the TenthACM International conference on web search and data mining, pages455–464, 2017. → page 14[180] W. Yu, W. Cheng, C. C. Aggarwal, K. Zhang, H. Chen, and W. Wang.Netwalk: A flexible deep embedding approach for anomaly detection indynamic networks. In Proceedings of the 24th ACM SIGKDD InternationalConference on Knowledge Discovery & Data Mining, KDD ’18, page2672–2681, New York, NY, USA, 2018. Association for ComputingMachinery. ISBN 9781450355520. doi:10.1145/3219819.3220024. URLhttps://doi.org/10.1145/3219819.3220024. → pages 1, 2, 14, 27, 28[181] X. Zhai, W. Zhou, G. Fei, W. Liu, Z. Xu, C. Jiao, C. Lu, and G. Hu. Nullmodel and community structure in multiplex networks. Scientific reports, 8(1):1–13, 2018. → page 27[182] C. Zhang, H. Fu, Q. Hu, X. Cao, Y. Xie, D. Tao, and D. Xu. Generalizedlatent multi-view subspace clustering. IEEE transactions on pattern analysisand machine intelligence, 42(1):86–99, 2018. → pages 15, 16[183] H. Zhang, L. Qiu, L. Yi, and Y. Song. Scalable multiplex networkembedding. In Proceedings of the Twenty-Seventh International JointConference on Artificial Intelligence, IJCAI-18, pages 3082–3088.93International Joint Conferences on Artificial Intelligence Organization, 72018. doi:10.24963/ijcai.2018/428. URLhttps://doi.org/10.24963/ijcai.2018/428. → pages 16, 28[184] J. Zhang, B. Cao, S. Xie, C.-T. Lu, P. S. Yu, and A. B. Ragin. Identifyingconnectivity patterns for brain diseases via multi-side-view guided deeparchitectures. In Proceedings of the 2016 SIAM International Conference onData Mining, pages 36–44. SIAM, 2016. → page 56[185] R.-Y. Zhang, X.-X. Wei, and K. Kay. Understanding multivariate brainactivity: Evaluating the effect of voxelwise noise correlations on populationcodes in functional magnetic resonance imaging. PLOS ComputationalBiology, 16(8):1–29, 08 2020. doi:10.1371/journal.pcbi.1008153. URLhttps://doi.org/10.1371/journal.pcbi.1008153. → pages 3, 55, 57, 58, 66[186] X. Zhang, L. He, K. Chen, Y. Luo, J. Zhou, and F. Wang. Multi-View graphconvolutional network and its applications on neuroimage analysis forparkinson’s disease. AMIA Annu Symp Proc, 2018:1147–1156, Dec. 2018.→ pages 55, 57, 58[187] L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, and H. Li.T-gcn: A temporal graph convolutional network for traffic prediction. IEEETransactions on Intelligent Transportation Systems, 21(9):3848–3858, 2019.→ page 15[188] L. Zheng, Z. Li, J. Li, Z. Li, and J. Gao. Addgraph: Anomaly detection indynamic graph using attention-based temporal gcn. In Proceedings of theTwenty-Eighth International Joint Conference on Artificial Intelligence,IJCAI-19, pages 4419–4425. International Joint Conferences on ArtificialIntelligence Organization, 7 2019. doi:10.24963/ijcai.2019/614. URLhttps://doi.org/10.24963/ijcai.2019/614. → pages 1, 2, 14, 23, 27, 28, 43, 44[189] Y. Zheng, M. Jin, Y. Liu, L. Chi, K. T. Phan, and Y.-P. P. Chen. Generativeand contrastive self-supervised learning for graph anomaly detection. IEEETransactions on Knowledge and Data Engineering, 2021. → page 14[190] Y. Zhu, H. Cui, L. He, L. Sun, and C. Yang. Joint embedding of structuraland functional brain networks with graph neural networks for mental illnessdiagnosis. In 2022 44th Annual International Conference of the IEEEEngineering in Medicine & Biology Society (EMBC), pages 272–276. IEEE,2022. → pages 55, 5694[191] Y. Zhu, H. Cui, L. He, L. Sun, and C. Yang. Joint embedding of structuraland functional brain networks with graph neural networks for mental illnessdiagnosis, 2022. → pages 12, 55, 57, 5895Appendix ASupporting MaterialsA.1 Performance of the Modified Attention on GeneralDatasetsIn Section 4.2.3, we define a complex attention mechanism that can learn the impor-tance of each view for each node, while in Section 6.4, we design a more scalablemechanism that considers the importance of a view for other views, independentof the nodes. We discuss its advantages for brain networks in Section 6.4 and6.5 but its performance on general multiplex networks remains unexplored. Here,we explore its performance for general multiplex networks (different domains).Table A.1 reports the results. ANOMULY and ADMIRE uses the complex attentionmechanism we proposed in Section 4.2.3, while ANOMULY-v2 and ADMIRE-v2uses the scalable attention mechanism that proposed in Section 6.4. The results showthe superior performance of the complex attention mechanism. As motivated inSection 6.4, the modified attention mechanism is useful for improving the scalabilityin the domain of human brain networks.96Table A.1: Performance of the modified attention on general datasets (AUC).Methods RM DKPol Amazon DBLP Ethereum RippleAnomaly % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 % 1% 5 %ANOMULY 0.8783 0.8729 0.8694 0.8610 0.8289 0.8195 0.8825 0.8754 0.8906 0.8852 0.8938 0.8871ADMIRE 0.9016 0.9125 0.9093 0.8952 0.8097 0.8041 0.8873 0.8824 0.8416 0.8392 0.9160 0.8899ANOMULY-v2 0.8416 0.8387 0.8502 0.8439 0.7990 0.8021 0.8235 0.7992 0.8421 0.8399 0.8562 0.8286ADMIRE-v2 0.8912 0.8841 0.8498 0.8515 0.7975 0.7926 0.8129 0.7953 0.8478 0.8257 0.0000 0.000097
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Seltzer, Margo
Anomaly detection in multiplex networks : from human brain activity to financial networks
Text