Search

It has been observed that graph neural networks (GNN) sometimes struggle to maintain a healthy balance between the efficient modeling long-range dependencies across nodes while avoiding unintended consequences such oversmoothed node representations or sensitivity to spurious edges. To address this issue (among other things), two separate strategies have recently been proposed, namely implicit and unfolded GNNs. The former treats node representations as the fixed points of a deep equilibrium model that can efficiently facilitate arbitrary implicit propagation across the graph with a fixed memory footprint. In contrast, the latter involves treating graph propagation as unfolded descent iterations as applied to some graph-regularized energy function. While motivated differently, in this paper we carefully quantify explicit situations where the solutions they produce are equivalent and others where their properties sharply diverge. This includes the analysis of convergence, representational capacity, and interpretability. In support of this analysis, we also provide empirical head-to-head comparisons across multiple synthetic and public real-world node classification benchmarks. These results indicate that while IGNN is substantially more memory-efficient, UGNN models support unique, integrated graph attention mechanisms and propagation rules that can achieve SOTA node classification accuracy across disparate regimes such as adversarially-perturbed graphs, graphs with heterophily, and graphs involving long-range dependencies.

Scalability of graph neural networks remains one of the major challenges in graph machine learning. Since the representation of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes from previous layers, the receptive fields grow exponentially, which makes standard stochastic optimization techniques ineffective. Various approaches have been proposed to alleviate this issue, e.g., sampling-based methods and techniques based on pre-computation of graph filters. In this paper, we take a different approach and propose to use graph coarsening for scalable training of GNNs, which is generic, extremely simple and has sublinear memory and time costs during training. We present extensive theoretical analysis on the effect of using coarsening operations and provides useful guidance on the choice of coarsening methods. Interestingly, our theoretical analysis shows that coarsening can also be considered as a type of regularization and may improve the generalization. Finally, empirical results on real world datasets show that, simply applying off-the-shelf coarsening methods, we can reduce the number of nodes by up to a factor of ten without causing a noticeable downgrade in classification accuracy., Comment: KDD 2021

Despite the recent success of graph neural networks (GNN), common architectures often exhibit significant limitations, including sensitivity to oversmoothing, long-range dependencies, and spurious edges, e.g., as can occur as a result of graph heterophily or adversarial attacks. To at least partially address these issues within a simple transparent framework, we consider a new family of GNN layers designed to mimic and integrate the update rules of two classical iterative algorithms, namely, proximal gradient descent and iterative reweighted least squares (IRLS). The former defines an extensible base GNN architecture that is immune to oversmoothing while nonetheless capturing long-range dependencies by allowing arbitrary propagation steps. In contrast, the latter produces a novel attention mechanism that is explicitly anchored to an underlying end-to-end energy function, contributing stability with respect to edge uncertainty. When combined we obtain an extremely simple yet robust model that we evaluate across disparate scenarios including standardized benchmarks, adversarially-perturbated graphs, graphs with heterophily, and graphs involving long-range dependencies. In doing so, we compare against SOTA GNN approaches that have been explicitly designed for the respective task, achieving competitive or superior node classification accuracy. Our code is available at https://github.com/FFTYYY/TWIRLS., Comment: accepted as long oral for ICML 2021

We study the secure decentralized Pliable Index CODing (PICOD) problem with circular side information sets at the users. The security constraint forbids every user to decode more than one message while a decentralized setting means there is no central transmitter in the system. Compared to the secure but centralized version of the problem, a converse bound from one of our previous works showed a factor of three difference in optimal code length under the constraint of linear encoding. In this paper, we first list the linearly infeasible cases, that is, problems where no linear code can simultaneously achieve both correctness/decodability and security. Then, we propose linear coding schemes for all remaining cases and show that their attained code length is to within an additive constant gap from our converse bound., Comment: 13 pages, 31 figures, 1 table

This paper studies a variant of the Pliable Index CODing (PICOD) problem, i.e., an index coding problem where a user can be satisfied by decoding any message that is not in its side information set, where communication is decentralized, i.e., it occurs among users rather than by the central server, and secure, i.e., each user is allowed to decode only one message outside its side information set and must not be able to collect any information about any other message that is not its decoded one. Given the difficulty of the general version of this problem, this paper focuses on the case where the side information sets are `$s$~circular shifts', namely, user $u$'s side information set is the set of messages indexed by $\{u, u+1, \ldots, u+s-1\}$ for some fixed $s$ and where the indices are intended modulo the cardinality of the message set. This particular setting has been studied in the `decentralized non-secure' and in the `centralized secure' settings, thus allows one to quantify the cost of decentralized communication under security constraints on the number of transmissions. Interestingly, the decentralized vs the centralized secure setting incurs a multiplicative gap of approximately~three. This is in contrast to the cases without security constraint, where the multiplicative gap is known to be at most two., Comment: 6 pages, 1 figure, submitted to ISIT 2020

This paper introduces the ${\it decentralized}$ Pliable Index CODing (PICOD) problem: a variant of the Index Coding (IC) problem, where a central transmitter serves ${\it pliable}$ users with message side information; here, pliable refers to the fact that a user is satisfied by decoding ${\it any}$ $t$ messages that are not in its side information set. In the decentralized PICOD, a central transmitter with knowledge of all messages is not present, and instead users share among themselves massages that can only depend on their local side information set. This paper characterizes the capacity of two classes of decentralized complete--$S$ PICOD$(t)$ problems with $m$ messages (where the set $S\subset[m]$ contains the sizes of the side information sets, and the number of users is $n=\sum_{s\in S}\binom{m}{s}$, with no two users having the same side information set): (i) the consecutive case: $S=[s_\min:s_\max]$ for some $0 \leq s_\min\leq s_\max \leq m-t$, and (ii) the complement-consecutive case: $S=[0:m-t]\backslash[s_\min:s_\max]$, for some $0 < s_\min\leq s_\max < m-t$. Interestingly, the optimal code-length for the decentralized PICOD in those cases is the same as for the classical (centralized) PICOD counterpart, except when the problem is no longer pliable, that is, it reduces to an IC problem where every user needs to decode all messages not in its side information set. Although the optimal code-length may be the same in both centralized and decentralized settings, the actual optimal codes are not. For the decentralized PICOD, sparse Maximum Distance Separable (MDS) codes and vector linear index codes are used (as opposed to scalar linear codes)., Comment: 5 pages. To be presented at ISIT 2019

The Pliable Index CODing (PICOD) problem is a variant of the Index Coding (IC) problem, where the desired messages by the users, who are equipped with message side information, is part of the optimization. This paper studies the PICOD problem where users are subject to a privacy constraint. In particular, the following spacial class of private PICODs is investigated: 1) the side information structure is circular, and 2) each user can decode one and only one message. The first condition is a special case of the "circular-arc network topology hypergraph" class of PICOD studied in [Liu and D. Tuninetti, "Tight information theoretic converse results for some pliable index coding problems," ITW, 2018], for which an optimal solution was given without the privacy constraint. The second condition was first studied in [S. Sasi and B. S. Rajan, "On pliable index coding," arXiv:1901.05809] and was motivated by the need to keep content privacy is some distribution networks. This paper proposes both converse and achievable bounds. The proposed achievable scheme not only strictly outperforms the one in [S. Sasi and B. S. Rajan, "On pliable index coding," arXiv:1901.05809] for some values of the system parameters, but it is also information theoretically optimal in some settings. For the remaining cases, the proposed linear code is shown to require at most one more transmission than the converse bound derived by restricting the sender to only use linear codes., Comment: 6 pages. Submitted to ITW 2019. Eq. 4 changed for a constraint on individual messages in v3

This paper studies the Pliable Index CODing problem (PICOD), which models content-type distribution networks. In the PICOD$(t)$ problem there are $m$ messages, $n$ users and each user has a distinct message side information set, as in the classical Index Coding problem (IC). Differently from IC, where each user has a pre-specified set of messages to decode, in the PICOD$(t)$ a user is "pliable" and is satisfied if it can decode any $t$ messages that are not in its side information set. The goal is to find a code with the shortest length that satisfies all the users. This flexibility in determining the desired message sets makes the PICOD$(t)$ behave quite differently compared to the IC, and its analysis challenging. This paper mainly focuses on the \emph{complete--$S$} PICOD$(t)$ with $m$ messages, where the set $S\subset[m]$ contains the sizes of the side information sets, and the number of users is $n=\sum_{s\in S}\binom{m}{s}$, with no two users having the same side information set. Capacity results are shown for: (i) the \emph{consecutive} complete--$S$ PICOD$(t)$, where $S=[s_{\min}:s_{\max}]$ for some $0 \leq s_{\min} \leq s_{\max} \leq m-t$, and (ii) the \emph{complement-consecutive} complete--$S$ PICOD$(t)$, where $S=[0:m-t]\backslash[s_{\min}:s_{\max}]$, for some $0 < s_{\min} \leq s_{\max} < m-t$. The novel converse proof is inspired by combinatorial design techniques and the key insight is to consider all messages that a user can eventually decode successfully, even those in excess of the $t$ required ones. This allows one to circumvent the need to consider all possible desired message set assignments at the users in order to find the one that leads to the shortest code length. In addition, tight converse results are also shown for those PICOD$(1)$ with circular-arc network topology hypergraph., Comment: 38 pages, 4 figures, submitted to IEEE Transactions on Information Theory

Pliable Index CODing (PICOD) is a variant of the Index Coding (IC) problem in which a user is satisfied whenever it can successfully decode any one message that is not in its side information set, as opposed to a fixed pre-determined message. The complete--$S$ PICOD with $m$ messages, for $S\subseteq[0:m-1]$, has $n = \sum_{s\in S} \binom{m}{s}$ users with distinct side information sets. Past work on PICOD provided tight converse results when either the sender is constrained to use linear codes, or for some special classes of complete--$S$ PICOD. This paper provides a tight information theoretic converse result (i.e., no restriction to linear codes) for the so-called "consecutive complete--$S$" PICOD, where the set $S$ satisfies $S=[s_{min} : s_{max}]$ for some $0\leq s_{min} \leq s_{max} \leq m-1$. This result extends existing converse results and shows that linear codes have the smallest possible code length given by $\min(m-s_{\min},1+s_{\max})$. The central contribution is a novel proof technique rooted in combinatorics. The main idea is to consider all the messages a user can eventually successfully decode, in addition to its own desired message. This allows us to circumvent the necessity of essentially considering all possible assignments of desired messages for the users. The keystone of the proof is to show that, for the case of $S=\{s\}$ and $m = 2s+1$, there exists at least one user who can decode $s+1$ messages. From this, the extension to the "consecutive complete--$S$" PICOD follows., Comment: Submitted to ITW 2018