Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter

1 Introduction

Message-passing algorithms, like Belief Propagation (BP) [Pearl, 1991] and its variants, have proved empirically effective for solving hard/computationally intensive problems in a range of important and real-world AI tasks. For example, consider the well-known problem of web page ranking. Viewing the web as a graph where nodes are web pages and directed edges are hyperlinks between web pages, a highly successful web page ranking metric computed from this graph is the PageRank [Brin and Page, 2006]. Converting this graph to an ergodic Markov chain, the PageRank of a web page node v is the (limit) stationary probability that a random walker is at v. Recently, Bickson et al. have shown how to compute the PageRank distributively and efficiently using Gaussian belief propagation (GaBP) [2007].

There are many improvements that can be made to (Ga)BP, especially when applied to inference in graphical models containing structural symmetries. Such symmetries are commonly found in first-order and relational probabilistic models (see e.g. Getoor and Taskar [2007]) that combine aspects of

Scott Sanner

Statistical ML Group, NICTA & ANU 7 London Circuit, Canberra, Australia

Scott.Sanner@nicta.com.au

first-order logic and probability, a long-standing goal of AI. Instantiating all ground atoms from the formulae in such a model induces a standard graphical model with symmetric, repeated potential structures for all grounding combinations.

To exploit these symmetries, lifted BP (LBP) approaches have been recently developed [Singla and Domingos, 2008; Kersting et al., 2009] to automatically group nodes and potentials of the graphical model into supernodes and superpotentials if they have identical computation trees (i.e., the tree-structured unrolling of the graphical model computations rooted at the nodes). LBP then runs a modified BP on this lifted (clustered) network. LBP has proved extremely fast at computing approximate marginal probability distributions and has yielded significant efficiency gains on important AI tasks such as link prediction, social network analysis, satisfiability and boolean model counting problems.

This paper makes a number of important and novel contributions to both the LBP and GaBP literature while demonstrating the powerful application of these techniques to important AI and novel lifted inference tasks: personalized PageRanks and Kalman filters. To start, we note that the core matrix inversion computation in both PageRank and Kalman filtering can be na¨ıvely solved by combining Shental et al.'s [2008] GaBP approach to solving linear systems with Kersting et al.'s [2009] color passing approach for LBP, yielding Lifted GaBP (LGaBP). In fact, this novel LGaBP approach - as we will show - already results in considerable efficiency gains. However, we can do considerably better.

Essentially, the computations in personalized PageRanks and Kalman filters require the LGaBP solution of several linear systems with only small changes to the evidence. In turn repeatedly constructing the lifted network for each new inference can be extremely wasteful, because the evidence changes little from one inference to the next. Hence, a less na¨ıve solution would exploit recent efficient approaches for updating the structure of an existing lifted network with small changes to the evidence [Nath and Domingos, 2010; Ahmadi et al., 2010]. In the inference stage, however, this solution would still run a modified LGaBP algorithm on each lifted network separately: symmetries across the inference tasks are not exploited. An investigation of the question of whether we can achieve additional efficiency gains by exploiting symmetries across the inference tasks leads to our main contribution: multi-evidence lifting.

In multi-evidence lifting, we first construct the ground networks for all inference tasks. We then run color passing on the union of these networks to compute the joint lifted network that automatically exploits symmetries across inference tasks. Finally, we run a modified message passing algorithm on the joint lifted network that simulates message passing on each ground network in parallel. Intuitively, this sacrifices space complexity for a lower time complexity, and the na¨ıve approach of lifting the joint network will not scale well to large problem sizes. Consequently, we develop an efficient sequential lifting variant that computes the joint lifted network by considering evidence sequentially rather than jointly. As our experiments show, multi-evidence LGaBP 1 and its sequential variant can yield significantly faster inference than na¨ıve LGaBP and GaBP on synthetic problems and the realworld problems of PageRank and Kalman filter computation.

We proceed as follows. After touching upon related work, we briefly review GaBP and color passing for LBP. Then, we introduce multi-evidence lifting, sketch its correctness, and present an efficient sequential lifting variant. Before concluding, we provide empirical results including the first lifted approaches to PageRank and Kalman filter computations.

2 RelatedWork

Recent years have witnessed a surge of interest in lifted probabilistic inference. Poole [2003], de Salvo Braz et al. [2005], and Milch et al. [2008] have developed lifted versions of variable elimination for discrete domains; Choi and Amir [2010] have extended these ideas to relational continuous models. These exact inference approaches are extremely complex and have only been applied to artificial domains to date. Moreover, these methods require a first-order logical specification of the model; multi-evidence lifting as presented here does not. Sen et al. [2009] presented a lifted (approximate) variable elimination approach based on bisimulation; in contrast to the previous approaches, it does not require a firstorder logical specification but is considerably complex. Arguably, the simplest and most efficient approximate lifted inference algorithms are based on the already mentioned LBP approaches. Motivated by Jaimovich et al. [2007], Singla and Domingos [2008] developed the first LBP variant requiring a Markov logic network as input. Kersting et al. [2009] generalized it to any graphical model over discrete, finite variables.

In contrast to LGaBP introduced here, all previous LBP approaches have been developed for discrete domains only. While in principle they can be applied to continuous domains through discretization, Choi and Amir [2010] have noted the precision of discretizations deteriorates exponentially in the number of random variables. Thus, discretization and application of LBP would be highly imprecise for large networks.

Finally, Nath and Domingos [2010] and Ahmadi et al. [2010] developed efficient algorithms for sequential lifting, where the structure of an existing lifted network is updated with incremental evidence changes. However, for inference, these algorithms run message passing independently on the lifted networks constructed for each evidence case. In contrast, the sequential version of multi-evidence lifting we present shares computation via the joint lifted network.

1 We focus here on matrix inversion, but multi-evidence lifting is generally applicable, also to discrete domains.

3 Lifted Gaussian Belief Propagation

In this section, we present a unified review of Gaussian belief propagation (GaBP) and lifted belief propagation (LBP) leading to lifted GaBP (LGaBP). We develop LGaBP in the context of solving linear systems that are key to our lifted PageRank and Kalman filtering applications presented later.

Many real world applications such as environmental sensor networks, information diffusion in social networks, and localization in robotics involve systems of continuous variables. One of the most fundamental problems encountered in these applications is solving linear systems of the form Ax = b where A ∈ Rn×n is a real-valued square matrix, and b ∈ Rn is real-valued column vector, and we seek the column vector x such that equality holds. As a running example, consider b = (0 0 1)t (where t denotes transpose) and

Shental et al. [2008] have shown how to translate this problem into a probabilistic inference problem, i.e., to solve a linear system of equations of size n we compute the marginals of the Gaussian variables x1, . . . , xn in an appropriately defined graphical model. Given the matrix A and the observation matrix b, the Gaussian density function p(x) ∼ exp(- 12 xtAx + btx) can be factorized according to the graph consisting of edge potentials ψij and self potentials φi as follows: p(x) ∝ ∏ni=1 φi(xi) ∏i,j ψij(xi, xj), where the potentials are ψij(xi, xj) := exp(- 12 xiAij xj ) and φi(xi) := exp(- 12 Aiix2i +bixi). The edge potentials ψij are defined for all (i, j) s.t. Aij > 0.

To solve the inference task, Shental et al. proposed to use Weiss et al.'s [2001] Gaussian BP (GaBP) which is a special case of continuous BP, where the underlying distribution is Gaussian. BP in Gaussian models gives simpler update formulas than the general continuous case and the message updates can directly be written in terms of the mean and precision. Since p(x) is jointly Gaussian, the messages are proportional to Gaussian distributions N(μij, P -1 ij ) with precision

for i ̸= j and ˜ Pii = Aii and ˜μii = bi/Aii. Here, N(i) denotes the set of all the nodes neighboring the ith node and N(i)\j excludes the node j fromN(i). All messages parameters Pij and μij are initially set to zero. The marginals are Gaussian probability density functions N (μi, P -1 i ) with precision Pi = ˜ Pii+∑k∈N(i) Pki and mean μi = P -1 i\j ( ˜ Pii ˜μii+ ∑k∈N(i) Pkiμki ). If the spectral radius of the matrix A is smaller than 1 then GaBP converges to the true marginal means (x = μ). We refer to [Shental et al., 2008] for details.

Although already quite efficient, many graphical models produce inference problems with symmetries not reflected in the graphical structure. LBP can exploit this structure by automatically grouping nodes (potentials) of the graphical model G into supernodes (superpotentials) if they have identical computation trees (i.e., the tree-structured unrolling of the graphical model computations rooted at the nodes). This compressed graph G is computed by passing around color signatures in the graph that encode the message history of each node. The signatures are initialized with the color of the self potentials, i.e., cs0i = φi and iteratively updated by cski = {csk-1 i }∪{[ψij, cs(ψk-1 j )]| j ∈ N(i)}. The algorithmic details of color passing are not important for this paper, we refer to [Kersting et al., 2009]. The key point to observe is that this very same process also applies to GaBP (viewing "identical" for potentials only up to a finite precision), thus leading to a novel LGaBP algorithm.

To continue our running example, let us examine computing the inverse of matrix A in Eq. (1) using LGaBP. We note that A-1 = [x1, . . . , xn] can be computed by solving Axi = ei for i = 1 . . . n, where ei is the ith basis vector - I = [e1, . . . , en] for the n × n identity matrix I. In our running example, this yields the respective lifted networks in Figs. 1(a-c). As one can see, for the evidence cases e1 and e2 there is no compression and lifted inference is essentially ground. All nodes get different colors for these cases (Figs. 1(a) and (b)). For the evidence case e3, however, variables x1 and x2 are assigned the same color by LGaBP (Fig. 1(c)). The final lifted graph G is constructed by grouping all nodes (potentials) with the same color (signatures) into supernodes (superpotentials), which are sets of nodes (potentials) that behave identical at each step of carrying out GaBP on G (Fig. 1(d)). On the lifted graph G, LGaBP then runs a modified GaBP. The modified messages simulate running GaBP on the original graph G. Following LBP, we have to pay special attention to the self-loops introduced by lifting that correspond to messages between different nodes of the same supernode. Reconsider our running example. As shown in Fig. 1(d), there is a self-loop for the supernode {x1, x2}. In general, there might be several of them for each supernode and we assume that they are indexed by k. To account for the self-loops and in contrast to GaBP, we introduce "selfmessages" P k ii = -A2ii (P k i\i )-1 and μkii = -P -1 ij Aiiμki\i with

As i is now a neighbor of itself, the termN(i) \ i is required. Furthermore, ♯lij - also given in Fig. 1(d) - are counts that encode how often the message (potential) would have been used by GaBP on the original network G. Using these counts we can exactly simulate the messages that would have been sent in the ground network. Messages between supernode i and j, i ̸= j, are modified correspondingly:

where N(i) \ i, j denotes all neighbours of node i without i and j. Adapting the arguments from [Kersting et al., 2009], the following LGaBP correctness theorem can be proved:

Theorem 3.1. Given a Gaussian model G, LGaBP computes the minimal compressed lifted model, and running modified GaBP on G produces the same marginals as GaBP on G.

4 Multi-Evidence Lifting

Both applications considered in this paper - lifted PageRank and Kalman filtering - require the inversion of very large, structured matrices. As shown previously, this task can be reduced to the problem of solving several linear systems with GaBP - more precisely, calling GaBP multiple times, each time with a different evidence case.

Returning to our running example, inverting A from Eq. (1) using GaBP results in three graphical models of size 3/9 (nodes/potentials). Given the recent success of LBP approaches, we ask "can we do better?" A first attempt to affirmatively answer the question is to simply replace GaBP with LGaBP for each evidence case ei as illustrated in the three lifted graphical models of Figs. 1(a-d). In general, this single-evidence lifting approach is illustrated in Fig. 2(a). Due to lifting, we can hope to greatly reduce the cost of inference in each iteration. For our running example, this results in two ground networks both of size 3/9 and one lifted network of size 2/5 shown respectively in Figs. 1(a,b) and (d). Thus, the total size (sum of individual sizes) drops to 8/23 This LGaBP approach - as we will show in our experiments

- can already result in considerable efficiency gains. However, we can do even better.

Repeatedly constructing the lifted network for each new evidence case can be wasteful when symmetries across multiple evidence cases are not exploited (e.g., the common 0's amongst all ei). Compare for example the graphs depicted in Fig. 1(a) and (b). These two networks are basically symmetric which is not exploited in the single-evidence case.They stay essentially ground if they are processed seperately. To overcome this, we propose multi-evidence lifting (as illustrated in Fig. 2(b) for inverting a matrix):

compute the graphical models of each evidence case, form their union, and run LGaBP on the resulting joint graphical model.

This automatically employs the symmetries within and across the evidence cases due to Theorem 3.1. In our running example, we get a single lifted graph of size 5/14. Intuitively, multi-evidence lifting only produces (in this example) one of the two ground networks and hence consists of the union of the networks shown in Figs. 1(a) and (d). This is clearly a reduction compared to LGaBP's size of 8/23.

However, there is no free lunch. Multi-evidence lifting sacrifices space complexity for a lower time complexity. Inverting a n × n matrix may result in a joint ground graphical model with n2 nodes (n nodes for each of the n systems of linear equations) and O(n3 ) edges (O(n2 ) edges for each of the n systems of linear equations; edges are omitted if Aij = 0). This makes multi-evidence essentially intractable for large n. For instance, already for n > 100 we have to deal with millions of edges, easily canceling the benefits of lifted inference. We develop an efficient sequential multi-evidence lifting approach that computes the joint lifted network by considering one evidence case after the other (Fig. 2(c)).

Indeed, one is tempted to employ one of the efficient algorithms recently presented for updating the structure of an existing lifted network with incremental changes to the evidence to solve the problem [Nath and Domingos, 2010; Ahmadi et al., 2010]. While employing the symmetries in the graphical model across multiple evidence cases for the lifting, in the inference stage they need to construct a separate lifted network for each evidence case and run a modified message passing algorithm on each lifted network separately. Thus, symmetries across evidence cases are missed.

5 Sequential Multi-Evidence Lifting

We seek a way to efficiently construct the joint lifted network while still being able to lift across multiple evidence cases. To do this, we can modify Ahmadi et al.'s [2010] sequential single-evidence lifting to the multi-evidence case. Ahmadi et al. give a clear characterization of the core information required for sequential clamping for lifted message passing, namely the shortest-paths connecting the variables in the network which resemble the computation paths along which the nodes communicate in the network.

Thus, to be able to adapt the lifted network for incoming evidence in the single-evidence case, we compute in a first step the set of shortest paths connecting any two nodes in the graph. Now, when there is new evidence for a node, the adapted lifted network is computed as a combination of the nodes' initial coloring, i.e. the lifting without evidence, and the set of shortest paths to the nodes in our evidence.

Algorithm 1 describes how we can adapt this to the multievidence case. Intuitively, we would like to view each Axi = ei (i = 1, 2, . . . , n) as conditioning an initial network on node i and efficiently computing its contribution to the resulting lifted joint network directly from the initial one. But what should be the initial network? It is not provided by the task itself. Thus, to be able to efficiently find the lifted network structure, we propose to introduce an additional system of linear equations, namely the one with no evidence: Ax = 0 (Alg.1, line 1). Indeed, it is not needed in the inversion task per se but it allows us to significantly speed up the multievidence lifting process. Intuitively, each ei only differs from 0 in exactly one element so it serves as the basis for lifting all subsequent networks. To do this, we compute the path colors for all pairs of nodes (line 2) to know how it affects the other nodes when conditioning on a variable i and the initial lifting without evidence (line 3). The lifted graph Hi

Input: Matrix A Construct network G0 for Ax = 0; 1 Compute path color matrix PC on G0; 2 Lift G0 to obtain lifted network H0; 3 foreach unit vector ei do 4 colors(Hi) = colors(H0); 5 evidence = {i:Aii}; 6 repeat 7 colors(Hi) = newColor (H0, PC, evidence); 8 Add nodes that have changed color to evidence; 9 until colors(Hi) does not change ; 10 if Hi is previously unseen then 11 Add Hi to joint lifted network H{1,..,i-1} 12 else 13 Bookmark the corresponding index j 14 15 Run modified GaBP on joint lifted network H{1,..,n}; 16 return X = (x1, x2, . . . , xn), the inverse of A; 17

for the ith system of linear equations Axi = ei can now be adaptively computed by combining the initial lifting and the path colors to node i (line 8). The combination is essentially an elementwise concatenation of the two respective vectors.

Consider computing the lifted network for Ax3 = e3 for our running example. When we have no evidence the nodes x1 and x2 are clustered together, and x3 is in a separate cluster. Thus, we obtain an initial color vector C = (0, 0, 1). Since we want to compute the network conditioned on x3 we have to combine this initial clustering C with the path colors with respect to x3, PCx3 = ({3, 5}, {3, 5}, ∅) = (0, 0, 1). To obtain the lifted network conditioned on x3 we have to (1) do an elementwise concatenation (in the following depicted by ⊕) of the two vectors and (2) interpret the result as a new color vector: H3 = (0, 0, 1)⊕(0, 0, 1) =(1) (00, 00, 11) =(2) (2, 2, 3). Since only the shortest paths are computed, adapting the colors has to be performed iteratively to let the evidence propagate. For further details on adapting the color vector (line 8) we refer to [Ahmadi et al., 2010].

Moreover, we can implement a type of memoization when we perform the lifting in this fashion. Because we know each resulting lifted network Hi in advance, we can check whether an equivalent lifted network was already constructed: if the same color pattern exists already, we simply do not add Hi and instead only bookmark the correspondence of nodes (line 11-14) 2 . This does not affect the counts at all and, hence, still constructs the correct joint lifted network. This argument together with the correctness of the sequential singleevidence lifting and multi-evidence lifting effectively proves the correctness of sequential multi-evidence lifting:

Theorem5.1. Sequential multi-evidence lifting computes the same joint lifted model as in the batch case. Hence, running the modified GaBP on it produces the same marginals.

2 This is not as hard as solving (sub)graph-isomorphisms. We only have to check whether the color pattern of Hi was previously seen. If so, the result has already been memoized.

6 Experimental Evaluation

Our intention here is to investigate the following questions: Q1 Can LGaBP be faster than GaBP? Q2 Can multievidence lifting produce smaller inference problems than single-evidence lifting? Q3 Does sequential multi-evidence lifting scale better than just multi-evidence lifting.

We implemented all variants in Python using the LIBDAI library 3 and evaluated their performances on (a) random matrices, (b) PageRank computations of graphs induced by a Markov logic network (MLN), and (c) Kalman filtering problems. The GaBP variants ran using parallel message updates, no damping and convergence threshold ϵ = 10-8 . They all converged within ϵ of the correct solution.

Inverting Random Matrices: We generated a random matrix R ∈ R20×20 with Rij ∈ [0, 1] and added 10 to the diagonal to ensure non-singularity. Using R, we constructed a diagonal matrix with 1, 2, 4 and 8 blocks. On each of the matrices we run all four algorithms measuring the number of potentials created and total messages sent (including coloring messages), and the CPU time. Figs. 3(a)-(c) show the results averaged over 10 random reruns. As one can see, SMELGaBP < ME-LGaBP < LGaBP < GaBP in terms of the number of messages sent (b) and CPU-time (sec.) (c). Furthermore, (sequential) ME-LGaBP and create - as expected - the same number of potentials and significantly less than (L)GaBP (b).

Lifted Personalized PageRank: Recall the problem of ranking web pages already touched upon in the introduction. In a nutshell, a Markov chain transition matrix M is constructed out of a given graph G. Let A be the n×n adjanceny matrix of G, that is Aij = 1 if there is an edge from vertex j to vertex i and zero otherwise. PageRank now constructs the probability transition matrix M by adding 1/n to all entries of A and renormalizes each row of A to sum to 1. Furthermore, a prior probability v can be taken to weight the results. The personalized PageRank can then be computed by solving the following system of linear equations (I -αM)x = v where α trades off speed of convergence with the accuracy of the solution and I is the identity matrix.

In several PageRank applications, however, one needs to know, in addition to the rank of a given page, which pages or sets of pages contribute most to its rank. These PageRank contributions have been used for link spam detection and in the classification of web pages. The contribution that a vertex v makes to the PageRank of a vertex u is defined rigorously in terms of personalized PageRank for all vertices, i.e., for vi = ei, i = 1, 2, . . . , n. So, we are interested in PRMα - the matrix whose u-th row is the personalized PageRank vector of u. The PageRank contribution of u to v is then the entry (u, v) of this matrix. This, however, is the inverse of (I - αM) and we can make use of multi-evidence lifting.

We computed PRM0.9 for the ground network induced by the Friends & Smokers Markov logic network [Richardson and Domingos, 2006]. We varied the number of people in the domain, namely 3, 5, 10. Figs. 3 (d)-(f) show the (d) the total number of (lifted) potentials (e) total numbers of messages sent and (f) the total CPU times (sec.) per PRM0.9 computation averaged over 10 runs. Again one can see, SME-LGaBP < ME-LGaBP < LGaBP < GaBP. In particular, we see the benefit of multi-evidence lifting. The number of generated potentials saturates for more than 3 people whereas singleevidence lifting generates more and more potentials.

3 http://www.libdai.org/

Lifted Kalman Filter: Kalman Filtering is a computational tool with widespread application in robotics, financial and weather forecasting, and environmental engineering. Given observation and state transition models, the Kalman Filter (KF) recursively estimates the state x ∈ Rn of a discrete-time controlled process that is governed by the linear stochastic difference equation xk = Axk-1+Buk-1+wk-1 with a measurement z ∈ Rm that is zk = Hxk + vk . Here, wk and vk represent the process and measurement noise (respectively) and are assumed to be independent (of each other), white, and with normal density, i.e., p(w) ∼ N(0, Q) and p(v) ∼ N(0,R). The matrix A relates consecutive states xk-1 and xk. The matrix B relates the optional control input u to the state, and H relates the state to the measurement z. In practice, the matrices A,B,H,Q and R might change with each time step or measurement, however, here we assume they are constant.

Due to space limitations, we cannot go into details but instead refer to, e.g, [Thrun et al., 2005], and note that the main step of the KF consists of computing the Kalman gain: Kk = P-k Ht (HP-k Ht + R)-1 where P-k = APk-1At + Q. Thus, the KF requires to invert a matrix at every time step allowing us to apply multi-evidence lifting.

In our experiments, we tracked 10 people randomly spread among k groups. Each group had its own (local) motion model (mm). We varied the number of groups: 1 (all people have the same mm) , 5 (two people have the same mm), and 10 (everybody has its own mm). Figs. 4 shows (a) the total number of (lifted) potentials, (b) the total number of messages sent and (c) the CPU times (sec.) averaged over all matrix inversion tasks in a Kalman filtering over 10 steps (GaBP is omitted). It clearly shows: the larger the number of groups, the lower the gain of (sequential) multi-evidence lifting. For 10 groups, when there are no mm symmetries - motion symmetries ratio 0 - across people, single-evidence lifting is faster. However, when we have symmetries across evidence cases - 5 and 1 groups, i.e., ratios of 0.5 and 1.0 - ME lifting significantly outperforms single-evidence lifting.

The Discrete Case: Indeed, we introduced multi-evidence lifting in the context of GaBP. It is, however, also applicable in discrete cases. To validate its generality, we peformed parameter estimation - another natural case for multievidence lifting - in discrete domains. For the Friends & Smokers MLN with ten people. we maximized the conditional marginal log-likelihood (CMLL) using scaled conjugate gradient (SCG) for 10 data cases sampled from the joint distribution. Here, lifted BP (LBP) took 0.089 seconds for a single iteration - already a reduction compared to BP's 0.1 sec. - but ME-LBP exploits the additional symmetries and in turn took only 0.049 sec.

All experimental results together clearly answer questions Q1-Q3 affirmatively.

7 Conclusions

In this paper, we proposed multi-evidence lifting for belief propagation in graphical models that exploits symmetries within and across different evidence cases. To avoid the cubic space requirement of a na¨ıve realization, we then presented a sequential algorithm for efficiently computing the multi-evidence lifted network. The experimental results on two novel tasks for lifted inference, namely computing PageRank contributions and Kalman filter updates show that multi-evidence lifting provides substantial speedups - up to two orders of magnitude - over standard lifting, making it applicable to a wide range of problems.

Indeed, much remains to be done. Since lifting of GaBP itself and the exploitation of multi-evidence sequential lifting for solving large linear systems is a major advance, further experimentation and application of these techniques to other tasks requiring the solution of linear systems and matrix inversion is one important direction. In addition, exploring its usefulness in other AI and machine learning tasks is another interesting avenue for future work; promising candidates are lifted variants of ridge regression, least-squares support vector machines, and linear program solvers.

Acknowledgments: The authors thank the anonymous reviewers for their comments. BA and KK were supported by the Fraunhofer ATTRACT fellowship STREAM and by the European Commission under contract number FP7-248258First-MM. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.