We consider the problem of identifying the source of a rumor in a network. Given a snapshot observation of the network, in which a rumor has been spreading for some time, how to identify the source from which the rumor started to spread? In this paper, we point out the limitations of existing estimators in the literature. As a remedy, we put forth a new estimator by incorporating an independent random observation time. To capture the structure of information flow beyond graphs, our formulations consider rate constraints on the rumor and the multicast capacities for cyclic polylinking networks.

Identifying locally dense subgraphs aims to pinpoint subgraphs characterized by tight internal connectivity. However, existing methods for identifying dense subgraphs based on density can lead to loose internal connections. This paper addresses this issue by introducing a concept of strength to detect strong subsets. Our approach encompasses the existing work that finds a nested chain of densest k-subgraphs as a special case and reveals subgraphs that have tight internal connections overlooked by existing methods. The strong subsets exhibit a laminar structure and can be computed in polynomial time. In contrast to previous works defining locally densest subgraphs without a natural extension to weighted graphs, our method accommodates both weighted and unweighted, directed and undirected graphs, as well as hypergraphs. Furthermore, it extends to a broader notion of information density, surpassing the scope of weighted graphs.

In this paper, we explore the connection between secret key agreement and secure omniscience within the setting of the multiterminal source model with an eavesdropper having side information. While the secret key agreement problem considers the generation of a maximum-rate secret key through public discussion, the secure omniscience problem is concerned with communication protocols for omniscience that minimize the rate of information leakage to the eavesdropper. The starting point of our work is a lower bound on the minimum leakage rate for omniscience,$R_{ \text {L}}$, in terms of the wiretap secret key capacity,$C_{ \text {W}}$. Our interest is in identifying broad classes of sources for which this lower bound is met with equality, in which case we say that there is a duality between secure omniscience and secret key agreement. We show that this duality holds in the case of certain finite linear source (FLS) models, such as two-terminal FLS models and pairwise independent network models on trees with a linear eavesdropper. Duality also holds for any FLS model in which$C_{ \text {W}}$is achieved by a perfect linear secret key agreement scheme. We conjecture that the duality in fact holds unconditionally for any FLS model. On the negative side, we give an example of a (non-FLS) source model for which duality does not hold if we limit ourselves to communication-for-omniscience protocols with at most two (interactive) communications. We also address the secure function computation problem and explore the connection between the minimum leakage rate for computing a function and the wiretap secret key capacity.

We find a way to harden the decision of a neural network. Combining such a hardening effect with another adversarial training method would further improve its adversarial robustness. By suppressing the logit corresponding to the class that the model has highest confidence during training, the model is encouraged to make harder predictions. This significantly improves a model’s robustness against gradient-based adversarial attacks. The simplicity of our method makes it very easy to be deployed on existing adversarial training schemes with almost no computational overhead. The experimental results show that a model trained with TRADES benefits from hardening. It shows a greatly improved robustness against the PGD attack while retaining similar performance against decision-based attacks. How the hardening effect effectively defends the models from gradient-based attacks is worth further investigation.

We revisit the log N bound of InfoNCE (N is the sample size), which sets an upper limit on the estimator, thereby often causing the estimator to return an under-estimate of the mutual information. We show that the existing solution of excluding data samples from the reference set causes an equally debilitating problem, namely, it causes the estimator to overshoot, often with no sign of convergence, thereby leading to an overestimate of the mutual information. We mitigate both issues by introducing a classifier to smooth out the data labels and propose a new mutual information neural estimator called Smoothed InfoNCE. We conduct experiments on high-dimensional Gaussian data and demonstrate that the proposed model can break the log N curse without suffering from overshooting.

The characterization of the secret key capacity with wiretapper side information is a challenging open problem. In this paper, we give a necessary and sufficient condition for the positivity of wiretap secret key capacity for the multiterminal source model. This result extends the existing works for two-terminal sources. However, in the case of hypergraphical source models with a linear wiretapper, we derive a simpler equivalent condition for the positivity. We also show that blocklength need not be larger than the logarithm of the number of edges in order to generate a positive rate key. The proofs of these results involve a subclass called minimally connected hypergraphical sources with a linear wiretapper, for which we obtain a single-letter characterization of wiretap secret key capacity.

In this paper, we obtain a single-letter characterization of the wiretap secret key capacity for a large class of multiterminal source models (namely, tree-PIN models) with a linear wiretapper that can observe arbitrary linear combinations of the source. For this class of sources, we also show a duality between the problems of wiretap secret key agreement and secure omniscience, which suggests that such duality potentially holds for more general sources.

Estimating the mutual information (MI) by neural networks has achieved significant practical success, especially in representation learning. Recent results further reduced the variance in the neural estimation by training a probabilistic classifier. However, the trained classifier tends to be overly confident about some of its predictions, which results in an overestimated MI that fails to capture the desired representation. To soften the classifier, we propose a novel scheme that smooths the label adaptively according to how extreme the probability estimates are. The resulting MI estimate is unbiased under a mild assumption on the model. Experimental results on MNIST and CIFAR10 datasets confirmed that our method yields better representation and achieves higher classification test accuracy among existing approaches in self-supervised representation learning.

We show that, under the info-clustering framework, correlated random variables can be clustered in an agglomerative manner. While the existing divisive approach successively segregates the random variables into subsets with increasing multivariate mutual information, our agglomerative approach successively merges subsets of random variables sharing a large amount of normalized total correlation. We show that both approaches result in the same hierarchy of clusters, but the agglomerative approach is an order of magnitude faster than the divisive one. The uniqueness of the hierarchy produced by the two approaches is due to a fundamental connection that we uncover between the well-known total correlation and the recently proposed measure of multivariate mutual information. We implement the new algorithm and provide a data structure for efficient storage and retrieval of the hierarchical clustering solution.

We consider the problem of exchanging sensitive information in public and provide a general formulation that can unify and extend various existing scenarios of information exchange, such as the problems of private information extraction and information bottleneck. The formulation also gives rise to a new scenario called secure omniscience (SO), where users want to exchange all their private information with minimum leakage to a wiretapper with side information. Single-letter lower and upper bounds are obtained for the minimum leakage, and the bounds are shown to be tight under the finite linear source model with two users. The bounds are derived in terms of the solutions of the closely related problems of communication for omniscience (CO) and secret key agreement (SKA). However, we find examples where the bounds are not tight, and so the connections to CO and SKA are not precise. In particular, it is possible that any optimal CO scheme that minimizes communication does not minimize leakage, and any optimal SO scheme that minimizes leakage does not attain the capacity for SKA. Nevertheless, we identify a useful notion of information alignment that can modify an optimal CO scheme to reduce leakage for SO.

The discussion rate region in the multiterminal source model is the individual discussion rate required for generating a secret key of maximum rate. We give an explicit single-letter characterization of the discussion rate region for a large class of pairwise independent network (PIN) models. Besides, we also establish a sufficient condition for identifying whether a PIN model belongs to this class, which can be checked in strongly polynomial time. As a by-product, the discussion rate region reduces to a very simple expression for PIN model satisfying such condition.

This paper investigates the secret key generation in the multiterminal source model, where users observing correlated sources discuss interactively under limited rates to agree on a secret key. We focus on a class of sources representable by minimally connected hypergraphs. For such sources, we give a single-letter explicit characterization of the region of achievable secret key rate and public discussion rate tuple. This is the first result that completely characterizes the achievable rate region for a multiterminal source model, which is beyond the PIN model on a tree. We also obtain an explicit formula for the maximum achievable secret key rate, called the constrained secrecy capacity, as a function of the total discussion rate.

We consider the web community detection problem by providing a cost function that, not only penalizes external connections, but also rewards the internal ones. Our formulation addresses limitations of cut-clustering and extends web communities to digraphs. The formulation is parametric, resulting in a hierarchy of communities that is representable in linear storage and computable in a linear number of maxflow computations. Experiments on synthetic and real-world datasets show that the proposed method can find better web communities and more densest subgraphs than previous formulations. Simple examples also show that it can return different and more meaningful communities compared to other formulations that are based on graph conductance, map equation and modularity score.

We consider a non-asymptotic (one-shot) version of the multiterminal secret key agreement problem on a finite linear source model. In this model, the observation of each terminal is a linear function of an underlying random vector composed of finitely many i.i.d. uniform random variables. By restricting the public discussion to be a linear function of the terminals' observations, we obtain a characterization of the communication complexity (minimum number of symbols of public discussion) of generating a secret key of maximum length. More precisely, we show that the minimum discussion can be achieved by a non-interactive protocol in which each terminal first does a linear processing of its own private observations, following which the terminals all execute a discussion-optimal communication-for-omniscience protocol. The secret key can be chosen to be a linear function of the vector of all observations.

Hypergraphical sources are a natural class of sources for secret key generation, within which different subsets of terminals sharing secrets are allowed to discuss publicly in order to agree upon a global secret key. While their secrecy capacity, i.e., the maximum rate of a secret key that can be agreed upon by the entire set of terminals, is well-understood, what remains open is the maximum rate of a secret key that can be generated when there is a restriction on the overall rate of public discussion allowed. In this paper, we obtain a family of explicitly computable upper bounds on the number of bits of secret key that can be generated per bit of public discussion. These upper bounds are derived using a lamination technique based on the submodularity of the entropy function. In particular, a specific instance of these upper bounds, called the edge-partition bound, is shown to be tight for the pairwise independent network model, a special case of the hypergraphical source when the hypergraph is a graph. The secret key generation scheme achieving this upper bound is the tree-packing protocol of Nitinawarat et al., thereby resolving in the affirmative the discussion rate optimality of the tree-packing protocol.

We show that correlated random variables can be clustered more efficiently in an agglomerative manner rather than a divisive one. The agglomerative approach successively merges subsets of random variables sharing a large amount of normalized total correlation. Compared to the existing divisive approach that successively segregates the random variables into subsets with increasing multivariate mutual information, the agglomerative approach gives the same hierarchy of clusters faster by an order of magnitude. The underlying results justifying the agglomerative approach are also of theoretical interest since they reveal a fundamental connection between the well-known total correlation and the recently proposed multivariate mutual information.

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

We investigate the secret key generation in the multiterminal source model, where the users discuss under limited rate. For the minimally connected hypergraphical sources, we give an explicit formula of the maximum achievable secret key rate, called the secrecy capacity, under any given total discussion rate. Besides, we also partially characterize the region of achievable secret key rate and discussion rate tuple. When specializes to the hypertree sources, our results give rise to a complete characterization of the region.

We study the change of multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset of the random variables. This is formulated more precisely as two new multiterminal secret key agreement problems that, respectively, ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. Characterizations and strongly polynomial-time computations are derived for the rates of change, maximum usable increment, and redundancy. These results can be applied to study the communication complexity for secret key agreement.

For the multiterminal secret key agreement problem under a private source model, it is known that the maximum key rate, i.e., the secrecy capacity, can be achieved through communication for omniscience, but the omniscience strategy can be strictly suboptimal in terms of minimizing the public discussion rate. While a single-letter characterization is not known for the minimum discussion rate needed for achieving the secrecy capacity, we derive single-letter lower bounds that yield some simple conditions for omniscience to be discussion-rate optimal. These conditions turn out to be enough to deduce the optimality of omniscience for a large class of sources, including the hypergraphical sources. We also extend our results to more general class of multiterminal sources with helpers and silent users.

This paper considers the communication for omniscience problem: a set of users observe a discrete memoryless multiple source and want to recover the entire multiple source via noise-free broadcast communications. We study the problem of how to determine an optimal rate vector that attains omniscience with the minimum sum rate, the total number of communications. The results cover both asymptotic and non-asymptotic models where the transmission rates are real and integral, respectively. We propose a modified decomposition algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and non-asymptotic models, respectively, both of which determine the value of the minimum sum rate and a corresponding optimal rate vector in polynomial time. For the coordinate saturation capacity algorithm, a nesting algorithm in MDA and SIA, we propose to implement it by a fusion method and show by experimental results that this fusion method contributes to a reduction in computation complexity. Finally, we show that the separable convex minimization problem over the optimal rate vector set in the asymptotic model can be decomposed by the fundamental partition, the optimal partition of the user set that determines the minimum sum rate, so that the problem can be solved more efficiently.

Respiratory motion during positron emission tomography (PET)/computed tomography (CT) imaging can cause significant image blurring and underestimation of tracer concentration for both static and dynamic studies. In this paper, with the aim to eliminate both intra-cycle and inter-cycle motions, and apply to dynamic imaging, we developed a non-rigid event-by-event (NR-EBE) respiratory motion-compensated list-mode reconstruction algorithm. The proposed method consists of two components: the first component estimates a continuous non-rigid motion field of the internal organs using the internal-external motion correlation. This continuous motion field is then incorporated into the second component, non-rigid MOLAR (NR-MOLAR) reconstruction algorithm to deform the system matrix to the reference location where the attenuation CT is acquired. The point spread function (PSF) and time-of-flight (TOF) kernels in NR-MOLAR are incorporated in the system matrix calculation, and therefore are also deformed according to motion. We first validated NR-MOLAR using a XCAT phantom with a simulated respiratory motion. NR-EBE motion-compensated image reconstruction using both the components was then validated on three human studies injected with18F-FPDTBZ and one with18F-fluorodeoxyglucose (FDG) tracers. The human results were compared with conventional non-rigid motion correction using discrete motion field (NR-discrete, one motion field per gate) and a previously proposed rigid EBE motion-compensated image reconstruction (R-EBE) that was designed to correct for rigid motion on a target lesion/organ. The XCAT results demonstrated that NR-MOLAR incorporating both PSF and TOF kernels effectively corrected for non-rigid motion. The18F-FPDTBZ studies showed that NR-EBE out-performed NR-Discrete, and yielded comparable results with R-EBE on target organs while yielding superior image quality in other regions. The FDG study showed that NR-EBE clearly improved the visibility of multiple moving lesions in the liver where some of them could not be discerned in other reconstructions, in addition to improving quantification. These results show that NR-EBE motion-compensated image reconstruction appears to be a promising tool for lesion detection and quantification when imaging thoracic and abdominal regions using PET.

For the multiterminal secret key agreement problem, new single-letter lower bounds are obtained on the minimum public discussion rate required to achieve any given secret key rate below the secrecy capacity. The results apply to the general source model without helpers or wiretapper's side information, but can be strengthened for hypergraphical sources. In particular, for the pairwise independent network, our results yield a complete characterization of the maximum secret key rate achievable under a constraint on the total discussion rate.

We study the rate of change of the multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset. This is formulated more precisely as two new multiterminal secret key agreement problems which ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. The combinatorial structure has been clarified along with some meaningful open problems.

We consider the problem of how to fairly distribute the minimum sum-rate among the users in communication for omniscience (CO). We formulate a problem of minimizing a weighted quadratic function over a submodular base polyhedron which contains all achievable rate vectors, or transmission strategies, for CO that have the same sum-rate. By solving it, we can determine the rate vector that optimizes the Jain's fairness measure, a more commonly used fairness index than the Shapley value in communications engineering. We show that the optimizer is a lexicographically optimal (lex-optimal) base and can be determined by a decomposition algorithm (DA) that is based on submodular function minimization (SFM) algorithm and completes in strongly polynomial time. We prove that the lex-optimal minimum sum-rate strategy for CO can be determined by finding the lex-optimal base in each user subset in the fundamental partition and the complexity can be reduced accordingly.

In the multiterminal source model of Csiszár and Narayan, the communication complexity, RSK, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to RSKis given by RCO, which is the minimum rate of communication required for omniscience. In this paper we derive a better upper bound to RSKfor the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on RSK. This bound, however, is not tight, as demonstrated by a counterexample.

For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.

Modulation classification is crucial in applications such as electronic warfare and interference cancellation. In this letter, a novel feature-based Kolmogorov-Smirnov classifier is proposed for the identification of the modulation formats. The received signal is first preprocessed with a folding operation that helps identify the modulation formats based on their different axes of symmetry. Simulation results show that the performance of the proposed classifier is close to that of the optimal likelihood-based classifier, while its robustness to noise uncertainty is improved and its computational complexity is reduced compared to that of the optimal likelihood-based classifier.

Because the exchange of information among all the users in a large network can take a long time, a successive omniscience protocol is proposed. Namely, subgroups of users first recover the information of other users in the same subgroup at an earlier stage called local omniscience. Then, the users recover the information of all other users at a later stage called global omniscience. To facilitate the information exchange, a distributed storage system is used, so that users can conveniently upload and download messages through some reliable central servers. The minimum upload bandwidth is characterized and a bandwidth-storage trade-off is discovered. The results reveal the new connections to the problem of secret key agreement and, consequently, provide meaningful interpretations of a recently proposed multivariate mutual information measure that was inspired by the secret key agreement problem.

The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.

Alice wishes to potentially communicate with Bob over a compound Binary Symmetric Channel while Willie listens in over a compound Binary Symmetric Channel that is noisier than Bob's. The channel noise parameters for both Bob and Willie are drawn according to uniform distribution over a range, but none of the three parties know their exact values. Willie's goal is to infer whether or not Alice is communicating with Bob. We show that Alice can send her messages reliably to Bob while ensuring that even whether or not she is actively communicating is deniable to Willie. We find the best rate at which Alice can communicate both deniably and reliably using Shannon's random coding and prove a converse.

We survey here recent work pertaining to “deniable” communication - i.e., talking without being detected. We first highlight connections to other related notions (anonymity and secrecy). We then contrast the notions of deniability and secrecy. We highlight similarities and distinctions of deniability with a variety of related notions (LPD communications, stealth, channel resolvability) extant in the literature.

The problem of secret key agreement by public discussion is studied under a general multiterminal network, where each user can both send and receive over a private channel. Single-letter upper and lower bounds are for the maximum achievable key rate. The bounds are shown to match for a large class of private channels. A counter-example shows that the bounds do not match in general, and a better cooperative scheme can narrow the gap.

Positron emission tomography (PET) images usually suffer from poor signal-to-noise ratio (SNR) due to the high level of noise and low spatial resolution, which adversely affect its performance for lesion detection and quantification. The complementary information present in high-resolution anatomical images from multi-modality imaging systems could potentially be used to improve the ability to detect and/or quantify lesions. However, previous methods that use anatomical priors usually require matched organ/lesion boundaries. In this study, we investigated the use of anatomical information to suppress noise in PET images while preserving both quantitative accuracy and the amplitude of prominent signals that do not have corresponding boundaries on computerized tomography (CT). The proposed approach was realized through a postreconstruction filter based on the nonlocal means (NLM) filter, which reduces noise by computing the weighted average of voxels based on the similarity measurement between patches of voxels within the image. Anatomical knowledge obtained from CT was incorporated to constrain the similarity measurement within a subset of voxels. In contrast to other methods that use anatomical priors, the actual number of neighboring voxels and weights used for smoothing were determined from a robust measurement on PET images within the subset. Thus, the proposed approach can be robust to signal mismatches between PET and CT. A 3-D search scheme was also investigated for the volumetric PET/CT data. The proposed anatomically guided median nonlocal means filter (AMNLM) was first evaluated using a computer phantom and a physical phantom to simulate realistic but challenging situations where small lesions are located in homogeneous regions, which can be detected on PET but not on CT. The proposed method was further assessed with a clinical study of a patient with lung lesions. The performance of the proposed method was compared to Gaussian, edge-preserving bilateral and NLM filters, as well as median nonlocal means (MNLM) filtering without an anatomical prior. The proposed AMNLM method yielded improved lesion contrast and SNR compared with other methods even with imperfect anatomical knowledge, such as missing lesion boundaries and mismatched organ boundaries.

A general network link model is formulated, unifying the previous directed cyclic graphical network, linear deterministic network and layered linking network. It provides a seamless extension of Menger's theorem that the network can be decomposed into disjoint augmenting paths up to the min-cut value even in the presence of cycles and interference. This is obtained by developing new concepts for linking systems, which also lead to polynomial-time algorithms that compute the shortest path, maximum flow and optimal path decomposition.

A combinatorial notion of flow is identified for time-invariant linear coding over non-layered deterministic linear networks that may contain cycles, broadcast and interference links. It reveals the matroidal structure for efficient code construction, and enables a seamless extension of the classical network coding results. In particular, the flow can be decomposed efficiently into disjoint information flow paths to support a maximum unicast rate up to the cut-set bound.

A variational-distance-based scheme is proposed for the modulation classification problem. It decides on the modulation that minimizes the variational distance between the theoretical and empirical probability density of the received signal. Simulation suggests that it outperforms some existing featured-based classifiers, namely the cumulant classifier, K-S classifier and Kuiper classifier. Its computational complexity is comparable to those classifiers but it is more robust to the error in estimating the noise power.

The undirected graphical model is generalized to a linear matroid. The optimal direction for multicasting can be found in polynomial time with respect to the size of the network. A more general problem is also considered where certain function of a distributed source is to be computed at multiple nodes. The converse results are derived, not from the usual cut-set bound but through the related problem of secret key agreement and secure source coding by public discussion. A unifying model of partly directed network can also be formulated, covering both the directed and undirected networks as special cases.

A secret key agreement problem is proposed with the additional restriction that the key is a function of a given secret source. An inner bound to the achievable rates, error and secrecy exponents is derived. The maximum key rate strongly achievable with positive exponents is characterized. The result leads to class of admissible restrictions on the key functions that does not diminish the strongly achievable key rate.

An information identity is proven, equating the secrecy capacity of the multiterminal secret key agreement problem and the throughput of certain undirected network. As a consequence, network coding can be used for secret key agreement while secrecy capacity characterizes the network throughput. A meaningful notion of mutual dependence is established with the combinatorial interpretation of partition connectivity.

A linear scheme is proposed for multiterminal secret key agreement under a private finite linear source model with public discussion. With a wiretapper observing the public discussion and a subset of the source components, it attains the secrecy capacity perfectly and non-asymptotically with a finite block length. Upper bounds on the block length and public discussion rate are given.