L. Xia v. Rex Tillerson

*646 PILLARD, Circuit Judge: The plaintiffs, five former Chinese nationals, received certificates of United States naturalization, on the basis of which they obtained United States passports. In 2006, government investigators discovered that Robert Schofield, an employee of the United States Customs and Immigration Services (USCIS), had illegally issued nearly 200 certificates of naturalization to individuals—mostly Chinese nationals— who, the government contends, had not satisfied the requirements to become U.S. citizens. After USCIS learned of Scho-field’s illegal activities, it administratively canceled plaintiffs’ certificates of naturalization without seeking a court order, and the State Department administratively revoked or refused to renew their passports. The plaintiffs sued, claiming that the administrative processes by which the United States canceled their certificates of naturalization and revoked their passports violated their rights to constitutionally and statutorily adequate process and to be free from discrimination based on their Chinese ethnicity. The government moved to dismiss the case for lack of subject matter jurisdiction on the ground that the United States had not waived sovereign immunity. The district court rejected that ground but, after giving plaintiffs an opportunity to amend their complaint, dismissed the amended complaint for failure to state a claim on which relief can be granted. Plaintiffs appealed. We affirm the dismissal of plaintiffs’ claims that the government’s revocations of their certificates of naturalization and their passports violated the Immigration and Nationality Act and due process because they took place through administrative rather than judicial process. We also affirm the dismissal of their claims of ethnicity or national origin discrimination. Because the government denied plaintiffs the administrative review of their passport revocations or non-renewals that the INA and agency rules require, however, we reverse insofar as the district court held that any plaintiff is barred by failure to exhaust administrative remedies from (a) challenging under the APA the government’s failure to afford plaintiffs the review the law requires, and (b) pursuing 8 U.S.C. § 1503 claims in the correct venues. We therefore remand plaintiffs’ APA and section 1503 claims to the district court with a suggestion that the court consider transferring the APA claims together with the section 1503 claims to the venues required for consideration of the latter. I. Background A. Factual Allegations On review of a dismissal for failure to state a claim, our description of events relies on plaintiffs’ allegations, which we provisionally accept as true. Aware that discovery and proffers of proof might well alter our understanding of the facts, we allow untested allegations of the complaint to set the factual stage for now. The government has yet to file an answer to the complaint, and the parties have neither conducted discovery nor presented or tested evidence as they would on summary judgment motions or at trial. But under the Federal Rules of Civil Procedure, if plaintiffs lack legally valid claims even on the facts as they allege them, we need go no further. See Fed. R. Civ. P. 12(b)(6); see also Ashcroft v. Iqbal, 556 U.S. 662, 678-79, 129 S.Ct. 1937, 173 L.Ed.2d 868 (2009). Because the district court denied plaintiffs leave to amend based on the legal inadequacy of the amended complaint, we draw the following facts from that document. The plaintiffs in this litigation—Lihong Xia, Wei Liu, Hoi Lun Li, Jinsong Chen, and Hua Chen—were Chinese citizens before they obtained their certificates of nat *647 uralization and United States passports. According to plaintiffs, China’s Nationality-Law provides that any “Chinese national who has settled abroad and who has been naturali[z]ed as a foreign national ... shall automatically lose Chinese nationality.” App’x 202. When Chinese authorities discovered that plaintiffs had become U.S. citizens, the Chinese government responded by rescinding their Chinese citizenship. After USCIS officer Robert Schofield pleaded guilty to bribery and the unlawful procurement of citizenship or naturalization, 1 the United States government revoked each plaintiffs certificate of naturalization and either revoked or denied renewal of their passports. Plaintiffs allege that they satisfied the requirements for naturalization and therefore are U.S. citizens. Neither the complaint nor any public record the parties have identified or provided explains precisely whether or how these plaintiffs’ facially valid certificates of naturalization and passports were affected by Schofield’s activities. No information before the court at this stage shows that plaintiffs were aware of inadequacies or fraud in the procurement of their naturalization certificates or passports. That said, the' details of plaintiffs’ situations are not entirely clear. The allegations focus primarily on the experience of plaintiff Lihong Xia. The complaint alleges that Xia was naturalized and obtained her United States passport in 2004. She resided in the United States as a citizen, and traveled back and forth without incident between the United States and China, where her parents lived, until October 2009, when an officer from U.S. Immigration and Customs Enforcement (ICE) stopped Xia at the airport as she returned to the United States. After questioning her, the officer deemed Xia an “arriving alien” and seized her passport. Am. Compl. ¶ 15. The government initiated a removal proceeding, but the immigration court dismissed the proceeding because the Department of Homeland Security (DHS) failed to prosecute. Xia repeatedly contacted DHS to demand the return of her passport, to no avail. A year and a half later, in 2011, USCIS sent Xia a notice of its intent to cancel her certificate of naturalization, asserting that Xia was among the nearly 200 individuals who received naturalization certificates from Schofield. The notice gave Xia sixty days to refute USCIS’s decision in writing or request a hearing. Xia opposed cancellation and requested a hearing within the time limit. While the proceeding before USCIS was pending, the State Department notified Xia that it had revoked her passport based on USCIS’s cancellation of her certificate of naturalization. Contrary to the State Department’s explanation, however, USCIS had not yet issued any decision canceling Xia’s certificate of naturalization and would not do so for another year. Once USCIS notified Xia that it had canceled the certificate, she appealed to USCIS’s Administrative Appeals Office and appeared for a hearing. She once again denied USCIS’s charge that her naturalization certificate was not adequately supported. By that time, USCIS asserted that it was her parents who were on the list of people affected by Schofield’s misconduct. Xia strenuously disputed that her parents could have had any contact with Schofield because they had never set foot in the United States. Her position was that *648 any irregularity on Schofield’s part had not been shown to undermine her naturalization, and argued that USCIS’s administrative procedure for revoking certificates of naturalization did not satisfy the Due Process Clause of the Fifth Amendment. USCIS dismissed the appeal, without addressing Xia’s due process arguments because they were “outside the jurisdiction of th[e] office.” App’x 154. The complaint contains sparse but similar allegations about Wei Liu. He allegedly was naturalized around 2001 and traveled abroad freely as a U.S. citizen. While on a trip to China in December 2007, however, he attempted to renew his U.S. passport. The State Department denied his application and confiscated his passport. USCIS sent Liu a notice of its intent to cancel his certificate of naturalization and provided him with an administrative hearing at the U.S. Embassy in Beijing. After the hearing, USCIS canceled Liu’s certificate of naturalization. USCIS notified Liu of his opportunity to appeal its decision administratively, but the complaint does not say whether Liu pursued an appeal. There is less we can glean about the remaining plaintiffs from their sparse and unclear allegations. Plaintiffs claim without elaboration that • ICE agents confiscated Hoi Lun Li’s passport at the Los Angeles International Airport, and USCIS later canceled her certificate of naturalization “without due process proceedings,” Am. Compl. ¶ 62; • The State Department denied Jinsong Chen’s passport renewal application while he was in Shanghai; and • Hua Chen’s passport and certificate of naturalization were administratively cancelled. In addition to making various statutory and constitutional claims that the government failed to follow the requisite processes to revoke their passports and certificates of naturalization, plaintiffs contend that the government targeted them for that unfair treatment based on their Chinese ethnicity. In support of the discrimination claims, plaintiffs attached to their complaint a list of individuals, who they contend were not Asian, who, they say, “received full evidentiary hearings” before being denaturalized. App’x 161-82 (list of former U.S. citizens who have been dena-turalized). B. District Court Proceedings Plaintiffs sued the Secretary of State and Secretary of Homeland Security in their official and individual capacities. As relevant to this appeal, plaintiffs sought declaratory and injunctive relief under (1) the Due Process Clause of the Fifth Amendment to the Constitution; (2) the Immigration and Nationality Act (INA), 8 U.S.C. §§ 1421, 1451(a); (3) the Administrative Procedure Act (APA), 5 U.S.C. § 701 et seq.-, and (4) two provisions of the Civil Rights Acts, sections 1981 and 1983 of Title 42 of the U.S. Code. Defendants moved to dismiss the case for lack of subject matter jurisdiction under Rule 12(b)(1) of the Federal Rules of Civil Procedure. They principally argued that the government had not waived sovereign immunity for this type of suit. See Defs.’ Mot. to Dismiss, Xia v. Kerry, 14-cv-57 (June 13, 2014). The district court rejected that argument, Xia v. Kerry (Xia I), 73 F.Supp.3d 33, 39 (D.D.C. 2014), but sua sponte dismissed the complaint without prejudice under Rule 12(b)(6) for failure to state a claim, id. at 39-46. The court held that plaintiffs failed to state a due process claim because it was “impossible to discern the procedures to which plaintiffs believe they were entitled but deprived.” Id. at 42. The court dis *649 missed plaintiffs’ civil rights claims under sections 1981 and 1983 for want of allegations that the government acted under col- or of state (as opposed to federal) law. Id. at 43-44. Plaintiffs’ INA claims likewise failed, the court said, because none of the INA provisions plaintiffs cited applied to the government’s alleged conduct. Id. at 44. As for plaintiffs’ APA claim, the court concluded that the complaint identified nothing arbitrary in the government’s actions. Id. at 44-45. Alternatively, the court held, section 1503 of Title 8 of the U.S. Code provides an adequate alternative judicial remedy for plaintiffs, thus barring any APA claim. Id. at 45. Section 1503 would allow plaintiffs to sue in federal court for a declaration of their United States citizenship. Id at 46. The district court cautioned, however, that section 1503 requires plaintiffs to first exhaust their administrative remedies, which it held that only Xia had done. Id. at 45-46. The court therefore dismissed the complaint without prejudice. Id. at 46. Plaintiffs moved for leave to amend their complaint to address the shortfalls the district court identified. Their proffered amended complaint added claims under 8 U.S.C. §§ 1447(b) and 1503 seeking declarations that they are U.S. citizens and so entitled the restoration of their naturalization certificates and passports. Plaintiffs also included new allegations that they were entitled to “full, fair and meaningful De-Naturalization proceedings.” Am. Compl. ¶ 5. Despite those changes, the district court denied leave to amend the complaint, concluding that the proffered amended complaint “failed to cure inadequacies present in their previous complaint that led th[e] Court to dismiss their claims.” Xia v. Kerry (Xia II), 145 F.Supp.3d 68, 74 (D.D.C. 2015). The court held that it could not decide the new section 1503 claims because Xia alleges she resides in New Jersey, making the federal court there, not here, the proper venue under section 1503, and because, in its view, no other plaintiff alleged the requisite exhaustion of administrative remedies that it saw as a prerequisite to a section 1503 claim. Id at 73-74. II. Analysis The district court dismissed plaintiffs’ case in its entirety and denied as futile their motion for leave to amend. We affirm the dismissal of plaintiffs’ claims that the government violated the INA and due process by revoking their certificates of naturalization and their passports through administrative rather than judicial process. We also affirm the dismissal of plaintiffs’ claims of discrimination, and the determination that the District of Columbia is the wrong venue for their claims under 8 U.S.C. § 1503. However, we reverse the district court’s determination that plaintiffs are barred due to a failure to exhaust their administrative remedies from pursuing (a) APA claims challenging the government’s failure to afford them proper administrative review, and (b) section 1503 claims in the correct venue. We ordinarily review the denial of a motion for leave to amend for abuse of discretion, but where, as here, a district court denies leave to amend because the amended complaint would not survive a motion to dismiss, our review is de novo. In re Interbank Funding Corp. Secs. Litig., 629 F.3d 213, 218 (D.C. Cir. 2010). As on review of a dismissal under Rule 12(b)(6), “we treat the complaint’s factual allegations as true and must grant the plaintiffis] the benefit of all inferences that can be derived from the facts alleged.” Abdelfattah v. U.S. Dep’t of Homeland Sec., 787 F.3d 524, 529 (D.C. Cir. 2015) (alteration omitted). “To survive a motion to dismiss, a complaint must contain suffi *650 cient factual matter, accepted as true, to ‘state a claim to relief that is plausible on its face.’ ” Iqbal, 556 U.S. at 678, 129 S.Ct. 1937 (quoting Bell Atl. Corp. v. Twombly, 550 U.S. 544, 570, 127 S.Ct. 1955, 167 L.Ed.2d 929 (2007)). “Threadbare recitals of the elements of a cause of action, supported by mere conclusory statements, do not suffice.” Id. A. Claims of Inadequate Procedure Under the INA and Due Process Clause We begin with the most troubling aspect of plaintiffs’ case: Their claims that their citizenship was revoked without the process required by the Constitution and federal law. Plaintiffs allege that they were “strippfed] of U.S. citizenship” without “any kind of due process,” ie. the judicial process the INA requires to effectuate de-naturalization. Appellants Br. 13. 1. Citizenship is among the most momentous elements of an individual’s legal status. “It would be difficult to exaggerate its value and importance.” Schneiderman v. United States, 320 U.S. 118, 122, 63 S.Ct. 1333, 87 L.Ed. 1796 (1943). Many invaluable benefits flow from United States citizenship, including rights to vote in federal elections, to travel internationally with a U.S. passport, to convey citizenship to one’s own children even if they are born abroad, to be eligible for citizen-only federal jobs, and, indeed, to be free of discrimination by Congress on the basis of alienage. Before an individual may obtain U.S. citizenship through naturalization, “there must be strict compliance with all the congressionally imposed prerequisites to the acquisition of citizenship.” Fedorenko v. United States, 449 U.S. 490, 506, 101 S.Ct. 737, 66 L.Ed.2d 686 (1981). The possessor of a facially valid naturalization certificate is presumptively a citizen. “Congress has vested sole naturalization authority in the Attorney General, 8 U.S.C. § 1421(a), and a certificate of naturalization represents conclusive evidence of the Attorney General’s determination.” United States v. Straker, 800 F.3d 570, 586 (D.C. Cir. 2015), cert. denied, — U.S. —, 136 S.Ct. 1170, 194 L.Ed.2d 191 (2016) (citing Tutun v. United States, 270 U.S. 568, 577, 46 S.Ct. 425, 70 L.Ed. 738 (1926); 8 U.S.C. § 1443(e)). Citizenship is constitutionally protected by due process from unintentional relinquishment. Afroyim v. Rusk, 387 U.S. 253, 268, 87 S.Ct. 1660, 18 L.Ed.2d 757 (1967). “[0]nce citizenship has been acquired, its loss can have severe and unsettling consequences.” Fedorenko, 449 U.S. at 505, 101 S.Ct. 737. Denaturalization “may result in the loss of both property and life; or of all that makes life worth living.” United States v. Minker, 350 U.S. 179, 187, 76 S.Ct. 281, 100 L.Ed. 185 (1956). Reflecting the gravity of that step, revocation or -cancellation of citizenship may only be accomplished by a federal judicial order. See United States v. Zucca, 351 U.S. 91, 95 & n.8, 76 S.Ct. 671, 100 L.Ed. 964 (1956); Bindczyck v. Finucane, 342 U.S. 76, 79, 72 S.Ct. 130, 96 L.Ed. 100 (1951); Schneiderman, 320 U.S. at 122-23, 63 S.Ct. 1333; Gorbach v. Reno, 219 F.3d 1087, 1092-98 (9th Cir. 2000) (en banc). In other words, although citizenship may be administratively bestowed, it can only be revoked by a federal court. If the government concludes that a naturalized citizen is not legally entitled to citizenship, it may seek to effect denaturalization either through federal criminal prosecution or a civil action in federal court. If an individual knowingly procures naturalization or a certificate or evidence of citizenship to which the puta *651 tive citizen is not entitled, the government may criminally prosecute her under 18 U.S.C. § 1425. Once a person is convicted under section 1425, the federal court in which the conviction occurred shall on that ground revoke the defendant’s citizenship. See 8 U.S.C. § 1451(e); see Maslenjak v. United States, 582 U.S. -, 137 S.Ct. 1918, 1920, 198 L.Ed.2d 460 (2017). If proof of the requisite mens rea is lacking or some other factor counsels against criminal prosecution, the government alternatively may denaturalize a person by obtaining a civil denaturalization order in federal court pursuant to 8 U.S.C. § 1451. “The exclusive [noncriminal] process for challenging the validity of the grant of a naturalization petition is through a revocation of naturalization proceeding pursuant to 8 U.S.C. § 1451.” United States v. Clarke, 628 F.Supp.2d 15, 23 (D.D.C. 2009), aff'd sub nom. United States v. Straker, 800 F.3d 570. Whenever any person procures a naturalization order or certificate illegally, or by concealment of a material fact or willful misrepresentation, section 1451 authorizes the government to sue “for the purpose of revoking and setting aside the order admitting such person to citizenship and cancelling the certificate of naturalization.” 8 U.S.C. § 1451(a); see Zucca, 351 U.S. at 91, 76 S.Ct. 671; Bindczyck, 342 U.S. at 83, 72 S.Ct. 130. In that proceeding, the govern ment “carries a heavy burden of proof.” Costello v. United States, 365 U.S. 265, 269, 81 S.Ct. 534, 5 L.Ed.2d 551 (1961). “[I]n view of the grave consequences to the citizen, naturalization decrees are not lightly to be set aside—the evidence must indeed be ‘clear, unequivocal, and convincing’ and not leave ‘the issue in doubt.’ ” Id. (quoting Schneiderman, 320 U.S. at 125, 158, 63 S.Ct. 1333; Baumgartner v. United States, 322 U.S. 665, 670, 64 S.Ct. 1240, 88 L.Ed. 1525 (1944)) (alteration omitted); see Nowak v. United States, 356 U.S. 660, 663, 78 S.Ct. 963, 2 L.Ed.2d 1048 (1958). Here, however, the government has not gone to court to seek denaturalization of any of the plaintiffs in this case; it has administratively canceled their certificates of naturalization and revoked their passports. The Attorney General has statutory authority, without a court order, to “cancel any certificate of citizenship” where it appears “to the Attorney General’s satisfaction” that the document was illegally or fraudulently obtained. 8 U.S.C. § 1453. The Department of Homeland Security has promulgated regulations governing that process. 8 C.F.R. §§ 342.1-342.9. The regulations require the government to provide written notice of its intent to cancel a certificate of naturalization. 8 C.F.R. § 342.1. The certificate holder, who may be represented by counsel, can then dispute the cancellation either in writing or in person. 8 C.F.R. § 342.1. If the government decides to cancel the certificate of naturalization, it must inform the affected individual of the right to appeal to the USCIS Administrative Appeals Office. See 8 C.F.R. § 342.8. The statute makes clear, however, that administrative cancellation of a certificate of naturalization “shall affect only the document and not the citizenship status of the person in whose name the document was issued.” 8 U.S.C. § 1453. Similarly, if the State Department discovers that a passport was “illegally, fraudulently, or erroneously obtained,” the Secretary of State is authorized to cancel it. 8 U.S.C. § 1504(a). Generally, the passport holder “shall be given, at such person’s last known address, written notice of the cancellation of such document, together with the procedures for seeking a prompt post-cancellation hearing.” Id. But administrative cancellation of a citizen’s passport, like administrative cancellation *652 of a certificate of naturalization, shall “affect only the document and not the citizenship status of the person in whose name the document was issued.” Id. Even though administrative cancellation of a certificate of naturalization or passport cannot affect an individual’s citizenship, those actions nevertheless have consequences. Without proof of one’s citizenship, for example, a person will be unable to travel abroad, or to establish entitlement to the many other rights and privileges of citizenship. Subject to exceptions relating to removal proceedings not relevant here, anyone in the United States who “claims a right or privilege as a national of the United States and is denied such right or privilege by any department or independent agency, or official thereof, upon the ground that he is not a national of the United States” has a statutory right to claim the benefits of citizenship in a declaratory judgment action under 8 U.S.C: § 1508(a). Section 1503 empowers “the district court of the United States for the district in which such person resides or claims a residence” to enter “a judgment declaring [her] to be a national of the United States.” 8 U.S.C. § 1508(a). The plaintiff “need make only a prima facie case establishing [her] citizenship by birth or naturalization.” Perez v. Brownell, 356 U.S. 44, 47 n.2, 78 S.Ct. 568, 2 L.Ed.2d 603 (1958), overruled on other grounds by Afroyim, 387 U.S. 253, 87 S.Ct. 1660. The government must then respond with “clear, unequivocal, and convincing” evidence rebutting the plaintiffs showing of citizenship. Id. 2. Plaintiffs contend that the government violated their right to statutorily and constitutionally adequate process by failing to provide them “full, fair and meaningful De-Naturalization proceedings.” Am. Compl. ¶ 5. The district court faulted plaintiffs for failing to identify the process they claim they are due. Although admittedly far from crystalline, we find it clear enough that plaintiffs claim entitlement to pre-deprivation process in the form of an action by the Attorney General in federal court, in which the government bears the burden of proof, as contemplated by 8 U.S.C. § 1451. See Am. Compl. ¶ 30 (“[A]ll plaintiffs are U.S. citizens whose citizenship can only be taken away through de-naturalization proceedings by the U.S. Judiciary Branch and none [has] been offered such ... process ... yet.”) (emphasis omitted); see also Fedorenko, 449 U.S. at 505, 101 S.Ct. 737 (citing Costello, 365 U.S. at 269, 81 S.Ct. 534). Plaintiffs’ due process claim thus dovetails with their claims under the INA. They argue that the Constitution required the government formally to denaturalize them under one provision of the INA (section 1451) rather than rest on administrative action under other INA provisions (sections 1453 an4 1504). Plaintiffs challenge the validity of the administrative cancellations as, in effect, an unauthorized and unconstitutional workaround of the requisite denaturalization process, accomplished by treating the revocation of plaintiffs’ certificates of citizenship and passports as having confirmed plaintiffs’ lack of U.S. citizenship without the requisite court order. Am. Compl. ¶ 27. Plaintiffs are now, as they put it, in “a gray limbo,” unable to travel abroad or, in the cases of Wei Liu or Jinsong Chen, to return to the United States, and lacking any proof of United States citizenship that would allow them to enjoy its benefits. Id. At the same time, viewed by China as having been naturalized here, plaintiffs are unable to live in or travel to and from China as citizens of the nation of their birth. *653 The government appears to have two responses to plaintiffs’ challenge: First, the government argues that, because plaintiffs received their certificates of naturalization through an illegal and inadequate process tainted by the criminal conduct of USCIS officer Robert Schofield, plaintiffs simply never became citizens. A person who is a non-citizen is not entitled to either a certificate of naturalization or a passport. Once the authorized administrative processes took away those unlawfully conferred documents, the government reasons, the problem was fixed and no more process was due. See Oral Arg. Audio 19:41-20:27, 24:20-25:27. Second, even assuming plaintiffs must be treated as if they were validly naturalized until proven otherwise, and acknowledging that judicial process under 8 U.S.C. § 1451 or 18 U.S.C. § 1425 is required for denaturalization, the government’s revocation of plaintiffs’ documents did not dena-turalize them. Because the administrative actions plaintiffs challenged were incapable of vitiating citizenship, those actions did not have to conform to denaturalization’s pre-deprivation judicial process. See Oral Arg. Audio 31:06-31:43, 32:14-32:32; see also Schneiderman, 320 U.S. at 122-23, 63 S.Ct. 1333. a. The first of these arguments is fatally circular. When pressed at oral argument as to why it did not seek orders in federal court under section 1451 to declare plaintiffs denaturalized, the government asserted that it need not do so because plaintiffs were never United States citizens to begin with. In their view, plaintiffs did not receive valid certificates of naturalization, so there is no citizenship for a court to revoke in an action under section 1451. But that argument assumes what the government must prove. We cannot begin our analysis where the government does for two reasons. First, we are reviewing the denial of leave to amend the complaint for failure to state a claim, and so must provisionally credit plaintiffs’ allegations. See Interbank, 629 F.3d at 218. Plaintiffs allege that they met the naturalization requirements, and that their applications and eligibility were not undermined by USCIS official Schofield’s fraudulent scheme. It is not clear why plaintiffs’ naturalizations would be invalid if, for example, they were not in fact among those Schofield illegally dealt with, or were extorted by Schofield and his illegal brokers in the process of obtaining naturalization for which they were nonetheless fully eligible. The government has not disputed that plaintiffs previously had facially valid certificates of naturalization and passports; it has not in this litigation yet had the chance to prove that plaintiffs did not qualify as citizens. At this stage, we must assume, as plaintiffs allege, that their certificates and passports evidenced U.S. citizenship. The government’s first rebuttal to plaintiffs’ procedural claims is inadequate for another, more fundamental reason. The government’s own administrative decision—even if well supported and ultimately vindicated—cannot relieve it of its burden to prove to a court by clear and convincing evidence that plaintiffs’ apparent naturalization is invalid. Indeed, section 1451, providing for judicial action to revoke naturalization, explicitly speaks to cases in which naturalizations “were illegally procured or were procured by concealment of a material fact or by willful misrepresentation.” 8 U.S.C. § 1451(a). The government’s theory would appear to allow it to circumvent in every such case its burden to obtain a judicial denatural-ization order, based on the theory that the naturalization was never valid to be *654 gin with. The denaturalization statute itself seems to foreclose that approach. The very cases that establish the principle that denaturalization requires a court order, obtained upon the government’s clear and convincing proof, likewise rebut the government’s position here. In those cases, as here, the government contended that naturalization was defective from the start. The entire denaturalization question in Schneiderman, for example, was whether Mr. Schneiderman’s certificate of naturalization was lawfully cancelled twelve years after it was granted because he had fraudulently procured it in the first place. 320 U.S. at 120-22, 63 S.Ct. 1333. The government argued that Schneiderman had never validly qualified as someone “attached to the principles of the Constitution of the United States” because he concealed his Communist affiliation in his application. Id. at 121, 63 S.Ct. 1333. The Court did not treat Schneiderman as a non-citizen simply because the government was convinced that he fraudulently obtained his U.S. citizenship, but instead required the government to persuade the Court with “the clearest sort of justification and proof.” Id. at 122, 63 S.Ct. 1333. In Baumgartner v. United States, too, the government sued for denaturalization of a man whom, it asserted, falsely claimed in the naturalization process his allegiance to the Constitution and laws of the United States while in fact remaining loyal to the German Reich. 322 U.S. at 666, 64 S.Ct. 1240. The Court emphasized “the importance of ‘clear, unequivocal, and convincing’ proof on which to rest the cancellation of a certificate of naturalization” and placed that “weighty proof’ burden on the government notwithstanding the government’s claim that the certificate of naturalization was never valid because fraudulently procured ab initio. Id. at 671, 675, 64 S.Ct. 1240. So, too, the petitioner in Costelb v. United States, was ostensibly naturalized 27 years before the government sought to divest him of his citizenship. 365 U.S. at 268, 81 S.Ct. 534. The Court noted that the record left no doubt that, at the time of his application, petitioner Costello willfully misrepresented his occupation as “real estate” and concealed that he was in fact an illegal bootlegger. Id. at 272, 81 S.Ct. 534. Before it treated Mr. Costello as a nonciti-zen, however, the government was required to file a federal denaturalization complaint under section 1451 and shoulder its “heavy burden of proof.” Id. at 269, 81 S.Ct. 534; see Fedorenko, 449 U.S. at 508-09, 101 S.Ct. 737 (underscoring government’s burden to prove the materiality of a false statement in a visa application in a case in which it was “seeking to revoke petitioner’s citizenship because of the alleged unlawfulness of his initial entry into the United States”); Nowak, 356 U.S. at 661, 663, 78 S.Ct. 963 (holding that the government had failed to prove by clear and convincing evidence “that Nowak had obtained his citizenship both fraudulently and illegally”). The government’s position here contradicts both the INA and the long line of precedent requiring the government to use federal judicial process and meet a high standard of proof to effectuate denatural-ization. If the government were correct that a successful administrative challenge ⅜ to a naturalization certificate or passport on the ground that it was unlawfully procured sufficed to reveal the holder’s true status as a noncitizen, obviating any need for judicial action under section 1451 to effect denaturalization, the precedents, the process provided by section 1451, and the express preservation of citizenship status in sections 1504 and 1453 would be illuso *655 ry. On the government’s logic, anyone whose naturalization the government deemed invalidly obtained would not be protected by the requirement of a court order to denaturalize, but could instead be denaturalized administratively. No court of which we are aware has accepted the contention that, in such circumstances, judicial process is unnecessary. b. The second response to plaintiffs’ due process claim hits the mark: The administrative actions that the government has thus far taken are not procedurally inadequate because they have not denaturalized the plaintiffs. In fact, the statutory authority on which the government relied is quite explicit that it authorizes only revocation of certain evidence of citizenship, not the citizenship status itself. See Gorbach, 219 F.3d at 1093 (noting that the INA “is unambiguous in not conferring upon the Attorney General the power to denaturalize citizens administratively” (emphasis omitted)). The logic of the administrative route is that it stops short of denaturalization, and thus comports with denaturalization’s more robust procedural prerequisites. As discussed above, if the government wishes to revoke a naturalized person’s status as a citizen without first criminally prosecuting her, see 18 U.S.C. § 1425, it must seek a court order under section 1451. And, according to the complaint, the only actions the government has so far concluded against these plaintiffs are administrative. Assuming, as we must, that plaintiffs were naturalized United States citizens, they retain that citizenship status until the government obtains a court order vitiating it. Administrative actions alone are inadequate to extinguish any United States citizenship plaintiffs may have. The statutory authority that permits USCIS administratively to revoke a certificate of naturalization expressly provides that such revocation “shall affect only the document and not the citizenship status of the person in whose name the document was issued.” 8 U.S.C. § 1453. The authority on which the State Department depends to cancel a passport administratively contains the same limitation. 8 U.S.C. § 1504(a). Because the administrative actions plaintiffs challenged were incapable of vitiating citizenship, plaintiffs were not entitled to de-naturalization’s pre-deprivation judicial process. Denying plaintiffs’ inadequate-process claims, however, need not leave plaintiffs in limbo. If plaintiffs believe that they are United States citizens and that USCIS erroneously invalidated their certificates of naturalization and passports, they may pursue (in the correct venue, as discussed below) the section 1503 claims in their amended complaint. Section 1503 provides for judicial review of denial of any “right or privilege” of citizenship, including inval-idations of passports or naturalization certificates. Of course, any such claim requires objectively reasonable factual and legal support. See Fed. R. Civ. P. 11(b). That said, while section 1503 provides plaintiffs an adequate avenue to assert their citizenship claims, it is not available to them in the District of Columbia. The district court correctly held that this is the wrong venue. Section 1503 requires a claimant to file in “the district in which such person resides or claims a residence.” 8 U.S.C. § 1503(a). The amended complaint states that Xia resides in Edison, New Jersey; Wei Liu resides in Los Ange-les, California, but is currently living in Beijing; and Li resides in Los Angeles, California. The complaint does not allege any United States residence for Jinsong Chen, only that he “is now living under duress in Shanghai.” Am. Compl. ¶ 78. The *656 paragraph of the complaint that identifies the Los Angeles residence of Wei Liu also mentions his wife, plaintiff Hua Chen, without specifying whether she also resides in Los Angeles, id,., but plaintiffs’, counsel confirmed at oral argument that she does not reside in Washington, D.C. Because none of the plaintiffs has alleged residence here, the District of Columbia is the wrong venue for their section 1503 action. Plaintiffs object that requiring them to seek recourse under section 1503 imper-missibly shifts the burden onto them to prove their citizenship, thus effectively depriving them of their procedural rights. See Am. Compl. ¶ 57. But we cannot say that the minimal initial showing the statute requires of a plaintiff to trigger the government’s proof burden facially invalidates section 1503 as a matter of due process, or puts it in conflict with section 1451. The threshold showing required of a section 1503 plaintiff is minimal. She or he need only show prima facie evidence of citizenship. See Perez, 356 U.S. at 47 n.2, 78 S.Ct. 568. Presenting proof of a naturalization certificate or passport—even if already administratively cancelled—would seem to satisfy that prima facie requirement. The government would then be put to its burden to establish by “clear, unequivocal, and convincing evidence” the plaintiffs lack of entitlement to the disputed “right or privilege” of citizenship. Id. c. We now consider the balance of plaintiffs’ INA claims. Plaintiffs contend that the government violated sections 1421, 1447(b), and 1451(a) of the INA. But those provisions do not apply to the conduct plaintiffs challenge here. Section 1421 grants the Attorney General the- power to naturalize individuals. 8 U.S.C. § 1421. It says nothing about de-naturalization or cancellation of certificates of naturalization. Section 1447(b) permits a person whose application for naturalization has been pending without decision to apply for a hearing before the district court “for the district in which the applicant resides.” 8 U.S.C. § 1447(b). That section is inapplicable here. Plaintiffs’ applications were not denied during the naturalization process; the government cancelled their certificates of naturalization years after they ostensibly became U.S. citizens. The government’s argument that it may treat plaintiffs as if they were never naturalized might lend some logic to plaintiffs’ invocation of section 1447(b), but we reject that argument for the reasons stated above. Plaintiffs also assert that section 1451(a) authorizes the government to seek a court order denaturalizing a citizen. 8 U.S.C. § 1451(a). In this case, however, the government did not attempt to denaturalize the plaintiffs under section 1451(a). Instead, they canceled their certificates of naturalization through an administrative proceeding under section 1453—a proceeding that, as discussed above, is powerless to bring about a denaturalization. There is, however, some resonance to the section 1451 claim insofar as that provision appears not only to authorize but to obligate the government to file in court if it has information that a certificate of naturalization may have been illegally procured. 8 U.S.C. § 1451 (declaring that “it shall be the duty of the United States attorneys for the respective districts, upon affidavit showing good cause therefor, to institute” denaturalization proceedings) (emphasis added). To the extent that the government has the requisite evidence to prove plaintiffs’ non-citizenship, the statute suggests that it should have filed a civil case under section 1451. *657 B. Administrative Procedure Act Claims This brings ns to plaintiffs’ APA claim. Under the APA, a party aggrieved by agency action may seek judicial review to set aside a final agency action that is “arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law.” 5 U.S.C. § 706(2); id. § 702. To obtain such review, the aggrieved party must show that a statute makes the agency action reviewable or, if no other statute explicitly provides for review, that it is a “final agency action for which there is no other adequate remedy in a court.” 5 U.S.C. § 704. There is no dispute that the challenged actions were final. And no argument has been made, nor does it appear, that the statutes authorizing the government to revoke the plaintiffs’ certificates of naturalization and passports independently provide for judicial review. 8 U.S.C. § 1453 (cancellation of certificate of naturalization); 8 U.S.C. § 1504 (cancellation of passport). Thus, plaintiffs may obtain judicial review under the APA so long as there is no other, adequate judicial remedy available. The complaint appears to assert an APA claim challenging as arbitrary and proeedurally inadequate the administrative revocation of the both the certificates of naturalization and the passports of all plaintiffs. Am. Compl. ¶¶ 70-71. The factual allegations specific to Xia allege that the State Department informed Xia on February 11, 2012, that it had revoked her passport because Xia’s certificate of naturalization had been canceled by USCIS, but that was untrue and thus arbitrary. Am. Compl. ¶ 19. “Actually,” the complaint alleges, at the time of the passport revocation “there was no cancellation decision in place” regarding her certificate of naturalization; USCIS did not formally cancel Xia’s certificate of naturalization until October 2, 2012. Id. When Xia sought reconsideration, the State Department informed her that she was not entitled to a post-cancellation hearing under 22 C.F.R. §§ 51.70-.74. App’x 201. Xia’s passport revocation was allegedly arbitrary because putatively based on an event that had yet to occur, and allegedly contrary to law because accomplished without the requisite administrative hearing. The district court rejected plaintiffs’ APA claims for failure to exhaust administrative remedies. Xia II, 145 F.Supp.3d at 73. We disagree, for two reasons. First, plaintiffs’ APA claims are plausibly alleged, given that the government took the position that no administrative remedies were open to them through which to seek return or reissuance of their passports. They had nothing to exhaust before filing their APA claims. Plaintiffs accordingly have a futility defense to any failure to exhaust administrative remedies regarding the passport deprivations. The State Department informed Xia that she was not entitled to any post-revocation hearing after it denied her request for the return of her passport. See App’x 201. In responding to Xia, the government cited a series of regulations, 22 C.F.R. §§ 51.70-.74, without making clear which one applied. The State Department presumably relied on the same authority regarding the other plaintiffs’ lack of any right to administrative review of their passport revocations. Section 51.70(b)(1) states that a person whose passport was denied or revoked based on “Non-nationality” is not entitled to a post-cancellation hearing. To the extent that the government relied on plaintiffs’ putative non-nationality as a reason to deny them post-deprivation process, section 51.70(b)(1) cannot bear the weight *658 that the government appears to assign it. The reasons detailed above in connection with the INA claims explain why a governmental assertion of non-nationality likewise cannot obviate a passport holder’s right to a hearing under section 51.70(b)(1). However finally it may have administratively invalidated plaintiffs’ documents, the government must do more than assume plaintiffs’ non-nationality to treat them as noncitizens. Second, and more importantly, the APA requires exhaustion of administrative remedies “only when expressly required by statute or ... an agency rule.” Darby v. Cisneros, 509 U.S. 137, 154, 113 S.Ct. 2539, 125 L.Ed.2d 113 (1993). The government argues in a footnote that plaintiffs’ APA claims are barred for failure to exhaust, Appellee Br. 27 n.8, but it points to no statute or rule requiring exhaustion in .this ease. The amended complaint seeks, among other forms of relief, an injunction instructing the Department of State to reconsider its decision to revoke plaintiffs’ passports and notify them of “the procedures to be followed for the administrative or judicial appeal.” Am. Compl. ¶ 104(E). Because the relevant law does not require exhaustion and, in any event, exhaustion would have been futile with respect to the passport invalidations, we vacate the district court’s judgment in part and remand for further consideration of the APA claims, or for transfer of those claims together with the section 1503 claims to the correct venues. C. Civil Rights Claims Plaintiffs contend that the government targeted them for adverse treatment based on their Chinese ethnicity and nationality in violation of 42 U.S.C. §§ 1981 and 1983. The district court dismissed those claims on the ground that sections 1981 and 1983 apply only to actions taken under color of state, not federal, law. Xia II, 145 F.Supp.3d at 73. On appeal, plaintiffs do not challenge the district court’s determination that the government’s conduct falls outside the scope of section 1983—nor could they, as section 1983 does not apply when federal officials act under color of federal law. Jones v. Horne, 634 F.3d 588, 594 n.2 (D.C. Cir. 2011); Williams v. United States, 396 F.3d 412, 414-15 (D.C. Cir. 2005). In any event, plaintiffs do not seek damages. Whatever constitutional support they invoke for their claims for injunctive relief does not depend on section 1983. Plaintiffs, aided on these issues by ami-cus Center for Individual Rights, focus instead on the section 1981 claim. Section 1981 guarantees to “[a]ll persons within the jurisdiction of the United States” the “same right” as white citizens enjoy “to make and enforce contracts ... and to the full and equal benefit of all laws and proceedings” as well as equal “punishment, pains, penalties, taxes, licenses, and exac-tions.” 42 U.S.C. § 1981(a). In the Civil Rights Act of 1991, Congress amended various civil rights laws in an effort to “strengthen and improve” them. The Act amended section 1981 in two ways, first by rejecting the narrow interpretation, in Patterson v. McLean Credit Union, 491 U.S. 164, 109 S.Ct. 2363, 105 L.Ed.2d 132 (1989), of the section 1981 right to “make and enforce contracts,” and, second, by forestalling any construction of that statute as inapplicable to private actors. In the course of deciding Patterson, the Court had sua sponte ordered reargument on whether it should overrule Runyon v. McCrary’s holding that section 1981 “reaches private conduct.” 427 U.S. 160, 173, 96 S.Ct. 2586, 49 L.Ed.2d 415 (1976); see Patterson v. McLean Credit Union, 485 U.S. 617, 617, 108 S.Ct. 1419, 99 *659 L.Ed.2d 879 (1988) (restoring case for reargument); CBOCS West, Inc. v. Humphries, 553 U.S. 442, 450, 128 S.Ct. 1951, 170 L.Ed.2d 864 (2008) (“Congress passed the Civil Rights Act of 1991 with the design to supersede Patterson”). In response to Patterson’s reading of section 1981 not to prohibit on-the-job racial harassment, Congress added section 1981(b), specifying that ‘“make and enforce contracts’ includes the making, performance, modification, and termination of contracts, and the enjoyment of all benefits, privileges, terms, and conditions of the contractual relationship.” Id.; see Civil Rights Act of 1991, Pub. L. No. 102-166, § 101, 105 Stat. 1071, 1071-72 (codified at 42 U.S.C. 1981(b)). And, because the Court had seemed poised to overrule Runyon, Congress added subsection (c), declaring that the rights identified above are “protected against impairment by nongovernmental discrimination and impairment under color of State law.” § 101, 105 Stat. at 1072 (codified at 42 U.S.C. § 1981(c)); see also 137 Cong. Rec. 30,630, 30,678 (Nov. 7, 1991) (Statement of Rep. Hyde) (“[Tjhis section of the Act codifies the holding of Runyon v. McCrary, under which section 1981 prohibits private, as well as governmental, discrimination.”) (citation omitted); 137 Cong. Rec. 28,999, 29,034 (Oct. 30, 1991) (Statement of Sen. Dole) (same). The district court held that subsection (c) limits section 1981 to claims against private parties or state actors, excluding federal actors. Xia I, 73 F.Supp.3d at 44. Before the 1991 amendment, however, the Supreme Court had treated section 1982, which “closely parallel[s]” section 1981, Jones v. Alfred H. Mayer Co., 392 U.S. 409, 441-42 n.78, 88 S.Ct. 2186, 20 L.Ed.2d 1189 (1968), to apply to “federal as well as state” discrimination, District of Columbia v. Carter, 409 U.S. 418, 422, 93 S.Ct. 602, 34 L.Ed.2d 613 (1973). Plaintiffs challenge the district court’s holding that federal discrimination is no longer covered, contending that Congress did not intend its affirmation in subsection (c) of section 1981’s application to private and “State” actors implicitly to eliminate claims based on the exercise of federal governmental authority. The district court’s narrower view would, anomalously, make section 1981 inapplicable to territories, a result in tension with subsection (a)’s coverage of all persons “in every State and Territory.” The 1991 Civil Rights Act should not, plaintiffs say, be read to effect by implication such a momentous repeal. See Appellants’ Br. 39-41; Amicus Br. for Ctr. for Individual Rights 16-22. We have not had occasion to decide whether the Civil Rights Act of 1991 affected section 1981’s coverage of federal government discrimination, and we find no occasion to do so here because plaintiffs have “not nudged [their] claims of invidious discrimination across the line from conceivable to plausible.” Iqbal, 556 U.S. at 680, 129 S.Ct. 1937. In pleading a claim under section 1981, the “plaintiffs’] initial burden is not onerous.” Nanko Shipping, U.S.A v. Alcoa, Inc., 850 F.3d 461, 467 (D.C. Cir. 2017). They must allege only facts that, “accepted as true,” suffice to “state a claim to relief that is plausible on its face.” Iqbal, 556 U.S. at 678, 129 S.Ct. 1937 (quoting Twombly, 550 U.S. at 570, 127 S.Ct. 1955). The allegations of discrimination in the amended complaint are so threadbare, however, that they do not meet even that low burden. 2 *660 Plaintiffs acknowledge that the government asserted it cancelled plaintiffs’ certificates of naturalization for the nonracial reason that former USCIS employee Robert Schofield issued them unlawfully. Other than the conclusory allegation that the “defendants acted under color of law ... to discriminate on the basis of race and original ethnicity, by denying their full and fair proceedings,” Am. Compl. ¶ 97, no factual allegation in the complaint suggests plaintiffs were targeted because they were Chinese. Their corresponding briefing—asserting that the government’s “taking” of their “property and liberty rights” and failure to afford them due process “may have been motivated by the Appellant’s color, race, ethnicity and of their national origin,” Appellant Br. 26—is speculative and vague. The most concrete basis plaintiffs identify for their claims of discrimination is a chart that purports to list denaturalized former U.S. citizens, many of whom were implicated in the commission of war crimes. App’x 161-82. Plaintiffs assert without factual support that the list contains over a hundred “similarly situated persons of other” (ie., non-Chinese) “original ethnicity” who were denaturalized via valid processes not equally offered to the plaintiffs. Am. Compl. ¶ 34. That chart (which appears to have been copied from Wikipedia) 3 and plaintiffs’ associated allegations fail to identify the listed individuals’ ethnicities or the process they received before being denaturalized. “The complaint and supporting materials simply do ‘not permit the court to infer more than the mere possibility of misconduct.’ ” Atherton v. D.C. Office of Mayor, 567 F.3d 672, 688 (D.C. Cir. 2009) (quoting Iqbal, 556 U.S. at 679, 129 S.Ct. 1937). We therefore affirm the district court’s dismissal of plaintiffs’ Civil Rights Act claims on the alternative ground that they are not adequately pleaded. See EEOC v. Aramark Corp., 208 F.3d 266, 268 (D.C. Cir. 2000) (“[B]ecause we review the district court’s judgment, not its reasoning, we may affirm on any ground properly raised.”). III. Conclusion We affirm the district court’s judgment insofar as it dismissed the due process and INA claims that plaintiffs are entitled to a judicial determination of the validity of the cancellations of their certificates of naturalization and passports. We also affirm the district court’s dismissal of the claims under 42 U.S.C. §§ 1981 and 1983 on the ground that the complaint fails plausibly to allege ethnicity discrimination. And we affirm the district court’s decision that the section 1503 claims may only be resolved in the districts in which the plaintiffs reside. See 28 U.S.C. §§ 1406,1631. We reverse the district court’s dismissal of the APA claims, including the district court’s associated conclusion that the 8 U.S.C. § 1503 claims of all plaintiffs except for Lihong Xia are barred by a failure to exhaust; no exhaustion bar applies here. *661 Plaintiffs say that they are stranded. With no certificates of naturalization and no passports, they cannot fully exercise the rights and privileges of U.S. citizenship. Yet it appears that, at least unless and until they are denaturalized here, the Chinese government will not reinstate their Chinese citizenship. According to plaintiffs, that renders them effectively stateless. But assuming, as discussed above, that they were naturalized, plaintiffs have not yet been denaturalized. The government has a strong interest in promptly clarifying the plaintiffs’ status, and where grounds for denaturalization appear, the government should initiate denaturalization proceedings under 8 U.S.C. § 1451(a). Or the plaintiffs themselves may trigger a resolution of their dilemma under 8 U.S.C. § 1503 by pursuing, in the appropriate venues, their claims that they have been denied “a right or privilege as a national of the United States,” and thereby put the government to its proof that they are not citizens. 8 U.S.C. § 1503(a). The district court should consider on remand whether it is in the interest of justice to transfer plaintiffs’ section 1503 claims to the appropriate venues rather than dismissing them. We note that it is our normal practice “to transfer the entire case,” rather than severing the claims that were properly raised in this venue—here, the APA claims. Cameron v. Thornburgh, 983 F.2d 253, 257 n.5 (D.C. Cir. 1993). Our decision today is without prejudice to plaintiffs’ ability to seek leave to file amended complaints in the correct venues to clarify and develop their APA and section 1503 claims. So ordered. Footnotes [1] See Plea Agreement, United States v. Schofield, No. 06-CR-427, Doc. 32 (E.D. Va. Nov. 30, 2006); see also Jerry Markon, Immigration Official Pleads Guilty to Falsifying Documents, The Washington Post, Dec. 1, 2006, http ://www. washingtonpost. com/wp-dyn/ content/article/2006/11/30/AR2006113000603. html (last accessed July 26, 2017). [2] An additional reason makes it inappropriate to decide an important question of statutory interpretation in this case. Plaintiffs seek only injunctive relief, not damages, and injunctive relief is unquestionably available against federal officials for violation of the Fifth Amendment's Due Process Clause, including its equal protection component. Thus, if plaintiffs *660 plausibly alleged discrimination based on their ethnicity, the court could grant them the relief they seek without regard to whether discrimination by federal actors creates an entitlement to damages under section 1981. See Adarand Constructors, Inc. v. Pena, 515 U.S. 200, 213, 115 S.Ct. 2097, 132 L.Ed.2d 158 (1995) (claim for injunctive relief for racial discrimination "arises under the Fifth Amendment to the Constitution”); Navab-Safavi v. Glassman, 637 F.3d 311, 318-19 (D.C. Cir. 2011) (acknowledging availability of constitutional claim against the federal government of discrimination because of ethnicity or national origin). [3] List of denaturalized former citizens of the United States, .Wikipedia, available at https:// en.wikipedia.org/wiki/List_of_denaturalized_ former_citizens_oLthe_United_States (last accessed July 11, 2017).