Resilience has emerged as a crucial and desirable characteristic of complex systems due to the increasing frequency of cyber intrusions and natural disasters. In systems such as power grids and transportation networks, resilience analysis typically deals with the assessment of system robustness in terms of identifying and safeguarding key system attributes. Robustness evaluation methods can be broadly classified into two types, namely network-based and performance-based. Network-based methodologies involve topological properties of the system, whereas performance-based methods deal with specific performance attributes such as voltage fluctuations in a power distribution network. Existing approaches to evaluate robustness have limitations in terms of (1) inaccurate modeling of the underlying system; (2) high computational complexity; and (3) lack of scalability. This dissertation addresses these challenges by developing computationally efficient frameworks to identify key entities of the system. First, it develops a probabilistic framework for a performance-based robustness attribute. Specifically, using power grid as a case study, this work focuses on the performance measure of interest, i.e., voltage fluctuations. This work first derives an analytical approximation for voltage change at any node of the network due to a change in power at other nodes of a three-phase unbalanced radial distribution network. Next, the probability distribution of voltage changes at a certain node due to random power changes at multiple locations in the network is derived. Then, these distributions with information theoretic metrics are used to derive a novel voltage influencing score (VIS) that quantifies the voltage influencing capacity of nodes with distributed energy resources (DERs) and active loads. VIS is then employed to identify the dominant voltage influencer nodes. Results demonstrate the high efficacy and low computational complexity of the proposed approach, enabling various future applications (e.g., voltage control). In the second part, this dissertation emphasizes on network-based robustness measures. Particularly, it focuses on the task of identifying critical nodes in complex systems so that preemptive actions can be taken to improve the system's resilience. Critical nodes represent a set of sub-systems and/or their interconnections whose removal from the graph maximally disconnects the network, and thus severely disrupts the operation of the system. The majority of the critical node identification methods in literature are based on an iterative approach, and thus suffer from high computational complexity and are not scalable to larger networks. Therefore, this work proposes a scalable and generic graph neural network (GNN) based framework for identifying critical nodes in large complex networks. The proposed framework defines a GNN-based model that learns the node criticality score on a small representative subset of nodes and can identify critical nodes in larger networks. Furthermore, the problem of quantifying the uncertainty in GNN predictions is also considered. Essentially, Assumed Density Filtering is used to quantify aleatoric uncertainty and Monte Carlo dropout captures uncertainty in model parameters. Finally, the two sources of uncertainty are aggregated to estimate the total uncertainty in predictions of a GNN. Results in real-world datasets demonstrate that the Bayesian model performs at par with a frequentist model. Furthermore, the combinatorial case of critical node identification is also addressed in this dissertation, where the node criticality scores would be associated with a set of nodes. This simulates a concurrent scenario where multiple nodes are being disrupted simultaneously. Essentially, this problem falls under the generic category of graph combinatorial problems. This problem is approached through a novel deep reinforcement learning (DRL) based framework. Specifically, GNNs are used for encoding the underlying graph structure and DRL for learning to identify the optimal node sequence. Moreover, the framework is first developed for Influence Maximization (IM), where one is interested in identifying a set of seed nodes, which when activated, will result in the activation of a maximal number of nodes in the graph. This generic framework can be used for various use-cases, including the identification of critical nodes set related to concurrent disruption. The results on real world networks demonstrate the scalability and generalizability of the proposed methodology. Thirdly, this dissertation presents a comparative study of different performance and network-based robustness metrics in terms of ranking critical nodes of a power distribution network. The efficacy of failure-based metrics in characterizing voltage fluctuations is also investigated. Results show that hybrid failure-based metrics can quantify voltage fluctuations to a reasonable extent. Additionally, several other challenges in existing robustness frameworks are highlighted, including the lack of mechanism to effectively incorporate various performance and network-based resilience factors. Then, a novel modeling framework, namely hetero-functional graph theory (HFGT) is leveraged to model both power distribution networks as well as other dependent infrastructure networks. Results demonstrate that HFGT can address key modeling limitations, and can be used to accurately assess system robustness to failures.