Smart Contract Interactions in Coq

We present a model/executable specification of smart contract execution in Coq. Our formalization allows for inter-contract communication and generalizes existing work by allowing modelling of both depth-first execution blockchains (like Ethereum) and breadth-first execution blockchains (like Tezos). We represent smart contracts programs in Coq's functional language Gallina, enabling easier reasoning about functional correctness of concrete contracts than other approaches. In particular we develop a Congress contract in this style. This contract -- a simplified version of the infamous DAO -- is interesting because of its very dynamic communication pattern with other contracts. We give a high-level partial specification of the Congress's behavior, related to reentrancy, and prove that the Congress satisfies it for all possible smart contract execution orders.

Introduction
Since Ethereum, blockchains make a clear separation between the consensus layer and the execution of interacting smart contracts. In Ethereum's Solidity language contracts can arbitrarily call into other contracts as regular function calls. Modern blockchains further separate the top layer in an execution layer and a contract layer. The execution layer schedules the calls between the contracts and the contract layer executes individual programs. The choice of execution order differs between blockchains. For example, in Ethereum the execution is done in a synchronous (or depth first) order: a call completes fully before the parent continues, and the parent is able to observe its result. Tezos and Scilla use a breadth first order instead, where observing the result is not possible.
We provide 1 a model/executable specification of the execution and contract layer of a third generation blockchain in the Coq proof assistant. We use Coq's embedded functional language Gallina to model contracts and the execution layer. This language can be extracted to certified programs in for example Haskell or Ocaml. Coq's expressive logic also allows us to write concise proofs. The consensus protocol provides a consistent global state which we treat abstractly in our formalization.
We work with an account-based model. We could also model the UTxO model by converting a list of UTxO transactions to a list of account transactions [12]. Like that work, we do not model the cryptographic aspects, only the accounting aspects: the transactions and contract calls.
Section 2 describes the implementation of the execution layer in Coq. In Section 3 we provide a simple principled specification for the Congress. By using such specifications one avoids having to deal with reentrancy bugs in a post-hoc way. Section 4 discusses related and future work.

Basic assumptions
Our goal is to model execution of smart contracts. To do so we will require some basic operations that are to be used both by smart contracts and when specifying our semantics. We do this with a typeclass in Coq: We require a countable Address type with a clear separation between addresses belonging to contracts and to users. While this separation is not provided in Ethereum its omission has led to exploits before 2 and we view it as realistic that future blockchains allow this. Other blockchains commonly provide this by using some specific format for contract addresses, for example, in Bitcoin such pay-to-script-hash addresses always start with 3. All semantics and smart contracts will be abstracted over an instance of this type, so in the following sections we will assume we are given such an instance.

Smart Contracts
We will consider a pure functional smart contract language. Instead of modelling the language as an abstract syntax tree in Coq, as in [2], we model individual smart contracts as records with (Coq) functions.
Local state. It is not immediately clear how to represent smart contracts by functions. For one, smart contracts have local state that they should be able to access and update during execution. In Solidity, the language typically used in Ethereum, this state is mutable and can be changed at any point in time. It is possible to accomplish something similar in pure languages, for example by using a state monad, but we do not take this approach. Instead we use a more traditional approach where the contract takes as input its state and returns an updated state which is similar to Liquidity. Different contracts will typically have different types of states. A crowdfunding contract may wish to store a map of backers in its state while an auction contract would store information about ongoing auctions. To facilitate this polymorphism we use an intermediate storage type called SerializedValue. We define conversions between SerializedValue and primitive types like booleans and integers plus derived types like pairs, sums and lists. Additionally we provide Coq tactics that can automatically generate conversions for custom user types like inductives and records. This allows conversions to be handled implicitly and mostly transparently to the user.
Inter-contract communication. In addition to local state we also need some way to handle inter-contract communication. In Solidity contracts can arbitrarily call into other contracts as regular function calls. This would once again be possible with a monadic style, for example by the use of a promise monad where the contract would ask to be resumed after a call to another contract had finished. To ease reasoning we choose a simpler approach where contracts return actions that indicate how they would like to interact with the blockchain, allowing transfers, contract calls and contract deployments only at the end of (single steps of) execution. The blockchain will then be responsible for scheduling these actions in what we call its execution layer.
With this design we get a clear separation between contracts and their interaction with the chain. That such separations are important has been realized before, for instance in the design of Michelson and Scilla [9]. Indeed, a "tail-call" approach like this forces the programmer to update the contract's internal state before making calls to other contracts, mitigating by construction reentrancy issues such as the infamous DAO exploit.
Thus, contracts will take their local state and some data allowing them to query the blockchain. As a result they then optionally return the new state and some operations (such as calls to other contract) allowing inter-contract communication. Tezos' Michelson language follows a similar approach.
The Ethereum model may be compared to object-oriented programming. Our model is similar to the actor model as contracts do not read or write the state of another contract directly, but instead communicate via messages instead of shared memory. Liquidity and the IO-automata-based Scilla use similar models.
The contract. Smart contracts are allowed to query various data about the blockchain. We model this with a data type: We allow contracts to access basic details about the blockchain, like the current chain height, slot number and the finalized height. The slot number is meant to be used to track the progression of time; in each slot, a block can be created, but it does not have to be. The finalized height allows contracts to track the current status of the finalization layer available in for example the Concordium blockchain [5]. This height is different from the chain height in that it guarantees that blocks before it can not be changed. We finally also allow the contract to access balances of accounts as is common in other blockchains. In sum, the following data types model the contracts: → option SerializedValue (* message *) → option (SerializedValue * list ActionBody)).
Here the ContractCallContext provides the contract with information about the transaction that resulted in its execution. It contains the source address (ctx_from), the contract's own address (ctx_contract_address) and the amount of money transferred (ctx_amount). The ActionBody type represents operations that interact with the chain. It allows for messageless transfers (act_transfer), calls with messages (act_call), and deployment of new contracts (act_deploy). The contract itself is two functions. The init function is used when a contract is deployed to set up its initial state, while the receive function will be used for transfers and calls with messages afterwards. They both return option types, allowing the contract to signal invalid calls or deployments. The receive function additionally returns a list of ActionBody that it wants to be scheduled, as we described earlier. This data type does not contain a source address since it is implicitly the contract's own address. Later, we will also use a representation where there is a source address; we call this type Action: Record Action := { act_from : Address; act_body : ActionBody; }.
This type resembles what is normally called a transaction, but we make a distinction between the two. An Action is a request by a contract or external user to perform some operation. When executed by an implementation, this action will affect the state of the blockchain in some way. It differs from transactions since act_deploy does not contain the address of the contract to be deployed. This models that it is the implementation that picks the address of a newly deployed contract, not the contract making the deployment. We will later describe our ActionEvaluation type which captures more in depth the choices made by the implementation while executing an action.
The functions of contracts are typed using the SerializedValue type. This is also the reason for the name WeakContract. This makes specifying semantics simpler, since the semantics can deal with contracts in a generic way (rather than contracts abstracted over types). However, this form of "string-typing" makes things harder when reasoning about contracts. For this reason we provide a dual notion of a strong contract, which is a polymorphic version of contracts generalized over the setup, state and message types. Users of the framework only need to be aware of this notion of contract, which does not contain references to SerializedValue at all.
One could also imagine an alternative representation using a dependent record of setup, state and message types plus functions over those types. However, in such a representation it is unclear how to allow contracts to send messages to other contracts when the blockchain itself does not have any knowledge about concrete contracts.

Semantics of the execution layer
Environments. The Chain type shown above is merely the contract's view of the blockchain and does not store enough information to allow the blockchain to run actions. More specifically we need to be able to look up information about currently deployed contracts like their functions and state. We augment the Chain type with this information and call it an Environment: It is not hard to define functions that allow us to make updates to environments. For instance, inserting a new contract is done by creating a new function that checks if the address matches and otherwise uses the old map. In other words we use simple linear maps in the semantics. In similar ways we can update the rest of the fields of the Environment record.
Evaluation of actions. When contracts return actions the execution layer will need to evaluate the effects of these actions. We define this as a "proofrelevant" relation ActionEvaluation in Coq, with type Environment → Action → Environment → list Action → Type. This relation captures the requirements and effects of executing the action in the environment. It is "proof-relevant", meaning that the choices made by the execution layer can be inspected. For example, when an action requests to deploy a new contract, the address selected by the implementation can be extracted from this relation.
We define the relation by three cases: one for transfers of money, one for deployment of new contracts, and one for calls to existing contracts. To exemplify this relation we give its formal details for the simple transfer case below: | eval_transfer : forall {pre : Environment} {act : Action} {new_env : Environment} (from to : Address) (amount : Amount), amount ≤ account_balance pre from → address_is_contract to = false → act_from act = from → act_body act = act_transfer to amount → EnvironmentEquiv new_env (transfer_balance from to amount pre) → ActionEvaluation pre act new_env [] In this case the sender must have enough money and the recipient cannot be a contract. When this is the case a transfer action and the old environment evaluate to the new environment where the account_balance has been updated appropriately. Finally, such a transfer does not result in more actions to execute since it is not associated with execution of contracts. Note that we close the evaluation relation under extensional equality (EnvironmentEquiv).
We denote this relation by the notation σ, a ⇓ (σ ′ , l). The intuitive understanding of this notation is that evaluating the action a in environment σ results in a new environment σ ′ and new actions to execute l.
Chain traces. The Environment type captures enough information to evaluate actions. We further augment this type to keep track of the queue of actions to execute. In languages like Solidity this data is encoded implicitly in the call stack, but since interactions with the blockchain are explicit in our framework we keep track of it explicitly. We now define what it means for the chain to take a step. Formally, this is defined as a "proof-relevant" relation ChainStep of type ChainState → ChainState → Type. We denote this relation with the notation (σ, l) → (σ ′ , l ′ ), meaning that we can step from the environment σ and list of actions l to the environment σ ′ and list of actions l ′ . We give this relation as simplified inference rules: The step-block rule allows the addition of a new block (b) containing some actions (acts) to execute. We require that the block is valid for the current environment (the "b valid for σ" premise), meaning that it needs to satisfy some well-formedness conditions. For example, if the chain currently has height n, the next block added needs to have height n + 1. There are other well-formedness conditions on other fields, such as the block creator, but we omit them here for brevity. Another condition is that all added actions must come from users (the "acts from users" premise). This models the real world where transactions added in blocks are "root transactions" from users. This condition is crucial to ensure that transfers from contracts can happen only due to execution of their associated code. When the premises are met we update information about the current block (such as the current height and the balance of the creator, signified by the add block function) and update that the queue now contains the actions that were added.
The step-action rule allows the evaluation of the first action in the queue, replacing it with the resulting new actions to execute. This new list (l in the rule) is concatenated at the beginning, corresponding to using the queue as a stack. This results in a depth-first execution order of actions. The step-permute rule allows an implementation to use a different order of reduction by permuting the queue at any time. For example, it is possible to obtain a breadth-first order of execution by permuting the queue so that newly added events are in the back. In this case the queue will be used like an actual FIFO queue.
Building upon steps we can further define traces as the proof-relevant reflexive transitive closure of the step relation. In other words, this is a sequence of steps where each step starts in the state that the previous step ended in. Intuitively the existence of a trace between two states means that there is a semantically correct way to go between those states. If we let ε denote the empty environment and queue this allows us to define a concept of reachability. Formally we say a state (σ, l) is reachable if there exists a trace starting in ε and ending in (σ, l). Generally, only reachable states are interesting to consider and most proofs are by induction over the trace to a reachable state.

Building blockchains
We connect our semantics to an executable definition of a blockchain with a typeclass in Coq: A chain builder is a dependent record consisting of an implementation type (builder_type) and several fields using this type. It must provide an initial builder, which typically would be an empty chain, or a chain containing just a genesis block. It must be convertible to an environment allowing to query information about the state. It must define a function that allows addition of new blocks. Finally, the implementation needs to be able to give a trace showing that the current environment is reachable with no more actions left in the queue to execute. This trace captures a definition of soundness, since it means that the state of such a chain builder will always be reachable.
Instantiations. We have implemented two instances of the ChainBuilderType typeclass. Both of these are based on finite maps from the std++ library used by Iris [4] and are thus relatively efficient compared to the linear maps used to specify the semantics. The difference in the implementations lies in their execution model: one implementation uses a depth-first execution order, while the other uses a breadth-first execution order. The former execution model is similar to the EVM while the latter is similar to Tezos and Scilla.
These implementations are useful as sanity checks but they also serve other useful purposes in the framework. Since they are executable they can be used to test concrete contracts that have been written in Coq. This involves writing the contracts and executing them using Coq's Compute vernacular to inspect the results. In addition, they can also be used to give counter-examples to properties. In the next section we will introduce the Congress contract, and we have used the depth-first implementation of our semantics to formally show that this contract with a small change can be exploited with reentrancy.

Case: Congress -a simplified DAO
In this section we will present a case study of implementing and partially specifying a complex contract in our framework.
The Congress contract Wang [11] gives a list of eight interesting Ethereum contracts. One of these is the Congress in which members of the contract vote on proposals. Proposals contain transactions that, if the proposal succeeds, are sent out by the Congress. These transactions are typically monetary amounts sent out to some address, but they can also be arbitrary calls to any other contract.
We pick the Congress contract because of its complex dynamic interaction with the blockchain and because of its similarity to the infamous DAO contract that was deployed on the Ethereum blockchain and which was eventually hacked by a clever attacker exploiting reentrancy in the EVM. The Congress can be seen as the core of the DAO contract, namely the proposal and voting mechanisms.
We implement the logic of the Congress in roughly 150 lines of Coq code. The type of messages accepted by the Congress can be thought of as its interface since this is how the contract can be interacted with: The Congress has an owner who is responsible for managing the rules of the Congress and the member list. By default, we set this to be the creator of the Congress. The owner can transfer his ownership away with the transfer_ownership message. It is possible to make the Congress its own owner, in which case all rule changes and modifications to the member list must happen through proposals (essentially making the Congress a democracy).
Anyone can use the create_proposal and finish_proposal messages. We allow proposals to contain any number of actions to send out, though we restrict the actions to only transfers and contract calls (i.e. no contract deployments). This restriction is necessary because deployments would require the state of the Congress to contain the contracts to deploy. Since contracts are functions in our shallow embedding this would require storing higher order state which we do not allow in the framework. This is a downside to the shallow embedding -with a deep embedding like [2], the code could be stored as an AST or bytes.
The rules of the Congress specify how long proposals need to be debated. During this period, members of the Congress have the ability to vote on the proposal. Once debated, a proposal can be finished and the Congress will remove it from its internal storage and send out its actions if it passed.
A partial specification The DAO vulnerability was in reward payout code in which a specially crafted contract could reenter the DAO causing it to perform actions an unintended number of times. Specifically, the attacker was able to propose a so-called split and have the original DAO transfer a disproportionate amount of money to a new DAO contract under his control. Congress does not allow splits, but the same kind of bug would be possible in code responsible for carrying out proposals.
Previous research such as [3] has focused on defining this kind of reentrancy formally. Such (hyper-)properties are interesting, but they also rely heavily on the benefit of hindsight and their statements are complex and hard to understand. Instead we would like to come up with a natural specification for the Congress that a programmer could reasonably have come up with, even without knowledge of reentrancy or the exploit. Our goal with this is to apply the framework in a very concrete setting.
The specification we give is based on the following observation: any transaction sent out by the Congress should correspond to an action that was previously created with a create_proposal message. This is a temporal property because it says something about the past whenever an outgoing transaction is observed. Temporal logic is not natively supported by Coq, so this would require some work. Therefore we prefer a similar but simpler property: the number of actions in previous create_proposal messages is always greater than or equal to the total number of transactions the Congress has sent out. Our main result about the Congress is a formal proof that this always holds after adding a block: This result states that, after adding a block, any address at which a Congress contract is deployed satisfies the property previously described. The number of actions created in previous create_proposal messages is calculated by function num_acts_created_in_proposals. The incoming_txs and outgoing_txs functions are general functions that finds transactions (evaluation of actions) in a trace. In this sense the property treats the contract as a black box, stating only things about the transactions that have been observed on the blockchain. This is not a full specification of the behavior of the Congress but proving this property can help increase trust in the Congress. In particular it would not have been provable in the original DAO contract because of the reentrancy exploit where the DAO sent out an unbounded number of transactions. Note also that we do not want to exclude reentrancy entirely: indeed, in the situation where the Congress is its own owner reentrancy is required for changing rules and the member list.
We prove the property by generalizing it over the following data: -The internal state of the contract; more specifically, the current number of actions in proposals stored in the internal state.
-The number of transactions sent out by the Congress, as before.
-The number of actions in the queue where the Congress is the source.
-The number of actions created in proposals, as before.
This results in a stronger statement from which the original result follows. The key observations are that 1. When a proposal is created, the number of actions created in proposals goes up, but so does the number of actions in the internal state of the Congress.
2. When a proposal is finished, the number of actions in the internal state goes down, but the number of actions in the queue goes up accordingly (assuming the proposal was voted for). In other words, actions "move" from the Congress's internal state to the queue.
3. When an outgoing transaction appears on the chain it is because an action moved out of the queue. Especially observation 3 is interesting. It allows us to connect the evaluation of a contract in the past to its resulting transactions on the chain, even though these steps can be separated by many unrelated steps in the trace.
The proof of the stronger statement is straightforward by inducting over the trace. When deploying the Congress we need to establish the invariant which boils down to proving functional correctness of the init function and the use of some results that hold for contracts which have just been deployed (for instance, such contracts have not made any outgoing transactions). On calls to the Congress the invariant needs to be reestablished, which boils down to proving functional correctness of the receive function. Crucially, we can reestablish the invariant because the implementation of the Congress clears out proposals from its state before the actions in the proposal are evaluated (the DAO was vulnerable because it neglected to do this on splits).

Conclusions
We have formalized the execution model of blockchains in Coq and used our formalization to prove formally a result about a concrete contract. Our formalization of blockchain semantics is flexible in that it accounts both for depth-first and breadth-first execution order, generalizing existing blockchains and previous work, while remaining expressive enough to allow us to prove results about complex contracts. We showed for a Congress -a simplified version of the DAO, which still has a complex dynamic interaction pattern -that it will never send out more transactions than have been created in proposals. This is a natural property that aids in increasing trust that this contract is not vulnerable to reentrancy like the DAO.
Related work Both Simplicity [7] and Scilla [9] are smart contract languages with an embedding in Coq. Temporal properties of several smart contracts have been verified in Scilla [10], although our Congress contract is more complex than the contracts described in that paper. We are unaware of an implementation of such a contract in Scilla. Scilla, as an intermediate language which includes both a functional part and contract calls, uses a CPS translation to ensure that every call to another contract is done as the last instruction. In our model, the high-level language and the execution layer are strictly separated.
The formalization of the EVM in F* [3] can be extracted and used to run EVM tests to show that it is a faithful model of the EVM. However, they do not prove properties of any concrete contracts. Instead they consider classes of bugs in smart contracts and try to define general properties that prevent these. One of these properties, call integrity, is motivated by the DAO and attempts to capture reentrancy. Intuitively a contract satisfies call integrity if the calls it makes cannot be affected by code of other contracts. VerX [8] uses temporal logic and model checking to check a similar property. Such statements are not hard to state in our framework given Coq's expressive logic, and it seems this would be an appropriate property to verify for the Congress. However, even a correct Congress does not satisfy this property, since it is possible for called contracts to finish proposals which can cause the Congress to perform calls. This property could potentially be proven in a version of the Congress that only allowed proposals to be finished by humans, and not by contracts.
Future work More smart contracts are available in Wang's PhD thesis [11] and specifying these to gain experience with using the framework will help uncover how the framework itself should be improved. In this area it is also interesting to consider more automatic methods to make proving more productive. For example, temporal logics like LTL or CTL can be useful to specify properties on traces and model checking these can be automated; see e.g. [8].
Finally, while our current framework is inspired by and generalizes existing blockchains, there is still more work to be done to get closer to practical implementations. Gas is notoriously difficult to deal with in our shallow embedding because tracking costs of operations can not be done automatically. However, perhaps a monadic structure can be used here [6]. We have connected our work with a deep embedding of a functional language [1] and explored pros and cons of shallow and deep embeddings in that work. We plan to use this deep embedding to explore reasoning about gas. In the other direction it is interesting to consider extraction of the execution layers we have shown to satisfy our semantics and extraction of verified contracts into other languages like Liquidity, Oak or Solidity.


extfieldsofstudy:
Computer Science
Mathematics

text:
Network Topology Inference Using Information Cascades with Limited Statistical Knowledge

We study the problem of inferring network topology from information cascades, in which the amount of time taken for information to diffuse across an edge in the network follows an unknown distribution. Unlike previous studies, which assume knowledge of these distributions, we only require that diffusion along different edges in the network be independent together with limited moment information (e.g., the means). We introduce the concept of a separating vertex set for a graph, which is a set of vertices in which for any two given distinct vertices of the graph, there exists a vertex whose distance to them are different. We show that a necessary condition for reconstructing a tree perfectly using distance information between pairs of vertices is given by the size of an observed separating vertex set. We then propose an algorithm to recover the tree structure using infection times, whose differences have means corresponding to the distance between two vertices. To improve the accuracy of our algorithm, we propose the concept of redundant vertices, which allows us to perform averaging to better estimate the distance between two vertices. Though the theory is developed mainly for tree networks, we demonstrate how the algorithm can be extended heuristically to general graphs. Simulation results suggest that our proposed algorithm performs better than some current state-of-the-art network reconstruction methods.

I. INTRODUCTION
Information is being propagated across networks, such as online social networks, with increasing speed owing to increased network connectivity. There has been recent increased interest to study the spread or diffusion of information, influence, or infections across a network. For example, information dynamics and social learning have been investigated in [1]- [7], most of which assume knowledge of the network structure. Finding the sources of an infection diffusing in a network has been investigated in various works, including [8]- [16]. Most of these efforts again assume that the underlying network structure is known. In many practical applications, knowledge of the network structure may not be readily available, and only the infection times of the nodes may be known. A goal of interest is to infer the network structure based only on this set of infection times, and possibly also limited a priori statistical information or assumptions.
In this paper, we consider the inference of a network topology based on knowledge of the time each vertex in the network receives a piece of information, when an information diffusion is initiated from a known source vertex. More precisely, the network is modeled by an undirected graph G = (V, E), with V the set of vertices and E the set of edges. A source vertex initiates an information diffusion, where the information is spread from an "infected" vertex to its neighbors stochastically along the edges connecting them. The time at which each vertex of G receives the information is observed. We call this the infection time of the vertex, and a collection of infection times with their corresponding source vertex a cascade. We wish to use these information cascades to estimate the connections among vertices of the graph.
The network inference problem has been investigated under various assumptions. For example, [17], [18] considered the inference of directed graphs with a continuous-time diffusion model.
The diffusion along each edge is assumed to be exponential or satisfies a power law. In [19], the authors assumed that the network can be undirected, and, along each edge, information spreads in two steps: a Bernoulli selection step and an exponential transmission step. Other related works based on different diffusion models include [18], [20], [21]. In most of these efforts, knowledge of the probability distribution of information spreading along edges is assumed, and many also assumed the spreading along different edges to be identically distributed. In practice, the spreading distribution is not easy to quantify. For example, information diffusion in an online social network depends on a host of factors [1]. However, moments-such as the average amount of time information takes to diffuse from a vertex to a neighbor-are typically 3 readily estimated from historical data [22], [23]. In this paper, we consider the case where we have limited knowledge of the spreading distribution and require only that the diffusion along different edges be independent. The distribution of information diffusion along edges is unknown to an observer, and only certain moments of the distribution (instead of the full distribution) are given. Therefore, the statistical inference approaches developed in [17]- [20] cannot be applied directly to our problem. Owing to recent advancements in the field of graph signal processing (see [24] for an overview), several network topology inference methods using graph signals have been proposed (for example, [25]- [27]). These approaches are based on the idea that certain graph signals are closely related to eigenvectors of graph-shift operators of a graph (e.g., graph adjacency matrix, graph Laplacian). However, in our setting, the timestamps are related to distance from vertices of a graph to a fixed source node. Such timestamps are usually not directly related to the above mentioned shift-operators, and depend on the choice of the source node. Therefore, the graph signal processing approaches cannot be applied to our problem.
We approach the problem by first determining a necessary condition for perfect tree reconstruction based only on distance information. We introduce the concept of a separating vertex set, denoted by V S , and show that if |V S | is sufficiently large, we can reconstruct the tree using the distances of vertices from those in V S . Because the mean of the infection times are proportional to the distances from a source vertex to other vertices in the graph, we can estimate the distances from the information cascades. We propose an algorithm that makes use of the concept of redundant vertices to reduce the estimation variance. We further extend the method heuristically to general graphs by building on the tree reconstruction algorithm. Such an extension is supported by theoretical results obtained in the paper. The rest of this paper is organized as follows. In Section II, we introduce our graph model and assumptions. In Section III, we introduce the notion of a separating vertex set and derive a necessary condition for perfect tree reconstruction. In Section IV, we introduce the notion of redundant vertices and use that to develop an iterative tree inference algorithm in Section V.
We further extend the algorithm to general graphs in Section VI. Theoretical results supporting the extension are also discussed in Section VI. We present simulation results in Section VII and conclude in Section VIII.

II. GRAPH MODEL
Let G = (V, E) be a connected simple graph (i.e., undirected graph containing no graph loops or multiple edges), with V the set of vertices and E the set of edges. Let d(·, ·) be the length of a shortest path between nodes u and v. We use [u, v] to denote any shortest path between u and v, and (u, v) the path with end vertices u, v excluded. A path P between u and v is called simple if P does not cross itself; thus, [u, v] is always a simple path. For later use, we introduce the following definitions (see Figure 1 for an example). If v is a leaf and the unique neighbor of v is ordinary, then we say that v is a long leaf. The set of long leaves is denoted by L ∂G . Definition 2. We take ∂B G ⊂ B G to be the subset of vertices having a simple path to a leaf without passing through other vertices of B G : Let L ∂B G be the set of vertices v ∈ ∂B G such that none of the neighbors of v are leaves.
Although ∂B G is defined for any graph, it is particularly useful when considering tree networks.
Definition 3. Given a subset of vertices V ⊂ V , the convex hull conv(V ) of V in V is the union of all simple paths connecting any pair of distinct vertices of V .
A cascade c consists of a single source vertex that initiates an information diffusion together with the times each vertex first receives the information. We assume that the information diffusion along different edges is independent with known means. Without loss of generality, we assume that the mean for every edge is µ. We do not require the distributions along different edges to be identical or known.
We assume that each cascade persists long enough to infect all the vertices, and the following information is recorded: Fig. 1. In G, the boundary ∂G consists of the green vertices. The branched vertices BG are the red and yellow nodes, and ∂BG are the yellow nodes. The blue nodes are ordinary. Moreover, v1, v2, and v3 are long leaves, and time of vertex v. We would like to infer the graph structure, by inferring the adjacency matrix For each vertex v, let d v (u) = d(v, u) denote the distance function (from any other node u ∈ G) to v. We have the following simple observation on T c and d v , with v being the source of c.
Proof. For a vertex u ∈ V , because G is a tree, there is a unique simple path P connecting v and The upshot of the lemma is that we can focus on distance functions associated with nodes of the graph.

III. RECONSTRUCTION ACCURACY AND SEPARATING VERTEX SET
We start this section with the following notion of "distance" associated with any subset of vertices of the graph.
By the triangle inequality associated with the usual absolute value, it is easy to verify that d V (·, ·) defines a pseudometric (which means that d V (u, v) can be 0 for u = v) on the set of vertices V of G.
In this section, using d V (·, ·), we aim to develop a necessary condition under which a tree G can be reconstructed uniquely. To this end, we introduce the concept of a separating vertex set as follows (see Figure 2).
. We say that V S is a separating vertex set.
Note that in the above definition, G can be any graph. However, in the case of trees, we have the following result. Proof. Let u, v ∈ conv(V ) be two distinct vertices. By the definition of convex hull, we can find Because G is a tree, there is a unique simple path P Next, we demonstrate how to approximate G using a subset V and the pseudometric d V (·, ·).   (b) Suppose that G is a tree. Let ∂B G contain vertices of ∂B G such that for each v ∈ ∂B G , some neighbors of v are not in conv(V ) (see Figure 4). Moreover, assume that d(u, v) > 1 for u, v ∈ ∂B G ∪ ∂ conv(V ). If V separates G, then E = E, and hence G = G.
(c) In the converse direction, suppose that G is a general graph that does not contain any triangle (three pairwise connected vertices). If E = E, then V separates G. is a simple path if V separates G), which gives a contradiction.
Next, assume that u and v are in different components of G \ conv(V ). Let u 1 and u 2 be their respective closest vertex (projections) on conv(V ). Notice that u 1 , u 2 ∈ ∂B G ∪ ∂ conv(V ).
According to the given condition, d(u 1 , u 2 ) > 1. Without loss of generality, we assume that . Moreover, we have seen in the proof of Lemma 2 that we can choose This contradicts the fact that u and v are connected by an edge in E .
(c) Suppose on the contrary that V does not separate G. We can find two vertices u 1 and u 2 Let u 3 be a vertex connected by an edge to either u 1 or u 2 , Therefore, because E = E , u 3 and u 2 are also connected by an edge. This contradicts the assumption that G does not contain any triangle. The proof is now complete. Motivated by Theorem 1, we introduce the following quantifier to evaluate the effectiveness (using the same notation as in Theorem 1) of a given V .
We have the following observations regarding r.a. based on the definition and results obtained so far. Proof.
(a) Follows immediately from the definition.
(c) From Lemma 2 and noting that ∂B G = ∅ in Theorem 1(b), the result follows.
On the other hand, if G is a tree, it is clear that for two vertices u, v connected by an Moreover, we have the following lower bound regarding the size of V .
Suppose that the following uniqueness property holds true: for any tree G on V with associated Proof. Suppose on the contrary that l < |L ∂G | − |L ∂B G |. By the pigeon-hole principle and Lemma 2, we can always find two simple paths P 1 and P 2 in G \ conv(V ) that are disjoint except where they intersect at a vertex v ∈ B G , and the length of at least one of them, say P 1 , is larger than 1 (see Figure 6).
Moreover, let u 1 be the vertex between u 1 and v. Because both P 1 and P 2 are not in conv(V ), it is impossible to determine if u 1 is connected to u 1 or u 2 based only on the information network (e.g., observing 40% of the network yields on average a r.a.(V ) > 60%). In Section V, we propose an algorithm that does not require a separating vertex set explicitly.

IV. REDUNDANT VERTICES
Our tree inference algorithm is based on the infection times of cascades, whose means are proportional to the distances between vertices. In practice, we face the following problems: (1) owing to the stochastic nature of the diffusion process, the recorded infection times at various vertices are not exactly proportional to the distance to the source; (2) infection times provided by cascades starting at certain vertices may be redundant when considered together with timestamps given by cascades starting at other vertices. In this section, we introduce and discuss the concept of redundant vertices before presenting a method to mitigate the aforementioned shortcomings in our tree inference algorithm in Section V.
We remark that here E is assumed to be constructed using d V (u, v) ≤ 1 in Definition 6, so that some results are more general. When necessary, we may also use the condition d V (u, v) = 1 instead, in which case we will state this explicitly.
Intuitively, when two vertices are mutually replaceable, they give the same amount of information in the reconstruction task. From the definition, we have the following simple observations.
Therefore, v i is redundant if and only if they are not connected to each when we use V \{v i }; (b) This follows immediately from the criterion given in (1).
(c) According to the definition, E constructed from V \{v 1 } and V \{v 2 } are both the same as that constructed from V . T v u be the subtree rooted at u.
be their respective closest points in conv(V \ {v i }). We have seen that we can always find Without loss of generality, we assume that u ∈ Suppose that d(u , v ) > 1 and without loss of generality that d(u, u ) ≤ d(v, v ). Therefore, For the remaining case where d(u , v ) ≤ 1, we treat (a) and (b) separately.
(a) Suppose that d(u , v ) ≤ 1 and v i = v i . Without loss of generality, we can further assume In this case, we see that (b) If both u and v are different from v i , then the same argument as above does the job because, in this case, Figure 8).
By the definition of convex hull and the choice of Notice that P contains ordinary vertices. Therefore, the assumption asserts that there is a It is easy to verify that Using the previous proposition, we can prove the following corollary.
Corollary 3. Suppose that G is a tree. Let ∂B G be any subset of ∂B G such that the distance between any two vertices of ∂B G is at least 2. Moreover, if each element of ∂B G has at most two non-leaf neighbors, then any V contains a subset V of size at most |∂G| − |∂B G | (which is a constant that depends only on G) such that all the vertices not in V are redundant w.r.t.
Proof. Let T be the convex hull of V and L the leaves of T . For each u ∈ ∂B G ∩ T , we define the set L u ⊂ L as follows: In other words, L u consists of the leaves of T to whom u is the closest among all the members If a neighbor v of u is not a leaf, then let l u be the (unique) node in L u such that v ∈ [l u , u]; and otherwise, let l u be any node in L u . Form V by removing these l u from V (see Figure 9). It is clear that |V | ≤ |∂G| − |∂B G |. Moreover, each other vertex is redundant by Proposition 1(a) and (b). Simulation results on randomly generated trees with 500 nodes show that on average, the bound |∂G| − |∂B G | given in Corollary 3 is at most 32% of |V |.
Proposition 1 should be modified if G is a general graph. To be more precise, in addition to the given condition, we have to assume further that v i is not contained in a cycle (see Figure 10 for a counterexample). Because v 1 and v 2 are connected by a direct edge, without loss of generality, we can assume In the following cases, we can also conclude that v 1 is redundant: (1) Either (a) or (b) of Proposition 1 holds for v 2 . Notice that we always have that v 1 is either v 1 or v 2 .
(2) If we construct E using To see this, suppose that u and v are not connected by an edge using v 1 , but are connected by an edge using v 2 . This can only happen when The same argument as the the proof of Proposition 1 (use a neighbor of v 2 in place of v in the last two paragraphs; and see Figure 11 for an illustration) proves the claim.
If any of the above cases happens, and information diffusion happens deterministically, v 1 and v 2 are mutually replaceable w.r.t. V in inferring the structure of the graph. Simulation results show that if |V | ≥ 0.3|V |, then on average, more than 84% of pairs of V connected by a direct edge are mutually replaceable. In practice, the diffusion process is stochastic. Time information provided by v 1 (respectively, v 2 ) can be used to average out the time information at v 2 (respectively, v 1 ) to obtain a better estimate of the distance with a lower variance. We first discuss the reconstruction step. For u, v ∈ V , from Theorem 1 and Remark 1, to determine if u, v are connected by an edge, we want to compare This motivates us to introduce the following: Here, we take the average difference with 1 instead of using sup as in Definition 4. This is because when the timestamps are stochastically generated, taking sup is sensitive to change of variance of distributions. Essentially, this is nothing but replacing the L ∞ pseudometric by the L 1 pseudometric.
If W (u, v) is small, it suggests a higher chance that u, v are connected by a direct edge. We call W the weight matrix, and its entries the weights. If we want to infer the structure of a tree of size n, we can select n − 1 (total number of edges) pairs of distinct vertices (u, v) such that In doing so, we obtain an estimated graph G = (V, E ). We can directly use E for the selection step. An alternative is to use the weight matrix W for the job. More precisely, we can set a numerical condition C based on W , and select a pair (u, v) as long as satisfies the pre-set condition C. For example, for a fixed parameter k, we can choose kn pairs of (u, v) with the smallest W (u, v) value. This reflects our belief that each selected (u, v) has a "high chance" of being connected by an edge.
For a selected pair of vertices (v i , v j ) with v i , v j ∈ V and u ∈ V , we construct the times at v j using T v i in the transfer step as follows: for each u ∈ V , We can now update T v j (·) by its average with T v i v j (·). Once T v j (·) are updated for every v j ∈ V , we can repeat the reconstruction step.
We summarize the above discussion in as our Iterative Tree Inference (ITI) algorithm in Algorithm 1.

VI. THE CASE OF GENERAL GRAPHS
In this section, we consider general simple graphs. We first discuss theoretical results on information propagation on general graphs, which lend support to our heuristic extension of the ITI algorithm. We then propose a general graph inference algorithm.
We assume that G is undirected, and the information propagation along every edge of G is independently distributed according to an unknown continuous distribution with probability for Each pair of (v i , v j ) selected do 6: Generate new cascades T v j v i (·) and T v i v j (·) as in (2).

7:
Update density function (pdf) f with mean µ. We also assume that f has infinite support. The continuous distributions commonly used in the literature to model diffusions (for example, [17], [18]) satisfy this assumption.
As a notational convention, we use a lower-case letter (e.g., f ) to denote the pdf of a continuous probability distribution, and the corresponding capital letter (e.g., F ) for its cumulative distribution function (cdf). Moreover, we letF = 1 − F .

A. Theoretical observations
Let u, v be two distinct vertices of a graph G. We use X u,v to denote the random variable Lemma 4. Let m, n, k be positive integers. Then for some x ∈ (0, 1), we have We find immediately that h (1) = −1/k < 0. As h (x) is continuous in a small neighborhood Proof: It suffices to prove thatF =F u,v . Suppose that the contrary is true. If u and v is connected by an edge, the mean propagation time will be strictly smaller than that of f as we assume f has infinite support (a more general result is given in Lemma 5 below). For the rest of the proof, we assume (u, v) / ∈ E. We first reduce the graph G to a simpler graph (see Figure 12 for illustration). Construct G 1 as follows: if both end points of an edge e in G are different from u and v, then shrink e to a single point (take note that this is different from removing e) in G 1 . As u, v are not connected by an edge in G, each path between u and v is of length 2 in G 1 . We should take note that multiple edges are allowed between two nodes in G 1 (and G 2 constructed below). The shrinking process reduces the time to travel from u to v and henceF u,v ≥F 1 .
Let C be a connected component of G 1 \{u, v}. It is easy to see that C is made up of a single node v C , with m C paths connecting v C to u, and n C paths connecting v C to v. Denote the total number of connected components of G 1 \{u, v} by k. Define m = max C {m C } and n = max C {n C }. Construct G 2 as follows: for each C, we add m − m C edges between v C and u, and add n − n C edges between v C and v. As we add additional edges between nodes without changing the rest of the graph, we haveF 1 ≥F 2 . The number of connected components of BecauseF (t) is continuous,F (0) = 1 and lim t→∞F (t) = 0. By the intermediate value theorem, (0, 1] is contained in the image ofF . Therefore, from Lemma 4, we obtain a contradiction and the theorem is proved. Theorem 2 suggests that even if the mean propagation time (as was used in the ITI algorithm) for X u,v is similar to that of a single edge, we can use higher moments to determine if u and v are connected by a single edge (except for certain pathological distributions that share the same moments). In the following, we provide bounds on the moments of X u,v to guide us in our extension of the ITI algorithm to general graphs.

Lemma 5.
Suppose that (u, v) ∈ E. Consider the graph G in which (u, v) is removed, and suppose that G is connected. Let Y u,v be the propagation time from u to v in G and its pdf be h. Then for all k ≥ 1, and any 0 > 1 > 0, where the interchange of integration in the third equality follows from Tonelli's theorem. The lemma is proved.
In particular, by choosing 0 − 1 to be sufficiently large and noting thatH(·) > 0 (as h has infinite support), Lemma 5 implies that E Y k u,v > E X k u,v for all k ≥ 1. Moreover, if the graph G is not too dense in the sense that F (1)H(1) is suitably large, then the difference between the means of Y k u,v (without an edge between u and v) and X k u,v (with an edge between u and v) can be made suitably large by choosing a sufficiently large k. This allows us to determine if (u, v) ∈ E based on empirical observations of the propagation times raised to the k-th power.
However, we may not observe information cascades from every vertex u in the network, and typically have to rely on information cascades starting at sources other than u and v. We have the following bound relating the propagation times to u and v from a distinct source node. Lemma 6. Let G u,v be the union of all the simple paths connecting u, v (i.e., the convex hull, according to Definition 3) in G; and w ∈ G. Then for any k ≥ 1, Proof: For any vertices a, b, let P a,b be the path associated with X a,b . The concatenation of P u,w and P u,v is a path from w to v with possibly some edges repeated. We therefore have almost surely, Similarly, X w,u − X w,v ≤ X u,v almost surely. We then obtain where the first inequality follows from Jensen's inequality, and the lemma is proved.
using T w (u) and the transfer step in the ITI algorithm in Section V). The reverse implication is not necessarily true, but for algorithmic convenience, the lemma suggests that we use an empirical estimate of the latter term as a proxy for E X k u,v .

B. Discussions and implications
We now discuss some implications of the results obtained in Section VI-A. Consider any pair of distinct nodes u, v, and the following cases: (i) Suppose that the number of paths between u and v is small (i.e., the graph G is sparse). (ii) Suppose that the number of paths between u and v is large (i.e., the graph G is dense).
According to Lemma 5 and the discussions thereafter, the existence of an edge between u and v can make both the sample mean and higher moments small relative to the corresponding moment values if such an edge is missing. Therefore, in this case, we may choose to infer that the edge (u, v) exists based on the size of the sample mean and higher moments. However, we should mention that if there are too many paths between u and v, then in practice, any distribution-based estimation is prone to errors as demonstrated in the discussion and example below.
Our next example demonstrates that it is almost impossible to determine if there exists an edge (u, v) in the graph G if it is very dense. To show this, we need the following result.
Lemma 7. Suppose that X and Y are two continuous random variables on (0, ∞), with cdf P and H respectively. Let Z = min{X, Y }. Then the total variation distance between the distributions of Y and Z is bounded from above by inf >0 {H( ) + P ( )}.
Proof: Let p and h be the pdf of P and H respectively. It is easy to show that the pdf of the distribution associated with Z is p(1 − H) + h(1 − P ). Therefore, we have to show that for To see this, we first apply the triangle inequality: The two integrals on the right hand side of (3) can be bounded separately as: The result follows by adding up the two inequalities.
Example 2. Suppose that the propagation along each edge are i.i.d. with exponential distribution having mean 1. Then, we have F (x) = 1 − e −x . Assume that there are k independent paths of length l between two distinct nodes u and v, which are not connected by an edge. Along each path, the propagation follows a Gamma distribution Γ(l, 1), whose cdf is 1 − e −x l−1 i=0 x i /i!. Let Y be the propagation time between u and v. Then, it can be shown that its complementary Let Z be the propagation time from u to v if the edge (u, v) is added to the graph. By Lemma 7, the total variation distance between Y and Z is bounded from above by We have lim →0 + (1−e ) = 0. On the other hand, the derivative of e −x l−1 i=0 we can always choose small enough and k large enough such that the upper bound (4) is as close to 0 as we wish. This suggests that in practice, if there are many paths between the two nodes, then it is almost impossible to determine if there is an edge between them or not by any distribution-based method.

C. The graph inference algorithm
The discussion in Section VI-B can be summarized in the following dichotomy: when the graph is sparse (as measured by the edge to vertex ratio, for example) or the distributions of the propagation times along each edge have small variance, it is enough to use the mean of the distributions as in the case of trees. On the other hand, if the graph is highly connected, the existence of an edge between two vertices u and v can make the mean propagation time between u and v small relative to µ. Therefore, it is instructive to use the length of the propagation time between u and v to decide if they are connected by an edge or not. The same consideration applies to other moments (as compared against unbiased sample moments); and they can be used as additional criteria to decide the existence of edges.
In a general graph, it is usually unknown whether the connection between two vertices u and v is dense or sparse. One way to overcome such a difficulty is to compute the difference between the sample mean (respectively, sample moments) with both the theoretical mean (respectively, theoretical moments) as well as 0. Once these two values are obtained, it is enough to take the smaller one. Hence the weight matrix being used in ITI should be modified based on available moment information. Suppose that the mean µ and variance σ 2 of propagation time along edges are known. We define the following: where "ave" is used to denote average over v i ∈ V as in (1) to shorten the expressions; and In the case of general graphs, we usually do not know the total number of edges based on the number of vertices n, in contrast to tree networks. Therefore, we first randomly choose a small percent of vertices and find their average degree deg s . We take deg s to be an estimate of the actual average degree of the network; and estimate the total number of edges as n e = n · deg s .
Based on these, we propose below the Graph Inference (GI) algorithm (Algorithm 2) as a heuristic extension of ITI.
A possible generalization of Algorithm 2 if higher order moments are available is to modify W 1 , W 2 and hence W accordingly as follows. According to Lemma 6 and the discussion thereafter, we may use |T v i (u) − T v i (v)| to estimate the sample moments. For each k ≥ 1, the k-th sample moment is denoted by S The k-th moment of the distribution (of propagation time) along each edge is denoted by µ k .
We fix a finite set of m positive numbers: {k 1 = 1, k 2 , . . . , k m }; and a continuous m-variable function φ. Define for each 1 ≤ i ≤ m: Under this generalization, the procedure depicted in Algorithm 2 uses m = 2, k 1 = 1, and k 2 = 2, while φ is the averaging function. The choice of φ should reflect one's belief about which moment should play a more important role in the network inference task. for Each pair of (v i , v j ) selected do 6: (2). 7: Update

VII. SIMULATION RESULTS
In this section, we present simulation results to verify the performance of our proposed topology inference algorithms. We first apply our ITI algorithm on tree networks, and compare its performance with with the tree reconstruction (TR) algorithm proposed in [19], which is most similar to ours in assumptions. We then perform simulations on general graphs, including some real-world networks, and compare the performance of the GI algorithm with the the NetRate algorithm proposed in [18]. As the NetRate algorithm assumes knowledge of the diffusion distribution, we also study the performance impact when there is a mismatch between the assumed and actual distributions.
Suppose that A G is the true adjacency matrix of G and A is an estimated adjacency matrix.
To evaluate the performance of our method, we define the edge recovery rate as For the same number of edges, each mistake in identifying an edge causes a mistake at another pair of vertices. To account for this, we have a factor of 2 in the denominator; and this makes R a real number in [0, 1]. The term 1 − R is called the error rate, in which both undetected edges and false positives are taken into account.

A. Tree networks
In this subsection, we show and discuss simulation results to verify the performance of our proposed algorithm for tree networks. As we are considering tree networks, in the reconstruction step, we always have |E| = n − 1 edges, where n is the number of vertices.
In each simulation run, we randomly generate trees with n = 500 vertices. We then randomly choose n c distinct sources, and generate κ v cascades per source using independent exponential spreading with mean µ = 1 at each edge. In applications, κ v can be different for distinct nodes v; however, in our simulations below, we keep it constant for all v for simplicity. We apply the ITI algorithm, and evaluate the performance by using (7).
We first study the edge recovery rate by varying n c and κ v , and skip the selection and transfer steps by setting I = 0 (see Figure 13). We notice that κ v has a significant impact on the performance. If the number of cascades per source κ v is small, the performance can be greatly improved if we perform additional transfer steps (see Figures 14). These results demonstrate the usefulness of the theory developed in Section IV. The choice I = 2 is usually enough, and the number of edges m s in the selection step can be chosen between n and 1.5n.
Moreover, comparing the curves for n c /n = 0.3, κ v = 2 and n c /n = 0.5, κ v = 1, we see that the performance is improved if we have more cascades originating from the same source. This suggests that the averaging process allows a better approximation of the distance on a tree.
Finally, we compare our method with the TR algorithm proposed in [19]. Although the theoretical part of [19] assumes i.i.d. exponential distribution for propagation time along different edges, the TR algorithm itself requires n and {T v i } as the only input. The comparison is shown in Figures 15 and 16. In Figure 16, we test the effect of having different diffusion distributions for different edges. The distributions are randomly selected unknown Gamma distributions with the same mean. As shown from the plots, our method performs much better in all the cases because our method does not require identical distributions for propagation times along different edges.

B. General graphs
For general graphs, we compare our GI algorithm with the NetRate algorithm proposed in [18]. 1 Although NetRate works under a completely different set of assumptions (in particular, [18] assumes propagation along edges follows one of the following families of distributions: exponential, power-law, or Rayleigh), it proves to be very powerful in graph topology inference using cascade information.
To accommodate comparison with NetRate, we use the standard exponential distribution with rate 1/µ = 1 for propagation time along each edge. We compare the performance of NetRate and GI on Erdös-Rényi graphs, the Forest-fire network [28], and a real-world Email network [28]. The parameters of all networks are described in the plots.
From the plots (Figures 17, 18, 19, and 20), we see that our method performs better in all the tested cases if the number of cascades does not exceed 60% of the number of nodes. However, we should mention that if the ratio is closer to 1 (i.e., on average each node sends a cascade), then NetRate can have a better performance for certain graph types (Figures 17 and 19). On the other hand, for ER-graphs with large average degree and the Email network, GI performs better for the entire spectrum of n c /n from 10% to 100%. The GI algorithm has a noticeably better performance when n c /n is very small, as compared with NetRate. For example, in the case of the Email Network and n c /n = 10%, NetRate has less than 5% edge recovery while the GI has more than 27% edge recovery. We note that since the Email network is dense, all inference methods based on the assumption that diffusion across each edge follows a distribution will have limited performance (cf. Example 2).
We would like to point out another important advantage of our method. Because of the nature of the two algorithms, our method is computationally much more efficient. For example, using the same computational resource under the same simulation settings, the time used to run GI and NetRate is a few seconds versus a few hours. Therefore, our method is more suitable in time-critical applications when computational resource is limited.

C. Distribution mismatch
For the next set of simulations, we test the effect of distribution mismatch on NetRate. To be precise, as our algorithm does not require knowledge of the type of distribution governing the diffusion process while NetRate does, we want to test whether such prior knowledge is crucial to NetRate.
The setup of the simulations is as follows: on each type of network, we generate the cascades using the exponential distribution with rate 1. We run the NetRate algorithm with the incorrect distributions: either the power-law distribution (POW) or the Rayleigh distribution (RAY), as  these are the other two families of distributions discussed in [18]. The results are shown in the same Figures 17, 18, 19, and 20, by dashed curves.  From the plots, we see that the performance of NetRate drops significantly if there is a distribution mismatch. For example, if the power-law distribution is used, the edge recovery of NetRate is close to 0% regardless of n c /n and the network type.
The experiments suggest that prior knowledge of the diffusion distribution is important to guarantee the performance of NetRate. In contrast, for the GI algorithm, no such prior knowledge is required.

VIII. CONCLUSION
In this paper, we have developed a theory and method for graph topology inference using information cascades and knowledge of some moments of the diffusion distribution across each edge, instead of the distribution itself. In the case of tree networks, we provided a necessary condition for perfect reconstruction, and used the concept of redundant vertices to propose an iterative tree inference algorithm. Our method works well as long as the total number of cascades is not too small compared to the size of the network. Moreover, our method works better if there are more cascades at each chosen source. Simulations demonstrate that our method outperforms the tree reconstruction algorithm in [19]. We have also provided some theoretical insights into how the moments of the propagation time between two vertices in a general graph behave, and extended our tree inference method heuristically to general graphs. Our simulation results suggest that our graph inference algorithm performs reasonably well, if the total number of cascades is not too small compared to the size of the network, and often outperforms the NetRate algorithm in [18]. Moreover, our method is suitable for time-critical applications owing to its low complexity.