One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.

Knowledge compilation is a method of transforming knowledge into a compressed and tractable form for permitting more efficient operations. For Boolean functions, numerous representations have been proposed that enhance succinctness and tractability. In this paper, we introduce a new representation named structured Decomposable And-Sum Circuit (st-DASC), which employs AND and SUM nodes with signed edges, in place of the standard AND and OR nodes with unsigned edges. Notably, incorporating negative signs permits polytime logical negation. By following a knowledge compilation map, we show that st-DASCs are more succinct than Sentential Decision Diagrams (SDDs) while maintaining support for every operation on the knowledge compilation map that SDD supports. Furthermore, st-DASCs are even more succinct than structured d-DNNFs (st-d-DNNFs), which are more succinct than SDDs although they support fewer operations than SDDs. Accordingly, st-DASCs break the traditional trade-off between succinctness and tractability over SDDs and st-d-DNNFs.

A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets.

Evaluating network reliability is crucial for designing communication infrastructures, particularly for such next-generation networks as 6 G, which require extremely high reliability levels, often reaching seven 9's (99.99999 %). However, network reliability evaluation is computationally tough, making it computationally intractable to achieve accurate results for large-scale networks within a reasonable time. Consequently, existing methods either sacrifice computational efficiency or lack guaranteed error bounds. This paper presents an efficient approximation method for network reliability evaluation that guarantees that the approximation error remains within a specified bound. Our proposed method first determines the maximum degree of simultaneous link failures that can be safely ignored without exceeding the bound. With binary decision diagrams, our method efficiently computes both the lower and upper bounds of network reliability. We validate our method through numerical experiments on real-world networks. Our method, which outperformed existing methods by several orders of magnitude, evaluated a network with 434 links in just 7 seconds; an existing method required more than 28 hours.

Modern society is underpinned by several network infrastructures, such as telecommunications and transportation. In these network infrastructures, every node pair should remain connected even if some network components fail. Thus, network operators must accurately evaluate the reliability between each node pair and effectively enhance unreliable pairs. Unfortunately, network reliability evaluation is known to be computationally difficult even for a single pair, and no accurate and efficient algorithm for all pairs has been developed. This paper introduces the problem of 2-NR++, evaluating network reliability for all node pairs, and proposes an efficient and exact algorithm. Unlike the previous algorithms, the proposed algorithm constructs only one data structure to compute the reliability of all node pairs. Numerical evaluation using real network benchmarks shows that our algorithm is faster than the state-of-the-art by an order of magnitude; e.g., our algorithm solves 2-NR++ in less than one hour even for a large network with 240 nodes, whereas the state-of-the-art requires more than one day. As an application of our algorithm, we also introduce a link augmentation problem to improve the least unreliable pair. We demonstrate that our algorithm reduces the computation time by around 30–90 times compared to the state-of-the-art.

As the reliability requirements increase for communication networks, e.g., the seven 9’s reliability for 6G, network operators must evaluate the reliability of their networks more accurately. Since public-communication networks are designed to be less prone to large-scale outages, their (un)reliability should be evaluated per outage scale (the number of disconnected nodes). Traditionally, scale-wise unreliability has been evaluated approximately or requires several hours due to its computational hardness. This paper proposes an efficient algorithm that exactly evaluates scale-wise unreliability by leveraging the given reliability requirements for computation acceleration. We first define a sub-problem that computes the probability of disconnecting x or more nodes and introduce a core algorithm that solves this problem with binary decision diagrams. The core algorithm is used to evaluate the scale-wise unreliability according to the given requirements, e.g., the outage probability or outage scale. The time complexity is theoretically analyzed, and its performance is experimentally verified. The proposed algorithm successfully evaluates in 82 minutes large benchmark networks with 400 links and the seven 9’s requirements; the state-of-the-art algorithm fails to evaluate it within 12 hours.

Since machine learning technologies are being used in various practical situations, models with merely low prediction errors might not be satisfactory; prediction errors occurring with a low probability might yield dangerous results in some applications. Therefore, there are attempts to achieve an ML model whose input-output pairs are guaranteed to satisfy given constraints. Among such attempts, many previous works chose the approach of modifying the outputs of an ML model at the inference time to satisfy the constraints. Such a strategy is handy because we can control its output without expensive training or fine-tuning. However, it is unclear whether using constraints only in the inference time degrades a model's predictive performance. This paper analyses how the generalization error bounds change when we only put constraints in the inference time. Our main finding is that a class of loss functions preserves the relative generalization error, i.e., the difference in generalization error compared with the best model will not increase by imposing constraints at the inference time on multi-class classification. Some popular loss functions preserve the relative error, including the softmax cross-entropy loss. On the other hand, we also show that some loss functions do not preserve relative error when we use constraints. Our results suggest the importance of choosing a suitable loss function when we only use constraints in the inference time.

Binary decision diagram (BDD) and zero-suppressed binary decision diagram (ZDD) are data structures to represent a family of (sub)sets compactly, and it can be used as succinct indexes for a family of sets. To build BDD/ZDD representing a desired family of sets, there are many transformation operations that take BDDs/ZDDs as inputs and output BDD/ZDD representing the resultant family after performing operations such as set union and intersection. However, except for some basic operations, the worst-time complexity of taking such transformation on BDDs/ZDDs has not been extensively studied, and some contradictory statements about it have arisen in the literature. In this paper, we show that many transformation operations on BDDs/ZDDs, including all operations for families of sets that appear in Knuth's book, cannot be performed in worst-case polynomial time in the size of input BDDs/ZDDs. This refutes some of the folklore circulated in past literature and resolves an open problem raised by Knuth. Our results are stronger in that such blow-up of computational time occurs even when the ordering, which has a significant impact on the efficiency of treating BDDs/ZDDs, is chosen arbitrarily.

In communication networks, the significance of an outage is measured mainly by its scale (number of disconnected nodes). To avoid serious outages, operators design their networks so that the reliability meets the specification for each outage scale, where the more significant the outage, the less likely it is to occur. Although scale-wise unreliability has been evaluated with rough approximation, sixth-generation (6G) mobile communication requires more accurate reliability evaluation with seven 9's accuracy. Unfortunately, accurate scale-wise reliability evaluation is a computationally very tough problem, so no previous literature has studied evaluation methods rigorous enough for 6G. This paper proposes an efficient algorithm to exactly compute the probability for each number of disconnected nodes. Our algorithm performs the scale-wise unreliability evaluation in a dynamic programming manner without redundant repetition for each outage scale. Numerical experiments using real network topologies show its great efficiency, e.g., our algorithm computes exact probabilities for every outage scale in just two hours for a network with nearly 200 links. We also provide several interesting insights on the reliability of real topologies from the scale-wise perspective, since our work is the first to present the scale-wise unreliability of real large topologies.

Contemporary society survives on several network infrastructures, such as communication and transportation. These network infrastructures are required to keep all nodes connected, although these nodes are occasionally disconnected due to failures. Thus, the expected number of connected node pairs (ECP) during an operation period is a reasonable reliability measure in network design. However, no work has studied ECP due to its computational hardness; we have to solve the reliability evaluation problem, which is a computationally tough problem, for O(n2) times where n is the number of nodes in a network. This paper proposes an efficient method that exactly computes ECP. Our method performs dynamic programming just once without explicit repetition for each node pair and obtains an exact ECP value weighted by the number of users at each node. A thorough complexity analysis reveals that our method is faster than an existing reliability evaluation method, which can be transferred to ECP computation, by O(n). Numerical experiments using real topologies show great efficiency; e.g., our method computes the ECP of an 821-link network in ten seconds; the existing method cannot complete it in an hour. This paper also presents two applications: critical link identification and optimal resource (e.g., a server) placement.

Network reliability, that is, the probability of con-necting specified nodes under link failures, is a key metric of network infrastructure. Because network reliability evaluation is a computationally heavy task, past research has relied on unre-alistically simple failure models such as the independent failure model, wherein each link fails stochastically and independently, ignoring large-scale failures such as disasters, or the deterministic-correlated failure model, wherein all links within a disaster area always fail. However, actual networks follow the probabilistic-correlated (PC) failure model, wherein links in a disaster area fail stochastically with respect to each disaster. This paper proposes an efficient method to accurately compute network reliability under the PC model. Following a conventional method for the independent model, the proposed method uses binary decision diagrams (BDDs) to efficiently handle an exponential number of failure states. Additionally, it employs a probabilistic inference technique to support probabilistic correlation, which is represented as another BDD for integration with the conventional method. The computational complexity was theoretically analyzed, and its performance was experimentally verified; it can compute the network reliability within 1 h for a large network with nearly 200 links and 100 potential disasters.

Since modern society largely depends on several network infrastructures such as telecommunications and various types of power, the reliability of networked systems needs to be accurately evaluated. Traditionally, network reliability has been evaluated on the assumption that the availability of each link is precisely given. However, in reality, it may be given with a degree of uncertainty, e.g., with variance, which must be propagated into the network reliability. To the best of our knowledge, no literature has investigated this issue because, since even computing the reliability itself belongs to a computationally tough class, computing the variance seems much harder.This paper proposes an efficient algorithm to compute the variance of the network reliability given the variance in link availability. We experimentally verify the performance of our algorithm and show that it can compute the variance of network reliability within 0.1 seconds for real topologies with nearly 200 links. We also perform extensive analyses on the variance of network reliability and reveal that network reliability tends to be accurate and that the variance in reliability does not significantly exceed the variance in link availability. Even when some links have a substantial variance in availability, the impact on network reliability is marginal.

Machine learning technologies have been used in a wide range of practical systems.In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements.However, it is difficult to obtain a model that satisfies requirements by just learning from examples.A simple solution is to add a module that checks whether the input-output pairs meet the requirements and then modifies the model's outputs. Such a module, which we call a {\em concurrent verifier} (CV), can give a certification, although how the generalizability of the machine learning model changes using a CV is unclear. This paper gives a generalization analysis of learning with a CV. We analyze how the learnability of a machine learning model changes with a CV and show a condition where we can obtain a guaranteed hypothesis using a verifier only in the inference time.We also show that typical error bounds based on Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings.

Network reliability, i.e., the probability of connecting a set of specified nodes under stochastic link failure, is a key indicator of network infrastructure, such as communication and power. Since network reliability evaluation is a computationally heavy task, several methods have been proposed to efficiently perform it. However, modern network infrastructures follow the client-server model, where many clients are served independently, so we have to evaluate the network reliability for every set consisting of the servers and each client. This evaluation process involves repetitive evaluations while changing the set, which imposes a heavy burden on network operators. This paper proposes a method that efficiently performs network reliability evaluation for the client-server model. Since our method is designed to evaluate reliability for multiple clients without explicit repetition, the computational complexity does not increase compared to the case where existing methods evaluate reliability for a single client. Numerical experiments using datasets of various topologies, including real communication networks, reveal great efficiency. Our method is more than 100 times faster than an existing method that requires repeated evaluation, e.g., it takes only 27 seconds to compute the reliability for 670 clients on a large network with 821 links.

Exact cover refers to the problem of finding subfamily F of a given family of sets S whose universe is D, where F forms a partition of D. Knuth’s Algorithm DLX is a state-of-the-art method for solving exact cover problems. Since DLX’s running time depends on the cardinality of input S, it can be slow if S is large. Our proposal can improve DLX by exploiting a novel data structure, DanceDD, which extends the zero-suppressed binary decision diagram (ZDD) by adding links to enable efficient modifications of the data structure. With DanceDD, we can represent S in a compressed way and perform search in linear time with the size of the structure by using link operations. The experimental results show that our method is an order of magnitude faster when the problem is highly compressed.

We address Stackelberg models of combinatorial congestion games (CCGs); we aim to optimize the parameters of CCGs so that the selfish behavior of non-atomic players attains desirable equilibria. This model is essential for designing such social infrastructures as traffic and communication networks. Nevertheless, computational approaches to the model have not been thoroughly studied due to two difficulties: (I) bilevel-programming structures and (II) the combinatorial nature of CCGs. We tackle them by carefully combining (I) the idea of \textit{differentiable} optimization and (II) data structures called \textit{zero-suppressed binary decision diagrams} (ZDDs), which can compactly represent sets of combinatorial strategies. Our algorithm numerically approximates the equilibria of CCGs, which we can differentiate with respect to parameters of CCGs by automatic differentiation. With the resulting derivatives, we can apply gradient-based methods to Stackelberg models of CCGs. Our method is tailored to induce Nesterov's acceleration and can fully utilize the empirical compactness of ZDDs. These technical advantages enable us to deal with CCGs with a vast number of combinatorial strategies. Experiments on real-world network design instances demonstrate the practicality of our method.

The Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions that subsumes the famous Ordered Binary Decision Diagram (OBDD) as a strict subset. SDDs are attracting much attention because they are more succinct than OBDDs, as well as having canonical forms and supporting many useful queries and transformations such as model counting and Apply operation. In this paper, we propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD). The key idea is to create a unique representation for Boolean functions that are equivalent under a specific variable substitution. We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite such succinctness, we show that numerous basic operations that are supported in polytime with SDD are also supported in polytime with VS-SDD. Experiments confirm that VS-SDDs are significantly more succinct than SDDs when applied to classical planning instances, where inherent symmetry exists.

Naoki Kobayashi, Tsutomu Hirao, Kengo Nakamura, Hidetaka Kamigaito, Manabu Okumura, Masaaki Nagata. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

We study the following dynamic graph problem: given an undirected graph G, we maintain a connectivity oracle between any two vertices in G under any on-line sequence of vertex deletions and insertions with incident edges. We propose two algorithms for this problem: an amortized update time deterministic one and a worst case update time Monte Carlo one. Both of them allow an arbitrary number of new vertices to insert. The update time complexity of the former algorithm is no worse than the existing algorithms, which allow only limited number of vertices to insert. Moreover, for relatively dense graphs, we can expect that the update time bound of the former algorithm meets a lower bound, and that of the latter algorithm can be seen as a substantial improvement of the existing result by introducing randomization.