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.

We consider the problem of learning a neural network classifier. Under the information bottleneck (IB) principle, we associate with this classification problem a representation learning problem, which we call "IB learning". We show that IB learning is, in fact, equivalent to a special class of the quantization problem. The classical results in rate-distortion theory then suggest that IB learning can benefit from a "vector quantization" approach, namely, simultaneously learning the representations of multiple input objects. Such an approach assisted with some variational techniques, result in a novel learning framework, "Aggregated Learning", for classification with neural network models. In this framework, several objects are jointly classified by a single neural network. The effectiveness of this framework is verified through extensive experiments on standard image recognition and text classification tasks.

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.

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 learning a neural network classifier. Under the information bottleneck (IB) principle, we associate with this classification problem a representation learning problem, which we call “IB learning”. We show that IB learning is, in fact, equivalent to a special class of the quantization problem. The classical results in rate-distortion theory then suggest that IB learning can benefit from a “vector quantization” approach, namely, simultaneously learning the representations of multiple input objects. Such an approach assisted with some variational techniques, result in a novel learning framework, “Aggregated Learning”, for classification with neural network models. In this framework, several objects are jointly classified by a single neural network. The effectiveness of this framework is verified through extensive experiments on standard image recognition and text classification tasks.

We derive two sufficient conditions for a function of a Markov random field (MRF) on a given graph to be a MRF on the same graph. The first condition is information-theoretic and parallels a recent information-theoretic characterization of lumpability of Markov chains. The second condition, which is easier to check, is based on the potential functions of the corresponding Gibbs field. We illustrate our sufficient conditions at the hand of several examples and discuss implications for practical applications of MRFs. As a side result, we give a partial characterization of functions of MRFs that are information preserving.

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 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.

Algebraic topology studies topological spaces with the help of tools from abstract algebra. The main focus of this paper is to show that many concepts from algebraic topology can be conveniently expressed in terms of (normal) factor graphs. As an application, we give an alternative proof of a classical duality result of Kramers and Wannier, which expresses the partition function of the 2-D Ising model at a low temperature in terms of the partition function of the 2-D Ising model at a high temperature. Moreover, we discuss analogous results for the 3-D Ising model and the Potts model.

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.

Let Xi, i E V form a Markov random field (MRF) represented by an undirected graph G = (V, E), and V' be a subset of V. We determine the smallest graph that can always represent the subfield Xi, i E V' as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i E V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

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.

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.

In the light of the recent interest in approximating the partition function of the Ising model using the dual normal factor graph, we revisit the classical duality result of Kramers and Wannier, where the dual normal factor graph may be viewed as an intermediate step in establishing such a result.

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.

In this paper, we show analytically that the duality of normal factor graphs (NFG) can facilitate stochastic estimation of partition functions. In particular, our analysis suggests that for the q-ary two-dimensional nearest-neighbor Potts model, sampling from the primal NFG of the model and sampling from its dual exhibit opposite behaviours with respect to the temperature of the model. For high-temperature models, sampling from the primal NFG gives rise to better estimators whereas for low-temperature models, sampling from the dual gives rises to better estimators. This analysis is validated by experiments.

Inspired by some new advances on normal factor graphs (NFGs), we introduce NFGs as a simple and intuitive diagrammatic approach towards encoding some concepts from linear algebra. We illustrate with examples the workings of such an approach and settle a conjecture of Peterson on the Pfaffian.

This paper stands at the intersection of two distinct lines of research. One line is “holographic algorithms,” a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is “normal factor graphs,” an elegant framework proposed by Forney for representing codes defined on graphs. We introduce the notion of holographic transformations for normal factor graphs, and establish a very general theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on the one hand underlies the principle of holographic algorithms, and on the other hand reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that potentially enable the use of normal factor graphs as a linear algebraic tool.

In his recent work, Valiant presented a powerful family of new algorithms, which he calls holographic algorithms. The mathematical foundation of holographic algorithms is what is known as Holant Theorem. Synthesizing from Valiant's work, in this paper, we introduce the notion of Valiant transform for normal graphs. Exploiting this synthesis, we establish a more general version of Holant Theorem, which allows an alternative interpretation of the duality results on normal graphs.

We consider network coding rates for directed and undirected k-pairs networks. For directed networks, meagerness is known to be an upper bound on network coding rates. We show that network coding rate can be ominus(|V|) multiplicative factor smaller than meagerness. For the undirected case, we show some progress in the direction of the k-pairs conjecture.

"Eligible for the student paper award." In this work we improve on the bounds presented in Z. Li and B. Li (2004) for network coding gain in the undirected case. A tightened bound for the undirected multicast problem with three terminals is derived. An interesting result shows that with fractional routing, routing throughput can achieve at least 75 % of the coding throughput. A tighter bound for the general multicast problem with any number of terminals shows that coding gain is strictly less than 2. Our derived bound depends on the number of terminals in the multicast network and approaches 2 for arbitrarily large number of terminals.