summaries: The authors formulate and study dynamic mechanism design in an MDP-like setting. The motivation is principal-agent problems. The principal commits to a policy to choose actions given observations of states; the environment evolves according to some transitions dynamics based on these actions; the agent does not act but is free to misreport states to the principal. Agent and principal receive utility; the principal’s goal is to choose a policy that is incentive compatible and individually rational (standard goals of mechanism design) while maximizing its own expected total utility.  In general, from a full description of the environment and dynamics, the “planning” type problem to find an optimal mechanism is NP-hard (shown via reduction from MAXSAT). If the time horizon of the problem is treated as a constant, then it is possible to formulate a linear program to find the optimal mechanism in polynomial time, and doing so is a major portion of the paper.

summaries: This paper presents and proves a linear program for unstructured dynamic mechanism design. The LP supports payments and different individual-rationality constraints. The key contributions are: 1) Presenting an LP that provably yields an optimal mechanism for an unstructured dynamic environment with a finite time horizon. 2) From this LP formulation and standard LP complexity results follows a polynomial runtime guarantee for finding an optimal mechanism.

summaries: The authors study the problem of computing optimal mechanisms in a dynamic unstructured environment. Unlike a static environment, the principal is allowed to repeatedly interact with a strategic agent and take actions based on the agent's reports of the current state of the world. The authors show that when the time horizon of such a dynamic environment is not finite, the problem is intractable. When the time horizon is small, they show that an efficient mechanism can be computed using an LP

summaries: This paper studies automated mechanism design in dynamic unstructured dynamic environments. In the setting of interest, a principal and agent repeatedly interact for a finite number of time steps (finite time horizon); at each time step, the agent reports the current state of the environment, the principal takes action, and the environment transitions to the new state. Importantly, the agent's and the principal's utilities are not necessarily the same, implying that the agent might misreport which further implies the need for a mechanism.  The paper considers a randomized dynamic mechanisms that consists of the policy of the principal and the mechanism's payment function. The main results are: a) an LP for finding optimal mechanisms (constant time horizon), b) a computational complexity result which shows that the principal's utility is hard to approximate within a certain factor for environments with large time horizons.  The paper has additional results, as mentioned in the abstract, but these are not presented in the main text.

abstractText: We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agent’s report of the current state of the world. Both the principal and the agent can have arbitrary and potentially different valuations for the actions taken, possibly also depending on the actual state of the world. Moreover, at any time, the state of the world may evolve arbitrarily depending on the action taken by the principal. The goal is to compute an optimal mechanism which maximizes the principal’s utility in the face of the self-interested strategic agent. We give an efficient algorithm for computing optimal mechanisms, with or without payments, under different individual-rationality constraints, when the time horizon is constant. Our algorithm is based on a sophisticated linear program formulation, which can be customized in various ways to accommodate richer constraints. For environments with large time horizons, we show that the principal’s optimal utility is hard to approximate within a certain constant factor, complementing our algorithmic result. These results paint a relatively complete picture for automated dynamic mechanism design in unstructured environments. We further consider a special case of the problem where the agent is myopic, and give a refined efficient algorithm whose time complexity scales linearly in the time horizon. In the full version of the paper, we show that memoryless mechanisms, which are without loss of generality optimal in Markov decision processes without strategic behavior, do not provide a good solution for our problem, in terms of both optimality and computational tractability. Moreover, we present experimental results where our algorithms are applied to synthetic dynamic environments with different characteristics, which not only serve as a proof of concept for our algorithms, but also exhibit intriguing phenomena in dynamic mechanism design.

authors:
Itai Ashlagi
Constantinos Daskalakis
Nima Haghpanah

title: Sequential mechanisms with ex-post participation guarantees

venue: In Proceedings of the 2016 ACM Conference on Economics and Computation,

authors:
Susan Athey
Ilya Segal

title: An efficient dynamic mechanism

authors:
Maria-Florina Balcan
Tuomas Sandholm
Ellen Vitercik

title: Sample complexity of automated mechanism design

venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,

title: A general theory of sample complexity for multi-item profit maximization

venue: In Proceedings of the 2018 ACM Conference on Economics and Computation,

authors:
David P Baron
David Besanko

title: Regulation and information in a continuing relationship

venue: Information Economics and policy,

title: A markovian decision process

venue: Journal of mathematics and mechanics,

authors:
Dirk Bergemann
Juuso Välimäki

title: The dynamic pivot mechanism

title: Dynamic mechanism design: An introduction

venue: Journal of Economic Literature,

authors:
Andrea Celli
Stefano Coniglio
Nicola Gatti

title: Private bayesian persuasion with sequential games

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Vincent Conitzer
Tuomas Sandholm

title: Complexity of mechanism design

venue: arXiv preprint cs/0205075,

title: Self-interested automated mechanism design and implications for optimal combinatorial auctions

venue: In Proceedings of the 5th ACM Conference on Electronic Commerce,

title: Computing the optimal strategy to commit to

venue: In Proceedings of the 7th ACM conference on Electronic commerce,

authors:
Pascal Courty
Li Hao

title: Sequential screening

venue: The Review of Economic Studies,

authors:
P Dütting
F Fischer
P Jirapinyo
J Lai
B Lubin
DC Parkes

title: Payment rules through discriminant-based classifiers

venue: ACM Transactions on Economics and Computation,

authors:
Paul Dütting
Zhe Feng
Harikrishna Narasimhan
David Parkes
Sai Srivatsa Ravindranath

title: Optimal auctions through deep learning

authors:
Péter Eső
Balazs Szentes

title: Optimal information disclosure in auctions and the handicap auction

authors:
Zhe Feng
Harikrishna Narasimhan
David C Parkes

title: Deep learning for revenue-optimal auctions with budgets

venue: In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems,

authors:
Jiarui Gan
Rupak Majumdar
Goran Radanovic
Adish Singla

title: Bayesian persuasion in sequential decision-making

venue: arXiv preprint arXiv:2106.05137,

authors:
Mohammad Taghi Hajiaghayi
Robert Kleinberg
Tuomas Sandholm

title: Automated online mechanism design and prophet inequalities

venue: In AAAI,

title: Dynamic programming and markov processes

authors:
Andrew Kephart
Vincent Conitzer

title: Complexity of mechanism design with signaling costs

venue: In AAMAS,

title: The revelation principle for mechanism design with reporting costs

authors:
Vahab Mirrokni
Renato Paes Leme
Pingzhong Tang
Song Zuo

title: Non-clairvoyant dynamic mechanism design

title: Optimal auction design

venue: Mathematics of operations research,

title: Multistage games with communication

venue: Econometrica: Journal of the Econometric Society,

authors:
Harikrishna Narasimhan
Shivani Brinda Agarwal
David C Parkes

title: Automated mechanism design without money via machine learning

venue: In Proceedings of the 25th International Joint Conference on Artificial Intelligence,

authors:
Christos Papadimitriou
George Pierrakos
Christos-Alexandros Psomas
Aviad Rubinstein

title: On the complexity of dynamic mechanism design

venue: In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms,

title: Dynamic mechanism design: Robustness and endogenous types

venue: In Advances in Economics and Econometrics: Eleventh World Congress,

authors:
Alessandro Pavan
Ilya Segal
Juuso Toikka

title: Dynamic mechanism design: A myersonian approach

authors:
Martin L Puterman
Moon Chirl Shin

title: Modified policy iteration algorithms for discounted markov decision problems

venue: Management Science,

authors:
Jad Rahme
Samy Jelassi
Joan Bruna
S Matthew Weinberg

title: A permutation-equivariant neural network architecture for auction design

venue: arXiv preprint arXiv:2003.01497,

authors:
Jérôme Renault
Eilon Solan
Nicolas Vieille

title: Optimal dynamic information provision

venue: Games and Economic Behavior,

authors:
Tuomas Sandholm
Anton Likhodedov

title: Automated design of revenue-maximizing combinatorial auctions

venue: Operations Research,

authors:
Tuomas Sandholm
Vincent Conitzer
Craig Boutilier

title: Automated design of multistage mechanisms

venue: In IJCAI,

authors:
Weiran Shen
Pingzhong Tang
Song Zuo

title: Automated mechanism design via neural networks

venue: In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems,

heading: 1 Introduction

text:
Consider the following scenario. A company assembles an internal research group to develop key technologies to be used in the company’s next-generation product in 5 years. The more progress the group makes, the more successful the product is likely to be. Since research progress is hard to monitor, the company manages the group based on its annual reports. At the beginning of each year, the group submits a report, summarizing its progress in the preceding year, as well as its needs for the current year. Taking into consideration this report (and possibly also reports from previous years), the company then decides the compensation level and the headcount of the group in the current year. Moreover, after the product launches, the company may also pay a bonus to members of the group, depending on how successful the product is.
For simplicity, suppose an annual report consists of two items: research progress (satisfactory/unsatisfactory), and need to expand (no request/request for an intern/request for a full-time employee). The company’s goal is to encourage and facilitate research progress while keeping the expenses reasonable. So, a natural managing strategy is to increase (resp. decrease) the compensation
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
level when the reported research progress is satisfactory (resp. unsatisfactory), and to allow the group to expand only when necessary, i.e., when the reported research progress is unsatisfactory. However, the research group may have a different goal than the company’s. Suppose members of the group do not care about the success of the product per se. Instead, their primary goal is to maximize the total compensation received from the company, and for this reason, they may be incentivized to misreport the situation. In other words, the company faces a dynamic mechanism design problem, where the principal (i.e., the company) needs to implement (and commit to) a mechanism (i.e., a managing strategy) that achieves its goal through repeated interactions, in the presence of strategic behavior of the agent (i.e., the research group).
Indeed this problem is nontrivial. For example, if the company implements the above strategy, then the group will report satisfactory progress regardless of the actual situation, which maximizes the group’s total compensation over the 5 years, but also causes greater expenses for the company and jeopardizes the success of the product. To counter this, the company may additionally promise a significant bonus contingent on the success of the product. This creates incentives for the group to make more progress, and discourages overreporting the progress, because the group is not allowed to expand when the reported progress is satisfactory. That is, if actual progress is unsatisfactory, this introduces an incentive to report this truthfully so that the group may expand. However, this also runs the risk of encouraging the group to report unsatisfactory progress in order to expand even if actual progress is satisfactory, because more members always make more progress, which leads to a higher (chance of) bonus, whereas the cost of expanding is paid by the company and therefore irrelevant to the group.
One may try to fix this by introducing more rules, possibly replacing existing ones. For example, the company may allow the group to recruit an intern, but not a full-time employee, when the reported progress is unsatisfactory. Then, in the next year, if the reported progress improves, the company allows the group to make a return offer to the intern as a full-time employee. Or alternatively, the company may unconditionally allow the group to recruit interns (which are less costly), but never full-time employees. In addition to the above, the company could also temporarily decrease the compensation level when a new member joins, and later adjust the compensation based on how the reported progress improves. While all these ad hoc rules make intuitive sense, it is not immediately clear which (combinations of) rules are better, how to optimize parameters of these rules (e.g., the number of new members allowed per year and the amount by which the compensation is adjusted), or whether there is a better set of rules that look totally different.
As demonstrated by the foregoing discussion, in general, the problem of finding an optimal mechanism in unstructured dynamic environments, such as the above example, turns out to be extremely rich and challenging. In such environments, the actions of the principal may go beyond the allocation of items to the agent, and affect the state of the world in arbitrary ways. Moreover, both the principal and the agent may have arbitrary valuations for these actions, which also depend on the current state of the world. In economic theory, the characterize-and-solve approach [25, 13, 30] to mechanism design has achieved spectacular success in both static and dynamic environments, by exploiting structure of the environment to construct a characterization of optimal mechanisms, often leading to closed-form or computationally tractable solutions. However, since the environments under consideration here are loosely structured at best, the classical characterize-and-solve approach does not seem particularly suited. When disregarding the agent’s incentives, one could treat the problem of finding an optimal strategy as a planning problem, which is known to be solvable efficiently [6, 21, 31]. However, as discussed above, the agent’s strategic behavior can ruin the performance of such a strategy. From a computational perspective, while numerous methods for automated mechanism design, which efficiently compute optimal mechanisms without heavily exploiting structures of the environment, have been proposed [10, 11, 12], all existing methods work only for static environments with one-time interactions, and it is not immediately clear how to generalize these methods to dynamic environments. All this brings us to the following question:
Can we efficiently compute optimal mechanisms in unstructured dynamic environments?

heading: 1.1 Our Results

text:
In this paper, we study the problem of computing optimal mechanisms in single-agent, discrete-time dynamic environments with a finite time horizon, without any further structural assumptions. Our main results (presented in Section 3) can be summarized as follows:
• Efficient algorithm: when the time horizon is fixed, there is a polynomial-time algorithm for computing optimal mechanisms, with or without payments, that maximize the principal’s utility facing a strategic agent.
• Inapproximability: when the time horizon can be large, it is NP-hard to approximate the principal’s optimal utility within a factor of (7/8 + ε) for any ε > 0.
To the best of our knowledge, our algorithm for constant time horizons is the first that efficiently computes optimal mechanisms in unstructured dynamic environments. The fact that our algorithm cannot scale beyond constant time horizons is by no means surprising: optimal dynamic mechanisms generally depend on the entire history, and as a result, the straightforward description of such a mechanism is exponentially large in the time horizon. Our inapproximability result further rules out the possibility of computing succinct representations of approximately optimal mechanisms that can be efficiently evaluated. These results together paint a complete picture of the computational complexity of dynamic mechanism design in unstructured environments.

heading: 1.2 Further Related Work

text:
Dynamic mechanism design. The problem we study can be situated in the broad area of dynamic mechanism design, and below we discuss some representative related work. For a more comprehensive exposition, see, e.g., the survey by Pavan [29] and the one by Bergemann and Välimäki [8]. In the context of efficient (i.e., welfare-maximizing) mechanisms, Bergemann and Välimäki [7] propose the dynamic pivot mechanism, which generalizes the VCG mechanism in static environments, and Athey and Segal [2] propose the team mechanism, which focuses on budget-balancedness. As for optimal (i.e., revenue-maximizing) mechanisms, which are more closely related to our results, following earlier work [5, 13, 17], Pavan et al. [30] generalize the classical characterization by Myerson [25] into dynamic environments, unifying previous results with continuous type spaces. Ashlagi et al. [1] study ex-post individual-rational dynamic mechanisms for repeated auctions, and give an efficient (1− ε)-approximation to the optimal revenue for a single agent with independent valuations across items. Mirrokni et al. [24] study non-clairvoyant dynamic mechanism design, where future distributional knowledge is unavailable to the principal. All these results for optimal mechanisms follow the characterize-and-solve approach, which is quite different from the computational approach that we take.
Particularly related to our results is the work by Papadimitriou et al. [28], who study a setting where one item is sold at each time, and agents’ valuations can be correlated across items. They show that designing an optimal deterministic mechanism is computationally hard even when there is only one agent and two items (thereby ruling out the possibility of efficiently computing optimal deterministic mechanisms in our model, which is more general). And moreover, they give a polynomial-size linear program formulation for optimal randomized mechanisms for independent agents when the number of agents and the time horizon are both constant. Restricted to a single agent, their LP formulation can be viewed as a special case of our main result: they focus on revenue maximization with a single item to be allocated at each time, in a model where the principal’s actions cannot affect the future valuations of the agent; on the other hand, we allow the principal to care about actions as well as revenue, with actions being general and unstructured (as opposed to allocation/no allocation), where the future state of the world can depend arbitrarily on the principal’s actions as well as the current state.
Automated Mechanism Design. There is a rich body of research regarding automated mechanism design (AMD) in (essentially) static environments. Conitzer and Sandholm [10, 11] initiated the study of automated mechanism design. They consider various specific static setups, and show that computing optimal deterministic mechanisms, even with a single agent, is often NP-hard (which also rules out the possibility of efficiently computing optimal deterministic mechanisms in our model, since the 1-period case is a special case), while computing optimal randomized mechanisms is often tractable. Conceptually related to our model, Hajiaghayi et al. [20] consider a model where agents
enter and leave the mechanism online (but still have one-time interactions with the mechanism), and provide an algorithm for computing mechanisms that are competitive against the optimal allocation from hindsight. Sandholm et al. [35] study automated design of multistage mechanisms, but these are not for dynamic settings; instead, the motivation is to implement static mechanisms using multiple rounds of queries in order to minimize the communication cost. Sandholm and Likhodedov [34] study automated design of combinatorial auction mechanisms, and Balcan et al. [3, 4] study the sample complexity thereof. Kephart and Conitzer [22, 23] and Zhang et al. [37] study AMD with partial verification and/or reporting costs. More recently, various methods have been proposed for automated mechanism design via machine learning [14, 27], and in particular, deep learning [15, 18, 36, 32]. All these results are essentially for static environments, whereas in this paper, we focus solely on AMD in dynamic environments. Another emerging research direction is Bayesian persuasion in dynamic environments [16, 33]. In particular, Celli et al. [9] study an algorithmic persuasion problem in extensive-form games, where a single signal is sent at the very beginning, and Gan et al. [19] study an algorithmic persuasion problem in infinite-horizon discounted MDPs, where a new signal is sent at every time. These persuasion problems can be viewed as a dual problem of ours: in our problem, the principal has the commitment power, and tries to encourage the agent to truthfully report their private information, whereas in (dynamic) Bayesian persuasion, the agent has the commitment power, and tries to induce the principal to act in favor of the agent by selectively revealing their private information.

heading: 2 Preliminaries

text:
Dynamic environments. Throughout this paper, we consider single-agent, discrete-time environments with a finite time horizon. Below, we give a general definition of such a dynamic environment. Let T be the time horizon, S be the state space, and A be the action space. The agent observes the state, but the principal controls the action that is taken. For each t ∈ [T ], let vPt : S ×A → R be the principal’s valuation function, where for each state s ∈ S and action a ∈ A, vPt (s, a) is the value of the principal when playing action a in state s, at time t; similarly, let vAt : S ×A → R be the agent’s value function. Let P0 ∈ ∆(S) be the initial distribution over states, and for each s ∈ S, denote by P0(s) the probability that the initial state is s. Moreover, for each t ∈ [T ], let Pt : S ×A → ∆(S) be the transition operator, which maps a state-action pair (s, a) at time t to the distribution of the next state at time t+ 1, Pt(s, a) ∈ ∆(S). We denote by Pt(s, a, s′) the probability that the next state is s′ when playing action a in state s at time t ∈ [T ]. For notational simplicity, let P0(s, a, s′) = P0(s′) for all s, s′ ∈ S and a ∈ A. (Note that the first actual action is taken at t = 1 — not t = 0 — possibly based on the state at t = 1.)
Histories. A t-step history is a sequence of states and actions (s1, a1, s2, . . . , at−1, st, at), where for each i ∈ [t], it is the case that si ∈ S and ai ∈ A. For each t ∈ [T ], let Ht be the set of all possible t-step histories, i.e.,
Ht = {(s1, a1, . . . , st, at) | si ∈ S, ai ∈ A for all i ∈ [t]}.
For each h = (s1, a1, . . . , st, at) ∈ H, let |h| = t, and moreover, for any st+1 ∈ S, at+1 ∈ A, let h + (st+1, at+1) = (s1, a1, . . . , st+1, at+1). Let H0 = {∅}, where ∅ corresponds to the empty history with |∅| = 0. LetH = H0 ∪ ⋃ t∈[T−1]Ht be the set of all possible histories of length at most T − 1 in the dynamic environment. Note thatH does not contain histories of length T .
Dynamic mechanisms. Dynamic mechanisms are more powerful than static ones, in that they may depend on the entire history, rather than only the current state. A (randomized) dynamic mechanism M = (π, p) consists of an action policy π and a payment function p. The action policy π : H × S → ∆(A) maps each history h ∈ H, extended with the reported current state s ∈ S, to a distribution over actions π(h, s) ∈ ∆(A). We denote by π(h, s, a) the probability that the action taken by the mechanism is a for (h, s). The payment function p : H× S → R maps the extended history (h, s) to a real number, i.e., the payment, made from the agent to the principal (but it can be negative). We remark that in principle, one can absorb payments into the action space. However, doing so would make the action space uncountable, introducing subtleties into the computational problem (which is the main focus of this paper). Here, we keep payments separate and explicit to avoid such issues. Also, our algorithm allows linear constraints on feasible payments, including but not limited to: nonnegative payments, no payments, etc. See Section 3.2 for more details.
Utilities. Fixing a mechanism M = (π, p), we can then define the onward utility of the principal and the agent. Let uMP : H× S → R be the principal’s onward utility function under mechanism M , defined inductively such that
uMP (h, s) = ∑ a π(h, s, a) · ( vP|h|+1(s, a) + ∑ s′ P|h|+1(s, a, s ′) · uMP (h+ (s, a), s′) ) + p(h, s),
with the boundary condition that uMP (h, s) = 0 for all h ∈ HT and s ∈ S . Here, all summations are over the entire state/action space. Let uMP (∅) be the overall utility of the principal, i.e.,
uMP (∅) = ∑ s P0(s) · uMP (∅, s).
Similarly, let uπA : H× S → R be the agent’s onward utility function under mechanism M , defined such that
uMA (h, s) = ∑ a π(h, s, a) · ( vA|h|+1(s, a) + ∑ s′ P|h|+1(s, a, s ′) · uMA (h+ (s, a), s′) ) − p(h, s),
where uMA (h, s) = 0 for all h ∈ HT and s ∈ S . And let uMA (∅) be the overall utility of the agent, i.e., uMA (∅) = ∑ s P0(s) · uMA (∅, s).
We remark that while the above definition assumes that the principal cares about payments as much as the agent does, in fact, our algorithm allows for the principal to care about payments in an arbitrary linear way (including possibly not at all). See Section 3.2 for a detailed discussion.
Incentive-compatible mechanisms. We say a mechanism M is incentive-compatible (IC) if the agent can never achieve a higher overall utility by misreporting the state, even in sophisticated ways. Formally, a reporting strategy r : H× S → S maps each history h extended with the current state s to a reported state s′, which is possibly different from s. Note that the agent only (mis)reports the current state, since the principal can memorize all historical reports. This reporting strategy induces a reported history r(h) = (s′1, a1, . . . , s ′ t, at) for each actual history h = (s1, a1, . . . , st, at), where for each i ∈ [t], s′i = r((s1, a1, . . . , si−1, ai−1), si). Note that we abuse notation here: in particular, r(h, s) denotes a reported state, whereas r(h) denotes a reported history. And without loss of generality, we only consider deterministic reporting strategies. Given a mechanism M and a reporting strategy r, we can define the agent’s utility function uM,rA under M and r inductively such that
uM,rA (h, s) = ∑ a π(r(h), r(h, s), a) · ( vA|h|+1(s, a) + ∑ s′ P|h|+1(s, a, s ′) · uM,rA (h+ (s, a), s ′) ) − p(r(h), r(h, s)),
where uM,rA (h, s) = 0 for all h ∈ HT and s ∈ S. And let u M,r A (∅) be the overall utility of the agent, i.e., uM,rA (∅) = ∑ s P0(s) · uM,rA (∅, s).
In words, uM,rA is the utility function of the agent applying the reporting strategy r in response to the mechanism M . The mechanism M is IC iff for any such reporting strategy r,
uMA (∅) ≥ u M,r A (∅).
Since the revelation principle holds in dynamic environments (see, e.g., [26]), we focus on IC mechanisms in the rest of the paper.1
1Of course, the revelation principle will not hold in our dynamic setting if we allow it to generalize a static setting in which the revelation principle does not hold. For example, in the case of partial verification — not every type being able to misreport every other type — or costly misreporting, the revelation principle is known to hold only under certain conditions [23]. In this paper, we only consider the standard mechanism design setting in which every type can freely misreport any other type, but our techniques can be generalized to the other settings as well.
Individually-rational mechanisms. When payments are allowed, it is standard to impose individual-rationality (IR) (also known as voluntary-participation) constraints on the mechanism, which roughly say that the agent should never be made worse off by participating in the mechanism. In this paper, we consider two versions of IR constraints:
• A mechanism M is overall IR if the overall utility of the agent is nonnegative, i.e., uMA (∅) ≥ 0. This ensures that the agent is willing to participate in the overall mechanism.
• A mechanism M is dynamic IR if the onward utility of the agent is nonnegative for every history h and current state s, i.e., uMA (h, s) ≥ 0 for all h ∈ H and s ∈ S. This stronger notion of IR further ensures that the agent has no incentive to leave the mechanism at any time.
As discussed in later sections, our algorithms work for all 3 cases regarding IR constraints: no IR (which results in an unbounded objective value if payments are allowed and valued by the principal), overall IR, and dynamic IR.

heading: 3 Computation of Optimal Mechanism

text: In this section, we investigate the computational problem of finding an optimal dynamic mechanism, which maximizes the principal’s overall utility. For concreteness, we assume that all components of the dynamic environment, including the time horizon T , state and action spaces S and A, valuation functions vP and vA, and transition operator P , are given explicitly as input.

heading: 3.1 Hardness Result for Long-Horizon Environments

text:
First we show that the problem with an arbitrarily large time horizon T is intractable. In general, it takes exponentially many parameters in T to describe a dynamic mechanism, which immediately rules out the possibility of computing a flat representation of an optimal mechanism in polynomial time. However, this leaves the possibility of computing succinct representations, e.g., an oracle which maps extended histories to distributions over actions. Our hardness result shows that it is hard to approximate the principal’s maximum utility within a constant factor, which rules out the possibility of such succinct representations that can be efficiently evaluated, assuming P 6= NP. The proof of the theorem, as well as all other proofs, are deferred to the appendices.
Theorem 1. When the time horizon T can be arbitrarily large, it is NP-hard to approximate the principal’s maximum utility within a factor of 7/8 + ε for any ε > 0.

heading: 3.2 Algorithm for Short-Horizon Environments

text:
Now we give a polynomial-time algorithm for computing an optimal mechanism when T is a constant. Our algorithm is based on a delicate linear program (LP) formulation, which relies on the following notation and concepts.
Feasible history-state pairs. A history-state pair (h, s), where h = (s1, a1, . . . , st, at), is ifeasible if Pj(sj , aj , sj+1) > 0 for every j ∈ {i, i + 1, . . . , t − 1}, and Pt(st, at, s) > 0. In other words, starting from si and taking the actions specified in h, there is a positive probability that the rest of the history and the state s are generated from the transition operator. We say a pair (h, s) is feasible if it is 1-feasible.
Feasible extensions. For two history-state pairs (h, s) and (h′, s′) where h = (s1, a1, . . . , st, at) and h′ = (s′1, a ′ 1, . . . , s ′ t′ , a ′ t′), we say that (h
′, s′) feasibly extends (h, s), i.e., (h, s) ⊆ (h′, s′), if (h, s) = (h′, s′), or the following conditions hold simultaneously:
• t = |h| < |h′| = t′. • For any i ∈ [t], (si, ai) = (s′i, a′i) (this holds automatically when h = ∅ and therefore |h| = 0). • s = s′t+1.
• (h′, s′) is (|h|+ 1)-feasible (note that this does not require h itself to be feasible).
Extended transition operator. For notational simplicity we define the following extended transition operator PEt : S ×A → ∆(S) for all t ∈ {0} ∪ [T ], such that
PEt (s, a, s ′) =
{ Pt(s, a, s
′), if Pt(s, a, s′) > 0 1, otherwise .
In words, the extended transition operator assigns phantom probability 1 to each way of transitioning that happens with probability 0 (so PEt (s, a) does not always normalize to 1). As a shorthand, let PE0 (s ′) = PE0 (s, a, s ′) for some s ∈ S and a ∈ A (the specific choice does not matter). The extended transition operator helps in constructing the flow and IC constraints below and simplifies the formulation. In particular, we always have PEt (s, a, s ′) > 0.
Last state-action pair. For a history h ∈ H where h = (s1, a1, . . . , st, at), we use last(h) as a shorthand for the last state-action pair, i.e., last(h) = (st, at). In particular, when h = ∅, last(h) can be any state-action pair (the choice does not affect our results — it is merely a simplifying shorthand).
Now we are ready to describe the LP formulation. The complete formulation is given in Figure 1. The formulation is for nonnegative payments and dynamic IR constraints — we will discuss later
how the formulation can be modified to allow other types of constraints. Below, we describe each of its components.
Variables, flow constraints, and the corresponding mechanism. There are 5 classes of variables in the LP:
• x(h, s, a): the absolute, unconditional probability that the mechanism reaches state s via history h, and takes action a.
• y(h, s): the payment for history-state pair (h, s), scaled by the probability that the mechanism reaches s via h (i.e., z(h, s)).
• z(h, s): the probability that the mechanism reaches state s via history h, which by definition satisfies z(h, s) = ∑ a∈A x(h, s, a).
• u(h, s): the onward utility of the agent at state s with history h assuming truthful reporting, scaled by the probability that the mechanism reaches s via h (i.e., z(h, s)).
• u(h, s, s′): the onward utility of the agent at state s with history h if the agent misreports s′, assuming truthful reporting in the future, scaled by the probability that the mechanism reaches s′ via h (i.e., z(h, s′)).
The flow constraints (Eq. (2)-(4)) enforce roughly the above interpretation of variables to x(h, s, a) and z(h, s), except for ways of transition that have probability 0. For each way of transition with probability 0, the extended transition operator assigns phantom probability 1. This phantom probability is not counted in the objective function (because only feasible history-state pairs are counted) or in the utility variables u(h, s) (because only feasible extensions are counted). So, the phantom probability does not affect the principal’s or the agent’s utility assuming truthful reporting. Instead, together with other constraints, it guarantees that the mechanism behaves well even for history-state pairs that appear with probability 0 under truthful reporting, which is necessary for the mechanism to be IC (see later paragraphs). Under the above interpretation, the LP variables (and in particular, x(h, s, a), y(h, s) and z(h, s)) naturally correspond to a mechanism M = (π, p). Formally, for each h ∈ H, s ∈ S:
• If z(h, s) > 0, then p(h, s) = y(h, s)/z(h, s),
and for each a ∈ A, π(h, s, a) = x(h, s, a)/z(h, s).
• If z(h, s) = 0, then let π(h, s) be an arbitrary distribution over A, and p(h, s) = 0.
The feasibility of the mechanism (i.e., every π(h, s) is a distribution over A and every p(h, s) is nonnegative) is guaranteed by constraints (2), (9) and (10). We remark that while the mechanism constructed from the LP variables may not be unique, effectively this makes no difference, since the parts of the mechanism that are chosen arbitrarily can never be accessed when executing the mechanism. This is because z(h, s) = 0 only if at some point in the history h, there is an action that the mechanism would never play given the reported states and actions before that. In particular, the above does not simply apply to all history-state pairs (h, s) that are reached with probability 0 under truthful reporting, in which case z(h, s) may still be positive due to the extended transition operator. Moreover, given any mechanism, one can construct LP variables in a similar way, such that the mechanism constructed from these variables is the same as the original mechanism (modulo the unreachable parts). In other words, the above correspondence is effectively bijective.
The objective. The objective function of the LP (Eq. (1)) is precisely the overall utility of the principal under the mechanism constructed above, assuming truthful reporting. This is captured by the following lemma. Lemma 1. Let M = (π, p) be the mechanism constructed from variables x(h, s, a), y(h, s), and z(h, s) which satisfy the flow constraints. Then
uMP (∅) = ∑
h∈H,s∈S:(h,s) is feasible (∑ a∈A vP|h|+1(s, a) · x(h, s, a) + y(h, s) ) .
From this lemma, it is clear that the objective of the LP is the natural quantity to maximize.
Utility. The utility constraints (Eq. (5)) collect the agent’s onward utility, where u(h, s) is equal to the agent’s onward utility in state s from history h, assuming truthful reporting, scaled by z(h, s). This is captured by the following lemma. Lemma 2. Let M = (π, p) be the mechanism constructed from variables x(h, s, a), y(h, s), and z(h, s) which satisfy the flow and utility constraints. For all h ∈ H, s ∈ S,
u(h, s) = z(h, s) · uMA (h, s).
The proof of Lemma 2 is essentially the same as that of Lemma 1. Given the correspondence to the agent’s utility uMA (h, s), the utility variables u(h, s) act as auxiliary variables in IC constraints.
IC constraints. IC constraints are a key component of the LP formulation. There are two families of IC constraints: collecting the agent’s scaled utility from single-step misreporting (Eq. (6)), and subsequently restricting the mechanism such that there is no incentive for misreporting (Eq. (7)). In Eq. (6), we build variables u(h, s, s′), which is supposed to be the onward utility of the agent in state s from history h misreporting s′, assuming truthful reporting in the future, scaled by z(h, s′) (rather than z(h, s)). This is captured by the following lemma. Lemma 3. Let M = (π, p) be the mechanism constructed from variables x(h, s, a), y(h, s), and z(h, s) which satisfy the flow constraints, the utility constraints, and Eq. (6). Then the following statement holds: for all h ∈ H, s, s′ ∈ S, let reporting strategy rh,s,s′ be such that
rh,s,s′(h ′, s′′) =
{ s′, if h = h′ and s = s′′
s′′, otherwise .
That is, rh,s,s′ misreports s′ only in state s from history h, and reports truthfully otherwise. Then for all h ∈ H, s, s′ ∈ S,
u(h, s, s′) = z(h, s′) · uM,rh,s,s′A (h, s).
Given Lemma 3, Eq. (7) then guarantees that the mechanism M is robust against single-step misreporting for all reachable history-state pairs. Lemma 4. Let M = (π, p) be the mechanism constructed from variables x(h, s, a), y(h, s), and z(h, s) which satisfy the flow constraints, the utility constraints, and Eq. (6). The following is true if and only if the LP variables also satisfy Eq. (7): for all h ∈ H, s, s′ ∈ S where (h, s) is reachable by the mechanism M ,
uMA (h, s) ≥ u M,rh,s,s′ A (h, s).
We then show that a mechanism is IC if and only if there is no incentive for single-step misreporting, which directly implies that the mechanismM constructed from the LP variables is IC. This is captured by the following lemma. Lemma 5. Let M = (π, p) be the mechanism constructed from variables x(h, s, a), y(h, s), and z(h, s) which satisfy the flow constraints, the utility constraints, and Eq. (6). Then M is IC if and only if the LP variables also satisfy Eq. (7).
IR constraints, feasible actions, and feasible payments. These constraints are straightforward given the correspondence between the LP variables and the mechanism that we have discussed above. Note that while Eq. (8) is for dynamic IR (i.e., the agent has no incentive to leave the mechanism at any point) and Eq. (10) is for nonnegative payments, it is easy to replace them with similar constraints that correspond to overall IR or no payments. See Appendix C for more details.
Optimality of LP solution. Given the above facts, we are ready to state and prove the main result of the paper. Theorem 2. There is an algorithm which computes an optimal IC and (optionally) IR dynamic mechanism, with or without payments, in time O(poly(|S|T , |A|T , L)), where L is the number of bits required to encode each of the input parameters. In particular, when T is constant, the algorithm runs in polynomial time.

heading: 4 The Case of Myopic Agents: Characterization and Faster Algorithm

text: In this section, we briefly discuss a special case of the problem of computing optimal dynamic mechanisms, namely the case where the agent is myopic, or, equivalently, the agent has a discount factor of 0. While our LP-based algorithm still applies, as we will see below, optimal mechanisms for myopic agents enjoy a succinct representation in this case, which also enables a faster algorithm that scales only linearly in the time horizon T . See Appendix D for more details, including the formal definition of myopic agents and the complete description of the algorithm.

heading: 4.1 Characterization of Optimal Mechanisms

text:
We first show that when the agent is myopic, without loss of generality, the actions and payments specified by an optimal mechanism depend only on the time, the previous state, the previous action and the current state (we call such a mechanism a succinct mechanism), instead of the entire history-state pair. Lemma 6. Fix a dynamic environment. When the agent is myopic, for any IC mechanismM = (π, p), there is another IC mechanism M ′ = (π′, p′) (which is IR whenever M is) such that
• uM ′
P (∅) ≥ uMP (∅), and
• for all h ∈ H, s ∈ S, π′ and p′ depend only on |h|, sp, ap and s, where (sp, ap) = last(h).
Moreover, the above is true regardless of whether payments are allowed, or which IR constraints are required.

heading: 4.2 Faster Algorithm for Myopic Agents

text:
Based on the above characterization, we present a faster algorithm for computing an optimal mechanism in the face of a myopic agent. In particular, the time complexity of this algorithm depends only linearly on the time horizon T , making it feasible for dynamic environments with a long time horizon. This is in contrast with the case of patient agents, for which, as we have seen, the long-horizon problem is hard to approximate. The algorithm uses as a subroutine a blackbox algorithm that computes an optimal IC (and optionally IR) mechanism in static environments, with or without payments. It is known that such an algorithm can be implemented using linear programming, and in some cases in more efficient ways [10, 12, 37]. Theorem 3. When the agent is myopic, Algorithm ?? computes an optimal IC and (optionally) IR dynamic mechanism, with or without payments, in time
O(T |S||A| · Tstat(|S|, |A|, L)) = O(T · poly(|S|, |A|, L)), where Tstat is the time complexity of the blackbox algorithm used for computing an optimal IC (and optionally IR) mechanism in static environments, and L is the number of bits required to encode each of the input parameters.

heading: 5 Conclusion

text:
We studied automated dynamic mechanism design and showed that, while it is computationally hard to find (even approximately) optimal mechanisms when (1) facing a patient agent and (2) the horizon is long, when either of these two conditions is dropped, an optimal mechanism can be found efficiently. An interesting future direction is to generalize our results to related problems with a stronger learning flavor, e.g., reinforcement learning with IC and/or IR constraints.
Besides using our algorithms directly for appropriate applications, the experimental results that they enable (including those that we presented in Appendix F) can guide new theory. For example, can we rigorously prove the benefit of facing a patient agent when the setting is not all too adversarial, and perhaps even characterize the transition point at which facing a patient agent becomes better than facing a myopic one? Analytically derived mechanisms can also be compared to these experimental results to see how close to optimal in performance they are. Finally, close inspection of the actual mechanisms generated by our algorithms may reveal insights that can be used to analytically design new mechanisms.
Funding Transparency Statement
Funding in direct support of this work: NSF grant IIS-1814056.

title: Automated Dynamic Mechanism Design


summaries: This paper combines the differentiable graph structure learning and neural architecture search together. By conducting the two iteratively, the framework can automate GNN design for tasks without given graph. It also provide an analysis that NAS could help balance GNN and MLP by the informativeness of graph against structure.

summaries: The paper investigates the ability of gradient-based NAS method on selecting desired operators to construct GNN architectures. It shows that DARTs method can discriminate the benefits of different operators based on the graph structure but suffers from the noised in graph. Based on the findings, the authors propose to add an extra graph-structure learning term during the optimization process to denoise the graph structure and shows improved performance compared to existing baselines.

summaries: This paper analyzes how DARTS selects its desired architectures, and shows that the gradient based NAS suffers from noises hidden in the graph, resulting in searching suboptimal GNN architectures. Besides, this paper improves the gradient based NAS methods by employing graph structure learning as a denoising process in the search procedure, and thus proposes GASSO, a more effective NAS algorithm. The theoretical analysis given by this paper is important and interesting, but the technical improvement lacks experimental analysis and proof, and important comparison experiments are missing.

summaries: This paper proposed one graph neural architecture search method to learn graph structures in one differentiable way. It makes an investigation on how NAS select the operations in GNNs, and then evaluate the NAS method on a set of synthetic datasets with different structures. This paper proposed one feature smoothness constraints which can learn the graph architecture in one differentiable way.

abstractText: Discovering ideal Graph Neural Networks (GNNs) architectures for different tasks is labor intensive and time consuming. To save human efforts, Neural Architecture Search (NAS) recently has been used to automatically discover adequate GNN architectures for certain tasks in order to achieve competitive or even better performance compared with manually designed architectures. However, existing works utilizing NAS to search GNN structures fail to answer the question How NAS is able to select the desired GNN architectures. In this paper, we investigate this question to solve the problem, for the first time. We conduct theoretical analysis and measurement study with experiments to discover that gradient based NAS methods tend to select proper architectures based on the usefulness of different types of information with respect to the target task. Our explorations further show that gradient based NAS also suffers from noises hidden in the graph, resulting in searching suboptimal GNN architectures. Based on our findings, we propose a Graph differentiable Architecture Search model with Structure Optimization (GASSO), which allows differentiable search of the architecture with gradient descent and is able to discover graph neural architectures with better performance through employing graph structure learning as a denoising process in the search procedure. Extensive experiments on real-world graph datasets demonstrate that our proposed GASSO model is able to achieve the state-of-the-art performance compared with existing baselines.

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In Proceedings of the 5th International Conference on Learning Representations,

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio

title: Graph attention networks

venue: In Proceedings of the 6th International Conference on Learning Representations,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

venue: In 7th International Conference on Learning Representations,

authors:
Guohao Li
Guocheng Qian
Itzel C Delgadillo
Matthias Muller
Ali Thabet
Bernard Ghanem

title: Sgas: Sequential greedy architecture search

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yang Gao
Hong Yang
Peng Zhang
Chuan Zhou
Yue Hu

title: Graph neural architecture search

venue: In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,

authors:
Barret Zoph
Quoc V Le

title: Neural architecture search with reinforcement learning

authors:
Hieu Pham
Melody Y Guan
Barret Zoph
Quoc V Le
Jeff Dean

title: Efficient neural architecture search via parameter sharing

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Hanxiao Liu
Karen Simonyan
Yiming Yang

title: Darts: Differentiable architecture search

venue: In Proceedings of the 7th International Conference on Learning Representations,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In Advances in neural information processing systems,

authors:
H. Li
X. Wang
Z. Zhang
J. Ma
W. Zhu

title: Intention-aware sequential recommendation with structured intent transition

venue: IEEE Transactions on Knowledge and Data Engineering,

authors:
Fangda Gu
Heng Chang
Wenwu Zhu
Somayeh Sojoudi
Laurent El Ghaoui

title: Implicit graph neural networks

venue: Advances in Neural Information Processing Systems,

authors:
Ming Jin
Heng Chang
Wenwu Zhu
Somayeh Sojoudi

title: Power up! robust graph convolutional network via graph powering

venue: In 35th AAAI Conference on Artificial Intelligence,

authors:
Heng Chang
Yu Rong
Tingyang Xu
Wenbing Huang
Somayeh Sojoudi
Junzhou Huang
Wenwu Zhu

title: Spectral graph attention network with fast eigen-approximation

venue: arXiv preprint arXiv:2003.07450,

authors:
Daniel Zügner
Amir Akbarnejad
Stephan Günnemann

title: Adversarial attacks on neural networks for graph data

venue: In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence,

authors:
Daniel Zügner
Stephan Günnemann

title: Adversarial attacks on graph neural networks via meta learning

authors:
Dingyuan Zhu
Ziwei Zhang
Peng Cui
Wenwu Zhu

title: Robust graph convolutional networks against adversarial attacks

venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Huijun Wu
Chen Wang
Yuriy Tyshetskiy
Andrew Docherty
Kai Lu
Liming Zhu

title: Adversarial examples for graph data: Deep insights into attack and defense

authors:
Negin Entezari
Saba A. Al-Sayouri
Amirali Darvishzadeh
Evangelos E. Papalexakis

title: All you need is low (rank): Defending against adversarial attacks on graphs. In WSDM ’20

venue: The Thirteenth ACM International Conference on Web Search and Data Mining,

authors:
Wei Jin
Yao Ma
Xiaorui Liu
Xianfeng Tang
Suhang Wang
Jiliang Tang

title: Graph structure learning for robust graph neural networks. In KDD ’20

venue: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,

authors:
Liang Yang
Zesheng Kang
Xiaochun Cao
Di Jin
Bo Yang
Yuanfang Guo

title: Topology optimization based graph convolutional network

authors:
Dongsheng Luo
Wei Cheng
Wenchao Yu
Bo Zong
Jingchao Ni
Haifeng Chen
Xiang Zhang

title: Learning to drop: Robust graph neural network via topological denoising

authors:
Ke Tu
Jianxin Ma
Peng Cui
Jian Pei
Wenwu Zhu

title: Autone: Hyperparameter optimization for massive network embedding

venue: In KDD ’19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,

authors:
Xin Wang
Shuyi Fan
Kun Kuang
Wenwu Zhu

title: Explainable automated graph representation learning with hyperparameter importance

venue: In Proceedings of the 38th International Conference on Machine Learning,

authors:
Zhikun Wei
Xin Wang
Wenwu Zhu

title: Autoias: Automatic integrated architecture searcher for click-trough rate prediction

venue: In CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management,

authors:
Yue Liu
Xin Wang
Xue Xu
Jianbo Yang
Wenwu Zhu

title: Meta hyperparameter optimization with adversarial proxy subsets sampling

authors:
Zhao Zhong
Junjie Yan
Wei Wu
Jing Shao
Cheng-Lin Liu

title: Practical block-wise neural network architecture generation

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Yuhang Jiang
Xin Wang
Wenwu Zhu

title: Hardware-aware transformable architecture search with efficient search space

venue: In IEEE International Conference on Multimedia and Expo,

authors:
Yijian Qin
Xin Wang
Peng Cui
Wenwu Zhu

title: Gqnas: Graph q network for neural architecture search

venue: In 21st IEEE International Conference on Data Mining,

authors:
Lingxi Xie
Alan Yuille

title: Genetic cnn

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Hanxiao Liu
Karen Simonyan
Oriol Vinyals
Chrisantha Fernando
Koray Kavukcuoglu

title: Hierarchical representations for efficient architecture search

authors:
Sirui Xie
Hehui Zheng
Chunxiao Liu
Liang Lin

title: Snas: stochastic neural architecture search

authors:
Kaixiong Zhou
Qingquan Song
Xiao Huang
Xia Hu

title: Auto-gnn: Neural architecture search of graph neural networks

authors:
Jiaxuan You
Zhitao Ying
Jure Leskovec

title: Design space for graph neural networks

authors:
Chaoyu Guan
Xin Wang
Wenwu Zhu

title: Autoattend: Automated attention representation search

authors:
Guohao Li
Matthias Müller
Ali K. Thabet
Bernard Ghanem

title: Deepgcns: Can gcns go as deep as cnns

venue: IEEE/CVF International Conference on Computer Vision,

authors:
Yue Wang
Yongbin Sun
Ziwei Liu
Sanjay E. Sarma
Michael M. Bronstein
Justin M. Solomon

title: Dynamic graph CNN for learning on point clouds

venue: ACM Trans. Graph.,

authors:
Zhijie Deng
Yinpeng Dong
Shifeng Zhang
Jun Zhu

title: Understanding and exploring the network with stochastic architectures

venue: In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems,

authors:
Geoffrey E. Hinton
Nitish Srivastava
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Improving neural networks by preventing co-adaptation of feature detectors

authors:
Stefan Lee
Senthil Purushwalkam
Michael Cogswell
David J. Crandall
Dhruv Batra

title: Why M heads are better than one: Training a diverse ensemble of deep networks

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: Dropedge: Towards deep graph convolutional networks on node classification

venue: In 8th International Conference on Learning Representations,

authors:
Wen-bing Huang
Tong Zhang
Yu Rong
Junzhou Huang

title: Adaptive sampling towards fast graph representation learning

venue: In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems,

authors:
Jie Chen
Tengfei Ma
Cao Xiao

title: Fastgcn: Fast learning with graph convolutional networks via importance sampling

venue: In 6th International Conference on Learning Representations,

authors:
William L. Hamilton
Zhitao Ying
Jure Leskovec

venue: In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems,

authors:
Xuanyi Dong
Yi Yang

title: Searching for a robust neural architecture in four gpu hours

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Asaf Noy
Niv Nayman
Tal Ridnik
Nadav Zamir
Sivan Doveh
Itamar Friedman
Raja Giryes
Lihi Zelnik

title: Asap: Architecture search, anneal and prune

venue: In International Conference on Artificial Intelligence and Statistics. PMLR,

authors:
Niv Nayman
Asaf Noy
Tal Ridnik
Itamar Friedman
Rong Jin
Lihi Zelnik

title: Xnas: Neural architecture search with expert advice

venue: In Advances in Neural Information Processing Systems,

heading: 1 Introduction

text:
In real-world applications including social networks, e-commerce, traffics, and biochemistry, a variety of relational data can be represented as graphs. This motivates the advent of graph neural networks (GNNs) based models such as GCN [1], GAT [2] and GIN [3], which are designed to learn and extract knowledge from the relational graph-structured data. To utilize information in graph structure and node features, GNNs follow a recursive message passing scheme where nodes aggregate information from their neighbors in each layer, making great success in various graph related tasks. Given that discovering ideal GNN architectures for different tasks is labor intensive and time consuming, graph architecture search [4, 5] employs the ideas of neural architecture search (NAS) [6–8] to facilitate the automatic design of optimal GNN architectures so that a large number of human efforts can be saved. These automatically generated GNNs can achieve competitive or even better performance compared with manually designed GNNs on graph related tasks. 2
Nevertheless, existing works on graph architecture search mainly focus on designing search space and search strategy, ignoring the fundamental mechanism in adopting NAS for automatic GNN ∗Corresponding Authors. 2Our code will be released at https://github.com/THUMNLab/AutoGL
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
structure search and failing to answer the following questions. (i) How does graph architecture search select its desired architectures? and (ii) How optimal are the architectures selected by graph neural architecture search? Answers to these questions can help us to understand the NAS and GNN mechanism in gathering messages, leading us to design better GNN structures for certain tasks. However, the failure of existing works in answering the questions significantly limits their capabilities of designing powerful GNN architectures.
In this paper, we answer the above question through exploring how graph neural architecture search is able to select the desired GNN architectures. Given that neural architecture search approaches in literature can be mainly categorized into several groups, i.e., gradient based (DARTS [8]), reinforcement learning based, evolution algorithm based, and Bayesian optimization based methods, we only focus on gradient based architecture search approach in this work and leave investigations into the other groups as future works. We theoretically analyze DARTS behavior and find that DARTS prefers operations who can help to correct the predictions on hard data. Further analysis on graph data shows that different operations fit graphs with different amount of information in the node features and graph structures. Measurement study via designing synthetic experiments corroborates our theory. We find that DARTS on GNN is able to evaluate the usefulness of information hidden in node features and graph structure with respect to the target task, then automatically select appropriate operations based on the evaluated usefulness for GNN architecture. On the other hand, we also discover that the performance of gradient based graph architecture search (e.g., DARTS) can also be deteriorated by noises inside the graphs, leading to suboptimal architectures.
To solve the problem, we propose Graph differentiable Architecture Search model with Structure Optimization (GASSO), which allows differentiable search of the architecture with gradient descent and is capable of searching the optimal architecture as well as adjusting graph structure adaptively through a joint optimization scheme. The graph structure adjustment in our proposed GASSO model serves as an adaptive noise reduction to enhance the architecture search performance. The framework of GASSO is shown in Figure 1. We employ differentiable graph structure to allow us to optimize graph structure by gradient based methods during the training process, and we use hidden feature smoothness to evaluate the edge importance and constrain edge weights. Overall, we jointly optimize the parameters of neural architecture and graph structure in an iterative updating manner. We evaluate our model on several widely used graph benchmark datasets including CiteSeer, Cora and PubMed. The experimental results show that our proposed GASSO model can outperform state-of-the-art methods and demonstrate a better denoising ability than existing graph architecture search model using DARTS and other GNNs models. To summarize, this paper makes the following contributions: (1) We theoretically explore how graph neural architecture search is able to select the desired GNN architectures, to the best of knowledge, for the first time, showing that i) gradient based graph
architecture search prefers operations who can help to correct the predictions on hard data, and ii) different operations fit graphs with different amount of information in the node features and graph structures. (2) We design measurement study with experiments to show that i) gradient based graph architecture search is able to select operations based on the usefulness of the information in graphs, and ii) noises in graph features and structures can deteriorate the architecture search performance. (3)We propose Graph differentiable Architecture Search model with Structure Optimization (GASSO), which searches the optimal architecture as well as adjusts graph structure adaptively through a joint optimization scheme. Experimental results on several graph benchmark datasets demonstrate the superiority of our GASSO model against state-of-the-art methods.

heading: 2 Related Work

heading: 2.1 Graph Neural Network

text: As an effective framework for graph representation learning, GNN [1–3, 9–13] follows a neighborhood aggregation scheme. At each iteration, representations of nodes are generated through aggregating their neighbors’ representations. For instance, graph convolutional neural network (GCN) [1] takes the average of all neighbor nodes’ features as aggregation. Different from GCN, Graph Attention Network (GAT) [2] treats neighbors unequally. It calculates the attention on each neighbor. Therefore, the aggregation can emphasize representations of more important neighbor nodes with larger attentions. The vectorized representation of a given node in the graph after k iterations can capture both structural (topological) and semantic (attributed) information within the region of the target node’s k-hop neighborhood. As such, GNN characterizes the whole graph by aggregating node representations [1, 14], making themselves achieve the state-of-the-art results for tasks including node and graph classifications. Like other types of deep neural networks, GNNs are vulnerable to noise and adversarial attacks. Graph attackers usually adopt data perturbation by changing the node features or graph structure [15, 16]. How to denoise and defend graph adversarial attacks is also a popular question [17–19]. Graph structure learning is presented in recent GNN methods [20–22]. Since graph structure plays an important role in GNN scheme, certain noise in the original graph is extremely harmful to GNNs. Graph structure learning aims to generate a clean graph during the training procedure. To achieve this, prior constraints such as low rank and smoothness are utilized. Learning a new graph structure improves the model’s ability of denoising, as well as its robustness to adversarial attacks of GNNs.

heading: 2.2 (Graph) Neural Architecture Search

text: Recent years have witnessed a significant surge in research on automated machine learning, including hyper-parameter optimization [23–26] and Neural Architecture Search (NAS) methods [6–8, 27–30] aim at designing an neural architecture automatically for certain tasks. Since the architecture search space is discrete, reinforce learning [6, 7] and evolution algorithm [31, 32] are often used in NAS methods. Besides, transferring the discrete architecture search space into a differentiable space is another strategy for solving the NAS problems. DARTS [8] and SNAS [33] construct a super network where each operation is mixed by all candidate operations, making it possible to update the architecture as well as the weights simultaneously through the classical gradient descent method. NAS has also been applied to graph tasks, achieving competitive performance with the state-of-the-art performances. Existing works [4, 5, 34–36] mainly focus on defining a proper search space and search strategy for GNNs. However, the mechanism of NAS methods to select architectures and the relationship between NAS methods and GNN denoising ability have not been noticed.

heading: 3 Exploring Architecture Search for Graph

heading: 3.1 Preliminaries: Differentiable Architecture Search

text:
We use DARTS [8], a representative NAS method with both conciseness and effectiveness as the exploration object in this paper. In DARTS, neural architecture is represented as a directed acyclic graph (DAG) where the input data is the source node, the output is the sink node, and the edges represent operations (e.g. a GCN layer, or a linear layer) adopted on the data. Following a micro
search space setting, DARTS only searches which operation should be selected and how the nodes in the DAG should be connected. The calculation inside each operation is predefined.
There are two phases in DARTS procedure, the searching phase and the evaluation phase. In searching phase, a super network (shown in Figure 1) is constructed, where edges exist between each two nodes, i.e., ei,j exists, ∀0 ≤ i < j ≤ N − 1. Each edge is a mixed operation that can be calculated by ei,j(xi) = ∑ o∈O exp{αoi,j}∑ o′∈O exp{αo ′ i,j} · o(xi), where xi is the output of node i, O is candidate operation set, α is learnable architecture parameters. After calculating the mixed weighted sum, each node aggregates all input edges by xj = ∑ i<j ei,j(xi). As such, all possible operations at all possible positions are contained in the super network. DARTS uses gradient based methods to optimize both architecture parameters α and operation parameters by a bi-level optimization scheme. Since the parameters are all trained in the super network, W of different architectures are shared with each other, the mathematical formulation is as follows:
min A
Lval(W ∗,A) s.t. W ∗ = argminWEA∈Γ(A)Ltrain(W,A). (1)
Here, Γ(A) is architecture distribution learned in the searching phase. In this formulation, W and A are independently learned, improving the search efficiency.
At the end of the training procedure, the operation with the maximum α of each node is chosen, and the selected operations compose the optimal architecture. Then comes to evaluation phase, a new network based on the designed architecture is constructed. This network will be trained from scratch and finally get tested after retraining.

heading: 3.2 Theoretical Analysis of Architecture Parameters

text:
We next explore the DARTS behavior on graph task, aiming to answer (i) how does graph neural architecture search select its desired architectures? and (ii) how optimal are the architectures selected by graph neural architecture search? We firstly provide theoretically analysis on (i).
Mixed operation is the key part in DARTS, where the architecture parameters controls the operation selection. However, there is no theoretical analysis on how these architecture parameters change according to the performance of different operations. To explore how these architecture parameters change during training procedure, we firstly analyze a simple scene of a binary classification problem, and there is only one layer with two candidate operations needs searching in the super network. The mixed operation is F (xk) = o1f1(xk) + o2f2(xk). Here, o1 =
exp{α1} exp{α1}+exp{α2} and o2 =
exp{α2} exp{α1}+exp{α2} . f1 and f2 are candidate operations. We use gradient methods to minimize binary cross entropy loss combined with a sigmoid function: H(F ) = − ∑ k[yk · lnσ(F (xk)) + (1− yk) · ln(1− σ(F (xk)))]. Then we can conduct following theorem with proof in Appendix A.1.
Theorem 1 The changes of operation weights on after one step of gradient descent w.r.t. architecture parameters depend on the score ∑ k[wkfn(xk)], where wk = σ(F (xk)) − yk. Specifically, if∑
k[wkf1(xk)] < ∑ k[wkf2(xk)], then o1 increases and o2 decreases, and vice versa.
Theorem 1 tells us that DARTS judges different candidate operations by a score, which can be seen as a weighted sum of logits. As for the weights, we have wk ∈ (−1, 1), whether it is positive or negative depends on the data label. If yk = 0, the weight is a positive number σ(F (xk)), which means those data with bad prediction given by the super network have larger weights. If only considering those scores with positive weights, the candidate operation giving better prediction has smaller logits. Summing them up will get smaller score and increase architecture weight on. We can reach a similar conclusion if we analyze data with label yk = 1. In a nutshell, we know DARTS prefers those operations which can help to correct the predictions over hard data.

heading: 3.3 Synthetic Graph Experiment Setting

text:
We further construct a synthetic graph which is composed of 600 nodes with 10 types, 60 nodes per type. The node features of a certain type follow a Gaussian distribution N (µi, σ1) (to be simple, we write one-dimension Gaussian distribution here, all dimensions are the same and independent, the same below), where µi is sampled from another Gaussian distribution N (0, σ2). σ1 and σ2 are predefined parameters. Here we can use β = σ2σ1 to represent the difficulty of classifying nodes by
their features. If β is large, intra-group node features are close while inter-group node features are far away ("group" denotes node label here), thus it is easy to classify nodes by their features, vice versa. This difficulty also reflexes the ratio of noises and type-relevant information inside the features.
As for the edges, we also set two parameters p1 and p2. p1 is the probability of generating an edge between two intra-group nodes while p2 is that of two inter-group nodes. We define δ = p1p2 , which can reflex the difficulty of classifying nodes by message passing scheme. If δ is large, intra-group nodes appear more often in the neighborhood, making it easier to classify nodes by aggregating neighborhood information, and vice versa. This difficulty also reflexes the ratio of noises and type-relevant information inside the graph structure.
We generate synthetic graphs with different β and δ, then split the nodes in supervised setting for node classification task. To theoretically explore how different operations behave under different settings, we analyze a simple scene here. We only consider one target node, which is connected with only two classes of nodes, one is the same as its own class. The node feature channel is 1. The candidate operations only contain linear and GCN [1], they can represent two types of operations, message-passing operations and those without message passing.
Theorem 2 Under our synthetic graph setting, let n be the number of edges connected the target node, the relative distance between the centers of two classes is |D|, which follows D ∼ N (0, β2). Then, the probability of that linear operation gives more accurate prediction than GCN on the target node is P = Φ[ √ 2n|D|
(δ+1) √ (n+1)(n+2) ].
The proof of Theorem 2 is in Appendix A.2. Theorem 2 shows that the information gained by different operations are influenced by β, δ and n. When β increases, the expectation of |D| increases, thus the probability to choose linear increases. When δ increases, the probability to choose GCN increases. the number of edges can influence the probability as well, but weaker than β and δ.

heading: 3.4 Operation Selection

text:
To discover how β and δ influence DARTS in practice, we generate synthetic graphs by controlling one variable when we change the other one. We set β = 0.4 while changing δ, and set δ = 4.0 while changing β. For each setting of β and δ, we generate 100 different graphs and adopt DARTS on it. We choose GCN [1], GAT [2], GIN [3], MRConv [37], EdgeConv [38], linear, skip connect and zero operation as the candidate operations in DARTS. We set the number of operations to be 6. Since GNNs usually are very shallow, we mainly explore DARTS behavior on operation selection but not the connections. We count the times of each operation that appears in the optimal architecture and show the frequency in Figure 2.
According to the results above, we found that for different graphs, DARTS suggests using different operations. To be more specific, for graphs with more structure information (large δ) less feature information (small β), DARTS tends to select typical message passing operations, such as GIN. When there is less structure information (small δ) and more feature information (large β), DARTS is more likely to select operations like linear and skip connect to prevent message passing. The results agree with Theorem 2.
Here we can give some explanations for (i) by combining two theorems and the experiment results. A GNN can be regarded as an information extractor, which collects useful messages inside the graph to give accurate node classification. The operations in the search space have different ability to extract information from node feature and graph structure, e.g., GCN has the ability to extract information from graph structure but reduce the influence of the node’s own feature, while linear only uses the feature information and ignores graph structure. DARTS aims to find the optimal information extractor to help correct the prediction of the super network. To achieve this, it should judge how the node feature and graph structure is useful for the task. If the graph structure is useful, DARTS will take advantage of it and select operations that can extract information from the topology. If the node features are useful, DARTS will decide to prevent message passing to make full use of the features.
In addition, we can find that the heat map of the two experiment results are very similar, revealing that DARTS judges the relative amount of the two types of information but not the absolute amount. This also agrees with Theorem 2, e.g., as long as node features are more useful than graph structure, the structure is thought to have certain noise that is harmful to the task, so message passing is preferred to be prevented.
On denoising issue. We have concluded that DARTS has the ability to judge which part inside the graph is useful and select proper operations. This behavior motivates us to test the denoising ability of DARTS. When random noise perturbs a clean graph, DARTS can rejudge the usefulness of these two parts and give new architecture suggestions according to the current condition. Thus DARTS may have denoising ability. We make experiments on real graph datasets in Section 5. The results show its denoising ability is unstable. Therefore, we move on to explore how accurate DARTS selects operations.

heading: 3.5 Accuracy of Operation Selection

text:
To further explore the answer to (ii), we save the architectures searched on graphs with each β and δ in Figure 2, and transfer them on graphs with different settings to do the evaluation. We also control one variable while changing the other one. The results are shown in Table 1.
Following normal sense, the architecture searched on a graph should perform well on the same graph, i.e., the elements on the main diagonal in the tables should be the maximum elements of theirs columns. However, we find that when evaluating on a certain setting, architecture searched from another setting can perform well, even better than the architecture searched at the same setting. E.g., the best architecture evaluated on the graph with δ = 5 is searched from the graph with δ = 4. This phenomenon can answer (ii). DARTS may not be able to accurately select the optimal architecture with the original graph.
We can also give our explanation here. Although DARTS can judge the usefulness of different information, they cannot get an accurate answer, e.g., when δ = 6, graph structure contains useful classification information. However, DARTS may have overconfidence in it and make radical decisions, aggregating too much message from the neighborhood which includes noises and cause over-fitting. Less graph structure information (δ = 4, 5) lets DARTS become more conservative about aggregation. Architectures searched at these settings perform better when evaluating at δ = 6 setting. Similarly, DARTS may misjudge the information’s usefulness in other settings.
Based on the above exploration, we have found that DARTS cannot design the optimal architecture due to certain noise in the original graph. Message passing scheme used in GNNs smooths node
features, which can also be seen as a denoising process. Therefore, denoising graph structure is what we should consider more. Combining architecture search and structure learning becomes a natural way. In the next section, we will introduce our method which jointly optimizes neural architecture and graph structure.

heading: 4 Joint optimization of graph architecture and structure

heading: 4.1 Differentiable Graph Structure

text:
In most real graph datasets, the graph structure is discrete, i.e., the edges given in the graph are unweighted. Although these edges contain crucial information, certain noise is brought into the data as well. Take citation dataset for example, a paper cites other papers for many different reasons. Some citations are helpful for paper classification, such as citing related works and baselines. Others may have less use, such as citing a mathematical method. However, the graph treats all these different types of citation equally. The classification model may be confused by those unhelpful edges. This phenomenon can be also found in other types of graphs. In addition, the discrete space of graph structure makes it difficult to optimize the structure. Thus, it is necessary to differentiate the edges in the graph.
We apply differentiable graph structure here. We use a parameter to represent the weight of each edge. To restrict the weight is in (0, 1) during message passing, we use a sigmoid function to the parameter. Thus, the parameter matrix used in message passing can be represented as Gp = normalize(sigmoid(G)), where G is the parameter. The normalize function includes adding self-loops, i.e, we can only change the weight of normal edges, the weight of self-loops is fixed. In the message passing procedure, edge weights are used as multipliers before aggregation.
We benefit from the differentiable graph structure in two ways. One is we can distinguish the helpfulness of edges, and aggregate more useful information during message passing. The other one is we can use gradient based methods to optimize the structure. We should note this differentiable graph structure fits most of GNNs by just replacing the adjacent matrix with the parameter matrix Gp.

heading: 4.2 Learning by Hidden Feature Smoothness Constraint

text:
An important assumption in graph is the first-order proximity. It is proved in [21, 22] that more links between intra-group nodes and fewer links between inter-group nodes improve the node classification accuracy. However, we cannot get all node labels in the training phase. We use hidden feature H to approximate the node labels, which is the matrix indicating the probability of which type the nodes belong to. It is proper to use H to represent the node label. To minimize the connections between inter-group nodes, we can use the hidden feature smoothness as a regularizer. In condition that the model has learnt some knowledge, the model will give good predictions about node labels. Thus, the edge weights whose connected nodes have similar hidden features are larger than those have different hidden features. By updating the structure, similar node features are aggregated more in later GNN procedure, improving the denoising ability of the algorithm. However, if we only adopt this loss to optimize the structure. All edge weight will be reduced to 0 at convergence. Thus we combine the smoothness loss with a distance loss, which can be formulated as:
Ls = λ N∑ i,j Gij ‖ hi − hj ‖2 + N∑ i,j (Gij −Go,ij)2, (2)
where Gij is the weight parameter of the edge between node i and j, Go,ij is the elements in the initialization ofG, we initial all edge weights as 0.5, λ is a hyper-parameter to control the contribution of the hidden feature smoothness. Hence, the weight of edges between inter-group nodes is reduced. This loss guarantees the first-order proximity to a certain degree. In addition, this loss restricts G not to change too much from the original graph. To save calculation resources, we only learn the weight of edges existing in the original graph in this procedure. The weight of other edges is always kept as 0. Therefore, the memory and time complexity of our methods is O(|E|). Besides, since G also takes part in the calculation of Ls, we detach H from the computational graph while calculating the gradient of Ls to G in order to prevent a complex back-propagation.

heading: 4.3 Training Procedure

text:
We formulate the joint optimization problem as follows: min A Lval(W ∗,A, G∗)
s.t. G∗ = argminGLs(W ∗,A, G), W ∗ = argminWEA∈Γ(A)Ltrain(W,A, G).
(3)
In this problem, there are three parameters W,A, G needing optimized. It is hard to optimize all of them at the same time. Thus we apply gradient descent methods to these parameters in turns. In the training procedure, we set the first several epochs as warming up, when only W is updated. Since at the very beginning of training, W is unstable and may lead to incorrect hidden features. Using those hidden features to update the other two parameters aggravates the model’s unstableness.
Different from DARTS for image tasks where a small proxy model is usually used in the searching phase due to the memory limitation, and a larger network is retrained in the evaluation phase. Here, the number of layers in the super network is the same as a complete GNN. We can directly use the super network to do the evaluation. Interestingly, we find that the super network performs well in node classification tasks, even better than retraining the designed architecture at most times. This phenomenon may be due to the regularization caused by weight sharing, which is one type of ensemble model [39]. Other ensemble models such as dropout [40] and multiple heads [41] have proved their success in deep neural networks. All these models can be regarded as an ensemble of different submodels, which learn different parts of knowledge from the data and provide different perspectives of it. These submodels restrict each other during the training phase, which is de facto a type of regularization, helping reduce over-fitting and improve performance.

heading: 5 Experiments

heading: 5.1 Performance Evaluation

text:
† To be fairly compared, we expand the channels of these model to make the number of model parameters comparable with GASSO. ‡We rerun GraphNAS because their code leaks test set of data.
20 40 60 80 100 epoch
0.825
0.850
0.875
0.900
0.925
0.950
0.975
1.000
ra ti
o
20 40 60 80 100 epoch
0.800
0.825
0.850
0.875
0.900
0.925
0.950
0.975
1.000
ra ti
o
Figure 3: Weight ratio of noisy edges to orignical edges. Top: Cora. Bottom: Citeseer.
Since structure learning is directly performed on the original graph, we focus on transductive node classification task. We evaluate our model on three widely used citation benchmark datasets, Cora, Citeseer, and Pubmed, where nodes denote papers and edges denote citation relationship. We apply
the full-supervised training fashion used in [42–44]. Hyper-parameter settings are listed in Appendix B.2. We use GCN [1], GAT [2], ARMA [45], DropEdge [42], DARTS [8], GDAS [46], ASAP [47], XNAS [48] and GraphNAS [5] as our baselines, and the hyper-parameter of them are following the original implementation. For our GASSO model, we set the number of layers as 2 in Cora and CiteSeer, 4 in PubMed. The candidate operations contain GCN [1], GAT [2], GIN [3], MRConv [37] and linear. In the super network, we adopt dropout (p=0.8) before each layer and a ReLU function after each layer. We summarize node classification accuracy in Table 2. All results in the table are averaged over 10 runs with random parameter initialization, and the standard deviations are also provided in the table.
We can find that our model GASSO outperforms all baselines on all three benchmark datasets. The results show that our proposed model has the power to effectively utilize information in the original graph, giving better node label predictions.
We conduct further experiments on three larger graph benchmarks: Physics, CoraFull and ogbnarxiv. For Physics and CoraFull, we randomly split train/valid/test set as 50:25:25. For ogbn-arxiv, we follow the default setting. We narrow down the op-
eration search space to GCN, GAT and linear because of the memory limit. The results shown in Table 3 indicating that our model still performs well in larger graphs.

heading: 5.2 Ablation Study

text:
In our scheme, the most two important parts are neural architecture search and graph structure learning. To further evaluate the contribution of these two components and their cooperation, we conduct an ablation study on them. We design several variant models, which can be divided into three parts. 1) We change the graph structure learning model in the first part of variants. For GASSO-V1, we remove the structure learning part, i.e., the model becomes pure DARTS with our initial G. For GASSO-V2, we replace hidden feature smoothness with original feature smoothness, which is used in [20]. For GASSO-V3: we replace hidden feature smoothness with one-hot predicted label smoothness, which is similar with [21]. For GASSO-V4: we directly calculate edge weight based on similarities between nodes. 2) In the second part, we change the neural architecture search method. For GASSO-V5, we do not update the neural architecture, but the super network is still kept, i.e., all candidate operations have equal weights from the beginning to the end. For GASSO-V6, we fix GCN as the architecture. For GASSO-V7, we fix GAT as the architecture. 3) In the third part, we change the optimization scheme. The aim of setting this part of variants is to prove the cooperation of graph structure learning and neural architecture search. For GASSO-V8: we split the training of neural architecture and graph structure. In the first half of epochs, we only train the graph structure. In the second half, we only train the neural architecture. To be fair, the number of training epochs is doubled, and the warming up procedure is still kept. For GASSO-V9: the same as GASSO-V8, but the order of training neural architecture and graph structure is exchanged.
We examine all these variant on the same datasets, the results are also presented in Table 2. Overall, our model outperforms all of the variants in all three datasets, showing training of both graph architecture and neural architecture contributes to our model.
For part 1), we find that GASSO-V1 also achieves comparable performance with GCN and GAT, showing the great power of ensemble in the super network. But the margin below GASSO proves that graph structure learning is necessary. Interestingly, the performance of GASSO-V2 is not even good as GASSO-V1. It is possible that using original feature smoothness to constrain edges causes more severe over-fitting. The performance of GASSO-V3 indicates that one-hot predicted label smoothness is of some usefulness. But neither the original feature nor the one-hot predicted label is better than hidden feature for graph structure learning. GASSO-V4 is a radical method, which makes the edge weights different at the early stage of training. For part 2), we observe that the performance has an obvious drop in GASSO-V5, demonstrating that the neural architecture training is of significant importance. GASSO-V6 and GASSO-V7 behave differently in three datasets compared with GCN and GAT, showing these datasets have different properties. For part 3), we dicover that GASSO-V8 can be regarded as GASSO-V4 followed by neural architecture search, and GASSO-V9
can be regarded as GASSO-V1 followed by graph structure learning. The margin of GASSO-V8 over GASSO-V4 and margin of GASSO-V9 over GASSO-V1 prove that adding neural architecture search behind graph structure learning can achieve better performances, while adding graph structure learning behind neural architecture search causes unstable influence. Nevertheless, neither GASSOV8 nor GASSO-V9 outperforms GASSO, demonstrating that the cooperation training in our scheme play a key role in optimizing the model.

heading: 5.3 Denoising Analysis

text: Here we examine the denoising ability of our model. We select the experiment setting following [15, 16, 20], where only the largest connected component is considered, and the split of training/validation/testing set is 10%/10%/80%. We manually include random edges in the three datasets with different perturbation rates, from 0% to 100% with a step of 20%. We compare our methods with baselines GCN, GAT and DARTS. The results are shown in Figure 4. We observe that DARTS has an unstable denoising ability. It performs very well on PubMed, the accuracy almost keeps as it on the original graph even when there is 100% perturbation rate of edges. However, it performs badly in the other two cases, even worse than GCN. Our proposed methods consistently outperform the three baselines in all three datasets. Comparing our proposed GASSO with GCN and GAT, the performance gain gets larger when more noise is added to the graph in all cases. Moreover, GASSO leads a margin of around 6% in CiteSeer and 4% in Cora upon DARTS at 100% perturbation rate setting. To better demonstrate the effectiveness of our denoising process, we show the weight ratio of noisy edges to original edges in Figure 3. We choose the case of 100% perturbation rate in Cora and CiteSeer. We use 20 epochs to warm up. Then the weight ratio begins to decrease. It tends to be stable at around 82.5% in both cases, indicating we can exclude 17.5% of noise effect. All the above results show that GASSO has a great power to reduce noise disturbing NAS methods.

heading: 6 Conclusion

text:
In this paper, we study how graph architecture search can select desired architectures by conducting measurement study and proposing a Graph Differentianle Architecture Search model with Structure Optimization (GASSO). We find that gradient based graph architecture search can select proper operations according to the usefulness of information inside the graph, and may suffer from noises in graph features and structures. Based on our findings, we proposed our GASSO model, which jointly optimizes graph architecture and structure. Extensive experiments on real graph benchmark datasets demonstrate that the joint optimization of neural architecture and graph structure not only benefits in graph learning but also enhances the denoising ability.
Acknowledgments and Disclosure of Funding
This work is supported by the National Key Research and Development Program of China No. 2020AAA0106300 and National Natural Science Foundation of China (No. 62050110, No. 62102222).

title: Graph Differentiable Architecture Search with Structure Learning