The Supreme Court in Mathews v. Diaz, 426 U.S. 67 (1976) has already given you the short answer to this question: "In the exercise of its broad power over naturalization and immigration, Congress regularly makes rules that would be unacceptable if applied to citizens." It's helpful at the outset to understand what the US's immigration law are and are not---in the US system, immigration laws are not criminal laws; deportation is not a criminal penalty. On a basic level, when you immigrate to the United States, you are, in the eyes of the law, essentially entering into a contract with the government, in which the government sets specific conditions of your entry, and if you break them, the "contract" is breached, and you can be removed. This distinction is generally lost on the public, but it's extremely relevant for understanding the rights of noncitizens in the US, not only in regards to the immigration laws' impact on the First Amendment, but also the Fourth, Fixth, Sixth, and Seventh. In short, because removal proceedings are noncriminal, many protections simply do not apply the way we would imagine they would. And it's why, even though we let trade unionists into the country now, the backbone of what you're describing is still good law to this day; in 1990, Congress repealed the restrictions you identify, but they’ve never been struck down by the Supreme Court.

But let's take a step back, since by 1918 the power of the US government to exclude individuals based on their political beliefs had already been well-established. The first law (which is still on the books) is the 1798 Alien Enemies Act, which permits the internment and removal of noncitizens from countries with which the US is at war. It has been used sporadically but regularly throughout the US’s history (note that this is different from the internment of US citizens like Japanese-Americans in WWII).

From the 1870s, there are a great deal of societal changes relevant to your question. From the 1870s-1900, you see approximately 11 million people immigrate to the US, more people than had immigrated to the US than in the 17th, 18th, and first part of the 19th century combined. From 1900-1915, another 12 million would immigrate to the US. Not only is this a massive influx of people, it also included what was referred to at the time as “new immigrants”---Southern and Eastern Europeans, often Catholic or Jewish. Anti-immigrant sentiment began to rise during this period, punctuated by incidents such as the 1886 Haymarket Affair, in which several police and civilians were killed during a labor demonstration after a thrown bomb prompted gunfire exchanges. In the wake of this, six immigrants, alleged anarchists, were sentenced to death for their purported involvement in the bombing, and you see a considerable upswelling of nationalist anti-immigrant sentiment. In 1897, you have the Lattimer Massacre, in which 19 peaceful Hungarian and Polish striking miners were killed, and in 1901, you have the assassination of McKinley by the anarchist Leo Czolgosz, a natural-born American but with an uncomfortably foreign-sounding name. Throughout this period you also see the rise of nativist groups like the American Protective Association, which tended to accuse these “new” immigrants as not only being bad generally (like you still see today), but fundamentally incompatible with American governance, “politically incompetent,” easily corruptible, and eager to see American democracy subsumed into Roman (papal) rule. In 1893 you see the onset of a depression in the US economy, lasting until 1897, which results in a political realignment that is not necessarily anti-immigrant (McKinley made use of nativism when it suited him, but big-business Republicans at the time were generally in favor of the cheap labor immigration provided) but nevertheless still significant. Finally, in 1898, you have the Spanish-American War, in which the US came into possession of a colonial empire.

In the midst of these economic, social, and political changes, you see a fundamental shift in the legal conception of immigration regulation; whereas previously immigration was essentially handled by the states individually, with little to no federal involvement, in the 1880s Congress began to pass general immigration laws, including the famous Chinese Exclusion Act as well as the first general federal immigration law. By 1891, the federal government takes exclusive control over immigration from the states (opening up the famous Ellis Island in the process). Throughout this period, Congress continues to update and revise immigration laws, with ebbs and flows in power between the nativist sentiment still present and the industrial need for cheap labor. In 1903, Congress passes the Immigration Act of 1903, AKA the Anarchist Exclusion Act, which, among other things, makes anarchists inadmissible. This means that someone with preexisting anarchist beliefs would be barred from entry, and deportable if it was discovered they harbored those beliefs when they entered. A key distinction here is that it did not render noncitizens deportable for beliefs developed while in the US.

In this period, you see a series of Supreme Court cases upholding this expansion of federal power into immigration and limiting court review of federal decisions related to it and the administration of colonial territories. Of particular note are the decisions upholding the Chinese Exclusion Act, where the Court wrote that if Congress “considers the presence of foreigners of a different race in this country, who will not assimilate with us, to be dangerous to its peace and security, their exclusion is not to be stayed because at the time there are no actual hostilities with the nation of which the foreigners are subjects.” Chinese Exclusion Case, 130 U.S. 581 (1889). As the Court itself would later say, this case established that the government’s power to exclude aliens is “inherent in sovereignty, necessary for maintaining normal international relations and defending the country against foreign encroachments and dangers---a power to be exercised exclusively by the political branches of government.” Kleindienst v. Mandel, 408 U.S. 753 (1972). By 1909, the Court said that “over no conceivable subject is the legislative power of Congress more complete than it is over” the admission of aliens. Oceanic Navigation Co. v. Stranahan, 214 U.S. 320, 339 (1909). At the same time, through a series of decisions known as the Insular Cases, the Court concluded that, to use the phrasing of the time, “the Constitution did not follow the flag,” and that Bill of Rights protections did not automatically extend to foreign colonial possessions such as Puerto Rico and the Philippines.

In other words what you’re seeing in this period is the genesis of a Supreme Court doctrine whereby it generally treats issues related to foreign affairs, immigration, and the like as functionally off-limits from Court review, and more or less entirely within the control of the political branches of government (Congress and the President) a doctrine that is still alive and well today.

(1/2)

There was nothing unconstitutional about it. In fact, the Supreme Court had recently upheld a similar law.

You may be accustomed to thinking of the first amendment as a powerful restraint on the government. For its first century, the Supreme Court didn't see the matter that way and heard few first amendment cases. The original understanding of the first amendment was that it did very little, and the Supreme Court invalidated government action on first amendment grounds only very sparingly and under a set of doctrines that bear little resemblance to the contemporary rules.

Anarchists were the subject of considerable political concern around the turn of the century. Anarchist Leon Czolgosz, for example, assassinated President McKinley in 1901. Thus, the Immigration Act of 1903 excluded anarchists from immigrating to the United States along with other "undesirables" (people with epilepsy, beggars, and prostitutes).

The Supreme Court specifically upheld this provision with respect to anarchists in the 1904 case of Turner v. Williams. This case involved the deportation of anarchist John Turner. Turner, represented by Clarence Darrow, argued that his deportation violated the first amendment. The Supreme Court was openly disdainful of this claim:

It is said that the [immigration] act violates the First Amendment ... We are at a loss to understand ... this objection. [The Act] has no reference to an establishment of religion, nor does it prohibit the free exercise thereof; nor abridge the freedom of speech or of the press; nor the right of the people to assemble and petition the government for a redress of grievances.

The Court allowed that, in some sense, Turner's speech might be impacted but argued that, he had no right of free speech because he was not permitted to enter the country in the first place:

It is, of course, true that if an alien is not permitted to enter this country, or, having entered contrary to law, is expelled, he is in fact cut off from worshipping or speaking or publishing or petitioning in the country; but that is merely because of his exclusion therefrom. He does not become one of the people to whom these things are secured by our Constitution by an attempt to enter, forbidden by law.

Thus, there was no constitutional problem in the court's view with excluding anarchists. By extension, there was no constitutional problem with deporting individuals who, after they entered, were found to be anarchists. The 1918 Act tightened up the rules for excluding anarchists, but no one in Congress would have had any sense that it might be unconstitutional given the Turner decision.

As I said, this was an entirely different era of first amendment jurisprudence. A few years later, in 1919, in Schenck v. United States, the court upheld a criminal conviction for distributing leaflets that were critical of the draft. That same year, the court in Debs v. United States upheld the criminal conviction of socialist and pacifist Eugene Debs for delivering an anti-war speech.

In Gitlow v. New York (1925), the court upheld socialist Benjamin Gitlow's conviction under the New York Criminal Anarchy Law for publishing a left wing manifesto (that didn't directly advocate any kind of anti-government violence but could be generally read as supporting revolution). This era, immediately after World War I, has often been described as a low point for free speech in the United States. This is largely true, though the immediate founding period and especially the Sedition Act of 1798 (which criminalized criticism of the federal government) was probably worse.

About a decade later, the Supreme Court's first amendment jurisprudence began turning towards the more expansive protections we have today, though progress was slowing and halting until the Warren Court revolution of the 1950s-1960s. For our purposes, the most relevant case is Brandenburg v. Ohio, which effectively (though not technically) reversed those post-WWI cases by holding that the government could only prosecute speech intended to incite imminent lawless action (and not general or philosophical arguments that might tend in that direction).

But bear in mind that in the immigration context, we're not talking about prosecuting anyone. In fact, the basic contours of Turner v. Williams are still good law today. The courts have held that the government has exceptionally broad and often unreviewable discretion to exclude noncitizens from entering the country (and to deport those found to have entered in violation of the rules). The gist of the argument here is that a noncitizen has no right to enter the country, and so no constitutional rights can be violated if the government denies someone entry. In 1972, in Kleindeinst v. Mandel, for example, the court upheld the government's right to deny communists entry.

I don't think I'm allowed to comment on more recent cases, but to this day, there's no reason to suspect that the court would wish to overrule Turner.

Isn't there a pretty clear parallel between the reaction post 9/11 to the perceived threat of militant Islam with the creation of completely new categories of enemy and a total discarding of legal process for many people and their imprisonment in places like Guantanamo, and the reaction to anarchist ideologies after a couple of high profile assassinations in the early twentieth century?