Neither Sweden's Security Service (Säpo) nor the police have confirmed the report, and have released few details about the arrests.
"Police suspect the men were about to carry out a terrorist attack with firearms and bombs," Gothenburg regional daily GT said in its online edition.
"Police sources have told GT the suspects are linked to the terror network al-Shabaab," the paper said, without disclosing its sources.
According to the TT news agency, the four suspects are all male between the ages of 23- and 26-years-old and are residents of Gothenburg.
Three of the men are born in Africa and the fourth in the Middle East, it said. The man born in the Middle East and two of the Africa-born men are Swedish citizens while another holds a Swedish residency permit, it added.
Swedish intelligence agency Säpo issued a short statement on Monday saying all information concerning the ongoing investigation was classified.
"Säpo's assessment is that there is no cause for widespread concern nor any reason to introduce tighter security measures," it said.
An elite counter-terrorism unit and police arrested four people in Gothenburg, Sweden's second city, and evacuated hundreds of people from a building in the city hosting an art fair "after concluding that there was a threat that could endanger lives or health or cause serious damage," officials said Sunday.
Police then searched the building thoroughly, breaking open seven lockers, the paper said.
It is not known why the venue was seen as a target, and art fair organisers have not been given an explanation, GT said.
The paper speculated that a Swedish artist who has received death threats from al-Shabaab for depicting the Prophet Muhammad as a dog had planned to attend the event but did not in the end.
"I will myself with great interest attend the event," Vilks wrote on his blog last week.
In an interview with the local Göteborgs-Posten daily he explained that he never intended to attend Saturday's inauguration, but didn't rule out that he was perhaps the intended target.
"If it is Islamists, which it seems to be, nothing is impossible," he said.
Lars Vilks has faced numerous death threats and a suspected assassination plot since his drawing of the Muslim prophet with the body of a dog was first published by a Swedish regional newspaper in 2007, illustrating an editorial on the importance of freedom of expression.
Gothenburg city officials and others have criticised Säpo for neglecting to inform the city about the planned raid, and for being so tight-lipped following the arrests.
“We would have liked to have gotten the information directly from Säpo, and not through the media,” city director Åke Jacobsson told the TT news agency.
Officials from Gothenburg and Säpo met on Monday morning to discuss the threats and ensuing arrests.
But Säpo was still refusing to offer any further details other than that four people were arrested in Gothenburg on Saturday evening.
“I can't go into any other details because of the confidentiality of the preliminary investigation,” Säpo spokesperson Michael Gunnarsson told TT.
Prosecutor Agnetha Hilding Qvarnström also refused to shed any light on the case.
Wilhelm Agrell, a professor on intelligence analysis, also made note of what he called a “total [media] blackout” on the part of Säpo regarding the case.
“Even if we've had blackouts in other terrorist cases, this one seems to go very far,” he said.
“Terror investigations can be very sensitive. You want to avoid every detail that can have a negative effect on the investigation and it can be hard to know ahead of time what sort of information has that character,” Agrell told TT.
Al-Shabaab is an al-Qaeda-linked militia has waged a years-long insurgency against Somalia's weak, western-backed transitional government and controls much of the south and centre of the Horn of Africa country.
"Wherever you are, if not today or tomorrow, know that we haven't yet forgotten about you," a Swedish al-Shabaabmember, Abu Zaid, said in a video, according to US monitoring group SITE.