The number of times Dallas ISD police reported using force on students doubled in recent years, according to a report released Wednesday.
Police used force in Dallas schools 204 times in 2014-15, up from 106 in 2011-12. In two cases, the students were just 6 years old, according to a joint report by the nonprofits Texas Appleseed and Texans Care for Children.
The report also found that black students in Dallas ISD were disproportionately issued tickets and complaints. Nearly half went to African-American students though they make up less than a quarter of the district's enrollment.
The "Dangerous Discipline" report examined school records from 72 districts, as well as ticketing information and county court documents to see how Texas used police in schools from the 2011-12 school year to 2014-15. They found that many turned to law enforcement instead of school staff.
Dallas ISD police chief Craig Miller said the vast majority of 'use of force' cases involved restraining students, such as when breaking up fights or stopping kids from hurting themselves. The department does not use tasers but does issue officers pepper spray, though that use is very rare.
He said the district's numbers are up because since he took charge of the department in 2011, he's pushed for a more accurate reporting. That means labeling any incident where a student is restrained as a use of force.
Dallas school officials say they're committed to changing how children are disciplined by relying more on interventions and less on police. The district will consider new preventative measures next month, including district-wide training on behavior and social-emotional interventions.
"We can all get better in how we equip staff to deescalate situations before they get out of hand," said Leslie Stephens, Dallas ISD's executive director of school leadership.
Across the state, the advocacy groups found a significant drop in the number of tickets issued to students since 2013 legislation that banned police from citing students for disrupting class. The number of charges issued against Texas students dropped 50 percent in the following year. But other disturbing trends continue, said Yamanda Wright, director of research for Texas Appleseed.
"While there are fewer students in the school-to-prison pipeline we still have significant numbers of students getting tickets and having to go to adult court for simply misbehaving," Wright said. Research repeatedly shows that such heavy-handed measures do little to correct kids' bad behavior and only gets them on track to dropping out and having more problems with the law, she said.
The report found that the number of disorderly conduct tickets was increasing. Wright worries schools are shifting minor, nonviolent behavior problems to that offense, essentially replacing the disrupting class offense. The two advocacy groups are urging lawmakers to ban citations for disorderly conduct at schools as well.
Texas districts spent far more on police officers -- an average of $1.4 million -- than they did on counselors (an average of $534,000) who are better trained to work with troubled youth.
And minority students were much more likely to get harsher punishments, facing more arrests, court referrals and use of force than their peers for similar offenses.
For example, 12-year-old African-American children were sent to juvenile probation at rates similar to older white teens in 2015. Black students overall were referred to juvenile probation nearly three times the rate as white students while Latino students were referred at about twice the rate as their white peers.
Miller said that while he wasn't aware of the specifics for the two incidents involving 6-year-olds, officers aren't staffed at elementary schools. They are only called in when situations escalate.
"If a student was trying to harm themselves or having a violent episode, then it wouldn't be unheard of for police officers to be called in to help restrain them to prevent them from harming themselves or others," Miller said, adding that his officers can't arrest children younger than 10.
Miller noted that when he arrived to the district, DISD was issuing about 4,000 tickets a year. The change in the law helped get that number down to fewer than 1,000, Miller said. Now issuing a ticket rarely happens, he said.
The report praised Dallas' use of restorative discipline -- now at 21 schools -- and urged other districts to implement the practice. Staff at those schools are trained to have children talk through situations and build strong relationships with their peers. Dallas schools that use restorative discipline saw a nearly 70 percent reduction in suspensions, according to the report.
A task force reviewing DISD's discipline is set to make recommendations to the board next month that are aimed at further reducing suspensions, particularly for the youngest children. While it's costly to implement the restorative discipline methods, some have been copied elsewhere. The task force is recommending that the entire district receive some form of training, particularly on behavior interventions and support.
Dallas trustee Miguel Solis, whose push to ban suspensions of the district's youngest children led to the discipline task force, said the report is a stark reminder that drastic changes are needed across the state.


Demonstration of C. burnetii in a clinical specimen by detection of antigen or nucleic acid.
Clinically compatible or epidemiologically linked case with a single supportive Immunoglobulin G (IgG) or Immunoglobulin M (IgM) titer.
A febrile illness usually accompanied by rigors, myalgia, malaise, and retrobulbar headache. Severe disease can include acute hepatitis, pneumonia, and meningoencephalitis. Clinical laboratory findings may include elevated liver enzyme levels and abnormal chest film findings. Asymptomatic infections may also occur.
Potentially fatal endocarditis may evolve months to years after acute infection, particularly in persons with underlying valvular disease. A chronic fatigue-like syndrome has been reported in some Q fever patients.


text:
Opponents taunted with "Trail of Tears" sign
A High School Football Team Taunted A Rival Team Named The Indians With A "Trail Of Tears" Banner
Update: The school later apologized.
By Ryan BroderickThis photo was posted on Tumblr over the weekend. It was taken at McAdory High School in McCalla, Ala.
The blogger who posted the picture, fiftyfourfortyorfight, wrote that as of Sunday the school has not addressed it and that local media hasn't covered either.
Last night, this sign went up at a McAdory High School football game.
I am absolutely disgusted that this sign was allowed to go up, and that it was not stopped by school administrators, and that after this, no one has mentioned it.
The school and the students have shown no remorse for the sign (as expected) and the students have claimed ignorance and/or that it was just a "joke".
Sorry, but the Indian Removal Act of 1830 and the death of thousands of Native Americans is not a joke.High School Football Team Taunts 'Indians' Opponent With 'Trail Of Tears' Banner
By Travis WaldronSchool officials apologized Sunday in a statement on the McAdory web site.
"This was not condoned by the school administration, the Jefferson County Board of Education or the community," McAdory principal Tod Humphries said in the statement . "The person who would normally be responsible for approving such signs is out on maternity leave, and I take full responsibility that arrangements were not made to have the signs pre-approved before the ballgame. Please accept our sincere apologies to the Native American people and to anyone who was offended by the reference to an event that is a stain on our nation's past forever."
Humphries said the school's social studies and history teachers would re-teach or review lessons on the 1830 Indian Removal Act that created the Trail of Tears.
This incident, though, is the epitome of the basic problem with the prevalence of Native American imagery in sports. When we turn Native Americans into mascots, we put them in a class with the Philly Phanatic or generic Bulldogs and Tigers rather than remembering that they are a people who have survived—and are still dealing with the effects of—real atrocities and terrible policies that aren't in any way similar to the outcome of a high school football game.Principal Apologizes for 'Trail of Tears' Banner, Makes It a Teaching Moment
By Vincent SchillingMonday, McAdory High School Principal Tod Humphries issued an apology on the school's website and today he reached out to ICTMN. He said he wanted to ensure the public he felt remorseful about the incident and that the sign was a mistake, not malicious.
"I knew when the sign popped up that it was a mistake. The woman that oversees this was on maternity leave, but I know this is not an excuse. I don't know what else to say other than it was wrong," Humphries said.
"That is not what we are. The adults in the audience and in the stands understood immediately when the sign went up that it was wrong. I know this perception is not out there right now, but it is not who we are."
Humphries expressed concern that his school would be seen as a stereotypical Alabama "redneck" school that did not care about the history of Indians. Humphries says nothing could be further from the truth and that the school is extremely diverse.
"We are a very diverse school, with 40 percent African-American, 15 percent Hispanic, rich and poor and everybody gets along. We are probably the most diverse school in our district. Our school is also very family oriented," Humphries said.
"Most people in the South are part Native American. If you asked our classes who has Native American ancestry, about half the class will raise their hands. The Creeks were here—the Cherokee and the Scots-Irish came in here and intermarried. Most of us here have Native American blood, however ignorance can still slip in about the history of us," said Humphries.
Humphries also said the moment, though difficult, was an opportunity for teaching.
"We are going to take buses and travel Friday to Gadsden, Alabama to visit the Native American man who has a Indian Removal Act Museum," Humphries said. "We will be taking the cheerleaders and the student government."
Natives respond
Cherokee Nation responds to offensive Trail of Tears referenceCherokee Nation Principal Chief Bill John Baker issued the following statement.
Ironically, the Cherokee Nation is commemorating the 175th anniversary of the start of our Trail of Tears this year. About 16,000 Cherokees began the trek to Oklahoma from our homelands in Alabama, Georgia, Tennessee, North Carolina, South Carolina and Kentucky, but only 12,000 lived through the harsh conditions that winter.
The Trail of Tears was arguably the most horrific period in the Cherokee Nation's history and among the worst atrocities ever sanctioned by the United States government.
The legacy of that terrible era has had a profound effect on generations of tribal citizens, and still lingers today.
This unfortunate display shows how much improvement is still needed in the understanding of Native peoples, our triumphs and our challenges, both historical and modern.
We hope this becomes an opportunity for administrators at McAdory High School, and at schools all across the United States, to teach our young people not only the terrible history behind the Indian removal era, but also the resilience of tribes across the nation.Trails of Tears Lesson: Anti-Semitism, Gay Hatred, Native "Learning Opportunity?"
By Linda SacksIt is unbelievable to write off the genocide known as the Trail of Tears as a "learning opportunity." This cheerleading squad glorified the horrific massacre of my ancestors for the sake of sports and the 2nd round of playoffs.
Despite its form and despite the ignorance claimed, they directly praised and glorified the murdering of a people group that still exists…my family and all that comprise the Nations of Cherokee, Chickasaw, Choctaw, Seminole, and Creek. We, natives, are not something of the past and a history lesson.
McAdory, you say, "sorry" and "reteach?" What exactly are you teaching them?
When it comes to sports, political correctness is applied selectively. What if the words "rape" and "murder" were used? These terms are used to describe how awful the opponent suffered on the playing field or court, expressing the brutality of which one team "destroys" another. Anyone in the sports world can testify to this, as do I, therefore finding the cheerleaders' actions not guilty of ignorance, but fully charged with the lack of conscience for Native American people."Trail of Tears" Signs Mocking Genocide at Multiple High Schools Point to Epidemic of Racism and Insensitivity Against Native Americans
By Danielle MillerHow could anyone think that mocking genocide is acceptable in any context? I don't understand how thought processes can be so disconnected. Football games are not a place where racism gets to be excused. People certainly wouldn't allow anyone to mock 9/11, Hiroshima, or the Holocaust. If there was a sign about lynching at a football game it wouldn't be a joke. Even some black people with the shared history of oppression defend the issue and basically deem Native Americans unimportant. Why is the genocide and continued marginalization of Native Americans considered to be a "joke"? Has America devolved back to the era of Assimilation and Termination of Natives?
Why are all these administrators and educators ALLOWING this to happen? Clearly there must be institutional racism taking place. Schools also handle this situations terribly with apologies which put the blame on those victimized by racism. Their apologies are always something along the lines of: "We're sorry YOU were offended. We will reteach about the Trail of Tears." Great for you to emphasize that WE are offended, rather than taking responsibility. The acts of racism themselves are far more harmful than being "offended" or calling them out will ever be. Obviously repeating a lesson will not help the situation, if its colonized content was part of the reason this occurred in the first place.
It appears that America is harboring subconscious, engrained racism towards Native Americans; their actions are showing it. No matter what excuse or intentions they claim to have. If you act racist, you are perpetuating racism, period. The new racism is the denial of racism. People believe if they defend racism and deny that it is racist, it justifies them in whatever they do. That is completely absurd. If you are dehumanizing or marginalizing a race of people, congratulations--you are being racist! That is a fact, not an opinion!Comment: Not everyone emphasized the point, but again, the opposing team's nickname was the Indians. These "Indians" received this death-dealing threat because of their stereotype-inducing identity. "We're gonna kill you, fake Indians, just like we did the real Indians!"
This incident is a good example of what happens when we treat Indians as mascots and other stereotypical figures. No one treats the Jewish Holocaust lightly anymore, but Indians are still something of a national joke.
They're the silly savages who got in the way of progress. We smile at their antics: the leathers and feathers, the whoops and dances, the painted faces and birds on the heads. They're like Elmer Fudd against Bugs Bunny or the Coyote against the Roadrunner: potentially deadly but in reality hapless.
When Americans wear phony headdresses or laugh at a "Trail of Tears" sign, they're not taking Indians seriously. They're not recognizing the Indians' pain or even acknowledging their existence. Therefore, it's not surprising that Americans also ignore Native issues--whether it's climate change, the effects of sequestration, or violence against women. Why would anyone bother to care when the people affected are only cartoon characters?
Labels: football, mascots, sports, Stereotype of the Month, stereotypes, Trail of Tears
For more on the subject, see:
http://blog.al.com/spotnews/2013/11/after_trail_of_tears_banner_co.html
After 'Trail of Tears' banner controversy, petition asks Pinson Valley High to drop 'Indians' mascot (updated)
An online petition is asking the superintendent of Jefferson County schools to forbid Pinson Valley High School from using Indians as its school mascot.
The petition comes as a result of the recent controversy stemming from McAdory High School referencing the 'Trail of Tears' on a banner when the Yellow Jackets played Pinson Valley.
"The McAdory team was taunting the opposing team with their offending banner. The opposing team was the Pinson Valley Indians, whose homecoming float carried a child complete with fake leather fringed shirt and pants, wearing a dyed chicken feather headdress while standing next to his teepee," Weitchpec, Cal. resident Toby Vanlandingham wrote in the change.org petition.
"Also on the float was a paper chain made with white, black, red and yellow links, the four colors of the medicine wheel. In Native American spirituality, the Medicine Wheel represents harmony and connections and is considered a major symbol of peaceful interaction among all living beings on Earth. This is another shining example of how Indian mascots are in no way "honoring" any native American Indian, living or deceased, and is just a blatant form of accepted racism that needs to end," Vanlandingham wrote.
Stereotypical Dress-Up Fridge Magnets
Mastodon's stereotypical Thankgiving t-shirt
The #1 Thanksgiving myth
Best Thanksgiving cartoons 2013
Indians in Macy's parade 2013
The rage of angry white men
"Ask a Slave" on Indians
Thanksgiving pub crawls in Indian costumes
Codetalker stunt doesn't mollify "Redskins" critics
Miley Cyrus erects $25,000 teepee
Redskins honor Navajo codetalkers
Katy Perry in yellowface
Wrongheaded obsession with "vanishing" tribes
"Land O' Takes"
Reviews of The Inconvenient Indian
Kennedy's record on Indians
"Drunken Indians" invalidate land claim?!
Targeting the Redskins' corporate sponsors
"Alcoholic" inserted in list of tribes
Second "Trail of Tears" banner displayed
"Colonial Bros and Nava-Hos" frat party
Myths about Indians and alcohol
Colleges ban peace pipe, invite Churchill
Pocahotties show depth of microaggressions
Zuckerberg's "Chief Running Site"
Loup-Noir
"Rock Your Mocs" Day
Racist attempts to ban True Diary
Burroughs's The War Chief
Review of Houdini Pie
Oneida Indians thank Obama re "Redskins"
"Dreamcatcher and skull" clothing line
Crazy Horse play lacks drama
Mazinbiige comic-book collection
Wandering Bear in Curb Your Enthusiasm
10 things Christians got horribly wrong
Lots of Lakota documentaries
Natives protest Crazy Horse play
Natives protest Yum Yum logo
Hundreds protest "Redskins" in Minnesota
Tanning salon promotes Indian "color"
Toothpaste commercial shows stereotypical costume
Conservatives suppress minority voters
Yum Yum revives "little Indian"
23rd anniversary of Dances with Wolves
Did Indians inspire Jack Kirby?
Study links racism and guns
Decades of spying on minorities
Skye & Chang
Vanity Fair's "favorite" Indian costume

redpajama_set_name: RedPajamaCommonCrawl


This study examines how components of strategic entrepreneurship (exploration and exploitation) relate to Russian SMEs performance during the economic crisis and to what extent combinations of firm resources determine these relationships. In order to address these issues we surveyed 651 Russian private SMEs. Our results show that during the economic crisis exploitation is positively associated with SME's performance. However, we found positive association of exploration with SME's performance during the economic crisis instead of negative association. Our results also indicate that relationship between exploration as well as exploitation and firm performance is dependent on different combinations of firm resources.
Shirokova, G. & Ivvonen, L., 2016. "Performance of Russian SMEs during the economic crisis: The role of strategic entrepreneurship," Working Papers 6454, Graduate School of Management, St. Petersburg State University.
Belinda Luke & Martie-Louise Verreynne, 2006. "Exploring strategic entrepreneurship in the public sector," Qualitative Research in Accounting & Management, Emerald Group Publishing, vol. 3(1), pages 4-26, April.
Pissarides, Francesca, 1999. "Is lack of funds the main obstacle to growth? ebrd's experience with small- and medium-sized businesses in central and eastern europe," Journal of Business Venturing, Elsevier, vol. 14(5-6), pages 519-539.
Ardichvili, Alexander & Cardozo, Richard & Ray, Sourav, 2003. "A theory of entrepreneurial opportunity identification and development," Journal of Business Venturing, Elsevier, vol. 18(1), pages 105-123, January.
Sascha Kraus & Ilkka Kauranen & Carl Henning Reschke, 2011. "Identification of domains for a new conceptual model of strategic entrepreneurship using the configuration approach," Management Research Review, Emerald Group Publishing, vol. 34(1), pages 58-74, January.
Paunov, Caroline, 2012. "The global crisis and firms' investments in innovation," Research Policy, Elsevier, vol. 41(1), pages 24-35.
Meuleman,M. & Amess, K. & Wright, M. & Scholes, L., 2008. "Agency, strategic entrepreneurship and the performance of private equity backed buyouts," Vlerick Leuven Gent Management School Working Paper Series 2008-05, Vlerick Leuven Gent Management School.
Sea-Jin Chang & Arjen van Witteloostuijn & Lorraine Eden, 2010. "From the Editors: Common method variance in international business research," Journal of International Business Studies, Palgrave Macmillan;Academy of International Business, vol. 41(2), pages 178-184, February.
Filippetti, Andrea & Archibugi, Daniele, 2011. "Innovation in times of crisis: National Systems of Innovation, structure, and demand," Research Policy, Elsevier, vol. 40(2), pages 179-192, March.
Webb, Justin W. & Ketchen Jr., David J. & Ireland, R. Duane, 2010. "Strategic entrepreneurship within family-controlled firms: Opportunities and challenges," Journal of Family Business Strategy, Elsevier, vol. 1(2), pages 67-77, June.
Boone, Christophe & Wezel, Filippo Carlo & van Witteloostuijn, Arjen, 2013. "Joining the pack or going solo? A dynamic theory of new firm positioning," Journal of Business Venturing, Elsevier, vol. 28(4), pages 511-527.
Kaarlo Paloniemi & Ville-Veikko Piispanen, 2015. "An alternative construction of opportunity-seeking action for strategic entrepreneurship," International Journal of Human Resources Development and Management, Inderscience Enterprises Ltd, vol. 15(2/3/4), pages 221-232.
James G. March, 1991. "Exploration and Exploitation in Organizational Learning," Organization Science, INFORMS, vol. 2(1), pages 71-87, February.
Davide Antonioli & Massimiliano Mazzanti & Paolo Pini, 2010. "Productivity, innovation strategies and industrial relations in SMEs. Empirical evidence for a local production system in northern Italy," International Review of Applied Economics, Taylor & Francis Journals, vol. 24(4), pages 453-482.
Valentina Hartarska & Claudio Gonzalez-Vega, 2006. "What Affects New and Established Firms' Expansion? Evidence from Small Firms in Russia," Small Business Economics, Springer, vol. 27(2), pages 195-206, October.
Achim Schmitt & Gilbert Probst & Michael L. Tushman, 2010. "M@n@gement in times of economic crisis: Insights into organizational ambidexterity," Post-Print hal-00771162, HAL.
Zi-Lin He & Poh-Kam Wong, 2004. "Exploration vs. Exploitation: An Empirical Test of the Ambidexterity Hypothesis," Organization Science, INFORMS, vol. 15(4), pages 481-494, August.
Shepherd Dhliwayo, 2014. "Entrepreneurship and Competitive Strategy: An Integrative Approach," The Journal of Entrepreneurship, Entrepreneurship Development Institute of India, vol. 23(1), pages 115-135, March.
Anderson, Brian S. & Eshima, Yoshihiro, 2013. "The influence of firm age and intangible resources on the relationship between entrepreneurial orientation and firm growth among Japanese SMEs," Journal of Business Venturing, Elsevier, vol. 28(3), pages 413-429.
Zahra, Shaker A., 1993. "Environment, corporate entrepreneurship, and financial performance: A taxonomic approach," Journal of Business Venturing, Elsevier, vol. 8(4), pages 319-340, July.
Duane Ireland, R. & Webb, Justin W., 2007. "Strategic entrepreneurship: Creating competitive advantage through streams of innovation," Business Horizons, Elsevier, vol. 50(1), pages 49-59.
Johan Wiklund & Holger Patzelt & Dean Shepherd, 2009. "Building an integrative model of small business growth," Small Business Economics, Springer, vol. 32(4), pages 351-374, April.
John Connaughton & Ronald Madsen, 2009. "Regional implications of the 2001 recession," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 43(2), pages 491-507, June.
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:sps:wpaper:6454. See general information about how to correct material in RePEc.


text:
Haines joins ranks of legends
The Living Legends of Aviation award honors people of "extraordinary accomplishment in aviation," and each year brings new names of inspiring, dedicated, and immensely skilled individuals into the league. The event is produced by Kiddie Hawk Air Academy—a nonprofit organization that introduces grade school-age children to aviation, and seeks to inspire them with the Kiddie Hawk Trainer—and nominees are selected by previous inductees.
The organization meets yearly to recognize individuals who have made significant contributions to aviation and confer a variety of awards. This year's gala was hosted by John Travolta, the organization's official ambassador of aviation.
Haines said in his speech that he was honored to receive this recognition and expressed gratitude to his mentors and the opportunities aviation journalism has afforded him over the years.
"Thirty-seven years in aviation journalism has allowed me to travel the world in all manner of airplanes and, hopefully, inspire a few others along the way," he said.
Haines joined the AOPA staff as an associate editor in 1988, and in 1994 (at 33 years old) he became the youngest person to ever lead a major aviation magazine. He has flown more than a hundred models of general aviation aircraft on five continents, and shared priceless aviation experiences with thousands of readers and viewers. Throughout it all, he has maintained a dedication to future generations of flight.
"For a long time, those of my generation in aviation journalism have lamented that there didn't seem to be a new generation coming along to replace us—in part because there were fewer and fewer jobs available as publishers cut back. Before I left AOPA, I wanted to make sure that we could make a place for the next generation and I'm so proud of how that has played out."
Haines also thanked his wife, Brenda; daughters Lauren and Jenna; and the media staff at AOPA in his speech.
Other 2023 inductees to Living Legends include Greg Evans, chairman of Universal Weather and Aviation; Alan Eustace, a pilot and Google executive who accomplished the highest human free-fall; and Jared Isaacman, a pilot and commercial astronaut who took the first all-private, nonmilitary crew into orbit. This year, honorees included former astronaut Buzz Aldrin and actor William Shatner—a private pilot and the oldest living person to travel to space—who received the Aviation Inspiration and Patriotism Award.
Other AOPA personalities honored at the annual gala are President Mark Baker in 2015, and longtime AOPA Pilot columnist and AOPA Foundation Legacy Society Chairman Barry Schiff, who was inducted among the Living Legends of Aviation in 2012, joining a list that includes such renowned names such as Steven F. Udvar-Hazy, Maj. Gen. Carl McNair, Harrison Ford, Patty Wagstaff, and Brig. Gen. C. E. "Bud" Anderson.


You have to write the same (long) XPath expression over and over again on different places in the same pipeline (especially in p:choose) or in different pipelines. This is both boring and error-prone, but since there is no possibility to declare your own functions in XProc, there is no way out with standard XProc syntax.
Sometimes you would like to use functions, that are not even covered by XPath 2.0′s function library and cannot be expressed by combining these functions. This is getting better with XPath 3.0′s much larger function library, but whenever there is a standard library, at one time or the other you will think of a function, not expressible using the functions in the standard.
Importing functions from Java packages.
Before we discuss these ways of declaring your own function for MorganaXProc, there is a caveat: Using self defined functions in your pipelines will make them unusable on other XProc processors and make it harder to deploy your pipelines to other users. But keeping that in mind, let us see how to do it.
Supposing you are somewhat familiar with XQuery, you will know about XQuery library modules: You can declare variables and functions in a library module and import it into the main module of your query. You have to declare a target namespace for the library module and make sure all of the module's functions and variables are in that namespace. The target namespace is also used to import the library module's functions and variables into your main module.
where prefix "mox" is bound to MorganaXProc's namespace "http://www.xml-project.com/morgana". You can now call all functions declared in the imported library module in the XPath expressions of pipeline by using their qualified name, so make sure you have declared the module's target namespace in your XProc pipeline.
Let us look at this in some more detail: The first thing you might have noticed is the attribute "content-type", that is not defined in Recommendation 11 May 2010. It allows you to specify the mime type for the resource to import. The default value for attribute "content-type" is XProc mime type "application/xproc+xml", which will import an XProc library as you might expect. To import an XQuery module, you have to use XQuery mime type "application/xquery" as seen in the example above.
Now, what about the attribute "href" when importing an XQuery module? You can give the uri of the query module to be imported and MorganaXProc will use the same mechanism to obtain the source you know from importing XProc step libraries: If the uri is relative, it is made absolute by using the base-uri of "p:import". This also means that MorganaXProc's security mechanism is applied to importing XQuery modules in the same way as it is used for importing pipelines: You have to allow the import of an XQuery module in the same way as allowing an XProc step library to be imported.
If you want to import the XQuery functions from MorganaXProc's implementation of the EXPath packaging system, the import is somewhat different as the packaging system uses the target namespace to identify the module to be imported. Therefore you have to specify the target namespace of the module to be imported as value for attribute "href" in the XProc import statement.
In addition to extension attribute "mox:content-type" MorganaXProc uses the optional extension attribute "mox:namespace" allowing you to make sure, the target namespace of the imported XQuery module is as expected. Just specify the namespace you expect on "mox:namespace" and MorganaXProc will raise a static error (mox:S0002) if the imported module does not have the specified target namespace.
If MorganaXProc is unable to import the XQuery module, either because it cannot resolve the module's source or because the import is not allowed by MorganaXProc's security system, a static error (mox:S0001) is raised.
The XQuery functions are always evaluated by MorganaXProc's built-in XQuery processor, so choosing another XQuery processor for "p:xquery" does not apply to function import. This means you cannot use any extensions implemented by the chosen third-party XQuery processor in your functions.
As with xquery modules the value given for "href" is checked against the security system and may related to a resource in an EXPath package or related to an XMLCatalog.
If the given resource is not found or can be compiled using the selected XSLT compiler, a new error "mox:S0005″ is raised.
Using XQuery functions in XProc makes it a lot easier to write effective pipelines, but it also has its obvious limits because there are a lot of use cases, where you cannot express a function using XQuery. As we said above, with XPath 3.0 there is a much improved and enlarged function library, but there will be still cases, where you will wish for some other way to express your functions.
As you can see, we again use the extension attribute "mox:content-type" to import the functions. As we want to import functions written in Java, we use the mime-type "application/java-archive" to tell MorganaXProc to look into a Java archive (commonly known as "JAR"-file) and import the functions found there. To tell MorganaXProc from which class we want to import the functions, we use attribute "href" by giving the fully qualified name of the java class (the full name of the package the class belongs to, and the name of the class itself).
Now, what happens: If MorganaXProc's compiler gets to a "p:import" with the java archive mime-type, it will take the value of attribute "href" to obtain the named class from a ".jar"-files in folder "Extensions" next to "MorganaXProc.jar" on your local file system. In fact, MorganaXProc will look into all ".jar"-files in folder "Extensions" to find the Java class with the given fully qualified name. So the name of the ".jar"-file does not matter, MorganaXProc will take the first class matching the given class name. And: MorganaXProc expects the found class to implement interface "com.xml_project.morganaxproc.extensions.FunctionPackage". If MorganaXProc is unable to find a class with these properties, static error "mox:S0003″ is raised.
If everything went right, you can now use all functions declared in the function package in the XPath expressions of your XProc pipelines. To call them, you have to use the namespace declared in the function package, so make sure you have this namespace also declared in your pipeline. To make the namespace of the imported functions more obvious when looking at the pipeline, you can -as with XQuery functions- use extension attribute "mox:namespace" to flag the namespace of the functions. This will also tell MorganaXProc just to import the function if they are declared in this namespace. If any other namespace is found, static error "mox:S0002″ is raised.
The scope of the imported functions is limited to XPath expressions in XProc itself, so the functions are not visible either in p:xquery or p:xslt. If you need a function to be visible in XProc pipelines, XQuery expressions within XProc and also in XSLT stylesheet within p:xslt, you can load this function globally by using property "ExtensionLibrary" in configuration. This will make the function useable without further import in the XPath expressions of XProc and also in p:xquery (only with MorganaXQueryConnector and SaxonXQueryConnector) and in p:xslt (only with SaxonXSLTConnector). Please note that the function will have no access to the dynamic and static context in XQuery and XSLT.
The last thing to keep in mind is that using XPath functions obtained from a java package is controlled by the security system built in to MorganaXProc. In order to use Java code in your XProc pipeline, you have to set security system's property "JavaLoadAllowed" to true. If you try to import Java functions without the property set to true, MorganaXProc's compiler will raise static error "mox:S0003″.


text:
Jeep patriot 2010 sport
Jeep patriot 2010 sport. Used 2010 Jeep Patriot Sport for Sale Near Me 2019-02-12
Tuesday, February 12, 2019 8:48:12 AM Marquis
The recall began on August 15, 2017. Chrysler's recall number is N01. Competitors for the better-equipped Patriot Limited include the and the capable Limited. The 4×4 variants offer only the 2. Intros and redesigns continued, including such knockouts as the redesigned Forester, Chevrolet Equinox and Tucson.
Used 2010 Jeep Patriot For Sale
Remedy Chrysler will notify owners, and dealers will correct the software free of charge. The Patriot looks like a shrunken down version of the Cherokee on the outside. Despite a tendency to wander a bit at highway speeds, steering is acceptable, and handling is pretty good — definitely more tidy than that of the Hyundai Tucson. Occasionally even a Jeep fan will admit to regarding the front-wheel-drive-based model as a travesty on philosophical grounds alone. Owners may contact Chrysler at 1-800-247-9753. . As a result, the Patriot looks in need of an interior redo.
Used 2010 Jeep Patriot Sport for Sale Near Me
Based on the same platform, the 2010 Jeep Patriot and Compass have similar measurements, similar price ranges and offer almost identical sets of comfort and convenience features. With the increased off-road capability engineered into it, we might have expected the Patriot's highway ride to be rougher than those of its Compass and Dodge Caliber relatives. Vehicle Details If you've spent time in most any Chrysler, Dodge or Jeep vehicle lately, the design and materials that define the Patriot's passenger cabin will likely feel familiar. I noticed the same thing in a four-cylinder Nissan Altima, but it was much less apparent there. With the Patriot Sport 4×2 you have your choice of either the 2. The Subaru Forester is capable of duty beyond the basic off-pavement trail, but it lacks the additional low gear that facilitates climbing steep inclines and scrambling over larger obstacles.
The in-dash multimedia system included a well-executed navigation system with a free year of Sirius Traffic Service. Owners may contact Chrysler customer service at 1-800-853-1403. Either engine comes with a standard five-speed manual transmission. The recall began June 21, 2013. Along with Good scores in front-, side- and rear-impact crash tests, the Top Pick distinction requires a Good rating in the roof-strength test, which all five best-sellers lack. But the next place where I managed to buy a car was scrupulous about upholding arrangements as we put the deal together. Some of the standard and optional features that count as bright spots include comfortable seats, a fold-flat front passenger's seat, 115-volt power outlet, auxiliary audio input, outward-projecting rear speakers and a removable and washable vinyl cargo floor.
Chrysler's recall number is N01. There are more available options now as well as driver and front passenger seats get active head restraints standard. Owners may contact Chrysler at 1-800-247-9753. As with all such devices, the unique behavior of the Patriot's two available continuously variable transmissions can take some getting used to. The recall began on August 15, 2017.
The recall began June 21, 2013. Owners may contact Chrysler at 1-800-247-9753. So why would Jeep produce such similar vehicles? Antilock brakes are standard, but the front-drive Sport trim level has rear drums. The compromise seems to have been made in the cornering department; wisely, where we wouldn't expect or require much from a Jeep anyway. As a result, vehicle occupants have an increased risk of injury in a crash. Whereas the Compass's styling trends toward the softer side of Jeep design, the 2010 Jeep Patriot's decidedly squarer lines and boxier stance evoke the purpose-built style of the now-defunct Cherokee and, to a lesser degree, its Grand Cherokee successor.
RHV CARFAX
As it turns out, the Patriot might be the most comfortable cruiser of the three. Even at low speeds it exhibits a faint chugga-chugga, like a distant diesel, as it revs, and the noise penetrates the cabin. Chrysler's number for this recall is S61. Where the Patriot falls flat is in interior quality, from the noise to the materials quality. The 2010 Jeep Patriot, like the Liberty, has the rugged looks of what you expect from a Jeep and definitely has some of the characteristics of the ultra popular from the past. To make your best deal, be sure to check our Fair Purchase Prices, which reflect real-world transaction prices being paid in your area. Boy, have times ever changed.
Where the Cherokee has leather seating, nicer interior materials and a cleaner overall look, the Patriot has none of that. Interim letters informing owners that parts are not available yet were mailed on October 26, 2016. Without getting into heavy-duty truck-based models like the Jeep Liberty or Wrangler, the Patriot has few peers among car-based crossovers. Owners may contact Chrysler customer service at 1-800-853-1403. Limited models are distinguished by bright inserts front and rear, bright roof rails, fog lamps, body-color side moldings and 17-inch aluminum wheels. I drove the Patriot off road after its debut and was impressed. We spoke a couple of times on the phone and I assured them the financing was coming through, and it did - when I called to confirm and arrange to complete the purchase, I was told someone else at the dealership went ahead and sold the car.
Remedy Chrysler will notify owners, and dealers will correct the software free of charge. As a result, vehicle occupants have an increased risk of injury in a crash. Show full review When people ask why Chrysler ended up in bankruptcy court, I say it was a history of too little, too late. But the interior leaves a lot to be desired. Formally known as the Mondial de l'Automobile, the biannual Paris motor show is the home turf for Citroen, Peugeot, and Renault; and each French automaker is planning several concept and production-car debuts.
Our test vehicle had the primary engine, a 172-hp, 2. The recall began June 21, 2013. Our owner reviews and the emails we receive are predominated by people who have owned many Jeeps and admittedly love Jeeps. Our test vehicle had the primary engine, a 172-hp, 2. Otherwise the engine is fairly quiet. It hadn't taken longer than we agreed it might take - they just ignored the arrangement. Just the thing for a drive to New York City for the festivities, right? Was not impressed w the return callers lack of knowledge about the car I was asking about.


Want to lose weight while still gaining speed? Don't diet, just pedal—these four workouts will help you get there.
Why it works: Before breakfast, your energy stores are only about a quarter to a third full, so your body is forced to burn primarily fat for fuel if you don't eat.
How to do it: Once or twice a week, have only black coffee (it releases stored fats into your bloodstream for quicker access and makes your effort feel easier) then ride, says Gale Bernhardt, two-time US Olympic cycling coach. (We recommend Bicycling's own Puncheur brew.) Save breakfast for afterward. Out for longer than 90 minutes? Start fueling after 75 minutes to avoid bonking.
Why they work: Bernhardt calls max-intensity efforts "miracle intervals" because of how effectively they burn fat and boost muscle-building human growth hormone.
How to do it: Once or twice a week, warm up, then do 30 seconds all out followed by 4 minutes and 30 seconds of easy spinning; then 20 seconds all out, 4:40 easy; 10 seconds all out, 4:50 easy. Repeat two more times. Cool down.
Why they work: One study found that when cyclists upped their cadence from 50 to 110 rpm, their energy demands increased tenfold, boosting calories burned. Spinning faster, rather than grinding a higher gear, also keeps your legs feeling fresh longer.
How to do it: Twice a week, as part of a longer ride, warm up for 15 minutes, then pedal just over your comfortable rate for five minutes—your heart rate should rise slightly. Reduce your cadence back to your comfort level for five minutes. Repeat two more times. Cool down.
Why it works: Riding even 10 minutes here and there helps keep your metabolism humming so that when you're back at a desk or on the couch, you burn more calories than if you hadn't ridden. One study also found that participants reported feeling less hungry in the afternoon after doing intermittent bouts of exercise throughout the day.
How to do it: For trips under five miles, forgo your car or public transit and ride your bike.
Get the Power to Gun It!


text:
We'd love for you to contribute to our source code and to make this even better than it is
today! Here are the guidelines we'd like you to follow:

##  Coding Rules

React-Setup uses `pre-git` as a git hook to run unit tests, check for lint errors and make sure commit message follow the proper format.

To ensure consistency throughout the source code, keep these rules in mind as you are working:

* All features or bug fixes **must be tested** by one or more specs.
* All public API methods **must be documented** with jsdoc.
* All files must be linted.

##  Git Commit Guidelines

We have very precise rules over how our git commit messages can be formatted.  This leads to **more
readable messages** that are easy to follow when looking through the **project history**.

The commit message formatting using ([Commitizen](https://github.com/commitizen/cz-cli)).

### Commit Message Format

```
<type>: (<scope>:) <subject>
```

The **header** is mandatory and the **scope** of the header is optional.

Any line of the commit message cannot be longer 100 characters! This allows the message to be easier
to read on GitHub as well as in various git tools.

### Revert
If the commit reverts a previous commit, it should begin with `revert: `, followed by the header of the reverted commit. In the body it should say: `This reverts commit <hash>.`, where the hash is the SHA of the commit being reverted.

### Type
Must be one of the following:

* **feat**: A new feature - should have a ticket number
* **fix**: A bug fix - should have a ticket number
* **docs**: Documentation only changes
* **style**: Changes that do not affect the meaning of the code (white-space, formatting, missing
  semi-colons, etc)
* **refactor**: A code change that neither fixes a bug nor adds a feature
* **perf**: A code change that improves performance
* **test**: Adding missing tests
* **chore**: Changes to the build process or auxiliary tools and libraries such as documentation
  generation

### Scope
The scope could be anything specifying place of the commit change. For example: component, homepage, about, router, server, build, etc...

### Subject
The subject contains succinct description of the change:

* use the imperative, present tense: "change" not "changed" nor "changes"
* don't capitalize first letter
* no dot (.) at the end

redpajama_set_name: RedPajamaGithub


text:
\section{Introduction}
The ever-expanding interconnection of social, email, and media service platforms presents an opportunity for adversaries manipulating networked data to launch malicious attacks~\cite{goodfellow2014explaining,aggarwal2015outlier,yan2018deep,pang2018towards}. Adversarially perturbed or simply anomalous graph data may disrupt the operation of critical machine learning {algorithms} with severe consequences. Detecting anomalies in graph data is of major importance in a number of contemporary applications such as flagging ``fake news,'' unveiling malicious users in social networks, blocking spamming users in email networks, and uncovering suspicious transactions in financial or e-commerce networks~\cite{akoglu2015graph,yan2016robust}.  Detecting these anomalous nodes can be formulated as a learning task over an attributed graph.

Before positioning our work in context, we highlight different types of graph-based anomalies. \emph{Homophilic} anomalies characterize nodes whose attributes are dissimilar to those of their  neighbors~\cite{perozzi2016scalable,mcpherson2001birds}. These nodes violate the homophily property that postulates neighboring vertices to have similar attributes, and is heavily employed in semi-supervised learning (SSL)~\cite{smola2003kernels,kipf2016semi,gleich2015pagerank,kloster2014heat}. In a social network of voters for example, friends typically belong to the same voting party; see Fig.~\ref{fig:anom_vot}. Oftentimes, anomalous nodes may form dense connections giving rise  to clustered homophilic anomalies Fig.~\ref{fig:anom_clust}.
\emph{Structural} anomalies correspond to nodes with attributes that are dissimilar to structurally similar nodes~\cite{eberle2007discovering}.
Structural similarity among nodes suggests that vertices involved in similar graph structural patterns possess related attributes~\cite{donnat2018learning}. In an academic collaboration network for instance, nodes with similar graph structure (central nodes) have similar labels (e.g., professors); see Fig.~\ref{fig:anom_col}.

\begin{figure*}[t]
    \centering
    \begin{subfigure}[b]{0.25\textwidth}\hspace{-1cm}
        \includegraphics[width=1\textwidth]{figs/polit_net4.png}
        \caption{Social network of voters.}
        \label{fig:anom_vot}
    \end{subfigure}~
     \begin{subfigure}[b]{0.25\textwidth}
        \includegraphics[width=0.95\textwidth]{figs/clust_anom2.png}
        \caption{Clustered anomalies.}
        \label{fig:anom_clust}
    \end{subfigure}~
    \begin{subfigure}[b]{0.23\textwidth}\hspace{+0.5cm}
        \includegraphics[width=1\textwidth]{figs/academ_collab2.png}
        \caption{Academic network.}
        \label{fig:anom_col}
    \end{subfigure}
    \caption{Nodes in dotted square exhibit (a) (b) homophilic and (c) structural anomalies.}
    \label{fig:anom}
\end{figure*}

\subsection{Related Work}
Todays era of data deluge has grown the interest for detecting anomalies in collections of high-dimensional data~\cite{iwata2016multi,zimek2012survey}.  This paper deals with anomalies in data that exhibit inter-dependencies captured by a graph~\cite{akoglu2015graph}. The inaccessibility and prohibitive cost associated with obtaining ground-truth anomalies motivates the development of mainly unsupervised techniques.

Methods for detecting anomalies in attributed graphs can be roughly classified in three categories. \emph{Community-based} approaches find clusters of nodes and search for anomalies within each cluster. A probabilistic method is developed in \cite{gao2010community} that jointly discovers communities, and detects community outliers as anomalies. Similarly, \cite{perozzi2016scalable} identifies anomalies by measuring the attribute correlation of nodes within each node's egonet, meaning the subgraph induced by the node of interest, its one-hop neighbors, and all their connections. \emph{Subspace-based} approaches focus on spotting anomalies in subspaces extracted from the nodal features~\cite{sanchez2013statistical}.
On the other hand, \emph{model-based} methods learn an embedding per node and flag anomalies by measuring the model-fitting  error~\cite{li2017radar,ding2019deep}. A parametric model is developed in \cite{li2017radar} to capture the coherence among the attributes of nodes and their connectivity. A deep graph autoencoder is advocated in \cite{ding2019deep} that fuses attributes and connections to an embedding per node, and identifies anomalies using the reconstruction error at the decoder side. Despite their empirical success, these contemporary approaches are confronted with a number of challenges. The computational overhead associated with community detection, subspace extraction and deep learning, discourages their applicability to large-scale graphs. The
local scope of community-based methods confines the breadth of the anomaly detector that is further vulnerable to clusters of connected anomalous nodes. Finally, all aforementioned approaches ultimately learn an anomaly score that relies on attributes and connections of \emph{all} nodes. However, either the attributes or the network links for some nodes may be compromised by adversaries~\cite{zugner18adv,xu2019topology}.

\subsection{Contributions}
Addressing the aforementioned challenges, we introduce a graph random sampling and consensus (GraphSAC) framework for detecting anomalous nodes on large graphs. Instead of directly considering all nodes, our novel method samples subsets of nodes, and relies on graph-aware criteria to judiciously filter out subsets contaminated by anomalous nodes. The ``clean'' sets are utilized by a SSL module that estimates a nominal class distribution per node. The core intuition behind GraphSAC is that attributes of anomalous nodes will have poor predictive performance in a SSL task. The contribution of this work is fourfold.
i) A novel approach to estimating a class distribution per node that is guaranteed to be minimally affected by anomalous nodes; ii) A versatile framework that adapts to different types of anomalies via an application-specific SSL module (cf. Fig.~\ref{fig:anom});
iii) Scalability to large-scale graphs (complexity is linear in the number of edges); and iv) experimental evidence confirming that the novel graph anomaly detector outperforms state-of-the-art approaches in identifying clusters of anomalous nodes, as well as contemporary adversarial attacks on graph data.

\section{Graph-based Random Sampling and Consensus} Consider a graph $\mathcal{G}:=\{\mathcal{V},\mathcal{E}\}$, where $\mathcal{V}:=\{n_1,n_2,\ldots,n_N\}$ is the vertex set, and $\mathcal{E}$ the edge set of $E$ edges . The connectivity of $\mathcal{G}$ is described by an adjacency matrix ${\mathbf A}\in{\mathbb R}^{ N   \times N   }$, where $[{\mathbf A}]_{n,n'}>0$  if $(n,n')\in \mathcal{E}$. Each node $n\in\mathcal{V}$ is associated with one or more scalar labels $y_n\in\{1,\ldots,C\}$ that form the $N\times C$ matrix $\mathbf{Y} :=[\mathbf{y}_1^\top,\ldots,\mathbf{y}_N^\top]^\top$ with ${[\mathbf{Y}]}_{n,c}=1$, if $y_n=c$, and $0$ otherwise.

Given ${\mathbf A}$ and $\mathbf{Y}$ the goal in this paper is to detect ${K}$ anomalous nodes with indices in the set $\mathcal{A}:=\{{n}_{1},\ldots,{n}_{{K}}\}$. Such nodes are expected to violate a certain property such as homophily. To this end, we require a model that relates the graph with the labels, and promotes the desired properties.

An immediate approach is to directly consider all nodal labels and connections in a graph-based model. However, such a holistic approach will be vulnerable to the inclusion of anomalous nodes that will bias the learned model and poison the anomaly detection framework.

Instead, our idea is to sample labels $y_n$ at random subsets of nodes $n\in\mathcal{L}\subset \mathcal{V}$ and prudently discard contaminated subsets. Given $\mathcal{L}$,
we  perform SSL to predict the labels across all nodes. SSL methods utilize the labels at ${\mathcal L}$ along with the graph connectivity ${\mathbf A}$ to predict the labels at the unlabeled nodes $\mathcal{V}\setminus\mathcal{L}$. We draw inspiration from the random sampling approach for robust model fitting in image analysis~\cite{bolles1981ransac}. The SSL model $f(\cdot)$ utilizes the labels in $\mathcal L$ to estimate the $N\times C$ label distribution matrix as follows
\begin{align}
\label{eq:ssl}
{\hat{\mathbf P}}=f(\{y_n\}_{n\in\mathcal L},\mathbf{A})
\end{align}
where $\hat{{P}}_{(n,c)}\in[0,1]$ can be interpreted as the probability that $y_n=c$. Henceforth, for notation brevity we define the SSL model as follows $f({\mathcal L}):=f(\{y_n\}_{n\in\mathcal L},\mathbf{A})$. The choice of $f(\cdot)$ is dictated by specific properties one may want to capture; see also Fig. \ref{fig:anom}.

Nevertheless, if $\mathcal{L}\cap\mathcal{A}\ne\emptyset$, the predicted label distributions will be affected by the anomalous nodes. To bypass this hurdle, we formulate a hypotheses test to assess if anomalies are present in $\mathcal{L}$ by evaluating the predictive SSL performance instantiated with $\mathcal{L}$, namely $f({\mathcal L})$. Our test relies on the premise that attributes of anomalous nodes will have poor predictive performance for SSL.

\begin{algorithm}[t]
\caption{GraphSAC}
\begin{algorithmic}
\STATE\textbf{Input:} $f(\cdot,\cdot)$, $\mathbf{A}$, $\{y_{{n}}\}_{{n}=1}^ N, I,  T, i\leftarrow0$
\STATE 1. \textbf{while}  $i<I$ \textbf{do}
\STATE 2. \hspace{0.1cm} Select $\mathcal{L}^{(i)}$ at random
\STATE 3. \hspace{0.1cm} Estimate ${\hat{\mathbf P}}^{(i)}_{G}=f(\mathcal{L}^{(i)})$ and  consensus set  $\mathcal{U}^*$
\STATE 4. \hspace{0.1cm} If $|\mathcal{U}^*|/N<T$ then $\delta_f(\mathcal{L}^{(i)})=0$,  otw. $\delta_f(\mathcal{L}^{(i)})=1$
\STATE 5. \hspace{0.1cm} $i\leftarrow i+1$
\STATE 6. \textbf{end while}
\STATE 7. Obtain $\hat{\mathbf{P}}_{G}$ as in \eqref{eq:grout}
\STATE 8. Obtain anomaly scores $\{\phi_{n}\}_{n=1}^N$ as in \eqref{eq:anoma_score}
\end{algorithmic}
\end{algorithm}

Our iterative algorithm termed GraphSAC is summarized as Algorithm 1. Per iteration $i$, we first sample $S$ nodes uniformly at random from $\mathcal{V}$ without replacement, that is
\begin{align}
\label{eq:samplgrsac}
\mathcal{L}^{(i)}\sim \mathrm{Unif}(\mathcal{L}_S)
\end{align}
where $\mathcal{L}_S:=\{ \mathcal{L}\subseteq \mathcal{V} : |\mathcal{L}| = S \}$ is the set of all $S-$size subsets.
Given the labels in $\mathcal{L}^{(i)}$,  the SSL model~\eqref{eq:ssl} outputs the predicted label distribution matrix ${\hat{\mathbf P}}^{(i)}_{G}:=f({\mathcal L}^{(i)})$.
Nodes whose labels are correctly predicted by $f({\mathcal L}^{(i)})$ form the consensus set  $\mathcal{U}^*:=\{n: c'=\arg\max_{c}{[\hat{\mathbf P}}^{(i)}_{G}]_{n,c},~\text{ and }~y_n=c'\}$.

Next, GraphSAC compares the accuracy of $f({\mathcal L}^{(i)})$ using e.g., the ratio of nodes in the consensus set to a {prespecified} threshold $T$. If $|\mathcal{U}^*|/N>T$, GraphSAC decides that ${\mathcal L}^{(i)}$ does not contain anomalies, meaning $\delta_f(\mathcal{L}^{(i)})=1$; otherwise, the set is contaminated with anomalies and filtered out, that is $\delta_f{(\mathcal{L}^{(i)})}=0$. The following test of hypotheses is performed
\begin{align}
\label{eq:graphsacdetect}
    \left\{
\begin{array}{ll}
    H_0:~~\delta_f(\mathcal{L}^{(i)})=1,~~~~\text{if}~~~|\mathcal{U}^*|/N>T \\
    H_1:~~\delta_f(\mathcal{L}^{(i)})=0,~~~~\text{otherwise}.
\end{array}
\right.
\end{align}
Essentially, this test filters out subsets that are contaminated with anomalies $\mathcal{L}\cap\mathcal{A}\ne\emptyset$, and will bias the learned model.
Hence, $\delta_f(\cdot)$ corresponds to a filter that aims to retain only ``clean'' sets i.e. $\mathcal{L}\cap\mathcal{A}=\emptyset$.
We will elaborate on the performance of this filter in Section 3. The resulting sample average of the nominal label distribution is given by
\begin{align}
\label{eq:grout}
	    \hat{\mathbf{P}}_{G}=\frac{\sum_{i=1}^I f({\mathcal L}^{(i)})\delta_f{(\mathcal{L}^{(i)})}}{\sum_{i=1}^I\delta_f{(\mathcal{L}^{(i)})}}.
\end{align}
Even though  $\mathcal{L}^{(i)}$ are drawn uniformly at random \eqref{eq:samplgrsac}, $\delta_f(\cdot)$ introduces a sampling bias towards ``clean'' subsets. Consequently, $\hat{\mathbf{P}}_{G}$ is minimally affected by anomalous nodes and represents the  nominal class distribution.

Finally, we select as anomalous the nodes with the largest distance between their nominal distribution and their actual labels.   GraphSAC estimates an  $N\times 1$ anomaly score vector $\bm{\phi}(\hat{\mathbf{P}}_{G})$ with entries
\begin{align}
\label{eq:anoma_score}
\phi_{n}=\text{dist}(\hat{\mathbf{p}}_{n}^{G},\mathbf{y}_{n}),~~~~\forall n \in \mathcal{V}
\end{align}
where
$\hat{\mathbf{p}}_{n}^{G}$ is the $n$-th row of $\hat{\mathbf{P}}_{G}$, ${\hat{ \mathbf{p}}}_{n}^{(i)}$ is the $n$-th row of ${\hat{\mathbf P}}^{(i)}_{G}$,  and dist$(\cdot,\cdot)$ is the cross-entropy loss Therefore, $\phi_{n}$ is larger if $n$ does not adhere to the graph-related properties promoted by the  SSL model.
Hence, we rank the nodes in decreasing order with respect to $\phi_n$, and select the first K nodes as anomalous. Fig~\ref{fig:encoder} illustrates the GraphSAC operations.

\begin{figure*}\centerin
    \input{figs/graphsacoper.tex}
	\caption{An illustration of the operation of GraphSAC.  The first row represents the available graph and labels. The second row shows the sampled labels. The third row contains the SSL module that outputs the predicted labels, where green dotted lines indicate incorrectly classified nodes. The filter in the fifth row decides whether  $\mathcal{L}^{(i)}$ contains anomalies or not. The predictions with a larger number of missclasified nodes are discarded (colored red). The final anomalies are detected by combining the predictions from the ``clean'' subsets.} \label{fig:encoder}
\end{figure*}

Instead of using as many nodes as possible to obtain the solution, GraphSAC relies on small sets of $S$ nodes and SSL-aided hypotheses testing to avoid subsets contaminated with anomalous nodes. The small sample size ($S\ll N$) enables GraphSAC to remain operational even under adverse conditions where $K$ is relative large. GraphSAC's robustness is justified since only one ``clean'' ${\mathcal L}^{(i)}$ is required for a valid $\hat{\mathbf{P}}_G$~\eqref{eq:grout}.

The computational complexity of GraphSAC per $i$ is dictated by the label prediction step $f({\mathcal L})$ that scales linearly with the number of edges $\mathcal{O}(E)$ for scalable  SSL  methods~\cite{zhu2003semi,chapelle2006}. Further, since the draws $\mathcal{L}^{(i)}$ are independent, each GraphSAC iteration $i$ can be readily parallelized, thereby ensuring scalability to large-scale graphs.

Notice that so far $f(\cdot)$ is not specified. Hence, GraphSAC may adapt to the pertinent type of anomalies (see Fig.~\ref{fig:anom}) by appropriately choosing the model $f(\cdot)$. {Homophilic} anomalies for example, call for SSL methods e.g. diffusion-based classifiers \cite{zhu2003semi,chapelle2006} or contemporary graph convolutional neural networks (GCN)s~\cite{kipf2016semi}. On the other hand, {structural} anomalies necessitate models that promote structural similarities among nodes such as the work in~\cite{donnat2018learning}.

\section{Analytical guarantees}
This section strengthens our proposed randomized anomaly detection framework with analytical guarantees. Towards streamlining the analysis, we interpret the filter $\delta_f(\cdot)$ as introducing a sampling bias to the uniform sampling scheme in~\eqref{eq:samplgrsac} towards ``clean'' subsets.\footnote{An alternative analysis accounting directly for $\delta_f(\cdot)$ is in Section D of the supplementary material.}  Specifically, is rewritten $\hat{\mathbf{P}}_G$ as
\begin{align}
\label{eq:altgrout}
    \hat{\mathbf{P}}_{G}&:=\frac{1}{I}\sum_{i=1}^I
    f({\mathcal L}^{(i)}) \\
    \shortintertext{where
    $\mathcal{L}^{(i)}\sim p_G(\mathcal{L})$
     are drawn from the GraphSAC biased sampling scheme
    instead of~\eqref{eq:samplgrsac} with}
\label{eq:grsamplalt}
 p_G(\mathcal{L})&=
    \begin{cases} p_d(\mathcal{L}),& \forall\mathcal{L}\in \bar{\mathcal{L}}_S\\
    p_{f}(\mathcal{L})
    ,&\forall\mathcal{L}\in \bar{\mathcal{L}}_S^c
    \end{cases}
\end{align}
where  $\bar{\mathcal{L}}_S$ is a set of nodal subsets with no anomalous nodes $\bar{\mathcal{L}}_S:=\{ \mathcal{L}\subseteq {\mathcal{L}}_S , \mathcal{L}\cap \mathcal{A} = \emptyset \}$, while the complementary set $\bar{\mathcal{L}}_S^c$ contains all the remaining size-$S$ subsets  $\bar{\mathcal{L}}_S^c:={\mathcal{L}}_S \setminus  \bar{\mathcal{L}}_S$. Hence, $p_G(\mathcal{L})$  is related to the filter \eqref{eq:graphsacdetect} through
\begin{align}
\label{eq:con_det_pmf}
p_d(\mathcal{L})&=p(\delta_f(\mathcal{L})=1|\mathcal{L}\in \bar{\mathcal{L}}_S)p(\mathcal{L}\in \bar{\mathcal{L}}_S)\\
p_f(\mathcal{L})&=p(\delta_f(\mathcal{L})=1|\mathcal{L}\in \bar{\mathcal{L}}^c_S)p(\mathcal{L}\in \bar{\mathcal{L}}^c_S)\nonumber
\end{align}
where $p(\mathcal{L}\in \bar{\mathcal{L}}_S)={|\bar{{\mathcal{L}}}_S|}/{|{\mathcal{L}}_S|}$ and $p(\mathcal{L}\in \bar{\mathcal{L}}^c_S)={|\bar{{\mathcal{L}}}_S^c|}/{|{\mathcal{L}}_S|}$ in accordance with the uniform sampling \eqref{eq:samplgrsac}.
Notice that for this section all $I$ samples are included in the sample average \eqref{eq:altgrout}, but if the sample is contaminated, i.e. $\mathcal{L}\in \bar{\mathcal{L}}^c_S$, $\mathcal{L}$ will have a smaller probability to be sampled.
GraphSAC aims at a class distribution per node that is not affected by the anomalous nodes, but takes into account only the nominal nodes, and can thus be readily utilized for anomaly detection. Hence, the desired probability matrix is
\begin{align}
\label{eq:altpnraphsac}
    \mathbf{P}_{N}&:=\mathbb{E}_{\mathcal{L}\sim p_N}[f({\mathcal{L}})] \\
    \shortintertext{where ${\mathcal{L}}$ are drawn uniformly
    from
    $\bar{\mathcal{L}}_S$ that is}
   \label{eq:altsampl} p_N(\mathcal{L})&=
    \begin{cases} \frac{1}{|\bar{\mathcal{L}}_S|},&\forall\mathcal{L}\in \bar{\mathcal{L}}_S\\
    ~~0,&\forall\mathcal{L}\in \bar{\mathcal{L}}_S^c \;.
\end{cases}
\end{align}
Indeed, $ \mathbf{P}_{N}$ captures the nominal class distribution per node that is not affected by the anomalous nodes and conforms to the properties promoted by the SSL model.
As a result, the largest entries in the anomaly score vector $\bm{\phi}(\mathbf{P}_{N})$ (cf. \eqref{eq:anoma_score}) represent the anomalous nodes.

However, direct estimation of  $\mathbf{P}_{N}$ is not feasible since  $\mathcal{A}$ is unknown. If on the other hand all nodes are directly accounted for, anomalous ones will be included that will in turn bias the learned probability matrix. To obviate this hurdle,
GraphSAC introduces  \eqref{eq:graphsacdetect} to filter out contaminated subsets, giving rise to the biased sampler in~\eqref{eq:grsamplalt}.
GraphSAC's ultimate target is the expected probability matrix
\begin{align}
    \label{eq:altpgraphsac}
        \mathbf{P}_{G}:= \mathbb{E}_{\mathcal{L}\sim p_G}[ f(\mathcal{L})].
\end{align}
Upon considering $p_f(\mathcal{L})=0,~\forall\mathcal{L}\in \bar{\mathcal{L}}^c_S$ and  $p_d(\mathcal{L})=1/|\bar{\mathcal{L}}_S|,~\forall\mathcal{L}\in \bar{\mathcal{L}}_S$, as well as expanding the expectation in \eqref{eq:altpgraphsac} and \eqref{eq:altpnraphsac}, GraphSAC's expected probability matrix reduces to the desired one, meaning $\mathbf{P}_{G}=\mathbf{P}_{N}$. This corresponds to a perfect filter in \eqref{eq:graphsacdetect} that disregards all contaminated subsets $\delta_f(\mathcal{L})=0, \forall\mathcal{L}\in \bar{\mathcal{L}}^c_S$, and retains all the clean ones $\delta_f(\mathcal{L})=1, \forall\mathcal{L}\in \bar{\mathcal{L}}_S$.\\
\noindent
Thus,  GraphSAC's performance is directly related to the distance among $\hat{\mathbf{P}}_G$ and $\mathbf{P}_{N}$
\begin{align}
    \text{TV}(\hat{\mathbf{P}}_G,\mathbf{P}_{N})&:=\|\hat{\mathbf{P}}_G- \mathbf{P}_{N}\|_1\\&\le
    \label{eq:triang_ineq}\|\mathbf{P}_G- \mathbf{P}_{N}\|_1+
    \|\hat{\mathbf{P}}_G- \mathbf{P}_G\|_1
\end{align}
where \eqref{eq:triang_ineq} follows from the triangle inequality, and $\|\mathbf{Z}\|_1$ represents the sum of the absolute values of the $\mathbf{Z}$ entries.
Adhering to \eqref{eq:triang_ineq}, the following research questions have to be addressed to  characterize the performance of GraphSAC.
\begin{itemize}
\item[\textbf{RQ1}.] How $\|\mathbf{P}_G- \mathbf{P}_{N}\|_1$ relates to the filter performance? and
\item[\textbf{RQ2}.] How  $\|\hat{\mathbf{P}}_G- \mathbf{P}_G\|_1$  evolves as the number of draws $I$ increases?
\end{itemize}
The following analysis aspires to provide tangible answers to aforementioned questions. First, consider a simplified version of $p_G(\mathcal{L})$ given by
\begin{align}
\label{eq:pgrsampfin}
 p_G(\mathcal{L})&=
    \begin{cases} d,& \forall\mathcal{L}\in \bar{\mathcal{L}}_S\\
   {f}
    ,&\forall\mathcal{L}\in \bar{\mathcal{L}}_S^c \;.
    \end{cases}
\end{align}
which implies that any clean (contaminated) subset in $\bar{\mathcal{L}}_S$ ($\bar{\mathcal{L}}^c_S$) has the same sampling probability ${d}$ ($f$). This approximation suggests that GraphSAC samples all contaminated samples with a certain probability, and all non-contaminated with a different one (cf. \eqref{eq:con_det_pmf}). Extended analysis on a refined sampling scheme different from \eqref{eq:pgrsampfin} is included in Section D of the supplementary material, e.g. if a subset contains a large number of anomalies, the probability this sample is rejected is higher relative to a sample with only one anomaly.

\begin{theorem} (Proof in Section A of the supplementary material.) Let $\mathbf{P}_A:=\mathbb{E}_{\mathcal{L}\sim\text{Unif}(\bar{\mathcal{L}}_S^c)}\big[ f(\mathcal{L})\big]$ denote the expected distribution when anomalies are sampled.
It then holds for the total variation distance between $\mathbf{P}_{G}$ and $\mathbf{P}_{N}$ that
\begin{align}

    \|\mathbf{P}_G- \mathbf{P}_{N}\|_1
    =&\frac{|\bar{\mathcal{L}}_S^c|^2}{|{\mathcal{L}}_S|}p_{fa}\|\mathbf{P}_A -\mathbf{P}_{N}| \!\lceil_1\\=&|\bar{\mathcal{L}}_S^c|f\|\mathbf{P}_A -\mathbf{P}_{N}| \!\lceil_1
\end{align}
where $p_{fa}:=p(\delta_f(\mathcal{L})=1|\mathcal{L}\in \bar{\mathcal{L}}^c_S)$ is the probability of false alarms for \eqref{eq:graphsacdetect} that can be also expressed as $p_{fa}=({|{\mathcal{L}}_S|}/{|\bar{{\mathcal{L}}}_S^c|})f  $
with $|\bar{\mathcal{L}}^c_S|={N\choose S} -{N-K\choose S}$ and $|{\mathcal{L}}_S|={N\choose S}$.
\end{theorem}
\noindent Theorem 1 asserts that the desired distance is equal to the distance between the nominal distribution and the one affected by the anomalies scaled by the probability that GraphSAC fails to identify the anomalies.
An immediate observation is that for a perfect GraphSAC filter it holds that $p_{fa}=0$, and one would obtain the desired $\mathbf{P}_G=\mathbf{P}_{N}$. Another consequence of Theorem 1, is that as the number of anomalies $K$ increases, so does $|\bar{\mathcal{L}}^c_S|$ and  $\|\mathbf{P}_{G}-\mathbf{P}_{N}\|_1$, conditioned that the filter performance does not change. As demonstrated in the experiments, even if anomalous subsets are miss-classified as nominal by the filter for a specific draw, these will contain a small number of anomalies and will not affect the overall anomaly detection performance.

Towards addressing Q2 we utilize concentration inequalities theory applied to random matrices~\cite{tropp2015introduction} and establish the following.
\begin{theorem}(Proof in Section B of the supplementary material.)
With $\hat{\mathbf{P}}_{G}=\frac{1}{I}\sum_{i=1}^I\mathbf{P}^{(i)}_{G}$, where  $\mathbf{P}^{(i)}_{G}=f(\mathcal{L}^{(i)})$ and $\mathbf{P}_{G}= \mathbb{E}_{\mathcal{L}\sim p_G}[ f(\mathcal{L})]$, it holds that
\begin{align}
    &\mathbb{E}\big\{\|\hat{\mathbf{P}}_{G}-{\mathbf{P}}_{G}\|\big\}\le\sqrt{\frac{2N\log(N+C)}{I}}+\frac{2\sqrt{N}\log(N+C)}{3I}\label{eq:normbound}\\
    \shortintertext{and for all $t>0$}
    &\mathbb{P}\big\{\|\hat{\mathbf{P}}_{G}-{\mathbf{P}}_{G}\|\ge t\big\}\le(N+C)\label{eq:propbound}
    \exp{\left(\frac{-I t^2}{N + 2\sqrt{N}t/3}\right)}.
\end{align}
\end{theorem}
All the parameters in the right hand side of \eqref{eq:normbound} and \eqref{eq:propbound} are either known or controllable, and relate to the network size $N$ and the number of classes $C$. The expectation bound \eqref{eq:normbound} suggests that by increasing the number of draws $I$ the sample average of the random matrices will approach the desired ensemble mean. On the other hand, \eqref{eq:propbound} bounds the tail of the probability distribution of the difference. It can be shown that for $t\le \sqrt{N}$ the tail probability decays as fast as the tail of a Gaussian random variable with variance proportional to $N$, while for $t\ge \sqrt{N}$ it decays as that of an exponential random variable whose mean is proportional to $\sqrt{N}$.

Retracing back to \eqref{eq:triang_ineq}, we deduce that $\|\hat{\mathbf{P}}_G- \mathbf{P}_G\|_1$ decreases for increasing $I$, whereas $\|{\mathbf{P}}_N- \mathbf{P}_G\|_1$ directly depends on the filter performance.  In practice, GraphSAC amounts to ranking the per-node anomaly scores. This ranking may be evident even for relative large distances $\|\hat{\mathbf{P}}_G- \mathbf{P}_{N}\|_1$.

\subsection{Analysis on diffusion-based SSL models}
The results presented so far hold for any SSL model even for contemporary GCNs. Next, we focus on the class of diffusion-based SSL models $f_{\text{dif}}$, which have documented success in sizable graphs due to their scalability and robustness~\cite{zhu2003semi,chapelle2006}. Most of these models can be written as
\begin{align}
\label{eq:sslmodel}
    f_{\text{dif}}(\mathcal{L}) =h(\mathbf{A})\mathbf{Y}_{\mathcal{L}}
\end{align}
where  $h$ is e.g. a polynomial function, and
$\mathbf{Y}_{\mathcal{L}}$ is an $N\times C$ matrix whose $n$-th row is $\mathbf{y}_n$ if $n\in\mathcal{L}$, and $\mathbf{0}_{C}$ otherwise. A common choice is $h(\mathbf{A})= \sum_{t=0}^T \alpha_t (\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2})^t$, where $\alpha_t >0$ and $\mathbf{D}=\text{diag}(\mathbf{A}\mathbf{1})$ denotes the degree matrix.
\begin{corollary} (Proof in Section C of the supplementary material.)
Let $f_{\text{dif}}(\mathcal{L})=h(\mathbf{A})\mathbf{Y}_{\mathcal{L}}$ with $h(\mathbf{A})=[\mathbf{h}_1,\ldots,\mathbf{h}_N]$ be the diffusion matrix, and $\mathcal{N}:=
\mathcal{V}-\mathcal{A}$ the set containing the nominal nodes.
The total variation distance between $\mathbf{P}_{G}$ and $\mathbf{P}_{N}$  is
\begin{align}
    \label{eq:finres1}
     \|\mathbf{P}_G
- \mathbf{P}_{N} \|_1=
p_{fa}\tfrac{f_{\mathcal{A}}}{|\bar{\mathcal{L}}^c_S|}
\bigg{\|}
\tfrac{K}{N-K}\sum_{n\in\mathcal{N}}
    \mathbf{h}_n\mathbf{y}_n^\top -\sum_{n'\in\mathcal{A}}
    \mathbf{h}_{n'}\mathbf{y}_{n'}^\top \bigg{\|}_1
\end{align}
where $f_{\mathcal{A}}:={N-1 \choose S-1}$  and $|\bar{\mathcal{L}}^c_S|={N\choose S} -{N-K\choose S}$.
\end{corollary}
Upon applying the reverse triangle inequality to \eqref{eq:finres1}, Corollary 1 yields
\begin{align}
     \|\mathbf{P}_N
- \mathbf{P}_{A} \|_1\ge&
\tfrac{f_{\mathcal{A}}}{|\bar{\mathcal{L}}^c_S|}
\bigg|\|\sum_{{n'}\in\mathcal{A}}
    \mathbf{h}_{n'}\mathbf{y}_{n'}^\top \|_1-
\tfrac{K}{N-K}\|\sum_{n\in\mathcal{N}}\mathbf{h}_n\mathbf{y}_n^\top\|_1\bigg|\nonumber\\
=&\tfrac{f_{\mathcal{A}}}{|\bar{\mathcal{L}}^c_S|}
\bigg|\sum_{{n'}\in\mathcal{A}}
    \|\mathbf{h}_{n'}\|_1-
\tfrac{K}{N-K}\sum_{n\in\mathcal{N}}\|\mathbf{h}_n\|_1\bigg|\label{eq:finineq}
\end{align}
where \eqref{eq:finineq} follows since $\mathbf{y}_n$ has entries either 0 or 1, and $\mathbf{h}_n$ has nonegative entries. Hence, anomalous nodes with large $\|\mathbf{h}_n\|_1$ contribute more to the error norm $\|\mathbf{P}_N-\mathbf{P}_{G} \|_1$. In diffusion-based models, nodes with larger $\|\mathbf{h}_n\|_1$ typically have higher degree. Consequently, as expected anomalous nodes with high degree have a large effect on the learned distributions.

\section{Experiments}
In this section, we compare GraphSAC with state-of-the-art alternatives under different anomaly generation models based on random walks, clustered anomalies, as well as contemporary adversarial attacks for graph data.
\begin{table}[]
    \centering
    \caption{AUC values for detecting adversarial attacks.}
    \rowcolors[]{1}{white}{gray}
    \begin{tabular}{p{1.4cm} c c c c}
    		\toprule
\texttt{Dataset} & \texttt{Citeseer} & \texttt{Polblog} & \texttt{Cora} &\texttt{Pubmed}\\%& Youtube?\\
   \midrule
    GraphSAC & \textbf{0.75} &\textbf{0.98}
&\textbf{0.80} &\textbf{0.82}
 \\
    Gae  & 0.64 &0.51 &
0.50 &0.69
\\

    Amen & 0.73 &0.89 &
0.75& 0.62
\\

    Radar& 0.67&
0.76& 0.77 &0.44
\\
    Degree & 0.58&
0.48& 0.40&0.57
\\
 Cut ratio & 0.49&
0.51&0.35&0.55
\\
Flake & 0.47&
0.61&0.46&0.60
\\
Conductance & 0.35&
0.39& 0.61&0.59
\\
		\bottomrule
    \end{tabular}
    \label{tab:adv}
\end{table}
\begin{figure*}[t]
\hspace{1.5cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_corasmall.tex}
\hspace{0.7cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_pubmed.tex}
\hspace{0.7cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_citeseer.tex}
\hspace{0.8cm}\input{figs/exp3_anomal_rw_k=10_min_d=5_polblog.tex}

\vspace{1cm}\hspace{2.3cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_blogcat.tex}
\hspace{1cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_WIKI.tex}
\hspace{1cm}
\input{figs/exp3_anomal_rw_k=10_min_d=5_homo.tex}

\vspace{1.3cm}
    \caption{AUC values for increasing number of anomalies $|\mathcal{A}|=K$. \textbf{(Top left)} Pubmed,
    \textbf{(Top middle left)} Cora, \textbf{(Top middle right)} Citeseer, \textbf{(Top right)} Polblogs,
    \textbf{(Bottom left)} Blogcat, \textbf{(Bottom middle)} Wikipedia \textbf{(Bottom right)} PPI.

    }
    \label{fig:labpert}
\end{figure*}

\noindent\textbf{Baselines}. Amen identifies anomalies by evaluating the attribute correlation of nodes per egonet of the graph~\cite{perozzi2016scalable}. The graph neural network encoder (GAE) ranks anomalies by measuring the reconstruction error recovered at the decoder
output~\cite{ding2019deep}. Radar asserts nodes as anomalous if they do not adhere to the proposed parametric model~\cite{li2017radar}. Following the experimental setup in \cite{perozzi2016scalable}, additional anomaly detection methods are considered that only utilize graph connectivity but not nodal labels, namely approaches based on the Average degree~\cite{charikar2000greedy}, Cut ratio~\cite{fortunato2010community}, Flake~\cite{flake2000efficient}, and Conductance~\cite{andersen2006local}.
Unless stated otherwise, GraphSAC  is configured with $T=0.5$, $I=50$ and the personalized PageRank (PPR)~\cite{bahmani2010fast} as the SSL model.
The different methods are evaluated using the area under the curve (AUC) of the receiver operating characteristic (ROC) curve. The ROC curve  plots the rate an anomaly is detected (true positive) against the rate a node is miss-classified as anomalous (false positive). The AUC value represents the probability that a randomly chosen abnormal node is ranked higher than a normal node.

\noindent\textbf{Datasets}. The 7 benchmark labeled graphs are Cora ($N=2708,C=7$), Citeseer ($N=3327, C=6$), Pubmed ($N=19717,C=3$), Polblogs ($N=1224,C=2$), Blogcat ($N=10312,C=39$), PPI ($N=3890,C=50$), and Wikipedia ($N=4733, C=39$). The nodes in the last three graphs are multilabel ones.\footnote{For graphs with multilabeled nodes, clustered anomalies and adversarial attacks are not defined and hence, these graphs are not included in the respecitive experiments.}

\subsection{Adversarial attacks}
We generated anomalies using the adversarial setup in~\cite{zugner18adv}, where attacks are effected on attributed graphs targeted for GCNs. We focus on structural attacks, which means that edges adjacent to the targeted node are added or removed; that is, we select a random subset of targeted nodes $\mathcal{A}$, and alter their connectivity by a sequence of structural attacks~\cite{zugner18adv}.

Table \ref{tab:adv} reports the AUC values for competing state-of-the-art techniques in detecting adversarial attacks with $K$=10 targeted nodes. As GAE relies on a deep graph autonencoder~\cite{ding2019deep}, it is maximally affected by the adversarial attacks. Our novel method outperforms all alternatives in detecting the  attacked nodes. These promising results suggest that GraphSAC can be effectively employed as a preprocessing step to flag adversarial input to a graph neural network.

\begin{figure*}[t]
\hspace{2cm}\input{figs/runtimemain.tex}
\vspace{-0.4cm}
	\caption{Runtime comparisons across different graphs for Fig.~\ref{fig:labpert}.}\label{fig:runtimemain}
\end{figure*}
\subsection{Random walk-based anomalies}
We test the algorithms in identifying homophilic random-walk based  anomalies.
To generate these we select a subset of $|\mathcal{A}|$ nodes at random, and alter their labels. For each $n \in \mathcal{A}$, we perform a random walk of length $k=10$, and replace $y_n$ with the label of the landing node. Hence, we modify the labels of the targeted nodes in $\mathcal{A}$ as prescribed by the random walk model. The resulting nodes violate the homophily property.

Fig. \ref{fig:labpert} plots the AUC values of various methods with increasing $K$ on 6 benchmark graphs.  Evidently, GraphSAC outperforms alternatives while the performance of all methods degrades slightly as $K$ increases. Furthermore, Fig.~\ref{fig:runtimemain} reports the runtime of the best performing algorithms for $K=20$ in Fig.~\ref{fig:labpert} across all graphs. Evidently, GraphSAC is significantly faster than these competing methods. For further details on these  runtime comparisons see Section E of the supplementary material.

\subsection{Clustered anomalies}
Next, we consider indentifying clusters of anomalous nodes Fig.\ref{fig:anom_clust}.  Towards generating clustered anomalies, we select a cluster of connected nodes  $\mathcal{A}$ using \cite{cordasco2010community}, and set all labels as $y_n=c, \forall n \in \mathcal{A}$, where $c$ is the least common label in $\mathcal{A}$. The anomalous nodes satisfy the homophily property inside the corrupted cluster that further challenges their detection.

Table \ref{tab:clust_anom} reports the AUC values of anomaly detection algorithms for identifying clustered anomalies. The performance of competing algorithms is heavily affected since within the affected cluster the anomalous nodes appear as nominal. On the other hand, our novel approach utilizes random sampling and consensus strategies, and markedly outperforms the baseline schemes in identifying the ground-truth anomalies.
\begin{table}[t!]
    \centering
        \caption{AUC values for discovering clusters of anomalous nodes.}

    \rowcolors[]{1}{white}{gray}
    \begin{tabular}{p{1.4cm} c c c c}
    \toprule
    \texttt{Dataset} &
    \texttt{Citeseer
    & \texttt{Polblog}
    & \texttt{Cora}
    & \texttt{Pubmed}
    \\%& Youtube?\\
    \midrule
GraphSAC & \textbf{0.88} &\textbf{0.74}
&\textbf{0.97}&\textbf{0.96}
 \\
    Gae  & 0.50 &0.30 &
0.58&0.95
\\
    Amen & 0.51 &0.10 &
0.48&0.42
\\
    Radar & 0.86&
0.40& 0.88&0.88
\\
    Degree & 0.46&
0.10& 0.45&0.29
\\
Cut ratio & 0.49&
0.08&0.40& 0.27
\\
Flake & 0.40&
0.05&0.37&0.33
\\
Conductance & 0.55&
0.55& 0.40&0.37
\\
		\bottomrule
    \end{tabular}
    \label{tab:clust_anom}
\end{table}

\noindent\textbf{Parameter sensitivity}. Sensitivity of GraphSAC to $I,T$ is reported in Fig.~\ref{fig:sens}. GraphSAC's AUC performance is stable around the preselected values. As deduced in the discussion after Theorem 2, the number of iterations $I$ for a reliable anomaly score ranking is relatively small. A large enough ratio of correctly classified nodes $T$, aides GraphSAC in discarding contaminated samples since these will result in a large number of miss-classified nodes.

\begin{figure}
    \hspace{-0.2cm}\input{figs/auc_maximum_iterations=anomal_rw_k=10_min_d=5_na=80_citeseer.tex}~
        \input{figs/auc_score_val=anomal_rw_k=10_min_d=5_na=80_citeseer.tex}

    \caption{GraphSAC's sensitivity to $I,T$  for the Citeseer dataset with $K=80$ in Fig.~\ref{fig:labpert}.}
    \label{fig:sens}
\end{figure}

\noindent\textbf{Additional SSL methods}. Fig.~\ref{fig:pol} reports the AUC for  GraphSAC when using the personalized page-rank (ppr)~\cite{bahmani2010fast} and heat-kernel (hk)~\cite{kloster2014heat} SSL methods for the experiment in Fig.~\ref{fig:labpert}. Deep SSL methods~\cite{kipf2016semi} for GraphSAC  will be part of our future research.
\begin{figure}
   \centering\input{figs/exp3_hkpr_anomal_rw_k=10_min_d=5_citeseer.tex}\vspace{0.2cm}
    \caption{Citeseer with additional SSL methods.}
    \label{fig:pol}
\end{figure}

\noindent\textbf{On the practical interpretation of Theorem 1}.
Fig. \ref{fig:auc2d} reports the AUC performance of GraphSAC for Citeseer in Fig.~\ref{fig:labpert} with varying number of anomalies $K$ and sampling size $S$, where darker boxes indicate larger values of AUC. Observe that the AUC increases for larger $S$. For larger $K$ the AUC drops as expected, but this can be rectified by increasing $S$.
Fig. \ref{fig:maxval} demonstrates the maximum number of anomalies $K_m:=\max_i K^{(i)}$ that existed in the contaminated samples that were missclasiffied as nominal $\delta(f(\mathcal{L}^{(i)}))=1$, where $K^{(i)}:=|\mathcal{L}^{(i)}\cup\mathcal{A}|$. Notice $K_m$ in Fig. \ref{fig:maxval} is significantly smaller than the total number of anomalies that is $K=17,33,83$, respectively.
Hence, even though there are contaminated samples, the number anomalies in $\mathcal{L}$ is so small that does not affect the AUC values in~Fig. \ref{fig:auc2d}. Motivated by this result, we derive  a stronger version of Theorem 1 that accounts for $K_m$ and is included in Section D of the supplementary material.

\begin{figure}[h]
    \centering

    \begin{subfigure}[b]{0.24\textwidth}\centering
        \includegraphics[width=0.6\textwidth]{figs/fi_aucexp10_score_val0.76_5_5anomal_rw_k=10_min_d=5_pct=0.08_citeseer.png}
        \vspace{-0.2cm}
        \caption{AUC values for detecting the anomalous nodes.}
        \label{fig:auc2d}
    \end{subfigure
    \begin{subfigure}[b]{0.24\textwidth}\centering
        \includegraphics[width=0.6\textwidth]{figs/fi_max_num_anomalexp10_score_val0.76_5_5anomal_rw_k=10_min_d=5_pct=0.08_citeseer.png}
                \vspace{-0.2cm}
        \caption{Maximum number of anomalies in missed $L^{(i)}$}
        \label{fig:maxval}
    \end{subfigure
            \vspace{-0.2cm}
    \caption{X-axis denotes the fraction of samples $S/N$ and y-axis represents the fraction of anomalies $K/N$. }
    \label{fig:2d}\vspace{-0.6cm}
\end{figure}

\section{Conclusion}
We introduced a graph-based random sampling and consensus approach to effectively  detect  anomalous nodes in large-scale graphs. Rigorous analysis provides performance guarantees for our novel algorithm, by bounding the number of random draws involved. GraphSAC outperforms competing algorithms in detecting random walk-based anomalies, clustered anomalies, as well as contemporary adversarial attacks for graph data. Our future research will leverage GraphSAC to guard semi-supervised learning algorithms from adversarial attacks.
\small
\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv