Homophily modulates double descent generalization in graph convolution networks.

Graph neural networks (GNNs) excel in modeling relational data such as biological, social, and transportation networks, but the underpinnings of their success are not well understood. Traditional complexity measures from statistical learning theory fail to account for observed phenomena like the double descent or the impact of relational semantics on generalization error. Motivated by experimental observations of "transductive" double descent in key networks and datasets, we use analytical tools from statistical physics and random matrix theory to precisely characterize generalization in simple graph convolution networks on the contextual stochastic block model. Our results illuminate the nuances of learning on homophilic versus heterophilic data and predict double descent whose existence in GNNs has been questioned by recent work. We show how risk is shaped by the interplay between the graph noise, feature noise, and the number of training labels. Our findings apply beyond stylized models, capturing qualitative trends in real-world GNNs and datasets. As a case in point, we use our analytic insights to improve performance of state-of-the-art graph convolution networks on heterophilic datasets.

Acoustic echoes reveal room shape.

Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room's response. Can you hear the shape of the room? Some people can do it naturally, but can we design computer algorithms that hear rooms? We show how to compute the shape of a convex polyhedral room from its response to a known sound, recorded by a few microphones. Geometric relationships between the arrival times of echoes enable us to "blindfoldedly" estimate the room geometry. This is achieved by exploiting the properties of Euclidean distance matrices. Furthermore, we show that under mild conditions, first-order echoes provide a unique description of convex polyhedral rooms. Our algorithm starts from the recorded impulse responses and proceeds by learning the correct assignment of echoes to walls. In contrast to earlier methods, the proposed algorithm reconstructs the full 3D geometry of the room from a single sound emission, and with an arbitrary geometry of the microphone array. As long as the microphones can hear the echoes, we can position them as we want. Besides answering a basic question about the inverse problem of room acoustics, our results find applications in areas such as architectural acoustics, indoor localization, virtual reality, and audio forensics.

The Fastest l1,∞ Prox in the West.

Proximal operators are of particular interest in optimization problems dealing with non-smooth objectives because in many practical cases they lead to optimization algorithms whose updates can be computed in closed form or very efficiently. A well-known example is the proximal operator of the vector l1 norm, which is given by the soft-thresholding operator. In this paper we study the proximal operator of the mixed l1,∞ matrix norm and show that it can be computed in closed form by applying the well-known soft-thresholding operator to each column of the matrix. However, unlike the vector l1 norm case where the threshold is constant, in the mixed l1,∞ norm case each column of the matrix might require a different threshold and all thresholds depend on the given matrix. We propose a general iterative algorithm for computing these thresholds, as well as two efficient implementations that further exploit easy to compute lower bounds for the mixed norm of the optimal solution. Experiments on large-scale synthetic and real data indicate that the proposed methods can be orders of magnitude faster than state-of-the-art methods.

Metals in proteins: correlation between the metal-ion type, coordination number and the amino-acid residues involved in the coordination.

Metal ions are constituents of many metalloproteins, in which they have either catalytic (metalloenzymes) or structural functions. In this work, the characteristics of various metals were studied (Cu, Zn, Mg, Mn, Fe, Co, Ni, Cd and Ca in proteins with known crystal structure) as well as the specificity of their environments. The analysis was performed on two data sets: the set of protein structures in the Protein Data Bank (PDB) determined with resolution <1.5 A and the set of nonredundant protein structures from the PDB. The former was used to determine the distances between each metal ion and its electron donors and the latter was used to assess the preferred coordination numbers and common combinations of amino-acid residues in the neighbourhood of each metal. Although the metal ions considered predominantly had a valence of two, their preferred coordination number and the type of amino-acid residues that participate in the coordination differed significantly from one metal ion to the next. This study concentrates on finding the specificities of a metal-ion environment, namely the distribution of coordination numbers and the amino-acid residue types that frequently take part in coordination. Furthermore, the correlation between the coordination number and the occurrence of certain amino-acid residues (quartets and triplets) in a metal-ion coordination sphere was analysed. The results obtained are of particular value for the identification and modelling of metal-binding sites in protein structures derived by homology modelling. Knowledge of the geometry and characteristics of the metal-binding sites in metalloproteins of known function can help to more closely determine the biological activity of proteins of unknown function and to aid in design of proteins with specific affinity for certain metals.